Systematically and efficiently improving $k$-means initialization by pairwise-nearest-neighbor smoothing
This work addresses the challenge of efficient and effective initialization for k-means clustering, which is incremental as it builds on existing seeding methods to enhance performance.
The paper tackles the problem of improving k-means clustering initialization by introducing PNN-smoothing, a meta-method that splits data into subsets, clusters them individually, and merges results using pairwise-nearest-neighbor, leading to systematically better costs and outperforming greedy k-means++ in effectiveness and speed.
We present a meta-method for initializing (seeding) the $k$-means clustering algorithm called PNN-smoothing. It consists in splitting a given dataset into $J$ random subsets, clustering each of them individually, and merging the resulting clusterings with the pairwise-nearest-neighbor (PNN) method. It is a meta-method in the sense that when clustering the individual subsets any seeding algorithm can be used. If the computational complexity of that seeding algorithm is linear in the size of the data $N$ and the number of clusters $k$, PNN-smoothing is also almost linear with an appropriate choice of $J$, and quite competitive in practice. We show empirically, using several existing seeding methods and testing on several synthetic and real datasets, that this procedure results in systematically better costs. In particular, our method of enhancing $k$-means++ seeding proves superior in both effectiveness and speed compared to the popular "greedy" $k$-means++ variant. Our implementation is publicly available at https://github.com/carlobaldassi/KMeansPNNSmoothing.jl.