k-medoids

k-medoids es un algoritmo de agrupamiento (del inglés clustering) relacionado con los algoritmos k-means y medoidshift.

Tanto el k-medoids como el k-means son algoritmos que trabajan con particiones (dividiendo el conjunto de datos en grupos) y ambos intentan minimizar la distancia entre puntos que se añadirían a un grupo y otro punto designado como el centro de ese grupo. En contraste con el algoritmo k-means, k-medoids escoge datapoints como centros y trabaja con una métrica arbitraria de distancias entre datapoints en vez de usar la norma $l_{2}$. En 1987 se propuso este método para el trabajo con la norma $l_{1}$ y otras distancias.

K-medoid es una técnica clásica de particionado de grupos que divide los datos conformados por n objetos en k grupos (con k conocido de antemano).

Es más robusto ante el ruido y a partes aisladas que k-means porque minimiza una suma de disimilaridades (entre pares de puntos) en vez de una suma de distancias euclidianas cuadradas.

Un medoid puede ser definido como el objeto de un grupo cuya disimilaridad media a todos los objetos en el grupo es mínima. Es el punto ubicado más hacia el centro en todo el grupo.

Algoritmos

La aplicación práctica más común de k-medoids es el algoritmo Partición Alrededor de Medoids (PAM). PAM utiliza una búsqueda golosa que puede no encontrar la solución óptima, pero es más rápido que la búsqueda exhaustiva.Trabaja como sigue:

1. Inicialización: seleccionar k de los n puntos como el medoid.
2. Asociar cada punto al medoid más cercano.
3. Mientras el costo de la configuración disminuya:
   1. Para cada medoid m, para cada no medoid o:
      1. Intercambiar m y o, recalcular el costo (suma de la distancia de los puntos a sus medoids).
      2. Si el costo total de la configuración aumentó en el paso anterior, deshacer el intercambio.

Otros algoritmos han sido sugeridos en la literatura, incluyendo el siguiente método de Iteración Voronoi:

1. Seleccionar los medoids iniciales.
2. Iterar mientras el costo disminuya:
   1. En cada grupo, marcar como medoid el punto que minimiza la suma de distancias dentro del grupo.
   2. Reasignar cada punto al grupo definido por el medoid más cercano determinado en el paso anterior.

Demostración de PAM

Agrupar el siguiente conjunto de datos de diez objetos en dos grupos (k = 2).

Considera el siguiente conjunto de datos:

Figura 1.1 - distribución de los datos.

X1	2	6
X2	3	4
X3	3	8
X4	4	7
X5	6	2
X6	6	4
X7	7	3
X8	7	4
X9	8	5
X10	7	6

Paso 1

Figura 1.2 - grupos después del paso 1.

Inicializar k centros.

Asumir x2 y x8 está marcados como medoids, así que los centros son c1 = (3,4) y c2 = (7,4).

Calcular distancias a cada centro para asociar cada objeto a su medoid más cercano. El costo está calculado utilizando distancia de Manhattan. Costos al medoid más cercano están mostrados en negrita en la tabla.

Costo (distancia) a c1
i	c1		Objetos (Xi)		Costo (distancia)
1	3	4	2	6	3
3	3	4	3	8	4
4	3	4	4	7	4
5	3	4	6	2	5
6	3	4	6	4	3
7	3	4	7	3	5
9	3	4	8	5	6
10	3	4	7	6	6

Costo (distancia) a c2
i	c2		Objetos (Xi)		Costo (distancia)
1	7	4	2	6	7
3	7	4	3	8	8
4	7	4	4	7	6
5	7	4	6	2	3
6	7	4	6	4	1
7	7	4	7	3	1
9	7	4	8	5	2
10	7	4	7	6	2

Entonces los grupos serían:

Cluster₁ = {(3,4)(2,6)(3,8)(4,7)}

Cluster₂ = {(7,4)(6,2)(6,4)(7,3)(8,5)(7,6)}

Dado que los puntos (2,6) (3,8) y (4,7) son más cercanos a c1, por ello forman un grupo, mientras que los demás puntos forman otro grupo.

Así que el costo total implicado es 20.

Donde el costo entre cualesquier dos puntos se ha calculado utilizando la fórmula:

$costo(x,c)=\sum _{k=1}^{d}|x_{i}-c_{i}|$

donde x es cualquier objeto, c es el medoid, y d es la dimensión del objeto, en este caso 2.

El costo total es la suma de los costos de los objetos a su medoid en el grupo, siendo:

$${\begin{alignedat}{5}costo\ total&=\{costo((3,4),(2,6))+costo((3,4),(3,8))+costo((3,4),(4,7))\}\\&+\{costo((7,4),(6,2))+costo((7,4),(6,4))+costo((7,4),(7,3))+costo((7,4),(8,5))\\&+costo((7,4),(7,6))\}\\costo\ total&=(3+4+4)+(3+1+1+2+2)\\costo\ total&=20\end{alignedat}}$$

Paso 2

Figura 1.3 - grupos después del paso 2.

Selecciona uno de los no medoids O'.

Asumimos O′ = (7,3).

Ahora los medoids son c1(3,4) y O′(7,3).

Si c1 y O′ son nuevo medoids, calcular el coste total implicado.

Utilizando la fórmula del paso 1.

i	c1		Objetos (Xi)		Costo (distancia)
1	3	4	2	6	3
3	3	4	3	8	4
4	3	4	4	7	4
5	3	4	6	2	5
6	3	4	6	4	3
8	3	4	7	4	4
9	3	4	8	5	6
10	3	4	7	6	6

i	O′		Objetos (Xi)		Costo (distancia)
1	7	3	2	6	8
3	7	3	3	8	9
4	7	3	4	7	7
5	7	3	6	2	2
6	7	3	6	4	2
8	7	3	7	4	1
9	7	3	8	5	3
10	7	3	7	6	3

Figura 2. K-medoids versus k-Medios. Figs 2.1a-2.1f presenta un ejemplo típico de la convergencia de k-means a un mínimo local. Este resultado de k-means contradice la estructura de grupo obvia del conjunto de datos. En este ejemplo, el algoritmo k-medoids (Figs 2.2a-2.2h) con la misma posición inicial de medoids (Fig. 2.2a) converge a la estructura de grupo obvia. Los círculos más pequeños son objetos, las cuatro estrellas de rayo son centroids (medias), las nueve estrellas de rayo son medoids.​

${\begin{aligned}costo\ total&=3+4+4+2+2+1+3+3\\costo\ total&=22\end{aligned}}$

Siendo el costo del intercambio de medoids de c2 a O′:

$${\begin{aligned}S&=costo\ total\ actual-costo\ total\ pasado\\&=22-20\\&=2>0\end{aligned}}$$

De manera que cambiar a O′ sería una idea mala, así que la elección anterior estaba bien. Así que probamos con otros no-medoids y encontrados que nuestra primera elección era la mejor. Así que la configuración no cambia y el algoritmo termina aquí (ya que no hay ningún cambio en los medoids).

Puede pasar que algunos puntos de datos pueden cambiar de un grupo a otro en dependencia de su cercanía a los medoids.

En algunas situaciones estándares, k-medoids demuestra rendimiento mejor que k-means. Un ejemplo se presenta en la Fig. 2. La parte más costosa del algoritmo es el cálculo de las distancias entre los puntos u objetos. Si fuera aplicable un preprocesamiento cuadrático y el almacenamiento, la matriz de distancias puede ser precalculada para conseguir una mayor rapidez. Existen ejemplos, donde los autores también introducen una heurística para escoger los k medoids iniciales.​

Software

• ELKI Incluye algunas variantes de k-means, incluyendo un k-medoids basado en EM y el algoritmo PAM original.
• Julia contiene una implementación de k-medoid en el paquete JuliaStats clustering.
• KNIME Incluye una implementación de k-medoids que brinda una variedad de medidas eficades de distancias matriciales, así como un número de implementaciones nativas (e integradas) de k-means.
• R Incluye variantes de k-means en el paquete "flexclust" y PAM está implementado en el paquete "cluster".
• RapidMiner Tiene un operador llamado KMedoids, pero no implementa el algoritmo k-medoids correctamente. En cambio, es una variante de k-means, que sustituye la media con el punto u objeto más cercano (que no es el medoid).
• MATLAB Implementa PAM, CLARA, y otros dos algoritmos para resolver el problema de agrupamiento k-medoids.

Referencias

• Datos: Q3191282