# 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;

}

}
}

}


$\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.