衷衛(wèi)聲，羅力維，張強

(南昌大學a.信息工程學院，江西 南昌 330031；b.先進制造學院，江西 南昌 330031)

隨著電子技術和無線通信的不斷發(fā)展，無線傳感器網(wǎng)絡(wireless sensor network,WSN)應運而生，它廣泛應用于定位、導航、工業(yè)和軍事等領域。由于WSN在系統(tǒng)穩(wěn)定性、可靠性、感知信息的準確性等方面存在不少問題需要解決，這可能會導致傳感器數(shù)據(jù)不可靠、產生噪聲、數(shù)據(jù)丟失與冗余，從而影響到原始數(shù)據(jù)的質量和匯總結果，所以需要離群值檢測算法[1-3]。

目前，WSN中離群值檢測方法大致分為基于統(tǒng)計的方法[4]、基于最近鄰的方法[5]、基于聚類的方法[6]以及基于分類的方法[7-9]等。其中，基于分類的方法是機器學習的重要領域，而一分類支持向量機(OCSVM)是其中最流行的方法之一。它不斷地將低維數(shù)據(jù)投影到高維空間中并且形成邊界，將邊界外部的數(shù)據(jù)判斷為離群值，通過最大化決策邊界的余量為分類提供最佳解決方案。此外它還能通過核函數(shù)簡化投影計算從而避免維數(shù)詛咒的問題。為了更好地將OCSVM用于WSN中，Rajasegarar等[10]將OCSVM的邊界拓展為球和橢球，并以此為基礎形成了四分之一球支持向量機(QSSVM)，以及中心橢球支持向量機(CESVM)。這兩種算法在運行過程中將球心移到坐標原點以計算支持向量，因此也增加了計算量，不適用于大規(guī)模的WSN。Miao等[11]將OCSVM應用于大規(guī)模的WSN并且摒棄了融合中心(FC)，從而形成分布式網(wǎng)絡。此外，Miao等[11]還在應用過程中使用隨機近似函數(shù)代替核函數(shù)，從而節(jié)省了計算資源。但隨著分布式網(wǎng)絡規(guī)模增大，每個節(jié)點的實際情況都各不相同，因此每個節(jié)點的OCSVM參數(shù)設置都應該不同。在機器學習中，OCSVM的錯誤容忍度參數(shù)υ和邊界調整參數(shù)γ是對其檢測效果影響最大的兩個參數(shù)。Wang等[12]通過找到最大和最小的γ參數(shù)，并且將其平均值作為最佳的參數(shù)。但是以這種方式選擇γ參數(shù)可能會有很大的波動。為了解決這個問題，Xiao等[13]提出計算從數(shù)據(jù)集到OCSVM封閉表面的距離，然后在此基礎上，提出了參數(shù)選擇的優(yōu)化目標函數(shù)。Anaissi等[14]則對算法做了進一步擴展，使其更適合于高維數(shù)據(jù)集。

然而，上述參數(shù)設置方法可能不適用于WSN。因為在WSN中要考慮各種因數(shù)的影響，如節(jié)點之間的相關性、時空性等，所以每個節(jié)點的參數(shù)應該自適應地調整。本文提出一種基于錨節(jié)點的無線傳感網(wǎng)離群值檢測算法，將定位算法中的錨節(jié)點引入檢測算法中，以錨節(jié)點與節(jié)點屬性之間相關性為基礎，利用大小根堆與標準差來動態(tài)地調整普通節(jié)點的參數(shù)，并將其轉換為錨節(jié)點，循環(huán)往復地拓展到整個無線傳感網(wǎng)，最終每個節(jié)點的參數(shù)都自適應地調整為最佳。

1 OCSVM算法

Sch?lkopf等[15]提出了一種稱為OCSVM的分類方法，用于在高維現(xiàn)實世界數(shù)據(jù)集中進行離群值檢測。對于給定的數(shù)據(jù)集，OCSVM算法將在正常數(shù)據(jù)的密集區(qū)域周圍找到邊界。位于邊界上或內部的數(shù)據(jù)被稱為普通數(shù)據(jù)，否則為離群數(shù)據(jù)。但是，在實際情況下，數(shù)據(jù)并不總是線性可分離的。此時，我們可以選擇將低維數(shù)據(jù)集Rd投影到高維特征空間Rd'上，其中d<

OCSVM分類器的原始二次問題[16]為：

(1)

式中：ω∈Rd，ξ=[ξ1，…，ξn]是松弛變量，ρ是偏差項，且0<υ≤1。

為了更好地進行計算，使用拉格朗日乘數(shù)法將式(1)轉換為以下二次對偶問題：

(2)

然而，持續(xù)的投影可能會導致大量的計算(甚至是不可能的)。此時，可以使用核函數(shù)代替投影計算。在本文中，通過使用高斯徑向基函數(shù)(RBF)k(x，y)=e-γ||x-y||2來代替投影，從而減少計算量。

2 無線傳感網(wǎng)離群值檢測算法

在OCSVM算法中，參數(shù)設置直接關系到整個模型的好壞，特別是容忍度參數(shù)υ跟決策參數(shù)γ。容忍度參數(shù)υ參數(shù)決定了OCSVM能識別的離群值比例，過大或者過小都會影響最終識別離群值的比例。而決策參數(shù)γ決定了整個OCSVM算法投影邊界的復雜度，γ值過大則會讓邊界過于復雜，使運算復雜度增加，反之則會讓邊界變得簡單，最后導致無法正確分離離群值。因此在導入OCSVM算法之前需要將υ與γ設置為合適的值。本文算法引入了定位算法中的錨節(jié)點，并且充分考慮各個節(jié)點之間的相關性，利用大小根堆存儲周圍錨節(jié)點的υ值，并取這些數(shù)據(jù)中的中位數(shù)作為自身的υ值。最后利用數(shù)據(jù)本身的標準差與相關性調整參數(shù)γ。

在數(shù)理統(tǒng)計中，平均數(shù)是總體均值很好的估計，中位數(shù)是對總體中心很好的估計，如果數(shù)據(jù)是來自某對稱未知分布時，估計均值和估計中心是等價的。但就穩(wěn)健性而言，中位數(shù)是較優(yōu)于平均數(shù)。因為對于均值，只要有一個點無窮大，均值則會無窮大，但改變中位數(shù)至無窮大，則需要移動一半的數(shù)據(jù)，因此中位數(shù)要比均值穩(wěn)健。

2.1 大小根堆算法設計

堆是一顆完全二叉樹，在數(shù)據(jù)結構中常常用數(shù)組模擬二叉樹，具體公式如式(3)所示。并且在堆中的某個結點的值總是大于等于(大根堆)或小于等于(小根堆)其子結點的值，并且堆中每個結點的子樹都是堆樹。

(3)

在建立堆的過程中，每來一個數(shù)據(jù)對應地插入時間復雜度為O(log2N)。并且在建堆的過程中，設總共N個元素，可以在大根堆存放m個較小的數(shù)，小根堆存放n個較大的數(shù)，當N為奇數(shù)時，應該滿足式(4)

m=n+1=(N+1)/2

(4)

當N為偶數(shù)時，應該滿足式(5)

m=n=N/2

(5)

此時，取中位數(shù)的公式如式(6)所示

(6)

各種常用取中位數(shù)數(shù)據(jù)結構的復雜度如表1所示。

表1 時間復雜度

可知，無序數(shù)組插入時間復雜度最小，適合頻繁插入，但取中位數(shù)的時間復雜度較高。有序線性表查找快，但是數(shù)據(jù)結構的維護困難。平衡二叉樹查找和維護相對均衡，但是存儲的額外信息多(指針，子節(jié)點數(shù))，查找其他元素也很快。因此大小根堆是非常適用于查找中位數(shù)的算法，但是查找其他元素效率低。

因此可以維護兩個堆，里面用來存放周圍節(jié)點的υ，從而能隨時隨地地取出中位數(shù)的υ用來改變自己算法模型的參數(shù)。

2.2 滑動窗口算法設計

但這也隨之帶來一個問題，在無線傳感網(wǎng)中不一定需要周圍所有節(jié)點的數(shù)據(jù)，可能需要不斷地更新迭代。為此，本文引入了滑動窗口的概念，在無線傳感網(wǎng)中維護一個固定大小的窗口用來存放周圍節(jié)點的數(shù)據(jù)。當有新的數(shù)據(jù)來時，更新窗口，并且取出窗口中的中位數(shù)，具體滑動窗口的示意圖如圖1所示。

圖1 滑動窗口示意圖

在大小根堆算法中，只能增加元素，而不刪除元素，因此需要增加刪除元素的操作和對添加元素的操作進行修改。并且堆不支持隨意刪除除堆頂外的任何元素，所以本算法使用延遲刪除，即，若該元素不在堆頂，則記錄下該元素，等到該元素達到堆頂?shù)臅r候再進行刪除。延遲刪除可以保證在任意操作之后保證大小根堆的堆頂元素是不需要刪除的，因此能保證隨時能取得中位數(shù)。改進后的算法示意圖如圖2所示。

圖2 滑動窗口算法流程圖

實現(xiàn)刪除與插入所需實現(xiàn)設計的函數(shù)：

(1)設計哈希表為hash=(n,num)，用來表示元素n還需要刪除num次。

(2)設計modify(heap)函數(shù)，不斷彈出需要刪除的堆頂元素，并減少對應的num值。

(3)設計balance()函數(shù)來封裝modify(heap)函數(shù)，用來調整大小根堆的元素個數(shù)。

在balance()函數(shù)中，假設小根堆為A，堆頂為a1元素，大根堆為B，堆頂為b1元素。當需要調整大小時：

(1)如果A=B，不調整；

(2)如果A-B>1，將a1放入B中，通過調用modify(A)判斷A的堆頂元素是否需要刪除；

(3)如果A>B，將b1放入A中，調用modify(B)判斷B的堆頂元素是否需要刪除。

綜上，可以得到本算法所需erase(n)的步驟：

步驟1 如果n與大小根堆的堆頂不相同，將其在hash中的值加一，待其達到堆頂后便可將其刪除，實現(xiàn)了延遲刪除。

步驟2 若相同，可以通過延遲刪除模擬立即刪除，只需要將n在hash中對應的值加一，并且調用modify(heap)函數(shù)，就相當于實現(xiàn)了立即刪除的功能

步驟3 在刪除元素后，要調用balance()函數(shù)用來調整堆的大小

因此最終可以得到大小根堆跟滑動窗口的時間與空間復雜度如表2。

表2 復雜度

2.3 動態(tài)參數(shù)設置算法設計

在OCSVM算法中，另一個重要的參數(shù)是γ，作為邊界決策參數(shù)，它與數(shù)據(jù)的標準差存在一定關系。相關系數(shù)rXY的計算公式為：

(7)

式中：Cov(X,Y)為X與Y的協(xié)方差；D(X)為X的方差；D(Y)為Y的方差，相關系數(shù)rXY越接近1則表示相關性越高，標準差S的公式為：

(8)

定義3個錨節(jié)點，每個錨節(jié)點的υ，γ都是最佳，其與待定節(jié)點的關系圖如圖3所示。

圖3 節(jié)點關系示意圖

在圖3中，N1，N2和N3為錨節(jié)點，N4為普通節(jié)點。根據(jù)標準差公式計算出錨節(jié)點中每一類數(shù)據(jù)特征的標準差。由于生活中絕大多數(shù)受隨機因素影響的事物，基本上都符合正態(tài)分布，因此標準差越大，表示數(shù)據(jù)越離散。因為參數(shù)γ是邊界條件，所以γ越大，邊界會分得越細，但γ值過大會造成過擬合。所以可以假設錨節(jié)點γ的取值公式為：

(9)

式中：F為所收集數(shù)據(jù)特征數(shù)。

假設每個WSN節(jié)點只收集溫濕度兩種特征，使用θ代表攝氏溫度，H代表濕度，αi為i節(jié)點的平均相關系數(shù)?？傻霉?jié)點1和節(jié)點4之間的計算公式：

(10)

式中：r為相關系數(shù)，則可以通過下式計算出普通節(jié)點的γ值與周圍錨節(jié)點γ值：

(11)

式中：m為錨節(jié)點數(shù)。

綜上，檢測算法的流程如下：錨節(jié)點預先設置υ值為最佳，并使用公式計算出γ值。普通節(jié)點通過尋找周圍節(jié)點υ的中位數(shù)設置υ值和利用節(jié)點之間的相關性設置γ值，并且參數(shù)設置完之后，自身也轉換成錨節(jié)點。節(jié)點通信示意圖如圖4所示。

圖4 節(jié)點通信示意圖

3 實驗仿真

3.1 數(shù)據(jù)與仿真環(huán)境

本文探討的數(shù)據(jù)來源于文獻[17]，文章作者將其放入kaggle網(wǎng)站開源。整個數(shù)據(jù)集由9個ZigBee無線傳感器網(wǎng)絡收集溫濕度而成。整個收集時間從一月到五月，共137 d，溫濕度每10 min內取一次平均值，每個節(jié)點各收集了19 735組溫濕度數(shù)據(jù)。從整個數(shù)據(jù)集來看，其涵蓋了4.5個月的范圍，使數(shù)據(jù)集有很好的完整性。并且其節(jié)點所處的環(huán)境具有差異性，有室內室外，室內還有不同的環(huán)境，如：浴室、臥室以及大廳等，這樣保障了數(shù)據(jù)的多元性，從而保證仿真實驗的真實性與有效性。

整個仿真實驗設備使用第5代Intel Core i5CPU，12 GB RAW，開發(fā)平臺使用JupyterLab，scikit-learn，語言使用Python。

3.2 時間性能分析

在無線傳感網(wǎng)中，單個節(jié)點的內存、運算能力以及電池能量都是極為珍貴的，所以整個算法的運算時間不宜太久，不然資源一直被占用會影響正常工作。

由于無線傳感網(wǎng)的節(jié)點數(shù)可以非常大，因此用模擬數(shù)據(jù)檢驗查詢中位數(shù)的性能。本文選擇3種算法進行比較，滑動窗口、只尋求中位數(shù)的快速排序，以及大根堆與小根堆。隨機產生1 000，3 000，7 000，15 000，25 000，40 000個不同的數(shù)，通過這3個算法尋找到中位數(shù)。而在滑動窗口中，每次只保存一半的數(shù)據(jù)和更新10個數(shù)據(jù)。通過比較插入時間(滑動窗口的時間取插入一半數(shù)據(jù)的時間加上更新的平均時間)與尋找中位數(shù)的時間，來綜合比較各個算法的性能，不同數(shù)據(jù)量N所需的時間t如圖5所示。

N/103

可以看出，隨著數(shù)據(jù)量N的增大，通過大小根堆取中位數(shù)所花費的時間約為快速排序方法的一半。并且，引入了滑動窗口機制后，整個算法的運行時間進一步減少。此外，從額外空間復雜度來看，大小根堆都沒有使用額外空間，都只是利用本來就存在的數(shù)據(jù)進行取中位數(shù)的過程。而快速排序有O(log2N)的額外空間復雜度?；瑒哟翱趧t是在利用哈希表的時候會產生O(N)的額外空間復雜度，其與需要延遲刪除的元素有關。所以綜合比對下來，通過大小根堆和滑動窗口取中位數(shù)的算法合適。

3.3 相關性驗證與計算

在數(shù)據(jù)集中，一共有9個節(jié)點，稱節(jié)點1到節(jié)點9。其中，節(jié)點6處于戶外，其濕度晝夜溫差大與其余節(jié)點差異過大，為了避免出現(xiàn)較大偏差，所以將節(jié)點6去除，只分析余下8個節(jié)點。利用θ代表攝氏溫度，H代表濕度，建立數(shù)據(jù)分布圖，觀察是否為正態(tài)分布，結果如圖6、圖7所示。

θ/℃

H

從圖6與圖7可以得出大部分的數(shù)據(jù)都接近于正態(tài)分布，因此節(jié)點數(shù)據(jù)的相關性可以通過式(7)計算，并且整個相關性如圖8所示。

在圖8中，顏色越深代表越不相關，越淺則代表越相關，可以觀察出不同節(jié)點不同數(shù)據(jù)特征之間存在一定的相關性，只是這種相關性有強有弱。

圖8 相關性

3.4 綜合性能分析

在OCSVM中，容忍度參數(shù)υ跟決策參數(shù)γ決定了整個算法的好壞。因此，在容忍度參數(shù)υ中，預先設置錨節(jié)點的參數(shù)υ與參數(shù)γ為最佳，周圍的普通節(jié)點通過大小根堆與滑動窗口來獲取自身的υ值。而參數(shù)γ，則是在驗證相關性后之后，通過公式11自適應進行計算得出。獨立重復做仿真實驗5次，每次選取3個不同的錨節(jié)點，第1次錨節(jié)點為2，4，8，第2次錨節(jié)點為1，3，4，第3次錨節(jié)點為3，5，8，第4次錨節(jié)點為1，7，9，第5次錨節(jié)點為2，4，7，通過式(11)計算出的參數(shù)γ值如表3所示。

表3 γ參數(shù)

可以看出，在大部分的情況下，自適應獲得的參數(shù)與最佳參數(shù)相比，只有20%～30%的誤差，其中有部分參數(shù)與最佳參數(shù)接近一致。其誤差大小與錨節(jié)點的選擇有關，即事先要選取好錨節(jié)點，且錨節(jié)點之間不能相距過近，以免出現(xiàn)參數(shù)設置過于相近的情況。

在獲取最佳參數(shù)設置后，還需要驗證在所得參數(shù)設置下的算法是否將大部分正確的數(shù)據(jù)分離出來?；煜仃嚨亩x如表4所示。

表4 混淆矩陣

為了檢驗上述參數(shù)設計對數(shù)據(jù)分離的效果，使用真陽性率T與假陽性F來進行比對，其T定義是算法正確分類且本身為正例的比例，F(xiàn)定義是將負例預測為正例的比例，公式定義如下：

(12)

(13)

將參數(shù)導入OCSVM算法中，其中圓形的折線為最佳參數(shù)，其余折線分別為1～5次獨立重復實驗的結果，所得結果如圖9與圖10所示。

節(jié)點編號

從圖9中可以發(fā)現(xiàn)，整個算法的真陽性率T基本上保持在84.3%以上，這意味著絕大部分正常數(shù)據(jù)都被正確分離出來，而假陽性率F則大部分都在20%以下，這表明可以將大部分的異常數(shù)據(jù)分離出來。最后可以得出，參數(shù)γ與數(shù)據(jù)的相關性有關，并且可以良好通過滑動窗口、大小根堆所選擇的參數(shù)υ將數(shù)據(jù)集的正常與異常的數(shù)據(jù)分離出來。

節(jié)點編號

4 結論

本文以自適應調整無線傳感網(wǎng)中離群值檢測算法的參數(shù)為目標，結合錨節(jié)點與相關性提出了基于錨節(jié)點的無線傳感網(wǎng)離群值檢測算法。該算法以錨節(jié)點與節(jié)點屬性之間相關性為基礎，利用大小根堆、滑動窗口和標準差來動態(tài)地調整待定節(jié)點的參數(shù)，并將其轉換為錨節(jié)點，循環(huán)往復地拓展到整個無線傳感網(wǎng)，最終每個節(jié)點都能自適應地將參數(shù)調整為最佳。實驗結果表明，在不使用額外的空間的情況下，利用大小根堆尋求中位數(shù)能夠保持較低的運行時間。若可以使用一定的額外空間，利用滑動窗口機制則能夠更進一步降低運行時間。并且也證實了標準差與參數(shù)γ存在一定的關系，可以通過相關性與標準差來設置參數(shù)γ，結果表示本文提出的算法能較好地辨識出正常數(shù)據(jù)。在自適應調整方式下，檢測算法的真陽性率在84.3%以上，假陽性率在20%以下，并且能夠將數(shù)據(jù)正確的分離出來。并且該算法適用于許多小型室內的無線傳感網(wǎng)，這些網(wǎng)絡必須事先將算法模型導入進去用來實時監(jiān)控，并且傳感器的CPU與內存資源有限。因此可以通過本文所提出的算法來進行設置參數(shù)，以達到比較良好的數(shù)據(jù)監(jiān)測與分離的作用。