A courier company has k depots and many customers. It improves the depot positions in rounds; one round has two steps:
- Assign every customer to the nearest depot by squared Euclidean distance; on a tie, the depot with the smaller index.
- Move every depot to the mean position (coordinate by coordinate) of the customers assigned to it. A depot with no customers stays where it is.
Write kmeans_round(points, centres) that performs one round and returns a tuple (assign, new_centres, wcss): assign[i] is the index of the depot of customer i (from step 1), new_centres the list of depot positions after step 2, and wcss the within-cluster sum of squares Σ_i ‖points[i] - new_centres[assign[i]]‖².
The setup provides make_blobs(seed) (30 points around three centres) and customer_map(n, groups, seed) (n customers around groups towns); some tests use them.
Examples
Input: points = [[1, 1], [2, 1], [8, 9], [9, 9], [5, 5]], centres = [[0, 0], [10, 10]]
Output: ([0, 0, 1, 1, 0], [[2.6666666666666665, 2.3333333333333335], [8.5, 9.0]], 19.833333333333336)
Explanation: (5, 5) is at squared distance 50 from both depots and goes to depot 0.
Input: points = [[0, 0], [2, 0]], centres = [[1, 0], [1, 0], [50, 50]]
Output: ([0, 0], [[1.0, 0.0], [1, 0], [50, 50]], 2.0)
Explanation: depots 1 and 2 get no customers and stay put.
Constraints
1 <= len(points) <= 5000,1 <= k <= 20, points have 1 to 5 coordinates- floats are compared with a tolerance of
1e-6
Goals
- Assign every point to its nearest centre with a stated tie rule
- Move every centre to the mean of its points, keeping a centre that has none
- Compute the within-cluster sum of squares after the move