Compressive K-means

Nicolas Keriven 1 Nicolas Tremblay 2 Yann Traonmilin 1 Rémi Gribonval 1
1 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
Inria Rennes – Bretagne Atlantique , IRISA_D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
2 GIPSA-CICS - CICS
GIPSA-DIS - Département Images et Signal
Abstract : The Lloyd-Max algorithm is a classical approach to perform K-means clustering. Unfortunately, its cost becomes prohibitive as the training dataset grows large. We propose a compressive version of K-means (CKM), that estimates cluster centers from a sketch, i.e. from a drastically compressed representation of the training dataset. We demonstrate empirically that CKM performs similarly to Lloyd-Max, for a sketch size proportional to the number of cen-troids times the ambient dimension, and independent of the size of the original dataset. Given the sketch, the computational complexity of CKM is also independent of the size of the dataset. Unlike Lloyd-Max which requires several replicates, we further demonstrate that CKM is almost insensitive to initialization. For a large dataset of 10^7 data points, we show that CKM can run two orders of magnitude faster than five replicates of Lloyd-Max, with similar clustering performance on artificial data. Finally, CKM achieves lower classification errors on handwritten digits classification.
Type de document :
Communication dans un congrès
IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Mar 2017, New Orleans, United States. Proceedings of the 42nd International Conference on Acoustics, Speech and Signal Processing (ICASSP)
Liste complète des métadonnées

https://hal.inria.fr/hal-01386077
Contributeur : Nicolas Keriven <>
Soumis le : vendredi 10 février 2017 - 10:57:14
Dernière modification le : lundi 11 septembre 2017 - 17:04:10

Fichiers

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01386077, version 4
  • ARXIV : 1610.08738

Citation

Nicolas Keriven, Nicolas Tremblay, Yann Traonmilin, Rémi Gribonval. Compressive K-means. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Mar 2017, New Orleans, United States. Proceedings of the 42nd International Conference on Acoustics, Speech and Signal Processing (ICASSP). 〈hal-01386077v4〉

Partager

Métriques

Consultations de
la notice

677

Téléchargements du document

116