Consistency of anchor-based spectral clustering
Consistency of anchor-based spectral clustering
复制标题
DOI：
10.1093/imaiai/iaab023
复制
发表时间：
2021-10-11
影响因子：
1.6
通讯作者：
Higham, Desmond J.
中科院分区：
文献类型：
--
作者：
de Kergorlay, Henry-Louis;Higham, Desmond J.
基于锚的技术降低了谱聚类算法的计算复杂性。尽管实证测试显示出有希望的结果，但目前锚定方法缺乏理论支持。我们定义了一种特定的基于锚的算法，并表明它可以接受严格的分析，并且在实践中有效。我们在渐近设置中建立了该方法的理论一致性，其中数据是从基础连续概率分布中采样的。特别是，我们为算法中最近邻居的数量提供了尖锐的渐近条件，这确保了基于锚的方法可以恢复彼此相隔正距离的高概率不相交簇。我们说明了算法在合成数据上的性能，并解释了如何使用理论收敛分析来指导参数缩放的实际选择。我们还在两个大规模真实数据集上测试了算法的准确性和效率。我们发现该算法比标准谱聚类具有明显的优势。我们还发现它与 Chen 和 Cai 的最先进的 LSC 方法（第 25 届 AAAI 人工智能会议，2011 年）具有竞争力，同时具有一致性保证的额外好处。
Anchor-based techniques reduce the computational complexity of spectral clustering algorithms. Although empirical tests have shown promising results, there is currently a lack of theoretical support for the anchoring approach. We define a specific anchor-based algorithm and show that it is amenable to rigorous analysis, as well as being effective in practice. We establish the theoretical consistency of the method in an asymptotic setting where data is sampled from an underlying continuous probability distribution. In particular, we provide sharp asymptotic conditions for the number of nearest neighbors in the algorithm, which ensure that the anchor-based method can recover with high probability disjoint clusters that are mutually separated by a positive distance. We illustrate the performance of the algorithm on synthetic data and explain how the theoretical convergence analysis can be used to inform the practical choice of parameter scalings. We also test the accuracy and efficiency of the algorithm on two large scale real data sets. We find that the algorithm offers clear advantages over standard spectral clustering. We also find that it is competitive with the state-of-the-art LSC method of Chen and Cai (Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011), while having the added benefit of a consistency guarantee.