用最优传输改进k均值聚类，实现高效均衡分组。
BalLOT: Balanced $k$-means clustering with optimal transport
- 引入最优传输优化交替最小化，提升聚类平衡性。
- 在随机球模型下证明可精确或部分恢复预设簇结构。
- 提出初始化方法，一步即可恢复预设簇，适合高维数据。
我们研究基本的平衡k均值聚类问题。为此，提出一种基于最优传输的交替最小化方法BalLOT，该方法能快速有效地解决此问题。通过多种数值实验验证其性能，并建立若干理论保证：首先，对一般数据，证明BalLOT在每一步均产生整数耦合；其次，在随机球模型下进行景观分析，为精确和部分恢复预设簇提供理论支持；最后，提出初始化方案，可实现一步恢复预设簇。
原文摘要 · Abstract (English)
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 a variety of numerical experiments before proving several theoretical guarantees. First, we 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. Finally, we propose initialization schemes that achieve one-step recovery of planted clusters.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。