Recursive nearest agglomeration (ReNA): fast clustering for approximation of structured signals

Abstract : In this work, we revisit fast dimension reduction approaches, as with random projections and random sampling. Our goal is to summarize the data to decrease computational costs and memory footprint of subsequent analysis. Such dimension reduction can be very efficient when the signals of interest have a strong structure, such as with images. We focus on this setting and investigate feature clustering schemes for data reductions that capture this structure. An impediment to fast dimension reduction is that good clustering comes with large algorithmic costs. We address it by contributing a linear-time agglomerative clustering scheme, Recursive Nearest Agglomeration (ReNA). Unlike existing fast agglomerative schemes, it avoids the creation of giant clusters. We empirically validate that it approximates the data as well as traditional variance-minimizing clustering schemes that have a quadratic complexity. In addition, we analyze signal approximation with feature clustering and show that it can remove noise, improving subsequent analysis steps. As a consequence, data reduction by clustering features with ReNA yields very fast and accurate models, enabling to process large datasets on budget. Our theoretical analysis is backed by extensive experiments on publicly-available data that illustrate the computation efficiency and the denoising properties of the resulting dimension reduction scheme.
Type de document :
Article dans une revue
IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, In press, XX, 〈10.1109/TPAMI.2018.2815524〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01366651
Contributeur : Andres Hoyos Idrobo <>
Soumis le : vendredi 16 mars 2018 - 20:40:41
Dernière modification le : jeudi 29 mars 2018 - 10:32:02

Fichiers

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

Identifiants

Citation

Andrés Hoyos-Idrobo, Gaël Varoquaux, Jonas Kahn, Bertrand Thirion. Recursive nearest agglomeration (ReNA): fast clustering for approximation of structured signals. IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, In press, XX, 〈10.1109/TPAMI.2018.2815524〉. 〈hal-01366651v2〉

Partager

Métriques

Consultations de la notice

181

Téléchargements de fichiers

46