Details of the k-means++ algorithm that is used to seed k-means

Question

Regard to K-Means++ algorithm, which is an algorithm for choosing the initial values (or "seeds") for the k-means clustering algorithm.

K-Means++ algorithm in Wikipedia

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.

I dont understand 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."

What is probability proportional ?

If I do not misunderstand . . .

The next centroid x I choose must the distance

D(x) = D(x)^2 / summation of all distances from all data points square

Is that right ?

---

I still wonder about implementation. I try this in java but it does not work , the chance is very low and it make the selection distort.

public static double euclidean(Data a, Data b) {

    double accumValue = 0;
    double res;

    for (int i = 0; i < 72; i++) {

        res = a.features[i] - b.features[i];

        res = Math.pow(res, 2);

        accumValue += res;

    }

    double finalRes = Math.sqrt(accumValue);

    return finalRes;

}

public static double accumeratedSqrDistanceCal(ArrayList<Data> dataList, ArrayList<Data> centroids) {

    double[] squareDistanceCollection = new double[dataList.size()];

    for (int i = 0; i < dataList.size(); i++) {

        double minDistance = minDistanceFromClosetCentroidsCal(dataList.get(i), centroids);

        squareDistanceCollection[i] = Math.pow(minDistance, 2);

    }

    double accumerateDistance = 0;

    for (int i = 0; i < dataList.size(); i++) {

        accumerateDistance += squareDistanceCollection[i];

    }

    return accumerateDistance;

}

public static double minDistanceFromClosetCentroidsCal(Data d, ArrayList<Data> centroids) {

    double minDistance = 100000;

    for (int i = 0; i < centroids.size(); i++) {

        double distance = euclidean(d, centroids.get(i));

        if (distance < minDistance) {

            minDistance = distance;
        }

    }

    return minDistance;

}
public static void main(String[] args) {

for (int i = 0; i < CENTROIDS_SIZE; i++) {

            for (int j = 0; j < dataList.size(); j++) {

                double accumerateDistance = accumeratedSqrDistanceCal(dataList, centroids);

                double rand = Math.random();

                double distance = minDistanceFromClosetCentroidsCal(dataList.get(j), centroids);

                double distanceSquare = Math.pow(distance, 2);

                double chance = distanceSquare / accumerateDistance;

                if (chance > rand) {

                    centroids.add(dataList.get(j));
                    break;

                }

            }
        }

}

Answer 1

You want to spread out the initial clusters, the article argues that this gives (on average) faster convergence and lower error. This means that points with a higher distance to the closest center are likely to be better candidates for initial clusters. So the probability distribution for a new initial clustering point is:

$\mathbb{P}(C = c) = \frac{D(c)^2}{\sum_{\forall x\in X}D(x)^2}$

Where $X$ is the collection of all candidate points and $C$ the chosen point distribution.

This means the higher the distance, the higher the chance it will be picked as initial point.