Pourquoi l'algorithme de clustering k-means utilise-t-il uniquement la métrique de distance euclidienne?

62

Existe-t-il un objectif spécifique en termes d'efficacité ou de fonctionnalité pour lequel l'algorithme k-means n'utilise pas, par exemple, la similarité cosinus comme métrique de distance, mais ne peut utiliser que la norme euclidienne? En général, la méthode K-means sera-t-elle conforme et sera-t-elle correcte si d'autres distances que Euclidean sont considérées ou utilisées?

[Ajout par @ttnphns. La question est double. La "distance (non) euclidienne" peut concerner la distance entre deux points de données ou la distance entre un point de données et un centre de grappe. Les deux manières ont été essayées pour répondre dans les réponses jusqu'à présent.]

curieuse
la source
Cette question a déjà été posée environ 10 fois sur stackoverflow et sur ce site. Veuillez utiliser la fonction de recherche.
Anony-Mousse
3
@ Anony-Mousse: Bien que je sois tout à fait d’accord avec vous et que j’ai levé un paquet de drapeaux récemment sur SO, je trouve troublant l’absence de clôture en double sur la plupart de ces questions.
Nikana Reklawyks
4
Ceci est la page qui vient en premier en googlant sur ce sujet.
haripkannan

Réponses:

62

La procédure K-Means - qui est une méthode de quantification vectorielle souvent utilisée en tant que méthode de classification - n’utilise pas explicitement les distances paires de points de données n / w (contrairement à la classification hiérarchique et à certaines autres qui permettent une mesure de proximité arbitraire). Cela revient à attribuer de manière répétée des points au centre de gravité le plus proche, utilisant ainsi la distance euclidienne entre les points de données et un centre de gravité . Cependant, K-Means est implicitement basé sur des distances euclidiennes par paires n / w points de données, car la somme des écarts au carré par rapport au centre de la centroïde est égale à la somme des distances euclidiennes au carré par paires divisée par le nombre de points. Le terme "centroïde" vient lui-même de la géométrie euclidienne. C'est une moyenne multivariée dans l'espace euclidien. L'espace euclidien concerne les distances euclidiennes. Les distances non euclidiennes ne s'étendront généralement pas sur l'espace euclidien. C'est pourquoi K-Means concerne uniquement les distances euclidiennes.

Mais une distance euclidienne entre deux points de données peut être représentée de différentes manières . Par exemple, il est étroitement lié au cosinus ou au produit scalaire entre les points. Si vous avez un cosinus, ou une covariance, ou une corrélation, vous pouvez toujours (1) le transformer en distance euclidienne (au carré), puis (2) créer des données pour cette matrice de distances euclidiennes (au moyen de coordonnées principales ou d'autres formes métriques). Multidimensional Scaling) pour (3) entrer ces données dans la classification K-Means. Par conséquent, il est possible de faire en sorte que K-Means fonctionne avec des cosinus par paires ou autres; en fait, de telles mises en œuvre de la classification K-Means existent. Voir également à propos de "K-moyennes pour la matrice de distance" mise en œuvre.

Il est possible de programmer des K-moyennes de manière à calculer directement sur la matrice carrée des distances euclidiennes par paires, bien sûr. Mais cela fonctionnera lentement et le moyen le plus efficace est donc de créer des données pour cette matrice de distance (conversion des distances en produits scalaires, etc. - le laissez-passer décrit dans le paragraphe précédent) - puis d'appliquer la procédure standard K-means. à cet ensemble de données.

Veuillez noter que je discutais du sujet de savoir si la dissemblance euclidienne ou non-euclidienne entre les points de données est compatible avec K-means. La question qui se pose est de savoir si les déviations non-euclidiennes du centre de la centroïde (au sens large, au centre ou quasi-droïde) peuvent être incorporées dans des K-moyennes ou dans des "K-moyennes" modifiées.

Voir la question connexe K-means: Pourquoi minimiser WCSS, c'est maximiser la distance entre les clusters .

tnphns
la source
Pouvez-vous citer quelques exemples de la démarche que vous mentionnez?
curieux
4
@ Douglas, s'il vous plaît. J'ai dit que k-means ne pas utiliser des distances par paires. C'est clairement indiqué. Il utilise les distances jusqu'au centroïde. Mais cela signifie automatiquement que l'optimisation des distances par paires au sein des grappes est implicitement liée à la tâche.
15h30
1
@ttnphns: Dans le nombre de caractères que vous avez écrit But a Euclidean distance b/w two data points can be represented in a number of alternative ways. For example, it is closely tied with cosine or scalar product b/w the points. If you have cosine, or covariance, or correlation, you can always (1) transform it to (squared) Euclidean distance, vous auriez tout aussi bien pu écrire: distance(x,y) = 1 - cosine_sim(x,y)ou quelque chose de semblable, de même, informatif.
stackoverflowuser2010
1
Cela ressemble à une critique valable et constructive: il est préférable d’inclure des informations directement dans votre message plutôt que de compter sur un lien; et il vaut généralement mieux être explicite que vague. (cc @stackoverflowuser)
whuber
3
Qu'attendez-vous? Qu'il est préférable dans ce cas de s'appuyer sur un lien, ou plutôt d'être vague, ou les deux? Et pourquoi?
whuber
46

Voir aussi @ttnphns answer pour une interprétation de k-means qui implique des distances euclidiennes ponctuelles.

La manière dont k-means est construit n'est pas basée sur les distances .

K-moyennes minimise la variance intra-cluster. Maintenant, si vous regardez la définition de la variance, elle est identique à la somme des distances euclidiennes au carré par rapport au centre. (@ttnphns answer fait référence à des distances euclidiennes par paires!)

L'idée de base de k-means est de minimiser les erreurs au carré . Il n'y a pas de "distance" impliqué ici.

Pourquoi il n’est pas correct d’utiliser des distances arbitraires: parce que k-means peut cesser de converger avec d’autres fonctions de distance . La preuve commune de la convergence est la suivante: l’étape d’affectation et l’étape de mise à jour moyenne optimisent le même critère. Il y a un nombre fini d'assignations possibles. Par conséquent, il doit converger après un nombre fini d’améliorations. Pour utiliser cette preuve avec d'autres fonctions de distance, vous devez montrer que la moyenne (remarque: k- means ) minimise également vos distances.

Si vous recherchez une variante de k-moyennes à Manhattan, il existe des k-médianes. Parce que la médiane est un meilleur estimateur connu de la L1.

Si vous voulez des fonctions de distance arbitraires, jetez un œil à k-medoids (alias: PAM, partitionner autour de medoids). Le médoïde minimise les distances arbitraires (car il est défini comme le minimum), et il n'existe qu'un nombre fini de médoïdes possibles. C'est beaucoup plus cher que la moyenne, cependant.

Anony-Mousse
la source
Mais à la première étape de k-signifie que chaque point est mis dans le groupe avec la distance euclidienne la plus proche avec le centroïde du groupe ... Donc, il y a une métrique de distance
curieux
@AnonyMousse @ttnphns answer refers to pairwise Euclidean distances!Dans ma réponse, 1er paragraphe, je me réfère clairement à la fois aux interprétations "erreur SS" (directe) et "paire par seconde" (implicite).
Le
3
Je suis d'accord avec ta réponse. Notez que votre compte opérationnel k-means may stop converging with other distance functionsest homologue de ma théorie Non-euclidean distances will generally not span euclidean space.
Le
très bonne explication. Je n'ai jamais réfléchi à la distance euclidienne et je ne me suis pas rendu compte qu'elle minimisait réellement la somme des carrés restants.
Verena Haunschmid
Je ne vois toujours pas pourquoi la moyenne minimisait les distances en termes de distances euclidiennes et, en termes de cosinus, pas du tout en ce qui concerne la preuve
curieux
9

Je suis peut-être un peu pédant ici, mais K-means est le nom donné à un algorithme particulier qui attribue des étiquettes aux points de données, de sorte que les variances au sein des grappes soient minimisées et que ce n’est pas le nom d’une "technique générale".

L'algorithme K-moyennes a été proposé indépendamment de plusieurs domaines, avec de fortes interprétations applicables au domaine. Il s'avère simplement que c’est aussi une distance euclidienne au centre. Pour un bref historique de K-means, veuillez lire Data Clustering: 50 ans après K-means

Il existe une pléthore d'autres algorithmes de clustering qui utilisent des métriques autres qu'Euclidean. Le cas le plus général que je connaisse concerne l’utilisation des divergences de Bregman pour le regroupement, dont Euclidean est un cas spécial.

utilisateur1669710
la source
"métriques autres qu'Euclidienne" Je pourrais être un peu plus pédant, mais ces divergences ne sont pas des métriques, en général :)
mic
vrai :); Je devrais probablement éditer la réponse.
user1669710
8

Comme c'est apparemment maintenant une question canonique, et cela n'a pas encore été mentionné ici:

Une extension naturelle de k-moyen pour utiliser des métriques de distance autres que la distance euclidienne standard sur consiste à utiliser l' astuce du noyau . Cela fait référence à l'idée de mapper implicitement les entrées vers un espace de Hilbert aux dimensions élevées ou infinies, où les distances correspondent à la fonction de distance que nous souhaitons utiliser et où l'algorithme est exécuté. Soit une carte de caractéristiques telle que la métrique désirée puisse être écrite , nous k-means sur les points . Dans de nombreux cas, nous ne pouvons pas calculer explicitement map , mais nous pouvonsRdφ:RpHdd(x,y)=φ(x)φ(y)H{φ(xi)}φcalcule le noyau . Toutes les mesures de distance ne correspondent pas à ce modèle, mais bon nombre d'entre elles, et de telles fonctions sont définies sur des chaînes, des graphiques, des images, des distributions de probabilité, etc.k(x,y)=φ(x),φ(y)H

Dans cette situation, dans l'algorithme k-means standard (Lloyd's), nous pouvons facilement attribuer des points à leurs grappes, mais nous représentons les centres de la grappe de manière implicite (sous forme de combinaisons linéaires des points d'entrée dans l'espace de Hilbert). Pour trouver la meilleure représentation dans l'espace de saisie, il faudrait trouver une moyenne de Fréchet , ce qui est assez coûteux. Il est donc facile d’obtenir des assignations de grappes avec un noyau, mais plus difficile d’obtenir les moyens.

L'article suivant décrit cet algorithme et le relie au clustering spectral:

I. Dhillon, Y. Guan et B. Kulis. Noyau k-means, clustering spectral et coupes normalisées. KDD 2005.

Dougal
la source
Je ne comprends pas comment l'astuce du noyau peut être utilisée avec l'algorithme de Lloyd. Il me semble que pour calculer un centroïde (même implicitement dans l'espace de Hilbert), nous allons avoir besoin de la carte explicite (x_i)? Pour attribuer des points à des clusters, nous n’avons besoin que du noyau, mais pour recalculer les centroïdes, nous ne pouvons pas nous en tenir au noyau, car le centroïde est la moyenne du {φ (x_i)} attribué à ce cluster. Est-ce que je manque quelque chose?
user2428107
Vous avez raison, nous ne pouvons pas calculer explicitement les centroïdes. Mais nous pouvons les représenter simplement comme , et calculer les distances à un point comme . 1nijCiφ(xj)xφ(x)1nijCiφ(xj)2=k(x,x)+1ni2j,jk(xj,xj)2nijk(x,xj)
Dougal
5

J'ai lu de nombreux commentaires intéressants ici, mais permettez-moi d'ajouter que l'implémentation "personnelle" de k-means de Matlab prend en charge 4 distances non euclidiennes [entre les points de données et les centres de grappes]. Le seul commentaire de la documentation que je peux voir à ce sujet est:

Mesure de distance, dans l'espace p-dimensionnel, utilisée pour la minimisation, spécifiée comme la paire séparée par des virgules, composée de "Distance" et d'une chaîne.

kmeans calcule les groupes de centroïdes différemment pour les différentes mesures de distance prises en charge. Ce tableau récapitule les mesures de distance disponibles. Dans les formules, x est une observation (c'est-à-dire une ligne de X) et c est un centroïde (un vecteur de ligne).

Ensuite, une liste de fonctions de cet xsuit. Ainsi, étant donné que pc'est la dimensionnalité des données d'entrée, il semble qu'aucune incorporation euclidienne n'est effectuée auparavant.

BTW dans le passé, j'utilisais le k-moyennes de Matlab avec la distance de corrélation et il (sans surprise) a fait ce qu'il était censé faire.

Francesco Napolitano
la source
2
Notez que les distances non euclidiennes prises en charge sont cosine(qui est juste la distance euclidienne sur les points d’entrée normalisés), correlation(euclidienne sur les entrées normalisées), cityblock( , auquel cas la médiane est utilisée plutôt que la moyenne) et (qui est juste pour les entrées binaires). L1hammingcityblock
Dougal
@Dougal, comment la médiane est-elle intégrée dans l'algorithme? Cela ne change-t-il pas k- signifie un algo fondamentalement différent?
ttnphns
1
Notez également que pour les données binaires "distance de Hamming" = cityblock = distance euclidienne.
ttnphns
1
@ttnphns Oui, ce n'est certainement plus k-means, mais il a exactement la même structure, sauf qu'au lieu de calculer les centroïdes, cela signifie que vous calculez une médiane. Et oui sur les entrées binaires hamming , mais Matlab utilise la médiane à la place de la moyenne. =L22=L1
Dougal
1
@Dougal, Notez que la procédure matlab liée à dit de diverses distances entre un point de données et le centre du cluster; ce qui n’est pas la même chose que les types de distances par paires.
mardi
2

À partir d' ici :

entrez la description de l'image ici

Considérons deux documents A et B représentés par les vecteurs de la figure ci-dessus. Le cosinus traite les deux vecteurs comme des vecteurs unitaires en les normalisant, ce qui vous donne une mesure de l'angle entre les deux vecteurs. Il fournit une mesure précise de la similarité mais sans égard à la magnitude. Mais la magnitude est un facteur important tout en tenant compte de la similarité.

DL Dahly
la source
C'est une réponse générale. Cela n'explique pas pourquoi dans k-signifie qu'il n'y a pas de similarité cosinus. Par exemple, dans le classement hiérarchique, il est largement utilisé
curieux
3
@DLDahly: Parfois, la magnitude est importante, parfois c'est le bruit. Cela dépend du domaine de recherche et est une question de normalisation des données.
Le