I'm 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?