I am trying to implement my own k-means algorithm without external libraries/modules (with the exception of numpy). I have recently learned about the k-means++ algorithm; to my understanding, it improves the method of selecting k initial centroids and leaves the clustering algorithm unchanged. I looked at the wikipedia page about k-means++; under the "Improved initialization algorithm" tab, it states:
The exact algorithm is as follows:
1. Choose one center uniformly at random from among the data points. 2. For each data point x, compute D(x), the distance between x and the nearest center that has already been chosen. 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. 4. Repeat Steps 2 and 3 until k centers have been chosen. 5. Now that the initial centers have been chosen, proceed using standard k-means clustering.
Regarding point 3, I am unsure of how to proceed with using a weighted probability distribution. At first, I thought I might need to understand the nature of my dataset better (ie, is it normally distributed?) before this step. But I also realize that the probability distribution must be proportional to D(x)^2. I have read two different but related posts on this site here and here. I interpret step 3 to mean that given a single cluster and respective centroid, the probability distribution can be given as (the distances between the points of this single cluster and its respective centroid) divided by the (length of these distances); (numerator)/(denominator). But then how does one account for the probability distribution of the other cluster points? I am hoping that someone can help clarify this step given a simple example.
As a very brief example (for which initial centroids are input), consider the following:
.. initial centroids:
[[ 2 0]
[50 0]
[97 0]]
** (shape=(2, 9)) DATA:
[[ 1 2 3 4 50 51 98 99 100]
[ 0 0 0 0 0 0 0 0 0]]
.. K=3 CLUSTERS:
cluster #0 (shape=(2, 4)):
[[1 2 3 4]
[0 0 0 0]]
cluster #1 (shape=(2, 2)):
[[50 51]
[ 0 0]]
cluster #2 (shape=(2, 3)):
[[ 98 99 100]
[ 0 0 0]]
.. K=3 CENTROIDS (shape=(3, 2)):
[[ 2.5 0. ]
[50.5 0. ]
[99. 0. ]]
Given this, how does one create a probability distribution to initialize centroids?
