K-means clustering

This is my personal notes taken for the course Machine learning by Standford. Feel free to check the assignments.
Also, if you want to read my other notes, feel free to check them at my blog.

I) Introduction

In the clustering problem, we are given a training set

$x^{(1)},...,x^{(m)}$ ,and want to group the data into a few cohesive "clusters". Here,

$x^{(i)}\in R^n$ as usual; but no labels

$y^{(i)}$ are given. So, this is an unsupervised learning problem. The k-means clustering algorithm is as follows:

$$\begin{array}{rl}& \text{1. Initialize cluster centroids }{\mu }_1,{\mu }_2,...,{\mu }_k\in {\mathbb{R}}^n\text{ randomly}\\ & \text{2. Repeat until convergence : }\end{array}$$

$$\begin{array}{r}\text{For every i, set}\\ & c^{(i)}:{=}_j\Vert x^{(i)}-{\mu }_j{\Vert }^2\\ \text{For every j, set}\\ & {\mu }_j:=\frac{\sum _{i=1}^m{1}_{\{c^{(i)}=j\}}{x}^{(i)}}{\sum _{i=1}^m{1}_{\{c^{(i)}=j\}}}\end{array}$$

In the algorithm above, we have:

1. $k$, number of clusters.
2. $c^{(i)}$ is the index of the cluster such that
   $x^{(i)}$ belongs to it.
3. ${\mu }_j$ is a cluster centroid (center of a cluster).

II) Algorithm explanation

To initialize the cluster centroids (in step 1 of the algorithm above), we could choose

$k$ training examples randomly, and set the cluster centroids to be equal to the values of these

$k$ examples. (Other initialization methods are also possible).

Figure 1: 2 cluster centroids equal to 2 training examples

The inner-loop is then compose of 2 steps:

1. Cluster assignment step (clusters
   $c^{(i)}$ are updated).
2. Move cluster step (cluster centroids
   ${\mu }_j$ are updated).

1. Cluster assignment

We assign each training example

$x^{(i)}$ to the nearest cluster centroid

${\mu }_j$. To do so, we need to find the value

$j$ that minimizes

$\Vert x^{(i)}-{\mu }_j{\Vert }^2$ (Euclidean distance).

2. Move cluster

Compute the averages for all the points inside each of the cluster centroid groups

$c$, then move the cluster centroid points

${\mu }_j$ to those averages.

---

Remark:

• $\sum _{i=1}^m{1}_{\{c^{(i)}=j\}}{x}^{(i)}$ = sum over all the points
  $x^{(i)}$ that belong to the cluster
  $c^{(i)}$
• $\sum _{i=1}^m{1}_{\{c^{(i)}=j\}}$ = total number of points
  $x^{(i)}$ that belong to the cluster
  $c^{(i)}$ (we will denoted it as
  $n$).

Thus,

$\text{For every j, set:}$

$$\begin{array}{r}{\mu }_j:=\frac{\sum _{i=1}^m{1}_{\{c^{(i)}=j\}}{x}^{(i)}}{\sum _{i=1}^m{1}_{\{c^{(i)}=j\}}}=\frac{1}{n}\sum _{i=1}^m{1}_{\{c^{(i)}=j\}}{x}^{(i)}\end{array}$$

III) K-means algorithm

Figure 2: Training examples are shown as dots, and cluster centroids are shown as crosses

• a. Original dataset.
• b. Random initial cluster centroids (in this instance, not chosen to be equal to two training examples).
• (c-f). Illustration of running two iterations of k-means. In each iteration, we assign each training example to the closest cluster centroid (shown by "painting" the training examples the same color as the cluster centroid to which is assigned); then we move each cluster centroid to the mean of the points assigned to it.

Is the k-means algorithm guaranteed to converge? Yes it is, in a certain sense. In particular, let us define the distortion function to be:

$$\boxed{{\displaystyle J(c,\mu )=\sum _{i=1}^m\Vert x^{(i)}-{\mu }_{c^{(i)}}{\Vert }^2}}$$

where

${\mu }_{c^{(i)}}$ is cluster centroid of the cluster to which example

$x^{(i)}$ has been assigned.

It can be shown that k-means is exactly coordinate descent on

$J$.

The distortion function

$J$ is a non-convex function, and so coordinate descent on

$J$ is not guaranteed to converge to the global minimum. In other words, k-means can be susceptible to local optima. Very often k-means will work fine and come up with very good clusterings despite this. But if you are worried about getting stuck in bad local minima, one common thing to do is run k-means many times (using different random initial values for the cluster centroids

${\mu }_j$). Then, out of all the different clusterings found, pick the one that gives the lowest distortion

$J(c,\mu )$.

What is coordinate descent ?

Coordinate descent is an optimization algorithm that find the minimum of a function by minimizing one parameters at the time while holding others fixed.

In the case of distortion function,

$J(c,\mu )$, we will do the following:

$\text{Repeat until J converges {}$

$$\text{1. minimizes J with respect to }c\text{ while holding }\mu \text{ fixed.}$$

$$\text{2. minimizes }J\text{ with respect to }\mu \text{ while holding }c\text{ fixed.}$$

$\}$

Thus,

$J$ must monotonically decrease, and the value of

$J$ must converge. (Usually, this implies that

$c$ and

$\mu$ will converge too).