machine-learning - que - algoritmos de agrupamiento clustering

¿Qué hace que la medida de distancia en k-medoid sea "mejor" que k-means?

Question

Estoy leyendo sobre la diferencia entre la agrupación k-means y la agrupación k-medoid.

Supuestamente hay una ventaja al usar la medida de distancia pairwise en el algoritmo k-medoid, en lugar de la suma más familiar de la métrica euclidiana de tipo de distancia cuadrada para evaluar la varianza que encontramos con k-means. Y aparentemente esta diferente métrica de distancia de alguna manera reduce el ruido y los valores atípicos.

He visto este reclamo, pero todavía no he visto ningún buen razonamiento en cuanto a las matemáticas detrás de este reclamo.

¿Qué hace que la medida de distancia pairwise comúnmente utilizada en k-medoid sea mejor? Más exactamente, ¿cómo la falta de un término cuadrado permite a los k-medoides tener las propiedades deseables asociadas con el concepto de tomar una mediana?

Answer 1

1. K-medoid es más flexible

En primer lugar, puedes usar k-medoids con cualquier medida de similitud. Sin embargo, K-means puede no converger, solo debe usarse con distancias que sean consistentes con la media . Entonces, por ejemplo, la Correlación Absoluta de Pearson no debe usarse con k-means, pero funciona bien con k-medoids.

2. Robustez de Medoid

En segundo lugar, el medoide utilizado por k-medoides es más o menos comparable a la mediana (de hecho, también hay k-medianas, que es como K-means, pero para la distancia de Manhattan). Si busca literatura sobre la mediana, verá muchas explicaciones y ejemplos de por qué la mediana es más robusta a los valores atípicos que la media aritmética . Esencialmente, estas explicaciones y ejemplos también se aplicarán al medoide. Es una estimación más robusta de un punto representativo que la media utilizada en k-means.

Considere este ejemplo de 1 dimensión:

1 2 3 4 100000

Tanto la mediana como el medoide de este conjunto son 3 . La media es 20002.

¿Cuál crees que es más representativo del conjunto de datos? La media tiene el error cuadrado más bajo, pero suponiendo que puede haber un error de medición en este conjunto de datos ...

Técnicamente, la noción de punto de ruptura se utiliza en las estadísticas. La mediana tiene un punto de ruptura del 50% (es decir, la mitad de los puntos de datos puede ser incorrecta y el resultado no se ve afectado), mientras que la media tiene un punto de ruptura de 0 (es decir, una sola observación grande puede dar una mala estimación).

No tengo una prueba, pero supongo que el medoide tendrá un punto de ruptura similar a la mediana.

3. k-medoids es mucho más caro

Esa es la principal desventaja. Por lo general, PAM tarda mucho más en ejecutarse que k-means. Como se trata de calcular todas las distancias por pares, es O(n^2*k*i) ; mientras que k-medias se ejecuta en O(n*k*i) donde normalmente, k veces el número de iteraciones es k*i << n .

Answer 2

Creo que esto tiene que ver con la selección del centro para el clúster. k-means seleccionará el "centro" del clúster, mientras que k-medoid seleccionará el miembro "más centrado" del clúster. En un clúster con valores atípicos (es decir, puntos muy alejados de los otros miembros del clúster) k-means colocará el centro del clúster hacia los valores atípicos, mientras que k-medoid seleccionará uno de los miembros más agrupados (el medoide) como centrar.

Ahora depende de para qué uses la agrupación. Si solo quisieras clasificar un grupo de objetos, entonces realmente no te importa dónde está el centro; pero si el agrupamiento se usó para entrenar a un decisor que ahora clasificará nuevos objetos basados ​​en esos puntos centrales, entonces k-medoid le dará un centro más cercano a donde un humano colocaría el centro.

En palabras de wikipedia:

"Es [k-medoid] más robusto que el ruido y los valores atípicos en comparación con k-means, ya que minimiza una suma de desemejanzas pairwise en lugar de una suma de distancias euclidianas al cuadrado".

Aquí hay un ejemplo:

Supongamos que desea agrupar en una dimensión con k = 2. Un grupo tiene la mayoría de sus miembros alrededor de 1000 y el otro alrededor de -1000; pero hay un valor atípico (o ruido) en 100000. Obviamente, pertenece al grupo alrededor de 1000, pero k-means alejará el punto central de 1000 y hacia 100000. Esto incluso puede hacer que algunos de los miembros del grupo 1000 (por ejemplo) un miembro con valor 500) para ser asignado al cluster -1000. k-medoid seleccionará uno de los miembros alrededor de 1000 como el medoide, probablemente seleccionará uno que sea más grande que 1000, pero no seleccionará un valor atípico.

Answer 3

Solo una pequeña nota añadida a la respuesta de @ Eli, K-medoid es más robusto al ruido y atípicos que k-means porque este último selecciona el centro del cluster, que en su mayoría es solo un "punto de virtud", por otro lado el primero elige el "objeto real" del clúster.

Supongamos que tiene cinco puntos 2D en un grupo con las coordenadas de (1,1), (1,2), (2,1), (2,2) y (100,100). Si no consideramos los intercambios de objeto entre los grupos, con k-means obtendrá el centro del grupo (21.2,21.2) que está bastante distraído por el punto (100,100). Sin embargo, con k-medoid se elegirá el centro entre (1,1), (1,2), (2,1) y (2,2) de acuerdo con su algoritmo.

Aquí hay un applet divertido ( EM Mirkes, K-means y K-medoids applet. University of Leicester, 2011 ) que puede generar aleatoriamente conjunto de datos en el plano 2D y comparar k-medoid y k-means proceso de aprendizaje.