文件名称：A Unified View of Spectral Clustering
文件大小：330KB
文件格式：PDF
更新时间：2011-11-28 04:00:29
Spectral Clustering
We formulate a discrete optimization problem that leads to a simple and informative derivation of a widely used class of spectral clustering algorithms. Regarding the algorithms as attempting to bi-partition a weighted graph with N vertices, our derivation indicates that they are inherently tuned to tolerate all partitions into two non-empty sets, independently of the cardinality of the two sets. This approach also helps to explain the difference in behavior observed between methods based on the unnormalized and normalized graph Laplacian. We also give a direct explanation of why Laplacian eigenvectors beyond the Fielder vector may contain ne-detail information of relevance to clustering. Another advantage of our discrete formulation is that it admits a random graph interpretation, showing that spectral clustering may be viewed as maximum likelihood partitioning under the assumption that the data is an instance of a graph with random edge weights. The resulting distribution on the weights formalizes and quanti es the intuitive notion that vertices in the same cluster are more likely to have high weights than vertices in di erent clusters. Numerical experiments that illustrate the analysis are included.