nx_sketch_kmeans1d.nx source
↩ module page · 191 lines · 5724 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"
34
35const NX_KM_MIN_K: i64 = 2
36const NX_KM_MAX_K: i64 = 1024
37
38struct KMeans1D {
39 centroids: *i64, // k values
40 counts: *i64, // k per-cluster counts
41 k: i64,
42 n_seeded: i64, // # centroids primed so far
43 total_obs: i64,
44}
45
46// === construction =================================================
47
48func nx_kmeans_alloc(k: i64) -> *KMeans1D {
49 if k < NX_KM_MIN_K { return 0 as *KMeans1D }
50 if k > NX_KM_MAX_K { return 0 as *KMeans1D }
51 let raw: *u8 = sys_mmap(40)
52 let m: *KMeans1D = raw as *KMeans1D
53 m.centroids = sys_mmap(k * 8) as *i64
54 m.counts = sys_mmap(k * 8) as *i64
55 var i: i64 = 0
56 while i < k {
57 m.centroids[i] = 0
58 m.counts[i] = 0
59 i = i + 1
60 }
61 m.k = k
62 m.n_seeded = 0
63 m.total_obs = 0
64 return m
65}
66
67// === abs ==========================================================
68
69func nx_kmeans_iabs(x: i64) -> i64 {
70 if x < 0 { return -x }
71 return x
72}
73
74// === nearest centroid =============================================
75
76func nx_kmeans_nearest(m: *KMeans1D, x: i64) -> i64 {
77 if m.n_seeded == 0 { return -1 }
78 var best: i64 = 0
79 var best_dist: i64 = nx_kmeans_iabs(x - m.centroids[0])
80 var i: i64 = 1
81 while i < m.n_seeded {
82 let d: i64 = nx_kmeans_iabs(x - m.centroids[i])
83 if d < best_dist {
84 best = i
85 best_dist = d
86 }
87 i = i + 1
88 }
89 return best
90}
91
92// === observe =====================================================
93
94func nx_kmeans_observe(m: *KMeans1D, x: i64) -> i64 {
95 m.total_obs = m.total_obs + 1
96 if m.n_seeded < m.k {
97 // Seed phase: each new value seeds a new centroid if it's
98 // distinct from existing ones (or if we still have capacity).
99 // Simple policy: every distinct value up to k seeds.
100 var found: i64 = 0
101 var i: i64 = 0
102 while i < m.n_seeded {
103 if m.centroids[i] == x { found = 1 }
104 i = i + 1
105 }
106 if found == 0 {
107 m.centroids[m.n_seeded] = x
108 m.counts[m.n_seeded] = 1
109 m.n_seeded = m.n_seeded + 1
110 return 0
111 }
112 // x matches an existing seed -- update that cluster.
113 }
114 // Standard Lloyd's update.
115 let idx: i64 = nx_kmeans_nearest(m, x)
116 if idx < 0 { return -1 }
117 m.counts[idx] = m.counts[idx] + 1
118 // centroid += (x - centroid) / count (integer running mean)
119 let cnt: i64 = m.counts[idx]
120 let diff: i64 = x - m.centroids[idx]
121 m.centroids[idx] = m.centroids[idx] + diff / cnt
122 return 0
123}
124
125// === queries =====================================================
126
127func nx_kmeans_predict(m: *KMeans1D, x: i64) -> i64 {
128 return nx_kmeans_nearest(m, x)
129}
130
131func nx_kmeans_centroid(m: *KMeans1D, i: i64) -> i64 {
132 if i < 0 { return 0 }
133 if i >= m.n_seeded { return 0 }
134 return m.centroids[i]
135}
136
137func nx_kmeans_count(m: *KMeans1D, i: i64) -> i64 {
138 if i < 0 { return 0 }
139 if i >= m.n_seeded { return 0 }
140 return m.counts[i]
141}
142
143func nx_kmeans_n_clusters(m: *KMeans1D) -> i64 {
144 return m.n_seeded
145}
146
147func nx_kmeans_total(m: *KMeans1D) -> i64 {
148 return m.total_obs
149}
150
151// === isqrt ========================================================
152
153func nx_kmeans_isqrt(x: i64) -> i64 {
154 if x < 0 { return 0 }
155 if x == 0 { return 0 }
156 if x < 4 { return 1 }
157 var g: i64 = (x >> 1) + 1
158 var iter: i64 = 0
159 while iter < 64 {
160 let next_g: i64 = (g + x / g) / 2
161 if next_g >= g { iter = 64 }
162 if next_g < g {
163 g = next_g
164 iter = iter + 1
165 }
166 }
167 return g
168}
169
170// === typed envelope ==============================================
171//
172// Centroid stddev ~ within-cluster-std / sqrt(count_i). We declare
173// 1/sqrt(count) as the rel_stddev bound (conservative for narrow clusters).
174
175func nx_kmeans_query_centroid(m: *KMeans1D, i: i64) -> *ApproxI64 {
176 let c: i64 = nx_kmeans_centroid(m, i)
177 let cnt: i64 = nx_kmeans_count(m, i)
178 var stderr_ppb: i64 = 1000000000
179 if cnt > 0 {
180 let isq: i64 = nx_kmeans_isqrt(cnt)
181 if isq > 0 { stderr_ppb = 1000000000 / isq }
182 }
183 return nx_approx_new(c, NX_ENV_REL_STDDEV, stderr_ppb,
184 682700000,
185 NX_MATURITY_PRODUCTION,
186 NX_ADV_HONEST)
187}
188
189func nx_kmeans_memory_bytes(m: *KMeans1D) -> i64 {
190 return 40 + m.k * 16
191}