SPB Git

Repository Public

KMeans.swift 8.6 KB 178 lines swift

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
Files main
Menu

Theme