基于時空相關性的多傳感器數據異常檢測

柳月強 張建鋒 祝麒翔 楊會君

(西北農林科技大學信息工程學院 陜西 楊凌 712100)

0 引 言

傳感器持續采集的數據構成數據流，每一個傳感器所產生的數據流具有連續、實時、高速等特征[1]。受傳感器數據概念漂移、運行環境以及傳感器部署方案等因素的影響，傳感器數據具有不確定性[2]。應用異常檢測技術對部署在同一物理環境下的多個傳感器數據流進行分析，將在一定程度上提高傳感器數據的準確性和有效性[3]。傳感器在對物理環境進行感知的過程中可獲得在時間上連續的離散點，數據觀測值與時間之間的關聯關系稱之為數據的時間相關性，傳感器數據流也稱為時間序列。在傳感器網絡部署中往往會利用不同類型的多個傳感器對物理空間進行全面感知，這些不同類型的傳感器數據間具有的關聯關系稱為數據的空間相關性。根據無線傳感器網絡(WSN)的特點，將異常檢測的方法分為基于統計、基于分類、基于聚類、基于近鄰等方法。單傳感器數據流通常利用數據的時間相關性進行異常檢測，多應用基于統計分析、基于最近鄰距離等方法進行異常檢測[4-5]。多傳感器數據流同時具有時間和空間相關性，通常應用基于聚類的方法進行檢測，在應用聚類的過程中往往會忽略傳感器的時間相關性。

單傳感器數據流異常檢測是多傳感器數據流異常檢測的基礎。段青玲等[6]應用滑動窗口和支持向量回歸相結合的方法，預測傳感器的測量值，確定置信區間，根據傳感器的實測值是否在區間內來判斷數據是否異常。苑進等[7]采用高斯過程對溫室中真實傳感器數據進行單步預測，通過計算數據區間差異度來判斷異常，以上方法均無法對傳感器數據的多維度、屬性關聯等因素進行預測。Sarvani等[8]應用K-means算法對具有5個屬性的鳶尾花數據進行聚類分析，與傳統方法相比，基于聚類的孤立點剔除(ORC)技術取得了更好的效果。而DBSCAN空間算法以其對小樣本數據聚類速度快、有效處理噪聲點、發現任意形狀等優勢備受關注，在異常檢測技術領域也有研究，但目前應用較少。

本文提出一種基于時空相關性的多傳感器數據異常檢測方法，首先利用最近鄰距離差算法實現數據流在時間序列上的孤立點和孤立群檢測；再應用DBSCAN聚類算法對最近鄰距離差異常處理后的數據集進行空間相關性聚類，實現多傳感器數據流的異常檢測。

1 相關定義與技術

1.1 異常點定義

異常點是指當前數據觀測值與其他歷史數據觀測值之間有較大偏差的離群點，是一種由不同于正常的機制所產生的點[9]。不同的異常現象將會導致不同的數據異常，采取的措施也會有所不同。Shikha等[10]通過對物聯網環境的研究，將產生異常的原因分為兩種，即事件和錯誤。

(1)事件：指與預定義的“通常行為”相比，物理環境狀態突然發生劇烈變化。一類是人類所不能控制的自然災害如地震、火山等；另一類是由人類自身活動導致物聯網系統受到攻擊而無法工作。事件通常持續時間較長，同時會改變傳感器數據的歷史模式。

(2)錯誤：指由于傳感器數據噪聲、數據概念漂移，導致無線傳感網絡傳輸丟幀、網絡延緩等而造成觀測值不匹配且反復出現的一種變化。

本文只研究因錯誤導致的異常現象，將異常點定義為點異常、集體異常和關聯異常，其定義如下。

點異常：指單數據的實例與數據的正常模式不同，也可稱為數據跳躍。該異常點的觀測值與近鄰觀測值差異明顯，最易識別；集體異常：指一組連續的數據實例，其模式與整個正常模式不同；關聯異常：指數據實例在特定場景下發生的異常，也可稱為條件異常。

1.2 相關技術

最近鄰距離差的基本思想是度量對象之間的近鄰性，異常對象是指近鄰度較小的對象[12]。算法的優點在于時間復雜度低，可以有效地應用于時間序列異常檢測。近鄰距離差算法適合用于各種維度的數據集，假設數據集X的數據對象總數為N，數據維度為M，數據集X可表達為:

X={xi|xi∈RM,1≤i≤N}

(1)

其中數據對象xi為：

xi={xi1,xi2,…,xiM}

(2)

相鄰對象之間的距離為：

Dij={|Xi-Xj|,1≤i≤N,1≤j≤N}

(3)

該方法在判斷異常的過程中需要設置數據的鄰差閾值，通過鄰差閾值與測量值的比較來判斷是否異常，由于數據在不同的情況下波動不均衡，所以固定的閾值將會對數據的異常檢測造成不好的影響。

DBSCAN是一種將足夠密度區域作為聚類中心，不斷生長該區域的基于密度的空間聚類算法，其聚類原理如圖1所示，參數Eps為圓半徑，參數MinPts為鄰域內樣本點數，在本例中MinPts≥4。圖中以A點為核心點，Eps為半徑，鄰域A中包含A、a1、a2、a34個點，選擇Eps鄰域的邊界點繼續拓展鄰域得到新的邊界點如點B、點C所示，隨著樣本點不斷擴散，N在所有鄰域之外，則被標記為離群點。圖中A在a1鄰域內，A與a1直接密度可達，A同時也在a3鄰域內，所以a1與a3密度可達。點C與a3密度可達，a3與a1密度可達，則可知點C與a1密度相連，進而尋找到密度相連對象的最大集合即為聚類結果。由于DBSCAN算法采用的是全局參數，在處理不平衡數據時聚類效果不穩定且在大樣本聚類中收斂時間長，因此降低全局參數影響是DBSCAN算法首要解決的問題[11]。

圖1 DBSCAN算法原理圖

2 基于時空相關性的異常檢測算法

本文針對環境傳感器數據的特點，應用參數優化來提升算法性能，將改進后的K近鄰距離差(KNND)與聚類算法(PO_DBSCAN)結合，從時間和空間兩個角度分析多傳感器數據異常檢測的問題。在檢測數據的時間相關性中，應用最近鄰距離差算法的動態閾值克服傳感器數據在時間序列上波動不均勻的問題，通過K個近鄰點的距離差排序計算數據異常得分，然后采用得分最高點的2K個近鄰點的距離均值來優化鄰差閾值，完成異常檢測。在DBSCAN算法中，采用滑動窗口模型為多傳感器數據流設置固定的窗口大小和窗口重疊率，將數據集劃分為等量小樣本。DBSCAN算法聚類的參數可根據窗口內部樣本特征設置，克服算法采用全局參數、大樣本收斂慢的問題，完成異常檢測。本文算法包括最近鄰距離差算法、DBSCAN算法參數優化與異常檢測三部分。

2.1 KNND參數優化

傳統的最近鄰距離差算法對局部數據不均勻波動的處理具有局限性，受文獻[12]的啟發，本文提出一種新的基于K近鄰距離差的異常檢測方法。通過參數優化，將會有效地解決各個傳感器在時間序列上的異常問題，其步驟如下。

Step1獲取所有傳感器數據流，按照式(3)計算數據之間的距離差Dij。

Step2設置近鄰參數K，以K為窗口大小，窗口滑動步長為1，初始化異常得分S=0。

Step3對窗口內點之間的距離差進行排序，選擇距離差較大的q個點為距離優勝點，并對其異常得分S加1，滑動窗口循環求出各個點的異常得分S。

Step4統計標記異常得分為K的點，并求出該點左右相鄰的2K-1個點距離差的平均值mean。

Step5對異常得分為K的點進行判斷，根據環境數據的不突變性和因錯誤導致異常的可控性，定義距離差超過均值的1.5倍則標記該點為異常點。

Step6由Step 5可以確定數據中的點異常，判斷點異常處鄰近點的距離差正負變化情況，正負交替則將該點標記為異常點，直到有連續單一變化則異常停止，該過程捕獲的連續異常點數大于K則將連續數據標記為集體異常，反之為點異常。

Step7多維異常數據整合處理，對點異常通過近似值代替，消除異常；集體異常不做修改。

Step8整理數據，將K近鄰距離算法檢測并處理的數據集作為聚類算法的輸入。

2.2 DBSCAN參數優化

基礎的DBSCAN算法采用全局唯一參數Eps和MinPts實現聚類，受文獻[13]采用局部參數進行聚類的影響，本文提出一種基于滑動窗口數據劃分技術實現數據集在小樣本數據上利用局部參數進行密度聚類的方法。PO_DBSCAN聚類算法流程如圖2所示。

圖2 PO_DBSCAN算法流程

PO_DBSCAN聚類算法的聚類過程由三部分組成，分別是參數更新、聚類、異常檢測。

參數更新過程中設置聚類窗口的大小并計算窗口內各屬性間的平均距離差，以K為MinPst鄰域內點的個數，以屬性間的歐氏距離為半徑Eps，保證數據在單獨情況下聚類無誤。其公式為：

(4)

式中：yi為屬性的平均距離差；M為滑動窗口的大小。

聚類過程中采用DBSCAN算法進行聚類，針對屬性間相關性不一致的問題，通過給每一個屬性分配權重來降低對聚類效果的影響，權重WXY通過相關系數計算，其公式如下：

(5)

(6)

式中:Cov(X,Y)為屬性X與屬性Y的協方差；Var(X)為屬性X的方差；Var(Y)為屬性Y的方差。

異常檢測過程將對聚類結果進行分析，在聚類過程中將首次被標記為異常點的對象記為候選異常點，并設置異常得分加1(初值為0)，候選異常點進入下一次循環，繼續進行聚類標記，更新異常得分，異常得分S與聚類次數C(聚類次數為滑動窗口重疊率的倒數)相等則標記為異常點，反之為正常點。

2.3 ODSTC異常檢測算法

綜上所述，ODSTC算法首先利用KNND算法進行異常檢測與處理，然后利用PO_DBSCAN算法進行聚類檢測并標記，最后對所有異常點以及異常點類型進行統一標記，算法框架如算法1所示。

算法1基于時空相關性的多傳感器數據異常檢測

輸入：校試驗示范站信息服務體系項目多傳感器數據集。

輸出：通過算法檢測重新標記的異常點以及異常點所屬的類型。

1.應用滑動窗口技術劃分傳感器數據流

2.基于KNND算法對傳感器數據流進行時間特性上異常檢測

3.對KNND算法檢測出來的異常點用不同的處理方式進行處理

4.將處理后的數據集，再次利用滑動窗口模型劃分多傳感器數據流，作為聚類的輸入

5.PO_DBSCAN異常檢測算法對多傳感數據流進行異常檢測

6.對聚類異常檢測出來的異常進行標記

7.異常點統一標識，并標記異常點類型

2.4 ODSTC算法性能分析

算法的性能分析往往從時間效率和空間效率兩個角度進行，隨著計算機速度與容量的不斷提升，空間效率已經不再是關注重點，故本文著重從時間效率進行分析。

KNND算法將數據進行劃分，然后再對滑動窗口內的點進行排序，隨著窗口的滑動來檢測異常點。算法的時間頻度可表示為：

f(n)=(n-w)·w·logw

(7)

式中：n為算法輸入規模；常數w為滑動窗口大小，滑動步長為1。所以KNND算法的時間復雜度T1(n)為：

T1(n)=O(f(n))=O(n-w)=O(n)

(8)

DBSCAN算法的時間復雜度為找出半徑Eps鄰域中的點所需要的時間，在最壞情況下其時間復雜度是O(n2)。PO_DBSCAN算法是采用滑動窗口對數據進行劃分，其時間頻度可表示為：

(9)

式中:n為算法輸入規模，w為滑動窗口大小，即w2為常數，x為常數，即滑動步長為w/x，所以DBSCAN算法的時間復雜度T2(n)為:

(10)

ODSTC算法的時間復雜度為KNND與PO_DBSCAN算法時間復雜度之和，由加法法則可將ODSTC算法的時間復雜度表示為:

T(n)=O(max(f(n),g(n)))=O(n)

(11)

由此可知，ODSTC的時間復雜度呈線性增長，隨著處理數據樣本量的增大，時間效率比基礎的DBSCAN算法效率更高。在KNND算法中參數利用了時間序列的數據的不突變特性，PO_DBSCAN算法利用了多維數據的空間相關特性。充分考慮了數據相關性，有效地挖掘出數據的潛在關系，對提高算法檢測的準確率具有積極意義。

3 實驗及結果分析

為了評估ODSTC算法的性能，本文采用西北農林科技大學試驗示范站的環境數據進行實驗。實驗在Inter(R)Core(TM)i5-6400 CPU，主頻2.70 GHz，內存8 GB，操作系統Windows 10環境下進行，編程環境采用MATLAB 2016a。分別實現了DBSCAN、PO_DBSCAN、KNND以及ODSTC算法，并根據不同規模數據集和不同算法進行對比實驗。

3.1 數據集

環境數據集于2017年5月到2017年10月在西北農林科技大學千陽蘋果試驗示范站采集。環境傳感器采集周期為10分鐘，采集的物理量包括空氣溫度、空氣濕度、總輻射、風向、風速、降雨量、土壤溫度、土壤濕度，構成具有8個屬性的數據集。本文所采集的數據是集成在一個開發板上的多個傳感器分別采集的多維數據。根據數據之間的相關性強度，本文選取物理量空氣溫度、空氣濕度、總輻射、風速四個強相關的屬性進行相關性實驗。在進行對比實驗中，本文采用四組不同規模的數據集進行驗證實驗，實驗樣本記錄為1 440～8 640條，涉及數據點數為5 760～69 120個。千陽蘋果試驗示范站的環境相關數據均結合實際情況經過專家標記，異常來源均為錯誤，異常點分三類依次標。數據集詳細信息如表1所示。

表1 實驗數據集

3.2 性能評價

為了衡量算法特性，本文引入性能指標檢測率TPR(True Positive Rate)、誤報率FPR(False Positive Rate)和運行時間T。TPR是用來衡量異常值被正確標記的概率，FPR是用來衡量正常值被錯誤標記的概率，計算如下：

(12)

(13)

式中：TP表示被正確檢測出的異常值；TN表示未被檢測出來的異常值；FP表示正常值被檢測為異常值；FN表示正常值被檢測為正常值。

3.3 參數設置

基于時空相關性數據異常檢測算法分為三個步驟：首先應用KNND檢測；然后應用PO_DBSCAN算法進行聚類異常檢測；最后對異常檢測結果進行統一標記。整個算法在運行過程中需要設置的參數有：近鄰點個數K、KNND檢測滑動窗口大小w1、KNND檢測窗口滑動重疊率d1、聚類檢測滑動窗口大小w2、聚類檢測滑動窗口重疊率d2。在聚類過程中因為數據的冗余影響聚類效果，滑動窗口根據數據的變化規律以及DBSCAN算法不適合大樣本聚類的特點設定，近鄰閾值參數Threshold等于2K個近鄰元素距離差均值mean，聚類參數MinPts等于K，Eps計算見式(4)。算法所需設置的參數詳細信息如表2所示。

表2 ODSTC算法參數

3.4 實驗結果分析

實驗采用4個數據集對三種不同算法進行對比，檢測率和誤報率為數據集中三類異常點的平均值，詳細如表3所示。可以看出，本文所提出的ODSTC算法在TPR性能和FPR性能上較DBSCAN和PO_DBSCAN均有提升，隨著數據集的增大，算法的FPR平均降低0.3個百分點。對比文獻[14]與本文PO_DBSCAN算法，算法識別的準確率提升了2個百分點。對比數據集QY_3與QY_4可以發現，當算法中不相關屬性增加，算法的TPR約下降6個百分點，算法性能有所降低。由此可知本文算法在處理相關數據集時具有良好的檢測效率，但是針對數據中的不相關數據集其性能仍有待提升。綜上，本文算法與其他異常點檢測算法對比可得，前者的準確率提升較大，且誤檢率也有明顯的降低。算法的檢測效率滿足應用需求。

表3 異常檢測算法性能對比 %

本文截取數據集QY_1中空氣溫度的數據的檢測結果進行統計，其中點異常17個，聚集異常58個，關聯異常17個，檢測率為98.5%，誤報率1.5%。為了更清晰地描述異常點被標記情況，本文截取空氣溫度數據的前180個樣本點進行繪圖，檢測結果如圖3所示。空氣溫度數據的異常均在短時間內發生(每個樣本采集間隔10 min)，導致異常的原因均為錯誤。

圖3 溫度數據異常檢測結果

實驗時間效率T通過對具有相等屬性，不同樣本數的數據集QY_1、QY_2、QY_3進行對比驗證，對比結果如圖4所示。DBSCAN算法的運行時間增長速度最快，PO_DBSCAN與ODSTC算法的運行時間增長較慢，在數據集達到8 440小時，即數據點數達到337 760個時，PO_DBSCAN與ODSTC算法的運行時間少于DBSCAN算法的運行時間。結合前文對算法時間復雜度的分析可知，DBSCAN算法時間復雜度為O(n2)，PO_DBSCAN與ODSTC的時間復雜度為O(n)。當樣本量增大到一定程度，PO_DBSCAN與ODSTC算法的時間效率較DBSCAN算法必然會有所提高。圖中PO_DBSCAN與ODSTC算法的運行時間差別較小，由此可知，KNND算法時間復雜度較低。綜上，ODSTC可用于多傳感器數據流的異常檢測。

圖4 異常檢測算法時間效率對比

4 結 語

本文提出的時空相關性數據異常檢測算法(ODSTC)結合了最近鄰算法與聚類算法的思想，針對環境數據的特點對算法的參數進行優化，克服了最近鄰距離閾值固定與聚類參數全局性及收斂速度慢等問題，提高了異常檢測的效率。實驗結果表明，ODSTC算法對多傳感器數據流的檢測準確率更高，算法的時間效率也會隨著樣本量的增加而提高。針對具有相關性的多傳感器數據流，其效果滿足現行環境的使用。從實驗結果同樣也可看出，當相關性較低的數據屬性加入后，算法的效率有所降低，今后研究將進一步考慮不相關數據流的特征，提取頻域特征，結合當地氣候變化特征，從不同維度進行對照分析。