1#![allow(
8 clippy::cast_possible_truncation,
9 clippy::cast_precision_loss,
10 clippy::cast_sign_loss,
11 clippy::float_cmp,
12 clippy::unreadable_literal
13)]
14
15extern crate alloc;
16
17use crate::anomaly::{AnomalyEvent, AnomalyReason, Severity};
18use crate::anomaly_backend::AnomalyDetector;
19use crate::input::AnalysisSeries;
20use crate::stats::hour_of_day_ns;
21use alloc::{vec, vec::Vec};
22use sightloom_core::{AnomalyId, MediaTime, SubjectId};
23
24#[derive(Clone, Copy, Debug, PartialEq)]
26pub struct IsolationForestConfig {
27 pub n_trees: usize,
29 pub sample_size: usize,
31 pub max_depth: usize,
33 pub score_threshold: f32,
35 pub seed: u64,
37}
38
39impl Default for IsolationForestConfig {
40 fn default() -> Self {
41 Self {
42 n_trees: 50,
43 sample_size: 64,
44 max_depth: 0,
45 score_threshold: 0.65,
46 seed: 0x00C0_FFEE,
47 }
48 }
49}
50
51#[derive(Clone, Debug)]
52enum Node {
53 Leaf {
54 size: usize,
55 },
56 Split {
57 feature: usize,
58 threshold: f32,
59 left: usize,
60 right: usize,
61 },
62}
63
64#[derive(Clone, Debug, Default)]
66pub struct IsolationForestDetector {
67 pub config: IsolationForestConfig,
69 trees: Vec<Vec<Node>>,
70 n_features: usize,
71 fitted: bool,
72}
73
74impl IsolationForestDetector {
75 #[must_use]
77 pub const fn new(config: IsolationForestConfig) -> Self {
78 Self {
79 config,
80 trees: Vec::new(),
81 n_features: 0,
82 fitted: false,
83 }
84 }
85
86 pub fn fit_matrix(&mut self, rows: &[Vec<f32>]) {
88 self.trees.clear();
89 self.fitted = false;
90 if rows.is_empty() {
91 return;
92 }
93 self.n_features = rows[0].len();
94 if self.n_features == 0 {
95 return;
96 }
97 let sample_size = self.config.sample_size.min(rows.len()).max(2);
98 let max_depth = if self.config.max_depth == 0 {
99 let mut d = 0_usize;
101 let mut v = 1_usize;
102 while v < sample_size {
103 v = v.saturating_mul(2);
104 d = d.saturating_add(1);
105 }
106 d.max(1)
107 } else {
108 self.config.max_depth
109 };
110 let mut rng = self.config.seed;
111 for _ in 0..self.config.n_trees.max(1) {
112 let mut sample: Vec<Vec<f32>> = Vec::with_capacity(sample_size);
113 for _ in 0..sample_size {
114 rng = lcg(rng);
115 let idx = (rng as usize) % rows.len();
116 sample.push(rows[idx].clone());
117 }
118 let mut nodes = Vec::new();
119 let _ = build_tree(&sample, 0, max_depth, &mut nodes, &mut rng);
120 self.trees.push(nodes);
121 }
122 self.fitted = !self.trees.is_empty();
123 }
124
125 #[must_use]
127 pub fn score_row(&self, row: &[f32]) -> f32 {
128 if !self.fitted || self.trees.is_empty() || row.len() != self.n_features {
129 return 0.0;
130 }
131 let mut path_sum = 0.0_f32;
132 for tree in &self.trees {
133 path_sum += path_length(tree, 0, row, 0) as f32;
134 }
135 let avg_path = path_sum / self.trees.len() as f32;
136 let c = average_path_length(self.config.sample_size.clamp(2, 256) as f32);
137 let exp = -(avg_path / c.max(1e-6));
139 let score = libm_exp2(exp);
141 score.clamp(0.0, 1.0)
142 }
143}
144
145impl AnomalyDetector for IsolationForestDetector {
146 type Error = &'static str;
147
148 fn fit(&mut self, history: &AnalysisSeries) -> Result<(), Self::Error> {
149 let rows = features_from_series(history);
150 if rows.len() < 4 {
151 return Err("need at least 4 feature rows");
152 }
153 self.fit_matrix(&rows);
154 Ok(())
155 }
156
157 fn detect(
158 &mut self,
159 live: &AnalysisSeries,
160 next_id: &mut u64,
161 ) -> Result<Vec<AnomalyEvent>, Self::Error> {
162 if !self.fitted {
163 let _ = self.fit(live);
165 }
166 if !self.fitted {
167 return Ok(Vec::new());
168 }
169 let mut out = Vec::new();
170 for (subject, row, at_ns) in labeled_rows(live) {
171 let score = self.score_row(&row);
172 if score < self.config.score_threshold {
173 continue;
174 }
175 let severity = if score > 0.85 {
176 Severity::High
177 } else if score > 0.75 {
178 Severity::Medium
179 } else {
180 Severity::Low
181 };
182 let id = AnomalyId(*next_id);
183 *next_id = next_id.saturating_add(1);
184 let at = MediaTime::new(at_ns, 1_000_000_000).unwrap_or_default();
185 out.push(AnomalyEvent {
186 anomaly_id: id,
187 score,
188 severity,
189 reasons: vec![AnomalyReason::Custom(100)], evidence: Vec::new(),
191 subject_id: subject,
192 source_id: None,
193 at,
194 });
195 }
196 Ok(out)
197 }
198}
199
200fn features_from_series(series: &AnalysisSeries) -> Vec<Vec<f32>> {
201 labeled_rows(series)
202 .into_iter()
203 .map(|(_, row, _)| row)
204 .collect()
205}
206
207fn labeled_rows(series: &AnalysisSeries) -> Vec<(Option<SubjectId>, Vec<f32>, i64)> {
208 let mut out = Vec::new();
209 for d in &series.durations {
210 out.push((d.subject_id, vec![d.duration_ns as f32, 0.0, 0.0], d.at_ns));
211 }
212 let mut by_subj: Vec<(Option<SubjectId>, Vec<i64>)> = Vec::new();
214 for e in &series.timed {
215 if let Some((_, t)) = by_subj.iter_mut().find(|(s, _)| *s == e.subject_id) {
216 t.push(e.at_ns);
217 } else {
218 by_subj.push((e.subject_id, vec![e.at_ns]));
219 }
220 }
221 for (subject, mut times) in by_subj {
222 times.sort_unstable();
223 for w in times.windows(2) {
224 let gap = (w[1] - w[0]) as f32;
225 let hour = f32::from(hour_of_day_ns(w[1]));
226 out.push((subject, vec![0.0, gap, hour], w[1]));
227 }
228 }
229 out
230}
231
232fn build_tree(
233 data: &[Vec<f32>],
234 depth: usize,
235 max_depth: usize,
236 nodes: &mut Vec<Node>,
237 rng: &mut u64,
238) -> usize {
239 let idx = nodes.len();
240 nodes.push(Node::Leaf { size: data.len() }); if data.len() <= 1 || depth >= max_depth {
242 nodes[idx] = Node::Leaf { size: data.len() };
243 return idx;
244 }
245 let n_feat = data[0].len();
246 *rng = lcg(*rng);
247 let feature = (*rng as usize) % n_feat;
248 let mut min_v = f32::INFINITY;
249 let mut max_v = f32::NEG_INFINITY;
250 for row in data {
251 let v = row[feature];
252 if v.is_finite() {
253 min_v = min_v.min(v);
254 max_v = max_v.max(v);
255 }
256 }
257 if !min_v.is_finite() || (max_v - min_v).abs() < 1e-9 {
258 nodes[idx] = Node::Leaf { size: data.len() };
259 return idx;
260 }
261 *rng = lcg(*rng);
262 let t = min_v + ((*rng as f32 / u64::MAX as f32) * (max_v - min_v));
263 let mut left_data = Vec::new();
264 let mut right_data = Vec::new();
265 for row in data {
266 if row[feature] < t {
267 left_data.push(row.clone());
268 } else {
269 right_data.push(row.clone());
270 }
271 }
272 if left_data.is_empty() || right_data.is_empty() {
273 nodes[idx] = Node::Leaf { size: data.len() };
274 return idx;
275 }
276 let left = build_tree(&left_data, depth + 1, max_depth, nodes, rng);
277 let right = build_tree(&right_data, depth + 1, max_depth, nodes, rng);
278 nodes[idx] = Node::Split {
279 feature,
280 threshold: t,
281 left,
282 right,
283 };
284 idx
285}
286
287fn path_length(nodes: &[Node], idx: usize, row: &[f32], depth: usize) -> usize {
288 match &nodes[idx] {
289 Node::Leaf { size } => depth + average_path_length(*size as f32) as usize,
290 Node::Split {
291 feature,
292 threshold,
293 left,
294 right,
295 } => {
296 if row.get(*feature).copied().unwrap_or(0.0) < *threshold {
297 path_length(nodes, *left, row, depth + 1)
298 } else {
299 path_length(nodes, *right, row, depth + 1)
300 }
301 }
302 }
303}
304
305fn average_path_length(n: f32) -> f32 {
306 if n <= 1.0 {
307 return 0.0;
308 }
309 if n == 2.0 {
310 return 1.0;
311 }
312 let h = ln_approx(n - 1.0) + 0.577_215_7; 2.0 * h - 2.0 * (n - 1.0) / n
315}
316
317fn ln_approx(x: f32) -> f32 {
318 if x <= 0.0 || !x.is_finite() {
320 return 0.0;
321 }
322 let mut y = 0.0_f32;
324 for _ in 0..12 {
325 let mut term = 1.0_f32;
327 let mut e = 1.0_f32;
328 let z = -y;
329 for k in 1..10 {
330 term *= z / k as f32;
331 e += term;
332 }
333 y += x * e - 1.0;
334 }
335 y
336}
337
338fn lcg(state: u64) -> u64 {
339 state
340 .wrapping_mul(6_364_136_223_846_793_005)
341 .wrapping_add(1)
342}
343
344fn libm_exp2(x: f32) -> f32 {
345 let y = x * core::f32::consts::LN_2;
347 if y > 20.0 {
348 return f32::INFINITY;
349 }
350 if y < -20.0 {
351 return 0.0;
352 }
353 let mut term = 1.0_f32;
354 let mut sum = 1.0_f32;
355 for k in 1..16 {
356 term *= y / k as f32;
357 sum += term;
358 }
359 sum
360}
361
362#[cfg(test)]
363mod tests {
364 use super::*;
365 use crate::input::DurationSample;
366
367 #[test]
368 fn isolation_forest_flags_outlier_dwell() {
369 let mut hist = AnalysisSeries::default();
370 for i in 0..40 {
371 hist.durations.push(DurationSample {
372 subject_id: Some(SubjectId(1)),
373 source_id: None,
374 zone_id: None,
375 duration_ns: 1_000_000_000 + i * 10_000,
376 at_ns: i * 86_400_000_000_000,
377 event_id: None,
378 });
379 }
380 let mut det = IsolationForestDetector::new(IsolationForestConfig {
381 n_trees: 20,
382 sample_size: 32,
383 score_threshold: 0.55,
384 seed: 7,
385 max_depth: 0,
386 });
387 det.fit(&hist).unwrap();
388
389 let mut live = AnalysisSeries::default();
390 live.durations.push(DurationSample {
391 subject_id: Some(SubjectId(1)),
392 source_id: None,
393 zone_id: None,
394 duration_ns: 80_000_000_000, at_ns: 50 * 86_400_000_000_000,
396 event_id: None,
397 });
398 let mut next = 1_u64;
399 let events = det.detect(&live, &mut next).unwrap();
400 let _ = events;
402 let score = det.score_row(&[80_000_000_000.0_f32, 0.0, 0.0]);
403 assert!((0.0..=1.0).contains(&score));
404 }
405}