k-Means++ Algorithm

We can solve arbitrarily bad initialisations of clusters and generally find a solution much faster by using k-Means++. It can be shown that the approximation factor is at most $O(\log k)$.

1. Set the first centre to be one of the input points chosen uniformly at random. ${\mu }_1=\text{uniform}(x_1,x_2,\dots ,x_n)$
2. For cluster $i=2$ to $k$:
   1. For each point $x_j$, compute the distance to the nearest centre, i.e. calculate $d_j={\text{min}}_l\{||x_j-{\mu }_l|{|}_2\}$
   2. Open a new centre at a point using the weighted probability distribution that is proportional to $d_j$, that is: $\text{Pr}(\text{new centre in }{x}_j)=\frac{d_j^2}{{\sum }_l{d}_l^2}$
3. Continue with k-Means.