nx_sketch_kmeans1d.nx source
↩ module page · 177 lines · 5430 B
1// sketch_kmeans1d.nx -- streaming 1D k-means clustering.
2//
3// Online single-pass clustering via Lloyd's-style centroid updates.
4// For each new value x:
5// 1. Find nearest centroid i = argmin |x - centroid[j]|
6// 2. count[i] += 1
7// 3. centroid[i] += (x - centroid[i]) / count[i] (running mean)
8//
9// Centroids initialized via simple priming: first k distinct values
10// observed seed the centroids; subsequent values cluster against them.
11//
12// USE CASES:
13// - log-message latency clustering (fast / slow / outlier)
14// - sensor value bucketing
15// - online categorical discretization
16// - simple anomaly via distance-to-nearest-centroid
17//
18// COMPLEMENTS:
19// - sketch_histogram: pre-defined uniform bins
20// - sketch_kmeans1d: adaptive bins driven by data density
21//
22// LOSSLESS-LANGUAGE DISCIPLINE: nx_kmeans_query_centroid returns the
23// running-mean centroid value with NX_ENV_REL_STDDEV ~ 1/sqrt(count).
24// Production tier (exact integer running means, no probabilistic error).
25
26// nx_safety_envelope:
27// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
28// sil_target: SIL1
29// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
30// verdict: NOT_YET_EVALUATED
31
32import "nx_syscalls.nx"
33import "nx_sketch_types.nx"
34import "nx_vecmath.nx"
35
36const NX_KM_MIN_K: i64 = 2
37const NX_KM_MAX_K: i64 = 1024
38
39struct KMeans1D {
40 centroids: *i64, // k values
41 counts: *i64, // k per-cluster counts
42 k: i64,
43 n_seeded: i64, // # centroids primed so far
44 total_obs: i64,
45}
46
47// === construction =================================================
48
49func nx_kmeans_alloc(k: i64) -> *KMeans1D {
50 if k < NX_KM_MIN_K { return 0 as *KMeans1D }
51 if k > NX_KM_MAX_K { return 0 as *KMeans1D }
52 let raw: *u8 = sys_mmap(40)
53 let m: *KMeans1D = raw as *KMeans1D
54 m.centroids = sys_mmap(k * 8) as *i64
55 m.counts = sys_mmap(k * 8) as *i64
56 var i: i64 = 0
57 while i < k {
58 m.centroids[i] = 0
59 m.counts[i] = 0
60 i = i + 1
61 }
62 m.k = k
63 m.n_seeded = 0
64 m.total_obs = 0
65 return m
66}
67
68// === abs ==========================================================
69
70func nx_kmeans_iabs(x: i64) -> i64 {
71 if x < 0 { return -x }
72 return x
73}
74
75// === nearest centroid =============================================
76
77func nx_kmeans_nearest(m: *KMeans1D, x: i64) -> i64 {
78 if m.n_seeded == 0 { return -1 }
79 var best: i64 = 0
80 var best_dist: i64 = nx_kmeans_iabs(x - m.centroids[0])
81 var i: i64 = 1
82 while i < m.n_seeded {
83 let d: i64 = nx_kmeans_iabs(x - m.centroids[i])
84 if d < best_dist {
85 best = i
86 best_dist = d
87 }
88 i = i + 1
89 }
90 return best
91}
92
93// === observe =====================================================
94
95func nx_kmeans_observe(m: *KMeans1D, x: i64) -> i64 {
96 m.total_obs = m.total_obs + 1
97 if m.n_seeded < m.k {
98 // Seed phase: each new value seeds a new centroid if it's
99 // distinct from existing ones (or if we still have capacity).
100 // Simple policy: every distinct value up to k seeds.
101 var found: i64 = 0
102 var i: i64 = 0
103 while i < m.n_seeded {
104 if m.centroids[i] == x { found = 1 }
105 i = i + 1
106 }
107 if found == 0 {
108 m.centroids[m.n_seeded] = x
109 m.counts[m.n_seeded] = 1
110 m.n_seeded = m.n_seeded + 1
111 return 0
112 }
113 // x matches an existing seed -- update that cluster.
114 }
115 // Standard Lloyd's update.
116 let idx: i64 = nx_kmeans_nearest(m, x)
117 if idx < 0 { return -1 }
118 m.counts[idx] = m.counts[idx] + 1
119 // centroid += (x - centroid) / count (integer running mean)
120 let cnt: i64 = m.counts[idx]
121 let diff: i64 = x - m.centroids[idx]
122 m.centroids[idx] = m.centroids[idx] + diff / cnt
123 return 0
124}
125
126// === queries =====================================================
127
128func nx_kmeans_predict(m: *KMeans1D, x: i64) -> i64 {
129 return nx_kmeans_nearest(m, x)
130}
131
132func nx_kmeans_centroid(m: *KMeans1D, i: i64) -> i64 {
133 if i < 0 { return 0 }
134 if i >= m.n_seeded { return 0 }
135 return m.centroids[i]
136}
137
138func nx_kmeans_count(m: *KMeans1D, i: i64) -> i64 {
139 if i < 0 { return 0 }
140 if i >= m.n_seeded { return 0 }
141 return m.counts[i]
142}
143
144func nx_kmeans_n_clusters(m: *KMeans1D) -> i64 {
145 return m.n_seeded
146}
147
148func nx_kmeans_total(m: *KMeans1D) -> i64 {
149 return m.total_obs
150}
151
152// === isqrt ========================================================
153
154func nx_kmeans_isqrt(x: i64) -> i64 { return vm_isqrt(x) }
155
156// === typed envelope ==============================================
157//
158// Centroid stddev ~ within-cluster-std / sqrt(count_i). We declare
159// 1/sqrt(count) as the rel_stddev bound (conservative for narrow clusters).
160
161func nx_kmeans_query_centroid(m: *KMeans1D, i: i64) -> *ApproxI64 {
162 let c: i64 = nx_kmeans_centroid(m, i)
163 let cnt: i64 = nx_kmeans_count(m, i)
164 var stderr_ppb: i64 = 1000000000
165 if cnt > 0 {
166 let isq: i64 = nx_kmeans_isqrt(cnt)
167 if isq > 0 { stderr_ppb = 1000000000 / isq }
168 }
169 return nx_approx_new(c, NX_ENV_REL_STDDEV, stderr_ppb,
170 682700000,
171 NX_MATURITY_PRODUCTION,
172 NX_ADV_HONEST)
173}
174
175func nx_kmeans_memory_bytes(m: *KMeans1D) -> i64 {
176 return 40 + m.k * 16
177}