论文标题
对光谱聚类及以后的更严格的分析
A Tighter Analysis of Spectral Clustering, and Beyond
论文作者
论文摘要
这项工作研究了经典的光谱聚集算法，该算法将某些图的顶点嵌入了$ g =（v_g，e_g）$中，使用$ g $的某些矩阵的$ k $ eigenVectors纳入$ \ mathbb {r}^k $，并将其应用于$ k $ k $ - means $ k $ v_ $ v_ $ v_ $ k $ k $ k clusters。我们的第一个结果是对光谱聚类的性能进行更严格的分析，并解释了为什么它在某些弱弱的状态下起作用，而不是文献中研究的谱。对于第二个结果，我们表明，通过应用少于$ k $的特征向量来构建嵌入，光谱群集可以在许多实际情况下产生更好的输出；该结果是光谱聚类中的第一个结果。除了其概念性和理论意义外，我们工作的实际影响还通过对合成和现实世界数据集的经验分析证明，其中光谱聚类会产生可比或更好的结果，而较少$ k $ k $ eigenVectors。
This work studies the classical spectral clustering algorithm which embeds the vertices of some graph $G=(V_G, E_G)$ into $\mathbb{R}^k$ using $k$ eigenvectors of some matrix of $G$, and applies $k$-means to partition $V_G$ into $k$ clusters. Our first result is a tighter analysis on the performance of spectral clustering, and explains why it works under some much weaker condition than the ones studied in the literature. For the second result, we show that, by applying fewer than $k$ eigenvectors to construct the embedding, spectral clustering is able to produce better output for many practical instances; this result is the first of its kind in spectral clustering. Besides its conceptual and theoretical significance, the practical impact of our work is demonstrated by the empirical analysis on both synthetic and real-world datasets, in which spectral clustering produces comparable or better results with fewer than $k$ eigenvectors.
