K-means-sharp: Modified centroid update for outlier-robust k-means clustering
Peter Olukanmi, Bhekisipho Twala · 2017
The classical k-means clustering algorithm is easily misled by outliers. To address this problem, we modify its centroid update step so that outliers are avoided when new centroids are computed. Our modified algorithm, named k-means-sharp (k-means#), detects outliers automatically by means of a global threshold derived from the distribution of point-to-centroid distances. The approach requires neither user intervention nor prior knowledge of the number of outliers. Since it preserves k-means' structure, k-means# inherits the former's ease of implementation and if desired, it can benefit from other existing k-means improvements. On 10 datasets - 2 standard datasets and 4 outlier-contaminated versions of each - k-means# yields lower within-cluster mean squared error than k-means. It detects outliers with high accuracy (90.4% average and 99.2% maximum) and precision (86.8% average and 100% maximum), and moderate recall (52.4% average and 90.0% maximum) and F1-score (61.1% average and 92.9% maximum).