Arnold.L. Rosenberg
Journal of the ACM
In k-means clustering, we are given a set of n data points in d-dimensional space R d and an integer k and the problem is to determine a set of k points in R d, called centers, so as to minimize the mean squared distance from each data point to its nearest center. A popular heuristic for k-means clustering is Lloyd's algorithm. In this paper, we present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm. This algorithm is easy to implement, requiring a kd-tree as the only major data structure. We establish the practical efficiency of the filtering algorithm in two ways. First, we present a data-sensitive analysis of the algorithm's running time, which allows that the algorithm runs faster as the separation between clusters increases. Second, we present a number of empirical studies both on synthetically generated data and on real data sets from applications in color quantization, data compression, and image segmentation.
Arnold.L. Rosenberg
Journal of the ACM
Ben Fei, Jinbai Liu
IEEE Transactions on Neural Networks
Yehuda Naveli, Michal Rimon, et al.
AAAI/IAAI 2006
Susan L. Spraragen
International Conference on Design and Emotion 2010