Agrupación con K-Means y EM: ​​¿cómo se relacionan?

50

He estudiado algoritmos para agrupar datos (aprendizaje no supervisado): EM y k-means. Sigo leyendo lo siguiente:

k-means es una variante de EM, con los supuestos de que los grupos son esféricos.

¿Alguien puede explicar la oración anterior? No entiendo qué significa esférico y cómo se relacionan kmeans y EM, ya que uno realiza la asignación probabilística y el otro lo hace de manera determinista.

Además, ¿en qué situación es mejor usar el agrupamiento k-means? o usar la agrupación EM?

Myna
fuente
Esférico significa matrices de varianza-covarianza idénticas para cada grupo (suponiendo una distribución gaussiana), que también se conoce como agrupamiento basado en modelos. ¿Qué enfoque consideras como determinista?
chl
2
Sería bueno si proporciona la fuente de la cita.
ttnphns
1
k-significa "asume" que los grupos son nubes más o menos redondas y sólidas (no muy alargadas, curvadas o simplemente anilladas) en el espacio euclidiano. No se requiere que provengan de distribuciones normales . EM lo requiere (o al menos se conoce un tipo específico de distribución).
ttnphns

Respuestas:

38

K significa

  1. Difícilmente asigne un punto de datos a un grupo particular en la convergencia.
  2. Hace uso de la norma L2 cuando se optimiza (punto de norma Min {Theta} L2 y sus coordenadas centroides).

EM

  1. Soft asigna un punto a los clústeres (por lo que da una probabilidad de que cualquier punto pertenezca a cualquier centroide).
  2. No depende de la norma L2, sino que se basa en la Expectativa, es decir, la probabilidad de que el punto pertenezca a un grupo particular. Esto hace que K-means esté sesgado hacia grupos esféricos.
Sharan Srinivasan
fuente
57

No hay un "algoritmo k-means". Existe el algoritmo MacQueens para k-means, el algoritmo Lloyd / Forgy para k-means, el método Hartigan-Wong, ...

Tampoco existe "el" algoritmo EM. Es un esquema general de esperar repetidamente las probabilidades y luego maximizar el modelo. La variante más popular de EM también se conoce como "Modelado de mezcla gaussiana" (GMM), donde el modelo son distribuciones gaussianas multivariadas.

Se puede considerar que el algoritmo de Lloyds consta de dos pasos:

  • el paso E, donde cada objeto se asigna al centroide de manera tal que se asigna al grupo más probable.
  • el paso M, donde el modelo (= centroides) se vuelve a calcular (= optimización de mínimos cuadrados).

... iterar estos dos pasos, como lo hizo Lloyd, hace que esto sea efectivamente una instancia del esquema EM general. Se diferencia de GMM que:

  • utiliza particiones duras, es decir, cada objeto está asignado exactamente a un clúster
  • el modelo son solo centroides, no se tienen en cuenta covarianzas ni variaciones
Anony-Mousse
fuente
¿Puedes desarrollar un poco sobre las variantes de medias? Eché un vistazo rápido en Los elementos del aprendizaje estadístico (Hastie, Tibshirani, Friedman), capítulo 14 ... apoyan la idea de la existencia de un " algoritmo de medias". kkk
Elvis
10
Muchos libros equivalen a k-means con el algoritmo lloyds, pero él nunca lo llamó k-means. MacQueen introdujo el nombre k-means. Lo sentimos: muchos libros usan nombres incorrectos aquí . k-means es el problema, lloyd es solo una solución popular. De hecho, R ejecutará Hartigan-Wong por defecto para resolver kmeans.
Anony-Mousse
4

Aquí hay un ejemplo, si estuviera haciendo esto en mplus, que podría ser útil y complementar respuestas más completas:

Digamos que tengo 3 variables continuas y quiero identificar grupos basados ​​en estas. Especificaría un modelo de mezcla (más específicamente en este caso, un modelo de perfil latente), suponiendo independencia condicional (las variables observadas son independientes, dada la membresía del clúster) como:

Model: 
%Overall%
v1* v2* v3*;  ! Freely estimated variances
[v1 v2 v3];   ! Freely estimated means

Ejecutaría este modelo varias veces, cada vez especificando un número diferente de clústeres, y elegiría la solución que más me gusta (hacer esto es un tema muy amplio por sí solo).

Para ejecutar k-means, especificaría el siguiente modelo:

Model: 
%Overall%
v1@0 v2@0 v3@0;  ! Variances constrained as zero
[v1 v2 v3];      ! Freely estimated means

Por lo tanto, la membresía de clase solo se basa en la distancia a las medias de las variables observadas. Como se indicó en otras respuestas, las variaciones no tienen nada que ver con eso.

Lo bueno de hacer esto en mplus es que estos son modelos anidados, por lo que puede probar directamente si las restricciones resultan en peor ajuste o no, además de poder comparar la discordancia en la clasificación entre los dos métodos. Por cierto, ambos modelos se pueden estimar utilizando un algoritmo EM, por lo que la diferencia es realmente más sobre el modelo.

Si piensas en el espacio tridimensional, el 3 significa hacer un punto ... y las variaciones de los tres ejes de un elipsoide que atraviesan ese punto. Si las tres variaciones son iguales, obtendrías una esfera.

DL Dahly
fuente
Gracias por este ejemplo Ayuda mucho a arreglar algunas ideas.
Myna