科研之友
微信
新浪微博
Facebook
分享链接
摘要
k-means++ is a seeding technique for the k-means method with an expected approximation ratio of O(log k), where k denotes the number of clusters. Examples are known on which the expected approximation ratio of k-means++ is Omega(log k), showing that the upper bound is asymptotically tight. However, it remained open whether k-means++ yields a constant approximation with probability 1/poly(k) or even with constant probability. We settle this question and present instances on which k-means++ achieves an approximation ratio no better than (2/3 - epsilon) . log k with probability exponentially close to 1.
- 出版日期2013-9-23
