5
$\begingroup$

I am looking for a tutorial/gentle introduction (preferably with mathematics/proofs) on K-means as a special case of Gaussian Mixture Model using the EM Algorithm.

I have found this: https://www.youtube.com/watch?v=qMTuMa86NzU This video provides a good conceptual introduction, but I want to see a gentle, easy-to-understand proof for this. I know this is entirely subjective, so any leads are welcome.

I have also seen a proof from Coursera from the Russian HSE University, though I am confused why there was a sudden mention of the Dirac Delta Function as a prior.

Any leads welcome (tutorial/lecture notes/videos,etc) on this topic.

$\endgroup$
1

1 Answer 1

3
$\begingroup$

Let's start with the basics, log-density of Gaussian distribution is

$$ \log p(x|\mu,\sigma) \propto -\frac{1}{2\sigma^2} \,(x-\mu)^2 $$

So to estimate the mean you need to minimize the squared error. This is true not only for the mean of the Gaussian distribution, but in general, arithmetic mean is the value that minimizes the squared error. The loss function of $k$-means can be written as

$$ \underset{S}{\operatorname{arg\,min}} \, \sum_{i=1}^n \sum_{j=1}^k \mathbb{1}(\mathbf{x}_i \in S_j) \, (\mathbf{x}_i - \mathbf{m}_j)^2 $$

where $\mathbb{1}(\mathbf{x}_i \in S_j)$ is a indicator function that is equal to one if $\mathbf{x}_i$ belongs to cluster $S_j$ and zero otherwise (hence the Dirac delta). This is the standard, "hard" $k$-means. There is also a "soft" variant of $k$-means, where the cluster assignments are fuzzy and the loss function is

$$ \underset{S}{\operatorname{arg\,min}} \, \sum_{i=1}^n \sum_{j=1}^k w_{ij} \, (\mathbf{x}_i - \mathbf{m}_j)^2 $$

with $\sum_j w_{ij} = 1$ for all $i$. If you set the weights $w_{ij}$ to zeroes and one for one of the clusters where $\mathbf{x}_i$ belongs, the "soft" version of the algorithm can be thought as a generalization of the "hard" one. Here the weights $w_{ij}$ measure how far $\mathbf{x}_i$ lies from the $j$-th cluster mean $\mathbf{m}_j$.

Now recall that finite mixture distribution is defined as

$$ p(\mathbf{x}) = \sum_{j=1}^k w_j \, \mathcal{N}(\mathbf{x}_i| \boldsymbol\mu_j, \boldsymbol\sigma_j^2) $$

with $\sum_{j=1}^k w_j = 1$ being the mixing weights and $\mathcal{N}(\cdot| \boldsymbol\mu_j, \boldsymbol\sigma_j^2)$ being the individual Gaussian components. So soft $k$-means is very much like a Gaussian mixture model.

You can find more detailed answer in the In cluster analysis, how does Gaussian mixture model differ from K Means when we know the clusters are spherical? thread.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.