K-means++ algorithm I try to implement k-means++, but I'm not sure how it works. I have the following dataset:
(7,1), (3,4), (1,5), (5,8), (1,3), (7,8), (8,2), (5,9), (8,0)

From the wikipedia:


*

*Step 1: Choose one center uniformly at random from among the data points. 
let's say the first centroid is 8,0

*Step 2: For each data point x, compute D(x), the distance between x and the nearest center that has already been chosen. 
I calculate all each point's distance to tht point nr.9 (8,0)


*

*1 (7,1) distance = (8-7)^2 + (0-1)^2 = (1)^2 + (-1)^2 =  1 +  1 =  2

*2 (3,4) distance = (8-3)^2 + (0-4)^2 = (5)^2 + (-4)^2 = 25 + 16 = 41

*3 (1,5) distance = (8-1)^2 + (0-5)^2 = (7)^2 + (-5)^2 = 49 + 25 = 74

*4 (5,8) distance = (8-5)^2 + (0-8)^2 = (3)^2 + (-8)^2 =  9 + 64 = 73

*5 (1,3) distance = (8-1)^2 + (0-3)^2 = (7)^2 + (-3)^2 = 49 +  9 = 58

*6 (7,8) distance = (8-7)^2 + (0-8)^2 = (1)^2 + (-8)^2 =  1 + 64 = 65

*7 (8,2) distance = (8-8)^2 + (0-2)^2 = (0)^2 + (-2)^2 =  0 +  4 =  4

*8 (5,9) distance = (8-5)^2 + (0-9)^2 = (3)^2 + (-9)^2 =  9 + 81 = 90


*Step 3: Choose one new data point at random as a new center, using a weighted probability distribution where a point x is chosen with probability proportional to $D(x)^2$.

*Step 4: Repeat Steps 2 and 3 until k centers have been chosen.
Could someone explain in detail how to calculate the 3rd step?

For step 3, 

Choose one new data point at random as a new center, using a weighted
  probability distribution where a point x is chosen with probability
  proportional to $D(x)^2$.

Compute all the $D(x)^2$ values and convert them to an array of cumulative sums. That way each item is represented by a range proportional to its value. Then pick a uniform random number in that range and see which item it corresponds to (using a binary search).
For instance, you have:
D(x)^2 = [2, 41, 74, 73, 58, 65, 4, 90]
cumulative D(x)^2 = [2, 43, 117, 190, 248, 313, 317, 407]

So pick a random number from [0, 407). Say you pick 123.45. It falls in the range [117, 190)  which corresponds to the 4th item. 
