Comparaison des dendrogrammes de regroupement hiérarchique obtenus par différentes distances et méthodes

28

[Le titre initial "Mesure de la similitude pour les arbres de clustering hiérarchiques" a été modifié par la suite par @ttnphns pour mieux refléter le sujet]

J'effectue un certain nombre d' analyses de grappes hiérarchiques sur une trame de données des dossiers des patients (par exemple similaire à http://www.biomedcentral.com/1471-2105/5/126/figure/F1?highres=y )

J'expérimente avec différentes distances mesures, différents poids des paramètres et différentes hierarcical méthodes , de comprendre leur impact sur les pôles finale / structure / vue de l'arbre (dendrogramme). Ma question de savoir s'il existe un calcul / mesure standard pour calculer la différence entre différents arbres hiérarchiques et comment l'implémenter dans R (par exemple pour quantifier que certains arbres sont presque identiques et que certains sont radicalement différents).

Wouter
la source

Réponses:

44

Pour comparer la similitude de deux structures hiérarchiques (arborescentes), des mesures basées sur l'idée de corrélation cophénétique sont utilisées. Mais est-il correct d'effectuer une comparaison des dendrogrammes afin de sélectionner la «bonne» méthode ou mesure de distance dans le clustering hiérarchique?

Il y a certains points - des accrocs cachés - concernant l'analyse hiérarchique des clusters que je considérerais comme très importants :

  • Ne jamais comparer visuellement (afin de sélectionner la méthode donnant une partition plus forte) les dendrogrammes obtenus par différentes méthodes d'agglomération. Il ne dira pas quelle méthode est "meilleure" à cela. Chaque méthode a son propre aspect arborescent "prototypique": les arbres diffèrent de manière cohérente même lorsque les données n'ont pas de structure en grappes ou ont une structure en grappes aléatoire. (Et je ne pense pas qu'il existe une standardisation ou une mesure qui éliminerait ces différences intrinsèques.). Cependant, vous pouvez comparer l'apparence d'un dendrogramme de résultats produits par la même méthode mais des données différentes. Maxim: direct, l'apparence comparant des dendrogrammes après différentes méthodes est inacceptable .
  • Ne décidez pas du nombre de grappes (c.-à-d. Où couper l'arbre) en regardant le dendrogramme de la méthode Ward . À Ward, l’arbre montre la croissance du coefficient sommatif et non moyen de colligation; et la conséquence est que, puisque les grappes ultérieures sont plus grosses par le nombre de points, les grappes ultérieures semblent faussement "meilleures" sur l'arbre. Pour normaliser le dendrogramme de Ward de manière appropriée, divisez la croissance du coefficient à chaque étape par le nombre total de points dans les deux grappes combinées (un tel dendrogramme de Ward standardisé, cependant, peut être difficile à mettre en œuvre graphiquement). 1 Maxim: choisir un niveau de coupe en envisageant une apparence de dendrogramme, bien que possible, n'est pas la meilleure méthode pour sélectionner la partition, et pour certaines méthodes peut être trompeur . Il est recommandé de s'appuyer à la place sur un critère de clustering interne formel .
  • Bien que personne ne puisse vous interdire "d'expérimenter" avec des mesures de distance ou des méthodes agglomératives, il est préférable de sélectionner la distance et la méthode consciemment , et non à l'aveugle. La distance doit refléter les aspects de la différence qui vous intéressent, et la méthode - il faut être conscient - implique un archétype spécifique d'un cluster (par exemple, la métaphore d'un cluster Ward est, je dirais, type ; cluster après un lien complet serait être cercle [par passe-temps ou intrigue]; cluster après liaison unique serait spectre [chaîne]; cluster après méthode centroïde serait proximité de plates-formes [politique]; un cluster de liaison moyen est conceptuellement le plus indifférencié et serait généralement de classe unie ).
  • Certaines méthodes nécessitent des mesures de distance et / ou un type de données corrects. Ward et centroïde, par exemple, nécessitent logiquement une distance euclidienne (au carré) - parce que ces méthodes se livrent au calcul des centroïdes dans l'espace euclidien. Et le calcul des centroïdes géométriques est incongru avec, par exemple, des données binaires; les données doivent être à l'échelle / continues. Maxim: les hypothèses données / distance / méthode et la correspondance est une question très importante et pas si facile.
  • Le prétraitement (comme le centrage, la mise à l'échelle et d'autres formes de transformation de variables / caractéristiques), le calcul préalable d'une matrice de distance et le regroupement sont également des questions extrêmement importantes. Cela peut considérablement influer sur les résultats. Réfléchissez à ce que le prétraitement peut vous aider et aura du sens du point de vue de l'interprétation. Aussi, ne soyez pas timide pour inspecter soigneusement vos données graphiquement avant d'essayer de faire une analyse de cluster.
  • Toutes les méthodes de regroupement aggloméré ne peuvent pas être considérées de la même manière comme vous donnant une classification hiérarchique ... pour des raisons philosophiques. Par exemple, la méthode centroïde donne une hiérarchie dans un sens, car le centre de cluster est une caractéristique émergente et définissante d'un cluster dans son ensemble , et la fusion de clusters est entraînée par cette fonctionnalité. La liaison complète, en revanche, «rejette» les deux sous-grappes lorsqu'elle les fusionne - en raison de la distance entre les objets individuels des deux. Ainsi, un dendrogramme de liaison complet n'est qu'une histoire de collecte et non une sorte de taxonomie parent-enfant .Maxim: l'analyse de cluster aggloméré hiérarchique, généralement, s'attend à ce que vous fassiez une partition en fonction de son résultat, plutôt que de voir le résultat comme une taxonomie hiérarchique.
  • Le clustering hiérarchique est un algorithme gourmand typique qui fait le meilleur choix parmi les alternatives apparaissant à chaque étape dans l'espoir de se rapprocher de la solution optimale à la fin. Cependant, le "meilleur" choix apparaissant sur une étape de haut niveau est susceptible d'être plus pauvre que l'optimum global théoriquement possible sur cette étape. Plus le pas est grand, plus la sous-optimalité est grande, en règle générale. Étant donné que nous voulons généralement quelques clusters, les dernières étapes sont importantes; et, comme je viens de le dire, ils devraient être relativement médiocres si le nombre d'étapes est élevé (disons, millième étape). C'est pourquoi le regroupement hiérarchique n'est généralement pas recommandé pour les grands échantillons d'objets (numérotant des milliers d'objets) même si le programme peut gérer une matrice de distance aussi grande.

XjejOuijej


1 implémentations) et de ne pas cumuler. Pour répéter encore une fois, ces différences n'affectent que la forme / l'apparence générale du dendrogramme, pas les résultats du regroupement. Mais l'apparence du dendrogramme pourrait influencer votre décision sur le nombre de grappes. La morale est qu'il serait prudent de ne pas s'appuyer du tout sur le dendrogramme dans la méthode de Ward, à moins que vous ne sachiez exactement quels sont ces coefficients de votre programme et comment les interpréter correctement.

ttnphns
la source
5
Je peux appuyer à peu près tout cela. Deux points que je veux ajouter: A) ce que vous semblez faire est une sorte de sur- ajustement . En évaluant systématiquement les mesures, les poids et les méthodes, il y a un risque élevé que les paramètres avec lesquels vous vous retrouvez soient très spécifiques pour vos données actuelles, et puissent être inutiles sur d'autres données ou même des données ultérieures. B) à quoi bon connaître la similitude des dendrogrammes. Réfléchissez ensuite à ce que vous voulez en faire, puis essayez d'évaluer le résultat final. L'évaluation des résultats intermédiaires peut être trompeuse.
Anony-Mousse
1
Si le sujet vous intéresse toujours, j'ai pensé que vous pourriez trouver utile ma réponse récente sur DS SE , d'autant plus qu'elle offre une couverture, bien que limitée, des approches fréquentistes et bayésiennes des modèles topiques hiérarchiques (avec des informations de classe intégrées) et sélectionner des mesures de similitude .
Aleksandr Blekh
@ttnphns, pourriez-vous expliquer plus en détail comment utiliser le "coefficient de colligation" pour comparer deux classifications hiérarchiques?
bassir