基于深度信念網絡的高維傳感器數據異常檢測算法*

金 鵬,夏曉峰,喬 焰,3*,崔信紅

(1.安徽農業大學信息與計算機學院,合肥 230036;2.國家開發銀行信息科技局,北京 100000; 3.北京郵電大學網絡與交換技術國家重點實驗室,北京 100876)

隨著物聯網的普及,無線傳感器網絡WSNs(Wireless Sensor Networks)已經被廣泛地應用于各個領域,通過分析與挖掘傳感器所采集上報的數據,能夠為各個行業提供極具價值的有效信息。然而復雜的部署環境以及傳感器自身的內存、CPU以及能源的條件非常容易使傳感器發生軟硬件故障,從而產生異常數據,而對摻雜異常數據集合的分析會嚴重影響有效信息的挖掘及關鍵決策的制定。因此實時準確地檢測出無線傳感器網絡所采集的異常數據變得愈發重要。及時檢測出異常數據一方面可以更好的保證傳感器所采集數據的安全性和可靠性;另一方面,異常數據在某些監測環境下能夠發揮重要的作用,例如,可通過采集到的異常數據來判斷是否發生了某種突發事件(如火災、空氣污染、洪水及人為破壞等)[1-3]。然而,隨著傳感器網絡規模的不斷擴大,及所采集數據的日趨復雜,對傳感器數據異常的檢測變得越來越困難,主要表現為以下幾個方面:①無論是分布式還是集中式的數據處理,均要求對異常數據的檢測要具備較低的時間和空間復雜度,從而應對海量的采集數據;②由于傳感器通常實時地采集并上傳數據,因此要求數據的異常檢測需要具備在線檢測的能力;③現如今,越來越多的數據呈現高維的特征(一個數據項包含溫度,濕度,光照,坐標,位移等諸多維度),高維數據一方面會增加異常檢測的計算時間,另一方面若異常僅出現在少部分維度上,則這些異常數據很難與正常數據相區分。

過去的幾年中,已經有不少學者提出了無線傳感器網絡的異常數據檢測方法,主要可以分為以下四類:基于近鄰的方法[4-9]、基于聚類的方法[10-11]、基于統計的方法[12-13]以及基于分類的方法[14-16]。基于近鄰的方法通過計算自身數據與相鄰節點數據之間的距離來確定自身數據是否異常,如果某個數據與鄰居節點采集的數據存在較大差異則稱為異常數據,但是計算每個數據之間的距離會花費較長的時間,無法應用在大規模傳感器網絡中;基于聚類的方法通過對數據分簇來孤立異常數據,但此方法需要在得到全部數據后再進行分簇,不能在線式地檢測異常數據。基于統計的方法是利用歷史數據分布,建立數據的統計模型,不符合該模型的數據視為異常數據。但對于維度較大的數據集合,該方法很難建立較準確的統計模型。基于分類的方法通過歷史數據訓練得到一個分類模型,再將待檢測數據分類到所屬的模型之中,不屬于任何類型的數據,將視為異常數據。該方法能夠在保證檢測準確度的情況下滿足在線檢測的需求,并可應用于高維數據集合的異常檢測,是近幾年較為主流的異常檢測方法。其中基于單類支持向量機OCSVM(One-Class Support Vector Machine)的異常檢測方法是目前應用最廣泛的基于分類的異常檢測方法之一,它能在無監督模式下高效實時地檢測所采集數據中的異常數據。但OCSVM也存在重要的缺陷,由于在訓練過程中需要求解非線性規劃問題,當數據維度增加時,訓練時間會呈指數級增加。為了解決以上問題,文獻[17-18]提出了可利用深度信念網絡DBN(Deep Belief Network)對采集到的數據做降維處理,再對降維后的數據進行異常分類,這樣能夠大大降低OCSVM的訓練時間。但經過降維后,僅有較明顯的(即出現異常維度較多的)異常數據能夠保持與正常數據的較大差異,而不明顯的(出現異常維度較少的)異常數據經過降維后,OCSVM無法再將其與正常數據區分,從而導致較低的檢測準確度。

其中文獻[4]提出一種預測模型,對依據傳感器節點的以往數據進行分析并對給出預測值,將實測值與預測值之間的差距來發現其中的異常數據,實現了傳感器數據的實時檢測,提高了算法的效率;但是預測模型不適合處理高維的數據。文獻[12]提出了一種基于數學統計的算法,利用核函數對收集的數據進行異常檢測,從而找出異常數據;但是該方法需要大量的數據,無法實現實時監測。文獻[8]中提出了一種基于距離的數據流異常檢測算法,該算法使用滑動窗口來實現數據截取檢測,從而實現實時的檢測,該方法比前面的嵌套循環算法有較大的改進,但是沒有考慮到從窗口離開的數據對新檢測的數據的影響。文獻[14]提出了一種基于超球面的單類支持向量機,通過得到最小半徑的超球面來實現數據異常的檢測,超出計算得知的超球面,并被視為異常值。但是這個算法需要高的二次優化。文獻[15]提出了一種基于四分之一球面的支持向量機,通過計算得到以原點為中心的四分之一超球面,該方法將原本單類支持向量機中二次優化問題轉化為線性問題,從來減少復雜度,但是不能實現實時檢測,并且建模過程復雜。

本文在以上研究的基礎上,針對OCSVM進行優化,提出了一種基于DBN的1/4超球面支持向量機QSSVM(Quarter-Sphere Support Vector Machine)異常檢測模型,并在此模型基礎上提出一種在線式的異常檢測算法。首先將高維數據利用DBN進行降維處理,再針對降維后的數據通過QSSVM結合滑動窗口模型實現高效實時的異常檢測。經實驗表明,新算法可以更好地處理大規模高維傳感器數據,在降低了時間復雜度的同時,提高了異常檢測的準確度。總結來說,本文主要在傳感器數據異常檢測領域做出以下貢獻:

①提出了DBN-QSSVM異常檢測模型。實驗表明,經過DBN的降維,原數據集合中的異常數據呈線性不對稱的分布,而傳統的更適用于對稱分布的單分類支持向量機在處理不對稱分布數據時,容易得到有偏的超球面半徑。因此,當待檢測數據僅有部分維度異常時,異常數據與正常數據雖在高維映射空間存在少量差異,但對于單分類支持向量機卻難以區分。而本文提出的新模型所訓練得到的QSSVM更適用于區分不對稱分布的異常數據,在僅有部分維度異常的情況下,仍具備較高的檢測準確度;

②提出了基于滑動窗口的在線式異常檢測算法。由于傳感器所采集的數據具備一定的時間相關性,因此,所采集數據的分布會根據時間的推移而發生變化,根據當前窗口數據所訓練的模型相比單一歷史數據所訓練的模型更具實時性。本文在新模型基礎上提出基于滑動窗口的在線異常檢測算法,一方面能滿足在線式檢測的需求,另一方面能利用數據的時間相關性提高在線檢測的檢測準確度;

③實驗采用真實傳感器數據驗證了新算法的有效性。本文實驗收集了UCI機器學習庫中的四個真實的高維傳感器數據集合(Forest數據,GAS數據,DSA數據和HAR數據),并與先前基于單分類支持向量機的異常檢測方法做了對比,實驗結果表明,平均情況下,新方法能夠將檢測準確度提高17.57%,誤檢率降低20.02%。此外,本文提出的新模型將原有模型中的非線性規劃問題轉換為線性規劃問題,相比原有方法,新方法將訓練時間和檢測時間之和降低了約50%。

1 背景知識及問題描述

本節首先介紹單分類支持向量機(OCSVM),1/4超球面支持向量機(QSSVM)及深度信念網絡(DBN)的基本概念和原理,然后通過實驗數據說明QSSVM相比傳統OCSVM在處理DBN降維后的數據時更具優越性。

圖1 OCSVM超球面分類模型

1.1 單分類支持向量機(OCSVM)

OCSVM按照大部分輸入數據在高維空間中的相互距離將輸入數據進行單分類,并將待檢測數據中不屬于該分類的數據視為異常[19]。TAX等人[20]提出的基于超球面的支持向量機將在低維空間中不可分的數據映射到高維特征空間,并找到一個可以包圍絕大部分樣本點的超球面,將排除在超球面之外的樣本點作為異常樣本。圖1為超球面OCSVM異常檢測模型,圖1中位于球面邊緣的白色樣本點表示邊界支持向量,球面內部的灰色樣本節點是正常數據,球面以外的黑色樣本節點是異常樣本數據,其中超球面的半徑R表示球心到邊界支持向量之間的距離,由邊界支持向量機與球心的距離決定。

假設X={xi,1≤i≤n}為n個訓練樣本數據,特征空間中訓練樣本球面半徑的計算可規劃為以下問題的求解:

(1)

s.t. ‖Φ(xi)-C‖2-R2≤ξiξi≥0,i=1,2,…,n

其中Φ(·)為樣本到高維特征空間的映射函數,R和C分別為高維空間中超球面的半徑和球心,ξi是松弛變量,允許部分樣本在球面之外,v∈(0,1)為在球面之外樣本的比率。式(1)的對偶形式可表示為:

(2)

其中k(xi,xj)=Φ(xi)·Φ(xj)是核函數,表示xi和xj在高維特征空間的距離。在特征空間中,任意樣本x與球心的距離可通過以下公示計算:

(3)

當d≤R時,x為正常節點,當d>R時,其為異常節點。

圖2 QSSVM分類模型

1.2 1/4超球面支持向量機(QSSVM)

由于OCSVM需要在模型訓練時求解二次規劃問題(式(2)),時間復雜度較高,P Laskov在文獻[15]中提出單類QSSVM,將二次規劃問題轉化為線性規劃問題,從而降低了時間復雜度。QSSVM將輸入樣本映射到高維特征空間,并將特征空間中樣本的圓心移到坐標軸的原點,以正坐標軸為方向,得到一個1/4超球面,在球面內部的數據,為正常樣本數據,球面外部的數據為異常樣本數據,圖2為QSSVM分類模型。

訓練樣本X={xi,1≤i≤n}在特征空間的1/4球面可通過求解以下問題得到:

(4)

s.t. ‖Φ(xi)‖2≤R2+ξi

ξi≥0,i=1,2,…,n

式(4)的對偶問題可表示為:.

(5)

相比球面OCSVM的非線性規劃問題(式(2)),式(5)的線性規劃問題將計算復雜度大大降低。

但由于基于距離的核函數k(xi,xi)對于任何樣本節點均相等,因此式(5)無法求得有意義的解。以上問題可以通過將核函數中心化的方法得到解決[21],即定義中心化后的核函數為:

kc=k-1nk-k1n+1nk1n

(6)

其中1n為n×n的矩陣,矩陣元素均為1/n。此時式(5)可轉換為:

(7)

對于新到的樣本節點x,其在高維特征空間中與原點的距離無法通過簡單公式得到,因此QSSVM目前僅能作為離線式的異常檢測技術。在2.2小節本文將通過滑動窗口模型實現QSSVM的在線檢測。

圖3 RBM模型

1.3 深度信念網絡(DBN)模型

1.3.1 受限玻爾茲曼機(RBM)

受限玻爾茲曼機[22]RBM(Restricted Boltzmann Machine)是一種概率神經網絡,主要由兩層神經元構成,分別稱為隱藏層和可見層。如圖3所示,h為隱藏層神經元狀態向量,v為可見層神經元狀態向量,向量b是隱藏層的偏執系數,向量a為可見層的偏執系數,每一層之間的神經元相互獨立,隱藏層與可見層之間是全連接關系。

1.3.2 深度信念網絡(DBN)

深度信念網絡[23]是由多個RBM疊加合成的深度學習網絡。如圖4所示,該網絡通過對RBM一層一層的訓練,下層RBM的輸出作為上層RBM的輸入,在 DBN 的最后一層設置 BP神經網絡,用來接收RBM訓練后的特征數據。由于每一層RBM的訓練都只能保證自身的最優,因此一層一層訓練也無法保證全局最優,BP神經網絡能夠將得到的數據與期望數據比對,并進行自頂層向下的調整從而優化訓練結果。

圖4 DBN模型

此外,DBN還可作為數據的降維工具,將高維的輸入向量X∈Rn×d通過DBN進行壓縮提取后,輸出低維的特征向量Y∈Rn×s,其中s

1.4 降維后傳感器數據特征

通過DBN對高維數據降維后,正常數據與異常數據的分布呈現較明顯差異,并且異常數據不對稱地分布在正常數據一邊。本文從UCI機器學習庫網站下載了四組真實傳感器數據,分別為Forest(森林環境監測數據,54維),GAS(基于傳感器檢測的氣體種類集,128維),DSA(日常活動集,315維)和HAR(基于智能設備穿戴的人類活動集,561維),并在這些數據中隨機地加入了少量異常(具體實現方法見3.1節),降維后的數據分布如圖5所示(為了易于呈現,統一把數據降到3維)。從圖中可以看出,在四張圖中異常數據(圓點)分布在正常數據(方點)的一側,而非對稱地分布在其周圍。而傳統的單分類支持向量機所得到的球面以輸入數據在高維空間的中點為圓心,能夠較好地分割相對圓心對稱分布的異常數據。在數據呈單側分布時,圓心的定位會存在少量偏差,因此無法保證異常數據的檢測準確度。QSSVM將輸入數據在高維空間中平移,并以原點為圓心確定1/4球面,更適用于異常數據分布于單側的異常檢測問題,相比傳統的OCSVM具有更高的檢測準確度。

圖5 DBN降維后的數據分布特征

2 基于深度信念網絡的傳感器數據異常檢測算法

本節首先建立DBN與QSSVM混合模型(包括訓練模型和測試模型),再利用滑動窗口模型實現在線式地異常檢測。

圖6 訓練模型

2.1 DBN與QSSVM混合模型

DBN與QSSVM混合模型分為訓練模型和測試模型,如圖6和圖7所示。訓練模型用于DBN降維模型的訓練及訓練數據中異常數據的剔除,測試模型用于實時檢測新到數據是否為異常。

圖7 測試模型

在訓練模型中,將訓練數據輸入給DBN底層節點,訓練DBN中各層之間權值W,顯層節點偏執和隱層節點偏執(a,b,c),并將降維后的訓練數據輸入給QSSVM并輸出訓練數據中的異常數據,在訓練數據集中將異常數據剔除,如圖6所示。

在測試模型中,將新采集到的待檢測數據輸入給訓練好的DBN模型,輸出降維后的測試數據,并加入到滑動窗口中,最后將窗口數據輸入到QSSVM,檢測新到數據是否為異常,如圖7所示。

2.2 滑動窗口模型實現在線檢測

由于傳感器所采集的數據具備一定的時間相關性,所采集數據的分布會根據時間的推移而發生變化,因此采用滑動窗口模型將新采集的數據與最近時間數據放在同一窗口中,輸入給QSSVM進行異常檢測。一方面,通過窗口的滑動能夠實現實時地在線數據檢測,另一方面,利用數據的時間相關性,能夠提高異常檢測的準確度。

滑動窗口模型如圖8所示,m為滑動窗口大小,窗口1和窗口2分別t-1時刻和t時刻的窗口,白色點表示已檢測樣本,黑色點為待檢測樣本。在下一個時刻采集到新數據時,窗口向右滑動,將待檢測樣本滑入窗口中,并將部分已檢測樣本滑出窗口。最后將新窗口中的樣本數據輸入到QSSVM模型中檢測樣本是否為異常。

圖8 滑動窗口模型

2.3 基于深度信念網絡異常檢測算法

表1 算法偽代碼

3 實驗

本節將本文提出的新算法QSSVM與文獻[17]提出的基于DBN降維的OCSVM方法、文獻[11]提出的K-Means算法以及文獻[4]提出的DBSCAN算法作了對比,其中本文針對K-Means算法和DBCSAN算法,結合本文中提及的滑動窗口加以改進。實驗結果從不同性能角度證明了QSSVM算法的優越性。

3.1 數據集與實驗設置

實驗數據是從UCI機器學習庫網站下載的四組真實傳感器數據集,分別為:54維的Forest(森林環境監測數據)、128維的GAS(基于傳感器檢測的氣體種類集)、315維的DSA(日常活動集)和561維的HAR(基于智能設備穿戴的人類活動集)。從每個數據集中挑選連續時間的1000個樣本數據,并將前80%數據(即800個樣本)作為訓練數據,隨機加入5%的異常數據,將后20%的數據作為測試數據(即200個樣本),隨機加入10%的異常數據,并假設每個時間間隔有10個測試樣本被采集。所有樣本數據歸一化到[0,1]區間上,所有加入的異常數據從[0,1]區間的均勻分布隨機產生。

為達到最佳算法性能,通過多次實驗對比,本文選取了兩層的DBN結構,將輸入數據降到6維,QSSVM與OCSVM均選用RBF核函數。所有算法用MATLAB R2017a實現,并在1.9 GHz雙核CPU,32GB內存的專用服務器上運行,每個實驗結果均為10次獨立實驗的平均值。

3.2 算法性能指標

表2 算法性能指標

實驗測量的算法運行時間是從輸入訓練數據和測試數據開始,到算法輸出所有異常數據為止。

3.3 實驗結果與評價

本小節以圖表的形式比較了QSSVM與OCSVM、K-Means及DBSCAN的檢測準確度(檢測率,誤判率和召回率)及計算時間,同時評價了滑動窗口大小對QSSVM性能的影響。

3.3.1 算法效率及窗口大小影響

表3比較了兩個算法訓練模型及檢測異常的運行時間總和,及不同大小窗口下QSSVM的準確度變化。由于不同數據集合,不同異常維度比率對算法時間幾乎沒有影響,本小節所記錄的時間為所有異常維度比率情況下,在四個數據集合中算法運行時間的平均值。從表3中可看出,隨著窗口的增大,QSSVM的準確度是逐漸增加的(即檢測率與召回率逐漸增加,誤判率逐漸下降),這是因為窗口越大,窗口內包含樣本數據越多,每次在計算球面半徑時能參照的正常樣本數也會越多,得到的半徑也更加精確。

記樣本數為n,QSSVM算法使用RBF核,其最內層運算次數為n2次,時間復雜度為,核函數中心化方法解決對角線問題,其運算次數為n次,時間復雜度為,滑動窗口循環m次,時間復雜度為,即,則時間復雜度為。另外K-Means算法的時間復雜度為,DBNCAN算法的時間復雜度為,OCSVM算法的時間復雜度為。表3比較了四個算法的計算效率,K-Means、DBSCAN和QSSVM算法的運行時間都隨窗口的增大而增加,當窗口大小為100時,QSSVM的計算時間比OCSVM低50%左右,當窗口增大到包含200個樣本數據時,QSSVM算法與OCSVM算法的計算時間相近,K-Means和DBSCAN由于其時間復雜度較低,故低于QSSVM。

表3 不同窗口值下算法性能的比較

考慮到當窗口增加到一定程度時,能獲得的準確度越來越少,因此為保證算法的計算效率,在以下的準確度實驗中,將QSSVM算法的滑動窗口大小固定在100。

3.3.2 檢測率(DR)

圖9比較了四個算法在不同比率維度出現異常時的檢測準確度。從四組數據對應的四張圖中可以看出,隨著樣本維度異常比例的增加,四個算法的檢測率均呈上升趨勢,這是因為經過DBN的降維,異常數據與正常數據樣本偏差會隨著異常維度的增加而增大。QSSVM在Forest數據(54維)和GAS數據(128維)時略低于K-Means和DBSCAN,但隨著樣本維度的增加,QSSVM依舊可以表現出良好的檢測性能,K-Means檢測結果卻越來越差,在HAR數據(561維)時,檢測率最高僅有45.68%,而此時QSSVM最高可以達到93.07%,DBSCAN一直保持較高的檢測率,在隨著樣本維度增加時,較低的維度異常比例的異常數據無法被檢出,此時,DBSCAN表現出的召回率卻很低,表示只檢測出了部分的異常數據。QSSVM一直處于OCSVM的上方,大多數情況下,相比OCSVM,QSSVM檢測準確率高約20%。

圖9 不同異常維度比率下的異常數據檢測率

圖10 不同異常維度比率下的異常數據誤檢率

3.3.3 誤檢率(FPR)

圖10呈現了四個算法在不同比率維度出現異常時的誤檢率。從圖中可以看出,隨著樣本維度異常比例的增加,四個算法的誤檢率均呈下降趨勢。實驗結果表明,QSSVM在Forest數據(54維)和GAS數據(128維)時略高于K-Means和DBSCAN,但在隨著樣本維度增加時,K-Means在HAR數據(561維)時表現出較高的誤檢率,DBSCAN在低緯度異常時,也表現出高的誤檢率,此時,DBSCAN表現出的召回率卻很低,表示只檢測出了部分的異常數據。在所有情況中QSSVM的誤檢率均遠低于OCSVM,一般情況下,相比OCSVM,QSSVM誤檢率低20%～50%。

3.3.4 召回率(Recall)

圖11呈現了四個算法在不同比率維度出現異常時的召回率。隨著樣本維度異常比例的增加,四個算法的召回率均呈上升趨勢。一般情況下,QSSVM的召回率相比其他算法具有明顯優勢,僅在HAR數據時QSSVM的召回率低于K-Means,此時K-Means表現出較低的檢測率和較高的誤檢率,而此時QSSVM依舊表現現高的檢測率和低的誤檢率。

圖11 不同異常維度比率下的異常數據召回率

綜上,在QSSVM窗口值為100時,舍棄算法本身的時間復雜度的同時,獲得了更好的檢測結果,尤其在處理高維數據時,檢測結果明顯優于其他算法。特別地,當異常數據樣本僅有部分維度出現異常時(異常維度比率60%以下),QSSVM仍能表現出較高的檢測準確度。

4 總結

本文提出了一種基于深度信念網絡的傳感器數據異常檢測算法。該算法首先使用DBN對高維數據進行降維處理,再利用QSSVM結合滑動窗口模型實現了對降維后數據的在線實時檢測,實驗結果表明,相比先前異常檢測算法,新算法在對高維數據進行異常檢測時,舍棄算法自身的時間復雜度的同時,獲得了更好的檢測結果,尤其在處理高維數據時,檢測結果明顯優于其他算法。相比ocsvm可將檢測準確度提高約20%,誤判率降低20%～50%,同時計算時間僅為原有算法的一半。因此,本文提出的新方法為傳感器數據的處理與應用提供了重要的參考。

本文利用DBN實現了數據特征的提取從而達到對高維數據降維的目的,但針對不同數據集合特征,所提取特征個數應有不同,而本文實驗中對四組數據集合未做區分處理。在未來研究工作中,將繼續研究DBN所提取的特征對于異常檢測的影響,針對不同數據集合從理論上給出最適合的降維模型,從而使降維后的異常數據與正常數據存在更大的區分度。