K-means++

An improved algorithm was proposed in 2007. K-means++ addresses the problem of suboptimal clustering by introducing an additional step for a good centroids initialization.

An improved algorithm of initial centers selection looks like this:

1. Select randomly any data point to be the first center
2. For all other data points, calculate the distance to the first center d(x)
3. Sample the next center from the weighted probability distribution, where the probability of each data point to become a next center is proportional to the square of distance d(x)²
4. Until k centers are chosen, repeat step 2 and step 3
5. Proceed with the standard k-means algorithm

In Swift, it looks like this:

internal mutating func chooseCentroids() { 
  let n = data.count 
 
  var minDistances = [Double](repeating: Double.infinity, count: n) 
  var centerIndices = [Int]() 

clusterID is an integer identifier of a cluster: the first cluster has identifier zero, the second has one, and so on:

for clusterID in 0 ..< k { 
  var pointIndex...