螢火蟲優化和隨機森林的WSN異常數據檢測*

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

1.江南大學 物聯網工程學院，江蘇 無錫 214122

2.江蘇省無線傳感網高技術研究重點實驗室，南京 210003

3.物聯網技術應用教育部工程技術研究中心，江蘇 無錫 214122

1 引言

無線傳感器網絡（wireless sensor network，WSN）的構成單元是大量低成本、微型的傳感器節點，可以感知網絡部署區域內的各種數據信息，進行數據樣本的采集、處理以及傳輸，特別適宜于無人值守或惡劣環境的監測。WSN目前在許多領域都有所應用，如工業控制、智慧農業、醫療監測、基礎設施健康檢測以及環境監測等。然而，節點自身的軟硬件故障、電量耗盡或者部署環境遭遇突發事件（如強降雨、森林火災或者危險品泄漏）等因素常常導致節點采集的數據明顯地偏離正常數據形態。這類數據稱為離群數據或異常數據。及時準確地檢測出傳感器數據流中的異常數據，不論是對于外部事件的實時監測還是無線傳感器網絡本身健康狀態的監測都具有十分重要的意義。

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

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

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

2 預備知識

2.1 決策樹與隨機森林

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

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

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

2.2 選擇性集成學習

集成學習整體模型的泛化性能依賴于子分類器的多樣性和分類強度，對于選擇性集成，即通過提取一個比原始規模更小的子集成，以取得至少不低于甚至高于原始集成的性能。文中異常數據檢測的過程實際是對未知樣本標簽的分類，確定它是正常或異常是二元分類問題，標簽Label={ }-1,+1中的正負值分別表示正類樣本和負類樣本。以下簡要介紹選擇性集成思想[11]。

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

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

2.3 人工螢火蟲優化算法

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

3 MBGSO選擇性集成ARF的異常檢測算法

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

3.1 基于MBGSO算法優化RF集成模型

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

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

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

在進行目標函數值與熒光素值的轉換和鄰域移動目標選擇時方式不變，在位置更新時使用式（13）替換原有方式。構建概率映射函數并修改螢火蟲位置更新公式分別如式（14）和式（15）所示，此二式對應著sik(t)<0或sik(t)≥0時的新的位置更新方式。

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

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

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

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

1.初始化算法各參數；

2.以式（6）作為算法目標函數；

3.當t

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

5.選取distancelv(i)的個體構成Ni；

6.通過傳統GSO算法中的輪盤賭方法計算i的移動方向；

7.ds的更新依然以原先方式進行，以概率映射函數（式（13）至式（15））對個體的位置進行更新；

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

9.記錄當前迭代最優值vcurrent以及最優子集成組合rf-se；

輸出：迭代完成時的最優值以及rf-se。

3.2 WSN數據異常檢測與模型自適應更新

首先執行RF算法訓練選取的WSN數據集得到檢測模型，并使用本文所提MBGSO算法優化RF原始集成模型，對原始集成進行選擇性剪枝獲得最優子集成RF_SE，此時的子集成即可代替原始模型對后續的待測樣本執行異常檢測工作。

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

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

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

Table 1 Classifier prediction result contingency table表1 分類器預測結果列聯表

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

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

輸入：數據集X;測試數據塊大小s;測試樣本集T;用于存儲重訓練決策樹的樣本Buffer;用于評估每棵樹的小樣本集data-vali；X中樣本屬性數fe。

1.初始化算法各參數；

2.使用RF算法訓練模型rf；

3.通過MBGSO算法對rf進行優化得到剪枝后的集成模型rf-se；

Whilei

4.當i

5.使用rf-se對第i塊測試樣本集進行檢測，基于當前塊更新用于存儲重訓練決策樹的樣本Buffer和小樣本集data-vali；

6.對Buffer基于泊松分布隨機數采樣得到當前更新樣本集Buffer-rebuild；

7.使用data-vali對每棵決策樹的召回率以及多樣性進行評估得到tpr和div；

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

輸出：最終檢測結果漏報數以及誤報數。

4 仿真實驗

為了評價本文所提出的異常數據檢測算法的性能，使用Intel Berkeley實驗室數據集和帶標記的傳感器網絡數據集（LWSNDR）[20]完成了對比實驗。實驗所用PC機配置為64位Windows 7操作系統，Intel?CoreTMi7-4790 CPU，主頻3.6 GHz，內存16 GB，仿真編程語言為Matlab R2014a。在相同實驗環境下，分別實現了傳統RF算法、MBGSO-RF算法、ARF算法以及MBGSO-ARF算法。然后，比較各自實驗結果。

4.1 數據集介紹

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

另外，本文還使用LWSNDR中分別置于室內和室外的兩個節點數據集（表2中記為LWSNDR-1和LWSNDR-4），屬性分別對應溫度和濕度，其中的異常值是人為加熱水壺產生的，該數據集異常值較少。具體所取數據集如表2所示。

Table 2 Datasets of experiments表2 實驗數據集

4.2 算法性能評價指標

機器學習分類問題中常用的評價指標就是精度。而異常檢測和分類問題的區別在于類別分布的不平衡性，異常數據和正常數據比例不相當，因此精度不適合作為異常檢測的評價指標，并引出如下的評價指標。

異常檢測分為兩類樣本:正常以及異常，研究者將訓練集中占少數且擁有高識別重要性的異常樣本作為正類，其余的正常樣本作為負類。因此可將所檢測樣本根據其實際所屬類別以及檢測結果組成如表3所示混淆矩陣，其中有真正例（true positive，TP）、假正例（false positive，FP）、真反例（true negative，TN）、假反例（false negative，FN）。

Table 3 Confusion matrix of detection results表3 檢測結果混淆矩陣

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

4.3 實驗參數設置

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

Table 4 Basic parameters in GSO表4 GSO的基本參數

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

Table 5 Additional parameters in MBGSO表5 MBGSO的額外參數

本文在選取m時，分別設置為100、150以及200，并將算法用于25號節點數據進行了對比，結果如表6所示，其中Fp和Fn分別表示誤報數和漏報數，可以看出m為200時，算法性能收斂基本最優，因此本文m取200。

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

4.4 MBGSO與原始BGSO優化結果對比

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

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

因此，在后續實驗里采用MBGSO算法對隨機森林進行選擇性集成。優化結果的對比圖如圖2、圖3所示。

4.5 異常檢測算法對比實驗

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

接下來分成兩組對比：一組是引入自適應更新模型后的ARF對比原始RF模型，另一組是未引入自適應更新的MBGSO-RF和MBGSO-ARF算法的對比，由該兩組數據對比可以發現，在加入了模型更新機制后算法降低了誤報數目：第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數據集檢測結果對比

Table 8 Detection results on dataset IBRL表8 伯克利實驗室數據集檢測結果對比

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

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

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

而MBGSO-RF的平均檢測時間由原始RF的0.38 s降至0.33 s，MBGSO-ARF則由ARF所耗費的4.2 s降至3.23 s，具體對比如圖4和圖5所示。

為尋找優化收斂時間與檢測結果好壞間有無關聯，本文實驗采用3個節點的數據，分別選取決策樹個數為100、150、200進行了20次實驗，以MBGSORF算法的檢測結果尋找關聯，時間以及誤報漏報數都是3個節點數據在3種不同集成規模下的均值，具體如圖6所示。

由圖6可以看出，檢測結果較優時優化算法的收斂時間通常較高，反之亦然，進一步表明該算法的有效性。其中2個縱軸分別表示優化所耗時間和誤報漏報數目。

Fig.4 Detection time of RF and MBGSO-RF on each node圖4 RF和MBGSO-RF各節點檢測時間對比

Fig.6 Relationship between optimal time and Fp/Fn圖6 優化時間與誤報漏報數間的關系

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

Table 10 Detection results of 2 optimization algorithms on 3 datasets表10 兩種優化算法于3種數據集的檢測結果

4.6 算法復雜度分析

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

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

本文算法使用MBGSO優化隨機森林，選擇了最優子集成并引入模型更新機制，在提高檢測算法的召回率，并降低誤報率的前提下，縮小了所使用的模型集成大小，節省了檢測所耗時間，提高了異常檢測的效率。

5 結束語

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