Contents

Clustering is a unsupervised Machine Learning algorithm that groups a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters). [Suggested introductory reading]. Here, I shall talk about three of them namely EM clustering, k-means and hierarchical clustering.

### EM clustering

We have $N$ data samples (unlabelled) $D= { x_1,x_2,\dots,x_N }$ spanning $c$ classes $w_1,w_2,\dots,w_c$. In order to simplify our analysis let’s assume $c=3$ and $N=500$. We can write the prior and likelihood as follows

Prior Likelihood
$P(w_1)$ $P(x/w_1) \sim \mathcal{N}(\mu_1,‎‎\sum_1)$
$P(w_2)$ $P(x/w_2) \sim \mathcal{N}(\mu_2,‎‎\sum_2)$
$P(w_3)$ $P(x/w_3) \sim \mathcal{N}(\mu_3,‎‎\sum_3)$

#### Gaussian Mixture Model (GMM)

The problem can be formulated as a GMM

$P(x/\theta)=P(w_1)P(x/w_1)+P(w_2)P(x/w_2)+P(w_3)P(x/w_3)$

Given, the data points ${ x_1,x_2,\dots,x_N }$ our goal is to find the parameter $\theta$ (consists of $\mu_i \text{, } \sum_i \text{ and } P(w_i)$) using MLE (ML Estimation).

#### Expectation maximization to solve GMM parameters

We can find the parameters using an iterative scheme. We can initialize $(\mu_i,‎‎\sum_i)$ with some random values and then iterate over the expectation and maximization steps until convergance is achieved.

Expectation

Assuing $(\mu_1,‎‎\sum_1)$ are available, we can perform Bayesian classification on ${ x_1,x_2,\dots,x_n }$ using likelihood at some iteration as

$x_k \in w_i \text{ iff } P(x_k/w_i)>P(x_k/w_j) \forall j \neq i$

Maximization

Given some $x_k$, then what are $(\mu_i,‎‎\sum_i)$ that maximize for those $x_k$ to have $P(x_k/w_i) \sim \mathcal{N}(\mu_i,‎‎\sum_i)$?

$\{ x_1,x_2,\dots,x_n \} \in w_i$

Using MLE,

$\mu_i = \frac{1}{N_i} \sum_k x_k \forall x_k \in w_i$ $\sum_i = \frac{1}{N_i} \sum_k (x_k-\mu_i)(x_k-\mu_i)^T \forall x_k \in w_i$

Thus, we have the updated values for $(\mu_i,‎‎\sum_i)$ and can now again perform expectation step in an iterative way untill convergance.

### k-means clustering

Let us assume identity covarience matrix i.e. $| \sum | = 1$, we can write $P(x_k/w_i) = \frac{1}{(2\pi)^{d/2}} e^{ \frac{-1}{2} (x_k-\mu_i)^T (x_k-\mu_i)} = \frac{1}{(2\pi)^{d/2}} e^{ \frac{-1}{2} \| x_k-\mu_i \| ^2 }$

Algorithm

• Descide the number of clusters, $c$
• Assume $\mu_i$ for classes $1:c$
• Expectation
• $x_k \in$ if $P(x_k/w_i)>P(x_k/w_j) \forall i \neq j$
• if $\| x_k-\mu_i \| ^2 \leq \| x_k-\mu_j \| ^2 \forall i \neq j, \text{ then } x_k \in w_i$
• Maximization $\mu_i = \frac{1}{N_i} \sum_k x_k \forall x_k \in w_i$
• Repeat step 2 and 3 untill convergence, $\| \mu_i^t-\mu_i^{t-1} \| ^2 \to \text{constant}$

#### Below code shows the implementation

Fig.1: Initial iteration using k-means

Fig.2: Final clusters obtained via k-means

As shown in the above two figures the k-means algorithm correctly clusters the data points into three clusters.

### Hierarchical clustering

Hierarchical clustering is a clustering method which seeks to build a hierarchy of clusters based on some distance or similarity meteric. This can be further classified as

• Agglomerative clustering: (“bottom-up” approach) each point starts as a seperate individual cluster and merges into a single cluster.
• Divisive clustering: (“top-down” approach) starts with one single cluster and keeps on dividing upto individual point clusters
• Isodata clustering: combines features of both agglomerative and divisive clustering to achieve optimal clusters

Based on the distance meteric used the agglomerative clustering can be further classified as

• Single link or Nearest neighbour
• Distance between two clusters $c_1$ and $c_2$, $d = \min | X-Y |^2 \text{ where, } X \in c_1 \text{ and } Y \in c_2$
• Complete link or farthest neighbour
• Distance between two clusters $c_1$ and $c_2$, $d = \max | X-Y |^2 \text{ where, } X \in c_1 \text{ and } Y \in c_2$

Suppose that we have the given points $x_1,x2,\dots,x7$ with the distances shown below.

x1 ------- x2 ------- x3 ------- x4 ------- x5 ------- x6 ------- x7
1          1.1        1.2        1.3        1.4        1.5


To form clusters, we treat the individual points as clusters and grow them. Find the distance between the clusters using $d = \min | X-Y |^2 \text{ where, } X \in c_1 \text{ and } Y \in c_2$ and merge $c_i$ with $c_j$ if $d(c_i,c_j) \leq d(c_i,c_k) \forall k \neq j$. Finally we can obtain

x1         x2         x3         x4         x5         x6         x7
|          |          |           |         |          |          |
|          |          |           |         |          |          |
------------ 1        |           |         |          |          |
|                |           |         |          |          |
|                |           |         |          |          |
------------------ 1.1       |         |          |          |
|                   |         |          |          |
|                   |         |          |          |
--------------------- 1.2     |          |          |
|                   |          |          |
|                   |          |          |
--------------------- 1.3      |          |
|                   |          |
|                   |          |
--------------------- 1.4      |
|                    |
|                    |
---------------------- 1.5



We can use the same example distances given in single link example. Here, we can find the distance between the clusters using $d = \max | X-Y |^2 \text{ where, } X \in c_1 \text{ and } Y \in c_2$ and merge $c_i$ with $c_j$ if $d(c_i,c_j) \leq d(c_i,c_k) \forall k \neq j$. Finally we can obtain

x1         x2         x3         x4         x5         x6         x7
|          |          |           |         |          |          |
|          |          |           |         |          |          |
------------ 1        |           |         |          |          |
|                ------------- 1.2     |          |          |
|                      |               ------------ 1.4      |
|                      |                     |               |
|                      |                     |               |
|                      |                     ----------------- 2.9
------------------------ 3.3                         |
|                                           |
|                                           |
--------------------------------------------- 7.5