En estadística , la agrupación de k -medians [1] [2] es un algoritmo de análisis de agrupaciones . Es una variación de la agrupación de k medias en la que 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 conglomerados con respecto a la métrica de distancia de 1 norma , a diferencia de la métrica de distancia de 2 normas al cuadrado (que significa k ).
Esto se relaciona directamente con el problema de la k- mediana con respecto a la norma 1, que es el problema de encontrar k centros de manera que los grupos formados por ellos sean los más compactos. Formalmente, dado un conjunto de puntos de datos x , los k centros c i deben elegirse de manera que se minimice la suma de las distancias de cada x al c i 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 usa ampliamente en aplicaciones como la ubicación de instalaciones .
El algoritmo propuesto utiliza una iteración al estilo de Lloyd que alterna entre un paso de expectativa (E) y un paso 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.
Medianas y medoides
La mediana se calcula en cada una de las dimensiones en la formulación de la distancia de Manhattan del problema de los k -medians, por lo que los atributos individuales provendrán del conjunto de datos. Esto hace que el algoritmo sea más confiable para conjuntos de datos discretos o incluso binarios. En contraste, 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 en el conjunto de datos; por lo tanto, la mediana resultante puede no ser un miembro del conjunto de datos de entrada.
Este algoritmo se confunde a menudo 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 la distancia de Manhattan esto solo es válido para valores de un solo atributo. Por tanto, la mediana real puede ser una combinación de varios 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.
Software
Ver también
Referencias
- ^ AK Jain y RC Dubes, algoritmos para agrupar datos . Prentice-Hall, 1988.
- ^ PS Bradley, OL Mangasarian y WN Street, "Agrupación mediante minimización cóncava", en Avances en sistemas de procesamiento de información neuronal, vol. 9, MC Mozer, MI Jordan y T. Petsche, Eds. Cambridge, Massachusetts: MIT Press, 1997, págs. 368–374.