Algorithmes de regroupement (clustering)

Les algorithmes de regroupement (clustering) partitionnent les données en groupes d'éléments similaires, révélant ainsi une structure naturelle sans recourir à des étiquettes.

Definition

Le regroupement (clustering) est le partitionnement non supervisé d'un ensemble de données en groupes, de telle sorte que les points au sein d'un même groupe sont plus similaires entre eux qu'aux points des autres groupes, la similarité étant définie par un critère de distance ou de densité choisi pour l'application.

Scope

Ce sujet aborde les principales familles de regroupement (clustering) : les méthodes basées sur les centroïdes, telles que k-means ; le regroupement hiérarchique agglomératif qui construit un arbre de groupes imbriqués ; les méthodes basées sur la densité qui identifient des groupes de formes arbitraires ; ainsi que le choix des mesures de distance et du nombre de groupes. Il examine ce qui constitue un bon regroupement et pourquoi le problème est intrinsèquement ambigu.

Core questions

• Qu'est-ce qui définit un groupe (cluster) à partir d'un ensemble de points ?
• Comment k-means minimise-t-il itérativement la variance intra-groupe ?
• Comment le nombre de groupes est-il choisi ?
• Quand les méthodes hiérarchiques ou basées sur la densité surpassent-elles les méthodes basées sur les centroïdes ?

Key theories

k-means et l'algorithme de Lloyd

k-means minimise la somme des distances euclidiennes au carré aux centres des groupes en alternant l'affectation des points aux centres les plus proches et le recalcul des centres, une procédure qui converge vers un optimum local.

Regroupement hiérarchique

Le regroupement agglomératif fusionne de manière répétée les groupes les plus proches pour construire un dendrogramme, offrant des regroupements à chaque niveau de granularité et évitant la nécessité de fixer le nombre de groupes à l'avance.

Regroupement par modèles de mélange

Traiter les groupes comme des composantes d'un mélange probabiliste permet des affectations souples et des groupes de formes et de tailles différentes, reliant ainsi le regroupement à l'estimation de densité par variables latentes.

Clinical relevance

Le regroupement (clustering) est à la base de la segmentation de marché, de l'organisation de documents et d'images, du regroupement d'expressions géniques et de la détection d'anomalies ; c'est également un outil principal de l'analyse exploratoire des données. Étant donné que les regroupements dépendent de la distance choisie et du nombre de groupes, les résultats doivent être interprétés avec prudence plutôt que d'être considérés comme une vérité fondamentale unique.

History

La procédure k-means trouve ses origines dans les travaux de quantification de Lloyd en 1957, publiés en 1982, et dans la formulation indépendante de MacQueen. Le regroupement hiérarchique est apparu dans la taxonomie numérique, et les méthodes basées sur la densité, telles que DBSCAN, ont étendu le regroupement à des groupes de formes arbitraires, formant ainsi ensemble la boîte à outils standard du regroupement non supervisé.

Key figures

• Stuart Lloyd
• James MacQueen
• Trevor Hastie

Seminal works

• lloyd1982
• hastie2009
• bishop2006

Frequently asked questions

Pourquoi k-means nécessite-t-il de choisir le nombre de groupes ?

k-means optimise le placement d'un nombre fixe de centres, ce nombre est donc une donnée d'entrée. Son choix repose sur des heuristiques telles que la méthode du coude, les scores de silhouette ou la connaissance du domaine, car l'ajout de groupes supplémentaires réduit toujours la distance intra-groupe.

Les différentes méthodes de regroupement peuvent-elles donner des résultats différents ?

Oui. Puisqu'il n'existe pas de définition unique d'un groupe, les méthodes basées sur les centroïdes, hiérarchiques et basées sur la densité peuvent produire des partitions différentes des mêmes données, chacune étant valide selon son propre critère. Le bon choix dépend des formes de groupes attendues et de l'objectif.