The seeding algorithm for k-means problem with penalties
The seeding algorithm for k-means problem with penalties
复制标题
DOI：
10.1007/s10878-019-00450-w
复制
发表时间：
2019-09
影响因子：
1
通讯作者：
Min Li;Dachuan Xu;Jun Yue;Dongmei Zhang;Peng Zhang
中科院分区：
文献类型：
--
作者：
Min Li;Dachuan Xu;Jun Yue;Dongmei Zhang;Peng Zhang
K-Means问题是机器学习和计算几何中的经典NP-Hard问题。它的目标是根据最小平方距离将给定的集合划分为k个簇。带有惩罚的k-Means问题是k-Means问题的一种推广，它允许某些点不需要聚类而不需要支付一定的惩罚。本文利用种子算法研究了带惩罚的k-均值问题。我们认为，精度只涉及最大罚值与最小罚值之比。当惩罚是一致的时，k-均值问题的近似因子减小到相同的。此外，我们的结果将k-Means问题的k-Means++推广到惩罚形式。数值实验表明，我们的播种算法比不使用播种的算法更有效。
The k-means problem is a classic NP-hard problem in machine learning and computational geometry. And its goal is to separate the given set into k clusters according to the minimal squared distance. The k-means problem with penalties, as one generalization of k-means problem, allows that some point need not be clustered instead of being paid some penalty. In this paper, we study the k-means problem with penalties by using the seeding algorithm. We propose that the accuracy only involves the ratio of the maximal penalty value to the minimal one. When the penalty is uniform, the approximation factor reduces to the same one for the k-means problem. Moreover, our result generalizes the k-means++ for k-means problem to the penalty version. Numerical experiments show that our seeding algorithm is more effective than the one without using seeding.