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