孤立森林（Isolation Forest）算法简介

简介：

孤立森林算法是一种适用于连续数据的无监督异常检测方法，由南京大学周志华教授等人于2008年首次提出，之后又于2012年提出了改进版本。与其他异常检测算法通过距离，密度等量化指标来刻画样本间的疏离程度不同，孤立森林算法通过对样本点的孤立来检测异常值。具体来说，该算法利用一种名为孤立树的二叉搜索树结构来孤立样本。由于异常值的数量较少且与大部分样本的疏离性，因此，异常值会被更早的孤立出来，也即异常值会距离的根节点更近，而正常值则会距离根节点有更远的距离。此外，相较于LOF，K-means等传统算法，孤立森林算法对高纬数据有较好的鲁棒性。

定义：

我们先给出孤立树(Isolation Tree)和样本点在孤立树中的路径长度的定义

孤立树：若为孤立树的一个节点，存在两种情况：没有子节点的外部节点，有两个子节点和一个test的内部节点。在的test由一个属性和一个分割点组成，的点属于,反之属于。

样本点在孤立树中的路径长度:样本点从的根节点到叶子节点经过的边的数量

基本思想：

从下图我们可以直观的看到，相对更异常的只需要4次切割就从整体中被分离出来，而更加正常的点经过了11次分割才从整体中分离出来。这也体现了孤立森林算法的基本思想。(ps:图片来自原论文)

Isolation_Forest_show.jpeg

算法介绍：

下面，我们来详细介绍孤立森林算法。该算法大致可以分为两个阶段，第一个阶段我们需要训练出颗孤立树，组成孤立森林。随后我们将每个样本点带入森林中的每棵孤立树，计算平均高度，之后再计算每个样本点的异常值分数。

Step1: 为给定数据集, ,从中随机抽取个样本点构成的子集放入根节点。
Step2:从个维度中随机指定一个维度，在当前数据中随机产生一个切割点，。
Step3:此切割点生成了一个超平面，将当前数据空间划分为两个子空间：指定维度小于p的样本点放入左子节点，大于或等于p的放入右子节点。
Step4:递归Step2和Step3，直至所有的叶子节点都只有一个样本点或者孤立树 已经达到指定的高度。
Step5:循环Step1至Step4，直至生成个孤立树

第二阶段：
Step1: 对于每一个数据点,令其遍历每一颗孤立树,计算点在森林中的平均高度,对所有点的平均高度做归一化处理。异常值分数的计算公式如下所示：

其中，

示例：

from sklearn.ensemble import IsolationForest  
from scipy import stats  
rng = np.random.RandomState(42)
X_train = data[:10000,:]
X_test = data
clf = IsolationForest(max_samples=256,random_state=rng)
clf.fit(X_train)
y_pred_test = clf.predict(X_test)

参考：https://dl.acm.org/citation.cfm?doid=2133360.2133363