Yinyang K-Means: A Drop-In Replacement of the Classic K-Means with Consistent Speedup - Ding, Yufei; Zhao, Yue; Shen, Xipeng; Musuvathi, Madanlal; Mytkowicz, Todd; Musuvathi, Madan (Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, 2015)
This paper presents Yinyang K-means, a new algorithm for K-means clustering. By clustering the centers in the initial stage, and leveraging efﬁciently maintained lower and upper bounds between a point and centers, it more effectively avoids unnecessary distance calculations than prior algorithms. It signiﬁcantly outperforms prior K-means algorithms consistently across all experimented data sets, cluster numbers, and machine conﬁgurations. The consistent, superior performance—plus its simplicity, user-control of overheads, and guarantee in producing the same clustering results as the standard K-means—makes Yinyang K-means a drop-in replacement of the classic K-means with an order of magnitude higher performance.