Mi objetivo es ver que K-means el algoritmo es, de hecho, Expectation-Maximization algoritmo de Gauss mezclas en las que todos los componentes de covarianza $\sigma^2 I$ en el límite de $\lim_{\sigma \to 0}$.
Supongamos que tenemos un conjunto de datos de $\{x_1, \dots ,x_N\}$ de las observaciones de la variable aleatoria $X$.
La función objetivo para el M-significa que está dada por:
$$J = \sum_{n=1}^{N}\sum_{k=1}^{K} r_{nk} ||x_n - \mu_k ||^2$$
donde $r_{nk}$ es indicador binario variable de un duro asignación de $x_n$ a un clúster $k$.
(si los datos de punto de $x_n$ es asignado al cluster $k$, $r_{nk} = 1$ $r_{nj} = 0$ $j \ne$ k).
K-means el algoritmo de minimizar $J$ a través de la iteración hasta convergencia, que consiste en dos pasos sucesivos:
(E) minimizar $J$ con respecto al $\{r_{nk}\}_{n,k}$ manteniendo todas las $\mu_k$ fijo
(M) minimizar $J$ con respecto al $\{\mu_k\}_k$ manteniendo todas las $r_{nk}$ fijo
En general, denota todos los datos observados por $X$, todas las variables latentes por $Z$ y el conjunto de todos los parámetros del modelo por $\theta$, el algoritmo EM maximizar la distribución posterior $p(\theta | X)$ a través de la iteración hasta que la convergencia, de la alternancia de dos pasos:
(E) calcular la expectativa $Q(\theta, \theta^{\text{old}}) := \sum_{Z}p(Z | X, \theta^{\text{old}})\log p(Z,X|\theta)$
(M) encontrar $\theta^{\text{new}} = \arg \max_{\theta} Q(\theta, \theta^{\text{old}})$
Ahora, considere el Gaussiano mezcla de distribución:
$$p(x) = \sum_{k=1}^K \pi_k N(x | \mu_k, \Sigma_k)$$
La introducción de una latente $K$-dimensiones binaria variable aleatoria $z$$p(z_k = 1) = \pi_k$, vemos que:
$$p(X, Z) = \prod_{n=1}^N\prod_{k=1}^K \pi_k^{z_{nk}} N(x_n | \mu_k, \Sigma_k)^{z_{nk}}$$
$$\gamma(z_k) := p(z_k = 1 | x) = \frac{\pi_k N(x| \mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j N(x | \mu_j, \Sigma_j)}$$
$$\log p(X,Z | \mu, \Sigma, \pi) = \sum_{n=1}^N \sum_{k=1}^K z_{nk}(\log \pi_k + \log N(x_n| \mu_k, \Sigma_k))$$
$$\mathbb{E}(z_{nk}) = \gamma(z_{nk})$$
Por lo $$Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}}) = \sum_{n=1}^N \sum_{k=1}^K \gamma(z_{nk})(\log \pi_k + \log N(x_n| \mu_k, \Sigma_k))$$
Si ahora todos los Gaussianas en la mezcla de un modelo de covarianza $\sigma^2 I$, teniendo en cuenta el límite de $\sigma \to 0$ me puede mostrar fácilmente que $\gamma(z_{nk}) \to r_{nk}$ donde $r_{nk}$ es como se definió anteriormente. Así que, de hecho, la (E) paso actualizaciones $r_{nk}$ como en el K-means el algoritmo.
Sin embargo, tengo un problema con la maximización de la $Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}})$ en este contexto, como por $x \ne \mu$
$\lim_{\sigma \to 0} log(N(x|\mu,\sigma^2)) = - \infty$.
Es cierto, que hasta algunas constantes y la multiplicación escalar:
$\lim_{\sigma \to 0} Q((\pi, \mu, \Sigma), (\pi, \mu, \Sigma)^{\text{old}}) = -J$ ?
Tal vez me estoy perdiendo algo. Algún consejo?
