K-Means Clustering From Scratch

MediumML Coding

Reported in interviews at Citadel Renaissance Technologies The Voleon Group

Problem statement

Implement the k-means clustering algorithm from scratch and return its final inertia.

Given a set of $n$ data points in $d$-dimensional space and a target number of clusters $k$, write a function

def kmeans_inertia(points, k):
    ...

that partitions the points into $k$ clusters by iteratively assigning points to their nearest centroid and updating centroids, then returns the within-cluster sum of squared Euclidean distances (the inertia) as a single float.

Deterministic initialization (required so the answer is unique):

  • centroid[i] = points[i] for i in 0..k-1 (the first $k$ points).

Then run Lloyd iterations until assignments stop changing (max 100 iterations):

  • Assign: assign each point to its nearest centroid (Euclidean distance).
  • Update: move each centroid to the mean of its assigned points. If a cluster is empty, leave its centroid unchanged.

Inertia $= \sum_{\text{points } p} \|p - \text{assigned\_centroid}(p)\|^2$.

Constraints:

  • $1 \leq k \leq n \leq 10^4$
  • $1 \leq d \leq 100$
  • Use Euclidean distance.

Example

kmeans_inertia([[1,2],[1,4],[1,0],[4,2],[4,4],[4,0]], 2) -> 17.5

Centroids are initialized to the first 2 points [1,2] and [1,4]. Lloyd iterations then converge to a local minimum whose within-cluster sum of squared distances is $17.5$. Because initialization is fixed to the first $k$ points rather than optimized, the result is a deterministic local optimum, not necessarily the globally best clustering.

Show hint

What two alternating optimization steps each lower the within-cluster squared error while holding the other variables fixed?

Relevant roles: ML Engineer, Deep Learning Engineer, Applied Scientist and Data Scientist.

Related free problems