随机选中心数让k-means++在最坏情况下仍保持常数级近似比
Randomizing the Number of Centers in k-means++
- 让中心数在区间内随机选择，缓解固定k的最坏情况
- 证明在预算平滑设定下，算法有常数概率获得常数近似比
- 对实际应用中中心数不确定的场景具有鲁棒性
k-means++ 是 k-means 聚类的标准种子选择方法，但当中心数 $k$ 固定时，其最坏情况下的期望近似比为 $Θ(\log k)$。本文考虑一种新设定：对手先固定数据集和某个 $K$，然后从 $\{K,\ldots,2K-1\}$ 中均匀随机选择中心数 $k$。我们证明，在此预算平滑（budget-smoothed）设定下，k-means++ 以常数概率达到 $O(1)$ 近似比。
原文摘要 · Abstract (English)
The $k$-means++ algorithm is a standard and widely used seeding method for $k$-means clustering, but for a fixed number $k$ of centers its worst-case expected approximation ratio is $Θ(\log k)$. We consider the same algorithm when an adversary first fixes the dataset and some $K$; the number of centers $k$ is then chosen uniformly from $\{K,\ldots,2K-1\}$. We prove that $k$-means++ is an $O(1)$-approximation with constant probability in this budget-smoothed setup.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。