En estadística , la agrupación de k -medianas [1] [2] es un algoritmo de análisis de conglomerados . Es una variación de la agrupación de k -medias donde, en lugar de calcular la media de cada grupo para determinar su centroide, se calcula la mediana . Esto tiene el efecto de minimizar el error en todos los grupos con respecto a la métrica de distancia de 2 normas , a diferencia de la métrica de distancia de 2 normas al cuadrado (que k -means sí).
Esto se relaciona directamente con el problema de la k -mediana , que es el problema de encontrar k centros tales que los grupos formados por ellos sean los más compactos con respecto a la norma 2. Formalmente, dado un conjunto de puntos de datos x , los k centros ci deben elegirse de manera que se minimice la suma de las distancias desde cada x al ci más cercano .
La función de criterio formulada de esta manera es a veces un criterio mejor que el utilizado en el algoritmo de agrupamiento de k -medias , en el que se utiliza la suma de las distancias al cuadrado. La suma de distancias se utiliza ampliamente en aplicaciones como el problema de ubicación de instalaciones .
El algoritmo propuesto utiliza una iteración estilo Lloyd que alterna entre un paso de expectativa (E) y de maximización (M), lo que lo convierte en un algoritmo de expectativa-maximización . En el paso E, todos los objetos se asignan a su mediana más cercana. En el paso M, las medianas se vuelven a calcular utilizando la mediana en cada dimensión.
La mediana se calcula en cada dimensión en la formulación de distancia de Manhattan del problema de k -medianas, por lo que los atributos individuales provendrán del conjunto de datos (o serán un promedio de dos valores del conjunto de datos). Esto hace que el algoritmo sea más confiable para conjuntos de datos discretos o incluso binarios . Por el contrario, el uso de medias o medianas de distancia euclidiana no necesariamente producirá atributos individuales del conjunto de datos. Incluso con la formulación de la distancia de Manhattan, los atributos individuales pueden provenir de diferentes instancias del conjunto de datos; por lo tanto, la mediana resultante puede no ser miembro del conjunto de datos de entrada.
Este algoritmo a menudo se confunde con el algoritmo k -medoides . Sin embargo, un medoide tiene que ser una instancia real del conjunto de datos, mientras que para la mediana multivariada de distancia de Manhattan esto solo es válido para valores de atributo único. Por tanto, la mediana real puede ser una combinación de múltiples casos. Por ejemplo, dados los vectores (0,1), (1,0) y (2,2), la mediana de la distancia de Manhattan es (1,1), que no existe en los datos originales y, por lo tanto, no puede ser una medoide.