Skip to main content

sightloom_analysis/
isolation_forest.rs

1//! Lightweight Isolation Forest anomaly backend (pure Rust, no sklearn).
2//!
3//! Fits on feature vectors extracted from [`AnalysisSeries`] dwell / gap /
4//! hour signals. Not a production sklearn parity port — a portable classical
5//! backend behind [`crate::AnomalyDetector`].
6
7#![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/// Isolation Forest configuration.
25#[derive(Clone, Copy, Debug, PartialEq)]
26pub struct IsolationForestConfig {
27    /// Number of trees.
28    pub n_trees: usize,
29    /// Subsample size per tree.
30    pub sample_size: usize,
31    /// Max tree height (`0` = `ceil(log2(sample_size))`).
32    pub max_depth: usize,
33    /// Scores above this (normalized) flag anomalies.
34    pub score_threshold: f32,
35    /// Deterministic seed for splits.
36    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/// Fitted isolation forest on dense feature rows.
65#[derive(Clone, Debug, Default)]
66pub struct IsolationForestDetector {
67    /// Config.
68    pub config: IsolationForestConfig,
69    trees: Vec<Vec<Node>>,
70    n_features: usize,
71    fitted: bool,
72}
73
74impl IsolationForestDetector {
75    /// Creates an unfitted detector.
76    #[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    /// Fits on an explicit feature matrix (`rows × features`).
87    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            // ceil(log2(n)) without libm
100            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    /// Anomaly score in roughly `[0, 1]` (higher = more anomalous).
126    #[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        // score = 2^(-E(h)/c)
138        let exp = -(avg_path / c.max(1e-6));
139        // 2^x approx
140        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            // Fit on live if not fitted (smoke path).
164            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)], // isolation-forest tag
190                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    // Gaps as features
213    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() }); // placeholder
241    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    // c(n) = 2 H(n-1) - 2(n-1)/n
313    let h = ln_approx(n - 1.0) + 0.577_215_7; // Euler-Mascheroni approx
314    2.0 * h - 2.0 * (n - 1.0) / n
315}
316
317fn ln_approx(x: f32) -> f32 {
318    // log via change of base from exp2 inverse (coarse).
319    if x <= 0.0 || !x.is_finite() {
320        return 0.0;
321    }
322    // Newton for ln: y_{n+1} = y_n + x*e^{-y_n} - 1 ... use series around 1
323    let mut y = 0.0_f32;
324    for _ in 0..12 {
325        // e^{-y} approx
326        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    // 2^x = e^(x ln2); use Taylor for e^y
346    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, // huge dwell
395            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        // May or may not flag depending on tree randomness — at least runs.
401        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}