《异常检测——从经典算法到深度学习》1 基于隔离森林的异常检测算法

红太狼 2023-02-10 15:27 148阅读 0赞

# 《异常检测——从经典算法到深度学习》 #

*  [0 概论][0]
 *  [1 基于隔离森林的异常检测算法 ][1 _]
 *  [2 基于LOF的异常检测算法][2 _LOF]
 *  [3 基于One-Class SVM的异常检测算法][3 _One-Class SVM]
 *  [4 基于高斯概率密度异常检测算法][4]
 *  [5 Opprentice——异常检测经典算法最终篇][5 Opprentice]
 *  [6 基于重构概率的 VAE 异常检测][6 _ VAE]
 *  [7 基于条件VAE异常检测][7 _VAE]
 *  [8 Donut: 基于 VAE 的 Web 应用周期性 KPI 无监督异常检测][8 Donut_ _ VAE _ Web _ KPI]
 *  [9 异常检测资料汇总（持续更新&抛砖引玉）][9]
 *  [10 Bagel: 基于条件 VAE 的鲁棒无监督KPI异常检测][10 Bagel_ _ VAE _KPI]
 *  [11 ADS: 针对大量出现的KPI流快速部署异常检测模型][11 ADS_ _KPI]
 *  [12 Buzz: 对复杂 KPI 基于VAE对抗训练的非监督异常检测][12 Buzz_ _ KPI _VAE]
 *  [13 MAD: 基于GANs的时间序列数据多元异常检测][13 MAD_ _GANs]

相关：

*  [ VAE 模型基本原理简单介绍 ][VAE _]
 *  [ GAN 数学原理简单介绍以及代码实践 ][GAN _]

# 1. 基于隔离森林的异常检测算法 #

此篇主要介绍以下内容：

*  隔离森林算法概述
 *  隔离森林算法应用实例
 *  小结

## 1.1 隔离森林算法概述 ##

**隔离森林(Isolation Forest)** 又名孤立森林，是一种从异常点出发，通过指定规则进行划分，根据划分次数进行判断的异常检测方法。由周志华教授等人提出，对原论文感兴趣的不妨下载看看。[下载地址][Link 1]

**核心思路**：循环分割（隔离），越容易被分割的判定为异常可能性越大。因为异常具有“少而不同”这一特点，所以异常数据比正常数据更容易被隔离。利用隔离森林，完成分割后，在最终形成的树中，异常将更加接近于根的位置。

**隔离树：** 设T为隔离树的一个节点，T是没有子节点的外节点，或者一个具有测试条件的内节点，它有两个子节点（ T l ， T r T\_l，T\_r Tl，Tr）。测试条件由属性q和分割值p组成，根据测试条件q<p将数据点划分到  T l T\_l Tl或者  T r T\_r Tr。

**隔离树主要过程：**

iTree(X, e, L)
    Inputs: X->输入数据，e->当前生成树的高度，L->生成树的最大高度
    Output: 生成树(即隔离树iTree）
    (1) if e >= L or |X| <= 1 then 
    		达到终止条件
    (2)		return exNode{ Size->|X|} 
    (3)	else 
    (4)		令Q为X中的一组属性
    (5)		随机选择一个Q中的一个属性q
    (6)		对于属性q，随机在[min,max]中选一个划分点p
    (7)		Xl <- fiter(X,q<p)
    (8)		Xr <- fiter(X,q>=p)
    (9)		return inNode{  把节点添加到树
    			Left<-iTree(Xl,e+1,L),
    			Right<-iTree(Xr,e+1,L),
    			SplitAtt<-q,
    			SplitValue<-p
    		}
    (10) end if

**隔离森林主要过程：**

iForest(X, t, w)
    Inputs: X->输入数据，t->树的个数,w->子采样大小
    Output: t颗 iTree
    (1) 初始化 iTree
    (2) 设置高度限制 L = ceiling(log2(w))
    (3) for i in (t):
    (4)		X0 <- sample(X,w)
    (5)		Forest <- Forest U iTree(X0,0,L)
    (6)	end for
    (7)	return Forest

**隔离森林算法特点：**

*  隔离森林算法是一种集成学习算法
 *  隔离森林算法将异常识别为具有短路径的节点
 *  隔离森林算法具有多个作为“专家”的树，以针对不同的异常
 *  隔离森林算法不是基于模型(model-based)的算法
 *  线性事件复杂度，低内存
 *  隔离森林算法是一种非监督学习算法

## 1.2 隔离森林算法应用实例 ##

隔离森林(IsolationForest)在sklearn中已有实现，接下来的内容均来自于sklearn官网。详细地址为：[https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.IsolationForest.html?highlight=isolationforest\#sklearn.ensemble.IsolationForest][https_scikit-learn.org_stable_modules_generated_sklearn.ensemble.IsolationForest.html_highlight_isolationforest_sklearn.ensemble.IsolationForest]

**官网例子1**

from sklearn.ensemble import IsolationForest
    X = [[-1.1], [0.3], [0.5], [100]]
    clf = IsolationForest(random_state=0).fit(X)
    clf.predict([[0.1], [0], [90]])

输出内容：array([ 1,  1, -1])

简单理解就是训练集中存在一个离群点 `100`，对于测试集中的 `90`，很明显会最先被隔离，所以算法认为 `90` 是异常点。

补充：如果测试数 `10` ，则会输出 1 ，因为算法认为 10 不算离群点。

**官网例子2**

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()

输出结果如图所示：  
![Sklearn 官网例子2][Sklearn _2]  
这样更加直观，离群点可以看得非常明显。例子2和例子1区别不大，只是为了可视化，更加直观，添加了很多绘图代码。

## 1.3 小结 ##

隔离森林算法是基于两个重要假设下提出的：1. 异常是少量的；2.异常数据与正确数据有明显的区别，或者说异常数据与正常数据相比，具有非常不同的属性值。

另外算法运行时随机采样的数目非常重要，举个极端的例子，一次采样中采样10个数据，很不巧有9个是异常数据，那么，正常数据将会被认为是异常数据。对于这种情况可以考虑多次随机采样(即设置sklearn函数中的 `n_estimators` 参数) 与设置异常数所占的比例(即 `contamination` 参数)，并设置为有放回的取样，若对于不同取样样本中同一个数据，多次都被认为是异常，那么就认为它是异常。若预先设定好的比例，超出比例的部分将不会被认为是异常。

> 参考文档  
> Isolation Forest 论文 [下载地址][Link 2]  
> [sklearn 官网][https_scikit-learn.org_stable_modules_generated_sklearn.ensemble.IsolationForest.html_highlight_isolationforest_sklearn.ensemble.IsolationForest]  
> [https://www.cnblogs.com/fengfenggirl/p/iForest.html][https_www.cnblogs.com_fengfenggirl_p_iForest.html]

> Smileyan  
> 2020年5月21日

感谢您的 点赞、 收藏、评论 与 关注 .

[0]: https://blog.csdn.net/smileyan9/article/details/106239187
[1 _]: https://blog.csdn.net/smileyan9/article/details/106249594
[2 _LOF]: https://blog.csdn.net/smileyan9/article/details/106296832
[3 _One-Class SVM]: https://blog.csdn.net/smileyan9/article/details/106351651
[4]: https://smileyan.blog.csdn.net/article/details/106398233
[5 Opprentice]: https://blog.csdn.net/smileyan9/article/details/106587227
[6 _ VAE]: https://blog.csdn.net/smileyan9/article/details/109255466
[7 _VAE]: https://blog.csdn.net/smileyan9/article/details/109508502
[8 Donut_ _ VAE _ Web _ KPI]: https://blog.csdn.net/smileyan9/article/details/112307506
[9]: https://smileyan.blog.csdn.net/article/details/113728611
[10 Bagel_ _ VAE _KPI]: https://smileyan.blog.csdn.net/article/details/113463339
[11 ADS_ _KPI]: https://smileyan.blog.csdn.net/article/details/114763060
[12 Buzz_ _ KPI _VAE]: https://smileyan.blog.csdn.net/article/details/116106826
[13 MAD_ _GANs]: https://smileyan.blog.csdn.net/article/details/118312582
[VAE _]: https://smileyan.blog.csdn.net/article/details/107362252
[GAN _]: https://smileyan.blog.csdn.net/article/details/115307274
[Link 1]: https://www.lanzoui.com/icum7xe
[https_scikit-learn.org_stable_modules_generated_sklearn.ensemble.IsolationForest.html_highlight_isolationforest_sklearn.ensemble.IsolationForest]: https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.IsolationForest.html?highlight=isolationforest#sklearn.ensemble.IsolationForest
[Sklearn _2]: https://img-blog.csdnimg.cn/20200521195316593.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NtaWxleWFuOQ==,size_16,color_FFFFFF,t_70
[Link 2]: https://ww.lanzous.com/icum7xe
[https_www.cnblogs.com_fengfenggirl_p_iForest.html]: https://www.cnblogs.com/fengfenggirl/p/iForest.html