Pivot-based k-means Algorithm for Numerous-class Data Sets
Takashi Hattori, Kazuo Aoyama, Kazumi Saito, Tetsuo Ikeda, Eri Kobayashi · 2016
This paper presents an accelerated k-means clustering algorithm suitable for a large-scale and numerous-class data set. The proposed iterative algorithm avoids unnecessary exact distance calculations, especially in the early and the last stage in its convergence process, and retains the same result as the standard algorithm. This is efficiently performed by two distinct components. One uses the lower bounds on exact distances between objects and centroids for the acceleration in the early stage. The lower bound is calculated by the triangle inequality with newly introduced fixed points called pivots. The other component for the last stage skips the distance calculation between an invariant centroid and an object satisfying the following condition. The cluster to which the object is assigned remains unchanged, i.e., its centroid is also invariant. For much further speed-up, we can incorporate an existing algorithm into the proposed algorithm as an extension, which often performs a complementary role in the middle stage. The experimental results we obtained on large-scale and high-dimensional image data sets demonstrate that given a large k value, the proposed algorithm outperforms existing algorithms in terms of both the reduction rate of distance calculations and elapsed time.