K-Means One Iteration

Problem

Perform one iteration of k-means: 1. Assign each point to its nearest centroid (Euclidean distance). 2. Recompute each centroid as the mean of the points assigned to it.

If a centroid has no points assigned, keep it unchanged.

points is a list of [x, y, ...] vectors. centroids is a list of same-shape vectors. Returns the new list of centroids.

Hint

First pass: assignment. Second pass: recompute means.

Test cases

case 1

in: [[[0,0],[0,1],[10,10],[10,11]],[[0,0],[10,10]]]

expected: [[0,0.5],[10,10.5]]

case 2

in: [[[1,1],[2,2],[9,9],[10,10]],[[0,0],[5,5]]]

expected: [[1.5,1.5],[9.5,9.5]]

case 3

in: [[[1],[2],[9],[10]],[[0],[5]]]

expected: [[1.5],[9.5]]

Starter codePython

def kmeans_one_iter(points, centroids):
    # Your code here
    pass

3 test cases · run your code against them in the editor