k-means++ initialisation: first centroid uniform random, subsequent centroids drawn with probability proportional to squared distance from the nearest already-chosen centroid. Deterministic given `seed`.
(vectors: &[Vec<f32>], k: usize, seed: u64)
| 122 | /// centroids drawn with probability proportional to squared distance from the |
| 123 | /// nearest already-chosen centroid. Deterministic given `seed`. |
| 124 | fn kmeans_plus_plus_init(vectors: &[Vec<f32>], k: usize, seed: u64) -> Vec<Vec<f32>> { |
| 125 | let mut state = seed.wrapping_add(1); |
| 126 | let first = (lcg_next(&mut state) as usize) % vectors.len(); |
| 127 | let mut centroids: Vec<Vec<f32>> = vec![vectors[first].clone()]; |
| 128 | |
| 129 | while centroids.len() < k { |
| 130 | let dists: Vec<f32> = vectors |
| 131 | .iter() |
| 132 | .map(|v| { |
| 133 | let d = min_dist_to_centroids(v, ¢roids); |
| 134 | d * d |
| 135 | }) |
| 136 | .collect(); |
| 137 | let total: f64 = dists.iter().map(|&d| d as f64).sum(); |
| 138 | if total <= 0.0 { |
| 139 | // All remaining vectors coincide with existing centroids; just |
| 140 | // pick any unique-by-index vector to fill k. |
| 141 | let idx = (lcg_next(&mut state) as usize) % vectors.len(); |
| 142 | centroids.push(vectors[idx].clone()); |
| 143 | continue; |
| 144 | } |
| 145 | // Deterministic weighted draw from the LCG. |
| 146 | let r = (lcg_next(&mut state) as f64) / (u64::MAX as f64) * total; |
| 147 | let mut acc = 0.0f64; |
| 148 | let mut pick = vectors.len() - 1; |
| 149 | for (i, &d) in dists.iter().enumerate() { |
| 150 | acc += d as f64; |
| 151 | if acc >= r { |
| 152 | pick = i; |
| 153 | break; |
| 154 | } |
| 155 | } |
| 156 | centroids.push(vectors[pick].clone()); |
| 157 | } |
| 158 | |
| 159 | centroids |
| 160 | } |
| 161 | |
| 162 | /// Run Lloyd's K-means with k-means++ initialisation. Empty clusters are |
| 163 | /// re-seeded each iteration so the result always has exactly `k` distinct |