标题： 谱聚类的一致性 显示英文标题

标题： Consistency of spectral clustering

摘要： 一致性是分析随机抽样数据的所有统计程序的关键属性。 令人惊讶的是，尽管几十年来人们一直在研究，但大多数聚类算法的一致性却知之甚少。 本文我们研究了流行的谱聚类算法族的一致性，该算法通过图拉普拉斯矩阵的特征向量来聚类数据。 我们开发了新的方法来证明，对于样本容量增大时，那些特征向量会收敛到某些极限算子的特征向量。 结果表明，我们可以证明谱聚类两大主要类别之一（归一化聚类）在非常一般的条件下收敛，而另一个（未归一化聚类）仅在强附加假设下才一致，而这些假设在实际数据中并不总是成立。 我们得出结论，我们的分析提供了有力的证据，证明归一化谱聚类的优越性。 显示英文摘要

摘要： Consistency is a key property of all statistical procedures analyzing randomly sampled data. Surprisingly, despite decades of work, little is known about consistency of most clustering algorithms. In this paper we investigate consistency of the popular family of spectral clustering algorithms, which clusters the data with the help of eigenvectors of graph Laplacian matrices. We develop new methods to establish that, for increasing sample size, those eigenvectors converge to the eigenvectors of certain limit operators. As a result, we can prove that one of the two major classes of spectral clustering (normalized clustering) converges under very general conditions, while the other (unnormalized clustering) is only consistent under strong additional assumptions, which are not always satisfied in real data. We conclude that our analysis provides strong evidence for the superiority of normalized spectral clustering.