One k-means update
Medium14 min10 hidden tests
A ride-share team places pickup hubs at the centers of trip requests, with each request a point (x, y) in kilometers. Write kmeans_update(points, centroids) that runs one k-means iteration: assign every request to its nearest hub, then move each hub to the mean of its requests. A hub that gets no requests stays where it is.
Drag the hubs, then run one update
nearest hub, then the mean of its pointsAssigned to the nearest hub: hub 0 has 3 requests, mean (1.33, 1.33); hub 1 has 2 requests, mean (8.5, 8.5). Run one update to move each hub to its mean.
hub 0 has 3 requests, mean (1.33, 1.33); hub 1 has 2 requests, mean (8.5, 8.5).
Examples
Each hub moves to the middle of its requests
kmeans_update([[1.0, 1.0], [2.0, 1.0], [8.0, 9.0], [9.0, 8.0], [1.0, 2.0]], [[0.0, 0.0], [10.0, 10.0]])
returns [[1.33333, 1.33333], [8.5, 8.5]]
The far hub gets no requests and stays put
kmeans_update([[1.0, 1.0], [2.0, 1.0], [8.0, 9.0], [9.0, 8.0], [1.0, 2.0]], [[0.0, 0.0], [10.0, 10.0], [50.0, 50.0]])
returns [[1.33333, 1.33333], [8.5, 8.5], [50, 50]]
Requirements
pointsis a 2-D list or array of shape (n, d) andcentroidsone of shape (k, d), with n, k and d all 1 or more.- Assign each point to its nearest centroid by Euclidean distance, ties to the lower index.
- Each new centroid is the mean of its assigned points, feature by feature. A centroid with no points keeps its old position.
- Return a new float array of shape (k, d). Leave
centroidsunchanged.
The idea behind it
k-means finds k clusters by repeating two steps until the centroids stop moving. In the assignment step every point joins its nearest centroid. In the update step every centroid moves to the mean of its points, which is the spot that minimizes the summed squared distance to them. Each round can only lower that total, the within-cluster sum of squares, so the loop always settles, though maybe in a local minimum. An empty cluster is a real case. It happens when a centroid starts far from the data, or when two centroids sit on the same spot and the tie rule sends every point to the lower one. The mean of no points is undefined. Keeping the old centroid is the simplest fix. Libraries such as scikit-learn instead move it onto a data point that sits far from its own cluster's center, so the cluster gets used again.