Clustering

Le clustering, également connu sous le nom d'analyse de groupement, est une technique d'analyse de données qui partitionne un ensemble d'objets en groupes, ou clusters, de sorte que les objets au sein d'un même cluster soient plus similaires entre eux qu'aux objets d'autres clusters, selon une mesure de similarité ou de distance spécifique définie par l'analyste. C'est une tâche principale de l'analyse exploratoire de données et une technique courante pour l'analyse statistique de données, utilisée dans des domaines tels que la reconnaissance de formes, l'analyse d'images, la recherche d'informations, la bioinformatique, la compression de données, l'infographie et apprentissage automatique. En tant que méthode d'apprentissage non supervisé, le clustering ne repose pas sur des données étiquetées ; il découvre plutôt des structures et des regroupements inhérents aux données sans connaissance préalable des étiquettes de classe.

Le terme « clustering » englobe une famille d'algorithmes et de tâches plutôt qu'un algorithme spécifique unique. Différents algorithmes varient considérablement dans leur compréhension de ce qui constitue un cluster et dans la manière d'identifier efficacement les clusters. Les notions populaires de clusters incluent des groupes avec de petites distances entre les membres, des zones denses de l'espace de données, des intervalles ou des distributions statistiques particulières. Par conséquent, le clustering peut être formulé comme un problème d'optimisation multi-objectifs, et l'algorithme et les paramètres appropriés (tels que la fonction de distance, le seuil de densité ou le nombre de clusters attendus) dépendent de l'ensemble de données individuel et de l'utilisation prévue des résultats. L'analyse de groupement n'est pas une tâche automatique mais un processus itératif de découverte de connaissances ou d'optimisation interactive multi-objectifs, nécessitant souvent des essais et erreurs pour ajuster le prétraitement des données et les paramètres du modèle jusqu'à ce que le résultat atteigne les propriétés souhaitées.

Outre le terme clustering, plusieurs termes similaires existent, notamment la classification automatique, la taxonomie numérique, la botryologie (du grec βότρυς « raisin »), l'analyse typologique et la détection de communautés. Les différences subtiles résident souvent dans l'utilisation des résultats : en exploration de données, les groupes résultants sont l'objet d'intérêt, tandis qu'en classification automatique, le pouvoir discriminant résultant est l'objet d'intérêt.

Histoire

L'analyse de groupement est originaire de l'anthropologie avec les travaux de Driver et Kroeber en 1932. Elle a été introduite en psychologie par Joseph Zubin en 1938 et Robert Tryon en 1939, et célèbrement utilisée par Raymond Cattell à partir de 1943 pour la classification des traits de personnalité en psychologie de la personnalité. Depuis lors, le clustering a évolué pour devenir un outil fondamental dans de nombreuses disciplines scientifiques, avec des centaines d'algorithmes publiés développés au fil des décennies.

Modèles de clusters

La notion de « cluster » ne peut pas être définie précisément, ce qui est une raison clé de la diversité des algorithmes de clustering. Il existe un dénominateur commun : un groupe d'objets de données. Cependant, différents chercheurs utilisent différents modèles de clusters, et chaque modèle peut être implémenté par divers algorithmes. Comprendre ces modèles de clusters est essentiel pour comprendre les différences entre les algorithmes. Les modèles de clusters typiques incluent :

• Modèles de connectivité : Le clustering hiérarchique construit des modèles basés sur la connectivité de distance, où les clusters sont formés en reliant les objets en fonction de la proximité.
• Modèles de centroïdes : L'algorithme k-means représente chaque cluster par un vecteur moyen unique, ou centroïde, et assigne les objets au centroïde le plus proche.
• Modèles de distribution : Les clusters sont modélisés à l'aide de distributions statistiques, telles que les distributions normales multivariées utilisées par l'algorithme d'espérance-maximisation (EM).
• Modèles de densité : Des algorithmes comme DBSCAN, OPTICS et HDBSCAN définissent les clusters comme des régions denses connectées dans l'espace de données, séparées par des zones clairsemées.
• Modèles de sous-espaces : Dans le biclustering (également connu sous le nom de co-clustering ou clustering à deux modes), les clusters sont modélisés avec à la fois les membres du cluster et les attributs pertinents, permettant aux clusters d'exister dans différents sous-espaces des données.
• Modèles de groupes : Certains algorithmes ne fournissent pas un modèle raffiné pour leurs résultats et fournissent simplement l'information de regroupement.
• Modèles basés sur les graphes : Une clique, un sous-ensemble de nœuds dans un graphe où chaque paire de nœuds est connectée par une arête, peut être considérée comme une forme prototypique de cluster. Des relaxations de l'exigence de connectivité complète, connues sous le nom de quasi-cliques, sont utilisées dans des algorithmes comme l'algorithme de clustering HCS.
• Modèles de graphes signés : Dans les graphes signés, chaque chemin a un signe provenant du produit des signes sur les arêtes. Sous les hypothèses de la théorie de l'équilibre, les arêtes peuvent changer de signe, résultant en un graphe bifurqué. L'axiome plus faible de « capacité de regroupement » (aucun cycle n'a exactement une arête négative) donne des résultats avec plus de deux clusters ou sous-graphes avec uniquement des arêtes positives.
• Modèles neuronaux : Le réseau neuronal non supervisé le plus connu est la carte auto-organisatrice, et ces modèles peuvent généralement être caractérisés comme similaires à un ou plusieurs des modèles ci-dessus, y compris les modèles de sous-espaces lorsque les réseaux neuronaux implémentent des formes d'analyse en composantes principales ou d'analyse en composantes indépendantes.

Types de clustering

Un « clustering » est essentiellement un ensemble de clusters, contenant généralement tous les objets de l'ensemble de données. Il peut également spécifier la relation des clusters entre eux, comme une hiérarchie de clusters imbriqués les uns dans les autres. Les clusterings peuvent être grossièrement distingués comme :

• Clustering dur : Chaque objet appartient à un cluster ou non.
• Clustering flou (également clustering flou) : Chaque objet appartient à chaque cluster à un certain degré, comme une probabilité d'appartenance.

Des distinctions plus fines incluent :

• Clustering de partitionnement strict : Chaque objet appartient exactement à un cluster.
• Clustering de partitionnement strict avec valeurs aberrantes : Les objets peuvent également n'appartenir à aucun cluster, auquel cas ils sont considérés comme des valeurs aberrantes.
• Clustering chevauchant (également clustering alternatif, clustering multi-vues) : Les objets peuvent appartenir à plus d'un cluster, impliquant généralement des clusters durs.
• Clustering hiérarchique : Les objets qui appartiennent à un cluster enfant appartiennent également au cluster parent, créant une structure arborescente.
• Clustering de sous-espaces : Bien qu'il s'agisse d'un clustering chevauchant, dans un sous-espace uniquement défini, les clusters ne sont pas censés se chevaucher.

Algorithmes

Les algorithmes de clustering peuvent être catégorisés en fonction de leur modèle de cluster. Il existe probablement plus de 100 algorithmes de clustering publiés, et tous ne fournissent pas de modèles pour leurs clusters, ce qui rend la catégorisation difficile. Il n'existe pas d'algorithme de clustering « correct » objectivement ; comme indiqué, « le clustering est dans l'œil de celui qui regarde ». En fait, une approche axiomatique démontre qu'il est impossible pour toute méthode de clustering de satisfaire simultanément trois propriétés fondamentales : l'invariance d'échelle (les résultats restent inchangés sous un redimensionnement proportionnel des distances), la richesse (toutes les partitions possibles des données peuvent être atteintes) et la cohérence entre les distances et la structure de clustering. L'algorithme le plus approprié pour un problème particulier doit souvent être choisi expérimentalement, à moins qu'il n'y ait une raison mathématique de préférer un modèle de cluster à un autre.

Les algorithmes de clustering importants incluent :

• K-means : Un algorithme basé sur les centroïdes qui partitionne les données en k clusters en minimisant la somme des carrés intra-cluster. Il est simple et efficace mais nécessite de spécifier le nombre de clusters et est sensible aux valeurs aberrantes.
• Clustering hiérarchique : Construit une hiérarchie de clusters soit de manière agglomérative (de bas en haut) soit de manière divise (de haut en bas). Il ne nécessite pas un nombre prédéfini de clusters et produit un dendrogramme.
• DBSCAN : Un algorithme basé sur la densité qui identifie les clusters comme des régions denses séparées par des zones clairsemées. Il peut trouver des clusters de formes arbitraires et gérer les valeurs aberrantes, mais nécessite le réglage de paramètres comme epsilon et le nombre minimum de points.
• Espérance-maximisation (EM) : Un algorithme basé sur la distribution qui modélise les clusters comme des distributions gaussiennes et estime itérativement les paramètres pour maximiser la vraisemblance.
• OPTICS : Une extension de DBSCAN qui produit un ordre de clustering, le rendant plus robuste aux densités variables.
• Cartes auto-organisatrices (SOM) : Un modèle de réseau neuronal qui mappe des données de haute dimension sur une grille de basse dimension, préservant les relations topologiques.

Applications

Le clustering est largement utilisé dans de nombreux domaines. En reconnaissance de formes, il aide à identifier des groupes dans les données pour des tâches de classification. En analyse d'images, il est utilisé pour la segmentation d'images et la détection d'objets. En recherche d'informations, le clustering organise les documents par sujet pour la recherche et la recommandation. En bioinformatique, il regroupe des gènes ou des protéines avec des modèles d'expression similaires. En compression de données, le clustering réduit la taille des données en représentant des groupes avec des prototypes. En infographie, il aide à la quantification des couleurs et à la simplification de maillage. En intelligence artificielle, le clustering est une technique centrale pour l'apprentissage non supervisé, permettant aux systèmes de découvrir des modèles sans exemples étiquetés.

Défis et considérations

Le clustering présente plusieurs défis. Déterminer le nombre optimal de clusters est souvent difficile et peut nécessiter des connaissances du domaine ou des heuristiques. Le choix de la métrique de distance affecte considérablement les résultats ; les métriques courantes incluent la distance euclidienne, la distance de Manhattan et la similarité cosinus. Les données de haute dimension peuvent souffrir de la malédiction de la dimensionnalité, où les distances deviennent moins significatives. Les résultats du clustering sont sensibles à l'initialisation et aux paramètres, et il n'existe pas de solution universelle. De plus, la nature itérative du clustering signifie que les résultats doivent être validés à l'aide de métriques d'évaluation internes ou externes, telles que le score de silhouette ou l'indice de Rand, pour garantir qu'ils atteignent les propriétés souhaitées.

Concepts connexes

Le clustering est étroitement lié à d'autres techniques d'apprentissage non supervisé, telles que la réduction de dimensionnalité et la détection d'anomalies. Il est souvent utilisé en conjonction avec augmentation de données pour générer des échantillons synthétiques ou dans le prétraitement pour l'apprentissage supervisé. Dans le contexte de apprentissage profond, le clustering peut être intégré dans des architectures de réseaux neuronaux pour l'apprentissage de représentations. Les principes du clustering sous-tendent également la détection de communautés dans l'analyse de réseaux et la segmentation de marché dans l'analyse commerciale.