K-means, a simple and effective clustering algorithm, is

one of the most widely used algorithms in computer vision

community. Traditional k-means is an iterative algorithm—

in each iteration new cluster centers are computed and each

data point is re-assigned to its nearest center. The cluster

re-assignment step becomes prohibitively expensive when

the number of data points and cluster centers are large.

In this paper, we propose a novel approximate k-means

algorithm to greatly reduce the computational complexity

in the assignment step. Our approach is motivated by the

observation that most active points changing their cluster

assignments at each iteration are located on or near cluster

boundaries. The idea is to efficiently identify those active

points by pre-assembling the data into groups of neighboring

points using multiple random spatial partition trees, and

to use the neighborhood information to construct a closure

for each cluster, in such a way that only a small number of

cluster candidates need to be considered when assigning a

data point to its nearest cluster. Using complexity analysis,

real data clustering, and applications to image retrieval, we

show that our approach out-performs state-of-the-art approximate

k-means algorithms in terms of clustering quality

and efficiency.

PDF file

In  CVPR 2012

Publisher  IEEE Computer Society

Details