An efficient k-means clustering algorithm
Khaled A. Alsabti, Sanjay Ranka, Vineet Kumar Singh · Syracuse University Libraries (Syracuse University) · 1997
In this paper, we present a novel algorithm for performing k-means clustering. It organizes all the patterns in a k-d tree structure such that one can find all the patterns which are closest to a given prototype efficiently. The main intuition behind our approach is as follows. All the prototypes are potential candidates for the closest prototype at the root level. However, for the children of the root node, we may be able to prune the candidate set by using simple geometrical constraints. This approach can be applied recursively until the size of the candidate set is one for each node. Our experimental results demonstrate that our scheme can improve the computational speed of the direct k-means algorithm by an order to two orders of magnitude in the total number of distance calculations and the overall time of computation. 1. Introduction Clustering is the process of partitioning or grouping a given set of patterns into disjoint clusters. This is done such that patterns in the same c...