Algoritmo EM

El problema es que no sabemos de qué distribución viene cada dato y no concemos los parámetros de las distribuciones.

El algoritmo EM (Expectation Maximization) empieza adivinando los parámetros de las distribuciones y los usa para calcular las probabilidades de que cada objeto pertenezca a un cluster y usa esas probabilidades para re-estimar los parámetros de las probabilidades, hasta converger (se puede empezar adivinando las probabilidades de que un objeto pertenezca a una clase).

El cálculo de las probabilidades de las clases o los valores esperados de las clases es la parte de expectation.

El paso de calcular los valores de los parámetros de las distribuciones, es maximization, maximar la verosimilitud de las distribuciones dados los datos.

Para estimar los parámetros, tenemos que considerar que tenemos únicamente las probabilidades de pertenecer a cada cluster y no los clusters en si. Estas probabilidades actuan como pesos:

$$\mu_A = \frac{w_1 x_1 + w_2 x_2 + \ldots w_n x_n} {w_1 + w_2 + \ldots w_n}$$

$$\sigma_A^2 = \frac{w_1(x_1 - \mu)^2 + w_2(x_2 - \mu)^2 + \ldots w_n(x_n - \mu)^2}{w_1 + w_2 + \ldots w_n}$$

donde $w_i$ es la probabilidad de que el objeto $i$ pertenezca al cluster $A$ y se suma sobre todos los objetos (no solo los de $A$).

El algoritmo tiende a converger pero nunca llega a un punto fijo.

Podemos ver que tanto se acerca calculando la versorimilitud general de los datos con esos parámetros, multiplicando las probabilidades de los objetos individuales ($i$):

$$\prod_i (P_A P(x_i\vert A) + P_B P(x_i\vert B))$$

Esta medida crece en cada iteración, y se itera hasta que el crecimiento es despreciable.

Aunque EM garantiza convergencia, esta puede ser a un máximo local, por lo que se recomienda repetir el proceso varias veces.