stringtranslate.com

Agrupamiento de k-medianas

En estadística , el agrupamiento por k -medianas [1] [2] es un algoritmo de análisis de conglomerados . Es una generalización del algoritmo de mediana geométrica o 1-mediana, definido para un único conglomerado.

La k -mediana es una variación de la agrupación 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 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 hace la k -medias).

Esto se relaciona directamente con el problema de la k -mediana , que es el problema de encontrar k centros de manera 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 c i deben elegirse de manera que se minimice la suma de las distancias desde cada x hasta el  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 utiliza ampliamente en aplicaciones como el problema de ubicación de instalaciones .

El algoritmo propuesto utiliza una iteración de 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, 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 individual.

Medianas y medoides

La mediana se calcula en cada dimensión individual en la formulación de la distancia de Manhattan del problema de las 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 en el conjunto de datos; por lo tanto, la mediana resultante puede no ser un miembro del conjunto de datos de entrada.

Este algoritmo suele confundirse con el algoritmo k -medoides . Sin embargo, un medoide tiene que ser una instancia real del conjunto de datos, mientras que para la mediana de la distancia de Manhattan multivariada esto solo se aplica a 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 la distancia de Manhattan es (1,1), que no existe en los datos originales y, por lo tanto, no puede ser un medoide.

Software

Véase también

Referencias

  1. ^ AK Jain y RC Dubes, Algoritmos para agrupar datos . Prentice-Hall, 1988.
  2. ^ PS Bradley, OL Mangasarian y WN Street, "Agrupamiento mediante minimización cóncava", en Advances in Neural Information Processing Systems, vol. 9, MC Mozer, MI Jordan y T. Petsche, Eds. Cambridge, Massachusetts: MIT Press, 1997, págs. 368–374.