The quiter you become,the more you are able to hear!

iForest异常检测算法

Posted on Edited on

Author: geneblue

Blog: https://geneblue.github.io/

iforest-00

anomaly detection

我们先看一个问题，上图中你能找出哪些是异常的点？为什么认为这些是异常点呢？你有多少种方法能找出异常点？

什么叫异常？异常在这里指的是分布稀疏且距离高密度样本点较远的点，也叫离群点，这种检测叫离群点检测（outliner detection）

异常检测是数据挖掘中一类问题，在众多数据处理场景使用到，比如在业务风控领域：异常账户，异常设备，异常流量的检测；在数据清洗中，可以用来过滤噪声数据；在金融交易中，可以检测信用卡欺诈。

iForest简介

iForest(Isolation Forest) 孤立森林算法是由莫纳什大学的刘飞博士在周志华和陈开明教授的指导下完成的。第一版是在 2008 年 IEEE ICDM 国际数据挖掘大会发表，第二版改进版是在 2012 年的 TKDD 上发表，文后均附有两篇论文的下载链接。

iForest 是无监督算法，主要用于在连续结构化数据集中快速检测出异常数据。这里将异常定义为 "容易被孤立的离群点(more likely to be separated)"，即分布稀疏且距离高密度样本点较远的点。

iForest 原理

Isolation Forest 两个单词意味孤立和森林。

isolation

iforest-08

我们先以切蛋糕来粗略的理解算法思想。

孤立是指从剩余样本中分割出一个样本(separating an instance from the rest of the instances)，从而将异常点尽快的 "孤立" 出来；森林是指当样本集随机分割时会构建一棵树，为了消除掉维度选择的随机性，我们需要构建 T 棵树，最后统一计算结果并对样本打分，这 T 棵树便组成了森林。

基本思想： iForest 使用二叉树结构对样本做孤立(将样本挂载到叶子节点上)，因为异常样本大概率先被孤立出来，所以异常样本在树中的节点位置距离 root 节点更近，正常样本被孤立在树的更深层节点中。这里的树被成为 Isolation Tree，也叫 iTree。构建 T 棵 iTrees 后，异常点距离 root 节点的平均长度要比正常点距离 root 节点的平均长度更短。

isolation

比如上图，观察发现 \(x_0\) 需要 4 次分割就可以孤立出来，显然要想将 \(x_i\) 分割孤立开来需要更多的分割次数。

单棵 iTree 的训练步骤： - step1: 从样本集中随机选择 n 个样本作为子样本 X = {x_1, ..., x_n}，将其放入到 iTree 的根节点 - step2: 随机选择一个维度 q，并随机选择一个切割点 p，\(min(x_{ij}, j= q, x_{ij}\in X) < p < max(x_{ij}, j= q, x_{ij}\in X)\)，即 p 值选定在当前节点数据中 q 维的最大和最小值之间 - step3: 切割点 p 即可认为是一个超平面，将当前节点数据空间切分成2个子空间，将当前节点样本集中 \(< p\) 点的放在当前节点的左分支，\(\ge p\) 点的放在当前节点的右分支 - step4: 在左右分支节点递归步骤2，3，直到叶子节点只剩一个样本数据，或者 iTree 生长到设定高度

伪码表示为：

iTree

这里插一个例子，不从人类的视觉，只从提供的数据来看，哪个动物最特别呢？

iforest-09

我们整理上面的动物的特征数据如下：

ifroest-10

按照 itree 的构建步骤得到二叉树如下：

iforest-11

按照 itree 的构建步骤，这棵树的结果与我们第一直觉不相符。

forest

俗话说：三个臭皮匠赛过诸葛亮。

iforest-12

iTree 的训练过程是完全随机的，随机选择一个维度 q，随机选择选定维度范围内的分割值 p，这种随机性让单棵 iTree 的结果也是随机的，即单棵 iTree 中异常点不一定距离 iTree root 节点的长度更短。所以需要使用 ensemble 的方法使结果收敛，即从头开始切割，构建 T 棵 iTrees。

tree number

实验发现，在构建 100+ iTrees 后，\(x_0\), \(x_i\) 的平均路径长度将收敛。

构建 T 棵 iTrees 后，然后就可以计算样本点 \(x_i\) 的平均路径长度 \(E(h(x))\)，伪码表示为：

Length

接下来就可以计算平均异常分数 \(s\)，\(s\) 的计算结果是平均高度的归一化处理(通过某种计算公式映射到0~1区间)。

\(s(x, n) = 2^{-\frac{E(h(x))}{c(n)}}\)

\(c(n) = \begin{cases} 2H(n-1)-2(n-1)/n & n > 2 \\ 1 & n = 2 \\ 0 & otherwise \end{cases}\)

\(h(x)\) 是 \(x\) 在每棵 iTree 上的高度(长度)，\(E(h(x))\) 是 \(x\) 在 T 棵 iTree 上平均高度(长度)，\(c(n)\) 为给定样本 \(n\) 时路径长度的平均值。\(s\), \(h(x)\), \(c(n)\) 三者将其绘图如下：

E(h(x))

可以看出，:

  • \(E(h(x)) \to c(n), s \to 0.5\);

  • \(E(h(x)) \to 0, s \to 1\);

  • \(E(h(x)) \to n-1, s \to 0\);

  • \(s\) 接近 1 时，表明样本点均是异常点；

  • 如果 \(s\) 比 0.5 小很多，这些样本是正常样本；

  • 如果所有样本 \(s\) 值与 0.5 近似，说明在样本集中不不存异常点。

思考几个问题

  • 训练集中不包含 anomaly 样本是否影响检测
  • Anomaly 样本的特征值与正常样本差异不大可以吗
  • Anomaly 样本在数据集中占据大比例可以吗
  • 超高纬数据，iForest 是否可以处理

iForest 优点和其局限性

Swamping 与 Masking 问题

large samples

large samples

  • Swamping：错误的将正常样本归类为异常样本。当正常样本与异常样本相近时，那么从样本中区分处异常样本的难度将增加。
  • Masking: 指样本集中存在太多的异常样本。

以上两种特性都可能是因为训练样本集过大的原因，上图 a 中使用 4096 个样本训练，模型 AUC(Area Under Curve) 指标是 0.67；b 使用 128 个样本训练，模型 AUC 指标是 0.91，采用小样本训练能更好的缓解 Swamping 和 Masking 影响。

作者在实验中发现训练样本的大小达到 \(2^8\) 即 256 个样本之后，再增加训练样本并不会对改善检测性能；同样的，tree 数量也并不是越多越好，在 100 棵 iTree 左右，性能则稳定下来。

优缺点

优点： - iForest 是无监督算法，不需要提前标记训练集的输出标签 - iForest 具有线性时间复杂度，不需要计算距离，密度指标，可以用在海量数据集上面。构建的树的数量越多，算法越稳定，当然一定的树数量后，计算结果就收敛了。 - 由于每棵树都是独立生成，可以部署在分布式系统上来加速运算。

缺点： - iForest 不适用于高维数据。每次切数据空间都是随机选择维度，如果维度较多，在树构建完后，可能有的维度还没有被随机选择过，这就会影响算法结果。而且当维度较多时，并不是每个维度都会人工检验过对检测具有正向作用。 - iForest 只适用于处理全局稀疏点。

使用 sklearn 实现 iForest 算法

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
from sklearn.ensemble import IsolationForest
import numpy as np
import matplotlib.pyplot as plt
import pickle

if __name__ == '__main__':
    # 生成训练集
    seed = 42
    rng = np.random.RandomState(seed)

    X = 0.3 * rng.randn(100, 2)
    X_train = np.r_[X + 2, X - 2]

    X = 0.3 * rng.randn(20, 2)
    X_test = np.r_[X + 2, X - 2]

    X_outliers = rng.uniform(low=-4, high=4, size=(20, 2))

    # 使用 iforest 拟合
    clf = IsolationForest(max_samples=100, random_state=rng, contamination='auto')
    clf.fit(X_train)

    # 模型文件保存
    s = pickle.dumps(clf)
    model_file = open("./iforest-model", "wb+")
    model_file.write(s)
    model_file.close()

    # 使用模型文件预测
    model_file_2 = open("./iforest-model", "rb+")
    s2 = model_file_2.read()
    model_file_2.close()

    clf2 = pickle.loads(s2)
    y_pred_train = clf2.predict(X_train)
    y_pred_test = clf2.predict(X_test)
    y_pred_outliers = clf2.predict(X_outliers)

    print(y_pred_test)
    print(y_pred_outliers)

    # 绘图
    # print(np.linspace(-5, 5, 50))
    xx, yy = np.meshgrid(np.linspace(-5, 5, 50), np.linspace(-5, 5, 50))
    # print(xx.ravel())

    Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)

    plt.title("IsolationForest")
    plt.contourf(xx, yy, Z, camp=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-13

  • n_estimators：itree 的数量，默认 100
  • max_samples： 最大样本数，建议 < 512
  • contamination：数据集中异常数据的数量或比例
  • n_jobs：fit 和 predict 时的并行线程控制
  • random_state：随机数配置，可以配置常数，也可以配置伪随机数实例

参考