Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering
Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering
复制标题
高维高斯混合聚类中的相变和优化算法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
L. Zdeborová
中科院分区：
文献类型：
--
作者：
T. Lesieur;C. D. Bacco;Jessica E. Banks;Florent Krzakala;Cristopher Moore;L. Zdeborová
本文考虑高维极限下的高斯混合聚类问题，其中数据由n维m个点组成，n，m → ∞，α = m/n保持有限。使用统计物理学中精确但不严格的方法，我们确定了α的临界值和聚类之间的距离，在该距离处，信息理论上可以比机会更好地将成员关系重建到聚类中。我们还确定了贝叶斯最优估计算法所能达到的精度。特别是，我们发现，当集群的数量足够大，r > 4+2 α，有一个差距之间的阈值信息理论上的最佳性能和阈值，在已知的算法成功。
We consider the problem of Gaussian mixture clustering in the high-dimensional limit where the data consists of m points in n dimensions, n,m → ∞ and α = m/n stays finite. Using exact but non-rigorous methods from statistical physics, we determine the critical value of α and the distance between the clusters at which it becomes information-theoretically possible to reconstruct the membership into clusters better than chance. We also determine the accuracy achievable by the Bayes-optimal estimation algorithm. In particular, we find that when the number of clusters is sufficiently large, r > 4+2√α, there is a gap between the threshold for information-theoretically optimal performance and the threshold at which known algorithms succeed.