SPB Git

Repository Public

ClusteringTools.swift 10.7 KB 145 lines swift

1import Foundation2import SheetCore3import Statistics4import AnalysisKit56enum ClusterSupport {7    /// Cluster labels numbered from 1, aligned with the data rows.8    static func labelAction(frame: DataFrame, rows: [Int], labels: [Int], name: String) -> ResultAction {9        Sup.writeColumns(id: "write-labels", title: L("Write Cluster Labels"), label: L("Write Cluster Labels"), frame: frame, names: [name],10                         columns: [frame.expand(labels.map { Double($0 + 1) }, rows: rows)])11    }1213    /// Mean of each variable inside each cluster, in the original units.14    static func profile(data: Matrix, names: [String], labels: [Int], k: Int, title: String) -> ReportTable {15        var rows: [[Value]] = [[.text(L("Cluster")), .text(L("Size"))] + names.map { .text($0) }]16        for c in 0..<k {17            let members = labels.indices.filter { labels[$0] == c }18            let means: [Value] = (0..<data.cols).map { j in members.isEmpty ? .blank : .finite(members.reduce(0) { $0 + data[$1, j] } / Double(members.count)) }19            rows.append([.text(L("Cluster %d", c + 1)), .number(Double(members.count))] + means)20        }21        return ReportTable(title: title, rows: rows, columnFormats: [1: .integer])22    }2324    static func sizeChart(_ sizes: [Int]) -> ChartBlock {25        ChartBlock(title: L("Cluster sizes"), spec: ChartKit.columns(categories: sizes.indices.map { L("Cluster %d", $0 + 1) }, series: [(L("Observations"), sizes.map(Double.init))],26                                                                     xTitle: L("Cluster"), yTitle: L("Observations")),27                   summary: L("Bar chart of the sizes of %d clusters: %@.", sizes.count, sizes.map(String.init).joined(separator: ", ")), height: 200)28    }29}3031/// k-means clustering (Lloyd, k-means++ seeding).32enum KMeansTool {33    static let descriptor: ToolDescriptor = {34        var t = ToolDescriptor(35            id: "multivariate.kmeans", title: L("k-Means Clustering"), group: L("Multivariate"), systemImage: "circle.hexagongrid",36            summary: L("Partitions the observations into k clusters that minimise the within-cluster sum of squares."),37            fields: [38                .range("data", L("Data range")),39                .columns("vars", L("Variables")),40                .toggle("standardize", L("Standardize the variables (z-scores)"), true, help: L("Recommended when the variables have different units.")),41                .integer("k", L("Number of clusters k"), 3, min: 1, max: 50),42                .integer("restarts", L("Random starts"), 10, min: 1, max: 200),43                .integer("seed", L("Random seed"), 1, min: 0, max: 2_000_000_000),44            ],45            info: [46                L("Lloyd's algorithm with squared Euclidean distance; from fixed starting centres it matches scikit-learn exactly."),47                L("Starts use plain k-means++ seeding with the xoshiro256** generator: a given seed always gives the same result, but individual runs are not comparable with scikit-learn (which uses a greedy variant)."),48                L("The silhouette is the mean silhouette coefficient over all observations (O(n²))."),49            ],50            run: run)51        t.demo = { _, v in v.set("data", range: "Regression!A1:G121"); v.set("vars", columns: [0, 2, 3]) }52        return t53    }()5455    static func run(_ input: ToolInput) throws -> ToolResult {56        let standardize = input.values.bool("standardize")57        let raw = try Sup.matrix(input, atLeast: 1, standardize: false)58        let m = standardize ? try Sup.matrix(input, atLeast: 1, standardize: true) : raw59        let k = input.values.int("k")60        guard k >= 1, k <= m.rows.count else { throw ToolError(L("k must be between 1 and the number of complete rows (%d).", m.rows.count)) }61        let seed = Sup.seed(input)62        let r = try KMeans.fit(m.data, k: k, seed: seed, restarts: max(input.values.int("restarts"), 1), computeSilhouette: m.rows.count <= 5000)63        var centroids: [[Value]] = [[.text(L("Cluster")), .text(L("Size"))] + m.names.map { .text($0) }]64        for c in 0..<k { centroids.append([.text(L("Cluster %d", c + 1)), .number(Double(r.clusterSizes[c]))] + (0..<m.data.cols).map { .finite(r.centroids[c, $0]) }) }65        var blocks: [ResultBlock] = [66            .metrics([Metric(L("Clusters"), Double(k), .integer), Metric(L("Within-cluster sum of squares"), r.inertia),67                      Metric(L("Mean silhouette"), r.silhouette ?? .nan, .fixed(4)), Metric(L("Iterations"), Double(r.iterations), .integer)]),68            .table(ReportTable(title: standardize ? L("Centroids (standardized units)") : L("Centroids"), rows: centroids, columnFormats: [1: .integer])),69        ]70        if standardize { blocks.append(.table(ClusterSupport.profile(data: raw.data, names: raw.names, labels: r.labels, k: k, title: L("Cluster means (original units)")))) }71        blocks.append(.chart(ClusterSupport.sizeChart(r.clusterSizes)))72        var notes = [Sup.listwiseNote(used: m.rows.count, of: m.frame.rowCount), L("Seed %d, %d random starts; the run with the smallest sum of squares is reported.", Int(seed), r.runs)]73        if !r.converged { notes.append(L("The iteration limit was reached before the assignments stopped changing.")) }74        if r.silhouette == nil { notes.append(L("The silhouette is not computed for k = 1 or for more than 5,000 observations.")) }75        blocks.append(.note(notes))76        return ToolResult(title: L("k-Means Clustering"), subtitle: L("%@ — %d variables, k = %d", m.frame.label, m.names.count, k), blocks: blocks,77                          actions: [ClusterSupport.labelAction(frame: m.frame, rows: m.rows, labels: r.labels, name: L("Cluster (k-means)"))], sheetName: L("k-means"))78    }79}8081/// Agglomerative hierarchical clustering.82enum HierarchicalTool {83    static let maxObservations = 15008485    static let descriptor: ToolDescriptor = {86        var t = ToolDescriptor(87            id: "multivariate.hierarchical", title: L("Hierarchical Clustering"), group: L("Multivariate"), systemImage: "point.3.connected.trianglepath.dotted",88            summary: L("Builds a cluster tree by successive merges and cuts it into a chosen number of clusters."),89            fields: [90                .range("data", L("Data range")),91                .columns("vars", L("Variables")),92                .toggle("standardize", L("Standardize the variables (z-scores)"), true),93                .choice("linkage", L("Linkage"), [FieldOption("ward", L("Ward (minimum variance)")), FieldOption("average", L("Average (UPGMA)")),94                                                  FieldOption("complete", L("Complete (farthest neighbour)")), FieldOption("single", L("Single (nearest neighbour)"))]),95                .integer("k", L("Cut into k clusters"), 3, min: 1, max: 50),96            ],97            info: [98                L("Euclidean distances with Lance–Williams updates; merge order, distances and partitions match SciPy linkage / fcluster."),99                L("The algorithm needs O(n³) time and O(n²) memory: it is limited to 1,500 observations here."),100                L("Centroid, median and weighted linkages and other distance metrics are not shipped."),101            ],102            run: run)103        t.demo = { _, v in v.set("data", range: "Panel!A1:E61"); v.set("vars", columns: [2, 3, 4]) }104        return t105    }()106107    static func run(_ input: ToolInput) throws -> ToolResult {108        let standardize = input.values.bool("standardize")109        let raw = try Sup.matrix(input, atLeast: 1, standardize: false)110        guard raw.rows.count <= maxObservations else {111            throw ToolError(L("Hierarchical clustering is limited to %d observations (the range has %d complete rows) because its cost grows with n³.", maxObservations, raw.rows.count))112        }113        let m = standardize ? try Sup.matrix(input, atLeast: 1, standardize: true) : raw114        let method = HierarchicalClustering.Linkage(rawValue: input.values.choice("linkage")) ?? .ward115        let k = input.values.int("k")116        guard k >= 1, k <= m.rows.count else { throw ToolError(L("k must be between 1 and the number of complete rows (%d).", m.rows.count)) }117        try input.checkCancelled()118        let r = try HierarchicalClustering.linkage(m.data, method: method)119        let labels = try r.labels(clusters: k)120        var sizes = [Int](repeating: 0, count: k)121        for l in labels where l < k { sizes[l] += 1 }122        func node(_ i: Int) -> Value { i < r.n ? .text(L("Obs. %d", i + 1)) : .text(L("Merge %d", i - r.n + 1)) }123        var rows: [[Value]] = [[.text(L("Step")), .text(L("First")), .text(L("Second")), .text(L("Distance")), .text(L("Size"))]]124        for (i, g) in r.merges.enumerated() { rows.append([.number(Double(i + 1)), node(g.first), node(g.second), .finite(g.distance), .number(Double(g.size))]) }125        let tail = Array(r.merges.suffix(min(20, r.merges.count)))126        let heights = ChartBlock(title: L("Distances of the last merges"),127                                 spec: ChartKit.columns(categories: tail.indices.map { String(max(tail.count - $0, 1)) }, series: [(L("Distance"), tail.map(\.distance))],128                                                        xTitle: L("Clusters remaining after the merge"), yTitle: L("Linkage distance")),129                                 summary: L("Linkage distances of the last %d merges; the final merge is at distance %@.", tail.count, Fmt.number(tail.last?.distance ?? .nan, locale: input.locale)),130                                 height: 220)131        let blocks: [ResultBlock] = [132            .metrics([Metric(L("Observations"), Double(r.n), .integer), Metric(L("Clusters"), Double(k), .integer),133                      Metric(L("Largest cluster"), Double(sizes.max() ?? 0), .integer), Metric(L("Smallest cluster"), Double(sizes.min() ?? 0), .integer)]),134            .table(ClusterSupport.profile(data: raw.data, names: raw.names, labels: labels, k: k, title: L("Cluster means (original units)"))),135            .charts([heights, ClusterSupport.sizeChart(sizes)]),136            .table(ReportTable(title: L("Linkage table"), rows: rows, headerColumn: false, columnFormats: [0: .integer, 3: .fixed(4), 4: .integer],137                               note: L("A large jump in distance suggests cutting the tree just before that merge."))),138            .note([Sup.listwiseNote(used: m.rows.count, of: m.frame.rowCount),139                   standardize ? L("Distances are Euclidean on z-scores.") : L("Distances are Euclidean on the original units.")]),140        ]141        return ToolResult(title: L("Hierarchical Clustering"), subtitle: L("%@ — %d variables, k = %d", m.frame.label, m.names.count, k), blocks: blocks,142                          actions: [ClusterSupport.labelAction(frame: m.frame, rows: m.rows, labels: labels, name: L("Cluster (hierarchical)"))], sheetName: L("Clustering"))143    }144}145
Files main
Menu

Theme