BUGFIX-66

Bug 44: K-Means Demeaned: Lloyd-Forgy Clustering

The first k points are used as the initial cluster centers, consistent with our k-means++ initialization.
Each point is assigned to the cluster with the nearest center. If no assignments change, clustering ends.
Each cluster's center is replaced by the arithmetic mean of the points that are assigned to that cluster.
Using these updated cluster centers, the process repeats.

Fix The Tiny Bug In This Go Code:

func cluster(k int, pts [][]float32) []int { var ( n = len(pts) clusters = make([]int, n) ) if k > n { k = n } if k <= 1 { return clusters } var ( d = len(pts[0]) centers = make([]float32, k*d) counts = make([]int, k) ) for i, pt := range pts[:k] { clusters[i] = i copy(centers[i*d:], pt) counts[i] = 1 } for i := k; ; i = 0 { changed := i != 0 for ; i < n; i++ { var ( pt = pts[i] min = float32(math.MaxFloat32) cluster = 0 ) for i := 0; i < k; i++ { var ( center = centers[i*d:] dsq = float32(0) ) for i, pt := range pt { gap := center[i] - pt dsq += gap * gap } if min > dsq { min = dsq cluster = i } } if clusters[i] != cluster { clusters[i] = cluster changed = true } counts[cluster]++ } if !changed { break } for i := range centers { centers[i] = 0 } for i, pt := range pts { var ( cluster = clusters[i] center = centers[cluster*d:] ) for i, pt := range pt { center[i] += pt } } for i, count := range counts { if count == 0 { continue } var ( recip = 1 / float32(count) center = centers[i*d : i*d+d] ) for i := range center { center[i] *= recip } } } return clusters }

To receive a hint, submit unfixed code.