基于相关子空间的扩展隔离森林离群检测算法

刘 佳，朱鹏云，荀亚玲

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

0 引 言

离群检测是数据挖掘任务的重要内容之一，试图捕获显著偏离多数模式的异常情况[1]，挖掘出潜在的、有意义的知识。离群检测挖掘出的离群数据对象隐藏着非常重要的信息和知识,其背后可能蕴含着更大的研究价值。离群检测已经被广泛应用于入侵检测[2-4]、欺诈检测[5-6]、医疗异常诊断[7-8]、工业控制系统的异常检测[9]、无线传感器网络的异常检测[10]、城市交通流异常检测[11]、天体光谱数据挖掘[12]等领域。现有的离群检测算法大致可以分为以下几类：基于统计的方法、基于距离的方法、基于密度的方法、基于聚类的方法和基于集成的方法等。集成离群检测作为一种离群检测方法，将多个离群检测算法或模型相结合，形成一个集成框架，提高离群检测性能。

隔离森林(Isolation Forest)[13]作为一种集成离群检测方法,利用离群数据少且与众不同的特点将离群数据隔离在离树根较近的地方，而将正常数据隔离在离树根较远的一端。隔离森林可以将离群数据与正常数据快速分离，具有较低的线性时间复杂度。在组合多棵树构成森林后，离群检测效果优于多数传统的离群检测算法，但隔离森林在构建隔离树的过程中，分枝仅随机选择一个维度属性进行水平或垂直的切割，且属性可能为无关属性，降低了离群检测效果。扩展隔离森林算法具备了隔离森林离群检测的优点，允许数据切片使用带有随机斜率的超平面，解决了隔离森林中树分枝轴平行的切割使异常分数图中存在偏差等问题[14]，但隔离树超平面选取在数据集的密集区域或含有无关维度的区域，影响离群检测的效果。该文采用相关子空间，提出了一种基于相关子空间的扩展隔离森林离群检测算法，解决了扩展隔离森林离群检测确定超平面随机性强的问题，其主要贡献如下：

·提出了一种基于相关子空间的分支切割截距点选取方法；

·给出了一种扩展隔离森林分割平面选择策略；

·提出了一种基于相关子空间的扩展隔离森林离群检测算法。

1 相关工作

离群检测算法大致分为以下几类：基于统计的方法、基于距离的方法、基于密度的方法、基于聚类的方法和基于集成的方法等。隔离森林是一种独特的集成离群检测方法，它利用一种隔离机制来检测异常，通过递归轴平行细分将每个实例与其余实例隔离开来。隔离森林有较低的线性时间复杂度，避免了基于距离和密度方法进行检测时的计算量大的问题。隔离森林是集成的方法，组合多棵树构成森林后，离群检测效果优于多数传统的离群检测算法。隔离森林离群检测可以用在含有海量数据的数据集上，由于每棵树都是互相独立生成的，因此可部署在大规模分布式系统上来加速运算。

隔离森林作为一类集成离群检测方法，国内外学者对其进行了大量研究，其典型研究工作包括：文献[14]扩展隔离森林离群检测算法可选取随机斜率的超平面，解决了隔离森林中树分枝轴平行的切割使异常分数图中存在偏差等问题。文献[15]提出一种利用隔离概念进行离群检测的方法(isolation using Nearest Neighbor Ensemble，iNNE)，采用最近邻算法来代替基于树的方法来隔离数据对象,使用最近邻隔离超球体来隔离目标空间中的数据，是一种基于隔离思想的高精度集成学习算法，对局部离群数据较敏感，但在数量巨大的数据集中时间开销太大。文献[16]提出了一种基于k-means的隔离森林算法，优化隔离树的结构通过将每个节点分割成k个子节点，且在树的每个节点上采用k-means进行划分。该算法可以处理不同应用领域的数据，但没有考虑随机选择的属性可能为无关属性的问题。文献[17]提到基于树隔离机制的离群检测方法使用的这种快速隔离机制仅局限于距离测量，不能推广到其他常用测量，因此提出了一个LSHiForest通用框架，使用位置敏感哈希(LSH)森林。该框架具有通用性，可以用不同范围的LSH函数实例化，并且快速隔离机制可以扩展到定义LSH函数的任何距离度量、数据类型和数据空间。该文献表明现有的基于树隔离的检测方法是此框架的特例，具有相应的距离度量，且该框架具有较高的时间效率和异常检测效果。文献[18]提出了一种基于模糊孤立森林算法的离群数据检测方法，通过挑选一些有价值的属性对其分别建树组成孤立森林，从多维度出发，对每一维属性的检测结果进行隶属度判断，最后与模糊矩阵进行模糊运算得到最终评价结果。但算法需要从单因素的角度对各等级的模糊子集做隶属度判断，由专家根据评判等级对评价对象进行打分，组成模糊关系矩阵。

隔离森林离群检测算法可以将离群数据与正常数据快速分离，有较低的线性时间复杂度。但隔离森林每次分割随机选取一个维度，高维空间中可能有大量的维度信息没有被使用进行分割，且可能存在无关维度影响树的构建，基于路径长度的全局排名测度对局部异常不敏感，轴平行的细分掩盖了轴平行之间存在的异常。针对隔离森林算法的不足，一些国内外学者进行了改进，但算法选择分割点的方式随机性较强，均没有考虑无关属性维对离群检测的影响。该文提出了一种基于相关子空间的扩展隔离森林离群检测算法，利用多维度随机斜率的超平面，避免了轴平行分割带来的不足；优先在数据分布稀疏的数据集中进行分割，使离群数据快速地从稀疏数据区域中隔离出来；在数据的相关子空间维度上确定超平面，避免了无关维度的干扰，提高了离群检测的准确率和效率。

2 隔离森林与相关子空间

2.1 子空间与隔离森林离群检测

隔离森林离群检测利用了离群数据的两个特征：离群数据占数据集总体规模的比重较小；离群数据相比正常数据的属性值存在明显的差异。在隔离森林中，递归地随机分割数据集，直到所有的样本点都是孤立的。在该随机分割策略下，离群数据可以快速被隔离，而正常数据需要许多分支切割来隔离。参照文献[13]，相关概念定义如下：

定义1(隔离树，Isolation Tree)：令T是一棵二叉隔离树的节点，T要么是没有子节点的叶子节点(外部节点)，要么是只有两个孩子节点(Tl,Tr)的内部节点。每一次分割都包含属性q和分割值p，将数据点在属性q的值qi

给定n个样本数据的数据集X={x1,x2,…,xn}，数据集的特征维度为d。为其构造一棵隔离树，每次分割需要随机选择一个特征q及其分割值p，递归地分割数据集X构造左子树和右子树，直到满足以下任意一个条件：(1)树达到了限制的高度；(2)节点上只有一个样本；(3)节点上的样本所有特征都相同。

定义2(路径长度)：在一棵隔离森林树Isolation Tree中，从根节点到叶子节点所经历边的数目称为数据点x的路径长度，记为h(x)。

由于Isolation Tree与二叉查找树的结构等价，外部节点的平均路径长度h(x)的估计等价于二叉查找树中查找不成功的平均查找长度。对于给定的数据集X，二叉查找树中查找不成功的平均查找长度为：

c(n)=2H(n-1)-(2(n-1)/n)

(1)

其中，H(i)为调和数，H(i)=ln(i)+0.577 215 664 9 (欧拉常数)；n为叶子节点数；c(n)为给定n时h(x)的平均值，用来标准化数据点x的路径长度h(x)。数据点x的离群得分计算方法如下：

(2)

其中，E(h(x))为Isolation Tree集合中h(x)的平均值。当E(h(x))→c(n)时，s→0.5，即当所有数据均返回的s≈0.5时，全部样本中没有明显的异常值；当E(h(x))→0时，s→1，即当数据返回的s非常接近于1时，它们是异常值；当E(h(x))→n-1时，s→0，即当数据返回的s远小于0.5时，它们有很大的可能为正常值。

隔离森林离群检测每次随机选择一个属性维再随机选择其属性维的一个值作为分割点进行分割，一方面，隔离森林离群检测受到“维灾”的影响，在高维空间中一些无关维度严重地影响离群检测效果；另一方面，选择的分割点若在稠密数据区域，很难将离群数据隔离出来。

2.2 高斯混合模型与相关子空间

在隔离森林离群检测中，每次分割在由有意义属性维构成的子空间中，随机选择一个属性，可避免无关属性维对离群检测的干扰。在稀疏数据区域中，随机选择一个属性取值实现分割，可避免稠密数据区域的属性取值分割对离群检测的影响。

在离群检测中，某些相关属性维提供了有价值信息，而有些属性维有价值信息很少甚至没有[20]。若利用所有属性实现离群检测，就会受到离群信息很少的无关属性干扰。参考文献[20-21]，相关子空间是非均匀分布的属性维组成的集合，可有效地体现出“离群数据”的价值信息，其相关定义如下：

定义4：设DS是一个d维数据集,属性集FS={A1,A2,…,Ad},数据对象x的最近邻为N(x,FS)(即局部数据集LDS),如果N(x,FS)在Ai属性维上的取值是非均匀分布的,则称Ai可以提供有价值的信息,属于相关子空间中的属性维；反之，如果N(x,FS)在Ai属性维上的取值是均匀分布的,则称Ai不能提供有价值的信息,属于不相关子空间中的属性维。

为了通过局部属性维数的稀疏性来度量属性是否服从均匀分布，在文献[21]中，引入了稀疏度的概念。第i条数据第j维度的数据稀疏度yij为:

(3)

由公式(3)可得知，yij代表局部数据属性维的方差，yij较大,表明xi的局部数据集在属性维j上的值不均匀，xij在其局部数据集中的密度较小，xij所在的是稀疏子空间(相关子空间)；相反，yij较小，表明xi的局部数据集在属性维j上的值较均匀，xij在其局部数据集中的密度较大，xij所在的是稠密子空间(不相关子空间)。根据公式(3)，可以计算所有数据对象在每个属性维度的稀疏度，并生成整个数据集的稀疏因子矩阵，稀疏度矩阵每个维度的稀疏度yij是由稀疏子空间和稠密子空间混合组成的。通过稀疏度矩阵，可以更方便衡量数据空间的稠密和稀疏区域，去除均匀分布属性维，保留非均匀分布属性维，发现数据空间的相关子空间。

文献[21]中通过预先设定好的阈值对每个维度上稀疏因子进行区分，从而确定各数据对象的相关子空间和不相关子空间，解决了检测相关子空间时时间复杂度较高的问题，提高了算法的效率，然而通过同一个阈值对所有的维度确定子空间，当各个维度的数据分布有差异时，得到的相关子空间就会有一定的误差。但高斯混合模型利用高斯概率密度函数(正态分布曲线)精确地量化事物，它是一个将事物分解为若干的基于高斯概率密度函数形成的模型。稀疏度矩阵每个维度的稀疏度yij是由稀疏子空间和稠密子空间混合组成的，高斯混合模型的灵活性使其能够很好地适应稀疏度的分布，可以自适应地得到该维度的稀疏子空间和稠密子空间[22]。因此，利用高斯混合模型识别稀疏度yij所在的子空间，即该维度的相关子空间和不相关子空间。

把第j维所有数据对象的稀疏度yij用作高斯混合模型：

(4)

第r个高斯分布的密度函数为:

(5)

其中，每个部分的密度函数Nr含有两个参数，分别为期望ur和标准差σr，ur描述正态分布的集中趋势位置，σr描述正态分布中数据分布的离散程度。使用高斯混合模型对每一维度稀疏度进行拟合，把稀疏度分为两个高斯分布，稀疏度较大的分布中的数据构成相关子空间，较小的分布中的数据构成无关子空间，所以该高斯混合模型由两个高斯分布组成，即m=2。EM算法[23](最大似然估计)是一种改善模型参数估计的迭代算法，可以用来估计模型中的参数，也是GMM参数估计最常用的一种方式。使用EM算法来估计高斯混合模型各个参数，得到每一维度的每个稀疏度属于两个高斯分布的概率值，在哪个高斯分布的概率值大就属于哪个高斯分布。同时可以得到每一维度的两个高斯分布的均值，均值较大的高斯分布的稀疏度比较大，属于均值较大的高斯分布的数据构成的子空间是稀疏子空间即相关子空间。

文献[22]中使用二进制矩阵Z直观表示稀疏因子矩阵的相关性。第i个数据对象第j维度的值zij的定义如下：

定义5：对于数据对象xi，yij是第i个数据对象第j维度的稀疏度，zi是其子空间向量，zij是第i个数据对象第j维度的值，如果yij属于相关子空间，则zij=1，如果yij属于不相关子空间，则zij=0。

根据EM算法对稀疏度区分的结果和定义5，可以生成数据对象的子空间向量zi。

3 相关子空间与扩展隔离森林离群检测

3.1 相关子空间与分支切割截距点

设DS是一个d维数据集，xi为DS中的任意数据对象，依据公式(3)、(4)、(5)和定义5，可得到xi的子空间向量zi。为了刻画xi所有属性维度的稀疏程度，可定义如下的xi相关维系数mi：

(6)

由公式(6)可知，mi越大，表明xi在相关子空间中的维度占DS全部维度d的比值越大，即：xi的稀疏维度数量越多，xi越可能处于稀疏区域；反之，mi越小，表明xi在相关子空间中的维度占DS全部维度d的比值越小，即：xi的稀疏维度数量越少，xi越可能处于稠密区域。

利用相关维系数mi，将数据集DS分成稠密分布的子集Dd和稀疏分布的子集Ds，其中：Dd={xi|xi∈DS，mi=0}，Ds={xi|xi∈DS,mi≠0}。当mi=0时，xi的每个维度都不属于相关子空间属性，xi不存在稀疏属性维，xi属于稠密区域；当mi≠0时，表示xi的维度属于相关子空间属性，xi含有稀疏属性，xi属于稀疏区域。

由公式(3)可知，xi的稀疏度yij是在xi的局部数据集LDS上获得的，xi的局部数据集LDS反映了xi的分布情况，公式(4)和(5)高斯混合模型能很好地区分数据对象属性维的稀疏，因此xi的子空间向量zi能够准确反映局部数据的分布特征，mi的大小是由zi的取值决定的，可以较为准确地刻画数据对象分布的稀疏，从而可将DS划分为稀疏区域和稠密区域。

3.2 扩展隔离森林分割平面选择策略

依据该选择策略确定超平面，递归其分割操作，直到当前子树只包含一个节点或达到预设的树高。优先在数据分布稀疏的数据集中，选择分支切割的随机截距点，可快速地使离群数据从稀疏数据区域中隔离出来，并在截距点数据所对应的相关子空间维度上，生成超平面的随机斜率来确定超平面，可避免无关维度的影响，提高扩展隔离森林离群检测的效果。

3.3 扩展隔离森林离群检测算法

综上所述，采用相关子空间，扩展隔离森林离群检测基本思想为：首先，通过kd树寻找数据集中每个数据对象的k近邻并生成其局部数据集LDS，依据公式(3)-(5)计算出每个数据对象的稀疏度yij并识别yij所在的子空间,生成数据对象xi的子空间向量zi；然后，随机采样t次构造t棵不同的隔离树,每次随机采样ψ个数据，按照上述分割平面选择策略，构造每棵隔离树；最后，对整个数据集进行检测，使用PathLength函数计算数据对象xi在gTree树的路径长度h(x)，并计算xi在各隔离树的平均路径长度，依据公式(2)将平均路径长度归一化后作为数据对象的离群得分，输出离群得分最高的前M个数据对象作为离群数据。其算法描述如下：

算法：RSGMM-EIF

输入:数据集DS，子抽样大小ψ，隔离树数量t，近邻数k

输出:离群数据

1.n=DS的数据个数，d=DS的维度

2.for(i=0;i

3.LDSi=getknn()； //计算第i个数据对象的局部数据集LDS

4.spi=getspdegree()； //依据公式(3)计算第i个数据对象的稀疏度

5.}

6.Z=getsubspace(); //依据公式(4)和(5)计算相关子空间

7.IForest=iForest(DS,t,ψ)；//构造隔离森林

8.T=gTree(DS,e,l,Z)；//构造gTree

9.forxiin DS{

10.h_temp=0

11.forjin range(t){

13.h_temp= h_temp+depth；

14.}

15.Eh=h_temp/t；

16.依据公式(2)，计算数据对象的离群得分；

17.}

18.选取离群得分最大的M个数据对象作为离群数据；

19.End RSGMM-EIF

函数：gTree(DS,e,l,Z)

输入:数据集DS,当前树的高度e,隔离树的高度限制l,二进制矩阵Z

输出:隔离树

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

1.ife≥lor |X|≤1 then

2.return exNode

3.else

4. 依据公式(6)和(7)计算稀疏分布的数据集Ds；

5.if len(Ds)≠0，

8.else

11.end if

15.end if

16.End gTree

算法复杂性分析：参照文献[22]，计算数据对象的稀疏度和利用高斯混合模型识别数据对象的相关子空间的时间复杂度是O(nlogn)+O(n*k*d)+O(n*d)≈O(nlogn)+O(n*k*d)；在构建gTree时，每次分割需要生成确定超平面的两个向量并计算不同数据对象的隔离方向，构造隔离森林的时间复杂度是O(tdψlog2ψ)；计算整个数据集离群得分的过程时间复杂度和空间复杂度是O(ntdlog2ψ)；RSGMM-EIF的时间复杂度是O(nlogn)+O(n*k*d)+O(tdψlog2ψ)+O(ntdlog2ψ)。

4 实验结果及分析

实验环境：Intel(R) Core(TM) i5-1135G7，16 GB内存，Windows10操作系统，采用python语言实现了RSGMM-EIF算法及对比算法IF[13]、EIF[14]、iNNE[15]和基于密度的局部异常因子LOF算法[24]。采用UCI数据集作为实验数据，详见表1。

表1 UCI数据集

在表1中，Pima是印第安人糖尿病诊断数据集，由8个医学预测变量和一个目标变量Outcome类标变量(0或1)组成，预测变量包括患者的怀孕次数、BMI、胰岛素水平、年龄等；Cardio是由心电图上的胎儿心率(FHR)和子宫收缩(UC)特征测量结果组成的分类数据集，产科专家将其结果分为正常、可疑和病理三个类别，将可疑类的数据对象丢弃后作为离群检测数据集；Satellite是卫星图像的分类数据，样本分为7类，其中第6类没有实例，实验将数量较少的第2、4、5类样本标记为离群数据；Satimage-2是将多分类数据集Statlog (Landsat Satellite)的第2类数据对象作为离群数据，其他类合并作为正常数据得到的；Optdigits是光学识别手写数字数据集，数字1～9的数据对象作为正常数据,150个数字0的数据对象作为离群数据；Mnist将手写数字的原始Mnist数据集中数字0的图像作为正常数据，将抽取的700幅数字6图像中作为离群数据，并且数据集的特征是从图像总共784个特征中随机抽取了100个。

性能评估指标：AC和AUC。准确率AC表示给定测试集预测正确的样本数与总样本数之比，准确率能够衡量预测结果总体的正确率。ROC曲线是一个二维平面上的曲线，平面的横坐标是实际负样本中被错误预测为正样本的概率(FPR)，纵坐标是实际正样本中被预测正确的概率(TPR)，可准确反映FPR和TPR的关系，能更好地衡量样本不均衡的情况，是检测准确性的综合代表。AUC(Area Under Curve)是ROC曲线下方的面积。AUC值可以体现算法的性能，AUC越接近1，表明算法效果越好，AUC低于0.5，表明算法效果比随机检测还差。

4.1 参数ψ

为了实验验证参数抽样数ψ对算法性能的影响，采用了表1中的5个数据集，其实验结果详见图1和图2。

图1 抽样数ψ对算法AC的影响

图2 抽样数ψ对算法AUC的影响

从图1和图2可以看出，随着ψ增大，AC、AUC指标值逐渐增加，并接近最优值，后有所降低，表明将ψ一般设置为256通常可取得好的检测效果，无需再增大ψ，与文献[13]中的结论一致。其主要原因是随着ψ增大，隔离树的树高增加，可以更好地区分数据对象的路径长度，得到数据对象的离群得分；当样本量过大时，包含正常数据对象过多，不利于离群对象被隔离出来，导致算法效果不好。

4.2 参数t

为了实验验证参数隔离树的数量t对算法性能的影响，采用表1中的4个数据集，其实验结果详见图3和图4。

图3 隔离树数量t对算法AC的影响

图4 隔离树数量t对算法AUC的影响

从图3和图4可知，随着t的增加，AC、AUC指标值逐渐增加,并趋于稳定，表明随着t值的增加，离群检测性能趋于稳定。其主要原因是隔离森林离群检测依赖于集成学习的聚合能力，多棵树集合更体现隔离森林离群检测优势。

4.3 近邻k

为了实验验证参数近邻k对算法性能的影响，采用了表1中的4个数据集，其实验结果详见表2。

表2 近邻k对算法性能的影响

4.4 离群检测性能

为了实验验证算法的离群检测准确性，采用了表1中的数据集，以及AC和AUC指标，其实验结果详见表3。RSGMM-EIF、IF和EIF的默认参数:创建100棵隔离树,每棵树256个样本,树高限制为8。

表3 离群检测算法AC和AUC的比较

从表3可知，在大部分数据集上，RSGMM-EIF的AC和AUC指标值大，表明RSGMM-EIF优于其他算法的离群检测效果。在大部分数据集上，RSGMM-EIF优于IF和EIF的离群检测效果，其主要原因是RSGMM-EIF利用了相关维系数mi，将数据集划分为了稠密区域和稀疏区域，优先在稀疏数据区域中选择分支切割的随机截距点，使离群数据快速地从稀疏数据区域中隔离出来，且在数据对象的相关子空间确定超平面的随机斜率，避免了无关维度的干扰，算法性能更佳。在少部分数据集上，EIF是在数据集的全维度空间中确定超平面，利用了每个维度的信息，取得了良好的离群检测效果。iNNE和LOF在大部分数据集上离群检测效果不佳，主要原因是iNNE的抽样数ψ对检测性能有显著影响，若ψ过大，会将分布密集的一些正常对象当成异常对象；LOF没有考虑无关属性的影响，且对密度差异较大的簇边界上的数据对象评分不准确。

5 结束语

扩展隔离森林离群检测的超平面选取在数据集的密集区域或含有无关维度的区域，影响了离群检测效果。该文采用相关子空间，给出了一种扩展隔离森林离群检测算法RSGMM-EIF。该算法利用数据对象的稀疏度和高斯混合模型，构造了相关子空间，并在扩展隔离树构建过程中，利用其相关子空间，确定超平面，从而使离群数据快速地从稀疏数据区域中隔离出来，避免了无关维度的干扰。