标题： Lloyd算法在扰动下的一致性 显示英文标题

标题： Consistency of Lloyd's Algorithm Under Perturbations

摘要： 在无监督学习的背景下，Lloyd算法是最常用的聚类算法之一。 它激发了大量研究工作，探讨在各种设置下具有真实聚类情况的算法正确性。 特别是，在2016年，Lu和Zhou表明，在从子高斯混合分布中抽取的$n$个独立样本上，Lloyd算法在$O(\log(n))$次迭代后，其错误聚类率是指数有界的，假设算法的初始化是适当的。 然而，在许多应用中，真实的样本是不可观测的，需要通过预处理管道（如适当数据矩阵上的谱方法）从数据中学习。 我们表明，在子高斯混合分布中扰动样本上的Lloyd算法的错误聚类率，在适当初始化的假设下，并且扰动相对于子高斯噪声较小的情况下，经过$O(\log(n))$次迭代后也是指数有界的。 在具有真实聚类的典型情况下，我们推导出诸如$k$-means$++$算法的界限，以找到良好的初始化，从而通过主要结果实现聚类的正确性。 我们展示了这些结果对测量从数据中派生聚类的统计显著性的管道（如SigClust）的含义。 我们利用这些一般结果，推导出在一系列应用中Lloyd算法的错误聚类率的理论保证，包括高维时间序列、多维缩放以及通过谱聚类进行稀疏网络的社区检测。 显示英文摘要

摘要： In the context of unsupervised learning, Lloyd's algorithm is one of the most widely used clustering algorithms. It has inspired a plethora of work investigating the correctness of the algorithm under various settings with ground truth clusters. In particular, in 2016, Lu and Zhou have shown that the mis-clustering rate of Lloyd's algorithm on $n$ independent samples from a sub-Gaussian mixture is exponentially bounded after $O(\log(n))$ iterations, assuming proper initialization of the algorithm. However, in many applications, the true samples are unobserved and need to be learned from the data via pre-processing pipelines such as spectral methods on appropriate data matrices. We show that the mis-clustering rate of Lloyd's algorithm on perturbed samples from a sub-Gaussian mixture is also exponentially bounded after $O(\log(n))$ iterations under the assumptions of proper initialization and that the perturbation is small relative to the sub-Gaussian noise. In canonical settings with ground truth clusters, we derive bounds for algorithms such as $k$-means$++$ to find good initializations and thus leading to the correctness of clustering via the main result. We show the implications of the results for pipelines measuring the statistical significance of derived clusters from data such as SigClust. We use these general results to derive implications in providing theoretical guarantees on the misclustering rate for Lloyd's algorithm in a host of applications, including high-dimensional time series, multi-dimensional scaling, and community detection for sparse networks via spectral clustering.