Comment comprendre les inconvénients du clustering hiérarchique?

19

Quelqu'un peut-il expliquer les avantages et les inconvénients du clustering hiérarchique?

  1. Le clustering hiérarchique présente-t-il les mêmes inconvénients que K signifie?
  2. Quels sont les avantages du clustering hiérarchique par rapport à K signifie?
  3. Quand devrions-nous utiliser les moyennes de K sur le clustering hiérarchique et vice versa?

Les réponses à ce post expliquent très bien les inconvénients de k. Comment comprendre les inconvénients des K-means

GeorgeOfTheRF
la source
2
Dans cette réponse, j'ai abordé certaines des facettes potentiellement problématiques de l'analyse des clusters agglomérés hiérarchiques. Le principal "inconvénient" est qu'il s'agit d'un algorithme gourmand à passage unique non itératif. Avec un algorithme gourmand, vous optimisez la tâche de l'étape en cours qui, pour la plupart des méthodes HC, ne garantit pas nécessairement la meilleure partition à une étape future lointaine. Le principal avantage de HC est sa flexibilité quant au choix de la mesure de proximité à utiliser. @Mic a déjà donné une bonne réponse ci-dessous, donc je ne fais que répéter.
ttnphns

Réponses:

13

Alors que -means essaie d'optimiser un objectif global (variance des clusters) et atteint un cluster local optimal, agglomératif hiérarchique vise à trouver la meilleure étape à chaque fusion de cluster (algorithme gourmand) qui se fait exactement mais aboutit à une solution potentiellement sous-optimale .k

Il faut utiliser le clustering hiérarchique lorsque les données sous-jacentes ont une structure hiérarchique (comme les corrélations sur les marchés financiers) et que vous souhaitez récupérer la hiérarchie. Vous pouvez toujours appliquer -moyens pour ce faire, mais vous pouvez vous retrouver avec des partitions (de la plus grossière (tous les points de données d'un cluster) à la plus fine (chaque point de données est un cluster)) qui ne sont pas imbriquées et donc pas une hiérarchie appropriée.k

Si vous souhaitez explorer les propriétés plus fines du clustering, vous ne voudrez peut-être pas opposer le clustering plat tel que -moyen au clustering hiérarchique tel que les liens simples, moyens et complets. Par exemple, tous ces clusters sont économes en espace, c'est-à-dire que lorsque vous construisez des clusters, vous ne déformez pas l'espace, alors qu'un cluster hiérarchique tel que Ward ne conserve pas l'espace, c'est-à-dire qu'à chaque étape de fusion, il déformera l'espace métrique.k

Pour conclure, les inconvénients des algorithmes de clustering hiérarchiques peuvent être très différents les uns des autres. Certains peuvent partager des propriétés similaires aux moyens: Ward vise à optimiser la variance, mais pas le Single Linkage. Mais ils peuvent aussi avoir des propriétés différentes: Ward est dilatateur d'espace, alors que Single Linkage est conservateur d'espace comme k- moyens.kk

- modifier pour préciser les propriétés de conservation de l'espace et de dilatation de l'espace

Économie d'espace: D i j est la distance entre les clusters C i et C j que vous souhaitez fusionner, et d

Dij[minxCi,yCjd(x,y),maxxCi,yCjd(x,y)]
DijCiCjd est la distance entre les points de données.

Dilatation spatiale: c'est-à-dire qu'en fusionnant C i et C j l'algorithme repoussera plus loin le cluster C k .

D(CiCj,Ck)max(Dik,Djk),
CiCjCk
micro
la source
Pouvez-vous donner quelques exemples supplémentaires de données ayant une structure hiérarchique? N'a pas suivi l'exemple des marchés financiers.
GeorgeOfTheRF
Sûr. cf. arxiv.org/pdf/cond-mat/9802256.pdf ou simplement la figure 7 dans arxiv.org/pdf/1506.00976.pdf qui représente une matrice de corrélation qui a une structure de blocs de corrélation hiérarchique (bruyante): vous pouvez remarquer des blocs sur la principale diagonale, qui sont divisés en plusieurs blocs, chacun divisé en encore plus de blocs. Il correspond grosso modo à une subdivision en régions (Europe, États-Unis, Asie hors Japon, Japon), puis chaque région divisée par la qualité des actifs (disons haute qualité vs indésirable), puis divisée par les grands secteurs industriels (commerce de détail, industrie, media), subdivisé en (aérospatial, auto ...)
micro
3
+1. Cependant, should use hierarchical clustering when underlying data has a hierarchical structure... and you want to recover the hierarchypas nécessairement. Dans la plupart des cas, au contraire. La hiérarchie de HC est plutôt une histoire de l'algo qu'une structure des données . Pourtant, cette question est finalement philosophique / logique, pas si statistique.
ttnphns
Ward is not space-conserving, i.e. at each merging step it will distort the metric space. Pouvez-vous en écrire plus? Ce n'est pas très clair.
ttnphns
Ward is space-dilating, whereas Single Linkage is space-conserving like k-means. Vouliez-vous dire contrat d'espace pour liaison simple?
ttnphns
13

Évolutivité

signifie que c'est clairement le gagnant ici. O ( n k d i ) est bien meilleure que l'évolutivité O ( n 3 d ) (dans certains cas O ( n 2 d ) ) du clustering hiérarchique car généralement k et i et d sont généralement petits (malheureusement, j'ai tendance à croître avec n , donc O ( n ) ne faitpaskO(nkdi)O(n3d)O(n2d)kidinO(n)détiennent généralement). En outre, la consommation de mémoire est linéaire, par opposition à quadratique (généralement, des cas spéciaux linéaires existent).

La flexibilité

-means est extrêmement limité dans son applicabilité. Il est essentiellement limité aux distances euclidiennes (y compris euclidiennes dans les espaces du noyau et divergences de Bregman, mais celles-ci sont assez exotiques et personne ne les utilise réellement avec les k- moyens). Pire encore, k -means ne fonctionne que sur des données numériques (qui devraient en fait être continues et denses pour être bien adaptées aux k -means).kkkk

Le clustering hiérarchique est clairement le gagnant ici. Il ne nécessite même pas de distance - toute mesure peut être utilisée, y compris les fonctions de similitude simplement en préférant les valeurs élevées aux valeurs faibles. Données catégorielles? assurez-vous simplement d'utiliser par exemple Jaccard. Des cordes? Essayez la distance Levenshtein. Des séries chronologiques? sûr. Données de type mixte? Distance Gower. Il existe des millions d'ensembles de données où vous pouvez utiliser le clustering hiérarchique, mais où vous ne pouvez pas utiliser -means.k

Modèle

Aucun gagnant ici. signifie un score élevé car il permet une grande réduction des données. Les centroïdes sont faciles à comprendre et à utiliser. Le regroupement hiérarchique, en revanche, produit un dendrogramme. Un dendrogramme peut également être très très utile pour comprendre votre ensemble de données.k

Anony-Mousse -Reinstate Monica
la source
La hiérarchie échoue-t-elle comme k signifie lorsque les grappes sont 1) non sphériques 2) ont un rayon différent 3) ont une densité différente?
GeorgeOfTheRF
2
Les deux peuvent fonctionner et les deux peuvent échouer. C'est pourquoi des choses comme les dendrogrammes sont utiles. Ne faites jamais confiance à un résultat de clustering pour être "correct", jamais.
Anony-Mousse -Reinstate Monica
Le clustering hiérarchique peut donner des clusters optimisés localement car il est basé sur une approche gourmande mais K signifie donne des clusters optimisés globalement. J'ai également constaté que l'explication du clustering hiérarchique est relativement facile pour les gens d'affaires à comparer aux moyennes K.
Arpit Sisodia
7

Je voulais juste ajouter un peu aux autres réponses comment, dans un certain sens, il y a une bonne raison théorique de préférer certaines méthodes de regroupement hiérarchique.

Une hypothèse courante dans l'analyse en grappes est que les données sont échantillonnées à partir d'une densité de probabilité sous-jacente laquelle nous n'avons pas accès. Mais supposons que nous y ayons eu accès. Comment définirions-nous les grappes de f ?ff

Une approche très naturelle et intuitive consiste à dire que les grappes de sont les régions de haute densité. Par exemple, considérez la densité à deux pics ci-dessous:f

entrez la description de l'image ici

En traçant une ligne sur le graphique, nous induisons un ensemble de grappes. Par exemple, si nous dessinons une ligne à , nous obtenons les deux groupes affichés. Mais si nous dessinons la ligne à λ 3 , nous obtenons un seul cluster.λ1λ3

Pour rendre cela plus précis, supposons que nous ayons un arbitraire . Quels sont les clusters de f au niveau λ ? Ils sont la composante connectée de l'ensemble de super-niveaux { x : f ( x ) λ } .λ>0fλ{x:f(x)λ}

Maintenant, au lieu de choisir un arbitraire, nous pourrions considérer tous les λ , de sorte que l'ensemble des "vrais" groupes de f sont tous des composants connectés de tout ensemble de super-niveaux de f . La clé est que cette collection de clusters a une structure hiérarchique .λ λff

Permettez-moi de préciser cela. On suppose que est supporté sur X . Soit maintenant C 1 une composante connectée de { x : f ( x ) λ 1 } , et C 2 une composante connectée de { x : f ( x ) λ 2 } . En d'autres termes, C 1 est un cluster au niveau λ 1 et C 2 est un cluster au niveau λ 2 . Puis sifXC1{x:f(x)λ1}C2{x:f(x)λ2}C1λ1C2λ2 , puis soit C 1C 2 , soit C 1C 2 = . Cette relation d'imbrication s'applique à n'importe quelle paire de grappes de notre collection, donc ce que nous avons est en fait unehiérarchiede grappes. Nous appelons cela l'arborescence des clusters.λ2<λ1C1C2C1C2=

Alors maintenant, j'ai quelques données échantillonnées à partir d'une densité. Puis-je regrouper ces données d'une manière qui récupère l'arborescence des clusters? En particulier, nous aimerions qu'une méthode soit cohérente dans le sens où, à mesure que nous collectons de plus en plus de données, notre estimation empirique de l'arborescence des grappes se rapproche de plus en plus de la véritable arborescence des grappes.

ABfnfXnXnAnAXnBnBXnPr(AnBn)=1nAB

Essentiellement, la cohérence de Hartigan indique que notre méthode de regroupement devrait séparer de manière adéquate les régions de haute densité. Hartigan a cherché à savoir si le clustering à liaison unique pouvait être cohérent et a constaté qu'il n'était pas cohérent dans ses dimensions liaison unique robuste , qui est prouvée cohérente. Je suggère de lire leur méthode, car elle est assez élégante, à mon avis.

Donc, pour répondre à vos questions, il y a un sens dans lequel le cluster hiérarchique est la "bonne" chose à faire lorsque vous essayez de récupérer la structure d'une densité. Cependant, notez les citations effrayantes autour de "droite" ... En fin de compte, les méthodes de clustering basées sur la densité ont tendance à mal fonctionner dans les dimensions élevées en raison de la malédiction de la dimensionnalité, et donc même si une définition du clustering basée sur les clusters est des régions à forte probabilité est assez propre et intuitif, il est souvent ignoré au profit de méthodes plus performantes en pratique. Cela ne veut pas dire que la liaison unique robuste n'est pas pratique - elle fonctionne en fait assez bien sur les problèmes de dimensions inférieures.

Enfin, je dirai que la cohérence Hartigan n'est pas en quelque sorte en accord avec notre intuition de convergence. Le problème est que la cohérence Hartigan permet à une méthode de clustering de sur-segmenter considérablement les clusters de sorte qu'un algorithme peut être cohérent Hartigan, tout en produisant des clusters qui sont très différents de la véritable arborescence de cluster. Nous avons produit cette année des travaux sur une autre notion de convergence qui aborde ces questions. Le travail est apparu dans "Beyond Hartigan Consistency: Merge distortion metric for hierarchical clustering" dans COLT 2015.

jme
la source
C'est une façon intéressante de penser le clustering hiérarchique. Je trouve que cela rappelle fortement le regroupement par estimation de densité non paramétrique ( pdf ), qui est implémenté Rdans le package pdfCluster . (J'en discute ici .)
gung - Rétablir Monica
HDBSCAN * utilise une approche similaire.
Anony-Mousse -Reinstate Monica
3

Un avantage pratique supplémentaire dans le clustering hiérarchique est la possibilité de visualiser les résultats à l'aide d'un dendrogramme. Si vous ne savez pas à l'avance le nombre de clusters que vous recherchez (comme c'est souvent le cas ...), vous pouvez utiliser le diagramme de dendrogramme pour vous aider à choisirksans avoir besoin de créer des regroupements séparés. Le dédramogramme peut également donner un excellent aperçu de la structure des données, aider à identifier les valeurs aberrantes, etc. Dans k-means, vous pouvez également choisir différentes méthodes pour mettre à jour les moyennes de cluster (bien que l'approche Hartigan-Wong soit de loin la plus courante), ce qui n'est pas un problème avec la méthode hiérarchique.

EDIT grâce à ttnphns: Une caractéristique que le clustering hiérarchique partage avec de nombreux autres algorithmes est la nécessité de choisir une mesure de distance. Cela dépend souvent fortement de l'application et des objectifs particuliers. Cela peut être considéré comme une complication supplémentaire (un autre paramètre à sélectionner ...), mais aussi comme un atout - plus de possibilités. Au contraire, l'algorithme K-means classique utilise spécifiquement la distance euclidienne.

Jacek Podlewski
la source
3
Je suppose que le "problème" dans votre dernier paragraphe serait considéré comme un atout. K-means, cependant, est basé implicitement uniquement sur la distance euclidienne .
ttnphns
Beaucoup de choix possibles peuvent être un problème ainsi qu'un atout, en effet :) Merci pour le commentaire sur k-means, je vais améliorer ce paragraphe.
Jacek Podlewski
@ttnphns En fait, " k-means "peut être utilisé avec toutes les divergences de Bregman jmlr.org/papers/volume6/banerjee05b/banerjee05b.pdf ; je veux dire que c'est le cas lorsque l'on considère quek-moyens est ce qui résulte lorsque l'on considère le cas limite des modèles de mélange gaussiens (du doux au dur), puis en remplaçant le gaussien par un autre membre de la famille exponentielle, vous remplacez la distance euclidienne par une autre divergence de Bregman associée au membre de la famille que vous choisi. Vous vous retrouvez avec un schéma d'algorithme similaire qui vise à trouver une probabilité maximale avec une maximisation des attentes.
micro
Je crois que la question initiale a été posée en ce qui concerne les K-moyens "classiques" et non la moindre intention de se plonger dans les divergences de Bregman. Belle remarque cependant, je vais vérifier cet article plus en détail à coup sûr.
Jacek Podlewski
@mic personne n'utilise les divergences de Bregman au-delà des variations de la distance euclidienne ... c'est une toute petite classe. Mais les gens aimeraient utiliser par exemple la distance de Manhattan, Gower etc. qui ne sont pas des divergences de Bregman pour autant que je sache.
Anony-Mousse -Reinstate Monica