摘要
针对Amit Kumar提出的求解k-means算法的1+ε近似求解随机算法,提出了一个改进措施用来提高每次取样的成功概率。当固定k和ε值时该算法为线性的。通过多次运行该算法能以较高的概率求出k-means算法的1+ε近似值。
This paper introduces an improvement algorithm given by Amit Kumar for the problem of k - means. This improvement algorithm can get a higher probability for success in the process of sampling. This algorithm running time can be regarded as linear when fixed k and ε. After running this algorithm several times,we can get a higher probability to the ratio of （1 ＋ε）- approximation for the k - means problem.
出处
《现代电子技术》
2006年第19期154-156,共3页
Modern Electronics Technique
