SCIS & ISIS 2010, Dec. 8-12, 2010, Okayama Convention Center, Okayama, Japan

Seeding method based on Independent Component
Analysis 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 k-meansclustering 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 thatthe normalized mutual information of our proposed method
is better than the normalized mutual information of k-meansclustering method and k-means++ clustering method. Therefore,
the proposed method is useful for Web corpus.
Keywords-k-means; k-means++; independent component analysis; seeding;

I. I NTRODUCTION
Clustering is one of the classic problems in machine learning and computational geometry. In the popular k-means
formulation, one is given an integer k and a set of n data
points in Rd . The goal is to choose k centers so as to minimize
the sum of the squared distances between each point and its
closest center.
Solving this problem exactly is NP-hard, even with just two
clusters [1], but twenty-five years ago, Lloyd[2] proposed a
local search solution that is still very widely used today (seefor example [3], [4]). Indeed, a recent survey of data mining
techniques states that it ”is by far the most popular clustering
method used in scientific and industrial applications”[5].
Usually referred to simply as k-means, Lloyd’s method
begins with k arbitrary centers, typically chosen uniformly at
random from the data points. Each point is then assigned to thenearest center, and each center is recomputed as the center ofmass of all points assigned to it. These two steps (assignmentand center calculation) are repeated until the process stabilizes.
One can check that the sum of the squared distances
between each point and its closest center is monotonicallydecreasing, which ensures that no clustering is repeated during

the course of the method. Since there are at most k n possible
clusterings, the process will always terminate. In practice, very
few iterations are usually required, which makes the methodmuch faster than most of its competitors.
Unfortunately, the empirical speed and simplicity of the kmeans clustering method come at the price of accuracy. There
are many natural examples for which the method generates
arbitrarily bad clusters. Furthermore, these examples do not
rely on an adversarial placement of the starting centers, andthe ratio can be unbounded with high probability even withthe standard randomized seeding technique.
In this paper, we propose a way of initializing k-means bychoosing Independent Component Analysis based starting centers. We also provide preliminary experimental data showingthat in practice, our proposed method really does outperform
k-means and k-means++ in terms of both accuracy and speed.
II. R ELATED W ORKS
In this section, we formally define the k-means clustering
problem, as well as the k-means clustering and k-means++clustering methods.
For the k-means problem, we are given an integer k and aset of n data points χ ⊂ Rd . We wish to choose k centers C
so as to minimize the potential function,∑min ∥x − c∥2 .
ϕ=
x∈χ

c∈C

Choosing these centers implicitly defines a clustering for eachcenter, we set one cluster to be the set of data points that arecloser to that center than to any other. As noted above, finding
an exact solution to the k-means problem is NP-hard. Throughout the paper, we will let Copt denote the optimal clustering
for a given instance of the k-means problem, and we will let
ϕopt denote the corresponding potential. Given a clustering C
with potential ϕ, we also let ϕ(A) denotethe contribution of∑A ⊂ χ to the potential (i.e., ϕ(A) = x∈A minc∈C ∥x−c∥2 ).

1306

A. The k-means clustering method
The k-means clustering method is a simple and fast methodthat attempts to locally improve an arbitrary k-means clustering. 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 the setof points in χ that are closer to ci than they are to cj
for all j ̸= i.
3) For each i ∈ {1, . . . , k}, set ci∑to be the center of massof all points in Ci : ci = |C1i | x∈Ci x.
4) Repeat Steps 2) and 3) until C 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) areboth guaranteed to decrease ϕ, so the method makes local
improvements to an arbitrary clustering until it is no longer
possible to do so. To see that Step 3) does in fact decreases
ϕ, it is helpful to recall a standard result from linear algebra.
The k-means clustering method is attractive in practicebecause it is simple and it is generally fast. Unfortunately,
it is guaranteed only to find a local optimum, which can often
be quite poor.

x6

x3

3

2
x5

x2

1
x4

x1

0

0

1

2

3

Fig. 1.

Given Data

4

5

4

5

x6

x3

3

2

B. The k-means++ clustering methodx5x2

The k-means clustering method begins with an arbitrary setof cluster centers. The k-means++ clustering method proposes
for specifically choosing these centers. At any given time,
let D(x) denote the 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[6].
1a) Choose an initial center c1 uniformly at random fromχ.
1b) 1b) Choose the next center ci by the following.
a) Find a real value y uniformly at random. The value
satisfies the following equation∑0≤y≤
D(x)2 .
x∈χb) Find xi satisfying the following equation. Selectxi as a cluster center ci .
D(xi−1 )2 ≤ y ≤ D(xi ).
1c) Repeat Step 1b) until we have chosen a total of k centers.
Step 2)-4) proceed as with the standard k-means clustering
method. We call the weighting used in Step 1b) simply “D2weighting”.
III. P ROPOSED M ETHODThis section describes a problem for k-means clustering andk-means++ clustering methods. Then, we proposes k-means
combined with Independent Component Analysis (ICA) based
seeding method.

1
x4

x1

0

0

1
Fig. 2.

2

3

Global Optimal Clustering Case

A. Problem for k-means and k-means++ clustering methods
We have 6 points data which consist of xi , i = 1, . . . , 6 andthese points are divided into two clusters. Figure 1 shows these
6 points. And Figure 2 shows the global optimal clusteringresult for these 6 points data. The first cluster consists of{x1 , x2 , x4 , x5 } and the other cluster consists of {x3 , x6 }. We
assume that clustering methods can find the global optimalclusters. However, the k-means clustering method generates
bad clusters if x2 and x5 are chosen as initial cluster centersc1 and c2 . Figure 3 shows local optimal clusters, which are badclusters. 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 choice of the initialcenter c1 . The initial center c1 is chosen uniformly at random
from χ.
B. The k-means combined with ICA based seeding method
The k-means clustering method begins with an arbitrary setof cluster centers. The k-means++ clustering method begins

1307

preliminary experiments. We found that the k-means clustering
method combined with ICA based seeding method is accurate.
x6

x3

A. Datasets

3

We evaluated the performance of k-means clustering, kmeans++ clustering and the proposed methods on three data
sets of UCI Machine Learning repository and a dataset of
the ODP Web corpus. The first data set, iris, consists of 50
samples from each of three species of Iris flowers (Iris setosa,
Iris virginica and Iris versicolor). Four features were measured
from each sample, they are the length and the width of sepal
and petal. Based on the combination of the four features,
Fisher developed a linear discriminant model to determine
which species from these four measurements. It is used asa typical test for many other classification techniques.
The second dataset, wine, is the results of a chemical
analysis of wines grown in the same region in Italy but derived
from three different cultivars. The analysis determined thequantities of 13 constituents found in each of the three typesof wines.
The third dataset, soybean-small, is for four soybean diseasediagnosis. The dataset is consists of 47 samples and 35
attributes.
The forth dataset is the ODP Web corpus dataset for our
test experiment. The ODP Web corpus dataset consists of 12
directories, 247 samples, and 344 attributes.

2
x5

x2

1
x4

x1

0

0

1

2

Fig. 3.

3

5

Local Optimal Clustering Case

x6

x3

3

4

IC1

2
x5

x2

1
x1

0

0

1
Fig. 4.

IC2
2

B. Evaluation metrics

x4

3

4

5

The Concept of our proposed methodwith 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 get independent components(ICs)from given data x. Then, we define the following seeding
method.
1a) Extract k independent components ICm , m = 1, . . . , kfrom given data x.
1b) Choose an initial′ center c1 , selecting c1 = x′ ∈ χ with
IC1 ·x
minimum |IC′ .
1 ||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 k centers.
Step 2)-4) proceed as with the standard k-means clustering
method. Figure 4 shows the concept of the k-means clustering
method combined with ICA based seeding method.
IV. E XPERIMENTS

We used Normalized Mutual Information as a metric to evaluate the qualities of clustering outputs of different methods.
The Normalized Mutual Information measures the consistencyof the clustering output compared to the ground truth. Itreaches the maximum value of 1 only if the membership ϕcperfectly matches ϕg and the minimal zero if the assignmentsof ϕc and ϕg are independent. The membership function
ϕc (x), 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 the following
equation.
N M I(ϕg , ϕc ) =M I(ϕg , ϕc ),max(H(ϕg ), H(ϕc ))where M I(ϕg , ϕc ) denotes
M I(ϕg , ϕc ) =

k ∑
k
∑

pg,c (i, j) log

i=1 j=1

pg,c (i, j),
pg (i)pc (j)H(ϕg ) isH(ϕg ) =k∑pg (i) log

1,pg (i)

pc (j) log

1.
pc (j)

i=1

and H(ϕc ) denotes

To evaluate k-means clustering, k-means++ clustering andthe proposed method in practice, we implemented and tested
them in matlab. In this section, we discuss the results of these1308

H(ϕc ) =k∑
j=1

TABLE I
E XPERIMENTAL R ESULTS FOR iris DATASETThe pg (i) is the percentage of points∑n in cluster i according
l=1 1(ϕg (xl )−i)to the groundtruth,i.e.
p(i)=. Similarly,g∑nnl=1 1(ϕc (xl )−j)and pg,c (i, j) is the percentage ofpc (j) =npoints that belongtocluster
i in ϕg and also cluster j in ϕc ,∑n1(ϕ (x )−i)1(ϕc (xl )−j)i.e. pg,c (i, j) = l=1 g l n.
The above defined metrics were used to evaluate the accuracy of the clustering methods.

methodk-meansk-means++
ICA

max N M I

min N M I

avrg N M I

0.751
0.751
-

0.532
0.532
-

0.703
0.749
-

TABLE IIE XPERIMENTAL R ESULTS FOR wine DATASET
methodC. Experimental results
The k-means and k-means++ clustering methods were eachrun 100 times with different initializations over all threedatasets. The proposed method was run only one time because it can set up a unique initial seeding. Table I lists
the experimental results of the iris dataset, Table II lists theexperimental results of the wine dataset, and Table III lists
the experimental results of the soybean-small dataset. Thesetables 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 andthe k-means++ clustering method. In Tables I and II, theN 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 initial seeding. Table III shows that the N M I of our
proposed method is the same as the N M I of the k-meansclustering method and k-means++ clustering method when
the clusters achieved minimum variance. This situation showsthat the performance of our proposed method is as same as
the performance of the k-means clustering method and the
k-means++ 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 seeding.
Table IV lists the experimental results of the ODP Web
corpus dataset. The maximum N M I of k-means clustering
method was 0.421 and the minimum N M I was 0.341. The
maximum N M I of k-means++ clustering method was 0.432
and the minimum N M I was 0.358. Table IV shows that theN M I of our proposed method is better 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. The maximum N M I of k-means clustering
method is better than the N M I of the k-means clustering
method when the clusters achieved minimum variance. However, we generally cannot provide true cluster data. N M I
with minimum variance is the most important for real-world
applications. Therefore, Table IV shows that the proposed
method outperforms both k-means clustering and k-means++clustering methods for the ODP Web corpus dataset. And the
NMI with minimum variance is achieved by only one initial
seeding.

N M I withmin variance
0.751
0.751
0.751

k-meansk-means++
ICA

N M I withmin variance
0.429
0.429
0.429

max N M I

min N M I

avrg N M I

0.429
0.429
-

0.387
0.387
-

0.418
0.418
-

TABLE IIIE XPERIMENTAL R ESULTS FOR soybean-small DATASET
methodk-meansk-means++
ICA

N M I withmin variance
0.711
0.711
0.711

max N M I

min N M I

avrg N M I

1.000
1.000
-

0.518
0.711
-

0.714
0.806
-

TABLE IV
E XPERIMENTAL R ESULTS FOR ODP Web corpus DATASET
methodk-meansk-means++
ICA

N M I withmin variance
0.383
0.374
0.385

max N M I

min N M I

avrg N M I

0.421
0.432
-

0.341
0.358
-

0.385
0.388
-

V. C ONCLUSION
We proposed a method that combines k-means clustering
method with ICA based seeding method. From our experimental results, our proposed method performed the same asor better than the k-means clustering and k-means++ clustering
methods. 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.
3) Develop a method for finding clusters that are on only
one independent component.
R EFERENCES[1] P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay, “Clusteringlarge graphs via the singular value decomposition,” Mach. Learn., 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.
[3] P. K. Agarwal and N. H. Mustafa, “k-means projective clustering,” inProceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems,. New York, NY, USA: ACM
Press, 2005, pp. 155–165.
[4] R. Herwig, A. Poustka, C. Müller, C. Bull, H. Lehrach, and J. O’Brien,“Large-scale clustering of cdna-fingerprinting data,” Genome Research,
vol. 9, pp. 1093–1105, 1999.
[5] P. Berkhin, “Survey of clustering data mining techniques,” Accrue Software, San Jose, CA, Tech. Rep., 2002.
[6] D. Arthur and S. Vassilvitskii, “k-means++: the advantages of carefulseeding,” 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.

1309