Clustering algorithms
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 $
Example: Single Link
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
Example: Complete Link
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