There are times where I get less than K clusters in a K-Means algorithm implemented in Java so I searched for a solution. One thread suggested using KMeans++ for initialization but I am stucked on how to implement the algorithm (in Wiki) most especially the 3rd step. I am wondering how to implement in on a lattice where I am doing the K-Means algorithm.
This is the exact algorithm.
Choose one center uniformly at random from among the data points.
For each data point x, compute D(x), the distance between x and the nearest center that has already been chosen.
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.
Repeat Steps 2 and 3 until k centers have been chosen.
Now that the initial centers have been chosen, proceed using standard k-means clustering.
I am a bit confused on how to implement it most especially step 3 in choosing with probability proportional to D(x)^2.