K-Means Clustering From Scratch
Implement the k-means clustering algorithm from scratch.
Given a set of $n$ data points in $d$-dimensional space and a target number of clusters $k$, write a function that partitions the points into $k$ clusters by iteratively assigning points to their nearest centroid and updating centroids.
**Constraints:**
-
\leq k \leq n \leq 10^4$
-
\leq d \leq 100$
- Use Euclidean distance
- Terminate when assignments no longer change (or after a maximum number of iterations)
**Example:**
Input: `points = [[1,2],[1,4],[1,0],[4,2],[4,4],[4,0]]`, `k = 2`
Output: `centroids = [[1.0, 2.0], [4.0, 2.0]]`, `assignments = [0, 0, 0, 1, 1, 1]`
Explanation: The algorithm finds two natural clusters centered at $(1, 2)$ and $(4, 2)$.
Open the full interactive solver, hints, and worked solution →