Accelerating exactk-means algorithms with geometric reasoning
- 1 August 1999
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 277-281
- https://doi.org/10.1145/312129.312248
Abstract
We present new algorithms for the k-means clustering problem.They use the kd-tree data structure to reduce the large number ofnearest-neighbor queries issued by the traditional algorithm. Sufficientstatistics are stored in the nodes of the kd-tree. Then, an analysis ofthe geometry of the current cluster centers results in great reductionof the work needed to update the centers. Our algorithms behaveexactly as the traditional k-means algorithm. Proofs of correctnessare included. The...Keywords
This publication has 4 references indexed in Scilit:
- BIRCHPublished by Association for Computing Machinery (ACM) ,1996
- Neural Networks for Pattern RecognitionPublished by Oxford University Press (OUP) ,1995
- Vector Quantization and Signal CompressionPublished by Springer Nature ,1992
- Multidimensional divide-and-conquerCommunications of the ACM, 1980