K-Means Clustering

Sometimes nobody hands you labels. You have five hundred tickers and a matrix of returns, and the question is not "predict tomorrow" but "which of these behave like each other?" There is no right answer written down anywhere — you are looking for structure that is already in the data. That is clustering, and k-means is the method almost everyone reaches for first.

The cleanest way to picture it: you have to place $k$ ice-cream vans in a town so that everybody's walk to the nearest van is as short as possible. Park the vans somewhere. Every resident walks to whichever is closest, which carves the town into territories. Now look at each van's customers and move the van to the middle of that crowd. Some residents are now closer to a different van, so they switch, so the middles move again. Keep going until nobody switches. That loop is the algorithm.

What it is actually minimising

Write $\mu_j$ for the position of cluster $j$'s centre (its centroid) and $C_j$ for the set of points assigned to it. K-means minimises the total squared distance from points to their own centre:

$$\text{WCSS} \;=\; \sum_{j=1}^{k} \sum_{i \in C_j} \lVert x_i - \mu_j \rVert^2$$

In plain English: add up how far every point sits from the middle of its own group, squaring so that a far-flung point hurts much more than two mildly off ones. Lower is tighter. The two steps of the loop each reduce this number and neither can ever increase it, which is why the algorithm always stops — but only at a local minimum, not necessarily the best one.

Worked example 1: one full pass

Six numbers: $1, 2, 4, 8, 9, 12$. Ask for $k = 2$ and start the centres at $2$ and $10$.

Assign. Point $1$ is $1$ away from the first centre and $9$ from the second, so it joins the first. Same for $2$ (distances $0$ and $8$) and $4$ (distances $2$ and $6$). Point $8$ is $6$ from the first and $2$ from the second, so it joins the second, along with $9$ and $12$. Groups: $\{1,2,4\}$ and $\{8,9,12\}$.

Move. The new centres are the group means, $\tfrac{1+2+4}{3} = 2.33$ and $\tfrac{8+9+12}{3} = 9.67$.

Assign again. Nothing switches — $4$ is $1.67$ from the left centre and $5.67$ from the right — so the algorithm has converged. The final WCSS is

$$(1.333^2 + 0.333^2 + 1.667^2) + (1.667^2 + 0.667^2 + 2.333^2) = 4.67 + 8.67 = 13.33$$

Worked example 2: why you cannot just minimise WCSS

Run the same six numbers with $k = 3$. The best split is $\{1,2,4\}$, $\{8,9\}$, $\{12\}$, giving $4.67 + 0.5 + 0 = 5.17$. With $k = 4$, take $\{1,2\}, \{4\}, \{8,9\}, \{12\}$ for $0.5 + 0 + 0.5 + 0 = 1.0$. With $k = 6$ every point is its own cluster and WCSS is exactly $0$.

So the objective falls every time you add a cluster and bottoms out at a useless answer. You cannot choose $k$ by minimising the thing k-means minimises — you have to look at where the curve stops falling steeply and read off the bend.

What this means in practice

For assets, the natural features are not prices but co-movements: convert a correlation $\rho_{ij}$ into a distance $d_{ij} = \sqrt{2(1-\rho_{ij})}$ and cluster on that, which is the standard route to sector-like groupings that ignore the official taxonomy (Clustering for Portfolios, Correlation Clustering). Because the objective is squared distance, feature scale is destiny — mixing a variable in percent with one in basis points hands the whole clustering to the larger-numbered one. Standardise first.

Two more practicalities. Run it several times from different starts and keep the lowest WCSS, since the algorithm only finds a local minimum; better still, seed with K-Means++ Initialization, which spreads the initial centres apart and usually fixes it. And validate $k$ with something outside the objective — an elbow, a silhouette score, or plain stability under resampling (Choosing the Number of Clusters).

It is worth knowing why the loop is guaranteed to stop. Each step is a partial minimisation of the same quantity: reassigning a point to a nearer centre can only shrink WCSS, and moving a centre to the mean of its members is precisely the position that minimises squared distance to them. Since WCSS never rises and there are only finitely many ways to split $n$ points into $k$ groups, the algorithm must halt. What it cannot promise is that the resting place is the global best — finding that is a genuinely hard combinatorial problem, which is why restarts matter.