Machine learning/Unsupervised Learning/K-means Clustering

K-means is a method of clustering which is an unsupervised learning problem.

• In this method the number of clusters is an input to the algorithm (hyper-parameter).
• K-means method is a greedy algorithm. It is a special case of expectation maximization (EM) algorithm, in which we try to find maximum likelihood expectation (MLE).
• K-means algorithm is not guaranteed to converge to the global mean of the loss function (sum of Euclidean distances from each cluster center). The global minimum problem is an NP hard problem.

Relation to Gaussian Mixture Model (GMM):

• GMM is a more probabilistic approach to clustering.
• Expectation maximization (EM) algorithm is used to find a good gaussian mixture model to cluster the data.

Intuition

Data points in each cluster are closer to the center of each cluster than the center of other clusters.

Algorithm

Assume that the number of clusters is given by $k$ and the cluster centers are shown with ${\mu }_1,{\mu }_2,\cdots ,{\mu }_k\in {ℝ}^d$.

We define a loss function for clustering and try to minimize it through the following greedy algorithm.

The loss function is defined as

$$L=\sum _{j=1}^k\sum _i{a}_{ij}||x_i-{\mu }_j|{|}^2\text{where}{a}_{ij}=\{\begin{array}{cc}1& \text{if }{x}_i\text{ assigned to }j\\ 0& \text{else}\end{array}$$

Minimize $L$ with respect to $a$ and $\mu$ by following these two steps until convergence is achieved:

1. Choose optimal $a$ for fixed $\mu$ by assigning $x_i$ to the nearest ${\mu }_j$$$a_{ij}=\{\begin{array}{cc}1& \text{if }j={\arg \min }_l|x_i-{\mu }_l{|}^2\\ 0& \text{else}\end{array}$$
2. Choose optimal $\mu$ for fixed $a$ by updating ${\mu }_j$ to be the empirical mean of the points assigned to each cluster$${\mu }_j=\frac{1}{n_j}\sum _{i:x_i\text{ in j}}{x}_i\text{ where }{n}_j=\sum _{i=1}^m{a}_{ij}=\text{number of data points assigned to j}$$

Justification

In this section, we show that choosing cluster center, ${\mu }_j$, according to step 2 of the algorithm minimized loss function for a fixed set of assignment factors ($a_{ij}$)

In order to find the minimum value of loss function ($L$) as a function of ${\mu }_j$, we find the point for which the gradient of the function is zero

$${\mathrm{\nabla }}_{{\mu }_j}L=0$$Therefore, we have

$$\begin{array}{cc}{\mathrm{\nabla }}_{{\mu }_j}L=& \sum _i{a}_{ij}{\mathrm{\nabla }}_{{\mu }_j}(x_i-{\mu }_j{)}^T(x_i-{\mu }_j)\\ =& \sum _i{a}_{ij}{\mathrm{\nabla }}_{{\mu }_j}(x_i^T{x}_i-2{\mu }_j^T{x}_i+{\mu }_j^T{\mu }_j)\\ =& \sum _i{a}_{ij}(-2x_i+2{\mu }_j)=0\end{array}$$Getting rid of the factor of 2 in the last expression we have $${\mu }_j\sum _i{a}_{ij}=\sum _i{a}_{ij}{x}_i\Rightarrow {\mu }_j=\frac{\sum _i{a}_{ij}{x}_i}{\sum _i{a}_{ij}}$$We also have $n_j=\sum _{i=1}^n{a}_{ij}=\mathrm{\#}\{i:x_i\text{ is assigned to }j\}$, which simplifies ${\mu }_j$ to$${\mu }_j=\frac{1}{n_j}\sum _{i:x_i\text{ in j}}{x}_i$$