高维噪声下k-means易失效，因多数划分都成固定点
An Observation on Lloyd's k-Means Algorithm in High Dimensions
- 用简单GMM模型分析高维k-means失败机制
- 高维高噪声时几乎所有数据划分都是算法固定点
- 对冷冻电镜等复杂场景的分析有重要启示
聚类与簇均值估计是统计学和机器学习中的核心问题，k-means与期望最大化（EM）是两种广泛应用的算法。本文针对高维设置下高噪声、小样本情形中k-means的失效现象，基于一个简单的高斯混合模型（GMM）提供了理论解释。我们识别出若干参数范围，在这些范围内，几乎所有的数据划分都以高概率成为k-means算法的固定点。该研究受更复杂情形（如掩码GMM）及冷冻电镜应用中出现的问题驱动。
原文摘要 · Abstract (English)
Clustering and estimating cluster means are core problems in statistics and machine learning, with k-means and Expectation Maximization (EM) being two widely used algorithms. In this work, we provide a theoretical explanation for the failure of k-means in high-dimensional settings with high noise and limited sample sizes, using a simple Gaussian Mixture Model (GMM). We identify regimes where, with high probability, almost every partition of the data becomes a fixed point of the k-means algorithm. This study is motivated by challenges in the analysis of more complex cases, such as masked GMMs, and those arising from applications in Cryo-Electron Microscopy.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。