改進麻雀搜索算法優(yōu)化SVM的異常點檢測*

唐 宇,代 琪,楊夢園,陳麗芳,3

(1.華北理工大學理學院，河北 唐山 063210;2.中國石油大學(北京) 自動化系,北京 102249; 3.河北省數(shù)據(jù)科學與應用重點實驗室，河北 唐山 063210)

1 引言

大數(shù)據(jù)時代，各行各業(yè)都會產(chǎn)生大量數(shù)據(jù)，因此，數(shù)據(jù)質量受到了研究人員的重點關注。由于數(shù)據(jù)的多樣性和復雜性，在一組數(shù)據(jù)點中難免會出現(xiàn)和大多數(shù)數(shù)據(jù)不同的數(shù)據(jù)點[1]，在不同領域中這些異常的數(shù)據(jù)點往往具有更大的研究價值，例如在醫(yī)療錯誤診斷[2]、云服務器故障檢測[3]和網(wǎng)絡入侵[4]等應用中異常值比正常值更具有研究價值。異常點檢測旨在從海量數(shù)據(jù)中識別出不同于一般數(shù)據(jù)的對象?，F(xiàn)如今在很多領域中對異常點的研究更有意義，因此，研究更加高效的異常點檢測算法尤為重要。

近年來元啟發(fā)式的群智能優(yōu)化算法在各個領域廣泛應用。群智能優(yōu)化算法是受到自然界中生物的群體行為啟發(fā)而提出的一類元啟發(fā)式算法。Wang等[5]提出一種改進的回溯搜索優(yōu)化算法ABSA(Advanced Backtracking Search optimization Algorithm)，該算法找到了合理的補充頻率并使整個成本最小化，為多項目聯(lián)合補充問題提供了一個很好的解決方案。Peng等[6]使用果蠅算法優(yōu)化長短記憶模型中的參數(shù)，減小模型參數(shù)對整體性能的影響，進一步提高了模型的準確性。一些研究人員提出將群體智能優(yōu)化算法應用到異常點檢測中。李春生等[1]引入屬性隸屬度的概念，簡化屬性選擇方式，通過改進的加權距離得到距離矩陣，所提算法明顯改善了異常點檢測的準確率。Cao等[7]提出了一種用于分類矩陣對象數(shù)據(jù)的異常點檢測算法，該算法根據(jù)矩陣對象之間的平均距離定義矩陣對象的耦合，并根據(jù)信息熵和互信息定義內聚，提高了異常值檢測的準確率。Jiang等[8]提出了一種局部引力方法，該方法將每個數(shù)據(jù)點都視為具有質量和局部合力的對象LRF并由其近鄰生成，然后根據(jù)該對象變化率進行排序，最終排名靠前的數(shù)據(jù)點為異常值的概率較大。Mahboobeh等[9]提出最小冗余最大相關密度法，利用局部離群因子計算子空間中的數(shù)據(jù)離散度，降低了計算復雜度,減少了運行時間。Yang等[10]提出了一種均值偏移異常值檢測器，將均值替換為每個對象的k最近鄰居，提高了異常點檢測的準確性。Farag等[11]提出了一種檢測序列數(shù)據(jù)中異常值的并行異常值檢測技術，該技術使用圖方法檢測異常值，具有靈活、快速的特點。上述研究雖然在不同程度上提升了異常點檢測效率，但文獻[6-8]都存在著高維數(shù)據(jù)難以處理的問題，文獻[9-11]存在選取屬性不夠全面的問題。

傳統(tǒng)的支持向量機SVM(Support Vector Machine)算法應用于異常點檢測時，存在分類效果差、檢測精度低的問題[12]。魏晶茹等[13]用粒子群優(yōu)化算法PSO(Particle Swarm Optimization)來優(yōu)化SVM參數(shù)并應用到異常點檢測中，該算法在一定程度上提升了分類算法的精度，但容易陷入局部最優(yōu)解，同時還存在高維空間收斂速度慢、在不同規(guī)模的數(shù)據(jù)集上自適應能力差的缺點。馬晨佩等[14]使用麻雀搜索算法SSA(Sparrow Search Algorithm)優(yōu)化SVM參數(shù)并建立故障診斷模型，有效地提高了故障診斷的準確率，但該算法還存在迭代后期容易陷入局部最優(yōu)解的問題。

針對以上問題，本文引入改進折射反向學習和可變對數(shù)螺線對麻雀搜索算法進行改進，首先使用改進的折射反向學習使發(fā)現(xiàn)者在迭代后期更容易跳出局部最優(yōu)解；再引入可變對數(shù)螺線對加入者位置更新進行優(yōu)化，使加入者尋優(yōu)的方向更具多樣性；然后使用改進的麻雀搜索算法ISSA(Improved Sparrow Search Algorithm)優(yōu)化SVM參數(shù),并構建ISSA-SVM模型用于異常點檢測；最后利用KEEL數(shù)據(jù)集進行實驗，以表明ISSA-SVM的有效性。ISSA-SVM在一定程度上改善了傳統(tǒng)分類算法在迭代后期容易陷入局部最優(yōu)解的問題，能夠快速地在最優(yōu)值附近收斂，具有很強的跳出局部極值的能力，使算法更具活力，有效地提高了算法的準確率和穩(wěn)定性。

2 相關知識

2.1 麻雀搜索算法

麻雀搜索算法是Xue等[15]根據(jù)麻雀群體在覓食過程中的一系列行為所提出的群智能優(yōu)化算法。原始麻雀搜索算法能夠迅速地在最優(yōu)值附近收斂，具有高效的全局尋優(yōu)能力和高穩(wěn)定性。麻雀搜索算法由負責覓食和為群體提供方向的發(fā)現(xiàn)者、跟隨發(fā)現(xiàn)者的加入者和時刻警惕捕食者的警戒者3部分構成。發(fā)現(xiàn)者是麻雀群體中位置最好且距離食物最近的部分；加入者會根據(jù)發(fā)現(xiàn)者進行位置更新，以提高獲取食物的概率；當警戒者發(fā)現(xiàn)捕食者時向麻雀群體發(fā)出警戒，種群中的麻雀會相互靠近以減少被捕食的概率，做出反捕食行為。

2.1.1 發(fā)現(xiàn)者數(shù)學模型

發(fā)現(xiàn)者位置更新如式(1)所示：

(1)

2.1.2 加入者數(shù)學模型

加入者位置更新如式(2)所示：

(2)

2.1.3 警戒者數(shù)學模型

警戒者位置更新如式(3)所示：

(3)

其中，Xbest是當前的全局最優(yōu)位置;β是一個服從標準正態(tài)分布的隨機數(shù);K是[-1,1]的隨機數(shù)，表示麻雀移動方向和步長控制參數(shù);fi是當前麻雀個體的適應值;fg是當前全局最優(yōu)的適應度值;fw是當前全局最差的適應度值;ε是無窮小常量，避免分母為零。

2.2 改進折射反向學習

傳統(tǒng)反向學習雖然擴大了算法的搜索范圍，但迭代后期容易陷入局部最優(yōu)解。針對這種問題，本文采用折射反向學習的方法，將光的折射原理與反向學習相結合，將當前解通過光的折射定律獲得當前解的折射反向解，有效地避免了算法陷入局部最優(yōu)解，增大了粒子的搜索范圍，提升了算法的泛化能力。折射反向學習的原理如圖1所示。

Figure 1 Principle of refraction reverse learning 圖1 折射反向學習原理

為解釋折射反向學習原理做出如下假設：x軸上下為2種不同介質，y軸為法線，粒子x∈[a,b]，O為區(qū)間[a,b]的中點。光在粒子x正上方沿線段l方向射入(l與y軸夾角為α)，經(jīng)點O發(fā)生折射，使光沿線段l′方向射出(l′與y軸夾角為β)。

由圖1中幾何關系可得式(4)：

(4)

折射率η=sinα/sinβ，令k=|l|/|l′|代入式(4)，可得折射反向學習解的公式如式(5)所示：

(5)

以第j維的第i只麻雀為例，當η=1時，可得折射反向學習解公式如式(6)所示：

(6)

通過折射反向學習得到的候選解能夠有效地使算法跳出局部最優(yōu)解。但是，在迭代后期適應度值較好的解相距較近，獲取最優(yōu)解的難度加大，本文引入超參數(shù)ω，根據(jù)迭代次數(shù)的不同對ω值進行調整，以增加解的隨機性，進而使候選解具有更好的跳出局部極值的能力，能夠更加高效地尋找最優(yōu)解。改進公式如式(7)所示：

(7)

其中，ε∈[0,1];t表示當前迭代次數(shù);T表示迭代總數(shù);xi,j表示當前迭代次數(shù)中第i只麻雀在第j維的位置，x′i,j為xi,j的折射反向解;aj表示第j維空間上的上邊界；bj表示第j維空間上的下邊界。

2.3 可變對數(shù)螺線

加入者跟隨發(fā)現(xiàn)者尋找食物，通過發(fā)現(xiàn)者更新自己的位置，因此，加入者的搜索具有盲目性。本文使用可變對數(shù)螺線更新加入者的位置。

在麻雀群體尋優(yōu)過程中，迭代初期加入者需要對盡可能大的空間進行搜索，以尋找更多高質量的解，而迭代后期只需要對小范圍的空間進行搜索，以減少時間開銷，因此本文將傳統(tǒng)對數(shù)螺線中的常量θ設為變量，使其根據(jù)迭代次數(shù)動態(tài)變化，在迭代前期保證加入者搜索范圍盡可能大，能夠提高最優(yōu)解的質量，在迭代后期麻雀搜索范圍會不斷縮小，此時，使加入者在最優(yōu)解附近進行小范圍搜索。該策略使加入者在迭代后期可以更加快速、高效地對空間進行搜索以及對位置進行更新，增加了加入者對未知領域的探索能力，提高了算法的尋優(yōu)能力[17]。應用可變對數(shù)螺線對加入者位置進行更新如式(8)和式(9)所示：

(8)

s=eθt1·cos(2πt1)

θ=k-t/T

(9)

其中，k=5[18],t1∈[-1,1]，t表示當前迭代次數(shù)，T表示迭代總數(shù)。對數(shù)螺線如圖2所示。

Figure 2 Sample diagram of logarithmic spiral圖2 對數(shù)螺線示例圖

2.4 SVM算法原理

對于數(shù)據(jù)集{xu,yu}，u=1,2,…,m，xu表示輸入向量，yu∈{-1,+1}表示類別。SVM最初是為了解決二分類問題，核心思想是找到一個優(yōu)化的超平面來區(qū)分正負樣本[19]。超平面表示如式(10)所示：

y=wTx+b

(10)

其中，w表示權重向量，b表示權重偏置。可以通過求解原始空間中的二次規(guī)劃問題來簡化求解超平面的過程，如式(11)所示：

s.tyu[(w·xu+b)]-1+ξu≥0,

u=1,…,m,ξu≥0

(11)

其中，ξ為松弛變量,ξu表示允許第u個數(shù)據(jù)點偏離的間隔，表示錯誤分類的樣本與最佳超平面之間的距離;C為懲罰因子。引入Lagrange乘子后問題轉化為對偶問題，解決了數(shù)據(jù)維數(shù)高的問題,降低了計算復雜度,如式(12)所示：

0≤αu≤C,u=1,2,…,m

(12)

在高維空間中,數(shù)據(jù)復雜度高且超平面計算難度大，此時可以利用核函數(shù)k(xu,x)=φ(xu)φ(x)來降低計算復雜度，最終在原始數(shù)據(jù)空間中求得非線性決策邊界。分類器判決函數(shù)如式(13)所示：

(13)

核函數(shù)如式(14)所示：

(14)

其中，g為核函數(shù)參數(shù)。

3 ISSA-SVM算法設計

3.1 ISSA算法思想

傳統(tǒng)麻雀搜索算法中初始麻雀數(shù)量較少，在一定的迭代次數(shù)后，群體中的麻雀會逐漸接近某個最優(yōu)解，如果上一次迭代過程中的麻雀位置不理想，那么繼續(xù)更新麻雀個體位置會影響最終結果，使得算法容易陷入局部最優(yōu)解。針對這些問題，本文引入折射反向學習，在每次迭代過后根據(jù)發(fā)現(xiàn)者的位置求出折射反向學習的候選解，然后將發(fā)現(xiàn)者的適應度值與候選解的適應度值進行比較，取出適應度值較好的麻雀作為當前迭代次數(shù)下的發(fā)現(xiàn)者，有效地提高了局部搜索能力、算法的效率及種群的多樣性[20]。傳統(tǒng)麻雀搜索算法中加入者根據(jù)發(fā)現(xiàn)者的位置進行位置更新，具有一定的盲目性，引入可變對數(shù)螺線改進加入者的位置更新方式，擴大了加入者搜索范圍，能夠獲得更多高質量的解。本文ISSA算法能夠有效地減少麻雀搜索算法陷入局部最優(yōu)解的情況，更加迅速、高效地找到最優(yōu)麻雀位置和最優(yōu)適應度值，最后通過最優(yōu)麻雀位置得到SVM的最優(yōu)參數(shù)[21]。

3.2 ISSA對SVM參數(shù)優(yōu)化

SVM中懲罰因子C和核函數(shù)參數(shù)g對模型診斷有很大的影響。懲罰因子C表示分類復雜度和分類精度之間的權衡，核函數(shù)參數(shù)g控制徑向的效應范圍，這2個參數(shù)是衡量SVM泛化能力的指標，也是影響SVM性能的主要因素[22]。傳統(tǒng)SVM對異常點的分類性能差、檢測效率低，使得異常點檢測的準確度不高。因此，本文引入改進的麻雀搜索算法優(yōu)化SVM參數(shù)，以提高算法的自適應能力。算法中麻雀個體由位置和適應度值表示，異常點檢測準確率作為ISSA-SVM優(yōu)化的目標函數(shù)。ISSA能夠避免傳統(tǒng)算法陷入局部最優(yōu)解的情況，提高了算法的效率，增強了局部搜索能力，加快了算法收斂速度。本文使用ISSA算法對SVM參數(shù)進行優(yōu)化的具體流程如下：

Step1初始化麻雀種群及相關參數(shù)；

Step2計算每只麻雀的適應度值fi，選出當前最優(yōu)位置Xb和最優(yōu)適應度值fb，選出當前最差位置Xw和最差適應度值fw；

Step3在麻雀種群中選取適應度值較好的麻雀作為發(fā)現(xiàn)者，根據(jù)式(1)更新發(fā)現(xiàn)者位置；

Step4根據(jù)式(7)得到發(fā)現(xiàn)者折射反向學習的候選解；

Step5將發(fā)現(xiàn)者和候選解的適應度值進行比較，選取適應度值較好的作為發(fā)現(xiàn)者；

Step6除發(fā)現(xiàn)者之外的麻雀作為加入者，根據(jù)式(8)更新加入者的位置；

Step7在發(fā)現(xiàn)者和加入者中隨機選取麻雀作為警戒者，根據(jù)式(3)更新警戒者位置；

Step8判斷算法運行是否達到最大迭代次數(shù)，若達到循環(huán)結束，若未達到返回Step 3；

Step9輸出全局最優(yōu)位置和最優(yōu)適應度值，得到SVM最優(yōu)參數(shù)。

整個流程如圖3所示。

Figure 3 Flowchart of ISSA-SVM algorithm圖3 ISSA-SVM算法流程圖

3.3 基于ISSA-SVM的異常點檢測算法設計

目前SVM應用在異常點檢測中難以快速有效地獲取最優(yōu)參數(shù)，導致檢測效率低、穩(wěn)定性差等問題。ISSA算法能夠快速地在高維空間中獲得最優(yōu)解，可以通過最優(yōu)麻雀位置得到SVM的最優(yōu)參數(shù)。使用改進的麻雀搜索算法優(yōu)化支持向量機參數(shù)，增強異常點檢測算法的自學習和自適應能力，提高異常點檢測的準確率[23]?；贗SSA-SVM的異常點檢測算法流程如下所示：

Step1收集包含異常點的數(shù)據(jù)集；

Step2將收集的數(shù)據(jù)集作為SVM的訓練樣本；

Step3通過ISSA算法獲得SVM的最優(yōu)參數(shù)；

Step4利用獲取的SVM最優(yōu)參數(shù)對訓練集進行訓練，建立ISSA-SVM異常點檢測模型；

Step5使用ISSA-SVM異常點檢測模型對測試集進行測試；

Step6輸出異常點檢測結果。

ISSA-SVM及其對比算法用于檢測異常點的整個流程如圖4所示。

Figure 4 Flowchart of ISSA-SVM algorithm and compared algorithms圖4 ISSA-SVM算法及對比算法流程圖

4 仿真實驗與結果分析

4.1 實驗環(huán)境與數(shù)據(jù)集

實驗環(huán)境：軟件為Matlab,操作系統(tǒng)為Windows 10家庭中文版,CPU為AMD R7-4800,內存為16 GB。

本文主要使用KEEL數(shù)據(jù)庫中的12個數(shù)據(jù)集進行仿真實驗。在實驗過程中，把所有數(shù)據(jù)集中的少數(shù)類樣本看作異常數(shù)據(jù)，多數(shù)類樣本看作正常數(shù)據(jù)，所有數(shù)據(jù)集都是80%用于訓練，20%用于測試，并且數(shù)據(jù)隨機劃分。實驗所用數(shù)據(jù)集信息如表1所示。

Table 1 Information about the data sets表1 數(shù)據(jù)集基本信息

4.2 實驗結果及分析

為了驗證ISSA優(yōu)化SVM參數(shù)的有效性，將本文算法ISSA-SVM與傳統(tǒng)的支持向量機SVM、粒子群優(yōu)化算法優(yōu)化的支持向量機PSO-SVM和麻雀搜索算法優(yōu)化支持向量機SSA-SVM進行對比。實驗中SSA-SVM和ISSA-SVM參考文獻[22]將最優(yōu)麻雀數(shù)量設置為30，最大迭代次數(shù)設置為100。PSO-SVM參考文獻[13]中的最優(yōu)參數(shù)，即粒子數(shù)量設置為20，最大迭代次數(shù)設置為200。為保證實驗的準確性，采用五折交叉驗證，以F-measure和G-mean2個指標[24]的標準差值作為評價指標。2個評價指標值越高,異常點檢測效果越好。各評價指標中最優(yōu)結果已進行加粗處理。

F-measure計算公式如式(15)所示：

(15)

其中，精確度P=TP/(TP+FP)，召回率R=TP/(TP+FN)，TP為少數(shù)類樣本正確分類的樣本數(shù)目，F(xiàn)N為少數(shù)類樣本錯誤分類的樣本數(shù)目,FP為多數(shù)類樣本錯誤分類的樣本數(shù)目[25]。

G-mean值計算公式如式(16)所示：

(16)

其中，TPR=TP/(TP+FN)，為少數(shù)類樣本中預測正確樣本數(shù)量占實際少數(shù)類樣本數(shù)量的比例；TNR=TN/(FP+TN)，為多數(shù)類樣本中預測正確樣本數(shù)量占實際多數(shù)類樣本的比例[26]。

表2為各優(yōu)化分類算法的G-mean值。從表2可以看出，本文算法在ecoli1、ecoli2、Glass6、wisconsin、vehicle2、pima、newthyroid2、Iris0、ionosphere和wbc 10個數(shù)據(jù)集上的異常點檢測效果明顯高于其它3種分類算法的；在數(shù)據(jù)量相對較大的2個數(shù)據(jù)集vehicle2和pima上，本文算法的檢測效果更加有優(yōu)勢;在ecoli1和vehicle0數(shù)據(jù)集上,PSO-SVM算法優(yōu)于其它3種分類算法，本文算法為次優(yōu)分類算法且與PSO-SVM的G-mean值相差較小;在new-thyroid數(shù)據(jù)集上，SSA-SVM算法的分類效果最好，本文算法為次優(yōu)算法;在Glass6和wbc數(shù)據(jù)集上，實際異常點數(shù)量較少，本文算法檢測效率依然很高，G-mean值明顯優(yōu)于其它3種優(yōu)化分類算法，說明異常點占比情況對本文算法的影響較小?？傊疚乃惴ㄔ诓煌臄?shù)據(jù)集上都有較高的檢測效率。

Table 2 G-mean value of each algorithm表2 各算法的G-mean值

標準差均值是衡量算法效果和穩(wěn)定性的又一重要指標，標準差越小，算法穩(wěn)定性越好，反之穩(wěn)定性越差。圖5為各優(yōu)化分類算法的標準差均值。從圖5可以看出，相比于其他分類算法，本文算法在異常點檢測數(shù)據(jù)集上整體穩(wěn)定性更好。

Figure 5 Mean standard deviation of G-mean of each algorithm圖5 各算法G-mean的標準差值

表3為各優(yōu)化分類算法的F-measure值。從表3可以看出，在ecoli1、ecoli2、Glass6、wisconsin、vehicle0、vehicle2、newthyroid2、Iris0、wbc和ionosphere 10個數(shù)據(jù)集上，本文算法的異常點檢測效果優(yōu)于其它3種優(yōu)化分類算法的;在數(shù)據(jù)集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(xiàn)-measure值平衡了精確度和召回率之間的影響。通過對比表2中各優(yōu)化分類算法的G-mean值可以看出，當G-mean值較大時，F(xiàn)-measure值有可能偏低。

圖6為各優(yōu)化分類算法的標準差均值。從圖6可以看出，在此評價指標下本文算法的標準差均值最小為0.093，低于SVM、PSO-SVM和SSA-SVM的標準差均值0.288,0.107和0.158，說明本文算法具有較好的穩(wěn)定性,且明顯優(yōu)于其它3種優(yōu)化分類算法。

Figure 6 Mean standard deviation of F-measure of each algorithm圖6 各算法F-measure的標準差值

綜合分析各分類算法可以得出，傳統(tǒng)的SVM分類算法更適用于數(shù)據(jù)量較小、異常點占比更大的數(shù)據(jù)集，SVM分類算法在解決異常點數(shù)量較小的數(shù)據(jù)集時分類效果并不顯著；PSO-SVM分類算法能夠更好地改善傳統(tǒng)SVM的分類問題，并在檢測效率上有所提升，但是異常點檢測的準確率還有待進一步提升[23]；SSA-SVM分類算法更好地解決了許多傳統(tǒng)異常點檢測中的檢測效率低、穩(wěn)定性差等問題，但該分類算法在本文的評價指標G-mean值和F-measure值上還需要進一步改進;本文算法在G-mean值和F-measure值2個評價指標上優(yōu)化效果更為顯著，在少數(shù)數(shù)據(jù)集上雖然各個分類算法各有優(yōu)勢，但本文算法均值最高且標準差均值最小，足以表明本文算法檢測異常點的能力以及算法的穩(wěn)定度；本文算法在大部分數(shù)據(jù)集上檢測效率和穩(wěn)定性都要優(yōu)于其它3種優(yōu)化分類算法，在數(shù)據(jù)量不同、異常點占比情況不同的數(shù)據(jù)集上，本文算法都表現(xiàn)出了更高的準確率、更好的穩(wěn)定性及更強的泛化能力。

5 結束語

本文提出改進麻雀搜索算法優(yōu)化SVM的異常點檢測算法，在麻雀搜索算法的發(fā)現(xiàn)者中引入折射反向學習，以提高算法在迭代后期跳出局部最優(yōu)解的能力；在加入者中引入可變對數(shù)螺線,在迭代前期擴大了加入者的搜索范圍，在迭代后期加快了搜索最優(yōu)解的速度，提高了解的質量。實驗結果表明，與SVM、PSO-SVM和SSA-SVM 3種算法相比，ISSA-SVM能夠有效地提升異常點檢測的準確率，增強算法的穩(wěn)定性，提高算法的分類性能。未來研究工作的重點在于探索更加快速、高效的智能優(yōu)化算法，并將其應用于異常點檢測或數(shù)據(jù)挖掘等相關任務中。