A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++
A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++
复制标题
DOI：
--
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Dennis Wei
中科院分区：
文献类型：
--
作者：
Dennis Wei
本文研究了$k$ -means++聚类算法以及$k$ -means++所属的$D^\ell$类采样算法。结果表明，对于任何常数因子$\beta > 1$，通过$D^\ell$采样选择$\beta k$聚类中心，在期望和不需要数据集条件的情况下，产生具有$k$中心的最优聚类的常数因子近似值。该结果将先前已知的$\beta = 1$情况下的$O(\log k)$保证扩展到恒定因子双标准制度。它还改进了现有的仅以恒定概率成立的常量因子双标准结果。
This paper studies the $k$-means++ algorithm for clustering as well as the class of $D^\ell$ sampling algorithms to which $k$-means++ belongs. It is shown that for any constant factor $\beta > 1$, selecting $\beta k$ cluster centers by $D^\ell$ sampling yields a constant-factor approximation to the optimal clustering with $k$ centers, in expectation and without conditions on the dataset. This result extends the previously known $O(\log k)$ guarantee for the case $\beta = 1$ to the constant-factor bi-criteria regime. It also improves upon an existing constant-factor bi-criteria result that holds only with constant probability.