Repository Public
1import Foundation2import SheetCore34/// Result of a k-means clustering.5public struct KMeansResult: Sendable, Hashable, Codable, TableReport {6 /// Cluster centres (k × p).7 public var centroids: Matrix8 /// Cluster index 0…k−1 of each observation.9 public var labels: [Int]10 /// Within-cluster sum of squared Euclidean distances to the centres.11 public var inertia: Double12 /// Lloyd iterations of the best run.13 public var iterations: Int14 /// True when the assignments stopped changing before the iteration limit.15 public var converged: Bool16 public var clusterSizes: [Int]17 /// Mean silhouette coefficient (nil when k = 1 or not requested).18 public var silhouette: Double?19 /// Number of initialisations tried.20 public var runs: Int2122 public func table() -> [[Value]] {23 var out: [[Value]] = [24 Report.row("Clusters", centroids.rows),25 Report.row("Observations", labels.count),26 Report.row("Inertia (within-cluster SS)", inertia),27 [.text("Mean silhouette"), Report.num(silhouette)],28 Report.row("Iterations", iterations),29 [.text("Cluster"), .text("Size")] + (1...max(centroids.cols, 1)).map { .text("Centre X\($0)") },30 ]31 for c in 0..<centroids.rows {32 out.append([Report.int(c + 1), Report.int(clusterSizes[c])] + centroids.row(c).map { Report.num($0) })33 }34 return Report.rectangular(out)35 }36}3738public enum KMeans {39 /// k-means clustering (Lloyd's algorithm, squared Euclidean distance).40 /// - Parameters:41 /// - data: observations in rows.42 /// - seed: seed of the `Xoshiro256StarStar` generator used by the k-means++ initialisation; a given43 /// seed always gives the same result.44 /// - restarts: number of k-means++ initialisations; the run with the smallest inertia is returned.45 /// - initialCentroids: start Lloyd's iterations from these centres instead (single run, no randomness).46 /// - computeSilhouette: also compute the mean silhouette coefficient (O(n²)).47 /// Iterations stop when no observation changes cluster. Ties in distance go to the lower cluster index.48 /// A cluster that becomes empty is re-seeded with the observation farthest from its current centre.49 public static func fit(_ data: Matrix, k: Int, seed: UInt64 = 0, restarts: Int = 10, maxIterations: Int = 300,50 initialCentroids: Matrix? = nil, computeSilhouette: Bool = true) throws -> KMeansResult {51 let n = data.rows, p = data.cols52 guard n >= 1, p >= 1 else { throw StatError.insufficientData("k-means needs data") }53 guard k >= 1, k <= n else { throw StatError.invalidInput("k must be between 1 and the number of observations") }54 guard data.data.allSatisfy(\.isFinite) else { throw StatError.invalidInput("data contain non-finite values") }55 var best: KMeansResult?56 if let c0 = initialCentroids {57 guard c0.rows == k, c0.cols == p else { throw StatError.invalidInput("initial centroids must be k × p") }58 best = lloyd(data, c0, maxIterations)59 best!.runs = 160 } else {61 guard restarts >= 1 else { throw StatError.invalidInput("restarts must be ≥ 1") }62 var rng = Xoshiro256StarStar(seed: seed)63 for _ in 0..<restarts {64 let r = lloyd(data, plusPlus(data, k, &rng), maxIterations)65 if best == nil || r.inertia < best!.inertia { best = r }66 }67 best!.runs = restarts68 }69 if computeSilhouette, k >= 2 { best!.silhouette = silhouette(data, labels: best!.labels).mean }70 return best!71 }7273 private static func squaredDistance(_ data: Matrix, _ r: Int, _ c: Matrix, _ j: Int) -> Double {74 var s = 0.075 let p = data.cols76 for d in 0..<p { let t = data.data[r * p + d] - c.data[j * p + d]; s += t * t }77 return s78 }7980 /// k-means++ seeding (Arthur & Vassilvitskii 2007): first centre uniform, each further centre drawn81 /// with probability proportional to the squared distance to the nearest centre chosen so far.82 static func plusPlus(_ data: Matrix, _ k: Int, _ rng: inout Xoshiro256StarStar) -> Matrix {83 let n = data.rows, p = data.cols84 var centres = Matrix(rows: k, cols: p)85 let first = rng.nextInt(below: n)86 for d in 0..<p { centres[0, d] = data[first, d] }87 var dist = (0..<n).map { squaredDistance(data, $0, centres, 0) }88 for c in 1..<max(k, 1) {89 let total = dist.reduce(0, +)90 var pick = n - 191 if total > 0 {92 let u = rng.nextUniform() * total93 var acc = 0.094 for i in 0..<n { acc += dist[i]; if u < acc { pick = i; break } }95 } else {96 pick = rng.nextInt(below: n)97 }98 for d in 0..<p { centres[c, d] = data[pick, d] }99 for i in 0..<n { dist[i] = min(dist[i], squaredDistance(data, i, centres, c)) }100 }101 return centres102 }103104 private static func lloyd(_ data: Matrix, _ start: Matrix, _ maxIterations: Int) -> KMeansResult {105 let n = data.rows, p = data.cols, k = start.rows106 var centres = start107 var labels = [Int](repeating: -1, count: n)108 var dmin = [Double](repeating: 0, count: n)109 var iterations = 0110 var converged = false111 while iterations < max(1, maxIterations) {112 iterations += 1113 var changed = false114 for i in 0..<n {115 var bestJ = 0, bestD = Double.infinity116 for j in 0..<k {117 let d = squaredDistance(data, i, centres, j)118 if d < bestD { bestD = d; bestJ = j }119 }120 if labels[i] != bestJ { labels[i] = bestJ; changed = true }121 dmin[i] = bestD122 }123 if !changed { converged = true; break }124 var sums = Matrix(rows: k, cols: p)125 var counts = [Int](repeating: 0, count: k)126 for i in 0..<n {127 counts[labels[i]] += 1128 for d in 0..<p { sums.data[labels[i] * p + d] += data.data[i * p + d] }129 }130 for j in 0..<k {131 if counts[j] == 0 {132 // re-seed an empty cluster with the worst-fitted observation133 var far = 0134 for i in 1..<max(n, 1) where dmin[i] > dmin[far] { far = i }135 for d in 0..<p { centres[j, d] = data[far, d] }136 dmin[far] = 0137 } else {138 for d in 0..<p { centres[j, d] = sums[j, d] / Double(counts[j]) }139 }140 }141 }142 var inertia = 0.0143 var sizes = [Int](repeating: 0, count: k)144 for i in 0..<n { inertia += squaredDistance(data, i, centres, labels[i]); sizes[labels[i]] += 1 }145 return KMeansResult(centroids: centres, labels: labels, inertia: inertia, iterations: iterations, converged: converged,146 clusterSizes: sizes, silhouette: nil, runs: 1)147 }148149 /// Silhouette coefficients with Euclidean distance: s_i = (b_i − a_i)/max(a_i, b_i), where a_i is the150 /// mean distance to the other members of i's cluster and b_i the smallest mean distance to another151 /// cluster; s_i = 0 for singleton clusters. Returns the per-observation values and their mean.152 public static func silhouette(_ data: Matrix, labels: [Int]) -> (mean: Double, samples: [Double]) {153 let n = data.rows, p = data.cols154 guard labels.count == n, let maxLabel = labels.max(), maxLabel >= 1, (labels.min() ?? -1) >= 0 else { return (.nan, []) }155 let k = maxLabel + 1156 var counts = [Int](repeating: 0, count: k)157 for l in labels { counts[l] += 1 }158 var samples = [Double](repeating: 0, count: n)159 var sums = [Double](repeating: 0, count: k)160 for i in 0..<n {161 for j in 0..<k { sums[j] = 0 }162 for m in 0..<n where m != i {163 var s = 0.0164 for d in 0..<p { let t = data.data[i * p + d] - data.data[m * p + d]; s += t * t }165 sums[labels[m]] += s.squareRoot()166 }167 let own = labels[i]168 guard counts[own] > 1 else { samples[i] = 0; continue }169 let a = sums[own] / Double(counts[own] - 1)170 var b = Double.infinity171 for j in 0..<k where j != own && counts[j] > 0 { b = min(b, sums[j] / Double(counts[j])) }172 let denom = max(a, b)173 samples[i] = denom > 0 && b.isFinite ? (b - a) / denom : 0174 }175 return (Descriptive.mean(samples), samples)176 }177}178