K-Means++ Init

Problem

Run k-means++ seeding for the first two centroids. With random.seed(seed), pick the first centroid uniformly at random, then pick the second with probability proportional to its squared distance from the first (using a single random.random() draw over the cumulative distribution).

Return [index0, index1]; if all points coincide, pick the second uniformly at random. Empty input returns [].

Hint

D-squared weighting spreads out the initial centroids; compare the cumulative distance to a uniform draw scaled by the total.

Test cases

case 1

in: [[[0,0],[1,1],[5,5],[10,10]],42]

expected: [0,2]

case 2

in: [[[0],[1],[2],[10]],7]

expected: [2,3]

case 3

in: [[[3,3],[3,3],[3,3]],1]

expected: [0,2]

case 4

in: [[[1],[9]],0]

expected: [1,0]

Starter codePython

import random
def kmeans_plus_plus_init(points, seed):
    # Returns [index0, index1]
    # Your code here
    pass

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