Back to course

Clustering

A typical interview question is: "How would you cluster 500 stocks from their returns, and how would you know the clusters are real?" A full answer states the objective and what the algorithm guarantees, picks a distance built from correlation, and treats stability under resampling as the test of whether a cluster exists.

k-means

k-means splits nn points into KK groups to minimise the within-cluster sum of squares:

J=∑k=1K∑i∈Ck∥xi−μk∥2J = \sum_{k=1}^{K} \sum_{i \in C_k} \lVert x_i - \mu_k \rVert^2

where μk\mu_k is the mean of cluster CkC_k. Lloyd's algorithm alternates two steps: assign each point to its nearest centre, then move each centre to the mean of its points. Each step can only lower JJ or leave it unchanged, and there are finitely many partitions, so the algorithm stops. It stops at a local minimum, not the global one, so run it from several starts and keep the lowest JJ.

The rest of this lesson is for subscribers

Unlock every lesson in Machine Learning for Quantitative Research, and every other premium course.

Subscribe to continue

Test your knowledge

Questions are only available to subscribers.
Continue

Keep reading Machine Learning for Quantitative Research

27 lessons in this course, and every other premium course, on one subscription.

Subscribe now
  • Every lesson in every course, with the worked examples and interactive simulators
  • Graded questions on every lesson, with explanations for the wrong answers as well as the right one
  • The trainers, timed assessments and brainteaser library that go with them