K-Means Clustering

K-means clustering is an algorithm that divides a set of data points into a chosen number of groups, written $k$, so that each point belongs to the group whose centre is nearest to it. It is a method of unsupervised learning: the data carry no labels, and the algorithm finds structure using only the distances between points. It is one of the oldest and most widely used clustering techniques in machine learning and data science.

In finance it is used to group things that behave alike without deciding in advance what the groups should be: shares with similar return patterns, trading days with similar market conditions, or customers with similar activity. The name was introduced by James MacQueen in 1967, and the standard procedure is often called Lloyd's algorithm after Stuart Lloyd, who devised it at Bell Labs in 1957.

The algorithm looks for the assignment of points to clusters that minimises the total squared distance between each point and the centre of its cluster:

• $J$ is the within-cluster sum of squares, the quantity to be minimised.
• $k$ is the number of clusters, chosen by the analyst.
• $C_j$ is the set of points assigned to cluster $j$.
• $\mu_j$ is the centroid of cluster $j$, the mean of its points.
• $\lVert x - \mu_j \rVert$ is the distance between point $x$ and that centroid.

The procedure starts with $k$ initial centroids and then repeats two steps. In the assignment step each point is attached to its nearest centroid. In the update step each centroid is moved to the mean of the points attached to it. The loop ends when no point changes cluster. Each pass lowers $J$ or leaves it unchanged, so the algorithm always stops, though not necessarily at the best possible answer.

Take six shares with annual volatilities of 2, 3, 4, 10, 11 and 12 percent, to be split into two clusters, with starting centroids at 3 and 4. In the first assignment, 2 and 3 are nearer to the centroid at 3, while 4, 10, 11 and 12 are nearer to the centroid at 4. The centroids are updated to 2.5 and 9.25. In the second assignment, 4 is now closer to 2.5 than to 9.25, so it changes cluster. The centroids become 3 and 11, the means of (2, 3, 4) and (10, 11, 12). A third pass changes nothing, and the algorithm stops with a low-volatility group and a high-volatility group. The final value of $J$ is $1 + 0 + 1 + 1 + 0 + 1 = 4$.

• Grouping securities. Shares are clustered on features such as past returns, volatility, valuation ratios or factor exposures. The groups can differ from official industry sectors and are used to check diversification or to shortlist candidates for pairs trading.
• Market regimes. Trading days or weeks are clustered on measures such as return, volatility and correlation, giving labels like calm, trending or stressed that a strategy can condition on.
• Portfolio construction. Clustering assets before allocating among them is a step in some methods related to hierarchical risk parity.
• Customers and surveillance. Banks and brokers segment clients by behaviour, and compliance teams use distance from every cluster centre as a simple form of anomaly detection.

The number of clusters must be set before the algorithm runs. A common aid is the elbow method: $J$ is plotted for increasing values of $k$, and the point where further clusters bring little improvement is chosen. The silhouette score, which compares how close each point is to its own cluster and to the next nearest, is another. Neither gives a definitive answer.

Features must be put on a comparable scale first. If one input is a price-to-earnings ratio in the tens and another is a daily return in fractions of a percent, the first will dominate the distance calculation unless both are standardised, for example by converting each to a z-score.

The result depends on the starting centroids, and a poor start can leave the algorithm at an inferior solution. Running it several times from different starts, or using the k-means++ seeding method, reduces the problem. The method assumes clusters are roughly round and of similar size, and it handles elongated or overlapping groups badly. Because centroids are means, outliers pull them, which matters for return data with fat tails.

In markets there is a further difficulty. K-means will always return $k$ clusters, whether or not the data contain real groups, and clusters found in one period may not hold in the next as relationships between assets change. Results should therefore be tested on later data, in the same spirit as cross-validation, before a strategy is built on them. Treating an unstable grouping as a fixed fact is a form of overfitting.