Vectorized K-Means with Broadcasting
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)
Xhas shape(n, d)andCshape(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 to0.
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
C0until the largest centroid movement (Euclidean norm of any row's change) is belowtolormax_iteriterations have run. Return(C, labels, n_iter)wheren_itercounts the update steps performed andlabelsis 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
- K-Means ClusteringMedium
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium