改进K均值算法，确保收敛到局部最优解。
Modified K-means Algorithm with Local Optimality Guarantees
- 基于Bregman散度提出新更新规则
- 实验显示原算法常不收敛到局部最优
- 保持原复杂度，适合实际应用
K-means是机器学习中研究最广泛的聚类算法之一。尽管已有大量工作关注其全局最优性，但对其局部最优性的严格分析仍不足。本文首先给出K-means收敛至局部最优解的条件，并据此提出简单修改，在连续和离散意义上均保证局部最优性，且计算复杂度与原始算法相同。我们采用广义Bregman散度作为相似性度量，扩展了常用的平方欧氏距离。数值实验表明，原始K-means在实践中并不总能获得局部最优解，而所提方法可显著降低聚类损失，获得更优的局部解。代码已公开于https://github.com/lmingyi/LO-K-means。
原文摘要 · Abstract (English)
The K-means algorithm is one of the most widely studied clustering algorithms in machine learning. While extensive research has focused on its ability to achieve a globally optimal solution, there still lacks a rigorous analysis of its local optimality guarantees. In this paper, we first present conditions under which the K-means algorithm converges to a locally optimal solution. Based on this, we propose simple modifications to the K-means algorithm which ensure local optimality in both the continuous and discrete sense, with the same computational complexity as the original K-means algorithm. As the dissimilarity measure, we consider a general Bregman divergence, which is an extension of the squared Euclidean distance often used in the K-means algorithm. Numerical experiments confirm that the K-means algorithm does not always find a locally optimal solution in practice, while our proposed methods provide improved locally optimal solutions with reduced clustering loss. Our code is available at https://github.com/lmingyi/LO-K-means.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。