基于模拟退火的扩展孤立森林异常检测算法

王诗愉，肖利东，严心淳，应文豪

（1.常熟理工学院计算机科学与工程学院，江苏 常熟 215500；2.常熟市医学检验所，江苏 常熟 215500）

0 引 言

在数据挖掘中，异常检测是指对不符合预期模式的样本进行识别，从数据集中识别出与大多数样本差异较大的对象。异常点也被称为离群值、噪声和偏差等［1］，通常被认为是与其他数据点明显不同或不符合整体预期正常模式的数据点［2］。异常检测是数据挖掘领域中一个重要的方面，被广泛应用于各个领域。例如，在医学领域中，异常数据可能意味着禽流感等传染类疾病的预警，而在天文领域中，异常数据则可能标志着新星的发现［3-6］。因此，异常数据可能具备和正常数据相等的科学价值。

近年来，国内外学者对异常检测领域进行了深入的探讨，提出了许多实用性很高的异常检测算法，为异常检测的进一步研究奠定了基础。Domingues等［7］对常见的异常检测算法进行了分类总结，并根据异常检测所使用技术的不同，分为基于连接函数的异常检测方法［8］（Copula-Based Outlier Detection，COPOD）、基于距离的异常检测方法［9］和基于密度评估的异常检测方法等。其中基于密度评估的局部离群因子检测方法［10］（Local Outlier Factor，LOF）解决了数据倾斜分布下的异常检测问题。LOF 通过计算局部可达密度来得到每一个样本点的局部离群因子，最后根据阈值判断该样本点是否异常。但是，基于密度评估的局部异常检测方法时间复杂度均为O（n2）［11］，这种方法在大规模数据集上的计算成本很高。同时，因为数据相似度的计算离不开距离计算，所以可能会面临距离计算上的“维数灾难”问题［12］。随着大数据时代的到来，数据集的数量和维度呈爆炸式增长，基于此，设计出在高维数据集上表现良好的异常检测算法具有重要意义。

iForest［13］是一种基于相似度的算法，与集成学习算法随机森林［14］有许多内在的相似之处。iForest 的主要优点在于直接孤立异常点达到异常检测的目的，从而在一定程度上缓解异常检测的掩盖和淹没效应［15］，而传统的异常检测算法通常需要针对正常数据构建模型。iForest 利用数据集中异常点“少而不同”的特点采用子采样的方法构建iTree，将数据遍历划分到iTree 的节点中，数据在iTree 中所处的深度反映了该数据的“异常”程度，因此数据点在iTree 中的深度越浅，越有可能为异常点。

iForest不需要计算距离或密度度量，也不需要构建完全的模型，且具备线性复杂度，因而能高效处理高维数据［16-17］。即使iForest 适用于高维数据集的异常检测，但由于在构建iTree 时，每次划分数据空间都是随机选取一个特征，构建完iTree 后仍有大量维度信息没有被使用，并且每个数据点对于随机选取特征的异常程度也是不同的，最终导致算法的稳定性降低［18］。基于上述问题，杨晓辉等［19］提出了基于多维度随机超平面的iForest 异常检测算法（Multi-dimensional Random Hyperplane iForest，MRH-iForest）。该算法结合滑动窗口的多粒度扫描机制，在每个维度子集上分别构建iForest，多个iForest 构造层次化集成学习异常检测模型。该模型改善了iForest 在高维数据集中异常检测精度下降和稳定性较低的缺陷，但是随着数据集维度的增加，MRH-iForest 的时间开销增量要远大于iForest。

同时，因为iForest 使用的切割平面是轴平行的，而轴平行的切割方式可能会导致隔离超平面的交叉，进而产生异常分数分布不准确的区域。Hariri 等［20］发现iForest 对于局部异常点不敏感，基于此提出了EIF，该算法可以随机生成各种角度的切割平面，有效解决了iForest 对于局部异常点不敏感的问题。但由于EIF 在构建扩展孤立树（Extended Isolation Tree，EIT）时进行了多次向量点乘运算，所以在高维数据集上其计算成本往往远大于iForest。同时因为EIF 将轴平行的孤立条件更替为使用随机斜率［21］的超平面，导致算法模型损失了一部分泛化能力。

基于上述问题，本文利用模拟退火能够有效避免算法陷入局部最优解并最终以一定概率趋于全局最优解的特性，提出一种基于模拟退火的扩展孤立森林算法SA-EIF。SA-EIF的核心思想是：

1）在集成构建EIF的过程中计算iTree之间的差异值。2棵iTree之间的差异值越大，则说明2棵iTree的关联性越小。

2）基于K 折交叉验证的方法计算iTree 的精度值。因为检测精度较低的iTree 在集成学习模型中具有相同的投票权重，因此低精度的iTree 通常会降低集成学习模型的异常检测能力。

3）基于每棵iTree 的平均差异值和检测精度构建适应度函数，最终选择部分高平均差异值和检测能力较强的iTree 构建集成学习模型［22］。这就使得SAEIF 可以在保持原有检测精度的情况下，降低构造过程中所占用的内存，减少约20%～40%的时间开销，增强了算法的泛化能力和稳定性。

1 相关工作

1.1 iForest算法

iForest是一种集成学习算法，类似于随机森林由多棵决策树组成，iForest也由多棵iTree 组成。iForest的异常检测分为2 个部分，第一个部分是训练阶段，第二个部分是评估阶段。

1.1.1 训练阶段

在iForest 的训练阶段算法步骤中，假设数据集Χ={x1，x2，…，xn}，数据的维度为d，l为iTree 的数目，随机子采样的大小为ψ，将树的深度限制设为l，一棵iTree的构造步骤如下：

Step1 从数据集中随机选取ψ个数据，组成样本子空间，作为iTree的根节点。

Step2 从样本子空间中随机选取一个特征q作为起始节点，并在该特征的值区间内随机选取划分点p。

Step3 基于划分点生成的超平面，将当前样本子空间划分为2 个部分。把样本子空间中小于划分点p的数据划分到当前节点的左子树，大于等于p的数据划分到当前节点的右子树。

Step4 在iTree 的所有左右子树中重复执Step2、Step3 来构建一棵完整的iTree，当满足终止条件时，完成对当前iTree的构建，终止条件如下：

1）节点中只包含一个数据。

2）节点上数据的所有特征值相同。

3）iTree 达到限定的最大深度l（从算法效率角度出发，限制了l=log2（ψ））。

重复上述过程，得到由L棵iTree 构成的集成学习模型［23］iForest：

1.1.2 评估阶段

在iForest的评估阶段中，每个样本数据在每棵孤立树上都能得到一个路径长度，在所有iTree上的路径长度平均值则可以作为整个iForest 对于该样本异常程度的度量指标，路径长度越小，异常的可能性越大。

定义1 路径长度。对于给定的测试数据x，路径长度为x从iTree的根节点到叶节点所经历边的数目。

定义2 异常分数。给定一个大小为ψ的样本子空间和一个样本数据x，则对于样本数据x的异常分数s定义如公式（2）所示：

其中，E（h（x））表示样本数据x在多棵iTree中路径长度的均值；c（ψ）定义为在二叉搜索树（Binary Search Tree，BST）中搜索失败的平均路径长度［24］，在此处主要起归一化的作用，其定义如公式（3）所示：

其中，H（i）=ln（i）+0.5772156649（欧拉常数），H（i）为调和级数。

1.2 EIF算法

EIF 算法使用子空间［25］的思想进行异常检测，并使用随机斜率构建孤立超平面来避免iForest 中轴平行现象导致的决策精度下降、对局部异常点不敏感等问题。

EIF 算法适合高维度的数据，与iForest 不同，EIF将轴平行的孤立条件改进为具有随机斜率和截距的孤立超平面。每一个孤立超平面由随机斜率→n和随机截距→p确定。其中，随机斜率→n∈［0，1），随机截距→p则从每个分支点的值区间内随机选取。

在确定孤立超平面后，针对数据集Χ中一个给定的数据点→x，对其划分的孤立条件如公式（4）所示：

（→x-→p）·→n≤0 （4）

如果满足公式（4），则将数据点→x划分到当前节点的左子树，否则分配到当前节点的右子树。

对于一个N维数据集，EIF 可以确定N个扩展级别。以三维空间为例，在三维空间中，当扩展等级为完全扩展（Ex 2）即扩展等级为N-1 时，孤立超平面与3 个坐标轴相交。如果将扩展等级减小1，则二维孤立超平面始终与3 个坐标轴之一平行，此时的扩展等级为1（Ex 1）。再次减小扩展等级，此时的扩展等级为0（Ex 0）。孤立超平面始终平行于2 个坐标轴。扩展等级为0时，EIF 算法等同于标准的iForest算法。每个扩展等级的孤立超平面如图1所示。

图1 三维数据集中每个扩展等级的孤立超平面

1.3 存在的问题

在决策树对单一特征的决策过程中，会出现决策边界与坐标轴平行的轴平行（axis-parallel）现象［26］。因为iForest的决策模式与决策树具有高度一致性，所以也受轴平行的影响。iForest在高维数据集中，受轴平行现象的影响会发生异常检测的掩盖和重叠效应，导致iTree 对局部异常点不敏感，决策精度降低。因此iForest仅对全局异常点敏感，且更适用于分布稀疏且连续的数据集。

针对上述问题，Hariri 等［20］提出基于随机斜率构建超平面的EIF，在一定程度上改善了iForest 对于局部异常点不敏感的问题。

随着EIF 算法扩展等级的提高，算法的偏差也会随之减小。在各个维度上数据的分布差别较大的情况下，具有多个扩展等级的EIF 相比于iForest 精度和稳定性更好。但EIF仍存在一些需要改进的问题：

1）在一些极端情况下，若存在三维数据集，但其中2 个维度的值区间比第3 个维度小得多，则该数据集本质上可能是沿一条直线分布的，此时过高的扩展等级会带来不必要的计算开销。并且在EIF的训练和评估过程中，每棵iTree节点上都需要进行1次向量减法和乘法计算。因此EIF 相比于iForest，虽然增加了对局部异常点的敏感性，但同时也增加了计算开销。

2）在EIF 中每棵iTree 的检测能力不同，但每棵iTree 的投票权重却是相同的，因此可能会有一些异常检测能力较差的iTree 会对最终的异常检测结果产生误导影响。

基于上述问题，本文提出SA-EIF异常检测算法，该算法利用模拟退火算法优化EIF 的执行效率和泛化能力。

2 基于模拟退火的EIF算法

2.1 iTree的构建

模拟退火算法起源于冶金学的固体退火原理，是基于概率的一种局部搜索算法。在1983 年被Kirkpatrick 等［27］应用于组合优化领域。模拟退火算法最终求得的最优解与算法的初解无关，因此具备一定的稳定性。同时已在理论上证明模拟退火算法能够有效避免目标算法陷入局部最优解并最终以一定概率趋于全局最优解。

在EIF 中，虽然构造每棵iTree 的方式相同，但它们用于构建所选取的训练数据集却大不相同，因此导致了每棵iTree 的检测能力不同，基于Zhou 等［28］提出的选择性集成思想：部分或许优于整体，在集成模型中，从子集中选择优秀的个体构成新的子集可能会比整体集合的效果更好。本文基于模拟退火对EIF 进行改进的思想是：针对已经训练好的iTree 集合T中，利用模拟退火算法从T中选择检测性能较好的iTree组成最优子集T′来构建EIF，从而减少构建EIF 所需的iTree数量，提高执行效率和分类精度。

给定训练集Χtrain={x1，x2，…，xψ}，如果树Ti对于Χn的预测结果与真实结果一致，则y（ψ，i）=1，预测错误则y（ψ，i）=0。L代表初次构建时iTree 的数量，ψ代表Χtrain中的样本个数。最后根据每棵iTree 对于训练集的预测结果y（ψ，i）来构建Ti与Tj之间的混淆矩阵（i∈［1，L］，j∈［1，L］），如表1所示。

表1 Ti与Tj的检测结果混淆矩阵

iTree与iTree之间的差异值Qi，j如公式（5）所示：

根据Q-统计量法，Qi，j∈［-1，1］，Qi，j差异值越大，则说明树Ti与Tj这2 棵iTree 的差异度越小。如果存在2棵iTree相互独立，则这2棵iTree的差异值为0。

其次，对于iTree 检测能力的区分，本文使用K 折交叉验证的方法来计算每棵iTree 的检测性能。首先将训练数据划分为数量相等的K份子集，每次随机使用K-1份子集构建iTree，然后使用剩余的1份子集对模型的检测性能进行测试。将K份数据分别作为测试集进行测试，最终取K次检测精度值的平均值作为该棵iTree 的精度值A。A越高则代表iTree 的检测性能越好。使用K 折交叉验证计算精度值可以更准确客观地反应iTree的检测性能。

在选取iTree 时，通常选择精度较高、差异度较大的iTree。选择差异度较大的iTree 可以更容易互补iTree 之间的不同信息，增加EIF 的泛化能力，而低精度的iTree 通常会对集成学习模型的检测结果产生误导影响，因此需要舍弃检测能力较差的iTree。

2.2 适应度函数的构建

本节综合考虑精度值和差异值来计算每棵iTree的适应度值。适应度函数如公式（6）所示：

其中，μ和λ分别表示精确度和差异值对应的权重；Ai表示参与集成的Ti对于训练集的精度值；Qi表示Ti对于其他iTree的平均差异值，其计算方法如公式（7）：

2.3 SA-EIF算法步骤

随着EIF 扩展等级的提高，EIF 对局部异常点的敏感度也会随之提升，但随之而来的是大量的计算成本。EIF 本身是一种集成学习算法，本文结合模拟退火算法对EIF进行选择性集成。

随机选择一棵iTree 作为初解，将温度t模拟为控制参数，然后从初解的邻域中根据温度t随机扰动选择一个新解，其中，算法接受Metropolis 准则，计算新解与旧解的目标函数差值，允许目标函数在可接受的概率范围内接受新解。算法重复执行“产生新解→计算目标函数差→判断是否接受新解→接受或舍弃”的迭代过程，如果满足终止条件则终止上述过程，并输出当前选择的iTree。否则，减小控制参数t的值，并重复上述过程。最终使用从T棵iTree 中选择的k棵iTree来构建EIF。具体算法步骤如下：

算法SA-EIF

输入：数据集Χ；子采样数ψ；初始iTree数量L。

Step1 设置iTree的初始参数。

Step2 构建L棵iTree组成初始EIF。

Step3 使用数据集Χtrain对参与集成的L棵iTree进行训练，基于Q-统计量法计算iTree 之间的平均差异值，再根据K折交叉验证法计算每棵iTree的精度值。

Step4 结合模拟退火算法从L棵iTree 中选出k棵检测性能较优的iTree 构建EIF。该步骤的算法流程如图2所示。

图2 SA-EIF核心算法流程图

Step4.1 初始化参数。设初始温度t=t0，结束温度为t′，Metropolis 链的长度即任意温度的迭代次数C，任取一棵iTree作为初解Ti。

Step4.2 产生新解。基于当前温度t的大小，随机扰动产生一个新解Tj。

Step4.3 计算目标函数差：Δf=F（Tj）-F（Ti）。其中，F（Ti）、F（Tj）分别为树Ti和Tj的适应度值。

Step4.4 判断是否接受新解。根据Metropolis接受准则，若Δf＜0，则接受Tj作为新的当前解；否则以概率exp接受Tj作为新的当前解，其中，k是玻尔兹曼常数。

Step4.5 判断在当前温度t下，是否达到迭代次数C，若未达到迭代次数，则返回至Step4.2。

Step4.6 当满足模拟退火算法规定的终止条件，则返回当前解为最优解。终止条件如下：

1）连续若干个Metropolis中都没有新解被采用。

2）t≤t′，即当前温度t小于等于设定的结束温度t′。

若不满足终止条件，则根据温度衰减函数缓慢降低当前温度t，并返回至Step4.2，衰减函数如公式（8）所示：

Step4.7 最终从T棵iTree 中筛选出k（k≤L）棵检测性能较优的iTree构建EIF。

Step5 对测试集Χtest使用构建的EIF 进行检测，根据实例x在每棵iTree 中的平均路径长度E（h（x））计算其异常分数S（x，ψ），对于异常分数的评估指标如下：

1）E（h（x））→n-1，S（x，ψ）→0，说明x平均路径越长，越不容易被孤立，越有可能为正常点。

2）E（h（x））→0，S（x，ψ）→1，说明x越容易被孤立，越有可能为异常点。

3）E（h（x））→c（ψ），S（x，ψ）→0.5，说明实例x的平均路径长度E（h（x））与iTree 中查找点失败的平均路径c（ψ）相近，则x可能为异常点，也可能为正常点。

此时构建EIF 的iTree 即满足高精度值和高差异度值的iTree。SA-EIF 降低了基分类器的数量，提升了EIF的执行效率和分类精度。

3 实验结果与分析

实验平台配备Intel Core i7-8750H 处理器，16 GB 内存，Windows10 操作系统，所有算法都基于Python实现。

本章使用3组实验来对SA-EIF的有效性进行综合评估，验证该算法对于EIF执行效率和精确度的提升。

3.1 实验数据与测试方法

实验数据：实验使用离群值检测数据库（Outlier Detection DataSets，ODDS）中的真实数据集，详细信息如表2 所示。这些数据集包括低维数据集和高维数据集、样本数量较少的数据集和样本数量较多的数据集。对于样本数量较少的数据集Lympho，则采用10 折交叉验证求平均值的方法进行实验，对于其他数据集则采用5折交叉验证法。

表2 ODDS异常数据集

对比算法：为了验证所提SA-ELF 算法的有效性，将实验结果与EIF、iForest、LOF，进行了对比分析。同时为了更加合理地展现对比结果，将iForest、EIF、SA-EIF 的默认参数设定为：子样本数量ψ=256，iTree 数量T=100。其中EIF 与SA-EIF 的扩展等级则设置为最高。

评估指标：针对算法预测的准确性，选用异常检测常用的评估指标AUC［29］来对算法的准确性进行检验。AUC 值越高，则说明模型的泛化能力越强，预测的准确性越高［30］。同时，分别对算法的执行效率进行评估。最终，为了更好地评价算法性能，评估了iTree参数的变化对SA-EIF 算法预测结果的影响。

3.2 准确性评估

首先，在表2所示的6个异常检测数据集上，评估了SA-EIF 的预测准确性，并与EIF、iForest、LOF 算法进行了对比分析，实验结果如表3所示。

表3展示了4种算法在检测精度上的差异。综合分析实验结果可知，SA-EIF 算法的AUC 均优于EIF，具体提升约5%。而在较小规模的数据集中，LOF 的检测精度要高于其他3种算法，SA-EIF算法的检测精度与EIF 总体上差别很小，这是因为数据集分布较为稀疏因此易于划分。而对于异常点较多的Satellite数据集，由于异常数据的增多并且分布更加密集，SAEIF 的分类效果均优于其他3 种算法。因为SA-EIF基于模拟退火选择了精度高且差异度高的iTree 构建集成学习模型，使得最终的集成分类效果更好。

表3 4种算法在不同数据集上检测的AUC值

在Arrhythmia 和Satellite 这2 种异常数据比例较高的数据集中，SA-EIF 的AUC 值要明显高于其他3种算法，说明SA-EIF 更适合应用于异常数据比例较高的数据集。

3.3 执行效率评估

本节在表2 所给数据集上评估对比了SA-EIF、EIF、iForest、LOF 算法的执行时间。实验结果如表4所示。

由表4 综合分析实验结果可知，SA-EIF 算法由于构建时舍弃了部分检测性能较差的iTree，减少了测试时的计算消耗，因此SA-EIF 在各类型数据集上的执行效率均高于EIF 算法。根据SA-EIF 构建时选择iTree 的数量，较EIF 算法减少了约20%～40%的计算成本。随着数据量的增大，因为SA-EIF 和EIF 在构建过程中会进行部分向量间运算，所以在时间开销上均劣于iForest。在高维度的数据集上，LOF 的时间开销均高于其他3 种算法，因为LOF 是一种基于密度评估的算法，数据集维度的增加会导致距离计算的时间复杂度随之增加。而其他3 种算法的孤立机制对于数据集的维数不具依赖性，在高维数据集中也具有线性的复杂度。

3.4 局部异常检测评估

本节选用的实验数据集为服从高斯分布的2 个二维数据集。左上和右下数据簇的数量均为400。将iForest 和SA-EIF 算法的异常检测能力进行对比，可以直观地看出EIF 改善了iForest 对于局部异常点不敏感的问题。

分别使用iForest 和SA-EIF 对数据集进行训练、评估的过程后，得到2 组异常分数，并将所得到的异常分数划分为10 个层次。最终2 种算法的异常分数分布等高图如图3 所示，图中颜色越深，则表明该区域的异常分数越高，分布在该区域的数据点越有可能为异常点。

iForest由于采用了轴平行的划分策略，使得异常分数等高图在数据簇的平行轴线上偏差较大，导致了异常检测的掩盖效应。如图3（a）中，iForest就可能会将左下区域和右上区域中的异常点错误地判断为正常点。而SA-EIF的异常分数等高分布图则更具层次感，更加符合原数据的分布规律，因此可以更好地检测出数据集中的局部异常点。

图3 高斯分布数据集上异常分数等高图

3.5 参数敏感性评估

本节在异常数据比例较高的Arrhythmia 数据集上评估SA-EIF 选取k棵iTree 构建EIF 的重要参数k，观察k的变化对算法预测结果的影响。

设置SA-EIF算法的默认参数T=100，子采样数ψ=256，从50 到100 变化参数k。图4 展示了SA-EIF 在数据集上随参数k变化的时间开销。而图5 展示了SA-EIF在数据集上随着参数k变化的AUC标准差。

如图4 所示，随着k值从100～50 降低，SA-EIF 算法的时间开销也随之减小，这是因为k值的降低，缩小了EIF 的构建规模，减少了算法的测试开销。分析图5 可以得出，当k值在100～80 以内时，算法的AUC标准差波动较为平稳，随着k值从80～50 缓慢减少，SA-EIF 算法的AUC 标准差逐渐增加，当k值减少至50时，此时算法的预测结果波动较大，稳定性降低。

图4 SA-EIF在不同参数k下的时间开销

图5 SA-EIF在不同参数k下AUC的标准差

由实验结果得知，SA-EIF 参数k值设置过低虽然可以大幅减少EIF 的时间开销，但会导致最终的集成学习模型不收敛、欠拟合，算法的稳定性降低。

4 结束语

本文从EIF 算法泛化能力弱、构建冗余的iTree导致算法的时间开销较大等问题入手，根据选择性集成思想提出一种基于模拟退火的扩展孤立森林算法，对构建EIF 的iTree 使用了择优再组合的集成方法。最终在ODDS 异常检测数据集中的实验结果表明，SA-ELF 算法较EIF算法提升了约5%的检测精度，减少了约30%的时间开销。同时，与iForest 相比，改善了iForest对于局部异常点检测不敏感的问题，但增加了时间开销。

此外，SA-EIF 基于EIF，所以在构建孤立超平面时无法避免使用向量间计算，因而增加了计算成本。下一步工作可以结合SA-EIF 构建时选取的iTree 具有高差异度因此耦合度较低的特点，利用分布式系统实现并行化，改善本算法的执行效率。同样可以利用多粒度扫描机制MGS 作为维数选择过程，构建层次化集成学习模型，进一步提高算法的检测精度。