Effect of Data Parameters and Seeding on k-Means and k-Medoids

k-means and k-medoids are arguably the two most popular clustering methods. This paper reports an empirical study of the relative (de)merits of these two methods. We compare their performances under varying data conditions. We also assess the impact of replacing random selection of initial cluster centers, with a systematic approach. The technique employed in our study, for initial centroid selection, is the state-of-art D
²
-weighing technique used in k-means ++, a variant of k-means. We use an extensive set of well-known and recommended benchmark datasets. These datasets allow for the study of performance under varying data size; varying cluster count, imbalance and overlap; and varying dimensionality. We establish that although k-means is much less accurate than k-medoids (which is grossly inefficient and less scalable), the accuracy gap is reduced significantly by seeding k-means. On the other hand, seeding does not improve k-medoids' accuracy but significantly worsens its efficiency (typically doubles its running time). Increased dimensionality tends to improve the accuracy of both algorithms, while increased overlap tends to worsen them.