En quoi la distance mesurée dans k-medoid est-elle "meilleure" que k-means?
je suis en train de lire à propos de la différence entre le regroupement k-means et le regroupement k-medoid.
supposément il y a un avantage à utiliser la mesure de distance par paires dans l'algorithme K-medoid, au lieu de la somme plus familière de la métrique de type euclidienne de distance pour évaluer la variance que nous trouvons avec les k-means. Et apparemment cette métrique de distance différente réduit en quelque sorte le bruit et les valeurs aberrantes.
j'ai vu cette demande, mais je n'ai pas encore vu tout bon raisonnement comme pour les mathématiques derrière cette revendication.
Qu'est-ce qui rend la mesure de distance par paires couramment utilisée dans le K-medoid meilleure? Plus exactement, comment l'absence d'un terme au carré permettent de k-medoids avoir les propriétés associées à la notion de prendre une médiane?
3 réponses
1. K-medoid est plus flexible
tout d'Abord, vous pouvez utiliser k-medoids mesure de similarité. K-means cependant, peut ne pas converger, il doit vraiment être utilisé uniquement avec les distances qui sont compatibles avec les moyenne. Par exemple, la corrélation absolue de Pearson ne doit pas être utilisée avec les moyennes de k, mais elle fonctionne bien avec les K-médoïdes.
2. Robustesse de medoid
deuxièmement, le médicament tel qu'il est utilisé par les K-medoids est à peu près comparable à médiane (en fait, il y a aussi k-medians, qui est comme K-means mais pour la distance de Manhattan). Si vous regardez la littérature sur la médiane, vous verrez beaucoup d'explications et d'exemples pourquoi la médiane est plus robuste aux valeurs aberrantes que la moyenne arithmétique. Essentiellement, ces explications et exemples valent aussi pour le médicament. C'est un plus solide estimation d'un point représentatif par rapport à la moyenne telle qu'elle est utilisée dans K-means.
Envisager de cet exemple 1-dimensionnel:
1 2 3 4 100000
les médianes et les médiums de cet ensemble sont 3. La moyenne est de 20002.
Qui pensez-vous est le plus représentatif de l'ensemble de données? La moyenne présente l'erreur carrée la plus faible, mais en présumant qu'il pourrait y avoir une erreur de mesure dans cet ensemble de données ...
Techniquement, la notion de point de panne est utilisé en statistique. La médiane a un point de rupture de 50% (i.e. la moitié des points de données peuvent être incorrects, et le résultat n'est toujours pas affecté), alors que la moyenne a un point de décomposition de 0 (c'est-à-dire qu'une seule grande observation peut donner une mauvaise estimation).
Je n'ai pas de preuve, mais je suppose que le médicament aura un point de rupture similaire à la médiane.
3. k-medoids est beaucoup plus cher
C'est le principal inconvénient. Habituellement, PAM prend beaucoup plus de temps à courir que k-means. Comme il s'agit de calculer toutes les distances en paires, c'est O(n^2*k*i); alors que k-means court dans O(n*k*i) où, généralement, k fois le nombre d'itérations est k*i << n.
je pense que cela a à voir avec la sélection du centre pour le cluster. k-means sélectionnera le" centre "de l'amas, tandis que k-medoid sélectionnera le membre" le plus centré " de l'amas. Dans un cluster avec des valeurs aberrantes (c'est-à-dire des points éloignés des autres membres du cluster), k-means placera le centre du cluster vers les valeurs aberrantes, tandis que k-medoid choisira l'un des membres les plus agrégés (le medoid) comme centre.
Cela dépend maintenant de ce que vous utilisez le clustering pour. Si vous vouliez juste classer un tas d'objets alors vous ne vous souciez pas vraiment de l'endroit où le centre est; mais si le clustering a été utilisé pour former un décideur qui va maintenant Classer de nouveaux objets basés sur ces points du centre, alors k-medoid vous donnera un centre plus proche de l'endroit où un humain placerait le centre.
selon les mots de wikipedia:
Voici un exemple:
supposons que vous voulez regrouper sur une dimension avec k=2. Un cluster compte la plupart de ses membres autour de 1000 et l'autre autour de -1000; mais il y a une valeur aberrante (ou bruit) à 100000. Il appartient évidemment à l'amas autour de 1000 mais k-means mettra le point central à l'écart de 1000 et vers 100000. Cela peut même faire certains des membres du cluster 1000 (disons un membre avec valeur 500) à attribuer au cluster -1000. k-medoid sélectionnera un des membres autour de 1000 comme medoid, il sélectionnera probablement un qui est plus grand que 1000, mais il ne sélectionnera pas une valeur aberrante.
Juste une petite note ajoutée à @Eli réponse, K-medoid est plus robuste au bruit et aberrantes que k-means, parce que ce dernier sélectionne le centre de l'amas, qui est principalement une "vertu", d'autre part, l'ancien choisit la "objet réel" du cluster.
Supposons que vous avez cinq points 2D dans un cluster avec les coordonnées de (1,1),(1,2),(2,1),(2,2), et (100,100). Si nous ne considérons pas les échanges d'objets entre les clusters, avec k-signifie que vous obtiendrez le centre de cluster (21.2,21.2) ce qui est assez distrait par le point (100,100). Cependant, avec k-medoid choisira le centre parmi (1,1),(1,2),(2,1),et (2,2) selon son algorithme.
Ici, c'est un plaisir de l'applet ( E. M. Mirkes, K-means and K-medoids applet. Université de Leicester, 2011) que vous pouvez générer au hasard un ensemble de données dans le plan 2D et comparer le processus d'apprentissage k-medoid et k-means.