SPB Git

Repository Public

HierarchicalClustering.swift 5.0 KB 111 lines swift

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

Theme