Yinyang K-Means: A Drop-In Replacement of the Classic K-Means with Consistent Speedup

Abstract

This paper presents Yinyang K-means, a new algorithm for K-means clustering. By cluster-ing the centers in the initial stage, and lever-aging efficiently maintained lower and upper bounds between a point and centers, it more effectively avoids unnecessary distance calcula-tions than prior algorithms. It significantly out-performs prior K-means algorithms consistently across all experimented data sets, cluster num-bers, and machine configurations. The consis-tent, superior performance—plus its simplicity, user-control of overheads, and guarantee in pro-ducing the same clustering results as the stan-dard K-means does—makes Yinyang K-means a drop-in replacement of the classic K-means with an order of magnitude higher performance. 1.