K-bMOM: a robust Lloyd-type clustering algorithm based on bootstrap Median-of-Means

We propose a new clustering algorithm that is robust to the presence of\noutliers in the dataset. We perform Lloyd-type iterations with robust estimates\nof the centroids. More precisely, we build on the idea of median-of-means\nstatistics to estimate the centroids, but allow for replacement while\nconstructing the blocks. We call this methodology the bootstrap median-of-means\n(bMOM) and prove that if enough blocks are generated through the bootstrap\nsampling, then it has a better breakdown point for mean estimation than the\nclassical median-of-means (MOM), where the blocks form a partition of the\ndataset. From a clustering perspective, bMOM enables to take many blocks of a\ndesired size, thus avoiding possible disappearance of clusters in some blocks,\na pitfall that can occur for the partition-based generation of blocks of the\nclassical median-of-means. Experiments on simulated datasets show that the\nproposed approach, called K-bMOM, performs better than existing robust K-means\nbased methods. Guidelines are provided for tuning the hyper-parameters K-bMOM\nin practice. It is also recommended to the practitionner to use such a robust\napproach to initialize their clustering algorithm. Finally, considering a\nsimplified and theoretical version of our estimator, we prove its robustness to\nadversarial contamination by deriving robust rates of convergence for the\nK-means distorsion. To our knowledge, it is the first result of this kind for\nthe K-means distorsion.\n