Kernel k-means, Spectral Clustering and Normalized Cuts

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. 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.

essential for minimizing normalized cuts, b) various tech-niques, such as local search and acceleration schemes, may be used to improve the quality as well as speed of kernel k-means. Finally, we present results on several interest-ing data sets, including diametrical clustering of …

Loading..

Tags:

  Name, Essential, Cuts, Spectral, Normalized, Clustering, Spectral clustering and normalized cuts

Information

Related search queries