On Spectral Clustering: Analysis and an algorithm
On Spectral Clustering: Analysis and an algorithm
复制标题
DOI：
--
复制
发表时间：
2001-01
期刊：
影响因子：
--
通讯作者：
A. Ng;Michael I. Jordan;Yair Weiss
中科院分区：
文献类型：
--
作者：
A. Ng;Michael I. Jordan;Yair Weiss
尽管光谱聚类方法（利用从数据中导出的矩阵的特征向量对点进行聚类的算法）取得了许多经验上的成功，但仍有几个未解决的问题。第一。有各种各样的算法以稍微不同的方式使用特征向量。其次，这些算法中的许多都没有证据表明它们实际上会计算出合理的聚类。在本文中，我们提出了一个简单的光谱聚类算法，可以用几行Matlab实现。利用矩阵摄动理论的工具，对该算法进行了分析，并给出了预期算法性能良好的条件。我们还在一些具有挑战性的聚类问题上展示了令人惊讶的良好实验结果。
Despite many empirical successes of spectral clustering methods— algorithms that cluster points using eigenvectors of matrices derived from the data—there are several unresolved issues. First. there are a wide variety of algorithms that use the eigenvectors in slightly different ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems.