Vectorized K-Means with Broadcasting

MediumML Coding

Reported in interviews at Mistral AI

Problem statement

You have written k-means with a loop over points. The interviewer's follow-up is the one that matters: make it run with no Python loop over points or clusters, using broadcasting alone. Implement the vectorized algorithm around the identity

$$\lVert x - c \rVert^2 = \lVert x \rVert^2 + \lVert c \rVert^2 - 2\, x \cdot c$$

pairwise_sq_dists(X, C)

  • X has shape (n, d) and C shape (k, d). Return the (n, k) array of squared Euclidean distances using the identity above, with a single matrix product and broadcasting. Clip negative values that arise from rounding to 0.

assign_clusters(X, C)

  • The (n,) integer array of nearest-centroid indices (lowest index on ties).

update_centroids(X, labels, C)

  • The new (k, d) centroids: each is the mean of its assigned points; a cluster with no points keeps its previous centroid.

kmeans(X, C0, max_iter=100, tol=1e-6)

  • Run assignment and update from the initial centroids C0 until the largest centroid movement (Euclidean norm of any row's change) is below tol or max_iter iterations have run. Return (C, labels, n_iter) where n_iter counts the update steps performed and labels is the assignment to the returned centroids.

inertia(X, C, labels)

  • The sum of squared distances from each point to its assigned centroid, as a float.

Example

Input:

pairwise_sq_dists([[0, 0], [3, 4]], [[0, 0], [3, 0]])

Output:

[[0.0, 9.0], [25.0, 16.0]]

Reasoning: row one is the origin, at distance 0 from the first centroid and 9 from the second. Row two is $(3, 4)$: 25 from the origin and 16 from $(3, 0)$.

Show hint

Can you expand the squared distance into pieces that are each cheap to compute for all point and centroid pairs at once?

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

Related free problems