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

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.]

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 .

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.

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.

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 pouvons$\mathbb R^d$$\varphi : \mathbb R^p \to \mathcal H$$d$$d(x, y) = \lVert \varphi(x) - \varphi(y) \rVert_{\mathcal H}$$\{ \varphi(x_i) \}$$\varphi$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) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal 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.

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.

À partir d' 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é.