Repository Public
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