Le regroupement basé sur les centroïdes, ou « Centroid-based Clustering » en anglais, est une famille d’algorithmes de partitionnement de données dont l’objectif principal est d’identifier des groupes distincts (clusters) au sein d’un ensemble de données. La caractéristique distinctive de cette approche est que chaque cluster est représenté par un point central, appelé centroïde. Ce centroïde n’est pas nécessairement un point de données existant, mais plutôt un prototype qui résume les caractéristiques des points appartenant à ce cluster. L’algorithme vise à assigner chaque point de données au cluster dont le centroïde lui est le plus « proche » selon une mesure de distance ou de similarité prédéfinie, tout en cherchant à minimiser une fonction objectif, typiquement la somme des distances au carré entre les points et le centroïde de leur cluster respectif.
Les concepts fondamentaux du regroupement basé sur les centroïdes reposent sur plusieurs piliers. Premièrement, la notion de centroïde est cruciale. Pour des données numériques, le centroïde est souvent la moyenne arithmétique des vecteurs de caractéristiques de tous les points appartenant au cluster. Deuxièmement, une mesure de distance ou de similarité est indispensable pour quantifier la proximité entre un point de données et un centroïde, ainsi qu’entre les centroïdes eux-mêmes. La distance euclidienne est la plus couramment utilisée, mais d’autres mesures comme la distance de Manhattan ou la similarité cosinus peuvent être employées selon la nature des données. Troisièmement, la plupart des algorithmes de regroupement basés sur les centroïdes sont itératifs. Ils commencent par une initialisation des centroïdes (par exemple, aléatoire ou par des méthodes plus sophistiquées) puis alternent entre deux étapes : l’assignation des points de données au centroïde le plus proche et le recalcul des centroïdes en fonction des points nouvellement assignés. Ce processus se répète jusqu’à ce qu’un critère de convergence soit atteint, par exemple lorsque les assignations de points ne changent plus ou que les centroïdes se stabilisent. Enfin, une fonction objectif, souvent la somme des carrés des distances intra-cluster (WCSS), guide l’optimisation : l’algorithme cherche à trouver une configuration de clusters qui minimise cette valeur. Le nombre de clusters, noté ‘k’, est généralement un paramètre d’entrée qui doit être spécifié par l’utilisateur.
L’importance du regroupement basé sur les centroïdes réside dans sa simplicité conceptuelle, son efficacité calculatoire sur de grands ensembles de données, et sa large applicabilité. Ces méthodes sont souvent un premier choix pour l’analyse exploratoire de données non étiquetées, permettant de découvrir des structures et des groupements naturels. Leur capacité à produire des prototypes (les centroïdes) pour chaque cluster facilite l’interprétation des résultats ; on peut examiner les caractéristiques du centroïde pour comprendre la nature du groupe qu’il représente. L’impact de ces techniques se manifeste dans de nombreux domaines où la segmentation ou la catégorisation automatique d’objets ou d’observations est nécessaire, contribuant à une meilleure prise de décision, à l’optimisation de processus, et à la découverte de connaissances cachées dans les données.
Les applications pratiques du regroupement basé sur les centroïdes sont nombreuses et variées. En marketing, il est utilisé pour la segmentation de la clientèle : par exemple, regrouper les clients en fonction de leur historique d’achats, de leur démographie ou de leur comportement en ligne pour créer des campagnes publicitaires ciblées. Dans le domaine de la compression d’images, une technique appelée quantification vectorielle, qui est une forme de regroupement basé sur les centroïdes, permet de réduire le nombre de couleurs d’une image en regroupant les pixels de couleurs similaires et en remplaçant chaque groupe par la couleur du centroïde correspondant. En bio-informatique, ces algorithmes aident à regrouper des gènes ayant des profils d’expression similaires sous différentes conditions, ou à classer des séquences protéiques. D’autres applications incluent la détection d’anomalies (les points très éloignés de tout centroïde peuvent être des outliers), l’analyse et le regroupement de documents textuels en fonction de leurs thèmes, ou encore l’organisation de grandes collections de données.
Il existe plusieurs nuances et variations du regroupement basé sur les centroïdes. L’algorithme le plus connu et le plus emblématique est K-Means. Cependant, d’autres variantes ont été développées pour pallier certaines de ses limitations. K-Medoids (comme l’algorithme PAM, Partitioning Around Medoids) utilise des points de données réels comme centroïdes (appelés médoïdes), ce qui le rend plus robuste aux outliers et applicable à des données où le calcul d’une moyenne n’a pas de sens. Pour les données catégorielles, l’algorithme K-Modes remplace la moyenne par le mode pour définir les centroïdes. K-Prototypes est une extension qui gère les ensembles de données contenant des attributs mixtes (numériques et catégoriels). Le Fuzzy C-Means (FCM) est une version « floue » où chaque point de données peut appartenir à plusieurs clusters avec un certain degré d’appartenance, offrant une partition plus nuancée. Mean Shift Clustering est une autre approche basée sur les centroïdes qui ne nécessite pas de spécifier le nombre de clusters à l’avance, car il cherche les modes (pics) de la distribution de densité des données.
Plusieurs concepts sont étroitement liés au regroupement basé sur les centroïdes. Il s’agit d’une sous-catégorie de l’apprentissage non supervisé, car il explore les données sans étiquettes préexistantes. Les mesures de distance (Euclidienne, Manhattan, Cosinus, etc.) sont fondamentales à son fonctionnement. La validation des clusters, utilisant des indices comme l’indice de Silhouette ou l’indice de Davies-Bouldin, est importante pour évaluer la qualité des regroupements produits et aider à déterminer le nombre optimal de clusters. Parfois, des techniques de réduction de dimensionnalité sont appliquées en prétraitement pour améliorer les performances sur des données de haute dimension. En termes de synonymie, le « regroupement par partitionnement » est un terme plus large qui inclut les méthodes basées sur les centroïdes. La « quantification vectorielle » dans le traitement du signal partage des principes similaires. En contraste, les antonymes conceptuels seraient d’autres familles d’algorithmes de clustering comme le regroupement hiérarchique (qui construit une hiérarchie de clusters), le regroupement basé sur la densité (DBSCAN, OPTICS, qui identifie les régions denses de points), ou le regroupement basé sur des modèles (comme les modèles de mélange gaussien, qui supposent que les données sont générées à partir d’une distribution de probabilité).
L’origine du regroupement basé sur les centroïdes, et plus particulièrement de l’algorithme K-Means, remonte au milieu du 20e siècle. Bien que le terme « K-Means » ait été proposé pour la première fois par James MacQueen en 1967, des idées similaires ont été développées indépendamment par d’autres chercheurs. Hugo Steinhaus a décrit un problème similaire en 1956. Stuart Lloyd de Bell Labs a développé un algorithme standard pour la modulation par impulsions et codage (PCM) en 1957, qui est essentiellement l’algorithme K-Means, bien que son travail n’ait été publié qu’en 1982. E. W. Forgy a également publié une méthode similaire en 1965. Depuis ces travaux pionniers, de nombreuses recherches ont été menées pour améliorer l’algorithme K-Means et ses variantes, notamment en ce qui concerne les méthodes d’initialisation des centroïdes (comme K-Means++), la scalabilité pour les très grands ensembles de données, et l’adaptation à différents types de données et de structures de clusters.
Le regroupement basé sur les centroïdes présente plusieurs avantages. Sa simplicité de compréhension et de mise en œuvre est un atout majeur. Il est généralement très efficace sur le plan calculatoire, avec une complexité souvent linéaire par rapport au nombre de points de données, au nombre de dimensions et au nombre d’itérations, ce qui le rend adapté aux grands ensembles de données. Les centroïdes résultants offrent une interprétation intuitive des clusters. Ces méthodes fonctionnent particulièrement bien lorsque les clusters sont de forme sphérique, bien séparés et de tailles similaires.
Cependant, cette approche comporte également des inconvénients et des défis. L’un des principaux inconvénients est la nécessité de spécifier le nombre de clusters (k) à l’avance, ce qui n’est pas toujours connu a priori. Les algorithmes sont sensibles à l’initialisation des centroïdes et peuvent converger vers des optima locaux plutôt que l’optimum global, conduisant à des résultats sous-optimaux. Ils ont des difficultés à identifier des clusters de formes non sphériques, de densités variables ou de tailles très différentes. Le K-Means standard, utilisant la moyenne, est sensible aux outliers (valeurs aberrantes) qui peuvent fausser la position des centroïdes. De plus, il suppose implicitement que les clusters ont une variance égale et sont isotropes lorsque la distance euclidienne est utilisée. Un mauvais choix de k ou une mauvaise initialisation peuvent aussi mener à la formation de clusters vides. Les défis incluent donc le choix d’un k optimal, le développement de stratégies d’initialisation robustes, et l’adaptation à des données de haute dimensionnalité où les notions de distance peuvent devenir moins significatives (la « malédiction de la dimensionnalité »). Enfin, ces méthodes ne découvrent pas naturellement de relations hiérarchiques entre les clusters.