A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers
A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers
复制标题
DOI：
10.1287/opre.2022.2317
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Prateek Srivastava;Purnamrita Sarkar;G. A. Hanasusanto
中科院分区：
文献类型：
--
作者：
Prateek Srivastava;Purnamrita Sarkar;G. A. Hanasusanto
众所周知，传统的聚类算法，如k - 均值算法和普通的谱聚类算法，在存在异常值的情况下性能会显著下降。文献中先前的一些研究已经提出了这些算法的稳健变体；然而，它们没有提供任何理论保证。在关于高斯混合模型的先前聚类文献的基础上，普拉蒂克·R·斯里瓦斯塔瓦（Prateek R. Srivastava）、普尔纳米塔·萨卡尔（Purnamrita Sarkar）和格拉尼·A·哈纳苏桑托（Grani A. Hanasusanto）在他们的论文《一种用于含异常值的次高斯混合模型的稳健谱聚类算法》中开发了一种新的谱聚类算法，并在含异常值的一般次高斯混合模型设定下为该算法提供了误差界限。令人惊讶的是，他们推导出的误差界限与在相同无异常值设定下半定规划的最著名界限相匹配。在各种模拟数据集和真实世界数据集上进行的数值实验进一步表明，与其他最先进的算法相比，他们的算法对异常值不太敏感。
Traditional clustering algorithms such as k-means and vanilla spectral clustering are known to deteriorate significantly in the presence of outliers. Several previous works in literature have proposed robust variants of these algorithms; however, they do not provide any theoretical guarantees. Extending previous clustering literature on Gaussian mixture models, in their paper “A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers,” Prateek R. Srivastava, Purnamrita Sarkar, and Grani A. Hanasusanto developed a new spectral clustering algorithm and provided error bounds for the algorithm under a general sub-Gaussian mixture model setting with outliers. Surprisingly, their derived error bound matches with the best-known bound for semidefinite programs under the same setting without outliers. Numerical experiments on a variety of simulated and real-world data sets further demonstrate that their algorithm is less sensitive to outliers compared with other state-of-the-art algorithms.