Title :
A (1+µ)-approximate algorithm for k-means problem based on balancing constraint
Author :
Sheng, Zhang ; Shouqiang, Wang
Author_Institution :
Dept. of Inf. Eng., Shandong Jiaotong Univerisity, Jinan, China
Abstract :
k-means clustering has been widely applied in the field of Machine Learning and Pattern Recognition. This paper discussed the randomized algorithm of its sub problem which requires that each divided subset size has to be at least some given value. First a sample set was drawn at random from the given point, which contains some number of points of each optimal subset with high probability. Based on the sample set, this paper presented a randomized (1+μ)-approximate algorithm for k-means clustering. At last, the running time and the successful probability of this randomized algorithm were analysed in this paper.
Keywords :
learning (artificial intelligence); pattern clustering; probability; (1+μ)-approximate algorithm; balancing constraint; k-means clustering; k-means problem; machine learning; pattern recognition; randomized algorithm; Approximation algorithms; Clustering algorithms; Least squares approximation; Machine learning; Presses; Silicon; Centroid; Clustering; k-means;
Conference_Titel :
Intelligent Control and Automation (WCICA), 2010 8th World Congress on
Conference_Location :
Jinan
Print_ISBN :
978-1-4244-6712-9
DOI :
10.1109/WCICA.2010.5553912
