arXiv：cs.LG（机器学习，全量分类）· Wenyan Luo, Dustin G. Mixon·· 15 小时前AI 评分30
BalLOT：基于最优传输的平衡 k-means 聚类
BalLOT: Balanced $k$-means clustering with optimal transport
AI 导读
BalLOT 是一种结合最优传输的交替最小化方法，用于求解平衡 k-means 聚类问题。理论方面，论文证明该方法在通用数据上每步产生整数耦合，并在随机球模型下对精确与部分恢复植入簇给出保证，还提出可一步恢复植入簇的初始化方案。数值实验验证了上述理论结果。
正文
Abstract:We consider the fundamental problem of balanced $k$-means clustering. In particular, we introduce an optimal transport approach to alternating minimization called BalLOT, and we show that it delivers a fast and effective solution to this problem. We establish this with several theoretical guarantees and a variety of numerical experiments. On the theory front, we first prove that for generic data, BalLOT produces integral couplings at each step. Next, we perform a landscape analysis to provide theoretical guarantees for both exact and partial recoveries of planted clusters under the stochastic ball model. We also propose initialization schemes that achieve one-step recovery of planted clusters. To conclude, we present numerical experiments that corroborate our theoretical results.
| Comments: | 27 pages, 9 figures |
| Subjects: | Machine Learning (stat.ML); Data Structures and Algorithms (cs.DS); Information Theory (cs.IT); Machine Learning (cs.LG); Optimization and Control (math.OC) |
| Cite as: | arXiv:2512.05926 [stat.ML] |
| (or arXiv:2512.05926v2 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2512.05926 arXiv-issued DOI via DataCite |
Submission history
From: Wenyan Luo [view email]
[v1]
Fri, 5 Dec 2025 18:04:35 UTC (304 KB)
[v2]
Thu, 1 Oct 2026 03:03:39 UTC (350 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org