Utilisation de k-means avec d'autres mesures

Je me rends donc compte que cela a déjà été demandé: par exemple, quels sont les cas d'utilisation liés à l'analyse de cluster de différentes métriques de distance? mais j'ai trouvé les réponses quelque peu contradictoires avec ce qui est suggéré devrait être possible dans la littérature.

Récemment, j'ai lu deux articles qui mentionnent l'utilisation de l'algorithme kmeans avec d'autres mesures, par exemple pour éditer la distance entre les chaînes et la "Earth Mover Distance" entre les distributions. Étant donné que ces articles mentionnent l'utilisation de kmeans avec d'autres métriques sans préciser comment , en particulier lorsqu'il s'agit de calculer la moyenne d'un ensemble de points, cela me suggère qu'il existe peut-être une méthode "standard" pour traiter cela que je ne choisis tout simplement pas sur.

Prenons par exemple cet article , qui donne une implémentation plus rapide de l'algorithme k-means. Citant le paragraphe 4 de l'introduction, l'auteur dit que son algorithme "peut être utilisé avec n'importe quelle métrique de distance de boîte noire", et dans le paragraphe suivant, il mentionne la modification de la distance comme exemple spécifique. Cependant, son algorithme calcule toujours la moyenne d'un ensemble de points et ne mentionne pas comment cela pourrait affecter les résultats avec d'autres mesures (je suis particulièrement perplexe quant à la façon dont la moyenne fonctionnerait avec la distance d'édition).

Cet autre article décrit l'utilisation de k-means pour regrouper les mains de poker pour une abstraction texas hold-em. Si vous passez à la page 2 en bas de la colonne de gauche, l'écriture de l'auteur "puis k-means est utilisée pour calculer une abstraction avec le nombre souhaité de clusters en utilisant la distance Earth Mover entre chaque paire d'histogrammes comme mesure de distance".

Je ne cherche pas vraiment quelqu'un pour m'expliquer ces articles, mais manque-t-il une méthode standard pour utiliser k-means avec d'autres mesures? La moyenne standard avec la distance du moteur de terre semble pouvoir fonctionner heuristiquement, mais la distance d'édition semble ne pas du tout correspondre au moule. J'apprécie toute idée que quelqu'un pourrait donner.

(modifier) : Je suis allé de l'avant et j'ai essayé k-means sur des histogrammes de distribution en utilisant la distance du moteur de terre (similaire à ce qui est dans le papier de poker) et cela semblait avoir bien fonctionné, les clusters qu'il produisait semblaient assez bons pour mon cas d'utilisation. Pour la moyenne, je viens de traiter les histogrammes comme des vecteurs et de faire la moyenne de la manière normale. La seule chose que j'ai remarquée, c'est que la somme sur tous les points des distances aux moyennes n'a pas toujours diminué de manière monotone. Dans la pratique cependant, il s'installerait sur un min local dans les 10 itérations malgré les problèmes monotones. Je vais supposer que c'est ce qu'ils ont fait dans le deuxième article, la seule question qui reste alors est, comment diable feriez-vous la moyenne lorsque vous utilisez quelque chose comme la distance d'édition?

Ce n'est pas comme si k-means exploserait nécessairement et échouerait si vous utilisez une métrique différente.

Dans de nombreux cas, il retournera un résultat . Il n'est tout simplement pas garanti qu'il trouve les centroïdes ou les partitions optimaux avec d'autres mesures, car la moyenne peut ne pas convenir pour minimiser les distances.

Considérez la distance des moteurs de la Terre. Étant donné les trois vecteurs

3 0 0 0 0
0 0 3 0 0
0 0 0 0 3

La moyenne arithmétique est

1 0 1 0 1

qui a des distances EMD 6, 4, 6 (total 16). Si l'algorithme avait plutôt utilisé

0 0 3 0 0

les distances EMD auraient été de 6, 0, 6; c'est-à-dire mieux (total 12).

La moyenne arithmétique ne minimise pas l'EMD, et le résultat de l'utilisation des k-moyennes (avec la moyenne artihmétique) ne donnera pas des représentants optimaux.

Des choses similaires seront valables pour les distances d'édition.

K-means est approprié à utiliser en combinaison avec la distance euclidienne car l' objectif principal de k-means est de minimiser la somme des variances intra-cluster , et la variance intra-cluster est calculée exactement de la même manière que la somme d'Euclidean distances entre tous les points de l'amas au centre de gravité de l'amas. Comme le soulignent d' autres réponses , l'algorithme n'est garanti de converger (même si au minimum local) que si l'étape de mise à jour du centroïde et l'étape de réaffectation des points de données sont effectuées dans le même espace euclidien à n dimensions .

De plus, il a été démontré (et je mets un lien ici parce que je ne peux pas l'expliquer moi-même) que la moyenne est le meilleur estimateur à utiliser lorsqu'il faut minimiser la variance totale . Donc, k-means lié à la distance euclidienne est double: l'algorithme doit avoir un moyen de calculer la moyenne d'un ensemble de points de données (d'où le nom k- means ), mais cette moyenne n'a de sens et garantit la convergence de la processus de regroupement si la distance euclidienne est utilisée pour réaffecter des points de données aux centroïdes les plus proches.

Vous pouvez toujours utiliser k-means avec d'autres mesures de distance, comme dans cet article , dans lequel l'auteur utilise l'algorithme avec la distance de Minkowski, qui est une généralisation des distances de Manhattan, Euclidienne et Chebyshev. Cependant, dans ces cas, la convergence n'est pas garantie et, par conséquent, vous pouvez vous attendre à ce que les futures itérations de l'algorithme présentent en fait une variance totale plus grande que les itérations précédentes.

Même ainsi, comme le montre l'article ci-dessus, même sans garantie de convergence, les k-moyennes peuvent obtenir de meilleurs résultats de regroupement dans certains scénarios en utilisant d'autres mesures de distance. Si vous prenez les normes , par exemple, et sachant que la distance euclidienne est la norme et que la distance Manhattan est la norme , il a été montré que, pour les matrices de distance clairsemées, k-means utilisé en conjonction avec une norme avec atteint une plus grande précision de regroupement que lors de l'utilisation de la distance euclidienne.$L^p$$L^2$$L^1$$L^p$$0 < p \leq 1$

Enfin, je pense qu'il est intéressant de souligner qu'il existe certaines mesures de similitude qui peuvent d'une certaine manière être converties en distance euclidienne, de telle manière que si vous utilisez ladite mesure de similitude en conjonction avec k-means, vous devriez obtenir des résultats similaires. Un exemple de cela est la similitude cosinus .

Je ne sais pas si c'est ce que font les articles liés, mais il est possible de faire k-means avec des fonctions de distance non euclidiennes en utilisant l' astuce du noyau . Autrement dit, nous mappons implicitement les entrées dans un espace de haute dimension (souvent de dimension infinie) où les distances euclidiennes correspondent à la fonction de distance que nous voulons utiliser, et y exécutons l'algorithme. Pour l'algorithme k-means de Lloyd en particulier, nous pouvons facilement attribuer des points à leurs grappes, mais nous représentons implicitement les centres des grappes et trouver leur représentation dans l'espace d'entrée nécessiterait de trouver une moyenne de Fréchet . L'article suivant traite de l'algorithme et le relie au clustering spectral:

I. Dhillon, Y. Guan et B. Kulis. K-means du noyau, regroupement spectral et coupes normalisées. KDD 2005.

Il existe des noyaux basés sur la distance de montage et basés sur la distance du déménageur .