A Note On Spectral Clustering
A Note On Spectral Clustering
复制标题
关于谱聚类的注释
DOI：
10.4230/lipics.esa.2016.57
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
K. Mehlhorn
中科院分区：
文献类型：
--
作者：
Pavel Kolev;K. Mehlhorn
谱聚类是一种流行且成功的方法，用于将图的节点划分为外部连接与体积（度之和）相比的比率很小的簇。为了划分成k个聚类，首先计算G的（归一化的）拉普拉斯算子的底部k个特征向量的近似，使用它将G的顶点嵌入k维欧几里得空间R^k，然后通过k均值聚类算法划分结果点。如何解释谱聚类的成功是理论界的一个重要课题。
Peng et al.（COLT，2015）在这个方向上迈出了重要的一步。他们表明，如果归一化拉普拉斯算子的第（k+1）和第k个特征值之间的差距足够大，谱聚类就可以证明有效。他们证明了一个结构和算法的结果。该算法的结果需要一个相当强的间隙假设，并没有分析标准的谱聚类范式，它取代谱嵌入热核嵌入和局部敏感哈希的k-均值聚类。
我们在两个方向上扩展他们的工作。在结构上，我们提高了质量保证的谱聚类的一个因素，同时削弱了差距的假设。在数学上，我们表明，标准的谱聚类的工作模式。此外，它甚至适用于结构结果所需的相同间隙假设。
Spectral clustering is a popular and successful approach for partitioning the nodes of a graph into clusters for which the ratio of outside connections compared to the volume (sum of degrees) is small. In order to partition into k clusters, one first computes an approximation of the bottom k eigenvectors of the (normalized) Laplacian of G, uses it to embed the vertices of G into k-dimensional Euclidean space R^k, and then partitions the resulting points via a k-means clustering algorithm. It is an important task for theory to explain the success of spectral clustering.
Peng et al. (COLT, 2015) made an important step in this direction. They showed that spectral clustering provably works if the gap between the (k+1)-th and the k-th eigenvalue of the normalized Laplacian is sufficiently large. They proved a structural and an algorithmic result. The algorithmic result needs a considerably stronger gap assumption and does not analyze the standard spectral clustering paradigm; it replaces spectral embedding by heat kernel embedding and k-means clustering by locality sensitive hashing.
We extend their work in two directions. Structurally, we improve the quality guarantee for spectral clustering by a factor of k and simultaneously weaken the gap assumption. Algorithmically, we show that the standard paradigm for spectral clustering works. Moreover, it even works with the same gap assumption as required for the structural result.