K-Means

1 Introduction

Recall that in clustering, we want to divide a dataset into groups of points that are close to each other. In this page, we introduce K-means, one of the simplest and most widely used clustering algorithms.

K-means aims to divide the data into \(K\) clusters, where we choose \(K\) before running the algorithm. Each point belongs to exactly one cluster. Each cluster has a centre, called its centroid. For K-means, the centroid of each cluster is the average of its assigned points.

To find a clustering, K-means must answer two questions. The first is about the cluster assignments. Which cluster does each point belong to? The second is about the centroids. Where should the centroid of each cluster be?

The two questions depend on each other. If we knew the assignments, we could compute the centroids by averaging the points in each cluster. If we knew the centroids, we could compute the assignments by assigning each point to the cluster with the closest centroid. Each answer requires the other, so this is a chicken and egg problem. At the start, we know neither the assignments nor the centroids, so we cannot directly compute either one.

K-means gets around this problem by starting with an initial guess for the centroids. Given the guessed centroids, we can compute the assignments. Given those assignments, we can compute new centroids. We then alternate between the two computations until the answers stop changing.

2 How K-Means Works

This idea leads us to the following outline of the K-means algorithm, which partitions a dataset into \(K\) clusters.

  1. Initialize the \(K\) centroids randomly.
  2. Repeat until convergence.
    1. Assignment step: Assign each point to the cluster with the closest centroid.
    2. Refitting step: Update each centroid to be the average of its assigned points.

Note that this is an outline only because we haven’t described what convergence means. We will come back to this topic in a later section.

Let’s run one iteration of K-means by hand. Consider the following dataset with six points.

\[ \begin{aligned} \left\{ \mathbf{x}^{(1)}, \ldots, \mathbf{x}^{(6)} \right\} & = \left\{ \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 2 \\ 1 \end{bmatrix}, \begin{bmatrix} 3 \\ 3 \end{bmatrix}, \begin{bmatrix} 5 \\ 4 \end{bmatrix}, \begin{bmatrix} 6 \\ 5 \end{bmatrix}, \begin{bmatrix} 6 \\ 3 \end{bmatrix} \right\} \end{aligned} \]

We use \(K = 2\) clusters. Suppose that the initial centroids \(\mathbf{m}_1\) and \(\mathbf{m}_2\) are as follows.

\[ \begin{aligned} & \mathbf{m}_1 = \begin{bmatrix} 1 \\ 3 \end{bmatrix}, \qquad \mathbf{m}_2 = \begin{bmatrix} 4 \\ 4 \end{bmatrix} \end{aligned} \]

Six Points and Two Initial Centroids

Figure 1: The six data points are shown as blue circles. The initial centroids are shown as a brown circle and a green triangle.

Question: Starting from Figure 1, perform the assignment step. Which points are assigned to cluster 1, and which points are assigned to cluster 2?

Answer:

For each point, we compute its distance to each centroid and assign the point to the closer centroid. Comparing squared distances gives the same answer as comparing distances, so we skip the square roots. For example, the squared distances from \(\mathbf{x}^{(3)}\) to the two centroids are as follows.

\[ \begin{aligned} & \text{to } \mathbf{m}_1\text{:} \quad (3 - 1)^2 + (3 - 3)^2 = 4 \\ & \text{to } \mathbf{m}_2\text{:} \quad (3 - 4)^2 + (3 - 4)^2 = 2 \end{aligned} \]

The point \(\mathbf{x}^{(3)}\) is closer to \(\mathbf{m}_2\), so it is assigned to cluster 2. The table below gives the squared distances for all six points.

Point Squared distance to \(\mathbf{m}_1\) Squared distance to \(\mathbf{m}_2\) Cluster
\(\mathbf{x}^{(1)}\) 4 18 1
\(\mathbf{x}^{(2)}\) 5 13 1
\(\mathbf{x}^{(3)}\) 4 2 2
\(\mathbf{x}^{(4)}\) 17 1 2
\(\mathbf{x}^{(5)}\) 29 5 2
\(\mathbf{x}^{(6)}\) 25 5 2

Points \(\mathbf{x}^{(1)}\) and \(\mathbf{x}^{(2)}\) are assigned to cluster 1. Points \(\mathbf{x}^{(3)}\), \(\mathbf{x}^{(4)}\), \(\mathbf{x}^{(5)}\), and \(\mathbf{x}^{(6)}\) are assigned to cluster 2.

Assignments After the First Assignment Step

Figure 2: Each point is drawn with the marker of its cluster. Points in cluster 1 are brown circles, and points in cluster 2 are green triangles.

Question: Continuing from the previous exercise, perform the refitting step. What are the new centroids?

Answer:

We recompute each centroid as the average of its assigned points, by taking the average of each coordinate separately. For example, the first coordinate of the centroid is the average of the first coordinates of its assigned points.

Cluster 1 contains points \(\mathbf{x}^{(1)}\) and \(\mathbf{x}^{(2)}\). Cluster 2 contains points \(\mathbf{x}^{(3)}\), \(\mathbf{x}^{(4)}\), \(\mathbf{x}^{(5)}\), and \(\mathbf{x}^{(6)}\).

\[ \begin{aligned} & \mathbf{m}_1 = \begin{bmatrix} (1 + 2) / 2 \\ (1 + 1) / 2 \end{bmatrix} = \begin{bmatrix} 1.5 \\ 1 \end{bmatrix} \\ & \mathbf{m}_2 = \begin{bmatrix} (3 + 5 + 6 + 6) / 4 \\ (3 + 4 + 5 + 3) / 4 \end{bmatrix} = \begin{bmatrix} 5 \\ 3.75 \end{bmatrix} \end{aligned} \]

Centroids After the First Refitting Step

Figure 3: The six data points are shown as blue circles. The new centroids are shown as a brown circle and a green triangle.

Notice that the new centroids do not depend on where the old centroids were. The refitting step uses only the current assignments.

Question: Perform a second assignment step using the new centroids. Do any assignments change? Has K-means converged?

Answer:

The squared distances to the new centroids are given below.

Point Squared distance to \(\mathbf{m}_1\) Squared distance to \(\mathbf{m}_2\) Cluster
\(\mathbf{x}^{(1)}\) 0.25 23.5625 1
\(\mathbf{x}^{(2)}\) 0.25 16.5625 1
\(\mathbf{x}^{(3)}\) 6.25 4.5625 2
\(\mathbf{x}^{(4)}\) 21.25 0.0625 2
\(\mathbf{x}^{(5)}\) 36.25 2.5625 2
\(\mathbf{x}^{(6)}\) 24.25 1.5625 2

No assignments change. The next refitting step would compute the same centroids, so K-means has converged after one iteration.

3 K-Means Formally

We now know how to run K-means by hand. Next, we describe K-means formally using mathematics. The formal description tells us what objective K-means is optimizing, and it shows how the assignment and refitting steps work together to optimize this objective one step at a time.

Consider a dataset of \(N\) points, where each point has \(D\) features. We write the points as follows.

\[ \begin{aligned} & \mathbf{x}^{(1)}, \mathbf{x}^{(2)}, \ldots, \mathbf{x}^{(N)} \in \mathbb{R}^D \end{aligned} \]

We want to partition the data into \(K\) clusters, where \(K\) is chosen in advance. To define this partition, we need to determine two things. These are the centroid of each cluster and the cluster that each point belongs to.

Let the vector \(\mathbf{m}_k\) denote the centroid of cluster \(k\). Each centroid is a point in the same space as the data.

\[ \begin{aligned} & \mathbf{m}_k \in \mathbb{R}^D, \quad k = 1, \ldots, K \end{aligned} \]

Let the vector \(\mathbf{r}^{(i)}\) denote the cluster assignment of point \(\mathbf{x}^{(i)}\). This vector has one entry per cluster, and its \(k\)-th entry \(r_k^{(i)}\) indicates whether point \(\mathbf{x}^{(i)}\) belongs to cluster \(k\).

\[ \begin{aligned} & r_k^{(i)} = \begin{cases} 1 & \text{if } \mathbf{x}^{(i)} \text{ is assigned to cluster } k, \\ 0 & \text{otherwise.} \end{cases} \end{aligned} \]

Since each point belongs to exactly one cluster, exactly one entry of \(\mathbf{r}^{(i)}\) is 1 and the rest are 0. In other words, \(\mathbf{r}^{(i)}\) is a one-hot vector. For example, with \(K = 3\) clusters, a point assigned to cluster 2 has the following assignment vector.

\[ \begin{aligned} & \mathbf{r}^{(i)} = \begin{bmatrix} 0 & 1 & 0 \end{bmatrix}^\top \end{aligned} \]

Given this notation, we define the cost function \(\mathcal{E}\) as follows.

\[ \begin{aligned} & \mathcal{E}(\{\mathbf{m}_k\}, \{\mathbf{r}^{(i)}\}) = \sum_{i=1}^N \sum_{k=1}^K r_k^{(i)} \, \| \mathbf{m}_k - \mathbf{x}^{(i)} \|^2 \end{aligned} \]

K-means aims to minimize this cost function over all centroids and all assignments.

\[ \begin{aligned} & \min_{\{\mathbf{m}_k\}, \{\mathbf{r}^{(i)}\}} \; \mathcal{E}(\{\mathbf{m}_k\}, \{\mathbf{r}^{(i)}\}) \end{aligned} \]

Since each assignment vector is one-hot, only one term of the inner sum survives for each point, so the cost is the total squared distance between each point and its assigned centroid. In other words, the cost measures how tightly each cluster’s points sit around its centroid. This is the same as adding up the variance of each cluster, weighted by the number of points in it. Minimizing the cost therefore makes the clusters as compact as possible.

If attempt to optimize this cost function directly, we may run into two challenges. First, it is not feasible to optimize this cost function by brute force, which means trying every trying every possible assignment and keeping the best one. Each of the \(N\) points can go into any of the \(K\) clusters, so there are \(K^N\) possible assignments, which is far too many to check even for small datasets. Alternatively, we can attempt to minimize the cost with gradient descent. Gradient descent needs parameters that can change smoothly, but each assignment \(r_k^{(i)}\) can only be 0 or 1, so we cannot take a gradient with respect to the assignments.

Fortunately, the assignment and refitting steps from our outline suggest a much more feasible approach. Instead of minimizing over the centroids and the assignments at the same time, we can alternate between them. We keep one fixed and minimize the cost with respect to the other. This method is called block coordinate descent, and it is an alternative to gradient descent. Block coordinate descent splits the variables into groups, called blocks, and minimizes the cost with respect to one block at a time while keeping the other blocks fixed. For K-means, the two blocks are the centroids and the assignments.

In the next two sections, we will derive each step and show that it minimizes the cost with respect to one block while the other block stays fixed. In fact, K-means was invented well before the cost function was written down in this form.

3.1 Deriving The Assignment Step

Recall that, during the assignment step, we hold the centroids fixed and assign each point to the cluster with the closest centroid. Mathematically, we can express this step as follows:

\[ \begin{aligned} & r_{k}^{(i)} = \left\{ \begin{array}{ll} 1 & \mbox{if } k = \arg\min_j\|{\bf x}^{(i)} - {\bf m}_j\|^2 \\ 0 & \mbox{otherwise} \end{array} \right\} \end{aligned} \tag{1}\]

Intuitively, the math expression above says: For point \(i\), calculate the distance between the point and every centroid \(\mathbf{m}_j\), given by \(\|{\bf x}^{(i)} - {\bf m}_j\|\) and pick the centroid that minimizes this distance.

Please complete the exercise before to practice expressing the assignments using formal notation.

Question: Using the data set in Figure 1, write down the updated assignment vectors \({\bf r}^{(i)}\) after performing the assignment step for the first time.

Answer:

For each point, we compute its squared distance to each centroid and assign the point to the closer centroid. Recall that the initial centroids are as follows.

\[ \begin{aligned} & \mathbf{m}_1 = \begin{bmatrix} 1 \\ 3 \end{bmatrix}, \qquad \mathbf{m}_2 = \begin{bmatrix} 4 \\ 4 \end{bmatrix} \end{aligned} \]

The squared distances and the resulting assignment vectors are as follows.

\[ \begin{aligned} \mathbf{x}^{(1)}\text{:} & \quad \|\mathbf{x}^{(1)} - \mathbf{m}_1\|^2 = 4 \lt \|\mathbf{x}^{(1)} - \mathbf{m}_2\|^2 = 18 \implies \mathbf{r}^{(1)} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \\[0.5em] \mathbf{x}^{(2)}\text{:} & \quad \|\mathbf{x}^{(2)} - \mathbf{m}_1\|^2 = 5 \lt \|\mathbf{x}^{(2)} - \mathbf{m}_2\|^2 = 13 \implies \mathbf{r}^{(2)} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \\[0.5em] \mathbf{x}^{(3)}\text{:} & \quad \|\mathbf{x}^{(3)} - \mathbf{m}_1\|^2 = 4 \gt \|\mathbf{x}^{(3)} - \mathbf{m}_2\|^2 = 2 \implies \mathbf{r}^{(3)} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} \\[0.5em] \mathbf{x}^{(4)}\text{:} & \quad \|\mathbf{x}^{(4)} - \mathbf{m}_1\|^2 = 17 \gt \|\mathbf{x}^{(4)} - \mathbf{m}_2\|^2 = 1 \implies \mathbf{r}^{(4)} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} \\[0.5em] \mathbf{x}^{(5)}\text{:} & \quad \|\mathbf{x}^{(5)} - \mathbf{m}_1\|^2 = 29 \gt \|\mathbf{x}^{(5)} - \mathbf{m}_2\|^2 = 5 \implies \mathbf{r}^{(5)} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} \\[0.5em] \mathbf{x}^{(6)}\text{:} & \quad \|\mathbf{x}^{(6)} - \mathbf{m}_1\|^2 = 25 \gt \|\mathbf{x}^{(6)} - \mathbf{m}_2\|^2 = 5 \implies \mathbf{r}^{(6)} = \begin{bmatrix} 0 \\ 1 \end{bmatrix} \end{aligned} \]

Points \(\mathbf{x}^{(1)}\) and \(\mathbf{x}^{(2)}\) are assigned to cluster 1, and the other four points are assigned to cluster 2. These are the same assignments shown in Figure 2.

Let’s now use mathematical derivations to confirm that picking the closest centroid for each point indeed minimizes the cost function given fixed centroids. Since the derivation is a bit involved, we will break it down into several steps below.

First, we note that given fixed centroids, minimizing the cost function is the same as minimizing each point’s contribution to the cost function separately. Below, we will elaborate on this point and write down the simplified optimization for point \(i\).

Recall that the cost function is defined as follows.

\[ \begin{aligned} & \mathcal{E}(\{\mathbf{m}_k\}, \{\mathbf{r}^{(i)}\}) = \sum_{i=1}^N \sum_{k=1}^K r_k^{(i)} \, \| \mathbf{m}_k - \mathbf{x}^{(i)} \|^2 \end{aligned} \]

The cost function is a sum of one contribution per point. The contribution of point \(i\) depends only on its own assignment \(\mathbf{r}^{(i)}\). We can see this by writing out the contributions of two points \(1\) and \(2\).

\[ \begin{aligned} \mathcal{E}(\{\mathbf{m}_k\}, \{\mathbf{r}^{(i)}\}) & = \underbrace{\sum_{k=1}^{K} r_k^{(1)}\|\mathbf{m}_k-\mathbf{x}^{(1)}\|^2}_{\text{contribution of point } 1\text{, depends only on } \mathbf{r}^{(1)}} + \underbrace{\sum_{k=1}^{K} r_k^{(2)}\|\mathbf{m}_k-\mathbf{x}^{(2)}\|^2}_{\text{contribution of point } 2\text{, depends only on } \mathbf{r}^{(2)}} + \cdots \end{aligned} \]

The constraints on \(\mathbf{r}^{(i)}\) also involve only point \(i\). So we can minimize \(\mathcal{E}(\{\mathbf{m}_k\}, \{\mathbf{r}^{(i)}\})\) by minimizing each point’s contribution separately.

Therefore, it is sufficient for us to solve the simplified problem below for each point \(i\):

\[ \begin{aligned} & \min_{\mathbf{r}^{(i)}}\ \sum_{k=1}^{K} r_k^{(i)}\|\mathbf{m}_k-\mathbf{x}^{(i)}\|^2 \quad\text{subject to}\quad r_k^{(i)}\in\{0,1\}, \quad \sum_{k=1}^{K}r_k^{(i)}=1. \end{aligned} \tag{2}\]

Next, let’s take a closer look at Equation 2 and figure out what the simplified optimization problem for point \(i\) looks like if point \(i\) is assigned to cluster \(j\).

Because \(\mathbf{r}^{(i)}\) is one-hot, exactly one term in the sum is nonzero. If point \(i\) is assigned to cluster \(j\), then \(r_j^{(i)}=1\) and every other \(r_k^{(i)}=0\), so the contribution reduces to the contribution from cluster \(j\) only.

\[ \begin{aligned} & \sum_{k=1}^{K} r_k^{(i)}\|\mathbf{m}_k-\mathbf{x}^{(i)}\|^2 =\|\mathbf{m}_j-\mathbf{x}^{(i)}\|^2. \end{aligned} \]

Choosing \(\mathbf{r}^{(i)}\) is the same as choosing a cluster \(j\), so the problem for point \(i\) becomes

\[ \begin{aligned} & \min_{j\in\{1,\dots,K\}}\ \|\mathbf{m}_j-\mathbf{x}^{(i)}\|^2. \end{aligned} \]

Finally, we can now explain why minimizing the cost function is equivalent to assigning each point to the closest cluster.

By the previous step, the contribution of point \(i\) is the squared distance from \(\mathbf{x}^{(i)}\) to the centroid of its assigned cluster. This is smallest when the point is assigned to the cluster whose centroid is nearest to \(\mathbf{x}^{(i)}\). Since each point’s contribution is minimized separately, assigning every point to its nearest centroid minimizes \(\mathcal{E}(\{\mathbf{m}_k\}, \{\mathbf{r}^{(i)}\})\). This gives us the assignment step equations in Equation 1.

3.2 Deriving The Refitting Step

Next, let’s derive the equations for the refitting step. Recall that, during the refitting step, we hold the assignments fixed and update each centroid to be the average of its assigned points. Mathematically, we can express the refitting step as follows:

\[ \begin{aligned} & \mathbf{m}_k = \frac{\sum_{i=1}^N r_k^{(i)} \mathbf{x}^{(i)}}{\sum_{i=1}^N r_k^{(i)}} \end{aligned} \tag{3}\]

The indicator variable \(r_k^{(i)}\) ensures that only the points assigned to cluster \(k\) appears in the expression above. Therefore, it computes the average of the points assigned to centroid \(\mathbf{m}_k\).

Please complete the exercise below to practice computing the updated centroid.

Question: Consider the example in Figure 1 after executing the assignment step once. Points \(\mathbf{x}^{(1)}\) and \(\mathbf{x}^{(2)}\) are assigned to cluster 1, and the other four points are assigned to cluster 2. Use Equation 3 to perform the refitting step. What are the new positions of each centroid after refitting?

Answer:

For cluster 1, the assignments are 1 for \(\mathbf{x}^{(1)}\) and \(\mathbf{x}^{(2)}\) and 0 for the other points. So the numerator sums \(\mathbf{x}^{(1)}\) and \(\mathbf{x}^{(2)}\), and the denominator counts the two assigned points.

\[ \begin{aligned} & \mathbf{m}_1 = \frac{1}{2} \left( \begin{bmatrix} 1 \\ 1 \end{bmatrix} + \begin{bmatrix} 2 \\ 1 \end{bmatrix} \right) = \begin{bmatrix} 1.5 \\ 1 \end{bmatrix} \end{aligned} \]

For cluster 2, the assignments are 1 for \(\mathbf{x}^{(3)}\), \(\mathbf{x}^{(4)}\), \(\mathbf{x}^{(5)}\), and \(\mathbf{x}^{(6)}\) and 0 for the other points. So the numerator sums these four points, and the denominator counts the four assigned points.

\[ \begin{aligned} & \mathbf{m}_2 = \frac{1}{4} \left( \begin{bmatrix} 3 \\ 3 \end{bmatrix} + \begin{bmatrix} 5 \\ 4 \end{bmatrix} + \begin{bmatrix} 6 \\ 5 \end{bmatrix} + \begin{bmatrix} 6 \\ 3 \end{bmatrix} \right) = \begin{bmatrix} 5 \\ 3.75 \end{bmatrix} \end{aligned} \]

These are the same centroids we computed by hand, shown in Figure 3.

Let’s now write a derivation to show that updating each centroid to be the mean of its assigned points minimizes the cost function give fixed assignments.

To start, we take the gradient of the cost function with respect to one centroid \(\mathbf{m}_j\) while holding the assignments fixed. We then set the gradient to zero and solve for \(\mathbf{m}_j\).

Recall that the cost function is as follows.

\[ \begin{aligned} & \mathcal{E}(\{\mathbf{m}_k\}, \{\mathbf{r}^{(i)}\}) = \sum_{i=1}^N \sum_{k=1}^K r_k^{(i)} \, \| \mathbf{m}_k - \mathbf{x}^{(i)} \|^2 \end{aligned} \]

To start, we will take the gradient of the cost function and move the gradient inside the summation.

\[ \begin{aligned} \nabla_{\mathbf{m}_j} \sum_{i=1}^N \sum_{k=1}^K r_k^{(i)} \, \| \mathbf{m}_k - \mathbf{x}^{(i)} \|^2 & = \sum_{i=1}^N \sum_{k=1}^K r_k^{(i)} \, \nabla_{\mathbf{m}_j} \| \mathbf{m}_k - \mathbf{x}^{(i)} \|^2 \end{aligned} \]

Next, let’s take a closer look at the inner summation. Note that only the terms with \(k = j\) depend on \(\mathbf{m}_j\). Every term with \(k \neq j\) involves a different centroid, which is a constant with respect to \(\mathbf{m}_j\), so its gradient is zero. The inner sum therefore keeps only the term for cluster \(j\).

\[ \begin{aligned} \nabla_{\mathbf{m}_j} \sum_{i=1}^N \sum_{k=1}^K r_k^{(i)} \, \| \mathbf{m}_k - \mathbf{x}^{(i)} \|^2 & = \sum_{i=1}^N r_j^{(i)} \, \nabla_{\mathbf{m}_j} \| \mathbf{m}_j - \mathbf{x}^{(i)} \|^2 \end{aligned} \]

Then, we compute the gradient of the squared distance. The squared distance is a sum of squared differences over the \(D\) coordinates. Let \(m_{j,d}\) represent the \(d\)-th coordinate of centroid \(\mathbf{m}_j\) and \(x_d^{(i)}\) denote the \(d\)-th coordinate of \(\mathbf{x}^{(i)}\).

\[ \begin{aligned} \| \mathbf{m}_j - \mathbf{x}^{(i)} \|^2 = \sum_{d=1}^D \left( m_{j,d} - x_d^{(i)} \right)^2 \end{aligned} \]

Only the term for coordinate \(d\) depends on \(m_{j,d}\), so the partial derivative with respect to \(m_{j,d}\) is as follows.

\[ \begin{aligned} \frac{\partial}{\partial m_{j,d}} \| \mathbf{m}_j - \mathbf{x}^{(i)} \|^2 = 2 \left( m_{j,d} - x_d^{(i)} \right) \end{aligned} \]

Stacking these partial derivatives into a vector gives the gradient.

\[ \begin{aligned} \nabla_{\mathbf{m}_j} \| \mathbf{m}_j - \mathbf{x}^{(i)} \|^2 = 2 \left( \mathbf{m}_j - \mathbf{x}^{(i)} \right) \end{aligned} \]

Substituting this result back, we get the gradient of the cost function with respect to \(\mathbf{m}_j\).

\[ \begin{aligned} \nabla_{\mathbf{m}_j} \mathcal{E}(\{\mathbf{m}_k\}, \{\mathbf{r}^{(i)}\}) & = 2 \sum_{i=1}^N r_j^{(i)} \left( \mathbf{m}_j - \mathbf{x}^{(i)} \right) \end{aligned} \]

Finally, we set the gradient to zero and solve for \(\mathbf{m}_j\).

\[ \begin{aligned} 2 \sum_{i=1}^N r_j^{(i)} \left( \mathbf{m}_j - \mathbf{x}^{(i)} \right) & = \mathbf{0} \\[0.5em] \sum_{i=1}^N r_j^{(i)} \mathbf{m}_j - \sum_{i=1}^N r_j^{(i)} \mathbf{x}^{(i)} & = \mathbf{0} \\[0.5em] \mathbf{m}_j \sum_{i=1}^N r_j^{(i)} & = \sum_{i=1}^N r_j^{(i)} \mathbf{x}^{(i)} \\[0.5em] \mathbf{m}_j & = \frac{\sum_{i=1}^N r_j^{(i)} \mathbf{x}^{(i)}}{\sum_{i=1}^N r_j^{(i)}} \end{aligned} \]

This gives us the refitting step in Equation 3 for cluster \(j\). Note that the cost function is a sum of squared distances with nonnegative weights, so it is convex in \(\mathbf{m}_j\). Therefore, the point where the gradient is zero is a minimum, not a maximum or a saddle point.

The refitting step doesn’t need the previous centroids at all. Unlike gradient descent, which takes a small step away from the previous position, refitting moves each centroid straight to the mean of its assigned points.

3.3 The K-Means Algorithm Formally

Now, having derive the assignment and refitting steps mathematically, we will present an updated outline of the K-means algorithm as follows.

Consider a dataset of \(N\) points, where each point has \(D\) features, denoted below. \[ \begin{aligned} & \{ \mathbf{x}^{(1)}, \mathbf{x}^{(2)}, \ldots, \mathbf{x}^{(N)} \} \in \mathbb{R}^D \end{aligned} \]

We want to partition the data into \(K\) clusters. Let \(\mathbf{m}_k \in \mathbb{R}^D\) denote the centroid of cluster \(k\). The assignment \(r_k^{(i)}\) is 1 if point \(\mathbf{x}^{(i)}\) is assigned to cluster \(k\), and 0 otherwise. Each point is assigned to exactly one cluster.

  1. Initialize the \(K\) centroids randomly.
  2. Repeat until convergence.
    1. Assignment step: Assign each point to the cluster with the closest centroid. For each point \(i\) and each cluster \(k\), we set the assignment as follows.

      \[ \begin{aligned} & r_k^{(i)} = \begin{cases} 1 & \text{if } k = \arg\min_j \| \mathbf{x}^{(i)} - \mathbf{m}_j \|^2, \\ 0 & \text{otherwise.} \end{cases} \end{aligned} \]

    2. Refitting step: Update each centroid to be the average of its assigned points. For each cluster \(k\), we set the centroid as follows.

      \[ \begin{aligned} & \mathbf{m}_k = \frac{\sum_{i=1}^N r_k^{(i)} \mathbf{x}^{(i)}}{\sum_{i=1}^N r_k^{(i)}} \end{aligned} \]

4 Convergence of K-Means

Our updated outline of K-means still leaves two open questions. First, is K-means guaranteed to converge? Second, if it does converge, is it guaranteed to find the clustering with the lowest possible cost? Let’s explore these two questions one by one.

4.1 Is K-Means Guaranteed to Converge?

Before we can answer the first question, we need to fill in one missing piece of the outline. What does it mean for K-means to converge, and more broadly, when should we stop running it? In practice, we usually say that K-means has converged when the assignments stop changing. We could also stop K-means before it converges, for example, after a maximum number of iterations or when we run out of time or compute.

Suppose that we stop K-means when the assignments stop changing. Let’s complete the following exercise to prove or disprove the K-means algorithm has converged.

Question: Consider a dataset with the following six points.

\[ \begin{aligned} & \left\{ \mathbf{x}^{(1)}, \ldots, \mathbf{x}^{(6)} \right\} = \left\{ \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \begin{bmatrix} 2 \\ 3 \end{bmatrix}, \begin{bmatrix} 4 \\ 4 \end{bmatrix}, \begin{bmatrix} 4 \\ 5 \end{bmatrix}, \begin{bmatrix} 3 \\ 2 \end{bmatrix}, \begin{bmatrix} 2 \\ 4 \end{bmatrix} \right\} \end{aligned} \]

We are running K-means with \(K = 2\) clusters. Currently, points \(\mathbf{x}^{(1)}\) and \(\mathbf{x}^{(5)}\) are assigned to cluster 1, and the other four points are assigned to cluster 2. The current centroids are as follows.

\[ \begin{aligned} & \mathbf{m}_1 = \begin{bmatrix} 2 \\ 2 \end{bmatrix}, \qquad \mathbf{m}_2 = \begin{bmatrix} 3 \\ 4 \end{bmatrix} \end{aligned} \]

Six Points and Their Current Clusters

Figure 4: Each point is drawn with the marker of its current cluster. Points in cluster 1 are brown circles, and points in cluster 2 are green triangles. The current centroids are shown with a black outline.

Has K-means converged? Justify your answer.

Answer:

No, K-means has not converged. K-means has converged only if the assignments stop changing. We can perform the next assignment step and check whether any assignment changes. To prove that K-means has not converged, it is sufficient to find one point that will change its assignment after the assignment steps. With some experimentation, you should be able to determine that \(\mathbf{x}^{(2)}\) will change assignment since it is closer to centroid 1 than 2 as shown by the calculations below. \[ \begin{aligned} & \text{to } \mathbf{m}_1\text{:} \quad (2 - 2)^2 + (3 - 2)^2 = 1 \\ & \text{to } \mathbf{m}_2\text{:} \quad (2 - 3)^2 + (3 - 4)^2 = 2 \end{aligned} \]

Now that we have a convergence criterion for K-means, you might be wondering: is K-means guaranteed to converge? Or could it sometimes run forever?

To prove that K-means is guaranteed to converge, we will need to establish several properties. Please attempt each of the four exercises below yourself. After that, we will put them together into a formal proof.

Question: Explain why the assignment step cannot increase the total cost.

Answer:

During the assignment step, the centroids are fixed. Since each point is assigned to exactly one cluster, the total cost consists of contributions from the squared distances between each point and the centroid of its assigned cluster.

Let \(k^{(i)}\) denote the cluster that point \(\mathbf{x}^{(i)}\) is assigned to before the assignment step, and let \(\hat{k}^{(i)}\) denote the cluster it is assigned to after the assignment step. The assignment step picks the closest centroid for each point, so the new centroid is at least as close as the old one.

\[ \begin{aligned} & \| \mathbf{m}_{\hat{k}^{(i)}} - \mathbf{x}^{(i)} \|^2 \le \| \mathbf{m}_{k^{(i)}} - \mathbf{x}^{(i)} \|^2 \end{aligned} \]

In other words, no point’s contribution to the cost can go up. Adding up the contributions of all the points, the total cost cannot go up either.

Question: Explain why the refitting step cannot increase the total cost.

Answer:

During the refitting step, the assignments are fixed. We can group the terms of the cost function by cluster, so the total cost is a sum of one contribution per cluster. The contribution of cluster \(k\) is the sum of the squared distances from its assigned points to its centroid.

\[ \begin{aligned} & \mathcal{E}(\{\mathbf{m}_k\}, \{\mathbf{r}^{(i)}\}) = \sum_{k=1}^K \underbrace{\sum_{i=1}^N r_k^{(i)} \, \| \mathbf{m}_k - \mathbf{x}^{(i)} \|^2}_{\text{contribution of cluster } k} \end{aligned} \]

The contribution of cluster \(k\) depends only on its own centroid \(\mathbf{m}_k\). When we derived the refitting step, we showed that the mean of the assigned points in Equation 3 minimizes this contribution. The old centroid is just one possible choice for \(\mathbf{m}_k\), so moving the centroid to the mean gives a contribution that is at most as large as before. If a cluster has no assigned points, its centroid stays where it is and its contribution stays at zero.

In other words, no cluster’s contribution to the cost can go up. Adding up the contributions of all the clusters, the total cost cannot go up either.

Question: Explain why the assignment step strictly decreases the total cost if at least one point changes its assignment.

Assume that during the assignment step, ties are broken by keeping a point in its current cluster. In other words, a point changes clusters only if another centroid is strictly closer than its current centroid.

Answer:

As before, let \(k^{(i)}\) denote the cluster that point \(\mathbf{x}^{(i)}\) is assigned to before the assignment step, and let \(\hat{k}^{(i)}\) denote the cluster it is assigned to after the assignment step.

If point \(\mathbf{x}^{(i)}\) keeps its assignment, its contribution to the cost stays the same. If point \(\mathbf{x}^{(i)}\) changes its assignment, the tie-breaking rule tells us that its new centroid is strictly closer than its old centroid. So its contribution strictly decreases.

\[ \begin{aligned} & \| \mathbf{m}_{\hat{k}^{(i)}} - \mathbf{x}^{(i)} \|^2 \lt \| \mathbf{m}_{k^{(i)}} - \mathbf{x}^{(i)} \|^2 \end{aligned} \]

The total cost is the sum of the contributions of all the points. No contribution goes up, and at least one contribution strictly goes down, so the total cost strictly decreases.

Question: Explain why the number of possible assignments is finite.

Answer:

An assignment specifies which cluster each point belongs to. Each of the \(N\) points can be assigned to any one of the \(K\) clusters. Since the choices for different points are independent, the total number of possible assignments is as follows.

\[ \begin{aligned} & \underbrace{K \times K \times \cdots \times K}_{N \text{ points}} = K^N \end{aligned} \]

Since \(N\) and \(K\) are both finite, \(K^N\) is also finite.

Let’s put the properties above together into a formal proof.

Theorem (Convergence of K-means): Suppose that, during the assignment step, ties are broken by keeping a point in its current cluster. Then K-means converges after a finite number of iterations.

Proof: There are only finitely many possible assignments. If K-means never returns to an assignment it has already visited, then in the worst case it moves through every possible assignment once and then stops.

It remains to show that K-means cannot return to an assignment it has already visited. Consider the current assignment and an earlier assignment that K-means visited before.

The earlier assignment cannot have a strictly lower total cost than the current assignment. If this is the case, then K-means moved to an assignment with a higher cost at some point, which is impossible.

If the earlier assignment has a strictly higher cost than the current assignment, K-means will not revisit the earlier assignment because neither assignment nor refitting can increase the total cost.

Finally, the earlier assignment has the same total cost as the current assignment, based on the tie-breaking rule, K-means will remain at the current assignment and will not return to the earlier assignment. \(\blacksquare\)

To summarize, the total cost strictly decreases whenever the assignments change, and K-means is guaranteed to terminate after exploring at most a finite number of assignments.

4.2 Is K-Means Guaranteed to Converge to the Global Minimum?

Now that we know that K-means is guaranteed to converge, let’s explore our second question. Is K-means guaranteed to find the clustering with the lowest total cost? Let’s explore this question using Figure 5 below. Start by clicking on the plot to initialize at least two centroids, and then click on the Step button until the algorithm has converged.

K-Means, One Step at a Time

Figure 5: Interactive: Click on the plot to place up to five centroids. Press “Step” to run one step of K-means, which alternates between the assignment and refitting steps. Press “Clear All” to remove all centroids and restore the original point appearance.

Question: Try different initializations in Figure 5 above. Can you find two initializations with the same number of centroids that converge to different clusterings?

Answer:

One example is given below.

\[ \begin{aligned} \text{Initialization 1:} & \quad \begin{bmatrix} 14 \\ 16 \end{bmatrix}, \quad \begin{bmatrix} 20 \\ 8 \end{bmatrix} \\[0.5em] \text{Initialization 2:} & \quad \begin{bmatrix} 20 \\ 16 \end{bmatrix}, \quad \begin{bmatrix} 16 \\ 10 \end{bmatrix} \end{aligned} \]

This example shows that K-means can converge to different clusterings with different total costs depending on where the centroids start. We will explore why this happens soon.

With some experimentation, you likely found two initializations that lead to different final clusterings with different total costs. This means that K-means is not guaranteed to find the clustering with the lowest total cost. For example, with \(K=3\), K-means can converge to either of the two clusterings in Figure 6, depending on where the centroids start.

Two Clusterings of the Leaf Data with 3 Clusters

Clustering A

Clustering B

Figure 6: The leaf dataset after running K-means with \(K=3\) from two different sets of initial centroids. Each point is coloured and shaped according to its assigned cluster. Centroids are shown with a bold black outline. Clustering A has a total cost of 564.94, and Clustering B has a total cost of 748.00.

Why does this happen? In general, the cost function is not convex and can have multiple local minima. K-means may converge to a local minimum that is not the global minimum. Both clusterings in Figure 6 are local minima, but Clustering B has a much higher total cost and is not the global minimum. In practice, we reduce this risk by running K-means several times with different random initializations and keeping the clustering with the lowest total cost.

Question: Consider a dataset with the following four points.

\[ \begin{aligned} & \left\{ \mathbf{x}^{(1)}, \ldots, \mathbf{x}^{(4)} \right\} = \left\{ \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 5 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 3 \end{bmatrix}, \begin{bmatrix} 5 \\ 3 \end{bmatrix} \right\} \end{aligned} \]

We are running K-means with \(K = 2\) clusters. Currently, points \(\mathbf{x}^{(1)}\) and \(\mathbf{x}^{(2)}\) are assigned to cluster 1, and points \(\mathbf{x}^{(3)}\) and \(\mathbf{x}^{(4)}\) are assigned to cluster 2. The current centroids are as follows.

\[ \begin{aligned} & \mathbf{m}_1 = \begin{bmatrix} 3 \\ 1 \end{bmatrix}, \qquad \mathbf{m}_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix} \end{aligned} \]

Four Points and Their Current Clusters

Figure 7: Each point is drawn with the marker of its current cluster. Points in cluster 1 are brown circles, and points in cluster 2 are green triangles. The current centroids are shown with a black outline.

Show that this clustering is a local minimum.

Answer:

To prove that this clustering is a local minimum, we need to check that performing the assignment step will not change any assignment. By computing the squared distance of each point to either centroid, we can show that each point is already assigned to its closest centroid and K-means has converged.

Question: Show that the clustering in Figure 7 is not a global minimum.

Answer:

To show that a clustering is not a global minimum, it is enough to find another clustering with a lower total cost.

The current clustering has a total cost of 16, as calculated below. \[ \begin{aligned} \mathcal{E}(\{\mathbf{m}_k\}, \{\mathbf{r}^{(i)}\}) & = \|\mathbf{m}_1 - \mathbf{x}^{(1)}\|^2 + \|\mathbf{m}_1 - \mathbf{x}^{(2)}\|^2 + \|\mathbf{m}_2 - \mathbf{x}^{(3)}\|^2 + \|\mathbf{m}_2 - \mathbf{x}^{(4)}\|^2 \\ & = \left\| \begin{bmatrix} 3 \\ 1 \end{bmatrix} - \begin{bmatrix} 1 \\ 1 \end{bmatrix} \right\|^2 + \left\| \begin{bmatrix} 3 \\ 1 \end{bmatrix} - \begin{bmatrix} 5 \\ 1 \end{bmatrix} \right\|^2 + \left\| \begin{bmatrix} 3 \\ 3 \end{bmatrix} - \begin{bmatrix} 1 \\ 3 \end{bmatrix} \right\|^2 + \left\| \begin{bmatrix} 3 \\ 3 \end{bmatrix} - \begin{bmatrix} 5 \\ 3 \end{bmatrix} \right\|^2 \\ & = 16 \end{aligned} \]

Consider the clustering with the two centroids below. This clustering groups the two left points together and the two right points together. \[ \begin{aligned} & \mathbf{m}_1 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \qquad \mathbf{m}_2 = \begin{bmatrix} 5 \\ 2 \end{bmatrix} \end{aligned} \]

The total cost of this alternative clustering is 4, which is less than 16. So the current clustering is not a global minimum. \[ \begin{aligned} \mathcal{E}(\{\mathbf{m}_k\}, \{\mathbf{r}^{(i)}\}) & = \|\mathbf{m}_1 - \mathbf{x}^{(1)}\|^2 + \|\mathbf{m}_2 - \mathbf{x}^{(2)}\|^2 + \|\mathbf{m}_1 - \mathbf{x}^{(3)}\|^2 + \|\mathbf{m}_2 - \mathbf{x}^{(4)}\|^2 \\ & = \left\| \begin{bmatrix} 1 \\ 2 \end{bmatrix} - \begin{bmatrix} 1 \\ 1 \end{bmatrix} \right\|^2 + \left\| \begin{bmatrix} 5 \\ 2 \end{bmatrix} - \begin{bmatrix} 5 \\ 1 \end{bmatrix} \right\|^2 + \left\| \begin{bmatrix} 1 \\ 2 \end{bmatrix} - \begin{bmatrix} 1 \\ 3 \end{bmatrix} \right\|^2 + \left\| \begin{bmatrix} 5 \\ 2 \end{bmatrix} - \begin{bmatrix} 5 \\ 3 \end{bmatrix} \right\|^2 \\ & = 4 \end{aligned} \]

Four Points and an Alternative Clustering

Figure 8: Each point is drawn with the marker of its cluster in the alternative clustering. Points in cluster 1 are brown circles, and points in cluster 2 are green triangles. The centroids are shown with a black outline.

5 Limitations of K-Means

K-means uses the Euclidean distance to measure how far each point is from its centroid, and the cost adds up these squared distances. Since, the Euclidean distance treats every direction the same, the points at a given distance from a centroid form a circle in two dimensions or a sphere in higher dimensions. So K-means implicitly assumes that each cluster is roughly spherical, with its points spread out equally in all directions.

As a result, K-means struggles to find clusters that are not spherical. For example, the data in Figure 9 below was generated from two Gaussian distributions. The top-left Gaussian is circular, while the bottom-right one is spread out horizontally and narrow vertically. Try running K-means with \(K=2\) in the figure. You will likely see that K-means does not split the points the way they were generated. Instead, it tends to assign the points to the top-left cluster even though they were generated from the bottom-right cluster.

A Troublesome Dataset for K-Means

Figure 9: The grey ellipses are the contours of the two Gaussians that generated the data, at 1, 2, and 3 standard deviations from each mean. The two centroids start at the means of the two Gaussians. Interactive: Press “Step” to run one step of K-means, which alternates between the assignment and refitting steps. Press “Reset” to move the centroids back to their starting positions and restore the original point appearance.

To get around this limitation, sometimes practitioners will deliberately set K to a higher value than necessary, and then join some of the clusters together after K-means has completed. We will not discuss such methods in detail, but you can observe how they might be useful by experimenting with the above figure with \(K=5\).

Instead, in the next part of this chapter, we will discuss Gaussian Mixture Models, which are naturally well-suited to finding such clusters, without the need for post-hoc adjustments.

6 Soft K-Means

Soft K-means is a less commonly used extension of K-means that relaxes the assumption that all data points must belong to exactly one cluster. Instead, each cluster has some amount of responsibility for each data point, in the range \([0,1]\), where a responsibility of 0 indicates that the point does not at all belong to the cluster, and a responsibility of 1 indicates that the point belongs entirely to the cluster. To implement this change, we reformulate each \({\bf r}^{(i)}\) so that instead of being one-hot, their values must sum to one, giving the responsibility of each cluster for point \(i\).

We would still like it to be the case that the closest cluster centres are the most responsible for a point, so we need a function for both scaling responsibility inversely with distance and ensuring that the sum of all responsibilities is one. The softmax function (introduced in Chapter 4) can accomplish this for us. We then adjust the Assignment and Refitting steps as follows.

In the Assignment step, each data point \(i\) is given a soft “degree of assignment” to each cluster mean \(k\), based on responsibilities.

\[ \begin{aligned} & r_k^{(i)} = \frac{\exp[-\beta \|{\bf m}_k- {\bf x}^{(i)}\|^2]}{\sum_{j=1}^K \exp[-\beta \|{\bf m}_j- {\bf x}^{(i)}\|^2]} \\ & \implies {\bf r}^{(i)} = \text{softmax}(-\beta \{\|{\bf m}_k- {\bf x}^{(i)}\|^2\}_{k=1}^K) \end{aligned} \]

In the Refitting step, the coordinates of each cluster centre are adjusted to match the sample means of the data points they are responsible for.

\[ \begin{aligned} & {\bf m}_k =\frac{\sum_i r_k^{(i)}{\bf x}^{(i)}}{\sum_i r_k^{(i)}} \end{aligned} \]

Here, \(\beta\) is a hyperparameter that determines the “hardness” of K-means. When \(\beta\) is small, we get more mixing of responsibilities, and as \(\beta \to \infty\), we get back our original one-hot \({\bf r}^{(i)}\).

We can now refer to our original formulation, in which each data point can only be assigned to one cluster, as “Hard K-means”. However, when you see a reference to just “K-means” in the wild, it is generally a reference to Hard K-means (the more commonly used method), unless otherwise specified. We will adopt the same convention here, referring to Soft K-means when necessary, and just K-means otherwise.

7 Summary

We have introduced K-means, the first of two unsupervised clustering methods in this chapter. Although the Gaussian Mixture Models (GMMs) that follow are strictly more powerful in the kinds of clusters that can be captured, K-means remains a popular method for its speed and simplicity. You will also see that many parts of GMMs are directly analogous to the concepts introduced in this section.