nips nips2003 nips2003-107 nips2003-107-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Francis R. Bach, Michael I. Jordan
Abstract: Spectral clustering refers to a class of techniques which rely on the eigenstructure of a similarity matrix to partition points into disjoint clusters with points in the same cluster having high similarity and points in different clusters having low similarity. In this paper, we derive a new cost function for spectral clustering based on a measure of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem. Minimizing this cost function with respect to the partition leads to a new spectral clustering algorithm. Minimizing with respect to the similarity matrix leads to an algorithm for learning the similarity matrix. We develop a tractable approximation of our cost function that is based on the power method of computing eigenvectors. 1
[1] K. Wagstaff, C. Cardie, S. Rogers, and S. Schr¨ dl. Constrained K-means clustering with backo ground knowledge. In ICML, 2001.
[2] E. P. Xing, A. Y. Ng, M. I. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. In NIPS 15, 2003.
[3] S. X. Yu and J. Shi. Grouping with bias. In NIPS 14, 2002.
[4] S. D. Kamvar, D. Klein, and C. D. Manning. Spectral learning. In IJCAI, 2003.
[5] D. Martin, C. Fowlkes, D. Tal, and J. Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In ICCV, 2001.
[6] G. J. Brown and M. P. Cooke. Computational auditory scene analysis. Computer Speech and Language, 8:297–333, 1994.
[7] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. PAMI, 22(8):888– 905, 2000.
[8] H. Zha, C. Ding, M. Gu, X. He, and H. Simon. Spectral relaxation for K-means clustering. In NIPS 14, 2002.
[9] P. K. Chan, M. D. F. Schlag, and J. Y. Zien. Spectral K-way ratio-cut partitioning and clustering. IEEE Trans. CAD, 13(9):1088–1096, 1994.
[10] M. Gu, H. Zha, C. Ding, X. He, and H. Simon. Spectral relaxation models and structure analysis for K-way graph clustering and bi-clustering. Technical report, Penn. State Univ, Computer Science and Engineering, 2001.
[11] F. R. Bach and M. I. Jordan. Learning spectral clustering. Technical report, UC Berkeley, available at www.cs.berkeley.edu/˜fbach, 2003.
[12] G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, 1996.
[13] A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: analysis and an algorithm. In NIPS 14, 2001.
[14] L. J. Hubert and P. Arabie. Comparing partitions. Journal of Classification, 2:193–218, 1985.
[15] M. Meila and J. Shi. Learning segmentation by random walks. In NIPS 13, 2002.
[16] N. Cristianini, J. Shawe-Taylor, and J. Kandola. Spectral kernel methods for clustering. In NIPS 14, 2002.