Kmeans Clustering via Principal Component （通过主成分k means聚类）.pdf

K-means Clustering via Principal Component Analysis Chris Ding chqding@ Xiaofeng He xhe@ Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720 Abstract that data points belonging to same cluster are sim- Principal component analysis (PCA) is a ilar while data points belonging to different clusters are dissimilar. One of the most popular and efficient widely used statistical technique for unsuper- vised dimension reduction. K-means cluster- clustering methods is the K-means method (Hartigan ing is a commonly used data clustering for Wang, 1979; Lloyd, 1957; MacQueen, 1967) which unsupervised learning tasks. Here we prove uses prototypes (centroids) to represent clusters by op- that principal components are the continuous timizing the squared error function. (A detail account of K-means and related ISODATA methods are given solutions to the discrete cluster membership indicators for K-means clustering. Equiva- in (Jain Dubes, 1988), see also (Wallace, 1989).) lently, we show that the subspace spanned On the other end, high dimensional data are often by the cluster centroids are given by spec- transformed into lower dimensional data via the princi- tral expansion of the data covariance matrix pal component analysis (PCA)(Jolliffe, 2002) (or sin- truncated at K − 1 terms. These results in