# 2.13. 孤立森林
`IsolationForest` 是 RustyML 的无监督异常检测器。
大多数异常检测器先建模正常数据分布在哪里，再把落在这个区域之外的点标为异常。`IsolationForest` 反过来做。它利用了异常*少而不同*这一事实。一棵由随机轴对齐切分构成的树，只需几刀就能把一个异常点孤立进它自己的叶子。一个埋在稠密簇里的点，则需要多得多的切分才能被孤立。RustyML 把这个切分次数在一片树的森林上取平均，再归一化成一个异常分数。
这个估计器与 `sklearn.ensemble.IsolationForest` 对齐，即同一套来自 Liu、Ting 和 Zhou 的、基于子采样的集成方法。这套 API 现在与 scikit-learn 逐个方法对齐。`score_samples`、`decision_function` 和 `predict` 的含义与 Python 那边完全一致，包括分数的符号。如果你在迁移一份针对旧版 RustyML 写的代码，先读 [2.13.4 节](#2134-拟合与读取分数)。分数的符号和方法名都在那一节发生了变化。
## 2.13.1. 孤立原理与异常分数
每棵树都在数据的一个随机子采样上生长。构建过程反复重复一个简单的动作。它随机挑一个特征。它在该特征于当前节点内的最小值和最大值之间随机挑一个切分阈值。它把阈值以下的点送到左子节点，其余送到右子节点。
树一直递归，直到某个节点只剩 1 个点。它也会在该节点上所选特征的取值全部相等时停下，因为已经没什么可切了。它还会在触到深度上限时停下。一个远离数据主体的点，只需要少数几刀随机切分就能被孤立。一个落在稠密簇中央的点，则需要多得多的切分。
记录这一切的树结构保持极简。孤立树不需要类别计数或不纯度。它只需要知道自己在哪里切分、以及每个叶子收到了多少个点：
```rust,ignore
pub enum IsolationTree {
Leaf { size: usize },
Internal {
feature: usize,
threshold: f64,
left: Box<IsolationTree>,
right: Box<IsolationTree>,
},
}
```
一个样本的原始信号是它的**路径长度** `h(x)`。这是从根节点到该样本所落入的叶子之间经过的边数。树有一个深度上限，所以一个叶子仍可能留着若干树没能完全分开的点。路径长度会为那个本该在这个叶子之下继续下去的子树加上一个修正项。一个在深度 `d` 处、装着 `size` 个点的叶子，给路径长度贡献 `d + c(size)`。
`c(n)` 估计孤立 `n` 个点平均还需要多走的深度。`c(n)` 同时也是归一化常数。它等于在一棵含 `n` 个点的二叉搜索树中，一次失败查找的期望路径长度：
`c(n) = 2 * H(n-1) - 2 * (n-1) / n`，其中 `H(m)` 是第 m 个调和数。
当 `n <= 50` 时，RustyML 用精确方式（累加求和）算出 `H(m)`。超过这个规模，它就切到渐近式 `ln(m) + gamma + 1 / (2 * m)`。这里 `gamma` 是欧拉-马斯刻若尼常数，`m = n - 1`。这个近似把误差控制在 `1e-3` 以内。RustyML 钉死了 2 种边界情形：当 `n <= 1` 时 `c(n) = 0`，`c(2) = 1`。一个样本的最终分数，是把 `h(x)` 在每棵树上取平均，再套用 Liu 等人的公式并取负：
`s(x) = -2^(-E[h(x)] / c(n))`。
分数落在区间 `[-1, 0)` 内。分数*越低*就越异常。这与 RustyML 早先的取向正好相反。
一条*短*的平均路径容易被孤立，所以它是异常的。它把分数推向 **-1**。一条*长*的平均路径难以被孤立，所以它是正常的。它把分数推向 **0**。
取负号让分数落回“负数即被拒绝的那一类”这一常见惯例。它也让 `score_samples` 与 scikit-learn 版本的数值完全一致。
中性点是 `s = -0.5`。在这一点上，样本的期望路径长度恰好等于 `c(n)`，也就是说它的孤立代价正好等于树的平均水平。Liu 等人把这称为“没有明显异常”的区间。[`Contamination::Auto`](#2136-把分数变成标签contamination) 就用 `-0.5` 作为切分点。把 `-0.5` 当作*没有信号*，而不是*确认正常*。一个点只有把分数明显抬到 `-0.5` 以上，才配得上“正常”。
分母里的 `c(n)` 用的是 `n = sample_size`。这是每棵树实际用到的子采样规模，接下来两节会讲到。它不是 `max_samples`。当你的数据集比 `max_samples` 还小时，这个区别就很关键，因为用错了 `n` 去归一化会让每个分数都偏移。
RustyML 的测试套件直接检验这个闭式解。它用完全相同的点去拟合，并设 `max_samples >= n_rows`。每个分数都精确等于 `-0.5`，因为 `E[h(x)] = c(sample_size)` 把指数约掉了。
## 2.13.2. 构造森林
`IsolationForest` 有 2 个入口。`IsolationForest::default()` 给出标准配置。`IsolationForest::new(n_estimators, max_samples)` 设定这 2 个结构性参数。它会校验这两个参数，并返回 `Result<Self, Error>`。3 个 builder 方法进一步微调结果。每一个都消费并返回 `self`，所以你可以链式调用它们：
```rust,ignore
impl IsolationForest {
pub fn new(n_estimators: usize, max_samples: usize) -> Result<Self, Error>;
pub fn with_max_depth(self, max_depth: usize) -> Result<Self, Error>;
pub fn with_random_state(self, seed: u64) -> Self;
pub fn with_contamination(self, contamination: Contamination) -> Result<Self, Error>;
}
```
```rust
use rustyml::machine_learning::IsolationForest;
fn main() {
// 标准配置：100 棵树，每棵子采样 256 行，
// 深度自动 = ceil(log2(256)) = 8，不设种子。
let _a = IsolationForest::default();
// 显式配置，带一个种子和一个手动设定的深度上限，覆盖自动值。
let forest = IsolationForest::new(100, 256)
.unwrap()
.with_max_depth(10)
.unwrap()
.with_random_state(42);
assert_eq!(forest.get_n_estimators(), 100);
assert_eq!(forest.get_max_samples(), 256);
assert_eq!(forest.get_max_depth(), 10);
assert_eq!(forest.get_random_state(), Some(42));
}
```
`new` 会拒绝 `n_estimators == 0` 或 `max_samples == 0`。它返回 [`Error::InvalidParameter`](../Chapter-01/1.6._错误处理.md)，并点名出错的字段。`with_max_depth(0)` 同样会被拒绝。
注意这里的一处不对称。显式给出的深度 0 是非法的。*自动算出*的深度却可以是 0。举例来说，`max_samples == 1` 时 `ceil(log2(1)) = 0`。这没问题，因为只有 1 个点的子采样本来就没什么可切的。
| `n_estimators` | `new` / `default` | `100` | 大于 0 |
| `max_samples` | `new` / `default` | `256` | 大于 0 |
| `max_depth` | 自动或 `with_max_depth` | `ceil(log2(max_samples))` = `8` | 显式设定时须大于 0 |
| `random_state` | `with_random_state` | `None`（用熵播种） | 任意 `u64` |
| `contamination` | `with_contamination` | `Contamination::Auto` | 若为 `Fraction(c)`，须有限且落在 `(0.0, 0.5]` |
每个字段都有 getter。`get_n_estimators`、`get_max_samples`、`get_max_depth`、`get_random_state`（返回 `Option<u64>`）和 `get_contamination` 在构造之后就能用。另外 4 个 getter 只有在拟合之后才有意义：`get_n_features`、`get_sample_size`、`get_offset`（返回 `Option<f64>`，即解析出来的分数切分点）和 `get_trees`（返回 `Option<&Vec<IsolationTree>>`，拟合前为 `None`）。
在覆盖自动深度之前，先理解它。`ceil(log2(max_samples))` 估计的是这个子采样上一棵平衡树的高度。到这个高度，异常大致已经被孤立出来了。再往深切，大多只是在分开稠密正常簇内部的点。`c(size)` 这个叶子修正项已经把这部分算进去了。
更大的 `max_depth` 几乎换不来精度，反而多花构建时间。把 `max_depth` 留在自动挡，除非你有具体的理由要改它。
## 2.13.3. 子采样、`sample_size`，以及为什么是 256
孤立森林做了一个不寻常的设计选择。每棵树都在一个小的随机子采样上训练，而不是整个数据集。这是一个特性，不是偷工减料。RustyML 为每棵树抽 `sample_size = min(max_samples, n_rows)` 行，不放回，通过一次部分 Fisher-Yates 洗牌完成。
默认的 `max_samples = 256` 直接来自原始论文。小子采样能击败密度型检测器的 2 种失效模式。**淹没（swamping）** 指的是异常簇附近的正常点开始看起来也异常。**掩蔽（masking）** 指的是一团稠密的异常互相遮蔽了彼此。这两个问题都会随着每棵树看到更多数据而恶化，因为大样本会让异常自成小簇。这些小簇不再容易被孤立。
256 行的子采样，大到足以刻画正常区域的形状。它也小到能让异常保持稀疏、保持容易被孤立。更大的子采样多半只换来更高的构建开销和*更差*的检测质量。这正是为什么 `max_samples` 是一个子采样预算，而不是一个“多用点数据”的旋钮。
这个设计带来 2 个后果。其一，当你的数据集行数少于 `max_samples` 时，`sample_size` 会被夹到 `n_rows`。这样每棵树就都能看到整个数据集。森林依然照常工作，因为各棵树仍然靠随机切分产生差异。只是它不再子采样了。`fit` 会检查这种情况，绝不会 panic。
其二，归一化用的是 `c(sample_size)`，而不是 `c(max_samples)`。RustyML 从拟合后的模型里读回 `sample_size`，而不是想当然地用 `max_samples`。`get_sample_size()` 在 `fit` 之后报告实际值。
## 2.13.4. 拟合与读取分数
`fit` 接收一个二维 `f64` 数组，行是样本、列是特征。它返回 `Result<&mut Self, Error>`。`fit` 记录 `n_features` 和 `sample_size`，构建每一棵树，然后把 `contamination` 规则解析成一个存下来的分数切分点——`offset`。打分随后暴露出 4 个接口。它们串成一条链，每一个都是对前一个做平移或取阈值：
```rust,ignore
pub fn fit<S>(&mut self, x: &ArrayBase<S, Ix2>) -> Result<&mut Self, Error>
where S: Data<Elem = f64> + Send + Sync;
pub fn score_samples<S>(&self, x: &ArrayBase<S, Ix2>) -> Result<Array1<f64>, Error>
where S: Data<Elem = f64>; // 每行 1 个分数，落在 [-1, 0)。越低越异常
pub fn score_sample(&self, sample: &[f64]) -> Result<f64, Error>; // 单行，以切片形式
pub fn decision_function<S>(&self, x: &ArrayBase<S, Ix2>) -> Result<Array1<f64>, Error>
where S: Data<Elem = f64>; // score_samples(x) 减去 offset。负数表示异常
pub fn predict<S>(&self, x: &ArrayBase<S, Ix2>) -> Result<Array1<i32>, Error>
where S: Data<Elem = f64>; // decision_function 的符号：{-1 异常, +1 正常}
```
每个名字的含义都与 scikit-learn 里完全一致。`score_samples` 给出原始异常分数。`decision_function` 把这个分数平移，让零点成为判决边界。`predict` 给出判决值的符号。严格为负给出 `-1`。其余情况都给出 `+1`，所以一个恰好落在切分点上的样本算作正常。
按任务需要挑选方法。想排序样本、想自定切分点、想喂给下游校准器，就用 `score_samples`。想要一个带符号的间隔，就用 `decision_function`。想要一个硬性的 `{-1, +1}` 判决，就用 `predict`。
旧版 RustyML 在这里有 2 处不同。这两处变化都会悄悄改变结果，而不是让代码编译失败。
第一，分数现在被**取负**了。旧的量程是 `[0, 1]`，分数越高越异常。新的量程是 `[-1, 0)`，分数*越低*越异常。每一处给分数排序或卡阈值的比较，都要翻过来。
第二，逐样本的切片方法现在叫 **`score_sample`**（单数）。它取代了旧的 `anomaly_score` 方法。旧的批量形式——`predict` 返回分数——没有了。旧的 `predict_labels(&x, contamination)` 方法也没有了。`score_samples` 接替了前者。`predict` 连同已拟合的 `contamination` 规则，接替了后者。
`score_sample` 一次给一个点打分，适合实时流或临时查询。它接收一个 `&[f64]` 切片而不是矩阵。`fit_predict` 在同一个矩阵上先跑 `fit`、再跑 `predict`。它返回标签，是无监督模型“给训练集打标签”的标准便捷方法。
```rust
use ndarray::array;
use rustyml::machine_learning::IsolationForest;
fn main() {
let train = array![[0.0, 0.0], [0.1, 0.0], [0.0, 0.1], [0.1, 0.1], [30.0, 30.0]];
let mut forest = IsolationForest::new(80, 32).unwrap().with_random_state(1);
forest.fit(&train).unwrap();
// 通过切片 API 一次给一个点打分。
let normal = forest.score_sample(&[0.05, 0.05]).unwrap();
let weird = forest.score_sample(&[30.0, 30.0]).unwrap();
assert!(weird < normal); // 分数越低越异常
// 批量形式，以及同一批值按已拟合切分点平移后的结果。
let scores = forest.score_samples(&train).unwrap();
let decision = forest.decision_function(&train).unwrap();
let offset = forest.get_offset().unwrap(); // Contamination::Auto 下为 -0.5
assert!((decision[0] - (scores[0] - offset)).abs() < 1e-12);
}
```
每个入口都会校验输入，并返回一个带类型的 [`Error`](../Chapter-01/1.6._错误处理.md)。`fit` 在零行时返回 `Error::EmptyInput`。`fit` 在出现 `NaN` 或无穷值时返回 `Error::NonFinite`。`score_samples` 还会检查 `Error::DimensionMismatch`（特征数与训练时不符时）和 `Error::NotFitted`（`fit` 尚未运行时）。
`decision_function` 和 `predict` 原样向上传递这些相同的错误。`score_sample` 对它的单个切片只检查 `Error::NotFitted` 和 `Error::DimensionMismatch`。它不会检查这个切片里有没有 `NaN` 或无穷值。
批量调用接受任意 `ArrayBase` 后端。这包括非连续视图，比如一个转置数组。打分前你不必先把 `.t()` 拷进一块新缓冲区。
## 2.13.5. 一个完整示例：往数据团里注入离群点
这是异常检测器的标准正确性核验。搭一个紧凑的正常点簇。扔进几个明显不属于这里的点。确认森林把这些点排到最前面。
```rust
use ndarray::Array2;
use rustyml::machine_learning::{Contamination, IsolationForest};
fn main() {
// 20 个正常点，聚成 (5, 5) 附近的紧凑数据团……
let mut rows: Vec<f64> = Vec::new();
for i in 0..20 {
let t = i as f64;
rows.push(5.0 + 0.15 * t.sin());
rows.push(5.0 + 0.15 * t.cos());
}
// ……外加 3 个注入的离群点，远离该簇。
for &(x, y) in &[(30.0, 30.0), (-20.0, 40.0), (50.0, -10.0)] {
rows.push(x);
rows.push(y);
}
let n = rows.len() / 2; // 23 行
let data = Array2::from_shape_vec((n, 2), rows).unwrap();
// 15% 的污染率预算，会在拟合时被解析成一个固定的切分点。
let mut forest = IsolationForest::new(100, 256)
.unwrap()
.with_random_state(42)
.with_contamination(Contamination::Fraction(0.15))
.unwrap();
let labels = forest.fit_predict(&data).unwrap();
let scores = forest.score_samples(&data).unwrap();
// 这 3 个注入行（下标 20..23）的分数应当明显低于数据团。
for i in (n - 3)..n {
println!("outlier row {i}: score {:.3}", scores[i]);
}
let flagged: Vec<usize> = labels
.iter()
.enumerate()
.filter(|&(_, &l)| l == -1)
.map(|(i, _)| i)
.collect();
println!("cutoff (offset): {:.3}", forest.get_offset().unwrap());
println!("flagged as outliers (-1): {flagged:?}");
}
```
这 3 个离群点落在分数区间的下端。数据团各行则贴近零：
```text
outlier row 20: score -0.735
outlier row 21: score -0.779
outlier row 22: score -0.788
cutoff (offset): -0.419
flagged as outliers (-1): [2, 20, 21, 22]
```
注意这个切分点是什么、又不是什么。`Contamination::Fraction(0.15)` 把 offset 设成*训练*分数的第 15 百分位。它切掉的大致是最低的 15% 的样本。这里是 23 行里的 4 行，比实际注入的 3 行多 1 行。
确切的数目取决于分数实际落在哪里。它不取决于一个固定的 `ceil(0.15 * n)`，所以正常点也可能被扫进来。这正是 contamination 的*含义*，也引出了下一节。
## 2.13.6. 把分数变成标签：contamination
`contamination` 是你在 builder 上设定的一条规则。它不是传给某个预测调用的参数。`fit` 会把它解析成一个存下来的数字——`offset`：
```rust,ignore
pub enum Contamination {
Auto, // 论文里的切分点：offset = -0.5
Fraction(f64), // offset = 训练分数的第 100*c 百分位。c 落在 (0.0, 0.5]
}
```
`Contamination::Auto` 是默认值。它把切分点钉在 `-0.5`，即某个样本被孤立的速度恰好等于森林平均水平时的分数。`Contamination::Fraction(c)` 则从训练分数里读出切分点，取第 `100*c` 百分位。它对这个百分位采用 NumPy 的线性插值。这个做法让 `get_offset()` 在数值上等于 scikit-learn 的 `offset_`。它做的不只是标出数目相近的若干行。
`Fraction` 的值必须有限，并且落在 `(0.0, 0.5]` 之内。否则，`with_contamination` 返回 `Error::InvalidParameter`。上界 `0.5` 编码了“异常是少数”这一假设。
在拟合时解析切分点，正是这个设计的关键所在。这条规则会变成模型状态。无论你把一个样本单独打分、放在一小片里打分，还是放进整批里打分，它拿到的标签都一样。
早先的设计做法不同。它对手头拿到的这一批数据取分位数，因而是直推式的。单行调用总是返回 `-1`。把测试集一分为二就会改变它的标签。
拟合之后再改这条规则，需要重新调用一次 `fit`，因为 RustyML 是从训练分数里算出 offset 的。
contamination 仍然是一个*预算*，而不是一次发现。你告诉模型，训练数据里预计有多大比例是异常。切分点就照此摆放，不管真的有没有那么多异常点。如果你高估了，正常点就会被当成假阳性扫进来，正如上面的示例所示。如果你低估了，真正的异常就会被标成正常。模型无从得知真实比例，所以这个权衡无法回避。
当你手上有验证集的真实标签时，扫一遍这个比例。挑出在你的代价结构下，精确率与召回率权衡得最好的那个值。[5.2. 分类指标](../Chapter-05/5.2._分类指标.md) 里的工具在此适用，只要把 `-1` 当作正类。
当你没有真实标签时，优先使用原始的 `score_samples` 值。拿一个你说得清道理的水平去卡阈值，比如来自一段干净参考窗口的分位数，或者一个绝对分数切分点。不要只是一口咬定某个固定比例。如果你心里的“离群点”其实是“稀疏区域”，而不是“少而不同”，可以拿 [DBSCAN](./2.8._DBSCAN.md) 来对比，它把低密度点标为噪声。
## 2.13.7. 设种子与可复现的森林
未设种子的森林从熵里取随机性，所以 2 次拟合的结果不同。传入 `with_random_state(seed)`，可以让整片森林变得可复现。相同的种子加相同的数据，会给出逐位相同的分数。
```rust
use ndarray::array;
use rustyml::machine_learning::IsolationForest;
fn main() {
let data = array![[0.0, 0.0], [0.5, 0.5], [1.0, 1.0], [2.0, 2.0], [50.0, 50.0]];
let mut a = IsolationForest::new(30, 20).unwrap().with_random_state(13);
a.fit(&data).unwrap();
let sa = a.score_samples(&data).unwrap();
let mut b = IsolationForest::new(30, 20).unwrap().with_random_state(13);
b.fit(&data).unwrap();
let sb = b.score_samples(&data).unwrap();
assert_eq!(sa, sb); // 完全相同，与线程调度无关
}
```
这个确定性比看上去更强，其原因对下一节讲的并行构建很关键。RustyML 不在各棵树之间共享同一个 RNG。第 `i` 棵树拿到自己的生成器，种子是 `seed.wrapping_add(i)`。每棵树的种子只取决于它的下标。
所以无论这些树是串行构建，还是在 rayon 线程上以调度器任意选定的顺序构建，森林出来的结果都一样。并行永远不会改变结果。这与本 crate 里的神经网络组件形成了刻意的对照，后者的可复现性可能依赖于顺序。
你可以选择全局固定随机性，而不是给每个构造器都传一个种子。`rustyml::set_global_seed` 会用进程全局、线程本地的随机流，去给一个未设种子的森林播种：
```rust
use ndarray::array;
use rustyml::machine_learning::IsolationForest;
use rustyml::set_global_seed;
fn main() {
set_global_seed(2026);
let data = array![[0.0, 0.0], [0.5, 0.5], [1.0, 1.0], [50.0, 50.0]];
// 不调 with_random_state：各棵树的种子从全局流派生。
let mut forest = IsolationForest::new(30, 16).unwrap();
let _labels = forest.fit_predict(&data).unwrap();
}
```
显式的 `with_random_state` 总是压过全局种子。它也从不消耗全局流，所以两者混用的结果始终可预测。全局种子是线程本地的。要在构建模型的同一个线程上设置它。完整的种子解析规则见 [7.1. 可复现性与随机种子](../Chapter-07/7.1._可复现性与随机种子.md)。
## 2.13.8. 并行训练与预测
训练和打分都通过 rayon 并行。一道门限让微小的工作量保持串行，以此避开 fork/join 开销。一旦 `n_estimators` 达到 10 棵树这个阈值，`fit` 就会用 `into_par_iter` 并行构建树。默认的 100 棵树森林总是并行训练。每棵树都是一次独立的子采样加构建步骤，各自带着按下标播种的 RNG。这份工作干净地并行开来，没有共享的可变状态，也不影响结果。
一旦估算的遍历工作量越过校准好的树遍历门限，`score_samples` 就会按*行*并行。这个工作量估计是样本数乘以树数、再乘以平均路径长度。低于这道门限时，小批量就串行打分。`decision_function` 和 `predict` 都继承这个行为，因为它们只是 `score_samples` 的薄包装。`score_sample` 总是串行运行，因为它一次只处理 1 个样本。
孤立森林在宽森林和大批量打分上扩展性良好。训练成本大约是 `n_estimators * sample_size * log(sample_size)`，并且跨树是尴尬并行的。逐样本打分是 `O(n_estimators * tree_depth)`，并且跨行相互独立。如果要调整这些门限或研究成本模型，见 [7.3. 性能调优与并行](../Chapter-07/7.3._性能调优与并行.md)。
## 2.13.9. 保存与加载森林
拟合好的森林通过 `save_to_path` 和 `load_from_path`，序列化成紧凑的 postcard 二进制。每个 RustyML 估计器都提供这同一对方法。整个状态都会随之保存：每一棵树、超参数、`n_features`、`sample_size`，以及已拟合的 `offset`。重新加载的模型打出的分数*和标签*都与原模型逐字节一致。
```rust
use ndarray::array;
use rustyml::machine_learning::IsolationForest;
fn main() {
let data = array![[0.0, 0.0], [0.1, 0.1], [0.2, 0.0], [10.0, 10.0]];
let mut forest = IsolationForest::new(50, 32).unwrap().with_random_state(7);
forest.fit(&data).unwrap();
let before = forest.score_samples(&data).unwrap();
let path = "isolation_forest_model.bin";
forest.save_to_path(path).unwrap();
let loaded = IsolationForest::load_from_path(path).unwrap();
let after = loaded.score_samples(&data).unwrap();
assert_eq!(before, after); // 打分精确地经受住了往返
std::fs::remove_file(path).unwrap();
}
```
当文件缺失，或者字节不是一个合法的序列化森林时，`load_from_path` 返回 `Error::Io`。`sample_size` 被持久化了，所以加载的模型即使再也见不到训练数据，也能保住正确的 `c(n)` 归一化。它的分数与你保存之前处在同一尺度上。
有一处迁移提示需要注意。存下来的 `offset` 随分数一起换了符号。旧版本保存的森林，其切分点会落在零的另一侧。已持久化的森林，请重新拟合、重新保存。整个 crate 的版本管理与格式细节，见 [7.2. 深入模型持久化](../Chapter-07/7.2._深入模型持久化.md)。