Discussion :

[gheger]

Bonjour,

J'imagine que c'est une question récurrente mais j'y vais tout de même.

Je développe un algo de clustering (hiérarchique ou K-Means).

Et là je veux fusionner les clusters les plus proches mais je ne sais pas quelle distance utiliser...

Plutôt distance de Manhattan (simple somme de mes deltas x et y) ou euclidienne (somme des deltas au carrés puis racine).

Outre la complexité de calcul de ces 2 distances, laquelle serait le plus appropriée pour moi?

Autre question: l'ordre est-il toujours respecté? je veux dire une distance euclidienne entre 2 points est de longueur E1. Une autre distance entre 2 autres points est E2. Si E1 < E2, ce serait aussi toujours le cas pour M1 et M2 mesurées avec les mêmes points?

J'espère que j'ai réussi à me faire comprendre...

Salutations

[ToTo13]

Bonjour,

la distance Euclidienne est la plus courante, car naturelle.
En revanche, la distance de Manathan apporte souvent de bons résultats.
=> Il faut comparer les résultats pour ton problème.

[Mr.ux]

Je dirai que ca depend de ce que representent tes centres de cluster : dans quel referentiel travailles tu ?
Si tes variables sont de type "classe" par exemple la distance euclidienne n'est pas adaptée, celle de manhattan oui. Par contre si t'es variables sont les coordonnées spatiales d'un point x,y,z par ex. la distance euclidienne est la plus apropriée. (La distance de Mahalanobis aussi est pas mal, c' est une generalisation de la distance euclidienne en prennant en compte la correlation entre variables).
Dans ton cas ce site me semble pas mal.

[benDelphic]

Ce qu'il faut savoir c'est que mathématiquement toutes les distances ( et les normes ) sont équivalentes ... reste à voir d'un point de vu algorithmique ... certaines métriques sont plus simples à calculer

[ToTo13]

Ce qu'il faut savoir c'est que mathématiquement toutes les distances ( et les normes ) sont équivalentes ... reste à voir d'un point de vu algorithmique ... certaines métriques sont plus simples à calculer

Tout à fait vrai en théorie, mais en pratique les résultats apportés par ces métriques dans des problèmes de classification (k-means par exemple) sont très différents.

[Zavonen]

Ce qu'il faut savoir c'est que mathématiquement toutes les distances ( et les normes ) sont équivalentes .

Première mise au point: Il s'agit d'équivalences topologiques. C'est à dire que les espaces topologiques induits sont les mêmes.
Seconde mise au point: C'est vrai pour les normes et pas pour les distances. Su R^n la distance d(M,N)= 0 si M=N d(M,N)=1 si M<>n n'est pas équivalente à la distance euclidienne.
Troisième mise au point: Cela n'est vrai, pour les normes, qu'en dimension finie.
Quatrième mise au point: Si on ne s'intéresse qu'à des distances induites par des normes sur des espaces de dimension finie, alors nous avons effectivement une équivalence topologique (les ouverts d'une topologie sont les mêmes que celle de l'autre) mais pas pour autant une équivalence métrique. La Taxi-cab geometry de Krause (autre appelation de Manhattan) est bien différente de la géométrie euclidienne. En particulier, par deux points il passe plusieurs droites.

[souviron34]

je ne suis pas spécialiste des clusters, mais le bon sens voudrait que la distance à prendre en compte soit la distance mini entre les 2 clusters, et non pas entre les centres... non ?