Quels critères d'arrêt pour le clustering hiérarchique aggloméré sont utilisés dans la pratique?

32

J'ai trouvé une littérature abondante proposant toutes sortes de critères (par exemple Glenn et al. 1985 (pdf) et Jung et al. 2002 (pdf)). Cependant, la plupart d'entre eux ne sont pas si faciles à mettre en œuvre (du moins de mon point de vue). J'utilise scipy.cluster.hierarchy pour obtenir une hiérarchie de cluster, et j'essaie maintenant de décider comment former des clusters plats à partir de cela. Mon objectif est de découvrir des modèles communs dans mes observations, donc je n'ai aucune référence pour comparer le clustering obtenu. Quelqu'un peut-il suggérer une solution pragmatique?

Björn Pollex
la source
Sur ma page Web, il y a une collection zip "Critères de clustering" avec la description (et les fonctions SPSS) d'un certain nombre de critères de clustering populaires (règles d'arrêt). Pour ton information.
ttnphns

Réponses:

18

L'entrée Wikipedia suivante fait en fait un assez bon travail pour expliquer les méthodes les plus populaires et relativement simples:

L' heuristique de la méthode Elbow décrite ici est probablement la plus populaire en raison de sa simple explication (quantité de variance expliquée par le nombre de grappes) couplée à la vérification visuelle. La méthode de la théorie de l'information n'est pas difficile à implémenter non plus et la page a un pseudocode que vous pouvez utiliser pour commencer. Ce dernier est analogue à une probabilité pénalisée basée sur la complexité du modèle comme dans les critères d'information bien connus tels que AIC, BIC, etc.

ars
la source
Merci! L'article de Wikipedia sur le clustering hiérarchique n'est pas lié à celui-ci.
Björn Pollex,
2
Ah oui. Correction maintenant sous les liens "voir aussi", merci de l'avoir signalé!
ars
Dans la méthode Elbow, que se passe-t-il si les objets à regrouper sont assez "complexes"? Je veux dire que ce ne sont pas de simples points, mais plutôt des collections complexes de données. J'ai compris leur distance par paire (distance auto-définie). Comment calculer ici la soi-disant "variance" pour appliquer la méthode du coude?
Sibbs Gambling
17

Il est assez difficile de fournir une solution claire sur la façon de choisir le "meilleur" nombre de clusters dans vos données, quelle que soit la méthode de clustering que vous utilisez, car l'analyse de clusters cherche à isoler des groupes d'unités statistiques (qu'il s'agisse d'individus ou de variables ) à des fins exploratoires ou descriptives, essentiellement. Par conséquent, vous devez également interpréter la sortie de votre schéma de clustering et plusieurs solutions de cluster peuvent être tout aussi intéressantes.

Maintenant, en ce qui concerne les critères statistiques habituels utilisés pour décider quand s'arrêter pour agréger les données, comme indiqué par @ars, la plupart sont des critères visuels , y compris l'analyse du dendrogramme ou l'inspection des profils de grappes, également appelés graphiques de silhouette (Rousseeuw, 1987) . Plusieurs critères numériques , également appelés indices de validité, ont également été proposés, par exemple l'indice de validité de Dunn, l'indice de validité Davies-Bouldin, l'indice C, le gamma d'Hubert, pour n'en nommer que quelques-uns. Le clustering hiérarchique est souvent exécuté avec k-means (en fait, plusieurs instances de k-means puisqu'il s'agit d'un algorithme stochastique), de sorte qu'il ajoute un support aux solutions de clustering trouvées. Je ne sais pas si tout cela est facilement disponible en Python, mais une énorme quantité de méthodes est disponible en R (voir leVue des tâches de cluster , déjà citée par @mbq pour une question connexe, Quels outils pourraient être utilisés pour appliquer des algorithmes de clustering sur MovieLens? ). D'autres approches incluent le clustering flou et le clustering basé sur un modèle (également appelé analyse des caractères latents , dans la communauté psychométrique) si vous recherchez un moyen plus robuste de choisir le nombre de clusters dans vos données.

BTW, je viens de découvrir cette page Web, scipy-cluster , qui est une extension de Scipy pour générer, visualiser et analyser des clusters hiérarchiques . Peut-être qu'il comprend d'autres fonctionnalités? J'ai également entendu parler de PyChem qui offre de très bonnes choses pour l'analyse multivariée.

La référence suivante peut également être utile:

Steinley, D. et Brusco, MJ (2008). Sélection de variables dans l'analyse en grappes: une comparaison empirique de huit procédures. Psychometrika , 73 , 125-144.

chl
la source
Merci pour cette excellente réponse! En fait, le module de clustering hiérarchique que vous avez montré fait déjà partie de scipy. De plus, scipy fournit une implémentation de k-means, donc je pourrais facilement l'utiliser.
Björn Pollex
D'accord, je n'ai pas examiné les détails. Pour k-means, vous devez faire attention au fait que nous avons généralement besoin de deux boucles externes pour valider la solution de cluster (une où vous faites varier le nombre de clusters et une autre pour varier la graine - l'objectif étant de minimiser le RSS); vous pouvez ensuite utiliser la statistique Gap pour choisir le nombre optimal de clusters.
chl
5

Je suis récemment devenu financeur de la méthode de visualisation clustergram (implémentée en R).

Je l'utilise comme méthode supplémentaire pour évaluer un "bon" nombre de clusters. L'extension à d'autres méthodes de clustering n'est pas si difficile (je l'ai fait, je n'ai pas pu publier le code)

texte alternatif

Tal Galili
la source