K-Means is a hard clustering method: it assigns each data point to a fixed cluster
GMM is a soft clustering method: it assigns each data point a probability of belonging to each of the clusters
GMM is a mixture of normal distributions
\[ P(\bold{x}) = \sum_{k=1}^{K} \pi_k \mathcal{N}(\bold{x} | \bold{\mu}_k, \bold{\Sigma}_k) \]$\pi_k$ represent the proportions, essentially how big the cluster $k$ is in the mixture
The proportions must sum to 1
\[ \sum_{k=1}^K \pi_k = 1 \]$\gamma(z_{nk})$ represents the probability of the $n^{th}$ observation belonging to the $k^{th}$ cluster.
Fit K clusters to N observations, each of which may be $d$-dimensional
We want:
For a complete observation set $\bold{X}$ containing $N$ observations, we have:
Using a gradient based optimizer would require computing a derivative, and we have a summation inside the log.
There are also other constraints to take care of, like
The E step: Infer missing values from observations
The M step: Optimize parameters using the "filled in" values in the E step
In theory, the expectation step involves "expected complete data log likelihood", which is just an expectation over the data given the parameters.
In practice, however, we only need to compute the responsibilities: $\gamma(z_{nk})$
\[ \gamma(z_{nk}) = \frac{\pi_k \mathcal{N}(\bold{x}_n | \bold{\mu}_k \bold{\Sigma}_k)}{\sum_{j=1}^{K} \pi_j \mathcal{N}(\bold{x}_n | \bold{\mu}_j \bold{\Sigma}_j)} \]We use the responsibilities ($\gamma(z_{nk})$) to compute optimal values of parameters
$\pi_k^* = \frac{1}{N} \sum_{n=1}^{N} \gamma(z_{nk})\qquad$$\bold{\mu}_k^* = \frac{\sum_{n=1}^N \gamma(z_{nk}) \bold{x}_n}{\sum_{n=1}^N \gamma(z_{nk})}$We alternate between the E step and the M step for many iterations, until the log likelihood $\ln P(\bold{X})$ converges.
The raw RI score is then adjusted for chance into the ARI score
\[ \green{\textsf{ARI} = \frac{\textsf{RI - Expected RI}}{\textsf{Max RI - Expected RI}}} \]We use the ARI (or ARS) as it is a better measure.
GMM with EM was done in 2 modes:
GMM with EM was done in 2 modes:
GMM with EM was done with a K-Means initialization
In the 1000 files run, GMM performed better than standard K-Means in 997 files
The only 3 files where K-Means performed better had some clusters with abnormally low points, like 1 or 2 only