Ce qui rend la mesure de la distance de k-medoid “meilleures” que les k-means?
Je lis à propos de la différence entre le clustering k-means et k-medoid de clustering.
Soi-disant il y a un avantage à utiliser les combinaisons mesure de la distance dans le k-medoid algorithme, au lieu de la plus familière somme des carrés de la distance Euclidienne de type métrique pour évaluer la variance que nous trouvons avec k-means. Et apparemment, cette différence de distance métrique en quelque sorte réduit le bruit et les valeurs aberrantes.
J'ai vu cette demande, mais je n'ai pas encore vu tout bon raisonnement que pour les mathématiques derrière cette revendication.
Ce qui rend le paires distance de mesure couramment utilisée dans k-medoid mieux? 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?
- stats.stackexchange.com peut être le meilleur endroit pour obtenir de plus profond et théoriques des réponses.
- Voir ma réponse mis à jour, pour la notion de répartition point à partir de statistiques robustes. Le medoid est probablement un robuste statistique, la moyenne n'est pas du tout robuste.
Vous devez vous connecter pour publier un commentaire.
1. K-medoid est plus souple
Tout d'abord, vous pouvez utiliser k-medoids avec tout mesure de similarité. K-means cependant, peut ne pas converger, il doit vraiment être utilisé uniquement avec les distances qui sont compatibles avec les dire. Si par exemple Absolu de Corrélation de Pearson ne doit pas être utilisé avec les k-means, mais il fonctionne bien avec k-medoids.
2. La robustesse de medoid
Deuxièmement, la medoid utilisé par k-medoids est à peu près comparable à la médiane (en fait, il y a aussi k-médianes, qui est comme K-means, mais pour la distance de Manhattan). Si vous regardez en haut de la littérature sur la médiane, vous verrez de nombreux exemples et explications pourquoi la médiane est plus robuste aux valeurs aberrantes que la moyenne arithmétique. Essentiellement, ces explications et exemples sera également valable pour la medoid. C'est un plus robuste estimation d'un point représentatif de la moyenne comme utilisé dans les k-means.
Considérer cette dimension 1 exemple:
De la médiane et medoid de cet ensemble sont 3. La moyenne est 20002.
Qui pensez-vous est le plus représentatif de l'ensemble de données? La moyenne est la plus faible erreur quadratique, mais en supposant qu'il pourrait y avoir une erreur de mesure dans cet ensemble de données ...
Techniquement, la notion de répartition point de est utilisée dans les statistiques. La médiane est une répartition de 50% (soit la moitié des points de données peuvent être erronées, et le résultat est pas encore atteint), alors que la moyenne a une panne de 0 (c'est à dire un seul gros observation peut donner une mauvaise estimation).
Je n'ai pas de preuve, mais je suppose que le medoid a la même répartition que pour la médiane.
3. k-medoids est beaucoup plus cher
C'est le principal inconvénient. Habituellement, le PAM prend beaucoup plus de temps que k-means. Comme il faut calculer toutes les distances, il est
O(n^2*k*i); considérant que k-means s'exécute dansO(n*k*i)où, généralement, k fois le nombre d'itérations estk*i << n.0,1,2,3,100000000. Comparer la moyenne et la médiane, qui est plus robuste?delta, cela n'affectera pas la medoid beaucoup, tout comme la médiane; parce que tous les autres candidats sont affectés de la même manière.Je pense que cela a à voir avec la sélection du centre pour le cluster. k-means permettra de sélectionner le "centre" du cluster, alors que k-medoid permettra de sélectionner les plus "centré" membre de la grappe.
Dans un cluster avec les valeurs aberrantes (c'est à dire des points loin de la d'autres membres du cluster) k-means place le centre de l'amas vers les valeurs aberrantes, tandis que k-medoid choisira l'un des plus en cluster membres (le medoid) comme le centre.
Cela dépend maintenant de ce que vous utilisez le clustering pour. Si tu voulais juste faire classer un ensemble d'objets, alors vous ne pouvez pas vraiment se soucier de, où le centre est; mais si le regroupement a été utilisé pour former un décideur qui va classer les nouveaux objets en se basant sur les points de centre, alors k-medoid vous donnera un centre de plus près à l'endroit où un homme aurait lieu de le centre.
Dans le wikipedia de mots:
"Il [k-medoid] est plus robuste au bruit et les valeurs aberrantes par rapport à k-means, car il minimise une somme de paires de différences au lieu d'une somme des carrés des distances Euclidiennes."
Voici un exemple:
Supposons que vous voulez de cluster sur une dimension avec k=2. Un cluster de la plupart de ses membres autour de l'an 1000 et l'autre autour de -1000; mais il est une valeur aberrante (ou bruit) à 100000.
Il est évident qu'elle appartient au cluster autour de 1000, mais k-means place le point central loin de 1000 et vers 100000. Cela peut même faire partie des membres de l'1000 cluster (dire à un membre de la valeur de 500) qui sera affecté à la -1000 cluster.
k-medoid choisira l'un des membres autour de 1000, comme le medoid, il sera probablement de choisir celui qui est plus grand que 1000, mais il ne sera pas sélectionner 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 point", 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 l'on ne considère pas l'objet d'échanges entre les clusters, avec k-means, vous obtiendrez le centre de cluster (21.2,21.2) ce qui est assez distrait par le point (100,100). Cependant, avec le k-medoid sera de choisir le centre de parmi les (1,1),(1,2),(2,1),et (2,2) en fonction de son algorithme.
Ici est un plaisir de l'applet ( E. M. Mirkes, K-means et K-medoids applet. L'université de Leicester, 2011 ) que vous pouvez générer aléatoirement base de données dans le plan 2D et comparez k-medoid et k-means processus d'apprentissage.