Kernel k-means, Spectral Clustering and Normalized Cuts

1 Kernel k-means, Spectral Clustering and Normalized CutsInderjit S. DhillonDept. of Computer SciencesUniversity of Texas at AustinAustin, TX GuanDept. of Computer SciencesUniversity of Texas at AustinAustin, TX KulisDept. of Computer SciencesUniversity of Texas at AustinAustin, TX and Spectral Clustering have both been usedto identify clusters that are non-linearly separable in inputspace. Despite significant research, these methods have re-mained only loosely related. In this paper, we give an ex-plicit theoretical connection between them. We show thegenerality of the weighted kernelk-means objective func-tion, and derive the Spectral Clustering objective of normal-ized cut as a special case.

2 Given a positive definite similaritymatrix, our results lead to a novel weighted kernelk-meansalgorithm that monotonically decreases the Normalized has important implications: a) eigenvector-based algo-rithms, which can be computationally prohibitive, are notessential for minimizing Normalized cuts , b) various tech-niques, such as local search and acceleration schemes, maybe used to improve the quality as well as speed of kernelk-means. Finally, we present results on several interest-ing data sets, including diametrical Clustering of large gene-expression matrices and a handwriting recognition data and Subject [Information Search and Retrieval]: InformationSearch and Retrieval; [Pattern Recognition]: Clus-teringGeneral TermsAlgorithms, TheoryKeywordsSpectral Clustering , Kernelk-means, Graph Partitioning1.

3 INTRODUCTIONC lustering has received a significant amount of attentionin the last few years as one of the fundamental problems indata is one of the most popular clusteringalgorithms. Recent research has generalized the algorithmPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a 04,August 22 25, 2004, Seattle, Washinton, USAC opyright 2004 ACM 1-58113-888-1/04/0008.

4 $ many ways; for example, similar algorithms for clusteringcan be obtained using arbitrary Bregman divergences as thedistortion measure [2]. Other advances include using localsearch to improve the Clustering results [5] and using thetriangle inequality to speed up the computation [4].A major drawback tok-means is that it cannot separateclusters that are non-linearly separable in input space. Tworecent approaches have emerged for tackling such a prob-lem. One is kernelk-means, where, before Clustering , pointsare mapped to a higher-dimensional feature space using anonlinear function, and then kernelk-means partitions thepoints by linear separators in the new space.

5 The otherapproach is Spectral Clustering algorithms, which use theeigenvectors of an affinity matrix to obtain a Clustering ofthe data. A popular objective function used in Spectral clus-tering is to minimize the Normalized cut [12].On the surface, kernelk-means and Spectral clusteringappear to be completely different approaches. In this pa-per we first unite these two forms of Clustering under a sin-gle framework. By generalizing thek-means objective func-tion to use both weights and kernels, we show how the twoapproaches to Clustering are related. Specifically, we canrewrite the weighted kernelk-means objective function as atrace maximization problem whose relaxation can be solvedwith eigenvectors.

6 The result shows how a particular kerneland weight scheme is connected to the Spectral algorithm ofNg, Jordan, and Weiss [10]. However, the advantage to ourapproach is that we can generalize the Clustering algorithmto use arbitrary kernels and , we show that by choosing the weights in particu-lar ways, the weighted kernelk-means objective function isidenticalto the Normalized cut. Thus far, only eigenvector-based algorithms have been employed to minimize normal-ized cuts in Spectral Clustering and image , software to compute eigenvectors of large sparsematrices (often based on the Lanczos algorithm) can havesubstantial computational overheads, especially when a largenumber of eigenvectors are to be computed.

7 In such situa-tions, our equivalence has an important implication: we canusek-means-like iterative algorithms for directly minimizingthe Normalized -cut of a show the usefulness of our approach to the applicationof Clustering gene expression data by applying a quadratickernel (squared correlation) to obtain anti-correlated geneclusters and we illustrate the scalability of our algorithms interms of computation time by applying it to a large hand-writing recognition data word about notation. Capital letters such asA, X, YPolynomial Kernel (a,b) = (a b+c)dGaussian Kernel (a,b) = exp( ||a b||2/2 2)Sigmoid Kernel (a,b) = tanh(c(a b) + )Table 1: Examples of Kernel functionsand denote matrices; lower-case bold letters such asa,bdenote column vectors; script letters such asA,B,V,Erep-resent sets;||a||denotes theL2norm of a vector.

8 And||X||Fdenotes the Frobenius norm of a matrix, and is given by||X||F= (Pi,jX2ij)1 THE ESSENTIALSIn this section, we summarize the seemingly different ap-proaches of weighted kernelk-means and Spectral Weighted Kernel k-meansThek-means Clustering algorithm can be enhanced by theuse of a Kernel function; by using an appropriate nonlin-ear mapping from the original (input) space to a higher-dimensional feature space, one can extract clusters that arenon-linearly separable in input space. Furthermore, we cangeneralize the kernelk-means algorithm by introducing aweight for each pointa, denoted byw(a).

9 As we shall seelater, this generalization is powerful and encompasses thenormalized cut of a us denote clusters by j, and a partitioning of pointsas{ j}kj=1. Using the non-linear function , the objectivefunction of weighted kernelk-means is defined as:D({ j}kj=1) =kXj=1Xa jw(a) (a) mj 2(1)wheremj=Pb jw(b) (b)Pb jw(b).Note thatmjis the best cluster representative sincemj= argminzXa jw(a) (a) z Euclidean distance from (a) to centermjis given by (a) Pb jw(b) (b)Pb jw(b) 2= (a) (a) 2Pb jw(b) (a) (b)Pb jw(b)+Pb,c jw(b)w(c) (b) (c)(Pb jw(b))2.

10 (2)The dot products (a) (b) are computed using Kernel func-tion (see Table 1 for examples of popular Kernel functions),and are contained in the Kernel matrixK. All computationis in the form of such inner products, hence we can replaceall inner products by entries of the Kernel weighted kernelk-means algorithm (Algorithm 1)shares many properties of standardk-means; for example,the objective function value defined in (1) monotonically de-creases with each we are able to store the whole affinity matrixin main memory, we can analyze the time complexity of Al-gorithm 1.