参考论文来源：Isolation-Based Anomaly Detection

背景

“An outlier is an observation which deviates so much from other observations as to arouse suspicions that it was generated by a different mechanism.”

— D. M. Hawkins, Identification of Outliers, Chapman and Hall, 1980.

异常检测 (anomaly detection)，或者又被称为“离群点检测” (outlier detection)，是机器学习研究领域中跟现实紧密联系、有广泛应用需求的一类问题。但是，什么是异常，并没有标准答案，通常因具体应用场景而异。如果要给一个比较通用的定义，很多文献通常会引用 Hawkins 在文章开头那段话。很多后来者的说法，跟这个定义大同小异。这些定义虽然笼统，但其实暗含了认定“异常”的两个标准或者说假设：

  1. 异常数据跟样本中大多数数据不太一样。
  2. 异常数据在整体数据样本中占比比较小。

为了刻画异常数据的“不一样”，最直接的做法是利用各种统计的、距离的、密度的量化指标去描述数据样本跟其他样本的疏离程度。而 Isolation Forest 的想法要巧妙一些，它尝试直接去刻画数据的“疏离”(isolation) 程度，而不借助其他量化指标。Isolation Forest 因为简单、高效，在学术界和工业界都有着不错的名声。

算法

我们先用一个简单的例子来说明 Isolation Forest 的基本想法。假设现在有一组一维数据（如下图所示），我们要对这组数据进行随机切分，希望可以把点 A 和点 B 单独切分出来。具体的，我们先在最大值和最小值之间随机选择一个值xx，然后按照<x<x 和>=x>=x 可以把数据分成左右两组。然后，在这两组数据中分别重复这个步骤，直到数据不可再分。显然，点 B 跟其他数据比较疏离，可能用很少的次数就可以把它切分出来；点 A 跟其他数据点聚在一起，可能需要更多的次数才能把它切分出来。

我们把数据从一维扩展到两维。同样的，我们沿着两个坐标轴进行随机切分，尝试把下图中的点 A’ 和点 B’ 分别切分出来。我们先随机选择一个特征维度，在这个特征的最大值和最小值之间随机选择一个值，按照跟特征值的大小关系将数据进行左右切分。然后，在左右两组数据中，我们重复上述步骤，再随机的按某个特征维度的取值把数据进行细分，直到无法细分，即：只剩下一个数据点，或者剩下的数据全部相同。跟先前的例子类似，直观上，点 B’ 跟其他数据点比较疏离，可能只需要很少的几次操作就可以将它细分出来；点 A’ 需要的切分次数可能会更多一些。

按照先前提到的关于“异常”的两个假设，一般情况下，在上面的例子中，点 B 和点 B’ 由于跟其他数据隔的比较远，会被认为是异常数据，而点 A 和点 A’ 会被认为是正常数据。直观上，异常数据由于跟其他数据点较为疏离，可能需要较少几次切分就可以将它们单独划分出来，而正常数据恰恰相反。这其实正是 Isolation Forest（IF）的核心概念。IF 采用二叉树去对数据进行切分，数据点在二叉树中所处的深度反应了该条数据的“疏离”程度。整个算法大致可以分为两步：

  • 训练：抽取多个样本，构建多棵二叉树（Isolation Tree，即 iTree）；
  • 预测：综合多棵二叉树的结果，计算每个数据点的异常分值。

训练：构建一棵 iTree 时，先从全量数据中抽取一批样本，然后随机选择一个特征作为起始节点，并在该特征的最大值和最小值之间随机选择一个值，将样本中小于该取值的数据划到左分支，大于等于该取值的划到右分支。然后，在左右两个分支数据中，重复上述步骤，直到满足如下条件：

  • 数据不可再分，即：只包含一条数据，或者全部数据相同。
  • 二叉树达到限定的最大深度。

预测：计算数据xx 的异常分值时，先要估算它在每棵 iTree 中的路径长度（也可以叫深度）。具体的，先沿着一棵 iTree，从根节点开始按不同特征的取值从上往下，直到到达某叶子节点。假设 iTree 的训练样本中同样落在xx 所在叶子节点的样本数为T.sizeT.size，则数据xx 在这棵 iTree 上的路径长度h(x)h(x)，可以用下面这个公式计算：

h(x)=e+C(T.size)h(x)=e+C(T.size)

公式中，ee 表示数据xx 从 iTree 的根节点到叶节点过程中经过的边的数目，C(T.size)C(T.size) 可以认为是一个修正值，它表示在一棵用 T.size 条样本数据构建的二叉树的平均路径长度。一般的，C(n)C(n) 的计算公式如下：

C(n)=2H(n−1)−2(n−1)nC(n)=2 H(n-1)-\frac{2(n-1)}{n}

其中，H(n−1)H(n-1) 可用ln(n−1)+0.5772156649ln(n-1)+0.5772156649 估算，这里的常数是欧拉常数。数据xx 最终的异常分值Score(x)Score(x) 综合了多棵 iTree 的结果：

Score⁡(x)=2−E(h(x))C(ψ)\operatorname{Score}(x)=2^{-\frac{E(h(x))}{C(\psi)}}

公式中，E(h(x))E(h(x)) 表示数据xx 在多棵 iTree 的路径长度的均值，ψ\psi 表示单棵 iTree 的训练样本的样本数，C(ψ)C(\psi) 表示用ψ\psi 条数据构建的二叉树的平均路径长度，它在这里主要用来做归一化。

从异常分值的公式看，如果数据xx 在多棵 iTree 中的平均路径长度越短，得分越接近 1，表明数据xx 越异常；如果数据xx 在多棵 iTree 中的平均路径长度越长，得分越接近 0，表示数据xx 越正常；如果数据xx 在多棵 iTree 中的平均路径长度接近整体均值，则打分会在 0.5 附近。

构建参数的说明
有两个参数控制着模型的复杂度：

  • 每棵树的样本子集大小，它控制着训练数据的大小，论文中的实验发现，当该值增加到一定程度后，IForest 的辨识能力会变得可靠，但没有必要继续增加下去，因为这并不会带来准确率的提升，反而会影响计算时间和内存容量，论文实现发现该参数取 256 对于很多数据集已经足够；
  • 集成的树的数量，也可以理解为对原始数据的采样的次数，它控制着模型的集成度，论文中描述取值 100 就可以了；

缺点

  • 需要计算所有的节点；
  • 每个叶子节点只包含一个数值点；
  • 每个节点都会将其点的边界框分成两半；

算法应用

Isolation Forest 算法主要有两个参数：一个是二叉树的个数；另一个是训练单棵 iTree 时候抽取样本的数目。实验表明，当设定为 100 棵树，抽样样本数为 256 条时候，IF 在大多数情况下就已经可以取得不错的效果。这也体现了算法的简单、高效。

Isolation Forest 是无监督的异常检测算法，在实际应用时，并不需要黑白标签。需要注意的是：（1）如果训练样本中异常样本的比例比较高，违背了先前提到的异常检测的基本假设，可能最终的效果会受影响；（2）异常检测跟具体的应用场景紧密相关，算法检测出的“异常”不一定是我们实际想要的。比如，在识别虚假交易时，异常的交易未必就是虚假的交易。所以，在特征选择时，可能需要过滤不太相关的特征，以免识别出一些不太相关的“异常”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import numpy as np
import matplotlib.pyplot as plt
from sklearn.ensemble import IsolationForest

rng = np.random.RandomState(42)

# Generate train data
X = 0.3 * rng.randn(100, 2)
X_train = np.r_[X + 2, X - 2]
# Generate some regular novel observations
X = 0.3 * rng.randn(20, 2)
X_test = np.r_[X + 2, X - 2]
# Generate some abnormal novel observations
X_outliers = rng.uniform(low=-4, high=4, size=(20, 2))

# fit the model
clf = IsolationForest(max_samples=100, random_state=rng)
clf.fit(X_train)
y_pred_train = clf.predict(X_train)
y_pred_test = clf.predict(X_test)
y_pred_outliers = clf.predict(X_outliers)

# plot the line, the samples, and the nearest vectors to the plane
xx, yy = np.meshgrid(np.linspace(-5, 5, 50), np.linspace(-5, 5, 50))
Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

plt.title("IsolationForest")
plt.contourf(xx, yy, Z, cmap=plt.cm.Blues_r)

b1 = plt.scatter(X_train[:, 0], X_train[:, 1], c='white',
                 s=20, edgecolor='k')
b2 = plt.scatter(X_test[:, 0], X_test[:, 1], c='green',
                 s=20, edgecolor='k')
c = plt.scatter(X_outliers[:, 0], X_outliers[:, 1], c='red',
                s=20, edgecolor='k')
plt.axis('tight')
plt.xlim((-5, 5))
plt.ylim((-5, 5))
plt.legend([b1, b2, c],
           ["training observations",
            "new regular observations", "new abnormal observations"],
           loc="upper left")
plt.show()
iForest 测试效果

参考