Physical Sciences and Mathematics Commons^™

An Efficient K-Means Clustering Algorithm, Khaled Alsabti, Sanjay Ranka, Vineet Singh

Electrical Engineering and Computer Science - All Scholarship

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 …