2011 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology

Independent Component Analysis based Seeding method for k-means Clustering
Takashi Onoda
System Engineering Lab.
Central Research Institute Electric Power Industry
Tokyo, JAPAN
Email: onoda@criepi.denken.or.jp

Miho Sakai
Department of Computational Intelligence and Systems Science
Tokyo Institute of Technology
Yokohama, JAPAN
Email: sakai@ntt.dis.titech.ac.jp

Seiji Yamada
Digital Content and Media Sciences Research Division
National Institute of Informatics
Tokyo, JAPAN
Email: seiji@nii.ac.jp

Abstract—The k-means clustering method is a widely usedclustering technique for the Web because of its simplicity andspeed. However, the clustering result depends heavily on thechosen initial clustering centers, which are chosen uniformly
at random from the data points. We propose a seeding method
based on the independent component analysis for the kmeans clustering method. We evaluate the performance of our
proposed method and compare it with other seeding methods
by using benchmark datasets. We applied our proposed method
to a Web corpus, which is provided by ODP. The experiments
show that the normalized mutual information of our proposed
method is better than the normalized mutual information of
k-means clustering method and k-means++ clustering method.
Therefore, the proposed method is useful for Web corpus.

It is difficult to find relevant data in search
results because the searched results are
mixed many kinds of data.

It is easy to understand topic andsystematically explore search results.

Keywords-independent component analysis; seeding; kmeans clustering;
Figure 1.

I. I NTRODUCTION
Search engines are useful tools for retrieving informationfrom the Web. When a user inputs his or her query into
them, it returns a list of results ranked in order of relevanceto the query. The user starts at the top of the list and follows
it down, examining one result at a time, until the relevant
information has been found.
While search engines are definitely good for certain searchtasks such as finding the home page of an organization, they
may be less effective for satisfying vague queries. The results
on different subtopics or meanings of the input query will
come together in a list, thus implying that the user may
have to sift through a large number of irrelevant items tolocate those of interest. On the other hand, there is no way
to estimate what is relevant to the user given that the queries
are usually very short and their interpretation is inherently
fuzzy in the absence of context.
An approach for clustering the entire Web is different to
one for retrieving information from the Web. This clustering
approach shows the results, which are associated with clusters that consist of similar items manually or automatically(see Figure 1). Even the largest Web directories cover only
978-0-7695-4513-4/11 $26.00 © 2011 IEEE
DOI 10.1109/WI-IAT.2011.29

Effect of clustering for serch resultsa small fragment of the existing web pages. Furthermore,these directories may be of little help for a particular user
query, or for a particular aspect of the query. In fact, Web
directories are most often used to affect the output of a direct
search in response to common user queries.
The clustering the entire Web has attracted considerable
commercial interest and it is also an active research area.
In this research area, a large number of papers have been
published and focusing on specific issues and systems. The
clustering the entire Web is clearly related to document
clustering. However, our focus is on easy clustering methods
and optimal clusters. Especially, we are interested in thesimplest and quickest clustering method. Therefore we deal
with the k-means clustering method in our research. We also
discuss how to solve the problem of ”seeding” in the kmeans clustering method.
The rest of the paper is organized as follows. Section
II discusses related work and the k-means clustering, KKZ
clustering method and k-means++ clustering methods. Sec122

tion III discusses a problem of these clustering methods
and introduces our proposed method. Section IV presents
experimental results from comparing the performance ofthe proposed method with those of k-means clustering,
KKZ clustering method and k-means++ clustering methods.
Section V concludes this research.

ϮϬClustering is a classic problem in machine learning andcomputational geometry. In the popular k-means formulation, one is given an integer k and a set of n data points
chi ⊂ R2 . k is the number of cluster centers. The goal is
to choose k centers C to minimize the sum of the squared
distances between each point and its closest center.
min x − c2 .
φ=

ǆϲ

ǆϮ

ϭ

II. R ELATED W ORKS

x∈χ

ǆϯ

ϯ

Ϭ

ϭ

Ϯ

ǆϱ

Ϯ

Figure 2.

ϯ

ϰ

ϱ

Ϭ

ǆϲ

ǆϮ

ϭ

ǆϰ

ǆϭ

ǆϯ

ϯ

ǆϱ

ǆϰ

ǆϭ

Ϭ

ϭ

Ϯ

ϯ

ϰ

ϱ

Given Data & Global Optimal Clustering Case

shortest distance from a data point x to the closest center wehave already chosen. Then, the following clustering method
is defined as KKZ clustering method[4].
1a) Choose initial centers c1 and c2 . The distance between
c1 and c2 is the widest of all distance between a data
point and the other data point.
1b) For all data, D(xj ), j ∈ {1, · · · , n} are calculated.
1c) Choose the next center ci , selecting ci = x ∈ χ withthe widest distance D(x ).
1d) Repeat Step 1b) until we have chosen a total of kcenters.
Steps 2)-4) proceed as with the standard k-means algorithm.

c∈C

Solving this problem is NP-hard, even with just two
clusters[1], but 25 years ago, Lloyd[2] proposed a local
search solution that is still widely used today. A recent
survey of data mining techniques states that it ”is by far
the most popular clustering algorithm used in scientific andindustrial applications”[3].
In this section, we formally define k-means clustering
method, KKZ clustering method and k-means++ clustering
method.

C. k-means++ clustering method
The k-means method begins with an arbitrary set of cluster centers. k-means++ clustering proposes for specificallychoosing these centers. At any given time, let D(x) denotethe shortest distance from a data point x to the closest center
we have already chosen. Then, the following clustering
method is defined as k-means++ clustering method[5].
1a) Choose an initial center c1 uniformly at random fromχ.
1b) Choose the next center ci , selecting ci = x ∈ χ with 2)probability  D(xD(x)2.
x∈χ1c) Repeat Step 1b) until we have chosen a total of kcenters.
Steps 2)-4) proceed as with the standard k-means clustering
method. We call the weighting used in Step 1b) simply ”D2weighting”.

A. k-means clustering method
The k-means clustering method is simple and fast, which
locally improves an arbitrary k-means cluster method. It
works as follows.
1) Arbitrarily choose k initial centers C = c1 , · · · , ck ,2) For each i ∈ {1, . . . , k}, set the cluster ci to be theset of points in χ that are closer to ci than they areto cj for all j = i.
3) For each i ∈ {1, . . . , k}, set ci to be the center ofthe mass
 of all points in a set Ci of cluster i ci =1x∈Ci x|Ci |4) Repeat Steps 2) and 3) until ci no longer changes.
It is standard practice to choose the initial centers uniformly
at random from χ. For Step 2), ties may be broken arbitrarily,
as long as the method is consistent. Steps 2) and 3) are bothguaranteed to decrease φ; therefore, the method makes local
improvements to an arbitrary cluster until it is no longer
possible to do so.
The k-means method is attractive in practice because it
is simple and generally fast. Unfortunately, it is guaranteed
only to find a local optimum, which can often be quite poor.

III. P ROPOSED M ETHODThis section describes a problem for the k-means and kmeans++ clustering methods. Then, we propose k-means
combined with Independent Component Analysis (ICA)
based seeding method.
A. Problem for k-means and k-means++ clustering methods

B. KKZ clustering method

We have six data points, which consist of xi , i = 1, . . . , 6
and these points, are divided into two clusters. Figure 2
shows these six data points. And Figure 2 shows the global
optimal clustering result for these six data points. The firstcluster consists of {x1 , x2 , x4 , x5 } and the other consists

KKZ method was proposed by Katsavounidis et al. [4].
This method calculates all distance between data and findthe data which have a wide distance. The data are selected as
initial cluster centers. At any given time, let D(x) denote the

123

ǆϯ

ϯ
Ϯ

ǆϮ

ϭ
Ϭ

ǆϲ

Ϭ

ϭ

Ϯ

ǆϮ

ϭ

ǆϰ

ϯ

ϰ

ϱ

Ϭ

ǆϲ

/ϭ

Ϯ

ǆϱ

ǆϭ

ǆϯ

ϯ

method on three datasets of the UCI Machine Learning
repository. The first data set, iris, consists of 50 samples
from three species of Iris (Iris setosa, Iris virginica, andIris versicolor). The second dataset, wine, is the result of achemical analysis of wines produced in the same region in
Italy but derived from three different cultivars. The analysis
determined the quantities of 13 constituents found in eachof the three types of wine. The third dataset, soybeansmall, was for diagnosing four soybean diseases. The dataset
consists of 47 samples and 35 attributes.
We used the ODP Web corpus dataset for our test
experiment. The ODP Web corpus dataset consists of 12
directories, 247 samples, and 344 attributes.

ǆϭ

Ϭ

ϭ

ǆϱ

/Ϯ
Ϯ

ǆϰ

ϯ

ϰ

ϱ

Figure 3. Local Optimal Clustering Case & The Concept of our proposed
methodof {x3 , x6 }. We assume that clustering methods can findthe global optimal clusters. However, the k-means clustering
method generates bad clusters if x2 and x5 are chosen as
initial cluster centers c1 and c2 . Figure 3 shows local optimalclusters, which are bad clusters. The k-means++ clustering
method was developed to avoid this bad clustering.
However, the k-means++ clustering method sometimes
generates bad clusters because it depends on the choice of
the initial center c1 . The initial center c1 is chosen uniformly
at random from χ.

B. Evaluation Metrics
We used normalized mutual information as a metricto evaluate the qualities of clustering outputs of different methods. The normalized mutual information measures the consistency of the clustering output comparedto the ground truth. It reaches a maximum value of 1
only if the membership φc perfectly matches φg and aminimum of zero if the assignments of φc and φg are
independent. The membership function φc (x) is the mapping of a point x to one of the k clusters. The membership φg (x) represents the true cluster label for x. Formally, the normalized mutual information is derived withM I(φ ,φc )N M I(φg , φc ) = max(H(φgg),H(φ, where M I(φg , φc ) dek ck))
p (i,j)pg,c (i, j) log pgg,cnotes M I(φg , φc ) =(i)pc (j) ,k i=1 j=1 1
pg (i) log pg (i) , and H(φc ) deH(φg ) is H(φg ) =k i=1
1
notes H(φc ) =j=1 pc (j) log pc (j) . The pg (i) is thepercentage of points 
inn cluster i according to the ground
l=1 1(φg (xl )−i)(i)=
. Similarly, pc (j) =truth,
i.e.
p
g
n
n
l=1 1(φc (xl )−j)
and
p
(i,
j)
is
the
percentage of points
g,c
n
and
also
cluster j in φc , i.e.
that belong toclusteriinφgn1(φ (x )−i)1(φc (xl )−j)pg,c (i, j) = l=1 g l n.
The above defined metrics were used to evaluate theaccuracy of the k-means clustering method, k-means++clustering method and the proposed method.

B. k-means combined with ICA based seeding method
The k-means clustering method begins with an arbitrary
set of cluster centers. The k-means++ clustering method
begins with a small arbitrary set of cluster centers. As
stated above, we propose a method for specifically choosing
these centers. At any given time, we can obtain independent
components (ICs) from given data x. Then, we define thefollowing seeding method.
1a) Extract k independent components ICm , m =1, . . . , k from given data x.
1b) Choose an initial center
c1 , selecting c1 = x ∈ χ
IC1 ·xwith minimum |IC1 ||x | .
1c) Choose the next center ci , selecting ci = x ∈ χ with
ICi ·x
minimum |IC .
i ||x |
1d) Repeat Step 1c) until we have chosen a total of kcenters.
Steps 2)-4) proceed as with the standard k-means clustering method. Figure 3 shows the concept of the k-means clustering method combined with ICA based seeding method.

C. Experimental results
The k-means and k-means++ clustering methods were
each run 100 times with different initializations over all
three datasets. The proposed method was run only one time
because it can set up a unique initial seeding. Table I, II,
III, IV have the averaged N M I, the maximum N M I, theminimum N M I, and the N M I when the clusters achieved
minimum variance.
Tables I and II show that the proposed method outperforms both the k-means clustering method and the kmeans++ clustering method. In Tables I and II, the N M I
of our proposed method is as same as the N M I of the maximum performance of the k-means clustering method and the
k-means++ clustering method and is achieved by only one

IV. E XPERIMENTS
To evaluate the k-means clustering method, the kmeans++ clustering method and the proposed method inpractice, we implemented and tested them in matlab. In
this section, we discuss the results of these preliminary
experiments. We found that the k-means clustering method
combined with ICA based seeding method is accurate.
A. Datasets
We evaluated the performance of the k-means clustering
method, k-means++ clustering method and the proposed124

Table I
E XPERIMENTAL R ESULTS FOR iris DATASET
methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.751
0.751
0.751

N M I withmin. variance
0.751
0.751
-

max.
NMI
0.751
0.751
-

min.
NMI
0.532
0.532
-

seeding. Also instead of ICA, we used a seeding method
based Principal Component Analysis(PCA). Table IV lists
the experimental results of the ODP Web corpus dataset.
Table IV shows that the N M I of our proposed method isbetter than the N M I of k-means clustering and k-means++clustering methods when the clusters achieved minimum
variance for the ODP Web corpus dataset. Table IV showsthat the N M I of the proposed method was 0.638. This value
is better than the maximum N M I of k-means clustering
method and the maximum N M I of k-means++ clustering
method. And also the N M I of the proposed method is better
than the N M I of KKZ method and the N M I of PCA
based method. Therefore, Table IV shows that the proposed
method outperforms k-means clustering method, k-means++clustering method, KKZ method and PCA bsed method for
the ODP Web corpus dataset. And the best N M I is achievedby only one initial seeding.

avrg.
NMI
0.703
0.749
-

Table IIE XPERIMENTAL R ESULTS FOR wine DATASET
methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.387
0.429
0.429

N M I withmin. variance
0.429
0.429
-

max.
NMI
0.429
0.429
-

min.
NMI
0.387
0.387
-

avrg.
NMI
0.418
0.418
-

V. C ONCLUSIONS
initial seeding. And Table I shows that the performance of
KKZ method is worse than the other methods.
We generally cannot provide true cluster data. N M I
with minimum variance is the most important for real-world
applications. Table III shows that the N M I of our proposed
method is the same as the N M I of the k-means clustering
method and k-means++ clustering method when the clusters
achieved minimum variance. This situation shows that theperformance of our proposed method is as same as theperformance of the k-means clustering method and the kmeans++ clustering method for the soybean-small dataset.
And the N M I with minimum variance is achieved by only
one initial seeding.
The k-means clustering and k-means++ clustering methods were each run 100 times with different initializations
for the ODP Web corpus dataset. The proposed method was
run only one time because it can set up a unique initial

We proposed a method that combines k-means clustering
method with ICA based seeding method. From our experimental results, our proposed method performed the sameas or better than the k-means clustering method, k-means++clustering method, KKZ method and PCA based method.
For our future work, we plan the followings.
1) Apply the proposed method to different Web data andbenchmark datasets.
2) Theoretically analyze the computational cost of the
proposed method.
R EFERENCES[1] P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay,“Clustering large graphs via the singular value decomposition,”
Maching Learning, vol. 56, no. (1-3), pp. 9–33, 2004.
[2] S. P. Lloyd, “Least squares quantization in pcm,” IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129–136,
1982.

Table IIIE XPERIMENTAL R ESULTS FOR soybean-small DATASET
methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.711
0.711
0.711

N M I withmin. variance
0.711
0.711
-

max.
NMI
1.000
1.000
-

min.
NMI
0.518
0.711
-

[3] P. Berkhin, “Survey of clustering data mining techniques,”
Accrue Software, San Jose, CA, Tech. Rep., 2002.
avrg.
NMI
0.714
0.806
-

[4] I. Katsavounidis, C.-C. J. Kuo, and Z. Zhang, “A new initialization technique for generalized lloyd iteration,” IEEE Signal
Processing Letters, vol. 1, no. 10, pp. 144–146, 1994.
[5] D. Arthur and S. Vassilvitskii, “k-means++: the advantagesof careful seeding,” in Proceedings of the eighteenth annual
ACM-SIAM symposium on Discrete algorithms,. New Orleans,Louisiana, USA: Society for Industrial and Applied Mathematics, 2007, pp. 1027–1035.

Table IV
E XPERIMENTAL R ESULTS FOR ODP Web corpus DATASET
methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.531
0.500
0.638

N M I withmin. variance
0.555
0.555
-

max.
NMI
0.589
0.589
-

min.
NMI
0.392
0.425
-

avrg.
NMI
0.514
0.525
-

125