Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithms
Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithms
复制标题
DOI：
--
复制
发表时间：
2017-12
期刊：
影响因子：
--
通讯作者：
A. Little;M. Maggioni;James M. Murphy
中科院分区：
文献类型：
--
作者：
A. Little;M. Maggioni;James M. Murphy
我们考虑了具有最长腿路径距离(LLPD)度量的聚类问题，该度量对于细长和不规则形状的簇是有用的。我们证明了当随机样本从高维空间中的多个本质低维集群中抽取时，在存在大量高维离群点的情况下，有限样本保证了关于该度量的聚类性能。通过将这些结果与LLPD的谱聚类相结合，我们给出了拉普拉斯特征统计量正确确定大类数据集的聚类数的条件，并证明了所提出的算法的标注精度是有保证的。我们的方法是非常通用的，并为任何超度量的谱聚类提供了性能保证。基于邻接图的多尺度分析，提出了一种高效、易于实现的LLPD近似算法，使得LLPD谱聚类的运行时间在数据点数量上是拟线性的。
We consider the problem of clustering with the longest-leg path distance (LLPD) metric, which is informative for elongated and irregularly shaped clusters. We prove finite-sample guarantees on the performance of clustering with respect to this metric when random samples are drawn from multiple intrinsically low-dimensional clusters in high-dimensional space, in the presence of a large number of high-dimensional outliers. By combining these results with spectral clustering with respect to LLPD, we provide conditions under which the Laplacian eigengap statistic correctly determines the number of clusters for a large class of data sets, and prove guarantees on the labeling accuracy of the proposed algorithm. Our methods are quite general and provide performance guarantees for spectral clustering with any ultrametric. We also introduce an efficient, easy to implement approximation algorithm for the LLPD based on a multiscale analysis of adjacency graphs, which allows for the runtime of LLPD spectral clustering to be quasilinear in the number of data points.