Sensitivity analysis of an outlier-aware k-means clustering algorithm
Peter Olukanmi, Bhekisipho Twala · 2017
K-means-sharp (k-means#), a recently introduced outlier-robust alternative to classical k-means, excludes points further than a threshold T from their cluster centroids, when computing new centroids. T is determined online as a constant multiple q of the estimated population standard deviation of the point-to-centroid distances. The approach preserves k-means' structure, and requires no preprocessing, user intervention or prior knowledge of the outlier rate. In pursuit of insights for optimizing the algorithm, this paper investigates the algorithm's sensitivity to variation in q. We study q values in the range 2-6, which corresponds to 95% - nearly 100% confidence in rejecting a point as an outlier. On 10 datasets tested, k-means# yields better within-cluster mean square error, for all values of q, thus establishing its effectiveness in producing good partitions. More interestingly, as q is varied, trade-offs are observed between clustering quality, outlier-detection accuracy, precision, recall and F1-score.