Repository Public
1import Foundation2import SheetCore34/// Agglomerative clustering result (a dendrogram).5public struct HierarchicalResult: Sendable, Hashable, Codable, TableReport {6 public struct Merge: Sendable, Hashable, Codable {7 /// Indices of the merged clusters, first < second: 0…n−1 are observations, n + i is the cluster formed by merge i.8 public var first: Int9 public var second: Int10 /// Linkage distance at which they merge.11 public var distance: Double12 /// Observations in the new cluster.13 public var size: Int14 }15 public var method: HierarchicalClustering.Linkage16 /// Number of observations.17 public var n: Int18 /// The n − 1 merges in order (same layout as SciPy's linkage matrix).19 public var merges: [Merge]2021 /// Cuts the tree into `clusters` groups (undoing the last merges). Labels are 0-based and numbered22 /// in order of first appearance among the observations.23 public func labels(clusters: Int) throws -> [Int] {24 guard clusters >= 1, clusters <= n else { throw StatError.invalidInput("clusters must be between 1 and \(n)") }25 var parent = Array(0..<(2 * n - 1))26 func find(_ x: Int) -> Int { var r = x; while parent[r] != r { r = parent[r] }; return r }27 for (i, m) in merges.prefix(n - clusters).enumerated() {28 parent[find(m.first)] = n + i29 parent[find(m.second)] = n + i30 }31 var map = [Int: Int]()32 return (0..<n).map { obs in33 let root = find(obs)34 if let l = map[root] { return l }35 map[root] = map.count36 return map[root]!37 }38 }3940 public func table() -> [[Value]] {41 var out: [[Value]] = [[.text("Step"), .text("Cluster A"), .text("Cluster B"), .text("Distance (\(method.rawValue))"), .text("Size")]]42 for (i, m) in merges.enumerated() {43 out.append([Report.int(i + 1), Report.int(m.first), Report.int(m.second), Report.num(m.distance), Report.int(m.size)])44 }45 return out46 }47}4849public enum HierarchicalClustering {50 public enum Linkage: String, Sendable, Codable, CaseIterable {51 /// Nearest neighbours.52 case single53 /// Farthest neighbours.54 case complete55 /// Unweighted average of pairwise distances (UPGMA).56 case average57 /// Ward's minimum-variance criterion (distances reported on SciPy's scale: √ of the Lance–Williams58 /// update on squared Euclidean distances).59 case ward60 }6162 /// Agglomerative clustering with Euclidean distances (observations in rows) by the Lance–Williams63 /// updates. O(n³) time and O(n²) memory: intended for up to a few thousand observations.64 /// Ties between equal distances are broken by the lowest pair of cluster indices.65 public static func linkage(_ data: Matrix, method: Linkage = .ward) throws -> HierarchicalResult {66 let n = data.rows, p = data.cols67 guard n >= 2, p >= 1 else { throw StatError.insufficientData("clustering needs at least 2 observations") }68 guard data.data.allSatisfy(\.isFinite) else { throw StatError.invalidInput("data contain non-finite values") }69 let squared = method == .ward70 var d = [Double](repeating: 0, count: n * n)71 for i in 0..<n {72 for j in 0..<i {73 var s = 0.074 for c in 0..<p { let t = data.data[i * p + c] - data.data[j * p + c]; s += t * t }75 let v = squared ? s : s.squareRoot()76 d[i * n + j] = v; d[j * n + i] = v77 }78 }79 var active = [Bool](repeating: true, count: n)80 var ids = Array(0..<n)81 var sizes = [Int](repeating: 1, count: n)82 var merges = [HierarchicalResult.Merge]()83 for step in 0..<(n - 1) {84 var bi = -1, bj = -1, bd = Double.infinity85 for i in 0..<n where active[i] {86 for j in (i + 1)..<n where active[j] && d[i * n + j] < bd { bd = d[i * n + j]; bi = i; bj = j }87 }88 let ni = Double(sizes[bi]), nj = Double(sizes[bj])89 for k in 0..<n where active[k] && k != bi && k != bj {90 let dik = d[bi * n + k], djk = d[bj * n + k]91 let v: Double92 switch method {93 case .single: v = min(dik, djk)94 case .complete: v = max(dik, djk)95 case .average: v = (ni * dik + nj * djk) / (ni + nj)96 case .ward:97 let nk = Double(sizes[k])98 v = ((ni + nk) * dik + (nj + nk) * djk - nk * bd) / (ni + nj + nk)99 }100 d[bi * n + k] = v; d[k * n + bi] = v101 }102 let a = min(ids[bi], ids[bj]), b = max(ids[bi], ids[bj])103 sizes[bi] += sizes[bj]104 merges.append(.init(first: a, second: b, distance: squared ? max(bd, 0).squareRoot() : bd, size: sizes[bi]))105 ids[bi] = n + step106 active[bj] = false107 }108 return HierarchicalResult(method: method, n: n, merges: merges)109 }110}111