Skip to Main content Skip to Navigation
Journal articles

QuicK-means: Acceleration of K-means by learning a fast transform

Abstract : K-means -- and the celebrated Lloyd algorithm -- is more than the clustering method it was originally designed to be. It has indeed proven pivotal to help increase the speed of many machine learning and data analysis techniques such as indexing, nearest-neighbor search and prediction, data compression, Radial Basis Function networks; its beneficial use has been shown to carry over to the acceleration of kernel machines (when using the Nyström method). Here, we propose a fast extension of K-means, dubbed QuicK-means, that rests on the idea of expressing the matrix of the $K$ centroids as a product of sparse matrices, a feat made possible by recent results devoted to find approximations of matrices as a product of sparse factors. Using such a decomposition squashes the complexity of the matrix-vector product between the factorized $K \times D$ centroid matrix $\mathbf{U}$ and any vector from $\mathcal{O}(K D)$ to $\mathcal{O}(A \log A+B)$, with $A=\min (K, D)$ and $B=\max (K, D)$, where $D$ is the dimension of the training data. This drastic computational saving has a direct impact in the assignment process of a point to a cluster, meaning that it is not only tangible at prediction time, but also at training time, provided the factorization procedure is performed during Lloyd's algorithm. We precisely show that resorting to a factorization step at each iteration does not impair the convergence of the optimization scheme and that, depending on the context, it may entail a reduction of the training time. Finally, we provide discussions and numerical simulations that show the versatility of our computationally-efficient QuicK-means algorithm.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-02174845
Contributor : Luc Giffon Connect in order to contact the contributor
Submitted on : Wednesday, January 13, 2021 - 12:37:41 PM
Last modification on : Tuesday, October 19, 2021 - 10:50:57 PM

File

main-stripped.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Luc Giffon, Valentin Emiya, Hachem Kadri, Liva Ralaivola. QuicK-means: Acceleration of K-means by learning a fast transform. Machine Learning, Springer Verlag, 2021, Machine Learning, 110, pp.881-905. ⟨10.1007/s10994-021-05965-0⟩. ⟨hal-02174845v4⟩

Share

Metrics

Record views

223

Files downloads

158