A fast kk-means clustering algorithm using cluster center displacement

In this paper, we present a fast kk-means clustering algorithm (FKMCUCD) using the displacements of cluster centers to reject unlikely candidates for a data point. The computing time of our proposed algorithm increases linearly with the data dimension dd, whereas the computational complexity of major available kd-tree based algorithms increases exponentially with the value of dd. Theoretical analysis shows that our method can reduce the computational complexity of full search by a factor of SF and SF   is independent of vector dimension. The experimental results show that compared to full search, our proposed method can reduce computational complexity by a factor of 1.37–4.39 using the data set from six real images. Compared with the filtering algorithm, which is among the available best algorithms of kk-means clustering, our algorithm can effectively reduce the computing time. It is noted that our proposed algorithm can generate the same clusters as that produced by hard kk-means clustering. The superiority of our method is more remarkable when a larger data set with higher dimension is used.