螢火蟲優(yōu)化和隨機(jī)森林的WSN異常數(shù)據(jù)檢測(cè)*

許歐陽，李光輝,2,3+

1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122

2.江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，南京 210003

3.物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程技術(shù)研究中心，江蘇 無錫 214122

1 引言

無線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）的構(gòu)成單元是大量低成本、微型的傳感器節(jié)點(diǎn)，可以感知網(wǎng)絡(luò)部署區(qū)域內(nèi)的各種數(shù)據(jù)信息，進(jìn)行數(shù)據(jù)樣本的采集、處理以及傳輸，特別適宜于無人值守或惡劣環(huán)境的監(jiān)測(cè)。WSN目前在許多領(lǐng)域都有所應(yīng)用，如工業(yè)控制、智慧農(nóng)業(yè)、醫(yī)療監(jiān)測(cè)、基礎(chǔ)設(shè)施健康檢測(cè)以及環(huán)境監(jiān)測(cè)等。然而，節(jié)點(diǎn)自身的軟硬件故障、電量耗盡或者部署環(huán)境遭遇突發(fā)事件（如強(qiáng)降雨、森林火災(zāi)或者危險(xiǎn)品泄漏）等因素常常導(dǎo)致節(jié)點(diǎn)采集的數(shù)據(jù)明顯地偏離正常數(shù)據(jù)形態(tài)。這類數(shù)據(jù)稱為離群數(shù)據(jù)或異常數(shù)據(jù)。及時(shí)準(zhǔn)確地檢測(cè)出傳感器數(shù)據(jù)流中的異常數(shù)據(jù)，不論是對(duì)于外部事件的實(shí)時(shí)監(jiān)測(cè)還是無線傳感器網(wǎng)絡(luò)本身健康狀態(tài)的監(jiān)測(cè)都具有十分重要的意義。

近年來國(guó)內(nèi)外對(duì)于WSN異常數(shù)據(jù)檢測(cè)方法的研究已有諸多成果[1-4]。WSN異常數(shù)據(jù)檢測(cè)方法大致可以分為5類：基于統(tǒng)計(jì)的方法、基于最近鄰的方法、基于聚類的方法、基于分類的方法以及基于頻譜分析的方法[5]。姜旭寶等人[6]提出了一種基于變寬直方圖的數(shù)據(jù)異常檢測(cè)算法，將動(dòng)態(tài)感知數(shù)據(jù)以數(shù)據(jù)融合的方式聚合成為變寬的直方圖并執(zhí)行檢測(cè)過程，該方法可以避免不必要的數(shù)據(jù)傳輸耗費(fèi)。實(shí)驗(yàn)表明該方法在擁有較好檢測(cè)性能的同時(shí)降低了通信開銷。文獻(xiàn)[7]提出批處理式的1/4超球面支持向量機(jī)異常檢測(cè)算法，超球面支持向量機(jī)訓(xùn)練速度快，支持向量少。該檢測(cè)方式需要每一個(gè)子節(jié)點(diǎn)將采集的數(shù)據(jù)通信傳給父節(jié)點(diǎn)，然后集中在父節(jié)點(diǎn)執(zhí)行異常檢測(cè)算法，節(jié)點(diǎn)間要進(jìn)行大量數(shù)據(jù)的傳輸，資源耗費(fèi)較大。于是Rajasegarar等人[8]通過分布式的超球面支持向量機(jī)對(duì)傳感數(shù)據(jù)進(jìn)行檢測(cè)，在每個(gè)子節(jié)點(diǎn)和父節(jié)點(diǎn)上分別執(zhí)行局部異常檢測(cè)，然后子節(jié)點(diǎn)僅需將它們的局部半徑傳給父節(jié)點(diǎn)，父節(jié)點(diǎn)計(jì)算得到全局半徑，接下來在子節(jié)點(diǎn)上用全局半徑執(zhí)行異常檢測(cè)，大大降低了花費(fèi)在節(jié)點(diǎn)通信的資源，檢測(cè)效率因而得到提高。以上3種方法都在資源耗費(fèi)方面做了工作，但在檢測(cè)精度方面以及模型自適應(yīng)方面還有待提高。Zhang等人在文獻(xiàn)[9]中利用超球面支持向量機(jī)（sup-port vector machine，SVM）在WSN中執(zhí)行在線異常檢測(cè)，提出了自適應(yīng)離群檢測(cè)技術(shù)（adaptive outlier detection，AOD），并實(shí)現(xiàn)了在短時(shí)間內(nèi)對(duì)所收集到的數(shù)據(jù)的狀況進(jìn)行判斷，不同于文獻(xiàn)[7]中的批處理技術(shù)，其體現(xiàn)了實(shí)時(shí)的特點(diǎn)，但對(duì)模型的構(gòu)建未考慮集成思想，后續(xù)更新會(huì)使得未來的模型適應(yīng)度不夠強(qiáng)。Hill等人在文獻(xiàn)[10]中提出了在流數(shù)據(jù)中用多層感知器作為預(yù)測(cè)器得到下一時(shí)刻測(cè)量值的預(yù)測(cè)值，并以預(yù)測(cè)值和模型殘差等參數(shù)計(jì)算預(yù)測(cè)區(qū)間（prediction interval，PI），通過比較實(shí)際值與PI的關(guān)系進(jìn)行異常檢測(cè)。該方法在異常數(shù)據(jù)相對(duì)較少的情況下性能理想，一旦連續(xù)出現(xiàn)較多異常值，模型的精度會(huì)受影響。

Zhou等人[11]提出了“部分或許優(yōu)于整體”的選擇性集成（selective ensemble，SEN）思想并將其用在了神經(jīng)網(wǎng)絡(luò)上，只在集成模型中選取部分精度高，差異度大的基分類器，得到至少不亞于原始模型的性能;丁智國(guó)等人[12]基于SEN使用生物地理學(xué)優(yōu)化算法（biogeography-based optimization，BBO）實(shí)現(xiàn)了對(duì)集成的剪枝，用較少的個(gè)體分類器獲得和原始集成相同，甚至更好的泛化性能，同時(shí)降低系統(tǒng)的存儲(chǔ)和計(jì)算開銷。該方法是SEN的應(yīng)用，但在基分類器的選取以及選擇性集成優(yōu)化算法方面有待改進(jìn)。

隨機(jī)森林（random forest，RF）模型訓(xùn)練時(shí)采用隨機(jī)采樣，有泛化能力強(qiáng)，模型方差小等優(yōu)點(diǎn)。因此，本文結(jié)合RF與SEN思想，提出了一種基于MBGSO優(yōu)化RF的WSN異常檢測(cè)算法，該算法在BGSO中引入變異機(jī)制，使得它較BGSO有著更好的尋優(yōu)能力，該算法可應(yīng)用于特征選擇算法以及集成分類器的規(guī)模縮減中，ARF（adaptive updating random forest）則在目標(biāo)分類檢測(cè)領(lǐng)域應(yīng)用較多，且在檢測(cè)過程添加了模型更新機(jī)制，可隨時(shí)間的推移執(zhí)行模型自適應(yīng)更新，比原始RF模型更加適應(yīng)當(dāng)前數(shù)據(jù)。因此，檢測(cè)效率和準(zhǔn)確性均有提高。將以上兩者相結(jié)合，由于優(yōu)化算法對(duì)集成規(guī)模大小的縮減，使得檢測(cè)算法應(yīng)用在WSN數(shù)據(jù)異常檢測(cè)中所耗費(fèi)的時(shí)間更少。

2 預(yù)備知識(shí)

2.1 決策樹與隨機(jī)森林

決策樹（decision tree）是一種簡(jiǎn)單并廣泛使用的分類器，RF中以CART（classification and regression tree）作為基分類器，并結(jié)合了Bagging思想[13]和隨機(jī)特征子空間，集成所有子分類器，Breiman在文獻(xiàn)[14]將RF表示為{ }h(X,θk),k=1,2,…,k，算法如圖1所示，k為決策樹數(shù)目，θk為具有獨(dú)立同分布的隨機(jī)向量，該隨機(jī)向量即體現(xiàn)了bootstrap訓(xùn)練樣本選取和劃分屬性的隨機(jī)選取這兩個(gè)隨機(jī)因素。

Fig.1 Scheme of RF algorithm圖1 RF算法示意圖

定義隨機(jī)森林的邊界函數(shù)mr如式（1），兩項(xiàng)分別為分類正確的概率和分類為非正確類概率的最大值，鑒于檢測(cè)時(shí)分為兩類，因此后一項(xiàng)是對(duì)立類。Breiman通過大數(shù)定律給出了隨機(jī)森林誤差收斂定理，如式（2），結(jié)合決策樹平均強(qiáng)度s以及決策樹間平均相關(guān)度ρˉ，得出泛化誤差上界大小PE*≤ρˉ(1-s2)/s2。誤差上界的存在使RF具有良好的防過擬合能力，也是本文選取RF進(jìn)行選擇性集成的原因之一。本文后續(xù)優(yōu)化工作所需的s和ρˉ可由袋外數(shù)據(jù)估算，具體計(jì)算過程參見文獻(xiàn)[14]。

2.2 選擇性集成學(xué)習(xí)

集成學(xué)習(xí)整體模型的泛化性能依賴于子分類器的多樣性和分類強(qiáng)度，對(duì)于選擇性集成，即通過提取一個(gè)比原始規(guī)模更小的子集成，以取得至少不低于甚至高于原始集成的性能。文中異常數(shù)據(jù)檢測(cè)的過程實(shí)際是對(duì)未知樣本標(biāo)簽的分類，確定它是正常或異常是二元分類問題，標(biāo)簽Label={ }-1,+1中的正負(fù)值分別表示正類樣本和負(fù)類樣本。以下簡(jiǎn)要介紹選擇性集成思想[11]。

假定測(cè)試樣本集的大小為m，每個(gè)子分類器對(duì)未知樣本進(jìn)行分類，并采用多數(shù)投票方式得到該樣本的集成分類結(jié)果。集成整體誤差如式（3）所示，其中eoj∈{-1,+1}，j∈{1,2,…,m}。coj=sign(sj)表示集成模型對(duì)第j個(gè)測(cè)試樣本的檢測(cè)結(jié)果，其中sj與sign(x)分別為投票結(jié)果和指示函數(shù)。

在此假設(shè)第k個(gè)子分類器不參加最終的投票表決，則為選擇性集成，第j個(gè)測(cè)試樣本的檢測(cè)輸出以及誤差分別表示如式（4）和式（5）所示，可知Error′≤Error成立，詳細(xì)證明過程可參看文獻(xiàn)[11]。

2.3 人工螢火蟲優(yōu)化算法

文獻(xiàn)[15]通過模擬自然界中螢火蟲發(fā)光行為提出了人工螢火蟲優(yōu)化算法（glowworm swarm optimization，GSO），搜索空間中的每個(gè)螢火蟲表示所優(yōu)化問題的一個(gè)可行解，每只螢火蟲都擁有自身的感知半徑通過式（6）轉(zhuǎn)換為熒光素值，個(gè)體亮度與所處位置的目標(biāo)函數(shù)值相關(guān)，亮度越大，目標(biāo)函數(shù)值越優(yōu)。并于迭代中通過式（7）選取個(gè)體移動(dòng)目標(biāo)，更新決策半徑。不斷迭代使得某些螢火蟲發(fā)光越強(qiáng)，吸引力變得越大，最終絕大部分的個(gè)體螢火蟲都聚集到最亮的個(gè)體周圍，進(jìn)而尋找到最優(yōu)解，具體公式如下：

3 MBGSO選擇性集成ARF的異常檢測(cè)算法

本文將MBGSO與RF兩者相結(jié)合，提出了一種新的WSN異常數(shù)據(jù)檢測(cè)算法。由前文中RF模型的泛化誤差PE可知，要提高集成模型的性能，必須提升個(gè)體分類器的分類強(qiáng)度并同時(shí)增強(qiáng)分類器之間的多樣性。MBGSO算法適應(yīng)度函數(shù)fitness(CE)的設(shè)定借鑒文獻(xiàn)[16]，為防止最終得到的子集成規(guī)模太小，對(duì)RF算法的收斂性造成影響，加入原始集成大小N預(yù)防過剪枝。如式（9）所示：

3.1 基于MBGSO算法優(yōu)化RF集成模型

要對(duì)RF進(jìn)行選擇性集成，舉個(gè)例子，假設(shè)一個(gè)RF模型有100棵決策樹，要對(duì)該集成進(jìn)行優(yōu)化，實(shí)際是關(guān)于這100個(gè)個(gè)體的組合優(yōu)化問題，屬于離散性問題。然而，原始GSO針對(duì)的是連續(xù)型問題，且在尋優(yōu)時(shí)收斂速度慢，易陷于局部最優(yōu)。因此對(duì)于組合優(yōu)化問題，文獻(xiàn)[17]對(duì)傳統(tǒng)GSO進(jìn)行了改進(jìn)，提出離散型螢火蟲算法（discrete GSO，DGSO）；Li等人[18]提出二進(jìn)制螢火蟲算法（binary glowworm swarm optimization，BGSO），不再使用GSO中的位置更新公式，借鑒高斯分布的思想構(gòu)建高斯變異概率映射函數(shù)，將螢火蟲個(gè)體位置映射為位變化的概率。BGSO在對(duì)集成模型進(jìn)行優(yōu)化時(shí)，會(huì)出現(xiàn)效果不夠理想，過早收斂等問題，因此，本文在BGSO[18]基礎(chǔ)上引入變異思想進(jìn)一步提升了優(yōu)化能力。

算法中對(duì)個(gè)體使用0、1編碼，第i只螢火蟲可以表示為xi=(xi1,xi2,…,xid)，d為編碼長(zhǎng)度，在此即為所需優(yōu)化的RF原始集成規(guī)模，個(gè)體初始位置xit(t)隨機(jī)選取。

傳統(tǒng)GSO中的距離采用歐氏距離，鑒于該問題的離散性質(zhì)，對(duì)于某棵決策樹是否被選取，只能是0或1，因此使用式（10）和式（11）計(jì)算兩個(gè)螢火蟲在第k維上的距離，并用漢明距離表示螢火蟲i與j之間的距離。螢火蟲i第k維上的位移sik定義如式（12）所示，lf為學(xué)習(xí)因子，rd為[0,1]內(nèi)隨機(jī)數(shù)。

在進(jìn)行目標(biāo)函數(shù)值與熒光素值的轉(zhuǎn)換和鄰域移動(dòng)目標(biāo)選擇時(shí)方式不變，在位置更新時(shí)使用式（13）替換原有方式。構(gòu)建概率映射函數(shù)并修改螢火蟲位置更新公式分別如式（14）和式（15）所示，此二式對(duì)應(yīng)著sik(t)<0或sik(t)≥0時(shí)的新的位置更新方式。

本文在算法迭代過程中引入個(gè)體變異，設(shè)置一個(gè)變異概率閾值θ，若rand>θ，則對(duì)當(dāng)前個(gè)體進(jìn)行以下操作：隨機(jī)生成一個(gè)取值區(qū)間為（0,1）的d維向量r，變異公式參數(shù)p1、p2同屬于0到1之間，通過式（16）更新個(gè)體中每一維的取值，即對(duì)比r中每一維的取值與p1和p2的大小關(guān)系，來決定當(dāng)前維的值是否變化、轉(zhuǎn)移或是取反，最終完成對(duì)個(gè)體位置的變異；反之，若rand<θ，則跳過這個(gè)步驟繼續(xù)進(jìn)行迭代。

MBGSO算法優(yōu)化選擇RF子集成的偽代碼如下所示。

算法1MBGSO(X,N,t,theta,ds,p1,p2,rf,itermax)

輸入：數(shù)據(jù)集X；螢火蟲數(shù)目N；當(dāng)前迭代次數(shù)t；變異概率theta；決策半徑ds；變異公式參數(shù)p1、p2；訓(xùn)練所得檢測(cè)模型rf；最大迭代次數(shù)itermax。

1.初始化算法各參數(shù)；

2.以式（6）作為算法目標(biāo)函數(shù)；

3.當(dāng)t

4.對(duì)除第i個(gè)螢火蟲本身外的所有個(gè)體，求它們到i螢火蟲的漢明距離distance；

5.選取distancelv(i)的個(gè)體構(gòu)成Ni；

6.通過傳統(tǒng)GSO算法中的輪盤賭方法計(jì)算i的移動(dòng)方向；

7.ds的更新依然以原先方式進(jìn)行，以概率映射函數(shù)（式（13）至式（15））對(duì)個(gè)體的位置進(jìn)行更新；

8.若rand()>theta，通過p1、p2使用式（16）對(duì)部分個(gè)體進(jìn)行變異操作；

9.記錄當(dāng)前迭代最優(yōu)值vcurrent以及最優(yōu)子集成組合rf-se；

輸出：迭代完成時(shí)的最優(yōu)值以及rf-se。

3.2 WSN數(shù)據(jù)異常檢測(cè)與模型自適應(yīng)更新

首先執(zhí)行RF算法訓(xùn)練選取的WSN數(shù)據(jù)集得到檢測(cè)模型，并使用本文所提MBGSO算法優(yōu)化RF原始集成模型，對(duì)原始集成進(jìn)行選擇性剪枝獲得最優(yōu)子集成RF_SE，此時(shí)的子集成即可代替原始模型對(duì)后續(xù)的待測(cè)樣本執(zhí)行異常檢測(cè)工作。

MBGSO-ARF檢測(cè)算法在MBGSO-RF基礎(chǔ)上增加了自適應(yīng)更新的過程，在此設(shè)定數(shù)據(jù)塊大小size_block為1000，對(duì)WSN測(cè)試數(shù)據(jù)集以size_block為單位大小進(jìn)行讀取，每當(dāng)子集成RF_SE檢測(cè)完size_block待測(cè)樣本后，使用如下方式變更Buffer和validate內(nèi)的數(shù)據(jù)并對(duì)當(dāng)前集成模型進(jìn)行更新。

設(shè)定Buffer和validate的大小分別用于存儲(chǔ)模型更新樣本以及選擇性剔出集成中的某些子分類器。Buffer是通過泊松分布隨機(jī)數(shù)在待測(cè)樣本集合中隨機(jī)取樣得到，而validate則為數(shù)據(jù)塊中大小為size_val的小樣本集。并使用validate小樣本集對(duì)當(dāng)前集成中的子分類器進(jìn)行驗(yàn)證以得到檢測(cè)精度tpr和多樣性div，通過這兩個(gè)參數(shù)結(jié)合式（17）得到Fit，此處的α為兩參數(shù)的權(quán)值，在0到1之間，在此取0.4。

Cavalcanti等人[19]選擇了不合度量、Q統(tǒng)計(jì)量以及kappa值等多樣性度量進(jìn)行加權(quán)組合得到新的標(biāo)準(zhǔn)，由于模型中的決策樹的多樣性差異并不會(huì)太大而且更新須及時(shí)，因此本文在此只使用了不合度量（disagreement measure）計(jì)算div=(b+c)/m，它的值域在0到1之間，多樣性隨著該值的增大而增大，參見表1，其中b表示被hi分類為正類同時(shí)被hj分為負(fù)類的樣本個(gè)數(shù)，其余依此類推，m則為總和。

Table 1 Classifier prediction result contingency table表1 分類器預(yù)測(cè)結(jié)果列聯(lián)表

降序排列后留下Fit值高的一部分決策樹，余下的將被剔除，并使用Buffer重訓(xùn)練新決策樹用于補(bǔ)全集成模型。基于MBGSO-ARF模型自適應(yīng)更新的WSN異常數(shù)據(jù)檢測(cè)算法的偽代碼如下所示。

算法2MBGSO-ARF(X,s,T,Buffer,data-vali,fe)

輸入：數(shù)據(jù)集X;測(cè)試數(shù)據(jù)塊大小s;測(cè)試樣本集T;用于存儲(chǔ)重訓(xùn)練決策樹的樣本Buffer;用于評(píng)估每棵樹的小樣本集data-vali；X中樣本屬性數(shù)fe。

1.初始化算法各參數(shù)；

2.使用RF算法訓(xùn)練模型rf；

3.通過MBGSO算法對(duì)rf進(jìn)行優(yōu)化得到剪枝后的集成模型rf-se；

Whilei

4.當(dāng)i

5.使用rf-se對(duì)第i塊測(cè)試樣本集進(jìn)行檢測(cè)，基于當(dāng)前塊更新用于存儲(chǔ)重訓(xùn)練決策樹的樣本Buffer和小樣本集data-vali；

6.對(duì)Buffer基于泊松分布隨機(jī)數(shù)采樣得到當(dāng)前更新樣本集Buffer-rebuild；

7.使用data-vali對(duì)每棵決策樹的召回率以及多樣性進(jìn)行評(píng)估得到tpr和div；

8.以文中所選比例剔除排在最后的部分決策樹，通過Buffer-rebuild重訓(xùn)練相應(yīng)數(shù)目的決策樹補(bǔ)全集成模型forest-new賦予rf-se；

輸出：最終檢測(cè)結(jié)果漏報(bào)數(shù)以及誤報(bào)數(shù)。

4 仿真實(shí)驗(yàn)

為了評(píng)價(jià)本文所提出的異常數(shù)據(jù)檢測(cè)算法的性能，使用Intel Berkeley實(shí)驗(yàn)室數(shù)據(jù)集和帶標(biāo)記的傳感器網(wǎng)絡(luò)數(shù)據(jù)集（LWSNDR）[20]完成了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)所用PC機(jī)配置為64位Windows 7操作系統(tǒng)，Intel?CoreTMi7-4790 CPU，主頻3.6 GHz，內(nèi)存16 GB，仿真編程語言為Matlab R2014a。在相同實(shí)驗(yàn)環(huán)境下，分別實(shí)現(xiàn)了傳統(tǒng)RF算法、MBGSO-RF算法、ARF算法以及MBGSO-ARF算法。然后，比較各自實(shí)驗(yàn)結(jié)果。

4.1 數(shù)據(jù)集介紹

伯克利實(shí)驗(yàn)室數(shù)據(jù)集（IBRL）采集自部署于Intel Berkeley實(shí)驗(yàn)室中的無線傳感器網(wǎng)絡(luò)，其中包含有54個(gè)MICA2傳感器節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)采樣周期為30 s，節(jié)點(diǎn)數(shù)據(jù)采集周期從2004年2月28日至2004年4月5日，節(jié)點(diǎn)所采集的數(shù)據(jù)包括溫度、濕度、光照強(qiáng)度以及節(jié)點(diǎn)電壓4個(gè)屬性。本文實(shí)驗(yàn)中選取了9號(hào)、11號(hào)和25號(hào)傳感器節(jié)點(diǎn)所采集的數(shù)據(jù)（表2分別記為IBRL-9、IBRL-11以及IBRL-25）。分析數(shù)據(jù)樣本文件中的異常值時(shí)間戳，發(fā)現(xiàn)異常均為隨機(jī)插入的其他不同時(shí)間段的數(shù)據(jù)樣本。實(shí)驗(yàn)之前，首先通過時(shí)間戳將異常值標(biāo)記了出來，訓(xùn)練數(shù)據(jù)中的標(biāo)記用于作為訓(xùn)練標(biāo)簽，而測(cè)試數(shù)據(jù)中的標(biāo)簽則用于評(píng)價(jià)算法的性能。

另外，本文還使用LWSNDR中分別置于室內(nèi)和室外的兩個(gè)節(jié)點(diǎn)數(shù)據(jù)集（表2中記為L(zhǎng)WSNDR-1和LWSNDR-4），屬性分別對(duì)應(yīng)溫度和濕度，其中的異常值是人為加熱水壺產(chǎn)生的，該數(shù)據(jù)集異常值較少。具體所取數(shù)據(jù)集如表2所示。

Table 2 Datasets of experiments表2 實(shí)驗(yàn)數(shù)據(jù)集

4.2 算法性能評(píng)價(jià)指標(biāo)

機(jī)器學(xué)習(xí)分類問題中常用的評(píng)價(jià)指標(biāo)就是精度。而異常檢測(cè)和分類問題的區(qū)別在于類別分布的不平衡性，異常數(shù)據(jù)和正常數(shù)據(jù)比例不相當(dāng)，因此精度不適合作為異常檢測(cè)的評(píng)價(jià)指標(biāo)，并引出如下的評(píng)價(jià)指標(biāo)。

異常檢測(cè)分為兩類樣本:正常以及異常，研究者將訓(xùn)練集中占少數(shù)且擁有高識(shí)別重要性的異常樣本作為正類，其余的正常樣本作為負(fù)類。因此可將所檢測(cè)樣本根據(jù)其實(shí)際所屬類別以及檢測(cè)結(jié)果組成如表3所示混淆矩陣，其中有真正例（true positive，TP）、假正例（false positive，F(xiàn)P）、真反例（true negative，TN）、假反例（false negative，F(xiàn)N）。

Table 3 Confusion matrix of detection results表3 檢測(cè)結(jié)果混淆矩陣

為了評(píng)價(jià)WSN異常數(shù)據(jù)檢測(cè)方法的性能，本文采用召回率TPR（true positive rate）和誤報(bào)率FPR（false positive rate）兩個(gè)評(píng)價(jià)指標(biāo)。前者也被稱作查全率，是被正確檢測(cè)出來的異常個(gè)數(shù)與實(shí)際為異常的樣本個(gè)數(shù)的比值；后者是被算法誤判為異常的正常數(shù)據(jù)樣本數(shù)目與正常數(shù)據(jù)樣本總數(shù)之比。由于本文算法使用了選擇性集成的思想，因此增加一個(gè)評(píng)價(jià)指標(biāo):集成規(guī)模壓縮比ECR（ensemble compression ratio），即最終集成規(guī)模大小ES_selective與原始集成規(guī)模大小ES_ori的比值，公式如下：

4.3 實(shí)驗(yàn)參數(shù)設(shè)置

本文參數(shù)中的決策樹數(shù)目的設(shè)定是根據(jù)數(shù)據(jù)實(shí)驗(yàn)分析得到的，GSO部分參數(shù)采用的是默認(rèn)設(shè)定值，其他參數(shù)則是經(jīng)過不斷修改并對(duì)比實(shí)驗(yàn)結(jié)果采用的較優(yōu)值。RF中的參數(shù)不多，包括決策樹的數(shù)目m以及構(gòu)造決策樹時(shí)節(jié)點(diǎn)分裂所選屬性個(gè)數(shù)fe，若數(shù)據(jù)集屬性個(gè)數(shù)為d，取fe為sqrt(d)。自適應(yīng)更新部分選取的size_val大小定為300，并設(shè)置每次更新剔出重訓(xùn)練的分類器數(shù)目為m/10，在此即為20。而GSO算法中，基本參數(shù)取值參照原文獻(xiàn)[15]設(shè)置方法，設(shè)熒光素值揮發(fā)系數(shù)ρ為0.4，取熒光素增強(qiáng)系數(shù)γ為0.6，熒光素濃度Lo取5，感知半徑變化率β取作0.08，種群大小Pop、移動(dòng)步長(zhǎng)Sl、最大迭代次數(shù)It_max、鄰域閾值Nt、感知半徑Rs以及決策半徑Rd的具體取值如表4所示。

Table 4 Basic parameters in GSO表4 GSO的基本參數(shù)

螢火蟲種群數(shù)目pop在此設(shè)置為和RF中決策樹數(shù)目一樣，3.1節(jié)中的學(xué)習(xí)因子C和最大位移Max_M則按原算法[18]設(shè)定，MBGSO算法使用的額外參數(shù)如表5所示，其中有局部變異概率閾值θ以及MBGSO中變異思想中的兩個(gè)轉(zhuǎn)換概率閾值P1、P2，本文使用了試湊法進(jìn)行設(shè)置。

Table 5 Additional parameters in MBGSO表5 MBGSO的額外參數(shù)

本文在選取m時(shí)，分別設(shè)置為100、150以及200，并將算法用于25號(hào)節(jié)點(diǎn)數(shù)據(jù)進(jìn)行了對(duì)比，結(jié)果如表6所示，其中Fp和Fn分別表示誤報(bào)數(shù)和漏報(bào)數(shù)，可以看出m為200時(shí)，算法性能收斂基本最優(yōu)，因此本文m取200。

Table 6 Algorithm performance for different values of m表6 算法在不同的m取值時(shí)的性能比較

4.4 MBGSO與原始BGSO優(yōu)化結(jié)果對(duì)比

本文在對(duì)RF進(jìn)行選擇性集成時(shí)對(duì)BGSO引入了變異思路，為了驗(yàn)證該機(jī)制對(duì)算法的有效性，依然使用了上文所選取的3個(gè)節(jié)點(diǎn)的數(shù)據(jù)集對(duì)MBGSO和BGSO進(jìn)行了實(shí)驗(yàn)對(duì)比，以上2種優(yōu)化算法平均耗時(shí)分別為5.43 s和4.52 s。圖2和圖3分別為決策樹棵數(shù)設(shè)置為200和100時(shí)的對(duì)比圖，從中可以看出，盡管MBGSO的迭代次數(shù)比BGSO略多幾次，但前者的尋優(yōu)能力要比后者更強(qiáng)，且收斂性更好。

Fig.3 Convergence diagram of optimization(m=100)圖3 m為100時(shí)算法的尋優(yōu)收斂圖

因此，在后續(xù)實(shí)驗(yàn)里采用MBGSO算法對(duì)隨機(jī)森林進(jìn)行選擇性集成。優(yōu)化結(jié)果的對(duì)比圖如圖2、圖3所示。

4.5 異常檢測(cè)算法對(duì)比實(shí)驗(yàn)

為驗(yàn)證本文所提算法性能，在上文所述的3個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)對(duì)比，所取決策樹棵樹m為200，所有實(shí)驗(yàn)結(jié)果都是在運(yùn)行30次后選取的平均值。如表7所示，帶標(biāo)記數(shù)據(jù)集上，由于異常不多且易于檢測(cè)，檢測(cè)結(jié)果基本一致，召回率均達(dá)到90%以上，不是很高的原因是測(cè)試樣本中的異常數(shù)目不多。從表8可以看出，原始RF在幾個(gè)數(shù)據(jù)集上的檢測(cè)效果還比較理想，在檢測(cè)9號(hào)和11號(hào)節(jié)點(diǎn)數(shù)據(jù)時(shí)的誤報(bào)數(shù)目分別為1.76和0.53，該結(jié)果和選擇性集成后的MBGSORF算法結(jié)果相同，但在漏報(bào)數(shù)目上高于MBGSORF，而在25號(hào)節(jié)點(diǎn)數(shù)據(jù)的檢測(cè)效果上，原始RF算法不論是在漏報(bào)數(shù)目還是誤報(bào)數(shù)目上都比MBGSO-RF算法多，說明經(jīng)過選擇性集成后的RF算法在檢測(cè)性能方面都要優(yōu)于原始RF。

接下來分成兩組對(duì)比：一組是引入自適應(yīng)更新模型后的ARF對(duì)比原始RF模型，另一組是未引入自適應(yīng)更新的MBGSO-RF和MBGSO-ARF算法的對(duì)比，由該兩組數(shù)據(jù)對(duì)比可以發(fā)現(xiàn)，在加入了模型更新機(jī)制后算法降低了誤報(bào)數(shù)目：第1組中分別由1.76降至1.26、0.53降至0.26以及3.00降至1.80；第2組中分別由1.76降至1.20、0.53降至0.20以及3.00降至1.63。

Table 7 Detection results on dataset LWSNDR表7 LWSNDR數(shù)據(jù)集檢測(cè)結(jié)果對(duì)比

Table 8 Detection results on dataset IBRL表8 伯克利實(shí)驗(yàn)室數(shù)據(jù)集檢測(cè)結(jié)果對(duì)比

但更新機(jī)制的引入對(duì)于漏報(bào)數(shù)目的改善不是很大，由于更新模型時(shí)用于重訓(xùn)練決策樹的樣本中異常數(shù)不多，使得在新的數(shù)據(jù)環(huán)境下只是更加具備了對(duì)于正常數(shù)據(jù)樣本的感知，用于重訓(xùn)練的樣本中的異常數(shù)據(jù)的多樣性不足以提供模型識(shí)別出更多的異常值。綜合看平均值MBGSO-ARF算法的誤報(bào)數(shù)目以及漏報(bào)數(shù)目都要少于其他3種異常檢測(cè)算法，TPR均值達(dá)到99.09%。

各種算法在不同數(shù)據(jù)集上使用的模型集成大小比較如表9所示，本文MBGSO-RF算法和MBGSOARF算法在檢測(cè)各數(shù)據(jù)集時(shí)所用模型集成平均大小為154.3，未優(yōu)化時(shí)的模型集成大小為200，ECR為0.7718，算法實(shí)現(xiàn)了部分子分類器達(dá)到甚至高于原始RF性能的目的。模型集成大小降低了，因此使用MBGSO優(yōu)化過的算法在檢測(cè)時(shí)間上要低于優(yōu)化之前的算法。

Table 9 Ensemble size of different algorithm models表9 不同算法模型集成大小

而MBGSO-RF的平均檢測(cè)時(shí)間由原始RF的0.38 s降至0.33 s，MBGSO-ARF則由ARF所耗費(fèi)的4.2 s降至3.23 s，具體對(duì)比如圖4和圖5所示。

為尋找優(yōu)化收斂時(shí)間與檢測(cè)結(jié)果好壞間有無關(guān)聯(lián)，本文實(shí)驗(yàn)采用3個(gè)節(jié)點(diǎn)的數(shù)據(jù)，分別選取決策樹個(gè)數(shù)為100、150、200進(jìn)行了20次實(shí)驗(yàn)，以MBGSORF算法的檢測(cè)結(jié)果尋找關(guān)聯(lián)，時(shí)間以及誤報(bào)漏報(bào)數(shù)都是3個(gè)節(jié)點(diǎn)數(shù)據(jù)在3種不同集成規(guī)模下的均值，具體如圖6所示。

由圖6可以看出，檢測(cè)結(jié)果較優(yōu)時(shí)優(yōu)化算法的收斂時(shí)間通常較高，反之亦然，進(jìn)一步表明該算法的有效性。其中2個(gè)縱軸分別表示優(yōu)化所耗時(shí)間和誤報(bào)漏報(bào)數(shù)目。

Fig.4 Detection time of RF and MBGSO-RF on each node圖4 RF和MBGSO-RF各節(jié)點(diǎn)檢測(cè)時(shí)間對(duì)比

Fig.6 Relationship between optimal time and Fp/Fn圖6 優(yōu)化時(shí)間與誤報(bào)漏報(bào)數(shù)間的關(guān)系

為了凸顯本文MBGSO算法相對(duì)于其他優(yōu)化算法的優(yōu)勢(shì)，選擇了使用二進(jìn)制粒子群（binary particle swarm optimization，BPSO）算法對(duì)RF進(jìn)行選擇性集成實(shí)驗(yàn)，分別在伯克利數(shù)據(jù)集9號(hào)、11號(hào)和25號(hào)節(jié)點(diǎn)上使用MBGSO和BPSO算法對(duì)RF進(jìn)行優(yōu)化。對(duì)比實(shí)驗(yàn)中BPSO的種群大小與MBGSO設(shè)定一致，常數(shù)因子以及慣性權(quán)重分別取1.5以及0.7。對(duì)比結(jié)果如表10所示，可以看出通過MBGSO優(yōu)化的子集成在檢測(cè)效果上要優(yōu)于后者，結(jié)果也證明了算法的有效性。MBGSO-ARF在進(jìn)行WSN數(shù)據(jù)異常檢測(cè)時(shí)，主要約束條件在于需要包含部分異常樣本的傳感器歷史數(shù)據(jù)以及算法部分參數(shù)的調(diào)優(yōu)，鑒于歷史數(shù)據(jù)以及異常樣本的獲取都是可以達(dá)到的，算法參數(shù)的選取可以通過仿真實(shí)驗(yàn)調(diào)優(yōu)。如此可見，本文算法在實(shí)際檢測(cè)中是可行的。

Table 10 Detection results of 2 optimization algorithms on 3 datasets表10 兩種優(yōu)化算法于3種數(shù)據(jù)集的檢測(cè)結(jié)果

4.6 算法復(fù)雜度分析

設(shè)螢火蟲種群大小為p，RF中決策樹棵數(shù)為m，每次迭代選取的決策樹棵數(shù)為d，數(shù)據(jù)個(gè)數(shù)為N，算法迭代次數(shù)為iter_max。首先初始化種群的時(shí)間復(fù)雜度為O(p);每次迭代在計(jì)算所選組合的適應(yīng)度函數(shù)值時(shí)的時(shí)間復(fù)雜度為O(p×d);每次迭代計(jì)算螢火蟲個(gè)體熒光素更新以及之間距離的時(shí)間復(fù)雜度分別為O(p)和O(p2×m);個(gè)體位置和決策域半徑更新過程的時(shí)間復(fù)雜度分別為O(p×m)和O(p);每次迭代進(jìn)行變異過程的時(shí)間復(fù)雜度為O(p×m)。因此MBGSO算法時(shí)間復(fù)雜度為O(iter_max×p2×m)。

假設(shè)有n個(gè)訓(xùn)練樣本，T個(gè)測(cè)試數(shù)據(jù)，特征數(shù)fe，單位數(shù)據(jù)塊大小為s_block，Buffer大小s_buf，小樣本驗(yàn)證集大小為s_val，CART算法時(shí)間復(fù)雜度為O(fe×n(lgn))，RF在構(gòu)建時(shí)選取特征mtry小于fe且不剪枝，因此RF時(shí)間復(fù)雜度為O(m×mtry×n(lgn))。而計(jì)算當(dāng)前決策樹Fit值的時(shí)間復(fù)雜度為O(m×s_Val)，重訓(xùn)練時(shí)間復(fù)雜度為O((m/10×mtry×s_buf×lg(s_buf)))。因此復(fù)雜度為O(T/s_block(m/10×mtry×s_buf×lg(s_buf))+m×mtry×n(lgn))。從實(shí)驗(yàn)結(jié)果可以看出，優(yōu)化后的模型集成大小降低了近30%，MBGSO-ARF所耗時(shí)間由ARF的4.2 s降至3.23 s，若優(yōu)化后集成大小為L(zhǎng)，優(yōu)化后檢測(cè)復(fù)雜度為O(L(fe×T×lgT))對(duì)應(yīng)了后者3.23 s，而原始檢測(cè)復(fù)雜度為O(m(fe×T×lgT))則對(duì)應(yīng)了前者4.2 s，這部分時(shí)間的節(jié)約即對(duì)應(yīng)了使用子集成檢測(cè)與原始集成檢測(cè)時(shí)間的差值。

本文算法使用MBGSO優(yōu)化隨機(jī)森林，選擇了最優(yōu)子集成并引入模型更新機(jī)制，在提高檢測(cè)算法的召回率，并降低誤報(bào)率的前提下，縮小了所使用的模型集成大小，節(jié)省了檢測(cè)所耗時(shí)間，提高了異常檢測(cè)的效率。

5 結(jié)束語

本文結(jié)合RF和選擇性集成思路提出了一種無線傳感器網(wǎng)絡(luò)異常數(shù)據(jù)檢測(cè)算法（MBGSO-ARF）。該方法在二進(jìn)制螢火蟲算法的基礎(chǔ)上加入了變異思路，避免了算法出現(xiàn)過早收斂的情況，使其在對(duì)RF選擇性集成時(shí)獲得更優(yōu)的解，并以子集成模型結(jié)合自適應(yīng)更新模塊對(duì)待測(cè)樣本進(jìn)行異常檢測(cè)，克服了使用單一的RF訓(xùn)練模型執(zhí)行檢測(cè)的缺點(diǎn)，實(shí)時(shí)地對(duì)部分子分類器進(jìn)行重新訓(xùn)練并加入集成模型中，使得模型一定程度上能更適應(yīng)當(dāng)前數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明MBGSO-ARF算法的效率和異常數(shù)據(jù)檢測(cè)的準(zhǔn)確性都有了提高。由于MBGSO-ARF算法采用固定的模型更新方式，今后考慮在模型更新的約束條件等方面進(jìn)行改進(jìn)，以進(jìn)一步提高算法的性能。