一种改进隔离森林的快速离群点检测算法

冯嘉琛，蔡江辉，杨海峰

(太原科技大学 计算机科学与技术学院，太原 030024)

1 引 言

离群数据(Outliers)是明显偏离其他数据、不满足数据的一般模式或行为、与其他数据存在显著不同的数据[1].离群数据往往蕴含着大量不易被发现但很有价值的信息，所以高性能的离群点检测算法[2]被广泛应用于信用卡欺诈交易、入侵检测、医疗诊断、地震预报等领域.现有的离群数据检测算法大致可以分为以下几类：基于统计的方法，基于距离的方法，基于密度的方法和基于聚类的方法等.其中，基于统计的方法首先建立一个数据模型，不能同模型拟合的对象被认为是离群点[3].代表性例子包括最小协方差矩阵(MCD)[4]和一类支持向量机(OCSVM)[5].基于距离的方法考虑数据对象给定半径的邻域，如果它的邻域没有足够多的其他点，则认为它是离群点[3]，例如k近邻算法[6]和反向最近邻算法[7].基于密度的方法采用数据点的邻域密度来表示其离群程度，离群点与正常点相比具有较低的密度.代表性的例子包括局部异常因子(LOF)[8]和基于局部密度的离群检测方法(RDOS)[9].基于聚类的方法假定正常数据对象属于大或稠密的簇，而离群点属于小或稀疏的簇，或者不属于任何簇[3].例如基于快速k近邻的最小生成树方法[10].但这些传统的检测方法都会受到“维度灾难”的影响，在高维空间中，由于数据量大且维度高，严重影响了离群数据挖掘的效果和效率[11]，算法在全维度进行离群检测时，真正的离群点被多个不相关维度的噪声效应掩盖，此时离群点通常嵌入到局部相关子空间中[12].

与基于密度和基于距离等方法不同，隔离森林[13]算法在识别离群点时考虑分散和聚类属性，它通过隔离数据来检测离群点，而不依赖于任何距离或密度度量.给定一个数据集，隔离森林构建了一个隔离树(iTree)集合.在树内，离群点是具有较短平均路径长度的样本.同时，隔离森林也可以被视为子空间方法，因为算法的评分函数量化了局部低维子空间分割特定点的容易程度，即越容易被分割的数据越有可能是离群点[12].但隔离森林在构造隔离树的过程中，选择根节点样本和选择切割点时随机性较强，可能导致构造隔离树的属性为无关属性，影响隔离树的性能，当存在较多无关属性时，会影响算法准确率和效率.

本文针对隔离森林算法的上述缺陷，提出了一种新的基于隔离森林的快速离群点检测算法FIF(Fast Isolation Forest).该算法首先根据所选根节点样本的数据分布，确定该样本集是否可能存在离群点，若不存在则不需构建隔离树，从而有效地避免无关隔离树对最终结果产生的影响；其次，在隔离树构建过程中，采用确定性的方法选择分割点，可以有效地降低随机选择对算法性能的影响；然后将隔离出的每个叶子节点的平均路径长度进行归一化，归一化后的结果即为离群值，将离群值最大的若干个数据对象视为离群点；最后采用UCI数据集，实验验证了该算法的正确性和有效性.

2 相关工作

2.1 隔离森林算法及相关概念

Isolation Forest主要利用集成学习的思路来检测离群点，它和随机森林类似，都是通过构建多棵决策树形成森林来对数据进行划分.但隔离森林每次选择划分属性和划分点(值)时都是随机的，而不是根据信息增益或基尼指数来选择.隔离树(Isolation tree)是一种特殊的二叉树，它把一维空间中的二分查找树扩展到了多维空间中，因此可以用于索引多维数据，在建树过程中，如果一些样本很快就到达了叶子节点(即叶子到根的距离很短)，则有很大概率是离群点.因为那些路径比较短的样本，都是距离主要的样本点分布中心比较远的，也就是说，可以通过计算样本在所有树中的平均路径长度来寻找异常点，该算法不依赖于近邻查询，也不需要计算距离，比传统的离群点检测算法更适合处理高维数据.

隔离森林算法中每个隔离树都是一个二叉树结构，其构造步骤是首先从训练数据中随机选择若干样本点作为子样本，放入树的根节点.其次随机指定一个维度，在当前节点数据中随机产生一个位于当前节点数据中指定维度的最大值和最小值之间的切割点，然后以此切割点生成一个超平面，将当前节点数据划分为两个子空间：把指定维度里小于该切割点的数据放在当前节点的左子树，把大于等于该切割点的数据放在当前节点的右子树.在叶子节点中递归重复以上过程，不断构造新的叶子节点，直到当前节点的高度超过了算法设置的阈值；或当前子树只包含一个叶节点；或当前子树的所有节点值的所有属性完全一致.

隔离树全部构造完成之后，算法训练阶段结束，需要用测试数据来评估生成的隔离森林.令训练数据遍历每一棵隔离树，计算该数据点最终落在每个树第几层，可以得出其在每棵树的高度平均值，平均高度值低于阈值的数据即为候选离群数据.文献[13]给出了计算离群值的方法：

(1)

其中，h(x)是数据点x从根节点到x所在叶子节点的路径长度，E(h(x))是所有隔离树集合的h(x)的平均值，c(m)指的是二叉搜索树中搜索不成功的平均路径长度：

(2)

其中H(i)为谐波数，通过ln(i)+0.5772156649(欧拉常数)来计算，公式(1)用c(m)来归一化h(x).若s接近于1，则它是离群点，若s远小于0.5，则它是正常点.

隔离森林是目前离群点检测比较常用的算法之一，它对内存要求较低，处理速度快，具有线性时间复杂度.因为每棵树都是互相独立生成的，可以部署在大规模分布式系统上来加速运算，所以能够适应大规模数据的处理需求.

2.2 隔离森林相关改进算法分析

目前针对隔离森林的改进方法主要包括：文献[14]提出一种名为SCiForest的检测算法，该算法通过引入随机生成的超平面构建模型，以便找到将离群点与正常点区分的合适投影来检测局部聚类离群点，但该算法相对于原隔离森林算法运行时间较长.文献[15]提出了一种名为Half-Space-Trees的检测算法，该方法针对数据流离群点检测构造了一个半空间隔离树，在选择切割点时使用所选属性的中点，将工作空间平分为两个半空间，从而创建节点的左右子节点.节点持续迭代，直到达到设定的最大深度，并根据质量概念使用滑动窗口对数据进行离群评分.文献[16]则针对隔离森林对局部离群点不敏感的缺点，提出了一种名为ReMass-IForest的检测算法，该算法使用基于局部相对质量的评估方法来对隔离出的数据进行排序，以检测局部离群点.上述各改进算法和原隔离森林算法采取的属性选择方式随机性较强，并且在大数据集的离群点检测方面用时较长.本文接下来的内容将针对隔离树在构建过程中的分割属性和分割点问题以及如何快速完成检测展开讨论，引入新的基于隔离森林的快速检测算法，以提高离群点检测的效率.

3 快速隔离森林算法

3.1 算法思想

针对隔离森林算法在构建隔离树分割属性和分割数据时随机性较强的问题，FIF重新定义隔离树，首先在构建隔离树采样时，对采样数据的数据分布进行分析，决定是否利用此样本集构造隔离树，以避免随机选择的根节点中包含较多没有离群点的样本集而对算法性能造成影响；然后在构造隔离树时，采用特定的切割点将数据分成两个子空间，比切割点大的放入右子树，小的放入左子树，这样做的目的同样是将随机选择切割点对算法的影响降低，并且可以加快隔离树的迭代.递归上述操作直到当前子树只包含一个节点或达到预设的树高，此时一棵隔离树构建完成.将若干隔离树组成隔离森林，然后计算每个被分割出的样本点在所有隔离树上的平均路径长度，将平均路径长度归一化后作为样本数据的离群值，选择离群值最高的前若干个数据点作为最终的离群点进行输出.

在隔离树的构建过程中，选择合适的根节点样本和属性分割值对算法至关重要，它们直接决定隔离树的性能.

定义(隔离树)：给定一组数据集D，随机选择X个样本点作为隔离树根节点子样本，再随机选择其中一维作为切割属性，在基于统计学的参数方法中，一元数据通常假定数据由高斯分布产生，且样本点离估计的分布均值超过三倍标准差的概率值很低，因此，由输入的根节点样本数据学习高斯分布的参数，若含有概率低的点，则说明可能存在离群值.用最大似然方法估计参数均值μ和标准差σ：

(3)

其中n是隔离树根节点样本数，在高斯分布的假定下，μ±3σ区域包含99.7%的数据，所以若有数据点落在此区域外则所选根节点样本中很可能包含离群点，若满足公式(4)，则选取X放入树的根节点：

maxValue>μ+3σ

(4)

其中maxValue代表样本集中的最大值，若不满足条件，则不再利用该子样本创建隔离树，而是将此树设计为一棵空树.这样做的目的是将可能影响隔离效果的树去除，既可以提高算法准确率，又能降低原隔离森林算法的运算时间.在选择切割点时，取样本数据最大值与最小值之间的黄金分割点作为切割点，以减小切割时的随机性并且黄金分割点切割能够让隔离树在生成子空间时每次都切割为与样本父节点均等比例的大小两棵左右子树，使构造子树时迭代速度加快.递归上述过程直到当前子树只包含一个节点或达到预设的树高，这里将此树定义为隔离树.

构建隔离树时采用子采样方法，因为当树的根节点样本太多时，包含正常点过多，正常点过于接近离群点导致算法隔离异常点所需的树高增加，分割离群点的子空间加深，隔离树分割离群点的能力降低，而采用子采样方法即可减少上述影响.隔离树通常是不平衡二叉树，因为稠密区域的数据点往往需要多次分裂才能被完全隔离，而稀疏区域的数据仅需几次分裂就能被完全隔离.因此，数据点的离群程度等于其在隔离树中的深度，并用公式(1)计算每个样本的离群值.如果数据集包含局部离群点，则将若干隔离树组成隔离森林后，把基于路径长度的全局排名度量替换为基于相对质量的局部排名度量.在隔离树结构中，数据点的相对质量是直接父节点和该点落入的叶节点的质量比，而数据的质量定义为一定区域内的数据点个数.为了能够增强隔离森林的局部离群点检测能力，可以用相对质量来评估离群值，参照文献[16]，数据点x的异常分数可以估计为数据质量的比率，如公式(5)所示：

(5)

与原隔离森林算法相同，样本的路径长度即平均高度以logn的速度增长，此时离群得分归一化不是有界的，不能直接比较，所以单个数据点在某棵隔离树的离群得分由公式(1)计算得到，样本最终的离群得分可以估算为各隔离树上的离群分数的平均值，如公式(6)所示：

(6)

对给定数据集中的每个数据点进行评分，就可以按其离群值分数的降序对数据点进行排序.当离群值越接近1时，该数据点是离群点的概率越大，当离群值远远小于0.5时，该数据点将不是明显的离群点.最后选取离群值最高的前若干个数据点作为离群点.

3.2 算法描述

算法的具体步骤如下：

1)构造隔离树

算法：iTree

输入：数据集D，样本点数量X，树高度限制l，当前树高e，

输出：隔离树

/*达到限定高度或孩子节点只有一个数据时完成树的构建*/

1)if e>=l or |x|<=1 then

2) return exNode

/*选择切割属性*/

3)else

4) 随机选择切割属性q∈X

/*确定当前样本是否适合建树*/

5) if maxValue<=μ+3σthen

6) 返回空树

7) else

/*选择黄金分割点作为切割点p*/

8) p=(maxValue-minValue)*0.382+minValue

9) Xl=filter(X,q

10) Xr=filter(X,q>=p)

/*递归构造隔离子树*/

11) return inNode{Left = iTree(Xl,e + 1,l),

12) Right = iTree(Xr,e + 1,l),

13) SplitAttr= q,

14) SplitValue = p}

15) end if

16)end if

2)构造隔离森林

与原隔离森林相同，给定一个包含n条记录的数据集D，随机采样一部分数据来构造每一棵树，保证不同隔离树之间的差异性，然后将构建好的隔离树组成隔离森林.

隔离森林的组建过程如下：

输入：数据集D,样本数量X,隔离树的数量t,限制树的高度为l

输出：隔离森林

1)初始化森林

2)fori=1 totdo

3)D′=sample(D,X)

4)Forest=Forest∪iTree(D′,0,l)

5)end for

6)return Forest

隔离森林构造完成之后，计算被隔离的样本在每棵隔离树的离群得分，样本在各隔离树的平均得分即为该点的最终离群分数，将离群得分最高的若干数据点确定为离群点.

3.3 算法复杂性分析

本文算法主要分为两个阶段，第一阶段为构造隔离树，第二阶段为组合隔离森林并计算离群值，对于包含n个点的数据集，构造隔离树平均情况下时间复杂度为O(n·log(n))，每棵隔离树所需要的空间复杂度为O(n).在最坏的情况下时间复杂度为O(n2).算法整体的时间复杂度为O(t(n+φ)logφ).为了使算法更有效，通常采用子采样策略，原因是大样本会影响隔离效果，当正常点过多时，正常点与异常点距离太近导致隔离异常点所需的路径长度变长，不利于隔离树的构造.子采样方法需要单独的测试阶段才能对数据点进行评分，测试阶段算法的时间复杂度和空间复杂度是恒定的，且都为O(n).若把整个数据集都放入隔离树根节点，则测试阶段每个数据点的平均时间复杂度为O(log(n)).改进算法与原隔离森林同样都不涉及距离的计算，且改进算法去除了可能含有干扰属性的隔离树，大大减少了计算开销.

4 实验结果与分析

基于上述思想，对本文提出的算法进行性能测试.实验平台配置为Intel core i7 8550U CPU，16G内存，64位操作系统的PC机，算法程序使用Python语言在Anaconda3 Spyder平台实现.

4.1 UCI数据集

为了验证所提方法的有效性，使用UCI机器学习库1http://www.ics.uci.edu和ODDS(异常检测数据集)2http://odds.cs.stonybrook.edu的11个真实数据集进行了实验.它们包含已知的离群点作为基础事实，且在其他离群点检测的文献中被多次使用.数据预处理阶段进行Z-S标准化处理，只保留连续型数值属性.

表1 选择的UCI数据集
Table 1 UCI dataset used in the experiment

数据集数据量维数离群数据占比/%Http(KDDCUP)56749730.4Shuttle4909797Breastw683935Arrhythmia45227815StatlogShuttle14500920.84Musk30621663.2Optdigits5216643WBC278305.6Mammography1118362.32Pima768835Smtp9515630.03

数据具体属性如表1所示，其中Http(kddcup)和Smtp是网络入侵检测数据，Shuttle是飞机的飞行数据，样本由两种类别构成，实验将相对较少的第二类样本标记为离群点，Breastw是威斯康星的乳腺癌诊断数据，其中恶性肿瘤占35%，实验将此类样本标记为离群点.Statlog Shuttle数据集中第二类中有3022个数据，约占20%，将这些数据点作为离群值.Arrhythmia是具有279个维度的多分类心律失常数据集.本实验去除五个分类属性，共274个属性.将其中数据量较小的3，4，5，7，8，9，14，15类组合作为离群点.Musk是麝香数据集，将非麝香类j146，j147和252作为正常点，而麝香类213和211作为离群值，并将其他类舍弃.Optdigits是光学识别手写数字数据集，数字1-9作为正常点，150个数字0的样本作为异常点.WBC数据集有两个类，良性和恶性.将该数据集的恶性类作为离群点.Mammography数据集有11183个样本，其中260个为钙化，将钙化的少数类作为是异常类，非钙化类作为正常类.

4.2 UCI数据集实验结果

本节对所提出的算法进行性能评估，与其他9种离群点检测算法进行AUC(Area Under Curve)对比并画出ROC(Receiver Operating Characteristic Curve)曲线，计算AUC[17]的公式(7)如下：

(7)

其中M和N分别是正样本的个数和负样本的个数，rankinsi代表第i条样本的序号(概率得分从小到大排，排在第rank个位置).∑insi∈positiveclass表示只把正样本的序号加起来.在ROC曲线中，AUC的值就是曲线下方的面积.AUC越接近1，说明算法效果越好，AUC低于0.5，则说明算法性能比随机检测效果差.

4.2.1 根节点采样大小X对AUC的影响

本节实验采用数据量大于10000的数据集对不同的X进行实验，因为当根节点采样较大时，数据量小的数据集将不再是子采样，而是利用全部数据构造隔离树.实验结果如图1所示.

图1 采样数X对算法AUC的影响Fig.1 AUC impact of X

由图1可知，FIF算法在各数据集上的AUC在初始阶段随根节点样本数X的增大而增加，由于离群点只占整个数据集中非常小的一部分，当采样数很小时，所构造的隔离树往往不包含离群点，此时算法无法完成有意义的检测.从实验结果可以看出，采样数X为16时，AUC已逐渐趋于收敛.这是因为X为16时隔离树已经具备将数据切割为多层子空间的能力，计算离群值的归一化方法可以将较长和较短的路径长度数据点进行有效区分.当样本数为256时AUC接近最大值，与原隔离森林算法相同，算法在X很小时就能得到很快收敛且样本较小时构造隔离树所需的时间较短，小样本的隔离树还可以适当减轻高维数据中掩蔽效应对精度的影响.因此不需要一直增加X.因为过度增加X只会使时间和空间复杂度增加，且样本数量很大时包含正常点过多，正常点与离群点距离接近会干扰隔离过程，导致算法精度下降.由于本文算法要先分析所选样本的数据分布再决定是否构建隔离树，所以若样本太小则很有可能其中不包含离群点，无法完成有意义的隔离树构建.因此选择256作为根节点样本集的大小，既可以使隔离树在构建时能多次切割将离群点和正常点分割，又能避免大数据量造成的淹没和掩蔽效应.

4.2.2 隔离树数量t对AUC的影响

采用与4.2.1节中同样的方法对不同的t进行实验，实验结果如图2所示.

由图2可知，算法在五个数据集上的AUC初期随隔离树的数量t增加而增加，且算法AUC在t很小时即可收敛且对于t的增加算法性能不敏感，因此，为了使算法效率提高，可以设置较小的t，但隔离森林算法本身依赖于集成学习的聚合能力.一棵树可能不是最优的，多棵树集合就能发挥强大的性能.FIF在选择隔离树样本时，会根据样本分布选择可能含有离群点的子样本集进行隔离树的构建，当选到可能不包含离群点的子样本集时，会将此树变为空树，为了避免较小的t可能只产生少量的有效隔离树而对最终的结果产生不良影响，

图2 隔离树数量t对算法AUC的影响Fig.2 AUC impact of t

我们要保证树的数量不能太小，从多次实验可以看出，在100棵隔离树时既可保证算法能构造出一定数量的有效隔离树，又能确保时间和空间消耗在很小的范围内，同时体现出集成方法的组合特性.若无特殊说明，实验中采用t=100作为默认值，可同时兼顾精度和效率.而对于树的高度限制l，隔离树作为一棵二叉树，是将较早被隔离出的数据视为离群点，越晚被隔离的点越有可能是正常点，因此不需要把所有的点都隔离，所以在根节点采样数为256时，将树高限制为8，使算法时间和空间消耗较少.

4.2.3 各算法AUC及运行时间对比

本节的目的是对10种离群点检测算法的AUC进行比较.对于原隔离森林算法和本文改进算法，我们采用默认参数：创建100棵隔离树，每棵树256个样本，树高限制为8.在4.2.1和4.2.2节中已做出分析，结果表明在该默认参数设置下检测性能接近最优.KNN算法使用距离第一个k最近邻居的距离作为离群值得分，使用KNN默认设置k=10.PCA[18]算法使用具有特征向量超平面的加权投影距离之和作为离群值得分.MCD使用马氏距离作为离群值得分.基于密度的LOF算法在实验中设置常用的k=10.ABOD[19]在该实验中使用FastABOD并用10个邻居来评估离群得分.FB算法是特征装袋，本实验中采用10个LOF作为训练子模型.LSCP[20]是一种无监督的并行异常检测集合框架，本实验中使用平均最大值策略.

表2 各算法的AUC
Table 2 AUC of several algorithm

图3 各算法ROC曲线Fig.3 ROC curve of several algorithm

表2展示了在11个数据集上各算法的AUC，并突出显示了各数据集中两个最高的AUC.其中HTTP和SMTP数据集因为数据量较大，所以一些时间复杂度很高的算法不能完成有效检测，表中用NA表示.通过比较各算法的AUC可以看出本文改进的算法在Arrhythmia，WBC，Pima和Statlog Shuttle数据集上比原IForest算法AUC高，在其他数据集上略低于或与原IForest基本相同.FIF和IForest在很多数据集上表现优于其他算法，且FIF，Iforest和MCD的表现较为稳定.KNN，LOF和其他基于距离测量的算法受数据维度的影响很大.当维度很高时，算法的效果并不理想.而FIF性能优于其他算法是因为该算法通过找到可能存在离群点的子样本集来构造隔离树，降低了原隔离森林算法中随机效应对实验结果产生的不良影响，使隔离树分割出的子空间比随机选择属性维度准确率高，且计算离群值时可信度更高.

图3展示了各算法在三个代表性数据集上的ROC曲线，它们分别是FIF与其他算法ROC曲线相近的图像，比其他算法ROC曲线高的图像和ROC曲线低于其他算法的图像，其中虚线是本文算法，通过图3可以看出，在Arrhythmia数据集上改进算法ROC曲线与其他算法基本相同，在Shuttle数据集上ROC曲线下面积几乎达到了1，比其他算法高很多，而在Statlog-shuttle数据集上的AUC仅低于MCD算法，这是因为基于隔离的检测方法更倾向于极值，而数据集内部区域存在离群点时，算法可能效果不佳，MCD方法则以多元高斯分布的形式将整个数据集建模为关于其均值的高斯分布，把每个方向按比例缩放到特征空间中，因此该高斯分布的所有不相关方向具有相同的方差.在这种情况下，将点与球面高斯中心的距离作为离群值得分对数据内部含有离群点的数据集是非常有效的[12].但MCD算法在处理大数据集时构造相似度矩阵并对角化在时间和空间复杂度方面都面临巨大挑战.

图4展示了本文算法与原算法及2.2节中介绍的三种改进隔离森林算法在各数据集上运行十次的总时间对比.由图4可以看出，FIF的运行时间与其他算法相比较快，在Shuttle，Breastw，Musk，Optdigits数据集上进行十次实验的运行时间比原算法快近十倍，在Http数据集上的时间比原算法快数百秒.SCiForest算法为了使正常簇和异常簇分割，要使用其设定分割选择标准寻找最佳分裂点，而原算法则采用随机分割，所以SCiForest比原算法稍慢.ReMass-iForest算法构造隔离树时使用和原算法相同的策略，因此与原算法具有相同的时间复杂度.但由图4可以看到它的运行时间比原算法稍快，这是由于原算法在子树只包含一个节点时才停止构造隔离树，而ReMass-iForest在评估阶段采用基于局部相对质量的方式来检测离群点，在构建隔离树过程中子树的节点小于5时即停止分裂，因此该算法比原隔离森林算法稍快.而本文算法运行时间最短的主要原因是FIF在构建隔离树时去除了可能不包含离群属性的树，只保留可能存在离群点的子样本集构造隔离树，减少了构造无关隔离树的时间，并使用收敛较快的黄金分割点来切分叶子节点，而隔离森林本身作为一种子空间方法，可以将隔离树看作隔离低维度的局部子空间中的集合，所以算法的微小修改也可用于快速发现低密度的子空间区域，使得算法在计算离群值时消耗的时间更少.

图4 算法的运行时间(以秒为单位)Fig.4 Run time(s)

5 结束语

本文提出了一种基于隔离森林的快速离群点检测算法.该算法通过使用确定的分裂点，降低了隔离森林的随机效应，提高了算法准确性；引入启发式的根节点样本选择策略，找到可能包含离群点的子空间构建隔离树，避免了无关属性对离群数据的影响，使算法在不降低精度的情况下提高隔离森林的效率.采用UCI数据集实验验证了算法的正确性和有效性.下一步的工作是实现算法的并行化，以适应海量高维数据.