2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology

Careful Seeding 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

makes the algorithm much faster than most of its competitors.
Unfortunately, the empirical speed and simplicity of thek-means algorithm come at the price of accuracy. There aremany natural examples for which the algorithm 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
showing that in practice, our proposed method really doesoutperform k-means and k-means++ in terms of both accuracy and speed.

Abstract—The k-means method is a widely used clustering
technique because of its simplicity and speed. However, theclustering result depends heavily on the chosen initial value.
In this report, we propose a seeding method with independent
component analysis for the k-means method. Using a benchmark dataset, we evaluate the performance of our proposed
method and compare it with other seeding methods.
Keywords-k-means; k-means++; independent component
analysis; seeding;

I. I NTRODUCTIONClustering is one of the classic problems in machinelearning and computational geometry. In the popular kmeans formulation, one is given an integer k and a set ofn data points in Rd . The goal is to choose k centers so as
to minimize the sum of the squared distances between eachpoint and its closest center.
Solving this problem exactly is NP-hard, even with justtwo clusters [1], but twenty-five years ago, Lloyd[2] proposed a local search solution that is still very widely used
today (see for example [3], [4]). Indeed, a recent surveyof data mining techniques states that it ”is by far the mostpopular clustering algorithm used in scientific and industrial
applications”[5].
Usually referred to simply as k-means, Lloyd’s algorithm
begins with k arbitrary centers, typically chosen uniformly
at random from the data points. Each point is then assigned
to the nearest center, and each center is recomputed as thecenter of mass of all points assigned to it. These two steps(assignment and center calculation) are repeated until theprocess 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 repeatedduring the course of the algorithm. Since there are at mostk n possible clusterings, the process will always terminate.
In practice, very few iterations are usually required, which
978-0-7695-4191-4/10 $26.00 © 2010 IEEE
DOI 10.1109/WI-IAT.2010.102

II. R ELATED W ORKS
In this section, we formally define the k-means problem,
as well as the k-means and k-means++ algorithms.
For the k-means problem, we are given an integer k anda set 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∈CChoosing these centers implicitly defines a clustering foreach center, we set one cluster to be the set of data points thatare closer 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 optimalclustering for a given instance of the k-means problem, andwe will let φopt denote the corresponding potential. Givena clustering C with potential φ, we also let φ(A) denotetheχ to the potential (i.e., φ(A) = contribution of A ⊂2minx−c).
c∈Cx∈A112

A. The k-means algorithm
The k-means method is a simple and fast algorithm that
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 theset of points in χ that are closer to ci than they areto cj for all j = i.
be the center of3) For each i ∈ {1, . . . , k}, set ci to
mass of 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 algorithm makes local
improvements to an arbitrary clustering until it is no longerpossible to do so. To see that Step 3) does in fact decreases
φ, it is helpful to recall a standard result from linear algebra(see [14]).
The k-means algorithm is attractive in practice because
it is simple and it is generally fast. Unfortunately, it isguaranteed only to find a local optimum, which can often
be quite poor.

ϮǆϮϭ
Ϭ

ǆϱ

ǆϰ

ǆϭ

Ϭ

ϭ

Ϯ

ϯ

Figure 1.

Given DataǆϯϯϮ

B. The k-means++ algorithm
The k-means algorithm begins with an arbitrary set ofcluster centers. We propose a specific way of choosing thesecenters. At any given time, let D(x) denote the shortest
distance from a data point x to the closest center we havealready chosen. Then, we define the following algorithm,
which we call k-means++[6].
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ϭFigure 2.

x∈χ1c) Repeat Step 1)b until we have chosen a total of kcenters.
Step 2)-4) proceed as with the standard k-means algorithm.
We call the weighting used in Step 1b) simply “D2 weighting”.

ϱϰϱǆϱǆϰǆϭϬϰǆϲǆϮϭϬǆϲǆϯϯϮϯ

Global Optimal Custering Casecluster consists of {x3 , x6 }. We are expecting that clustering
algorithms can find the global optimal clusters. But, k-means
algorithm generates bad clusters, if x2 and x5 are chosen
as initial cluster centers c1 and c2 . Figure 3 shows local
optimal clusters, which are bad clusters. The k-means++algorithm was proposed to avoid this bad clustering. But,the k-means++ algorithm sometimes generates bad clusters,
because the algorithm depends on choosing the initial centerc1 . The initial center c1 is chosen uniformaly at random
from χ.

III. P ROPOSED M ETHODThis section describes a problem for k-means and kmeans++ algorithms. Then, we proposes k-means with Independent Component Analysis(ICA) based seeding algorithm.
A. What is a problem for k-means and k-means++ algorithms

B. The k-means with ICA based seeding algorithm
The k-means algorithm begins with an arbitrary set ofcluster centers. The k-means++ algorithm begins with a little
bit arbitrary set of cluster centers. We propose a specific
way of choosing these centers. At any given time, we canget independent components(ICs) from given data x. Then,
we define the following algorithm.

Now, we have 6 points data which consist of xi , i =1, . . . , 6 and these points are divided into two clusters.
Figure 1 shows these 6 points. And Figure 2 shows theglobal optimal clustering result for these 6 points data.
The first cluster consists of {x1 , x2 , x4 , x5 } and the other113

seeding makes good performance of both the accuracy andthe speed.

ϮǆϮϭ
Ϭ

Ϭ

We evaluated the performance of k-means, k-means++
and the proposed method on three data sets of UCI Machine
Learning repository. The first data set, iris, is consists of
50 samples from each of three species of Iris flowers (Irissetosa, Iris virginica and Iris versicolor). Four features weremeasured from each sample, they are the length and thewidth of sepal and petal. Based on the combination of thefour features, Fisher developed a linear discriminant modelto determine which species from these four measurements.
It is used as a 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
disease diagnosis. The dataset is consists of 47 samples and35 attributes.

ǆϰϭ

Ϯ

ϯϰ

ϱ

Local Optimal Clustering CaseǆϯϯA. Data setsǆϱǆϭ

Figure 3.

ǆϲ/ϭ

B. Evaluation metricsϮǆϮϭϬǆϲǆϯϯǆϭϬϭ
Figure 4.

ǆϱ/ϮϮ

We used Normalized Mutual Information as a metricto evaluate the qualities of clustering outputs of different
methods. The Normalized Mutual Information measuresthe consistency of the clustering output compared to theground truth. It reaches the maximum value of 1 only if
the membership φc perfectly matches φg and the minimal
zero if the assignments of φc and φg are independent. Themembership function φc (x), the mapping of a point x toone of the k clusters. The membership φg (x) represents thetrue cluster label for x. Formally, the Normalized MutualInformation is the following equation.

ǆϰ

ϯ

ϰ

ϱ

The Concept of our proposed method1a) 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 ∈ χ withICi ·x
minimum |IC .
i ||x |1d) Repeat Step 1c) until we have chosen a total of kcenters.

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 kpg,c (i, j) log

i=1 j=1

H(φg ) isH(φg ) =Step 2)-4) proceed as with the standard k-means algorithm.
Figure 4 shows the concept of the k-means with ICA based
seeding algorithm.

kpg,c (i, j),pg (i)pc (j)pg (i) log

1,pg (i)pc (j) log

1.
pc (j)

i=1and H(φc ) denotes

IV. E XPERIMENTS

H(φc ) =In order to evaluate k-means++ and the proposed method
in practice, we have implemented and tested them in matlab.
In this section, we discuss the results of these preliminary
experiments. We found that the k-means with ICA basedk
j=1

The pg (i) is the percentage of points
 in cluster i accordingnto the ground truth, i.e. pg (i) =114

l=11(φg (xl )−i)
. Similarly,nTable I
E XPERIMENTAL R ESULTS FOR iris DATASETk-means
k-means++
ICA

avg N M I
0.703250.749295
0.751485

max N M I
0.7514850.751485-

min N M I
0.532224
0.532471-

N M I with min variance0.7514850.751485-

Table IIE XPERIMENTAL R ESULTS FOR wine DATASET

k-meansk-means++
ICA

avg N M I
0.417794
0.418351
0.428701

max N M I
0.428701
0.428701-

min N M I
0.38730.3873-N M I with min variance0.428701
0.428701-

Table IIIE XPERIMENTAL R ESULTS FOR soybean-small DATASETk-means
k-means++
ICAnavg N M I
0.714445
0.806213
0.710813

max N M I
11-1(φc (xl )−j)

pc (j) = l=1 n
and pg,c (i, j) is the percentage ofpoints that belong
to cluster i in φg and also cluster j in φc ,nmin N M I
0.518038
0.710813-N M I with min variance0.710813
0.710813-performance than the other algorithms or the performanceof our proposed algorithm is as same as the performance ofthe others. In our future work, we will improve our proposedalgorithm to improve the accuracy.

1(φg (xl )−i)1(φc (xl )−j)i.e. pg,c (i, j) = l=1.
nThe above defined metrics were used to evaluate theaccuracy of the clustering algorithms.

R EFERENCES

C. Experimental results
Each of the k-means and k-means++ methods was run
100 times with different initializations over all the datasets.
And the proposed method was run just one time, because
this method does not need an initial value. Table IV showsthe experimental results of iris dataset, Table V shows theexperimental results of wine dataset, and Table VI showsthe experimental results of 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
the minimum variance.
Table IV, V show that the proposed algorithm outperforms
both k-means and k-means++ algorithms. In Table IV, V, theN M I of our proposed algorithm is as same as the N M Iof the maximum performance of the other algorithms and isachieved by just one calculation.
Table VI shows that the N M I of our proposed algorithm
is as same as the N M I when the clusters achieved the minimum variance. This situation shows that the performanceof our proposed algorithm is as same as the performance ofthe other algorithms for soybean-small data set.

[1] P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay,“Clustering large 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,” in Proceedings of the twenty-third ACM SIGMODSIGACT-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 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.

V. C ONCLUSION
This paper proposed k-means with Independent Component Analysis(ICA) based seeding algorithm. In our experimental results, our proposed algorithm shows the better

115