Kernel k-means: spectral clustering and normalized cuts Export

@inproceedings{citeulike:464442, abstract = {Kernel k -means and spectral clustering have both been used to identify clusters that are non-linearly separable in input space. Despite significant research, these methods have remained only loosely related. In this paper, we give an explicit theoretical connection between them. We show the generality of the weighted kernel k -means objective function, and derive the spectral clustering objective of normalized cut as a special case. Given a positive definite similarity matrix, our results lead to a novel weighted kernel k -means algorithm that monotonically decreases the normalized cut. This has important implications: a) eigenvector-based algorithms, which can be computationally prohibitive, are not essential for minimizing normalized cuts, b) various techniques, 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 interesting data sets, including diametrical clustering of large gene-expression matrices and a handwriting recognition data set.}, address = {New York, NY, USA}, author = {Dhillon, Inderjit S. and Guan, Yuqiang and Kulis, Brian}, booktitle = {KDD '04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining}, citeulike-article-id = {464442}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1014118}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1014052.1014118}, doi = {10.1145/1014052.1014118}, isbn = {1-58113-888-1}, keywords = {clustering, spectral}, location = {Seattle, WA, USA}, pages = {551--556}, posted-at = {2007-03-13 01:40:06}, priority = {5}, publisher = {ACM}, title = {Kernel k-means: spectral clustering and normalized cuts}, url = {http://dx.doi.org/10.1145/1014052.1014118}, year = {2004} }

TY - CONF ID - citeulike:464442 L3 - citeulike-article-id:464442 N2 - Kernel k -means and spectral clustering have both been used to identify clusters that are non-linearly separable in input space. Despite significant research, these methods have remained only loosely related. In this paper, we give an explicit theoretical connection between them. We show the generality of the weighted kernel k -means objective function, and derive the spectral clustering objective of normalized cut as a special case. Given a positive definite similarity matrix, our results lead to a novel weighted kernel k -means algorithm that monotonically decreases the normalized cut. This has important implications: a) eigenvector-based algorithms, which can be computationally prohibitive, are not essential for minimizing normalized cuts, b) various techniques, 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 interesting data sets, including diametrical clustering of large gene-expression matrices and a handwriting recognition data set. CY - Seattle, WA, USA SN - 1-58113-888-1 AD - New York, NY, USA EP - 556 TI - Kernel k-means: spectral clustering and normalized cuts PB - ACM T2 - KDD '04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining SP - 551 KW - clustering KW - spectral AU - Dhillon, Inderjit AU - Guan, Yuqiang AU - Kulis, Brian PY - 2004/// UR - http://dx.doi.org/10.1145/1014052.1014118 ER -