Spatial Transformer K-Means

The K-means algorithm is one of the most employed centroid-based clustering algorithms. Unfortunately, it often requires intricate data embeddings for good performance, which comes at the cost of reduced theoretical guarantees and loss of interpretability. Instead, we propose to use the intrinsic data space and augment K-means with a similarity measure invariant to non-rigid transformations. This enables (i) the reduction of intrinsic nuisances associated with the data, making the clustering task simpler and improving performance, leading to state-of-the-art results, (ii) clustering in the input space of the data, providing a fully interpretable clustering algorithm, and (iii) the benefit of convergence guarantees.