孤立森林，一种非常高效快速的异常检测算法
开始探索
scikit-learn
import numpy as np
import matplotlib.pyplot as plt
from sklearn.ensemble import IsolationForest
rng = np.random.RandomState(0)
X_train = 0.3 * rng.randn(100, 2)
X_outliers = rng.uniform(low=-2, high=2, size=(10, 2))
clf = IsolationForest(n_estimators=100, max_samples='auto', contamination='auto', random_state=rng)
clf.fit(X_train)
y_pred_train = clf.predict(X_train)
y_pred_outliers = clf.predict(X_outliers)
plt.title("Isolation Forest")
plt.scatter(X_train[:, 0], X_train[:, 1], color='b', label="Normal")
plt.scatter(X_outliers[:, 0], X_outliers[:, 1], color='r', label="Outliers")
plt.legend()
plt.axis('tight')
plt.show()
脚本！启动：
watermarked-isolation_forest_1_4
深入理解
类似于随机森林，但每棵树不使用信息增益或基尼系数等指标，而是随机选择一个特征，在该特征的最小值和最大值之间随机选一个切分值，将数据集分成两部分，又在每个部分随机最大值与最小值之间随机选一个切分支，不断递归。指导到达指定深度或者当前节点只有1个样本
构造如此的树n棵，组成森林，开始计算每个样本在每棵树的平均路径长度（叶子节点的深度depth），计算异常分数
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
c
(
n
)
=
2
H
(
n
−
1
)
−
2
(
n
−
1
)
n
H
(
n
)
=
∑
n
i
=
1
1
i
s
(
x
,
n
)
=
2
−
E
(
x
)
c
(
n
)
s
≈
1
，强异常点，很容易被孤立
0.5
≤
s
<
1
，可能是异常点，越接近1越是异常点，需要配合其他参数来确定，比如异常点比例
s
<
0.5
，正常点
举例说明
假设有以下样本： [1, 1.5, 1.8, 2.0, 2.3, 10]
构造第一棵树：
1）第一层：depth=1，随机选择划分值：1 < split < 10 的区间中选择 split = 5
左子树：[1, 1.5, 1.8, 2.0, 2.3]
右子树：[10.0]
2）第二层：depth=2，随机选择划分值：1 < split < 2.3 的区间中选择 split = 1.6
左子树：[1, 1.5]
右子树：[1.8, 2.0, 2.3]
3）第三层：depth=3，左子树，随机选择划分值：1 < split < 1.5 的区间中选择 split = 1.2
左子树：[1]
右子树：[1.5]
4）第三层：depth=3，右子树，随机选择划分值：1.8 < split < 2.3 的区间中选择 split = 2.1
左子树：[1.8, 2.0]
右子树：[2.3]
5）第四层：depth=4，随机选择划分值：1.8 < split < 2.9 的区间中选择 split = 1.9
左子树：[1.8]
右子树：[2.9]
6）计算路径
watermarked-isolation_forest_1_1
样本值 路径长度
1.0 3
1.5 3
1.8 4
2.0 4
2.3 3
10.0 1
重复构造第n棵树，得出路径，计算路径平均值
样本值 第1棵树路径 第2棵树路径 第n棵树路径 平均路径
1.0 3 3 .. 3
1.5 3 3 .. 3
1.8 4 4 .. 4
2.0 4 4 .. 4
2.3 3 3 .. 3
10.0 1 1 .. 1
计算异常得分
s
(
x
,
n
)
=
2
−
E
(
x
)
c
(
n
)
1）计算样本（1.0）：
样本长度：
E
(
x
)
=
3
样本规模
n
=
6
的平均路径期望：
{
c
(
n
)
=
2
H
(
n
−
1
)
−
2
(
n
−
1
)
n
H
(
n
)
=
∑
n
i
=
1
1
i
c
(
6
)
=
2
H
(
n
−
1
)
−
2
(
n
−
1
)
n
=
2
⋅
(
1
+
1
2
+
1
3
+
1
4
+
1
5
)
−
2
(
6
−
1
)
6
≈
2.8999
s
(
1.0
)
=
2
−
E
(
x
)
c
(
n
)
=
2
−
3
2.8999
≈
0.4882
2）计算所有样本
样本值 平均长度 异常得分
1.0 3 0.4882
1.5 3 0.4882
1.8 4 0.3844
2.0 4 0.3844
2.3 3 0.4882
10.0 1 0.7874
判断异常点：
路径长度越短的越异常，比如10.0的路径长度为1，在第一次分割的时候就被孤立了
异常分数越高就是异常点
sklearn中的异常分数
from sklearn.ensemble import IsolationForest
import numpy as np
X = np.array([[1], [1.5], [1.8], [2], [2.3], [10]])
clf = IsolationForest(random_state=0, contamination='auto')
clf.fit(X)
pred = clf.predict(X)
score = clf.decision_function(X)
for x, p, s in zip(X, pred, score):
print(f"样本 {x[0]:>4} -> {'异常' if p==-1 else '正常'} | 异常分数（decision_function）: {s:.4f}")
脚本！启动：
watermarked-isolation_forest_1_2
问题出现了：
sklearn的分数和手工计算的并不一样
为什么1.0被当成异常了
分数越小反而越异常
先看第一个问题，sklearn的分数和手工计算的并不一样。首先，每棵树是采用部分的样本来计算，而不是采用所有的样本n=6来计算的。其次，在上面的手工计算中，期望路径长度
c
(
n
)
中的
H
(
n
)
，并不是由这个公式计算的
{
c
(
n
)
=
2
H
(
n
−
1
)
−
2
(
n
−
1
)
n
H
(
n
)
=
∑
n
i
=
1
1
i
这个公式一旦n的数量增大，
H
(
n
)
的计算将会带来很大的计算消耗，通常使用另外一个公式计算近似值：
H
(
n
)
≈
l
n
(
n
)
+
γ
，
其
中
γ
≈
0.5772
（
欧
拉
常
数
）
以上两点原因，带来的就是sklearn计算异常分数与手工计算不一样
再看第二个问题，为什么1.0被当成异常了
只需要调整一个参数，contamination=0.1就可以解决这个问题了
watermarked-isolation_forest_1_3
contamination用来调节异常比例的参数，如果是auto，那么异常比例为33.3%，6个样本，那么异常点就是2个。手动调整为0.1，那就告诉模型只有1个异常点，那么最不正常的就是10.0了
最后第三个问题，分数越小反而越异常。这明显是计算方式不一样造成的，这里直接解析一下源码，版本：scikit-learn:1.6.1：
decision_function函数
def decision_function(self, X):
return self.score_samples(X) - self.offset_
score_samples函数返回的是：经过公式
s
(
x
,
n
)
=
2
−
E
(
x
)
c
(
n
)
计算的相反数
def score_samples(self, X):
...
return self._score_samples(X)
def _score_samples(self, X):
return -self._compute_chunked_score_samples(X)
def _compute_chunked_score_samples(self, X):
...
for sl in slices:
# compute score on the slices of test samples:
scores[sl] = self._compute_score_samples(X[sl], subsample_features)
return scores
def _compute_score_samples(self, X, subsample_features):
...
scores = 2 ** (
# For a single training sample, denominator and depth are 0.
# Therefore, we set the score manually to 1.
-np.divide(
depths, denominator, out=np.ones_like(depths), where=denominator != 0
)
)
return scores
self.offset_是根据整个样本异常分数，再加上异常比例参数contamination的中位数计算出来的
self.offset_ = np.percentile(self._score_samples(X), 100.0 * self.contamination)
看到这里，我就想说，复杂就行了，经过这么复杂的计算，与手动计算出来的肯定不一样
小结
在sklearn中
找到孤立点，contamination是一个非常重要的参数，它决定了每个节点的分数以及后续确定是否异常
快速找到孤立点，直接通过pred函数即可，-1是孤立点，1是正常点
想要获取点的评分，通过decision_function函数获取评分，与理论公式不同，评分越低反而越异常
