BUGFIX-66

Bug 43: K-Means Demeaned: Initial Centers

This is k-means++ (an initialization heuristic for the Lloyd-Forgy k-means clustering algorithm).
It takes as input a slice of points (pts) and chooses k of those points to be the initial cluster centers.
The chosen points are swapped to the front of the slice. The first point is chosen uniformly at random.
The remaining k-1 points are each chosen randomly according to a weighted probability distribution.
The weight of a point is the minimum of its squared Euclidean distances to points already chosen.

Fix The Tiny Bug In This Go Code:

func initialCenters(k int, pts [][]float32, r *rand.Rand) { n := len(pts) if k <= 1 || k >= n { return } mins := make([]float32, n) for i := range mins { mins[i] = math.MaxFloat32 } i := r.Intn(n) last := pts[i] pts[i] = pts[0] pts[0] = last for have := 1; have < k; have++ { sum := float32(0) for i := have; i < n; i++ { var ( pt = pts[i] dsq = float32(0) ) for i, last := range last { gap := pt[i] - last dsq += gap * gap } min := mins[i] if min > dsq { min = dsq mins[i] = dsq } sum += min } var ( i = have r = sum * r.Float32() ) if r == sum { return } for sum := mins[i]; r >= sum; { i++ sum += mins[i] } last = pts[i] pts[i] = pts[have] pts[have] = last mins[have] = mins[i] } }

To receive a hint, submit unfixed code.