Sesión 14 A#
Modelos de Mezcla Gaussiana (GMM)#
Objetivos:
Introducir K-Means como contraste simple a GMM.
Familiarizarse con el algoritmo Expectation-Maximization (EM) para GMM.
Explorar GMMs.
Lectura recomendada:
Mixture Models and EM. Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.
1. K-Means Clustering#
1.1. El modelo#
Dado un conjunto de datos:
Queremos particionarlos en \(K\) clusters definidos por sus centroides:
Introducimos variables de asignación: $\( r_{nk} \in \{0,1\} \)$
donde
\(r_{nk} = 1\) si el punto \(x_n\) está asignado al cluster \(k\)
cada punto pertenece a un único cluster: $\( \sum_{k=1}^K r_{nk} = 1 \)$
1.2. Función de costo (distorsión / inertia / WCSS)#
La función objetivo que queremos minimizar es:
Esta mide la suma de distancias cuadradas dentro del cluster.
Minimizar \(J\) → significa clusters compactos.
K-means es geométrico, no probabilístico.
1.3. Algoritmo de optimización: algoritmo de Lloyd#
K-means minimiza \(J\) mediante un proceso iterativo de descenso alternado:
(A) Paso de asignación Fijando los centroides, asignamos cada punto al más cercano:
(B) Paso de actualización de centroides
Fijando las asignaciones, cada centroide se actualiza como el promedio de sus puntos:
(C) Criterio de convergencia
El algoritmo termina cuando:
las asignaciones no cambian, o
los centroides dejan de moverse, o
se alcanza un máximo de iteraciones.
🔥 Ejercicio en pizarron
Figura 1: (a) Los puntos verdes representan el conjunto de datos en un espacio euclidiano bidimensional. Las elecciones iniciales para los centros \(\mu_1\) y \(\mu_2\) se muestran con las cruces roja y azul, respectivamente.(b) En el paso E inicial, cada punto de datos se asigna al clúster rojo o al clúster azul, según cuál centroide esté más cerca. Esto es equivalente a clasificar los puntos según de qué lado de la bisectriz perpendicular entre los dos centros de clúster (línea magenta) se encuentren. (c) En el paso M posterior, cada centro de clúster se recalcula como la media de los puntos asignados al clúster correspondiente.(d)–(i) muestran los pasos E y M sucesivos hasta la convergencia final del algoritmo. Retomada de Bishop (2006).
1.4. ¿Por qué se le llama «hard-clustering»?#
Porque cada punto se asigna a un único cluster (asignación dura).
Anteriormente vimos en el paso de asignación: $\( r_{nk} = \begin{cases} 1 & \text{si } k = \arg\min_j \|x_n - \mu_j\|^2 \\ 0 & \text{otro caso} \end{cases} \)$
1.5. ¿Qué asume el modelo K-means sobre los datos?#
Figura 2: K-means asume que los clusters son esféricos y de tamaño similar, como ilustra la imagen de la izquierda. En la imagen de la derecha, K-means no puede capturar la estructura real de los datos debido a estas suposiciones. Retomada de Scikit-learn.
Los clusters son esféricos (isotrópicos) y de tamaño similar.
Fronteras de decisión lineales (basadas en distancia euclidiana).
Forma uniforme (simétrica alrededor del centroide).
Más puntos al centro del cluster que en los bordes.
Aquí puedes ver la documentación oficial de métodos de clustering en
scikit-learn
Nota
K-means funciona bien si los clusters son:
isotrópicos (no elípticos)
convexos
de tamaño parecido
con densidad decreciente radialmente
Falla si los clusters son:
elípticos
rotados
de distinta varianza
no convexos
solapados
Figura 3: Ejemplos de conjuntos de datos donde K-means puede fallar debido a sus suposiciones sobre la forma y distribución de los clusters. Retomada de Mael Fabien, 2020.
💡 ¿Nos hemos preguntado por qué sucede lo de clústers esféricos?
2. Gaussian Mixture Models (GMMs) y K-means#
K-means es un método simple, rápido y muy útil cuando los clústers son “redondos”, de tamaño similar y bien separados. Pero estas suposiciones son fuertes y en muchos problemas reales no se cumplen.
Esto nos deja con dos limitaciones importantes:
La forma del cluster está restringida.
La asignación de los puntos es dura.
Ahora, planteemos una pregunta natural:
¿Y si pudiéramos relajar estas dos restricciones?#
Soft-clustering
Para la forma:
¿Qué define realmente la forma de un cluster?Para la asignación:
¿Tiene sentido obligar a que cada punto pertenezca a un solo cluster?
Estas dos ideas —modelar la forma y permitir asignaciones suaves— nos llevan directamente a los Gaussian Mixture Models (GMMs).
Aquí van algunas pistas, si comparamos K-means y GMMs, tenemos que:
k-Means |
GMM (Gaussian Mixture Model) |
|---|---|
Los clústers se definen por sus medias |
Los clústers se definen por sus medias y sus varianzas, modelados como Gaussianas |
Tiene limitaciones si los clústers están superpuestos |
Funciona incluso si los clústers están superpuestos |
Utiliza la distancia euclidiana al centroide |
Utiliza la probabilidad de que X pertenezca a un clúster (modelo generativo) |
El algoritmo k-Means es, de hecho, un caso especial de un GMM con Expectation-Maximization: Hard, donde cada componente se modela mediante
siendo \(I\) la matriz identidad.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
# Generemos dos clústers
np.random.seed(0)
n1 = 500
n2 = 500
#Clúster 1
mu1 = [0, 0]
cov1 =[[1,0],
[0,1]]
C1 = np.random.multivariate_normal(mu1, cov1, n1)
#Clúster 2
mu2 = [5, 0] #puedo cambiar la media
cov2 =[[16,5], # puedo cambiar la covarianza
[4,12]]
C2 = np.random.multivariate_normal(mu2, cov2, n2)
/tmp/ipykernel_1164/3724255304.py:19: RuntimeWarning: covariance is not symmetric positive-semidefinite.
C2 = np.random.multivariate_normal(mu2, cov2, n2)
# Concatenar np.vstack
X = np.vstack([C1, C2])
X
array([[ 1.76405235, 0.40015721],
[ 0.97873798, 2.2408932 ],
[ 1.86755799, -0.97727788],
...,
[ 4.12178416, -0.23773256],
[-0.32062964, -3.01813074],
[11.32914938, -0.49276207]], shape=(1000, 2))
# Grafiquemos los datos
plt.figure(figsize=(10, 5))
plt.scatter(C1[:, 0], C1[:, 1], color='blue', alpha=0.5, label='Cluster 1 (Esférico)')
plt.scatter(C2[:, 0], C2[:, 1], color='red', alpha=0.5, label='Cluster 2 (Elongado)')
plt.title("Clusters con covarianza esférica vs. covarianza no esférica")
plt.xlabel("X1")
plt.ylabel("X2")
plt.legend()
plt.grid(True)
plt.axis('equal')
plt.show()
#import os
#os.environ["OMP_NUM_THREADS"] = "4"
# Aplicar K-means
kmeans = KMeans(n_clusters=2, random_state=0)
labels = kmeans.fit_predict(X)
centers = kmeans.cluster_centers_
# Graficar resultado de KMeans
plt.figure(figsize=(10, 5))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', alpha=0.5)
plt.scatter(centers[:, 0], centers[:, 1], c='red', s=200, marker='X', label='Centroides')
plt.title("Resultado de KMeans sobre los clusters")
plt.xlabel("X1")
plt.ylabel("X2")
plt.legend()
plt.grid(True)
plt.axis('equal')
plt.show()
3. GMMs#
Los GMMs son modelos probabilísticos que asumen que los datos son generados a partir de una mezcla de varias distribuciones Gaussianas.
3.1. ¿Por qué una «mezcla» de Gaussianas?#
Pensemos en el siguiente ejemplo:
Figura 4: Ejemplo de un conjunto de datos que parece obvio que proviene de dos grupos distintos. Si modelamos con una sola distribucuión Gaussiana, quizá terminemos con un promedio que no refleje la estructura real de los datos. Retomada de Mael Fabien, 2020.
3.1. Set up#
Tenemos datos \(X = \{x_1, x_2, \ldots, x_N\}\) que parecen venir de varios grupos, pero:
No sabemos cuántos grupos generaron los datos.
No sabemos a qué grupo pertenece cada punto.
No sabemos ni las medias ni las formas (var/cov) de esos grupos.
En un GMM, suponemos que:
Cada grupo o componente es una distribución Gaussiana con sus propios parámetros (media y covarianza).
Para aprender el modelo, necesitamos 3 parámetros por componente:
su media \(\mu_k\)
su varianza/covarianza \(\sigma_k\) o \(\Sigma_k\)
su peso \(w_k=p(z=k)\) (probabilidad de elegir ese grupo)
estos parámetros se inicializan aleatoriamente o con alguna otra técnica y se aprenden a partir de los datos usando el algoritmo de Expectation-Maximization (EM).
Figura 5: Se muestran tres distribuciones gaussianas (componentes de un modelo). Notese que cada gaussiana tiene un valor para sus parámetros \((\mu_k, \Sigma_k)\) y un peso \(w_k\).
3.2. ¿Cómo nos ayuda la probabilidad y los grafos probabilísticos?#
El objetivo principal de un Modelo de Mezcla Gaussiana (GMM) es poder calcular la probabilidad de observar un dato \(x\) bajo el modelo:
es decir, queremos saber qué tan probable es que el dato \(x\) haya sido generado por nuestro modelo.
Pero hay un problema:
El dato \(x\) sí lo observamos,
El componente del que proviene, \(z\), no lo observamos.
Por eso introducimos un concepto importante: la variable latente \(z_n\).
Figura 6: Diagrama de un modelo gráfico probabilístico para un GMM con \(K\) componentes. Retomade de Bishop (2006).
¿Qué representa la variable latente \(z_n\)?
La variable \(z_n\) es «latente» porque no se observa directamente. Su función es indicar a cuál componente del GMM pertenece el dato \(x_n\).
En un modelo de mezclas gaussianas, esta relación suele representarse mediante un grafo probabilístico como el mostrado en la Figura 6.
En este grafo se expresa la distribución conjunta como:
El nodo \(z\) genera (o explica) al nodo \(x\).
¿cómo obtenemos \(p(x) si \)z$ no es observable?
La probabilidad total nos da la clave: si hay variables ocultas, para obtener \(p(x)\) debemos sumar sobre todos los valores posibles de la variable oculta:
Si no sé qué generó el dato \(x\), considero todos los posibles orígenes.
Luego, si factorizamos la distribución conjunta usando la regla de la cadena:
y sustituimos, obtenemos:
Esta es la idea esencial! Aunque no separamos qué componente generó el dato, podemos considerar todos los componentes y ponderarlos por su probabilidad.
Modelo GMM:
En un GMM, los valores posibles de \(z\) corresponde a los \(K\) componentes de la mezcla.
Cada componente tiene:
un peso \(w_k = p(z=k)\)
una distribución Gaussiana \(p(x|z=k) = \mathcal{N}(x | \mu_k, \Sigma_k)\)
Sustituyendo en la fórmula, obtenmos el modelo GMM:
$$ \boxed{p(x) = \sum_{k=1}^K w_k , \mathcal{N}(x | \mu_k, \Sigma_k)}\tag{6}
El modelo en \((6)\) dice que la probabilidad de \(x\) es una suma ponderada de varias Gaussianas: cada una aporta según qué tan probable es que ese componente sea el responsable de generar \(x\).
3.3. ¿De qué componente vino ese dato?#
Hasta ahora sabemos cómo calcula un GMM la probabilidad total de un dato \(x\). Pero el siguiente paso es más interesante:
Inferencia de \(Z\): queremos inferir de qué componente \(k\) de la mezcla proviene un dato \(x_i\).
¿Cuál es la probabilidad de que el dato \(x_i\) haya sido generado por el componente \(k\)?
A esta probabilidad se le llama resposability (responsabilidad) del componente \(k\) sobre el dato \(x_i\):
Aplicamos el teorema de Bayes:
y esto tiene una lectura muy intuitiva:
\(p(z=k)\): lo probable que es el componente \(k\) antes de ver el dato (prior)
\(p(x_i|z=k)\): qué tan bien explica el componente \(k\) el dato.
\(p(x_i)\): normaliza la probabilidad para sumar 1.
En la Figura 6 imaginamos un dato \(x_i\) y tres gaussianas distintas. Cada gaussiana tiene una altura diferente en el punto \(x_i\).
La altura de cada gaussiana en \(x_i\) describe qué tan probable es ese dato si ese componente lo hubiere generado.
Figura 7: La figura representa un dato \(x_i\). Hay 3 distribuciones gaussianas del modelo \(k=1,2,3\). Cada gaussiana tiene un valor distinto en ese punto \(x_i\). Cada dato está asociado (o no) a varias Gaussianas. La altura relativa de cada Gaussiana en la posición del dato determina la probabilidad de que ese dato pertenezca a ese componente. Esa probabilida es precisamente \(\gamma_{ik} = p(z_k = k | x_i)\). Retomada de Mael Fabien, 2020.
Sustityendo cada término usando el modelo GMM:
Prior (peso del componente): \(p(z_k=k) = w_k\)
Likelihood (gaussiana del componente): \(p(x_i | z_k=k) = \mathcal{N}(x_i | \mu_k, \Sigma_k)\)
Evidencia (prob. total del dato): \(p(x_i) = \sum_{c=1}^K w_c \, \mathcal{N}(x_i | \mu_c, \Sigma_c)\)
$$ \gamma_{ik} = \frac{w_k , \mathcal{N}(x_i | \mu_k, \Sigma_k)}{\sum_{c=1}^K w_c , \mathcal{N}(x_i | \mu_c, \Sigma_c)}\tag{9}
3.4. Algoritmo Expectation-Maximization (EM)#
Esto nos lleva de forma natural al algoritmo EM, un método elegante y poderoso para encontrar soluciones de máxima verosimilitud en modelos con variables latentes.
El algoritmo EM alterna dos pasos: Estimación y Maximización.
La idea general puede visualizarse como en la Figura 7:
Figura 8: Diagrama del algoritmo Expectation-Maximization (EM) para Gaussian Mixture Models (GMMs). Retomada de Mael Fabien, 2020.
Partimos de unos parámetros iniciales \(\theta^{(t)}\) del modelo.
En el E-step (Estimation), mantenemos fijos esos parámetros y calculamos las \(\gamma_{ik}^{(t)}\), es decir, la probabilidad de que cada dato haya sido generado por cada componente.
En el M-step (Maximization), mantenemos fijas las \(\gamma_{ik}^{(t)}\) y actualizamos los parámetros del modelo para obtener \(\theta^{(t+1)}\).
E-step:
En el algoritmo EM, cada iteración tiene parámetros actuales
El E-step consiste precisamente en evaluar la expresión anterior usando los parámetros actuales, es decir:
Estas probabilidades \(\gamma_{ik}^{(t)}\) son la salida del E-step y se usarán como “asignaciones suaves” en el siguiente paso, el M-step, para actualizar los parámetros del modelo.
E-step calculamos \(\gamma_{ik} = p(z_k = k | x_i, \theta^{(t)})\) usando los parámetros actuales \(\theta^{(t)}\).
M-step:
Una vez calculadas las \(\gamma_{ik}^{(t)}\) en el E-step, el M-step mantiene fijas estas probabilidades y actualiza los parámetros del modelo para obtener nuevos valores
En esta etapa, cada dato contribuye a los parámetros de cada componente de forma ponderada por su \(\gamma_{ik}^{(t)}\).
El resultado es equivalente a realizar una estimación de máxima verosimilitud, pero donde cada dato tiene un peso diferente según qué componente lo explica mejor.
Las actualizaciones toman la forma:
Nuevos pesos: $\( w_k^{(t+1)} = \frac{1}{N}\sum_{i=1}^N \gamma_{ik}^{(t)} \)$
Nuevas medias: $\( \mu_k^{(t+1)} = \frac{\sum_{i=1}^N \gamma_{ik}^{(t)} \, x_i}{\sum_{i=1}^N \gamma_{ik}^{(t)}} \)$
Nuevas covarianzas: $\( \Sigma_k^{(t+1)} = \frac{ \sum_{i=1}^N \gamma_{ik}^{(t)} (x_i - \mu_k^{(t+1)})(x_i - \mu_k^{(t+1)})^\top }{ \sum_{i=1}^N \gamma_{ik}^{(t)} } \)$
Con estos parámetros actualizados \(\theta^{(t+1)}\), comienza una nueva iteración del algoritmo: volvemos al E-step, calculamos nuevas \(\gamma_{ik}^{(t+1)}\), y repetimos el ciclo hasta que el modelo converge.
Figura 9: Visualización del proceso iterativo del algoritmo Expectation-Maximization (EM) para Gaussian Mixture Models (GMMs). En cada iteración, el E-step calcula las responsabilidades \(\gamma_{ik}\) basadas en los parámetros actuales del modelo, y el M-step actualiza los parámetros utilizando estas responsabilidades. Este ciclo se repite hasta la convergencia del modelo.
Notas para revisar a fondo el algoritmo EM: