What does minimising the loss function mean in k-means clustering?

Question

I am learning about the k-means clustering algorithm, and I have read that the algorithm is "Trying to minimise a loss function in which the goal of clustering is not met".

I understand the basic concept of the algorithm, which initialises arbitrary centroids/means in the first iteration and then assigns data points to these clusters. The centroids are then updated after the points are all assigned, and points are re-assigned again. The algorithm continues to iterate until the clusters do not change anymore. The algorithm tries to minimise the within-cluster sum of squares (WCSS) value which is a measure of the variance within the clusters.

However, I am having trouble understanding what is meant by a loss function in the context of this algorithm. Any insights are appreciated.

Answer 1

Given $n$ points $\{x_i\}_1^n$ and a known number of clusters $k$, I think a possible loss function would be something like: $$L(c_1,...,c_k) = \sum_{i=1}^n \min_j || x_i - c_j ||^2 .$$ This would be the loss function for the k-means problem but it doesn't mean the the k-means algorithm is explicitly trying to decreases this loss (like a gradient descent would).

Answer 2

First, we use clustering when we have a prior knowledge that the dataset can be divided into many groups, where the points in each group are similar w.r.t some criterion. A simple example is a dataset composed of two parts of points, the points in the first part are sampled from $\mathcal{N}(4,1)$, and the ones in the second part from $\mathcal{N}(-4,1)$. Points in the first group are similar as they have shorter distance to 4 than to -4, and vice versa for points in the second group.

Now, we can explain why there are many clustering algorithms, as each algorithm has its own similarity criterion between points. For instance, the $k$-means algorithm assumes that the dataset is composed of $k$ groups (or clusters) of points, each group is sampled from a Gaussian distribution. All distributions share the same variance. Straight forward, and based on this hypothesis, the points in a group are similar by being closer to the mean value (centroid) of the associated distribution, than to centroids of other groups.

What is left now is to place these k centroids in their true/optimal position, where such placement should minimise the loss function you mentioned. To see the intuition behind the loss function, assume that you have $k=1$, i.e. you have all points in the dataset sampled from the same Gaussian distribution, and you want to find its centroid, clearly this mean value is the minimiser of the variance in this cluster of points in hand. Following the same rule for $k>1$, you want to find the $k$ groups and place the centroids in their mean values, thus minimising the within-cluster sum of squares (WCSS), which is the loss function here. Note that based on the law of total variance, this means maximising the distance between centroids, which means that you don't want to get two (or more) centroids in the mean value of the same group, which also means you don't want to assign one centroid to be the mean value of two groups. In other words, the global minimiser of the loss function is where you find the $k$ different groups, and you place the $k$ centroids in their mean values. And finding this global minimiser is a matter of a good initialisation of centroids.