Une distance doit-elle être une «métrique» pour qu'un clustering hiérarchique soit valide sur celle-ci?

9

Disons que nous définissons une distance, qui n'est pas une métrique , entre N éléments.

Sur la base de cette distance, nous utilisons ensuite un regroupement hiérarchique agglomératif .

Pouvons-nous utiliser chacun des algorithmes connus (liaison simple / maximale / moyenne, etc.) pour obtenir des résultats significatifs? Ou autrement dit, quel est le problème avec leur utilisation si la distance n'est pas une métrique?

clustering multilevel-analysis metric hierarchical-clustering Tal Galili
la source
Quels sont les "articles" dans votre cas? (Je demande si cela a quelque chose à voir avec la psychométrie parce que si c'est le cas, je recommanderais de jeter un coup d'œil à la classification des éléments , ou Revelle, W.Hierarchical cluster analysis and tihe internal structure of tests , MBR (1979) 14 : 57.)
chl

Réponses:

7

Les exigences pour les distances dépendent de la méthode de regroupement hiérarchique. Les méthodes simples, complètes et moyennes nécessitent que les distances soient non négatives et symétriques. Les méthodes Ward, centroïde et médiane ont besoin de distances euclidiennes (au carré) (qui sont encore plus étroites que métriques) pour produire des résultats géométriquement significatifs.

(On peut vérifier si sa matrice de distance est euclidienne en la centrant doublement [voir ma réponse ici ] et en regardant les valeurs propres; si aucune valeur propre négative n'est trouvée, alors les distances convergent dans l'espace euclidien.)

ttnphns
la source
Merci. Autre question: l'inégalité du triangle doit-elle tenir pour des méthodes simples, complètes et moyennes? et si une certaine distance n'est pas (par exemple) non symétrique, quel problème cela pose-t-il à ces méthodes? (Merci!)
Tal Galili
1
Les méthodes de clustering hiérarchiques classiques ne peuvent prendre que de la matrice symétrique: une distance de A à B = de B à A. Il existe d'autres méthodes spéciales pour traiter les asymétriques (vous pouvez google). Quant à l'inégalité triangulaire - ce n'est pas une condition nécessaire pour les méthodes que vous mentionnez. (Cependant, la sagesse commune pense que la "distance" est une mesure de l'inégalité, donc il vaut la peine d'envisager de l'imposer si elle est manquante. Pour ce faire, ajoutez de manière itérative une petite constante aux distances et vérifiez. Et si vous continuez à ajouter en atteignant alors vous arriverez bientôt à des distances euclidiennes)
ttnphns
5

Non, la distance ne doit pas nécessairement être une métrique. Il peut, par exemple, être ultramétrique:

d(A,B)≤max(d(A,C),d(B,C))

Les distances ultramétriques obtenues à partir des étapes successives de l'algorithme de clustering peuvent être représentées à l'aide de dendrogrammes, que vous avez peut-être vus dans ce contexte.

Hong Ooi
la source
Merci Hong. Je me souviens que les méthodes pour transformer certains objets en hclust exigent que le dendrogramme soit ultramétrique - je blesse si cela a à voir avec ce que vous avez écrit. En tout cas, merci pour la réponse.
Tal Galili