Clustering con K-Means y EM: ¿cómo se relacionan?

Question

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 la suposición de que los clusters son esféricos.

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

Además, ¿en qué situación es mejor utilizar el clustering de k-means? o utilizar el clustering de EM?

Answer 1

No existe 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 se conoce también como "modelización de mezclas gaussianas" (GMM), en la que el modelo son distribuciones gaussianas multivariantes.

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

• el paso E, en el que se asigna a cada objeto el centroide tal que se asigna al clúster más probable.
• el paso M, en el que se vuelve a calcular el modelo (=centroides) (= optimización por mínimos cuadrados).

... la iteración de estos dos pasos, como hace Lloyd, hace que esto sea efectivamente una instancia del esquema general de EM. Se diferencia del GMM en que:

• utiliza la partición dura, es decir, cada objeto se asigna exactamente a un clúster
• el modelo son sólo los centroides, no se tienen en cuenta las covarianzas ni las varianzas

Answer 2

K significa

1. Asignar con fuerza un punto de datos a un clúster particular en la convergencia.
2. Hace uso de la norma L2 a la hora de optimizar (Min {Theta} punto de la norma L2 y sus coordenadas del centroide).

EM

1. Soft asigna un punto a los clusters (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 clúster concreto. Esto hace que K-means tenga un sesgo hacia los clusters esféricos.

Answer 3

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 clusters basados en ellas. Especificaría un modelo de mezcla (más específicamente en este caso, un modelo de perfil latente), asumiendo la independencia condicional (las variables observadas son independientes, dada la pertenencia al clúster) como:

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

Yo ejecutaría este modelo varias veces, especificando cada vez un número diferente de clusters, y elegiría la solución que más me gustara (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 pertenencia a una clase sólo se basa en la distancia a las medias de las variables observadas. Como se ha dicho en otras respuestas, las varianzas no tienen nada que ver.

Lo bueno de hacer esto en mplus es que se trata de modelos anidados, por lo que se puede comprobar directamente si las restricciones dan lugar a un peor ajuste o no, además de poder comparar la discordancia en la clasificación entre los dos métodos. Ambos modelos, por cierto, pueden ser estimados utilizando un algoritmo EM, por lo que la diferencia es realmente más sobre el modelo.

Si piensas en el espacio tridimensional, las 3 medias forman un punto... y las varianzas los tres ejes de un elipsoide que pasa por ese punto. Si las tres desviaciones son iguales, se obtiene una esfera.