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