Skip to content

A reminder on K-means

Published:
• 7 min read
kmeans summary

Motivation

On November 6th, Meta unveiled e-means, claiming to outperform K-means in one-tenth the epochs: https://arxiv.org/abs/2611.09501

It got me curious and I felt like before reading their paper, I would jump back to reading about K-means again in order to fully understand their contribution. I didn’t really know what would be the best resource to revise this algorithm. But eventually while skimming through potential candidates, I have settled with watching this lecture on Youtube: https://youtu.be/LmpkKwsyQj4?si=5Fl5QCadtty5z-qB

It is a lecture from Dr. Anand Avati at Stanford (CS229). All the following will be based on his lecture and the notes I took while watching it.

On a personal note, I think we are extremely gifted to have such amazing content online for free, from the best universities in the world, just waiting out there for anyone to learn from!

So in the following part of this post, my goal is simply to put my notes into words regarding this algorithm and how it is presented in this lecture. I think it is a very good way for you to have a quick reminder on this algorithm and a great way for me to revise it again :)

Supervision or not?

Suppose we have a dataset of cheese images. After passing these through an encoder you would end up with one embedding xix_i for each of your images. This would results in the dataset X={x1,x2,…,xn}X = \{x_1, x_2, \ldots, x_n\}. In a supervised setting we would have a set of yiy_i associated with those xix_i. If you would like to formalize it, it could be Y={y1,y2,…,yn}Y = \{y_1, y_2, \ldots, y_n\}. If your goal is to know whether your cheeses are hard or soft, this supervision could be yi∈{hard,soft}y_i ∈ \{\text{hard}, \text{soft}\}.

However for K-means, we are working in an unsupervised setting, which means that in our case we only have XX and our goal is to figure out some interesting structure in our data in the absence of supervision (i.e in the absence of YY). Figure 1 showcases the difference between the two settings.

supervised vs unsupervised
Figure 1: Supervised vs Unsupervised

When you think about it, an unsupervised setting is the case you are going to encounter the most when dealing with data. You are likely to stumble upon messy pieces of text or a random image. You are less likely to find a clean labeled dataset for your task.

Now as you can see in Figure 1, in the supervised setting there is usually some ground truth hyperplane that cleanly separates hard cheeses from soft ones. However in the unsupervised setting, the correct answer can be more blurry. As illustrated in Figure 2, you might encounter situations for which it is equally reasonable to find two or three clusters. The “correct” answer is less obvious.

unsupervised ambiguity
Figure 2: Unsupervised settings can lead to fuzzy results

The K-means algorithm

Now how do you actually cluster your cheese images? Well that’s when K-means comes in. It is a pretty straight forward algorithm which goes like this.

First you are going to define your dataset X={x1,x2,…,xn}X = \{x_1, x_2, \ldots, x_n\} where xi∈Rdx_i \in \mathbb{R}^d. You also need to define KK as the number of clusters you want your algorithm to find. Given this you need to follow these steps:

  1. You randomly initialize cluster centroids which we are going to name μ1,μ2,…,μK\mu_1, \mu_2, \ldots, \mu_K here. Each μj\mu_j also belongs to Rd\mathbb{R}^d. This initialization is being shown in Figure 3.
kmeans init
Figure 3: Initializing the cluster centroids at random. Here k=2
  1. Then you are going to repeat until convergence the following (do not freak out, we are going to break down the math):

(*) For every ii, set ci:=arg⁡min⁡j∥xi−μj∥22c_i := \arg\min_j \lVert x_i - \mu_j \rVert_2^2

(**) For every jj, set μj=∑i=1n𝟙(ci=j) xi∑i=1n𝟙(ci=j)\mu_j = \dfrac{\sum_{i=1}^{n} 𝟙(c_i = j)\, x_i}{\sum_{i=1}^{n} 𝟙(c_i = j)}

Ok, we need to break down what is happening here.

Let’s start with (*).

Here is the formula:

For every ii, set ci:=arg⁡min⁡j∥xi−μj∥22c_i := \arg\min_j \lVert x_i - \mu_j \rVert_2^2

In other words, for every xix_i (every cheese image embedding), we are going to define a cic_i. Now, that cic_i is the identity of the closest cluster centroid. As shown in Figure 4, for a given data point (here the circled blue dot), we are going to check which cluster is the closest. In the case of Figure 4, that’s the blue star. And you need to do that for each data point. So now you have {x1,x2,…,xn}\{x_1, x_2, \ldots, x_n\} and {c1,c2,…,cn}\{c_1, c_2, \ldots, c_n\}, each cic_i being the closest cluster identity to xix_i. As written cic_i takes its values in {1,2,…,K}\{1, 2, \ldots, K\} because of the argmin.

kmeans assign 1
Figure 4: Assigning the closest cluster centroid to each data point

Now we need to understand (**) which says:

For every jj, set μj=∑i=1n𝟙(ci=j) xi∑i=1n𝟙(ci=j)\mu_j = \dfrac{\sum_{i=1}^{n} 𝟙(c_i = j)\, x_i}{\sum_{i=1}^{n} 𝟙(c_i = j)}

That one is maybe a little trickier to grasp. The first thing to understand is the indicator function. The indicator function 𝟙(⋅)𝟙(\cdot) takes a condition and returns 11 if it is true and 00 if it is false:

𝟙(ci=j)={1if ci=j0otherwise𝟙(c_i = j) = \begin{cases} 1 & \text{if } c_i = j \\ 0 & \text{otherwise} \end{cases}

Ok. Now that we are ok with that let’s look at our formula. What is happening here is that we are going to recompute the cluster centroids. Each cluster centroid is going to be recomputed as the mean of all its data points, and what I mean by “its” here is: all the data points for which μj\mu_j is the closest cluster centroid.

So in other words, for the cluster centroid μj\mu_j, if the indicator function 𝟙(ci=j)𝟙(c_i = j) returns 1, it means μj\mu_j is the closest cluster centroid for the data point xix_i and therefore we want to include xix_i in our sum, otherwise we don’t: 𝟙(ci=j)=0𝟙(c_i = j) = 0.

Now you do that for all data point and divide by the number of data point in your mean and you get the new value for your cluster centroid. An illustration of this process is given in Figure 5.

kmeans update
Figure 5: Updating μj

In practice it can be shown that K-means always converges to a local minimum. The loss function this algorithm minimizes is named the Distortion Function and is written as follows:

J(c,μ)=∑i=1n∥xi−μci∥22J(c, \mu) = \sum_{i=1}^{n} \lVert x_i - \mu_{c_i} \rVert_2^2

What this function says is that we are trying to find a set of μ\mu and cc such that the squared distance between all data points and their assigned cluster centroids is as small as possible.

As you saw earlier, this algorithm is alternating between two different steps. In one step it optimzes with respect to cc and in another it optimizes with respect to μ\mu. We say that K-means is coordinate descent of the Distortion Function.

Lastly, since it can be shown that JJ is a non convex function, we may end up with a different set of μ\mu and cc depending on the initialization chosen (Figure 6).

kmeans local min
Figure 6: K-means can lead to different outcomes depending on initialization.

And here you go! That’s what there is to know about K-means, now it’s time to read the paper from Meta on e-means :)

Acknowledgements

Many thanks to my friend Aritra for giving me valuable feedback on this post.


Edit on GitHub