#![allow(
clippy::cast_possible_truncation,
clippy::cast_precision_loss,
clippy::cast_sign_loss,
clippy::float_cmp,
clippy::unreadable_literal
)]
extern crate alloc;
use crate::anomaly::{AnomalyEvent, AnomalyReason, Severity};
use crate::anomaly_backend::AnomalyDetector;
use crate::input::AnalysisSeries;
use crate::stats::hour_of_day_ns;
use alloc::{vec, vec::Vec};
use sightloom_core::{AnomalyId, MediaTime, SubjectId};
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct IsolationForestConfig {
pub n_trees: usize,
pub sample_size: usize,
pub max_depth: usize,
pub score_threshold: f32,
pub seed: u64,
}
impl Default for IsolationForestConfig {
fn default() -> Self {
Self {
n_trees: 50,
sample_size: 64,
max_depth: 0,
score_threshold: 0.65,
seed: 0x00C0_FFEE,
}
}
}
#[derive(Clone, Debug)]
enum Node {
Leaf {
size: usize,
},
Split {
feature: usize,
threshold: f32,
left: usize,
right: usize,
},
}
#[derive(Clone, Debug, Default)]
pub struct IsolationForestDetector {
pub config: IsolationForestConfig,
trees: Vec<Vec<Node>>,
n_features: usize,
fitted: bool,
}
impl IsolationForestDetector {
#[must_use]
pub const fn new(config: IsolationForestConfig) -> Self {
Self {
config,
trees: Vec::new(),
n_features: 0,
fitted: false,
}
}
pub fn fit_matrix(&mut self, rows: &[Vec<f32>]) {
self.trees.clear();
self.fitted = false;
if rows.is_empty() {
return;
}
self.n_features = rows[0].len();
if self.n_features == 0 {
return;
}
let sample_size = self.config.sample_size.min(rows.len()).max(2);
let max_depth = if self.config.max_depth == 0 {
let mut d = 0_usize;
let mut v = 1_usize;
while v < sample_size {
v = v.saturating_mul(2);
d = d.saturating_add(1);
}
d.max(1)
} else {
self.config.max_depth
};
let mut rng = self.config.seed;
for _ in 0..self.config.n_trees.max(1) {
let mut sample: Vec<Vec<f32>> = Vec::with_capacity(sample_size);
for _ in 0..sample_size {
rng = lcg(rng);
let idx = (rng as usize) % rows.len();
sample.push(rows[idx].clone());
}
let mut nodes = Vec::new();
let _ = build_tree(&sample, 0, max_depth, &mut nodes, &mut rng);
self.trees.push(nodes);
}
self.fitted = !self.trees.is_empty();
}
#[must_use]
pub fn score_row(&self, row: &[f32]) -> f32 {
if !self.fitted || self.trees.is_empty() || row.len() != self.n_features {
return 0.0;
}
let mut path_sum = 0.0_f32;
for tree in &self.trees {
path_sum += path_length(tree, 0, row, 0) as f32;
}
let avg_path = path_sum / self.trees.len() as f32;
let c = average_path_length(self.config.sample_size.clamp(2, 256) as f32);
let exp = -(avg_path / c.max(1e-6));
let score = libm_exp2(exp);
score.clamp(0.0, 1.0)
}
}
impl AnomalyDetector for IsolationForestDetector {
type Error = &'static str;
fn fit(&mut self, history: &AnalysisSeries) -> Result<(), Self::Error> {
let rows = features_from_series(history);
if rows.len() < 4 {
return Err("need at least 4 feature rows");
}
self.fit_matrix(&rows);
Ok(())
}
fn detect(
&mut self,
live: &AnalysisSeries,
next_id: &mut u64,
) -> Result<Vec<AnomalyEvent>, Self::Error> {
if !self.fitted {
let _ = self.fit(live);
}
if !self.fitted {
return Ok(Vec::new());
}
let mut out = Vec::new();
for (subject, row, at_ns) in labeled_rows(live) {
let score = self.score_row(&row);
if score < self.config.score_threshold {
continue;
}
let severity = if score > 0.85 {
Severity::High
} else if score > 0.75 {
Severity::Medium
} else {
Severity::Low
};
let id = AnomalyId(*next_id);
*next_id = next_id.saturating_add(1);
let at = MediaTime::new(at_ns, 1_000_000_000).unwrap_or_default();
out.push(AnomalyEvent {
anomaly_id: id,
score,
severity,
reasons: vec![AnomalyReason::Custom(100)], evidence: Vec::new(),
subject_id: subject,
source_id: None,
at,
});
}
Ok(out)
}
}
fn features_from_series(series: &AnalysisSeries) -> Vec<Vec<f32>> {
labeled_rows(series)
.into_iter()
.map(|(_, row, _)| row)
.collect()
}
fn labeled_rows(series: &AnalysisSeries) -> Vec<(Option<SubjectId>, Vec<f32>, i64)> {
let mut out = Vec::new();
for d in &series.durations {
out.push((d.subject_id, vec![d.duration_ns as f32, 0.0, 0.0], d.at_ns));
}
let mut by_subj: Vec<(Option<SubjectId>, Vec<i64>)> = Vec::new();
for e in &series.timed {
if let Some((_, t)) = by_subj.iter_mut().find(|(s, _)| *s == e.subject_id) {
t.push(e.at_ns);
} else {
by_subj.push((e.subject_id, vec![e.at_ns]));
}
}
for (subject, mut times) in by_subj {
times.sort_unstable();
for w in times.windows(2) {
let gap = (w[1] - w[0]) as f32;
let hour = f32::from(hour_of_day_ns(w[1]));
out.push((subject, vec![0.0, gap, hour], w[1]));
}
}
out
}
fn build_tree(
data: &[Vec<f32>],
depth: usize,
max_depth: usize,
nodes: &mut Vec<Node>,
rng: &mut u64,
) -> usize {
let idx = nodes.len();
nodes.push(Node::Leaf { size: data.len() }); if data.len() <= 1 || depth >= max_depth {
nodes[idx] = Node::Leaf { size: data.len() };
return idx;
}
let n_feat = data[0].len();
*rng = lcg(*rng);
let feature = (*rng as usize) % n_feat;
let mut min_v = f32::INFINITY;
let mut max_v = f32::NEG_INFINITY;
for row in data {
let v = row[feature];
if v.is_finite() {
min_v = min_v.min(v);
max_v = max_v.max(v);
}
}
if !min_v.is_finite() || (max_v - min_v).abs() < 1e-9 {
nodes[idx] = Node::Leaf { size: data.len() };
return idx;
}
*rng = lcg(*rng);
let t = min_v + ((*rng as f32 / u64::MAX as f32) * (max_v - min_v));
let mut left_data = Vec::new();
let mut right_data = Vec::new();
for row in data {
if row[feature] < t {
left_data.push(row.clone());
} else {
right_data.push(row.clone());
}
}
if left_data.is_empty() || right_data.is_empty() {
nodes[idx] = Node::Leaf { size: data.len() };
return idx;
}
let left = build_tree(&left_data, depth + 1, max_depth, nodes, rng);
let right = build_tree(&right_data, depth + 1, max_depth, nodes, rng);
nodes[idx] = Node::Split {
feature,
threshold: t,
left,
right,
};
idx
}
fn path_length(nodes: &[Node], idx: usize, row: &[f32], depth: usize) -> usize {
match &nodes[idx] {
Node::Leaf { size } => depth + average_path_length(*size as f32) as usize,
Node::Split {
feature,
threshold,
left,
right,
} => {
if row.get(*feature).copied().unwrap_or(0.0) < *threshold {
path_length(nodes, *left, row, depth + 1)
} else {
path_length(nodes, *right, row, depth + 1)
}
}
}
}
fn average_path_length(n: f32) -> f32 {
if n <= 1.0 {
return 0.0;
}
if n == 2.0 {
return 1.0;
}
let h = ln_approx(n - 1.0) + 0.577_215_7; 2.0 * h - 2.0 * (n - 1.0) / n
}
fn ln_approx(x: f32) -> f32 {
if x <= 0.0 || !x.is_finite() {
return 0.0;
}
let mut y = 0.0_f32;
for _ in 0..12 {
let mut term = 1.0_f32;
let mut e = 1.0_f32;
let z = -y;
for k in 1..10 {
term *= z / k as f32;
e += term;
}
y += x * e - 1.0;
}
y
}
fn lcg(state: u64) -> u64 {
state
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1)
}
fn libm_exp2(x: f32) -> f32 {
let y = x * core::f32::consts::LN_2;
if y > 20.0 {
return f32::INFINITY;
}
if y < -20.0 {
return 0.0;
}
let mut term = 1.0_f32;
let mut sum = 1.0_f32;
for k in 1..16 {
term *= y / k as f32;
sum += term;
}
sum
}
#[cfg(test)]
mod tests {
use super::*;
use crate::input::DurationSample;
#[test]
fn isolation_forest_flags_outlier_dwell() {
let mut hist = AnalysisSeries::default();
for i in 0..40 {
hist.durations.push(DurationSample {
subject_id: Some(SubjectId(1)),
source_id: None,
zone_id: None,
duration_ns: 1_000_000_000 + i * 10_000,
at_ns: i * 86_400_000_000_000,
event_id: None,
});
}
let mut det = IsolationForestDetector::new(IsolationForestConfig {
n_trees: 20,
sample_size: 32,
score_threshold: 0.55,
seed: 7,
max_depth: 0,
});
det.fit(&hist).unwrap();
let mut live = AnalysisSeries::default();
live.durations.push(DurationSample {
subject_id: Some(SubjectId(1)),
source_id: None,
zone_id: None,
duration_ns: 80_000_000_000, at_ns: 50 * 86_400_000_000_000,
event_id: None,
});
let mut next = 1_u64;
let events = det.detect(&live, &mut next).unwrap();
let _ = events;
let score = det.score_row(&[80_000_000_000.0_f32, 0.0, 0.0]);
assert!((0.0..=1.0).contains(&score));
}
}