JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 201251

Careful Seeding Method based on Independent
Components Analysis for k-means Clustering
Takashi Onoda
System Engineering Lab., CRIEPI, Tokyo, JAPAN. Email: onoda@criepi.denken.or.jp
Miho Sakai
Tokyo Institute of Technology, Yokohama, JAPAN. Email: sakai@ntt.dis.titech.ac.jp
Seiji Yamada
National Institute of Informatics/SOKENDAI/Tokyo Institute of Technology, 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
and speed. However, the clustering result depends heavily
on the chosen initial clustering centers, which are uniformly
chosen at random from the data points. We propose aseeding method that is based on the independent component
analysis for the k-means clustering method. We evaluate
the performance of our proposed method and compare itwith other seeding methods by using benchmark datasets.
We also applied our proposed method to a Web corpus,
which was provided by ODP, and the CLUTO datasets. The
results from the experiments showed that the normalized
mutual information of our proposed method is better than
the normalized mutual information of the k-means clustering
method, the KKZ method, and the k-means++ clustering
method.
Index Terms— k-means clustering method, KKZ method, kmeans++ clustering method, independent components analysis, seeding

It is difficult to find relevant data insearch results because they containmany kinds of mixed data.

It is easy to understand topic andsystematically explore search results.

Figure 1. Effect of clustering the results of Web search.

I. I NTRODUCTION
Clustering is one of the most useful unsupervised
learning in data mining[1][2]. It has been applied tovarious fields and used widespread both in research andbusiness[3]. We are interested in application of clusteringto the Web clustering. The Web clustering[4] has avery wide ranges including clustering searched results[5],[6], [7], [8], clustering Web pages/sites[9], [10], [11],clustering Web multimedia[12] and so on. Especially,
we focus on clustering of Web searched results because
our final research objective is to build IWI (Intelligent
Web Interaction) systems. While Web search engines aredefinitely good for certain search tasks such as finding
an organization’s Web page, they may be less effective
at satisfying ambiguous queries. The results on different
subtopics or meanings of the input query also will cometogether in a hit list, thus implying that the user may haveto sift through a large number of irrelevant items to locate
those of interest. On the other hand, there is no way toestimate what is relevant to the user given that the queries
are usually very short and their interpretation is inherently
ambiguous in the absence of context.
An approach for clustering the results of Web search[5],[6], [7], [8] is different from one for retrieving information© 2012 ACADEMY PUBLISHER
doi:10.4304/jetwi.4.1.51-59

from the Web. This clustering approach shows the results,
which are manually or automatically associated withclusters that consist of similar items (Figure 1).
We consider this clustering of Web searched results
should be quick and accurate because a user neverwait for the clustered results so long. In particular, we
are interested in the simplest and quickest clustering
method. Therefore, we deal with the k-means clustering
method in our research. We particularly discuss how tosolve the problem of “seeding” in the k-means clustering
method[13], [14], [15].
The rest of this paper is organized as follows. Section II
discusses the related work and the k-means clustering, theKKZ clustering, and the k-means++ clustering methods.
Section III discusses the problem with these clustering
methods and introduces our proposed method. Section IV
presents our experimental results along with comparisonof the performance of the proposed method with thoseof the k-means clustering, the KKZ clustering, and kmeans++ clustering methods. Section V concludes thisresearch.

52

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012

II. R ELATED W ORKS
Clustering is a classic problem in machine learningand computational geometry. In the popular k-means
formulation, one is given an integer k and a set of ndata points X ⊂ Rm . 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.
ϕ=∑x∈Xmin ∥x − c∥2
c∈C

d

d

(1)

Solving this problem is NP-hard, even with just two
clusters[16], however Lloyd[17] proposed a local searchsolution 25 years ago that is still widely used today.
In this section, we formally define the k-means clustering method, the KKZ clustering method and the kmeans++ clustering method.
A. k-means clustering method
The k-means clustering method is simple and fast andlocally improves the centers of mass of clusters. 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 X 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 the points in a set Ci of cluster i:
ci = |C1i | x∈Ci x.
4) Repeat steps 2) and 3) until ci no longer changes.
It is standard practice to uniformly choose the initialcenters at random from X. For Step 2), the ties may bearbitrarily broken, as long as the method is consistent.
Steps 2) and 3) are both guaranteed to decrease ϕ;therefore, the method makes local improvements to anarbitrary 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 bequite poor.
B. KKZ clustering method
The KKZ method was proposed by Katsavounidis et al.
[18]. This method calculates the entire distance among thedata and finds the data with a wide distance. The data are
selected as the initial cluster 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 the KKZ
clustering method[18].
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(Figure 2).
1b) For all data, D(xj ), j ∈ {1, · · · , n} are calculated(Figure 3).
© 2012 ACADEMY PUBLISHER

Figure 2. Initial centers of KKZ method

Figure 3. Distance D(x)1c) Choose the next center ci , selecting ci = x′ ∈ X
with the widest distance D(x′ ) (Figure 4).
1d) Repeat step 1b) until we have chosen a total of kcenters.
Steps 2)-4) proceed just like that for the standard k-means
algorithm.
The KKZ method is attractive in practice because it issimple for decision of unique initial centers. However,the KKZ method sometimes find bad clusters because
unfortunately it depends on outlier data points.
C. k-means++ clustering method
The k-means method begins with an arbitrary set ofcluster centers. k-means++ clustering proposes specifically choosing these centers. At any given time, letD(x) denote the shortest distance from a data point x
to the closest center we have already chosen. Then, thefollowing clustering method is defined as the k-means++clustering method[19].
1a) Choose an initial center c1 uniformly at random
from X.
1b) For all data, D(xj ); j ∈ {1, · · · , n} are calculated(Figure 3).
1c) Randomly generate a real value L satisfying thefollowing equation.
∑
0<L≤
D(xj )(2)x∈X1d) Choose the next center ci , selecting the ci = xj
with satisfying the following equation (Figure 5).
j−1∑

D(xm ) < L ≤

m=1

j
∑

D(xm )

m=1

W
Figure 4. Next center ci of KKZ method(3)

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012

∑D x

L

0

53

( )

D ( x1 )D ( x 2 ) D ( x 3 )D(x n−1 )D(x n )

x3

3

x6

Figure 5. Next center ci of k-means++ method21e) Repeat step 1b) until we have chosen a total of kcenters.
Steps 2)-4) proceed in the same way as with the standard k-means clustering method. We call the weightingused in Step 1b) simply “D2 weighting”.

x2

1
0

x3

3
2

x2

1
0

x6

0

0

1

2

2

3

4

5

Figure 7. Global Optimal Clustering Case

x3

3
2

x2

1
0

x6

x5

x4

x1

0

1

2

3

4

5

Figure 8. Local Optimal Clustering Case

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 specificallychoosing these centers. At any given time, we can obtain
independent components (ICs) from given data X. Then,
we define the following seeding method.

x5

3

Steps 2)-4) proceed in the same way as with thestandard k-means clustering method. Figure 11 shows
the concept of the k-means clustering method combinedwith the ICA based seeding method. In the figure 11,
IC1 and IC2 denote independent components. The eachindependent component may become an initial seed togenerate the global optimal clustering case.

Figure 6. Given Data

© 2012 ACADEMY PUBLISHER

11a) Extract k independent components IC1 , · · · , ICkfrom given data X (Figure 9).
1b) Choose k initial centers ci (i = 1, · · ·′ , k), selecting
ICi ·xci = x′ ∈ X with a minimum |IC′ (Figure 10).
i ||x |

x4

x1

x4

x1

III. P ROPOSED M ETHODThis section describes a problem with the k-means
and the k-means++ clustering methods. Then, we proposea k-means combined with an Independent Component
Analysis (ICA)[20], [21], [22] based seeding method.
A. Problem for k-means and k-means++ clustering methods
We have six data points, which consist of xi (i =1, . . . ,6) and these points are divided into two clusters. Figure 6
shows these six data points.
In addition, Figure 7 shows the global optimal clustering result for these six data points. The first cluster
consists of {x1 , x2 , x4 , x5 } and the other consists of{x3 , x6 }. We assume that most of clustering methods canfind the global optimal clusters. However, the k-meansclustering method generates bad clusters if x2 and x5 arechosen as the initial c1 and c2 cluster centers. Figure 8
shows the local optimal clusters, 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 choiceof the initial center c1 . The initial center c1 is chosen
uniformly at random from X.

x5

4

5

54

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012

TABLE I.
N O . OF CLUSTERS , ATTRIBUTES , AND SAMPLES FOR UCI

IC2

IC1

REPOSITORY DATA SETS

Data set
Iris
Wine
Soybean-SmallBreast-Cancer

IC3

No. of clusters3
3

No. of attributes
4
13

No. of samples
150
178

4

35

47

2

9

683

Figure 9. Independent components
TABLE II.
N O . OF DIRECTORIES , ATTRIBUTES AND SAMPLES FOR ODP CORPUS
DATA SETIC2

IC1Data set
ODP

IC3

Figure 10. Initial centers ci of ICA based method

IV. E XPERIMENTAL CONDITION
To evaluate the k-means clustering method, KZZ
method, k-means++ clustering method and proposed
method in practice, we implemented and tested them inmatlab. In this section, we briefly explain about the data
sets that were used for the experiments, the evaluation
metrics in the experiments, some compared seeding methods and the results of the experiments. We found that the
k-means clustering method combined with the ICA based
seeding method performed well in the experiments.
A. Data sets
We evaluated the performance of the k-means clustering method, KKZ method, k-means++ clustering method,
and the proposed method using on two kinds of data
sets. One contained a small amount of data and the

x3

3

IC1

2

x2

1
0

x6

x1

0

1

x5

IC2
2

x4

3

4

Figure 11. Concept of Our Proposed Method© 2012 ACADEMY PUBLISHER

5

No. of clusters
4

No. of attributes
340

No. of samples
72

other a large data. The small data set consisted of the
UCI Machine Learning repository and Open Directory
Project(ODP) Web corpus. The large data set consistedof the CLUTO data sets.
1) UCI Machine Learning repository: The UCI Machine Learning repository had four data sets in our
experiments. The first data set, iris, consisted of 50
samples from each of three species of Iris (Iris setosa,
Iris virginica, and Iris versicolor). The second data set,wine, contained the results of a chemical analysis onwines produced in the same region in Italy but derived
from three different cultivars. The analysis determined
the quantities of 13 constituents found in each of thethree types of wine. The third data set, soybean-small,
was for diagnosing four soybean diseases. The data set
consisted of 47 samples and 35 attributes. The fourthdata set, breast-cancer, contained diagnosis results ofbreast cancer. The data set consisted of 683 samples and9 attributes. Table I lists the numbers of samples, thenumbers of attributes and the numbers of clusters in thedata sets used in our experiments.
2) ODP corpus data: We used the ODP Web corpus
data set for our test experiment. The ODP Web corpus was
extracted from the Open Directory Project1 by ourselves.
We selected twelve subdirectories from the “Science” topdirectory, and downloaded top pages of the web sites
listed in each directory. We removed tags and stopwords
from the pages, and stemmed each word. The summaryof each directory is listed in Table I. We treated eachdirectory as a target cluster, and made four datasets using
those clusters. Table II lists the number of samples, thenumber of attributes, and the number of directories of thedata sets used in our experiments.
3) CLUTO data sets: CLUTO2 is a software package
for clustering low- and high-dimensional datasets and foranalyzing the characteristics of various clusters. In our
experiments, seven CLUTO data sets were adopted. The
seven CLUTO data sets are tr11, tr12, tr31, tr41, tr45,
k1b, and re1. Table III describes statistics on CLUTO
1 http://www.dmoz.org/
2 http://glaros.dtc.umn.edu/gkhome/views/cluto

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012

TABLE III.
N O . OF CLUSTERS , ATTRIBUTES AND SAMPLES FOR CLUTO DATA
SETS

Data set
tr11
tr12
tr31
tr41
tr45
k1b
re1

No. of clusters
9
8
7
10
6
6
25

No. of attributes
6429
5804
10128
7454
8261
21839
3758

No. of samples
414
313
927
878
690
2340
1657

data sets including the number of samples, the number of
attributes and the number of clusters.
B. Evaluation Metrics
We used normalized mutual information as a metricto evaluate the qualities of the clustering outputs fromthe different methods. The normalized mutual information
measures the consistency of the clustering output compared to the ground truth. It reaches a maximum valueof 1 only if the membership ϕc perfectly matches ϕg
and a minimum 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
using the following equation
M I(ϕg , ϕc )NMI(ϕg , ϕc ) =(4)max(H(ϕg ), H(ϕc ))where M I(ϕg , ϕc ) denotes the next equation
M I(ϕg , ϕc ) =

k ∑
k
∑

pg,c (i, j) log

i=1 j=1

pg,c (i, j)
pg (i)pc (j)(5)

H(ϕg ) comes from the following equation
H(ϕg ) =k∑1
pg (i)(6)

1
pc (j)(7)

pg (i) log

i=1

and H(ϕc ) denotes the next equation
H(ϕc ) =k∑j=1

pc (j) log

The pg (i) is the percentage of points in cluster i basedon the ground truth, i.e.
∑n1(ϕg (xl ) − i)pg (i) = l=1.
(8)nSimilarly, pc (j) denotes the following equation∑n1(ϕc (xl ) − j)(9)
pc (j) = l=1nand pg,c (i, j) is the percentage of points that belong tocluster i in ϕg and also cluster j in ϕc , i.e.
∑n1(ϕg (xl ) − i)1(ϕc (xl ) − j)pg,c (i, j) = l=1. (10)n
The above defined metrics were used to evaluate theaccuracy of the k-means clustering method, KKZ method,
k-means++ clustering method and the proposed methods.
© 2012 ACADEMY PUBLISHER

PC1

55

PC2

Figure 12. Principal components

PC1

PC2

Figure 13. Initial centers ci of PCA based method

C. Compared methods
In our experiments, we tried to compare the performance of our proposed methods with the performanceof other methods. The other methods consist of the kmeans clustering method, KKZ method, and k-means++clustering method (See section II). Our proposed methods
are based on a k-means combined with an ICA based
seeding method and k-means combined with a PCA[23]based seeding method. k-means combined with ICA based
seeding method was explained in Section III. Now, we
briefly explain the k-means combined with a PCA based
seeding method.
At any given time, we can obtain principal components(PCs) from the given data x. Then, we define the following seeding method.
1a) Extract k principal components PC1 , . . . , PCkfrom given data X (Figure 12).
1b) Choose k initial centers ci (i = 1, · · ·′ , k), selecting
PCi ·xci = x′ ∈ X with a minimum |PC′ (Figure 13).
i ||x |
Steps 2)-4) proceed in the same way as with thestandard k-means clustering method. Figure 14 shows theconcept of the k-means clustering method combined witha PCA based seeding method.
V. E XPERIMENTS
This section discusses some of the experimental results
under the above experimental condition.
A. Experimental results for small data sets
The k-means and k-means++ clustering methods were
executed 100 times using different initializations over
all four data sets from the UCI repository3 . In our
experiments, the Euclid distance was used as a similarity
measure when the k-means clustering method was applied to the UCI repository. The KKZ method and the3 http://archive.ics.uci.edu/ml/

56

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012

TABLE VII.
E XPERIMENTAL RESULTS FOR breast-cancer DATA SET

x2

x6
x1

x4

x3

x5

NMI

k-meansk-means++
KKZ
PCA
ICA

0.743
0.743
0.743

NMI withmin. variance
0.743
0.743
-

max.
NMI
0.743
0.743
-

min.
NMI
0.743
0.743
-

avg.
NMI
0.743
0.743
-

TABLE VIII.
E XPERIMENTAL RESULTS FOR ODP Web corpus DATA SET

PC1

PC2

methodFigure 14. Concept of Our Proposed Method based on PCA

methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.531
0.500
0.638

NMI withmin. variance
0.555
0.555
-

max.
NMI
0.589
0.589
-

min.
NMI
0.392
0.425
-

avg.
NMI
0.514
0.525
-

TABLE IV.
E XPERIMENTAL RESULTS FOR iris DATA SET
methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.751
0.751
0.751

NMI withmin. variance
0.751
0.751
-

max.
NMI
0.751
0.751
-

min.
NMI
0.532
0.532
-

avg.
NMI
0.703
0.749
-

proposed method were executed only one time becausea unique initial seeding can be set up. Table IV lists
the experimental results for the iris data set. Table V
lists the experimental results for the wine data set. Table
VI lists the experimental results for the soybean-small
data set. Table VII lists the experimental results for thebreast-cancer data set. Tables IV, V, VI, and VII have an
averaged NMI, a maximum NMI, a minimum NMI, anda NMI when the clusters achieved minimum variance.
In IV, V, and VII tables, the NMIs of our proposed
method are the same as the maximum NMIs of the kmeans clustering method and the k-means++ clustering
method. The NMIs of our proposed methods are achievedby using only one initial seeding. Therefore, IV, V, andTABLE V.
E XPERIMENTAL RESULTS FOR wine DATA SET
methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.387
0.429
0.429

NMI withmin. variance
0.429
0.429
-

max.
NMI
0.429
0.429
-

min.
NMI
0.387
0.387
-

avg.
NMI
0.418
0.418
-

TABLE VI.
E XPERIMENTAL RESULTS FOR soybean-small DATA SET
methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.711
0.711
0.711

NMI withmin. variance
0.711
0.711
-

© 2012 ACADEMY PUBLISHER

max.
NMI
1.000
1.000
-

min.
NMI
0.518
0.711
-

avg.
NMI
0.714
0.806
-

VII tables show that the proposed method outperforms
both the k-means clustering method and the k-means++clustering method for the iris, wine, and breast-cancer
data sets of the UCI repository.
In IV and VII tables, the NMIs of the KKZ method
are the same as the maximum NMIs of the k-meansclustering method and the k-means++ clustering method.
The NMIs of the KKZ method are achieved by using
only one initial seeding. Therefore, the IV and VII tables
also show that the KKZ method outperforms both the kmeans clustering method and the k-means++ clustering
method for the iris and breast-cancer data sets of the
UCI repository. However the V table shows that theperformance of the KKZ method is the worst among thecompared methods in our experiments.
We generally cannot provide true cluster data. Having
a NMI with minimum variance is the most important
issue for real-world applications. Table VI shows that
the NMIs of our proposed method are the same as the
NMIs of the k-means clustering method and k-means++clustering method when the clusters achieved minimum
variance. This situation shows that the performance of our
proposed method is the same as the performance of the
k-means clustering method and the k-means++ clustering
method for the soybean-small data set. And the NMI withminimum variance is achieved by using only one initial
seeding.
In our experiments, the k-means clustering and kmeans++ clustering methods run 100 times using different
initializations for the ODP Web corpus data set. The
proposed method runs only one time because it can set
up a unique initial seeding. Table II lists the experimental
results of the ODP Web corpus data set. When the kmeans clustering method was applied to an ODP corpus,
the cosine distance was used as a similarity measure in our
experiments. The KKZ method and the proposed method
were executed only one time because they can set up aunique initial seeding.
Table VIII shows that the NMI of our proposed method
is better than the NMI of the k-means clustering and k-

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012means++ clustering methods when the clusters achieveda minimum variance for the ODP Web corpus data set.
Table VIII shows that the NMI of the proposed method
was 0.638. This value is better than the maximum NMIof the k-means clustering method and the maximum NMI
of k-means++ clustering method. In addition, the NMI of
the proposed method is better than the NMI of the KKZ
method and the NMI of PCA based method. Therefore,
Table II shows that the proposed method outperforms
the k-means clustering method, k-means++ clustering
method, KKZ method and PCA based method for the
ODP Web corpus data set. In addition, the best NMI isachieved by using only one initial seeding.
B. Experimental results for large data sets
The k-means and k-means++ clustering methods were
executed 100 times using different initializations for allseven data sets from the CLUTO data sets. In our experiments, the cosine distance was used as a similarity
measure when k-means clustering method was applied to
CLUTO data sets. KKZ method and the proposed method
were executed only one time because they could set up
a unique initial seeding. Table IX lists the experimental
results for the seven CLUTO data sets.
It is difficult to understand aspects of performance ofcompared methods from table IX. Therefore, we would
now like to introduce the ratio between the number of
attributes and the number of samples. We could order the
results from the CLUTO data sets by using the value ofthe ratio. Table X lists the ordered results of CLUTO data
sets. The underlined performances indicate the best ones.
The ratio denotes the following equation
ratio =

No. of attributes.
No. of samples(11)

The NMIs of the k-means and k-means++ are NMIs
with the minimum variance in table IX.
When the ratio is smaller than 10.00, table X showsthat shows the performance the proposed method basedon ICA is better than the performance of the k-meansclustering method, k-means++ clustering method and
KKZ method. In other words, the NMIs of the proposed
method is better than the NMIs of the k-means clustering method, k-means++ clustering method and KKZ
method for k1b, tr41 and re1 CLUTO data sets. However,when the ratio is larger than 10.00, the performance ofthe proposed method based on ICA is not better thanthe performances of the k-means clustering method, kmeans++ clustering method and KKZ method in table X.
In other words, the NMIs of the proposed method are
not better than the NMIs of k-means clustering method,
k-means++ clustering method, and KKZ method for tr12,
tr11, tr45, and tr31 CLUTO data sets. When the ratio islarger than 10.00, the number of attributes is much larger
than the number of samples and it is difficult to find stable
independent components. Therefore, the proposed methodwith ICA may not be able to perform well.
© 2012 ACADEMY PUBLISHER

57

TABLE IX.
E XPERIMENTAL RESULTS FOR CLUTO DATA SETS
methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.578
0.619
0.585

methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.683
0.500
0.638

methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.439
0.504
0.438

methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.584
0.680
0.667

methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.660
0.744
0.722

methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.491
0.438
0.587

methodNMI

k-meansk-means++
KKZ
PCA
ICA

0.557
0.557
0.575

tr11
NMI withmin. variance
0.630
0.669
tr12
NMI withmin. variance
0.664
0.621
tr31
NMI withmin. variance
0.579
0.523
tr41
NMI withmin. variance
0.623
0.651
tr45
NMI withmin. variance
0.769
0.794
k1b
NMI withmin. variance
0.537
0.523
re1
NMI withmin. variance
0.541
0.545
-

max.
NMI
0.730
0.717
-

min.
NMI
0.523
0.545
-

avg.
NMI
0.635
0.632
-

max.
NMI
0.752
0.689
-

min.
NMI
0.521
0.425
-

avrg.
NMI
0.664
0.621
-

max.
NMI
0.676
0.641
-

min.
NMI
0.377
0.392
-

avg.
NMI
0.503
0.507
-

max.
NMI
0.699
0.730
-

min.
NMI
0.533
0.530
-

avg.
NMI
0.611
0.620
-

max.
NMI
0.787
0.794
-

min.
NMI
0.594
0.564
-

avg.
NMI
0.696
0.697
-

max.
NMI
0.649
0.611
-

min.
NMI
0.421
0.422
-

avg.
NMI
0.518
0.521
-

max.
NMI
0.578
0.575
-

min.
NMI
0.460
0.465
-

avg.
NMI
0.523
0.545
-

C. Computational costs
Next, we explain the computational cost of the proposed method from an experimental point of view. In our
experiments, we used a Windows Vista 32 bit machinethat has an Intel Core 2 Duo E8600 3.34 GHz and 4 GB
memory. Table XI lists computational times of four UCI
repository data sets.
We can find from this table that the computational timeof the proposed method is larger than the computationaltime of the k-means clustering method for the four UCI
repository data sets. The k-means clustering method was

58

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012

TABLE X.
O RDERED EXPERIMENTAL RESULTS BASED ON RATIO ( NO . OF
ATTRIBUTES / NO . OF SAMPLES ) FOR CLUTO DATA SETS

data set
tr12
tr11
tr45
tr31
k1b
tr41
re1

ratio
18.54
15.52
11.97
10.92
9.33
8.49
2.26

proposed
0.638
0.585
0.722
0.438
0.587
0.667
0.575

k-means
0.664
0.630
0.769
0.579
0.537
0.623
0.541

k-means++
0.621
0.669
0.794
0.523
0.523
0.651
0.545

KKZ
0.683
0.578
0.660
0.439
0.491
0.584
0.557

TABLE XI.
C OMPUTATIONAL TIMES ( SEC .) FOR UCI REPOSITORY DATA SETS
methodk-means
proposediris
0.00320.0748wine
0.00340.0948breast-cancer
0.00590.0643

soybean-small
0.00410.0773

executed 100 times using different initializations for all
four data sets of the UCI repository.
Table XII lists computational times of the tr45 CLUTO
data set. We can find from this table that the computational time of the proposed method is smaller than thecomputational time of the k-means clustering method fora CLUTO data set. The k-means clustering method was
executed 100 times using different initializations for all
four data sets of the UCI repository. In other words, thecomputational time of the proposed method is smaller
than the computational time of the k-means-clustering
method for large data sets that contain many attributes.
Generally, the Web contains a lot of documents with many
attributes. Therefore, the proposed method is useful for
the Web.
VI. C ONCLUSION
We proposed a method that combines the k-meansclustering method with an Independent Component Analysis based seeding method and a Principal Component
Analysis based seeding method, and compared the performances of the proposed method with the performanceof the standard k-means clustering method, k-mean++clustering method, and k-means clustering method witha KKZ seeding method.
From our experimental results for small data sets (UCIrepository data sets), our proposed method performed thesame as or better than the standard k-means clustering
method, k-means++ clustering method, and k-means clustering method with a KKZ seeding method.
From our experimental results for large datasets(CLUTO data sets), our proposed method basedon ICA performed better than the standard k-meansclustering method, k-means++ clustering method, andk-means clustering method with a KKZ seeding method
when the ratio between the number of attributes and thenumber of samples is smaller than 10.00. When the ratio
between the number of attributes and the number ofsamples is larger than 10.00, our proposed method basedon ICA did not perform better than the standard k-meansclustering method, k-means++ clustering method, or© 2012 ACADEMY PUBLISHERTABLE XII.
C OMPUTATIONAL TIMES ( SEC .) FOR tr45 CLUTO DATA SET
methodk-means
proposed

tr45
90.42 × 100
52.39+90.42

k-means clustering method with a KKZ seeding method.
Generally, the Web has a lot of documents and the ratio
between the number of attributes and the number ofsamples is small. Therefore, the proposed method isuseful for the Web.
For our future work, we plan to theoretically analyze
the computational cost of the proposed method, and to
conduct research on how to decide the number of clusters
based on the observed data distribution.
ACKNOWLEDGMENT
This research was partially supported by the Ministryof Education, Science, Sports and Culture, Grant-in-Aid
for Scientific Research (B), 23300063, 2011.
R EFERENCES[1] S. Basu, I. Davidson, and K. Wagstaff, Eds., Constrained
Clustering: Advances in Algorithms, Theory, and Applications. Chapman and Hall/CRC, 2008.
[2] C. Ding, “A Tutorial on Spectral Clustering
Part I: Basic Theory,” 2004. [Online]. Available:
http://ranger.uta.edu/ chqding/Spectral/[3] P. Berkhin, “Survey of clustering data mining techniques,”
Accrue Software, San Jose, CA, Tech. Rep., 2002.
[4] C. Carpineto, S. Osiński, G. Romano, and D. Weiss,“A survey of web clustering engines,” ACM Computing
Survey, vol. 41, pp. 17:1–17:38, 2009.
[5] P. Ferragina and A. Gulli, “A personalized search engine
based on web-snippet hierarchical clustering,” in Special
interest tracks and posters of the 14th international conference on World Wide Web (WWW’05), 2005, pp. 801–810.
[6] R. Navigli and G. Crisafulli, “Inducing word senses toimprove web search result clustering,” in Proceedings ofthe 2010 Conference on Empirical Methods in Natural
Language Processing (EMNLP’10), 2010, pp. 116–126.
[7] B. Stein, T. Gollub, and D. Hoppe, “Beyond precision@10:
clustering the long tail of web search results,” in Proceedings of the 20th ACM international conference on Information and knowledge management (CIKM’11), 2011, pp.
2141–2144.
[8] Y. Wang and M. Kitsuregawa, “Evaluating contents-link
coupled web page clustering for web search results,”
in Proceedings of the eleventh international conferenceon Information and knowledge management (CIKM ’02),
2002, pp. 499–506.
[9] D. Crabtree, P. Andreae, and X. Gao, “Query directed web page clustering,” in Proceedings of the 2006
IEEE/WIC/ACM International Conference on Web Intelligence (WI’06), 2006, pp. 202–210.
[10] P. Li, B. Wang, W. Jin, and Y. Cui, “User-related tag
expansion for web document clustering,” in Proceedings ofthe 33rd European conference on Advances in information
retrieval (ECIR’11), 2011, pp. 19–31.
[11] C. Lu, X. Chen, and E. K. Park, “Exploit the tripartite network of social tagging for web clustering,” in Proceedingsof the 18th ACM conference on Information and knowledge
management (CIKM ’09), 2009, pp. 1545–1548.

JOURNAL OF EMERGING TECHNOLOGIES IN WEB INTELLIGENCE, VOL. 4, NO. 1, FEBRUARY 2012[12] B. Gao, T.-Y. Liu, T. Qin, X. Zheng, Q.-S. Cheng, and
W.-Y. Ma, “Web image clustering by consistent utilizationof visual features and surrounding texts,” in Proceedingsof the 13th annual ACM international conference on Multimedia (MULTIMEDIA’05), 2005, pp. 112–121.
[13] T. Onoda, M. Sakai, and S. Yamada, “Independent component analysis based seeding method for k-means clustering,” in In Proceedings of the International Workshop
on Intelligent Web Interaction 2011 (IWI-2011), 2011, pp.
122–125.
[14] T. Onoda, M. Sakai, and S. Yamad, “Careful seeding basedon independent component analysis for k-means clustering,” in In Proceedings of the International Workshop on
Intelligent Web Interaction 2010 (IWI-2010), 2010, pp.
112–115.
[15] T. Onoda, M. Sakai, and S. Yamad, “Seeding method
based on independent component analysis for k-meansclustering,” in In Proceedings of Joint 5th International
Conference on Soft Computing and Intelligent Systems
and 11th International Symposium on Advanced Intelligent
Systems (SCIS&ISIS-2010), 2010, pp. 1306–1309.
[16] 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.
[17] S. P. Lloyd, “Least squares quantization in pcm,” IEEE
Transactions on Information Theory, vol. 28, no. 2, pp.
129–136, 1982.
[18] 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.
[19] D. Arthur and S. Vassilvitskii, “k-means++: the advantagesof careful seeding,” in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 2007,
pp. 1027–1035.
[20] A. Hyv̈rinen and E. Oja, “Independent component analysis:
Algorithms and applications,” Neural Networks, vol. 13,
no. 4-5, pp. 411–430, 2000.
[21] A. Hyv̈rinen, “Fast and robust fixed-point algorithms forindependent component analysis,” IEEE Transactions on
Neural Networks, vol. 10, no. 3, pp. 626–634, 1999.
[22] A. Hyv̈rinen and E. Oja, “A fast fixed-point algorithm forindependent component analysis,” Neural Computation,
vol. 9, no. 7, pp. 1483–1492,, 1997.
[23] I. T. Jolliffe, Principal Component Analysis. Springer,
2002.
Takashi Onoda graduated from International Christian University, Tokyo, Japan in 1986. He received the M.S. degree innuclear engineering from Tokyo Institute of Technology, Tokyo,
Japan in 1988.
He works at Central Research Institute of Electric Power
Industry from 1988. He received the Dr. Eng. degree in mathematical engineering from University of Tokyo, Tokyo, Japan
in 2000. He worked as a visiting researcher in GMD FIRST
in Berlin from September in 1997 to September in 1998. He
is a sector leader at Central Research institute of ElectricPower Industry and a visiting professor at Tokyo Institute ofTechnology.
His research interests are in statistical learning theory and its
applications. He is a member of JSAI.

Miho Sakai graduated from Musashi Institute of Technology,
Tokyo, Japan in 2009. She received her MS degree in engineering from Tokyo Institute of Technology in 2011. Her researchinterest is in clustering method.
© 2012 ACADEMY PUBLISHER

59

Seiji Yamada is a professor at the National Institute of Informatics. Previously he worked at Tokyo Institute of Technology. He
received B.S. (1984), M.S. (1986) and the Ph.D. (1989) degrees
in artificial intelligence from Osaka University.
His research interests are in the design of intelligent interaction including Human-Agent Interaction, intelligent Webinteraction and interactive machine learning. He is a member ofIEEE, AAAI, ACM, JSAI, IPSJ and HIS.