Problem 549543 · medium · Level 05 Advanced Algorithms & Graphs

Rounds Until the Depots Settle

k-means clustering · convergence · seeded initialisation · local minima · within-cluster sum of squares

The courier company now runs its depot rounds (assign every customer to the nearest depot, then move every depot to the mean of its customers) until nothing changes any more.

Write kmeans(points, k, seed, max_rounds) that returns a tuple (centres, assign, wcss, rounds):

  • Start: centres are copies of the points points[i] for the indices i in random.Random(seed).sample(range(len(points)), k), in that order.
  • Round: assign every point to its nearest centre (squared Euclidean distance; on a tie, the smaller centre index). If this assignment is identical to the one of the previous round, stop. Otherwise move every centre to the mean of its points (a centre without points stays where it is) and count one round.
  • Stop also when max_rounds rounds have been counted.

Return the final centres, the last assignment, the within-cluster sum of squares Σ ‖points[i] - centres[assign[i]]‖² of that assignment with the final centres, and the number of rounds counted.

The setup provides make_blobs(seed) (30 points around three centres) and customer_map(n, groups, seed) (n customers around groups towns).

Examples

Input:  points = [[0], [1], [10], [11]], k = 2, seed = 0, max_rounds = 10
Output: ([[10.5], [0.5]], [1, 1, 0, 0], 1.0, 1)
Explanation: the start is [[11], [1]]. After one round the centres are 10.5 and 0.5; the
second assignment is the same as the first, so the loop stops with 1 round counted.

Input:  make_blobs(1), k = 3, seed = 0, max_rounds = 100
Output: centres ≈ [[1.9, 2.1], [8.2, 3.2], [5.5, 7.6]], wcss ≈ 42.2, rounds = 3

Input:  make_blobs(1), k = 3, seed = 9, max_rounds = 100
Output: centres ≈ [[3.7, 4.9], [7.8, 3.5], [8.9, 2.7]], wcss ≈ 255.1, rounds = 2

Constraints

  • 1 <= k <= len(points) <= 2000, points have 1 to 4 coordinates, 1 <= max_rounds <= 200
  • floats are compared with a tolerance of 1e-6

Goals

  • Start k-means from k data points chosen with a seeded random generator
  • Alternate assignment and update until the assignment stops changing, within a round limit
  • See that different starts can settle in different local minima
Starting Python…