唐 宇,代 琪,杨梦园,陈丽芳,3
(1.华北理工大学理学院，河北 唐山 063210;2.中国石油大学(北京) 自动化系,北京 102249; 3.河北省数据科学与应用重点实验室，河北 唐山 063210)
大数据时代，各行各业都会产生大量数据，因此，数据质量受到了研究人员的重点关注。由于数据的多样性和复杂性，在一组数据点中难免会出现和大多数数据不同的数据点[1]，在不同领域中这些异常的数据点往往具有更大的研究价值，例如在医疗错误诊断[2]、云服务器故障检测[3]和网络入侵[4]等应用中异常值比正常值更具有研究价值。异常点检测旨在从海量数据中识别出不同于一般数据的对象。现如今在很多领域中对异常点的研究更有意义，因此，研究更加高效的异常点检测算法尤为重要。
近年来元启发式的群智能优化算法在各个领域广泛应用。群智能优化算法是受到自然界中生物的群体行为启发而提出的一类元启发式算法。Wang等[5]提出一种改进的回溯搜索优化算法ABSA(Advanced Backtracking Search optimization Algorithm)，该算法找到了合理的补充频率并使整个成本最小化，为多项目联合补充问题提供了一个很好的解决方案。Peng等[6]使用果蝇算法优化长短记忆模型中的参数，减小模型参数对整体性能的影响，进一步提高了模型的准确性。一些研究人员提出将群体智能优化算法应用到异常点检测中。李春生等[1]引入属性隶属度的概念，简化属性选择方式，通过改进的加权距离得到距离矩阵，所提算法明显改善了异常点检测的准确率。Cao等[7]提出了一种用于分类矩阵对象数据的异常点检测算法，该算法根据矩阵对象之间的平均距离定义矩阵对象的耦合，并根据信息熵和互信息定义内聚，提高了异常值检测的准确率。Jiang等[8]提出了一种局部引力方法，该方法将每个数据点都视为具有质量和局部合力的对象LRF并由其近邻生成，然后根据该对象变化率进行排序，最终排名靠前的数据点为异常值的概率较大。Mahboobeh等[9]提出最小冗余最大相关密度法，利用局部离群因子计算子空间中的数据离散度，降低了计算复杂度,减少了运行时间。Yang等[10]提出了一种均值偏移异常值检测器，将均值替换为每个对象的k最近邻居，提高了异常点检测的准确性。Farag等[11]提出了一种检测序列数据中异常值的并行异常值检测技术，该技术使用图方法检测异常值，具有灵活、快速的特点。上述研究虽然在不同程度上提升了异常点检测效率，但文献[6-8]都存在着高维数据难以处理的问题，文献[9-11]存在选取属性不够全面的问题。
传统的支持向量机SVM(Support Vector Machine)算法应用于异常点检测时，存在分类效果差、检测精度低的问题[12]。魏晶茹等[13]用粒子群优化算法PSO(Particle Swarm Optimization)来优化SVM参数并应用到异常点检测中，该算法在一定程度上提升了分类算法的精度，但容易陷入局部最优解，同时还存在高维空间收敛速度慢、在不同规模的数据集上自适应能力差的缺点。马晨佩等[14]使用麻雀搜索算法SSA(Sparrow Search Algorithm)优化SVM参数并建立故障诊断模型，有效地提高了故障诊断的准确率，但该算法还存在迭代后期容易陷入局部最优解的问题。
针对以上问题，本文引入改进折射反向学习和可变对数螺线对麻雀搜索算法进行改进，首先使用改进的折射反向学习使发现者在迭代后期更容易跳出局部最优解；
再引入可变对数螺线对加入者位置更新进行优化，使加入者寻优的方向更具多样性；
然后使用改进的麻雀搜索算法ISSA(Improved Sparrow Search Algorithm)优化SVM参数,并构建ISSA-SVM模型用于异常点检测；
最后利用KEEL数据集进行实验，以表明ISSA-SVM的有效性。ISSA-SVM在一定程度上改善了传统分类算法在迭代后期容易陷入局部最优解的问题，能够快速地在最优值附近收敛，具有很强的跳出局部极值的能力，使算法更具活力，有效地提高了算法的准确率和稳定性。
2.1 麻雀搜索算法
麻雀搜索算法是Xue等[15]根据麻雀群体在觅食过程中的一系列行为所提出的群智能优化算法。原始麻雀搜索算法能够迅速地在最优值附近收敛，具有高效的全局寻优能力和高稳定性。麻雀搜索算法由负责觅食和为群体提供方向的发现者、跟随发现者的加入者和时刻警惕捕食者的警戒者3部分构成。发现者是麻雀群体中位置最好且距离食物最近的部分；
加入者会根据发现者进行位置更新，以提高获取食物的概率；
当警戒者发现捕食者时向麻雀群体发出警戒，种群中的麻雀会相互靠近以减少被捕食的概率，做出反捕食行为。
2.1.1 发现者数学模型
发现者位置更新如式(1)所示：
(1)
2.1.2 加入者数学模型
加入者位置更新如式(2)所示：
(2)
2.1.3 警戒者数学模型
警戒者位置更新如式(3)所示：
(3)
其中，Xbest是当前的全局最优位置;β是一个服从标准正态分布的随机数;K是[-1,1]的随机数，表示麻雀移动方向和步长控制参数;fi是当前麻雀个体的适应值;fg是当前全局最优的适应度值;fw是当前全局最差的适应度值;ε是无穷小常量，避免分母为零。
2.2 改进折射反向学习
传统反向学习虽然扩大了算法的搜索范围，但迭代后期容易陷入局部最优解。针对这种问题，本文采用折射反向学习的方法，将光的折射原理与反向学习相结合，将当前解通过光的折射定律获得当前解的折射反向解，有效地避免了算法陷入局部最优解，增大了粒子的搜索范围，提升了算法的泛化能力。折射反向学习的原理如图1所示。
Figure 1 Principle of refraction reverse learning 图1 折射反向学习原理
为解释折射反向学习原理做出如下假设：x轴上下为2种不同介质，y轴为法线，粒子x∈[a,b]，O为区间[a,b]的中点。光在粒子x正上方沿线段l方向射入(l与y轴夹角为α)，经点O发生折射，使光沿线段l′方向射出(l′与y轴夹角为β)。
由图1中几何关系可得式(4)：
(4)
折射率η=sinα/sinβ，令k=|l|/|l′|代入式(4)，可得折射反向学习解的公式如式(5)所示：
(5)
以第j维的第i只麻雀为例，当η=1时，可得折射反向学习解公式如式(6)所示：
(6)
通过折射反向学习得到的候选解能够有效地使算法跳出局部最优解。但是，在迭代后期适应度值较好的解相距较近，获取最优解的难度加大，本文引入超参数ω，根据迭代次数的不同对ω值进行调整，以增加解的随机性，进而使候选解具有更好的跳出局部极值的能力，能够更加高效地寻找最优解。改进公式如式(7)所示：
(7)
其中，ε∈[0,1];t表示当前迭代次数;T表示迭代总数;xi,j表示当前迭代次数中第i只麻雀在第j维的位置，x′i,j为xi,j的折射反向解;aj表示第j维空间上的上边界；
bj表示第j维空间上的下边界。
2.3 可变对数螺线
加入者跟随发现者寻找食物，通过发现者更新自己的位置，因此，加入者的搜索具有盲目性。本文使用可变对数螺线更新加入者的位置。
在麻雀群体寻优过程中，迭代初期加入者需要对尽可能大的空间进行搜索，以寻找更多高质量的解，而迭代后期只需要对小范围的空间进行搜索，以减少时间开销，因此本文将传统对数螺线中的常量θ设为变量，使其根据迭代次数动态变化，在迭代前期保证加入者搜索范围尽可能大，能够提高最优解的质量，在迭代后期麻雀搜索范围会不断缩小，此时，使加入者在最优解附近进行小范围搜索。该策略使加入者在迭代后期可以更加快速、高效地对空间进行搜索以及对位置进行更新，增加了加入者对未知领域的探索能力，提高了算法的寻优能力[17]。应用可变对数螺线对加入者位置进行更新如式(8)和式(9)所示：
(8)
s=eθt1·cos(2πt1)
θ=k-t/T
(9)
其中，k=5[18],t1∈[-1,1]，t表示当前迭代次数，T表示迭代总数。对数螺线如图2所示。
Figure 2 Sample diagram of logarithmic spiral图2 对数螺线示例图
2.4 SVM算法原理
对于数据集{xu,yu}，u=1,2,…,m，xu表示输入向量，yu∈{-1,+1}表示类别。SVM最初是为了解决二分类问题，核心思想是找到一个优化的超平面来区分正负样本[19]。超平面表示如式(10)所示：
y=wTx+b
(10)
其中，w表示权重向量，b表示权重偏置。可以通过求解原始空间中的二次规划问题来简化求解超平面的过程，如式(11)所示：
s.tyu[(w·xu+b)]-1+ξu≥0,
u=1,…,m,ξu≥0
(11)
其中，ξ为松弛变量,ξu表示允许第u个数据点偏离的间隔，表示错误分类的样本与最佳超平面之间的距离;C为惩罚因子。引入Lagrange乘子后问题转化为对偶问题，解决了数据维数高的问题,降低了计算复杂度,如式(12)所示：
0≤αu≤C,u=1,2,…,m
(12)
在高维空间中,数据复杂度高且超平面计算难度大，此时可以利用核函数k(xu,x)=φ(xu)φ(x)来降低计算复杂度，最终在原始数据空间中求得非线性决策边界。分类器判决函数如式(13)所示：
(13)
核函数如式(14)所示：
(14)
其中，g为核函数参数。
3.1 ISSA算法思想
传统麻雀搜索算法中初始麻雀数量较少，在一定的迭代次数后，群体中的麻雀会逐渐接近某个最优解，如果上一次迭代过程中的麻雀位置不理想，那么继续更新麻雀个体位置会影响最终结果，使得算法容易陷入局部最优解。针对这些问题，本文引入折射反向学习，在每次迭代过后根据发现者的位置求出折射反向学习的候选解，然后将发现者的适应度值与候选解的适应度值进行比较，取出适应度值较好的麻雀作为当前迭代次数下的发现者，有效地提高了局部搜索能力、算法的效率及种群的多样性[20]。传统麻雀搜索算法中加入者根据发现者的位置进行位置更新，具有一定的盲目性，引入可变对数螺线改进加入者的位置更新方式，扩大了加入者搜索范围，能够获得更多高质量的解。本文ISSA算法能够有效地减少麻雀搜索算法陷入局部最优解的情况，更加迅速、高效地找到最优麻雀位置和最优适应度值，最后通过最优麻雀位置得到SVM的最优参数[21]。
3.2 ISSA对SVM参数优化
SVM中惩罚因子C和核函数参数g对模型诊断有很大的影响。惩罚因子C表示分类复杂度和分类精度之间的权衡，核函数参数g控制径向的效应范围，这2个参数是衡量SVM泛化能力的指标，也是影响SVM性能的主要因素[22]。传统SVM对异常点的分类性能差、检测效率低，使得异常点检测的准确度不高。因此，本文引入改进的麻雀搜索算法优化SVM参数，以提高算法的自适应能力。算法中麻雀个体由位置和适应度值表示，异常点检测准确率作为ISSA-SVM优化的目标函数。ISSA能够避免传统算法陷入局部最优解的情况，提高了算法的效率，增强了局部搜索能力，加快了算法收敛速度。本文使用ISSA算法对SVM参数进行优化的具体流程如下：
Step1初始化麻雀种群及相关参数；
Step2计算每只麻雀的适应度值fi，选出当前最优位置Xb和最优适应度值fb，选出当前最差位置Xw和最差适应度值fw；
Step3在麻雀种群中选取适应度值较好的麻雀作为发现者，根据式(1)更新发现者位置；
Step4根据式(7)得到发现者折射反向学习的候选解；
Step5将发现者和候选解的适应度值进行比较，选取适应度值较好的作为发现者；
Step6除发现者之外的麻雀作为加入者，根据式(8)更新加入者的位置；
Step7在发现者和加入者中随机选取麻雀作为警戒者，根据式(3)更新警戒者位置；
Step8判断算法运行是否达到最大迭代次数，若达到循环结束，若未达到返回Step 3；
Step9输出全局最优位置和最优适应度值，得到SVM最优参数。
整个流程如图3所示。
Figure 3 Flowchart of ISSA-SVM algorithm图3 ISSA-SVM算法流程图
3.3 基于ISSA-SVM的异常点检测算法设计
目前SVM应用在异常点检测中难以快速有效地获取最优参数，导致检测效率低、稳定性差等问题。ISSA算法能够快速地在高维空间中获得最优解，可以通过最优麻雀位置得到SVM的最优参数。使用改进的麻雀搜索算法优化支持向量机参数，增强异常点检测算法的自学习和自适应能力，提高异常点检测的准确率[23]。基于ISSA-SVM的异常点检测算法流程如下所示：
Step1收集包含异常点的数据集；
Step2将收集的数据集作为SVM的训练样本；
Step3通过ISSA算法获得SVM的最优参数；
Step4利用获取的SVM最优参数对训练集进行训练，建立ISSA-SVM异常点检测模型；
Step5使用ISSA-SVM异常点检测模型对测试集进行测试；
Step6输出异常点检测结果。
ISSA-SVM及其对比算法用于检测异常点的整个流程如图4所示。
Figure 4 Flowchart of ISSA-SVM algorithm and compared algorithms图4 ISSA-SVM算法及对比算法流程图
4.1 实验环境与数据集
实验环境：软件为Matlab,操作系统为Windows 10家庭中文版,CPU为AMD R7-4800,内存为16 GB。
本文主要使用KEEL数据库中的12个数据集进行仿真实验。在实验过程中，把所有数据集中的少数类样本看作异常数据，多数类样本看作正常数据，所有数据集都是80%用于训练，20%用于测试，并且数据随机划分。实验所用数据集信息如表1所示。
Table 1 Information about the data sets表1 数据集基本信息
4.2 实验结果及分析
为了验证ISSA优化SVM参数的有效性，将本文算法ISSA-SVM与传统的支持向量机SVM、粒子群优化算法优化的支持向量机PSO-SVM和麻雀搜索算法优化支持向量机SSA-SVM进行对比。实验中SSA-SVM和ISSA-SVM参考文献[22]将最优麻雀数量设置为30，最大迭代次数设置为100。PSO-SVM参考文献[13]中的最优参数，即粒子数量设置为20，最大迭代次数设置为200。为保证实验的准确性，采用五折交叉验证，以F-measure和G-mean2个指标[24]的标准差值作为评价指标。2个评价指标值越高,异常点检测效果越好。各评价指标中最优结果已进行加粗处理。
F-measure计算公式如式(15)所示：
(15)
其中，精确度P=TP/(TP+FP)，召回率R=TP/(TP+FN)，TP为少数类样本正确分类的样本数目，FN为少数类样本错误分类的样本数目,FP为多数类样本错误分类的样本数目[25]。
G-mean值计算公式如式(16)所示：
(16)
其中，TPR=TP/(TP+FN)，为少数类样本中预测正确样本数量占实际少数类样本数量的比例；
TNR=TN/(FP+TN)，为多数类样本中预测正确样本数量占实际多数类样本的比例[26]。
表2为各优化分类算法的G-mean值。从表2可以看出，本文算法在ecoli1、ecoli2、Glass6、wisconsin、vehicle2、pima、newthyroid2、Iris0、ionosphere和wbc 10个数据集上的异常点检测效果明显高于其它3种分类算法的；
在数据量相对较大的2个数据集vehicle2和pima上，本文算法的检测效果更加有优势;在ecoli1和vehicle0数据集上,PSO-SVM算法优于其它3种分类算法，本文算法为次优分类算法且与PSO-SVM的G-mean值相差较小;在new-thyroid数据集上，SSA-SVM算法的分类效果最好，本文算法为次优算法;在Glass6和wbc数据集上，实际异常点数量较少，本文算法检测效率依然很高，G-mean值明显优于其它3种优化分类算法，说明异常点占比情况对本文算法的影响较小。总之，本文算法在不同的数据集上都有较高的检测效率。
Table 2 G-mean value of each algorithm表2 各算法的G-mean值
标准差均值是衡量算法效果和稳定性的又一重要指标，标准差越小，算法稳定性越好，反之稳定性越差。图5为各优化分类算法的标准差均值。从图5可以看出，相比于其他分类算法，本文算法在异常点检测数据集上整体稳定性更好。
Figure 5 Mean standard deviation of G-mean of each algorithm图5 各算法G-mean的标准差值
表3为各优化分类算法的F-measure值。从表3可以看出，在ecoli1、ecoli2、Glass6、wisconsin、vehicle0、vehicle2、newthyroid2、Iris0、wbc和ionosphere 10个数据集上，本文算法的异常点检测效果优于其它3种优化分类算法的;在数据集pima和new-thyroid上,SSA-SVM的F-measure值更好，而本文算法的F-measure值次之；
整体结果表明,ISSA-SVM算法具有良好的适用性。
Table 3 F-measure value of each algorithm 表3 各算法的F-measure值
F-measure值与G-mean值不同，F-measure值平衡了精确度和召回率之间的影响。通过对比表2中各优化分类算法的G-mean值可以看出，当G-mean值较大时，F-measure值有可能偏低。
图6为各优化分类算法的标准差均值。从图6可以看出，在此评价指标下本文算法的标准差均值最小为0.093，低于SVM、PSO-SVM和SSA-SVM的标准差均值0.288,0.107和0.158，说明本文算法具有较好的稳定性,且明显优于其它3种优化分类算法。
Figure 6 Mean standard deviation of F-measure of each algorithm图6 各算法F-measure的标准差值
综合分析各分类算法可以得出，传统的SVM分类算法更适用于数据量较小、异常点占比更大的数据集，SVM分类算法在解决异常点数量较小的数据集时分类效果并不显著；
PSO-SVM分类算法能够更好地改善传统SVM的分类问题，并在检测效率上有所提升，但是异常点检测的准确率还有待进一步提升[23]；
SSA-SVM分类算法更好地解决了许多传统异常点检测中的检测效率低、稳定性差等问题，但该分类算法在本文的评价指标G-mean值和F-measure值上还需要进一步改进;本文算法在G-mean值和F-measure值2个评价指标上优化效果更为显著，在少数数据集上虽然各个分类算法各有优势，但本文算法均值最高且标准差均值最小，足以表明本文算法检测异常点的能力以及算法的稳定度；
本文算法在大部分数据集上检测效率和稳定性都要优于其它3种优化分类算法，在数据量不同、异常点占比情况不同的数据集上，本文算法都表现出了更高的准确率、更好的稳定性及更强的泛化能力。
本文提出改进麻雀搜索算法优化SVM的异常点检测算法，在麻雀搜索算法的发现者中引入折射反向学习，以提高算法在迭代后期跳出局部最优解的能力；
在加入者中引入可变对数螺线,在迭代前期扩大了加入者的搜索范围，在迭代后期加快了搜索最优解的速度，提高了解的质量。实验结果表明，与SVM、PSO-SVM和SSA-SVM 3种算法相比，ISSA-SVM能够有效地提升异常点检测的准确率，增强算法的稳定性，提高算法的分类性能。未来研究工作的重点在于探索更加快速、高效的智能优化算法，并将其应用于异常点检测或数据挖掘等相关任务中。