K-Means From Scratch Steps

HardPython

Problem

Cincinnati Children's Hospital uses feature vectors to group similar clinical observations for exploratory analysis. Implement k-means clustering from scratch without machine learning libraries.

Given n points in d-dimensional space, divide them into exactly k clusters by repeatedly assigning each point to its nearest centroid and recomputing centroids.

Formal Specification

Implement kmeans(points, k, max_iters, tolerance). points is a non-empty list of equal-length numeric lists. Return a dictionary with:

labels: a list of length n, where labels[i] is the cluster index assigned to points[i]
centroids: a list of k coordinate lists

Initialize centroids deterministically using farthest-point initialization: choose the first point, then repeatedly choose the unselected point with the greatest distance to its nearest selected centroid. Use squared Euclidean distance. Stop when assignments no longer change or every centroid coordinate moves by at most tolerance. If a cluster becomes empty, retain its previous centroid.

Constraints

1 <= len(points) <= 2,000
1 <= k <= len(points)
1 <= len(points[i]) <= 20
All points have equal dimensionality
Coordinates are finite numbers in [-10^6, 10^6]
1 <= max_iters <= 1,000
0 <= tolerance <= 10^6

Function Signature

def kmeans(points, k, max_iters, tolerance):

Cincinnati Children's Hospital uses feature vectors to group similar clinical observations for exploratory analysis. Implement k-means clustering from scratch without machine learning libraries.

Given n points in d-dimensional space, divide them into exactly k clusters by repeatedly assigning each point to its nearest centroid and recomputing centroids.

Formal Specification

Implement kmeans(points, k, max_iters, tolerance). points is a non-empty list of equal-length numeric lists. Return a dictionary with:

labels: a list of length n, where labels[i] is the cluster index assigned to points[i]
centroids: a list of k coordinate lists