Clustering parcimonieux dans des sous-espaces : algorithme, théorie et applications

Dans de nombreux problèmes du monde réel, nous sommes confrontés à des ensembles de données de grande dimension, tels que des images, des vidéos, des textes et des documents web, des données d'arrays d'ADN (DNA microarray data) et bien d'autres. Souvent, ces données de grande dimension se situent près de structures de faible dimension correspondant à plusieurs classes ou catégories auxquelles appartiennent les données. Dans cet article, nous proposons et étudions un algorithme appelé Clustering de Sous-espaces Épars (Sparse Subspace Clustering, SSC), visant à regrouper des points de données qui se trouvent dans une union de sous-espaces de faible dimension. L'idée clé est que, parmi les nombreuses représentations possibles d'un point de données en termes d'autres points, une représentation éparse correspond à la sélection de quelques points provenant du même sous-espace. Cela motive la résolution d'un programme d'optimisation éparse dont la solution est utilisée dans un cadre de clustering spectral pour inférer le regroupement des données en sous-espaces. Étant donné que la résolution du programme d'optimisation éparse est généralement NP-difficile, nous considérons une relaxation convexe et montrons que, sous certaines conditions appropriées sur l'arrangement des sous-espaces et la distribution des données, le programme de minimisation proposé réussit à récupérer les représentations éparse souhaitées. L'algorithme proposé peut être résolu efficacement et peut gérer les points de données proches des intersections des sous-espaces. Un autre avantage majeur de l'algorithme proposé par rapport à l'état actuel de l'art est qu'il peut traiter directement les nuisances des données, telles que le bruit, les entrées aberrantes éparse et les entrées manquantes, en intégrant le modèle des données dans le programme d'optimisation éparse. Nous démontrons l'efficacité de l'algorithme proposé par le biais d'expériences sur des données synthétiques ainsi que sur deux problèmes réels : la segmentation de mouvement et le clustering facial.