Agrupamiento k -medianas

El agrupamiento k-medianas es una técnica de partición utilizada en el análisis de clústeres. ^{[ 1 ]} Agrupa los datos en k clústeres minimizando la suma de las distancias —normalmente utilizando la distancia de Manhattan (L1)— entre los puntos de datos y la mediana de sus clústeres asignados. Este método es especialmente robusto frente a valores atípicos y es muy adecuado para datos discretos o categóricos. Es una generalización del algoritmo de la mediana geométrica o 1-mediana, definido para un único clúster. k -medianas es una variación del agrupamiento k -medias donde, en lugar de calcular la media para cada clúster para determinar su centroide , se calcula la mediana . Esto tiene el efecto de minimizar el error en todos los clústeres con respecto a la métrica de distancia de norma 1 , a diferencia de la métrica de distancia de norma 2 al cuadrado (que utiliza k -medias).

Esto se relaciona directamente con el problema de la k -mediana : dado un espacio métrico${\displaystyle (V,d)}$y un número entero${\displaystyle k}$El problema pide encontrar un conjunto de k centros.${\displaystyle C\subsetequ V}$para minimizar la suma de las distancias desde cada elemento en${\displaystyle V}$al centro más cercano, es decir, queremos minimizar

${\displaystyle \sum _{u\in V}\min _{v\in C}d(u,v)}$

La función de criterio formulada de esta manera a veces resulta ser un mejor criterio que el utilizado en el algoritmo de agrupamiento k -means , en el que se emplea la suma de las distancias al cuadrado. La suma de distancias se utiliza ampliamente en aplicaciones como el problema de localización de instalaciones .

El algoritmo propuesto utiliza una iteración al estilo Lloyd que alterna entre un paso de expectativa (E) y uno de maximización (M), lo que lo convierte en un algoritmo de expectativa-maximización . En el paso E, a todos los objetos se les asigna su mediana más cercana. En el paso M, las medianas se recalculan utilizando la mediana en cada dimensión.

En la formulación de distancia de Manhattan del problema de las k -medianas, la mediana se calcula en cada dimensión , por lo que los atributos individuales provienen del conjunto de datos (o son el promedio de dos valores del conjunto). Esto hace que el algoritmo sea más fiable para conjuntos de datos discretos o incluso binarios . En cambio, el uso de medias o medianas de distancia euclidiana no garantiza necesariamente la obtención de atributos individuales del conjunto de datos. Incluso con la formulación de distancia de Manhattan, los atributos individuales pueden provenir de diferentes instancias del conjunto de datos; por lo tanto, la mediana resultante puede no pertenecer al conjunto de datos de entrada.

Este algoritmo suele confundirse con el algoritmo de k -medoides . Sin embargo, un medoide debe ser una instancia real del conjunto de datos, mientras que para la mediana de distancia de Manhattan multivariada esto solo se cumple para valores de atributos individuales. Por lo tanto, la mediana real puede ser una combinación de múltiples instancias. Por ejemplo, dados los vectores (0,1), (1,0) y (2,2), la mediana de distancia de Manhattan es (1,1), que no existe en los datos originales y, por lo tanto, no puede ser un medoide.

El agrupamiento k-medianas está estrechamente relacionado con otras técnicas de agrupamiento particional como k-medias y k-medoides , diferenciándose principalmente en cómo se determinan los centros de los clústeres y el tipo de métrica de distancia empleada. Estas diferencias dan lugar a comportamientos distintos en cuanto a robustez, coste computacional y aplicabilidad a diversas distribuciones de datos. El algoritmo k-medias minimiza la suma de las distancias euclidianas al cuadrado entre los puntos de datos y la media (centroide) de su clúster correspondiente. Utiliza la media aritmética como representante del clúster, lo que lo hace sensible a los valores atípicos y al ruido, ya que la media puede verse fuertemente influenciada por valores extremos. En cambio, k-medianas minimiza la suma de las diferencias absolutas (normalmente utilizando la distancia de Manhattan/L1), seleccionando la mediana a lo largo de cada dimensión como centro del clúster. Debido a que la mediana es resistente a los valores extremos, k-medianas suele ser más robusto en presencia de valores atípicos. El algoritmo k-medoides también enfatiza la robustez, pero en lugar de usar medianas o medias calculadas, selecciona puntos de datos reales (medoides) como centros de clúster. ^{[ 2 ]} Esto hace que k-medoides sea particularmente adecuado para datos no euclidianos o categóricos. Sin embargo, debido a que implica evaluar disimilitudes por pares y buscar repetidamente puntos representativos, tiende a ser computacionalmente más intensivo que k-medias y k-medianas, especialmente en conjuntos de datos grandes.

• ELKI incluye varias variantes de k-medias, incluidas las k-medianas.
• FORTRAN kmedians
• GNU R incluye la función k-medianas en el paquete "flexclust".
• kmedianos de Stata

• Análisis de clúster
• k -medias
• Medoid
• Silueta