高维数据下k均值算法会失效，而哈蒂根算法能避免这一问题。
The Catastrophic Failure of The k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It
- 提出高维噪声环境下k均值算法的固定点陷阱机制
- 证明在高维中几乎所有划分都是固定点，导致算法退化
- 哈蒂根算法不受此影响，适合高维聚类场景
Lloyd's k-means算法是应用最广泛的聚类方法之一。我们证明，在高维、高噪声设置下，该算法会出现灾难性失效：以高概率，数据的所有划分几乎都是固定点。因此，Lloyd算法仅返回初始划分，即使底层聚类结构可被其他方法轻松恢复。相比之下，我们证明哈蒂根算法不会出现此病理现象。结果揭示了两种算法间的显著差异，并为实际中常在高维下遇到的k-means困难提供了理论解释。
原文摘要 · Abstract (English)
Lloyd's k-means algorithm is one of the most widely used clustering methods. We prove that in high-dimensional, high-noise settings, the algorithm exhibits catastrophic failure: with high probability, essentially every partition of the data is a fixed point. Consequently, Lloyd's algorithm simply returns its initial partition - even when the underlying clusters are trivially recoverable by other methods. In contrast, we prove that Hartigan's k-means algorithm does not exhibit this pathology. Our results show the stark difference between these algorithms and offer a theoretical explanation for the empirical difficulties often observed with k-means in high dimensions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。