K-Means Clustering From Scratch
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]foriin0..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
- K-Means ClusteringMedium
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium