Clustering Large Datasets by MergingK-Means Solutions

Existing clustering methods range from simple but very restrictive to complex but more flexible. TheK-means algorithm is one of the most popular clustering procedures due to its computational speed and intuitive construction. Unfortunately, the application ofK-means in its traditional form based on Euclidean distances is limited to cases with spherical clusters of approximately the same volume and spread of points. Recent developments in the area of merging mixture components for clustering show good promise. We propose a general framework for hierarchical merging based on pairwise overlap between components which can be readily applied in the context of theK-means algorithm to produce meaningful clusters. Such an approach preserves the main advantage of theK-means algorithm-its speed. The developed ideas are illustrated on examples, studied through simulations, and applied to the problem of digit recognition.