Clustering has been one of the main building blocks in the fields of machine learning and computer vision. Given a pair-wise distance measure, it is challenging to find a proper way to identify a subset of representative exemplars and its associated cluster structures. Recent trend on big data analysis poses a more demanding requirement on new clustering algorithm to be both scalable and accurate. A recent advance in graph-based clustering extends its ability to millions of data points by massive utility of engineering endeavor and parallel optimization. However, most other existing clustering algorithms, though promising in theory, are limited in the scalability issue.
In this paper, a novel clustering method is proposed that is both accurate and scalable. Based on a simple criteria, ”key” items that are representative of the whole data set are iteratively selected and thus form associated cluster structures. Taking input of pairwise distance measure between data instances, the proposed method searches centers of clusters by identifying data items far away from selected keys, but representative of unselected data items. Inspired by hierarchical clustering, small clusters are iteratively merged until a desired number of clusters are obtained. To solve the scalability problem, a novel tracking table technique is designed to reduce the time complexity which is capable of clustering millions of data points within a few minutes.
To assess the performance of the proposed method, several experiments are conducted. The first experiment tests the ability of our algorithm on different manifold structures and various number of clusters. It is observed that our clustering algorithm outperforms existing alternatives in capturing different shapes of data distributions. In the second experiment, the scalability of our algorithm to large scale data points is assessed by clustering up to one million data points with dimensions of up to 100. It is shown that, even with one million data points, the proposed method only takes a few minutes to perform clustering. The third experiment is conducted on the ORL database, which consists of 400 face images of 40 individuals. The proposed clustering method outperforms the compared alternatives in this experiment as well. In the final experiment, shape clustering is performed on the MPEG-7 dataset, which contains 1400 silhouette images from 70 classes, 20 different shapes for each class. The goal here is to cluster the data items (here the binary shapes) into 70 clusters, so that each cluster only includes shapes that belong to one class. The proposed method outperforms other alternative clustering algorithms on this dataset as well.
Extensive empirical experiments demonstrate the superiority of the proposed method over existing alternatives, in terms of both effectiveness and efficiency. Furthermore, our algorithm is capable of large-scale data clustering where millions of data points can be clustered in a few seconds.