基于BIRCH 聚類算法的高維傳感器數據異常檢測?

趙 嬌

(綿陽職業技術學院電子與信息學院，四川 綿陽 621000)

將傳感器節點分布在目標范圍中，利用節點收集的周邊環境參數[1]，能有效挖掘自然環境內的突發事件和傳感器網絡的運行狀態。高維傳感器數據流具有數據量大、無法準確估測的特點，為增強無線傳感網絡的可靠性，對其采集的傳感器數據實施異常檢測變得格外重要[2]。和處理一般低維數據不同，高維數據處理具有更高的時間復雜度[3]，異常檢測時會面臨極大挑戰。

相關學者對此問題的研究內容如下:神顯豪等[4]在歸一化處理數據后，將其擬作卷積神經網絡輸入值，改進卷積層特征面與全連接層參數，通過卷積層學習異常數據特征。此方法在數據量采集時需要消耗大量時間，無法完成實時檢測預期目標。席亮等[5]使用無向圖結構提取樣本關聯特征，利用雙路自編碼器融合樣本初始特征和關聯特征，提出基于高斯混合模型的估計網絡，通過閾值計算實現數據異常檢測。但方法融合樣本特征時沒有消除冗余數據，異常檢測結果精度不高。Kim D 等[6]提出無監督異常檢測方法，該方法使用來自船用發動機的傳感器流來檢測異常系統行為，基于集成的異常檢測方法，并行訓練幾個具有不同超參數的異常檢測器，然后在異常檢測階段組合其結果。該方法的準確性較高，但耗時較長。

針對上述方法存在的問題，提出一種基于使用層次結構的平衡迭代約簡和聚類(Balanced Iterative Reducing and Clustering using Hierarchies，BIRCH)的高維傳感器數據異常檢測方案。使用線性回歸法采集高維傳感器數據并實施歸一化處理，通過BIRCH聚類分析數據屬性特征，將傳感器數據序列轉變成球形簇單元，獲得高質量異常檢測結果。

1 基于分簇處理的高維傳感器數據采集方法

高維傳感器數據采集即傳感器從待測目標環境中得到數據并安置在節點存儲器內，節點處理器利用某種方法在存儲器中獲取數據的流程。具體來說，數據采集就是在節點處理器傳遞采集指令后，智能傳感器板塊接收采集指令并實施采集工作。在此過程中，使用線性回歸法采集數據，經過如下:

部署于監控區域的傳感器節點，可按照節點信息的關聯性分割為多個簇，并假設處于相同簇內的兩個隨機節點數據為顯著線性關聯。設定傳感器網絡一個簇中涵蓋i個節點，每個節點同時采集，采集獲得長度是N的信號矢量，則節點相對的一階差分信號序列為:

式中，xi(k)代表節點i第k個時段的信號，Δxi(k)表示節點i第k個時段的一階差分信號。

若節點i、j為處在相同簇的節點，因相同簇內隨機兩個節點的數據為顯著線性關聯，節點j的一階差分信號序列和節點i的完全相等，記作:

式中，α0、α1均表示回歸指數，b是節點元素順從均值為0 的高斯分布。

節點i使用等間隔策略[7]采集高維傳感器數據，將采集后的信號矢量xi通過多跳路由傳輸到網關節點，使用高斯隨機矩陣Φ投影節點j的一階差分信號，計算公式為:

式中，zj是針對采集值組成的矢量。

倘若處于監控范圍的傳感器節點數量為B，則網關節點接收的數據可采用N×B矩陣來描述:

矩陣X的各列代表一個傳感器節點采集獲取的信號矢量，矩陣X的各行代表全部傳感器節點相同時段采集值組成的信號矢量。網關節點接收到數據后，可得到隨機兩個節點間的相關指數[8]，記作:

為驗證節點i、j之間是否存在線性關聯，使用樣本的相關指數dij創建一個驗證統計指標:

使用平均相關度衡量節點i和多個節點集合D＝{d1，d2，…，dn}的相關程度:

將節點i、j依次劃分至2 個簇內，空間相關性強的傳感器節點被分割在相同簇中，執行以上步驟就能夠將一個規模較大的簇分割成若干個小簇，直至各個簇中節點之間符合相關性需求為止，以此完成高維傳感器數據采集任務。

2 基于分割點選擇與區間標準化的數據歸一化處理

采集傳感器節點數據后，通常會對數據實施預處理，預處理涵蓋數據清洗、特征提取、歸一化等操作。歸一化是數據分析領域中的核心技術，能去除特征屬性之間的量綱影響，本文使用分割點選擇與區間標準化兩個步驟完成傳感器數據歸一化處理[9]。

利用分割點預設獲取傳感器數據特征屬性內的u－1 個候選分割點，利用式(8)推算候選分割點聯合信息增益，信息增益最大值所對應的分割點為最佳分割點，提升歸一化整體質量。

式中，γ表示信息增益系數，H′()是連續特征屬性tx分割前的數據集信息熵，η是某數據集在全部數據集中的占比，H′(｜left)是分割點左側信息熵，H′(｜right)為分割點右側信息熵。

對傳感器網絡異常數據的不同屬性特征實施標準化，記作:

式中，f是離散值，K(Q)是數據信息熵，K(Q｜f)代表離散值是f時，數據集類型的條件熵。

選取分割點后，使用式(10)進行區間變換[10]，完成數據歸一化全過程。

3 BIRCH 聚類算法下高維傳感器數據異常檢測實現

完成相關數據采集與處理工作后，將高維傳感器數據時間序列分割成多個時序組合，挑選出傳感器數據序列的孤立異常值[11]，同時在檢測時剔除初始篩查異常中涵蓋的正常數據，得到所有異常數據。傳感器數據內的顯性異常一般在時間序列的離心邊緣，運用分層聚類策略研究數據性質，以最快速率挖掘異常數據。

高維傳感器異常值通常為極大異常和極小異常，傳感器數據序列較高的觀測值證明數據內存在異常現象，較低的觀測值為正常數據。極大異常對分割小型數據集合的數據擾動較大，但中位數不會受到分布數列的極值影響，更能呈現小型集合的數據特點。將傳感器數據序列的中位數異常作為異常檢測的判定條件，計算過程為:

式中，Wlmp表示第m個子集內隨機p點的觀測值，MI(wlm)是第m個子集的中位數。若p點的觀測值高于中位數，則傳感器節點數據存在異常；反之無異常現象發生。

為實現準確快速的高維傳感器數據異常檢測目標，提出基于BIRCH 聚類[12]的高維傳感器數據異常檢測方法。BIRCH 算法僅需一次掃描數據集即可達到聚類目標，聚類特征(Clustering Feature，CF)與聚類特征樹(CF 樹)是該算法最為重要的計算步驟。

BIRCH 算法通過CF 描述不同節點簇的數據，假設某個簇內涵蓋F個N維數據點，此簇的聚類特征被設定為如下三元組:

式中，F是此簇內數據點的總和，LC 表示數據點的線性總和，SST 為數據點的平方和。

CF 樹保存了不同層次的聚類簇特征，是一棵高度平衡樹，CF 樹內包含根節點、枝節點與葉節點，樹的各節點是通過多個聚類特征構成。

將傳感器數據序列Wl分割成P個簇:

式中，wli表示簇內的因子，wlij是第i個簇的第j個觀測值。

進一步拓展式(12)，將線性總和與平方和分別記作:

CF 樹內含三個參數，依次為內部節點均衡因子B′、葉節點均衡因子L′與簇半徑臨界值R。第g個特征樹節點被定義成CFTg，如式(17)所示。

式中，H表示子節點最大值，CFi是特征節點第i個聚類屬性，Childi代表當前節點的下個子節點。

將簇半徑臨界值R表示為:

通常情況下，數據聚類的結果被展現為球形簇狀架構，球形簇表示在數據空間內的s個數據因素勻稱分布且呈球狀。但高維傳感器數據序列無球形簇特征，因此要將其變換為球狀計算形式，創建中時特征矢量概念，將傳感器數據序列變換為球形簇單元，變換過程如式(19)～式(21)所示，進而輸出準確的異常檢測結果。

式中，表示第i個聚類內第j個因素相對的方位角，J為聚類簇內的因素總和，是球形簇的質心，為簇半徑，即時間序列子集內的觀測值，Wlij是傳感器時序內各數據的特征矢量，由時序值wlij、簇質心與方位角共同構成。

綜上可得，基于BIRCH 聚類算法的高維傳感器數據異常檢測流程圖如圖1 所示。

圖1 基于BIRCH 聚類算法的高維傳感器數據異常檢測流程圖

分析圖1 可知，通于BIRCH 聚類算法中的聚類特征樹描述不同節點簇的數據，獲取CF 樹內部節點均衡因子、葉節點均衡因子與簇半徑臨界值。將高維傳感器數據序列變換為球狀計算形式，實現高維傳感器數據序列均勻分布，再將傳感器數據序列的中位數異常作為異常檢測的判定條件，通過分層聚類挖掘異常數據，實現準確的高維傳感器數據異常檢測。

4 仿真實驗

4.1 實驗設置

為驗證本文方法的有效性，設計高維傳感器數據異常檢測仿真實驗。仿真平臺為MATLAB R2010a，對比方法為文獻[4]方法、文獻[5]方法及文獻[6]方法。設網絡簇首壓縮比是0.3，節點分布范圍為300 m×700 m 的矩形區域，匯聚節點坐標是(150 m，350 m)，實驗參數設定如表1 所示。

表1 傳感網絡仿真實驗參數

實驗采用車聯網高維數據M1，人工設定故障節點與誤差節點數據集，讓故障節點數據在較長時段內維持不變，誤差節點數據保持變化并和相同采集時間的正常節點數據有顯著偏差。為直觀展現方法對異常數據檢測的性能優劣，從檢出率、誤報率、檢測時間三個方面在不同數據規模下進行測驗。檢出率是方法準確評估異常節點的概率，計算過程為:

式中，C表示檢測輸出的異常節點個數，r是異常節點的實際數量。

誤報率是正常節點被判斷成異常節點的數量和傳感網絡正常節點的比值，記作:

式中，S′是無線傳感網絡的全部節點，A′表示異常節點數量。

4.2 實驗分析

將節點異常概率作為檢出率與誤報率的衡量指標，從現實意義而言，在保證無線傳感網絡正常使用前提下，節點異常概率值通常為10%～30%。四種方法伴隨節點異常概率變化得到的異常數據檢出率結果如圖2 所示。

圖2 四種方法異常檢測的檢出率對比

從圖2 看出，隨著節點異常率的持續升高，四種方法均不同程度出現檢出率下降趨勢，在節點異常概率為30%時，本文方法的異常檢出率為95%，高于文獻方法，證明其受到外部節點異常干擾的影響較小，計算穩定性強。

圖3 為四種方法異常檢測誤報率對比。

圖3 四種方法異常檢測的誤報率對比

觀察圖3 可知，隨著節點異常概率的增多，誤報率也隨之升高，本文方法誤報率最小，最終穩定在0.35%。文獻[4]方法在卷積層學習時會產生一定數量邊緣節點，并將部分邊緣點誤報成異常值，導致其誤報率偏高。文獻[5]方法利用無向圖結構提取樣本關聯特征時，沒有考慮樣本時間序列特征，無法完成預期檢測精度。文獻[6]方法的誤報率相對較低，但仍高于本文方法。

圖4 為四種方法異常檢測時長對比的仿真結果，實驗次數為1 000 次，每200 次記錄一次數據。

圖4 四種方法異常檢測耗時對比

從圖4 能夠看出，相同實驗環境下，當數據量達到1 000 Mbyte 時，本文方法耗時為1.5 min，低于文獻對比方法。分析其原因為，本文方法通過分割點選擇與和區間標準化步驟歸一化處理傳感數據，能夠降低數據檢測計算量，從而縮減運算時間。

5 結束語

針對當前高維傳感器數據異常檢測效率慢、精度差等問題，提出基于BIRCH 聚類算法的高維傳感器數據異常檢測方法。所提方法在精準采集高維傳感器數據的同時，運用歸一化處理降低計算復雜度，使用BIRCH 聚類將數據特征分類，得到高維傳感器數據序列異常數據。實驗結果表明，本文方法對異常節點檢測的檢出率為95%，誤報率為0.35%，數據量為1 000 Mbyte 時本文方法耗時為1.5 min，與文獻對比方法相比，本文方法對高維傳感器數據異常檢測的性能更優，能夠實現預期的異常檢測目標。