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

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) {

break;

}

}
}

}


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.

• I still wonder how to implement I try this in java 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; } } } The selection chance is very low – tanawatl Dec 29 '15 at 1:09
• Change your script a little bit, if you add all the probabilities of the datapoints, does it add up to 1? That part looks ok to me. Two points about your script, you should remove datapoints that have been selected as centroid from your datapoint collection (I think) and the second is that I would change the randomized picking of a centroid to something like this: Make a list of cumulative probabilities, and then check where your rand falls, that way, if they do add up to 1 you will always have selected one. – Jan van der Vegt Dec 29 '15 at 10:16