Optimality of Spectral Clustering for Gaussian Mixture Model
Optimality of Spectral Clustering for Gaussian Mixture Model
复制标题
高斯混合模型谱聚类的最优性
DOI：
--
复制
发表时间：
2019
影响因子：
4.5
通讯作者：
Harrison H. Zhou
中科院分区：
文献类型：
--
作者：
Matthias Löffler;A. Zhang;Harrison H. Zhou
谱聚类是对高维数据进行聚类的一种常用算法。它易于实现，计算效率高。尽管它的流行和成功的应用，它的理论特性还没有得到充分的理解。本文证明了在高斯混合模型中，当聚类数固定且信噪比足够大时，谱聚类是最小最大最优的。谱间隔条件在文献中被广泛假设来分析谱聚类。相反，这些条件是不需要建立本文的谱聚类的最优性。
Spectral clustering is one of the most popular algorithms to group high dimensional data. It is easy to implement and computationally efficient. Despite its popularity and successful applications, its theoretical properties have not been fully understood. In this paper, we show that spectral clustering is minimax optimal in the Gaussian Mixture Model with isotropic covariance matrix, when the number of clusters is fixed and the signal-to-noise ratio is large enough. Spectral gap conditions are widely assumed in the literature to analyze spectral clustering. On the contrary, these conditions are not needed to establish optimality of spectral clustering in this paper.
DOI：
10.1287/opre.2022.2317
发表时间：
2019-12
期刊：
ArXiv
影响因子：
--
作者：
Prateek Srivastava;Purnamrita Sarkar;G. A. Hanasusanto
通讯作者：
Prateek Srivastava;Purnamrita Sarkar;G. A. Hanasusanto