The analysis of a simple k-means clustering algorithm

摘要: Abstract : K-means clustering is a very popular technique which used in numerous applications. Given set of n data points R(exp d) and an integer k, the problem to determine k d), called centers, so as minimize mean squared distance from each point its nearest center. A heuristic for k-means Lloyd's algorithm. In this paper, we present simple efficient implementation algorithm, call filtering This algorithm easy implement. It differs most other approaches that it precomputes kd-tree structure rather than center points. We establish practical efficiency two ways. First, data-sensitive analysis algorithm's running time. Second, have implemented performed number empirical studies, both on synthetically generated real applications color quantization, compression, segmentation.