Ahmed Haroon

Clustering

K-Means Algorithm

For a given dataset

x^{(1)}, \ldots, x^{(n)}

without any labels

y^{(i)}

, clustering is the task of finding a partition of the data into subsets (clusters) such that the data points in the same cluster are more similar to each other than to those in other clusters. For this purpose, we usually use the k-means algorithm.

\text{Initialize cluster centroids } \mu_1, \ldots, \mu_k \text{ randomly}

\text{Repeat until convergence \{}

\hspace{2em} \text{For each } i, \text{ set } \text{\{}

\hspace{4em} c^{(i)} \leftarrow \arg \min_j \| x^{(i)} - \mu_j \|^2

\hspace{2em} \text{\}}

\hspace{2em} \text{For each } j, \text{ set } \text{\{}

\hspace{4em} \mu_j \leftarrow \frac{\sum_{i=1}^n 1\left\{c^{(i)} = j\right\} \, x^{(i)}}{\sum_{i=1}^n 1\left\{c^{(i)} = j\right\}}

\hspace{2em} \text{\}}

\text{\}}

The first loop gives us the centroid

c^{(i)}

that is closest to each data point

x^{(i)}

. The second loop updates the centroid

\mu_j

for each cluster

j

as the mean of all data points

x^{(i)}

assigned to that cluster.

The distortion function (that measures the sum of the squared distances between each data point and its assigned centroid) can be written as:

J(c, \mu) = \sum_{i=1}^n \| x^{(i)} - \mu_{c^{(i)}} \|^2

In each step of the k-means algorithm,

J

either decreases or stays the same. Therefore, the algorithm is guaranteed to converge. However, the convergence is not guaranteed to reach a global minimum since

J

is non-convex.