基于二叉空間劃分的異常數據檢測算法

周萬里 ，王子謙 ，謝婉利 ，譚安祖 ，余節約

(1.溫州醫科大學附屬眼視光醫院 信息管理處，浙江 溫州325000；2.浙江方圓檢測集團股份有限公司 檢測部，浙江 杭州310000；3.杭州電子科技大學 數字媒體學院，浙江 杭州310000)

0 引言

無線傳感網絡(Wireless Sensor Networks，WSNs)[1-2]是由多個具有感測能力的微型節點構成的。這些節點部署在不同位置，并且它們感知周圍環境數據(如溫度、壓力、濕度)，再以無線通信方式將數據傳輸至信宿[3]。

傳感節點感知的數據通常存在空間相關性和時間相關性[4]。 由于所感測數據的不完整、不準確，甚至異常[5-7]，通過時間分析所感測數據顯得尤其重要。 產生異常的原因有兩種：(1)傳感節點的故障；(2)異常事件的發生，如森林發火、洪水。 節點故障產生的異常是獨立的，屬個體。而異常事件的產生的異常具有空間或時間相關性。因此，通過分析感測數據間的相關性，能夠提高對事件檢測的準確性。

所謂異常，是指不同于正常數據。 通過對異常數據和正常數據間的等級測量(Ranking Measures，RM)，能夠檢測異常事件。 既可通過局部傳感節點分布式識別異常，也可利用觀察節點集中式識別異常。

空間分割常用于事件分類。而二叉空間劃分(Binary Space Partition，BSP)就是對空間中的物體進行二叉遞歸劃分的算法。 即用平面將空間分割，空間中各部分又被分為前面和后面兩類，對分割后的空間繼續使用相同的方法進行分割，直到不能分割為止，進而產生BSP 樹[8]。

通過BSP 樹和質量等級的測量可檢測異常。 文獻[9]最初利用MassAD 算法進行質量估計，它將數據實例劃分為嚴重異常至完全正常。然而，相比于高質量數據，低質量數據屬異常的概率更高。

為此，提出基于二叉空間劃分的異常數據檢測(Binary Space Partition-based Anomaly Detection，BSP-AD)算法。BSP-AD 算法利用二叉空間劃分訓練數據，構成正常數據的區間范圍，再通過此區間范圍檢測異常數據。 仿真結果表明，提出的BSP-AD 算法能夠準確地檢測異常數據，并控制數據存儲成本和計算成本。

1 系統模型

令τj表 示 第j 棵BSP 樹。 t 棵 樹 構 成 樹 集γh，即|γh|=t，其中h 表示每棵樹的高度。

樹中每個節點代表一個子空間。 用md表示在子空間內正常數據實例的個數，而d 表示子空間的深度。 令pd表示深度為d 的子空間的分割點。

令xni表示在訓練階段中第i 個正常數據實例。 用φ項數據實例構成集η，即|η|=φ：

每個實例xk有t 分。 為此，令Sk表示分數集：

例如，S1(xk)表示在樹τ1中實例xk的分數，S2(xk)表示在樹τ2中實例xk的分數。

依式(4)將所有樹上的分數進行融合，再傳輸至實例xk：

2 BSP-AD 算法

BSP-AD 算法由訓練和測試兩個階段構成。 在訓練階段，利用正常數據實例建立參考樹，并定義異常檢測的主要參數。 而測試階段，判斷給定數據為正常或異常。

2.1 訓練階段

首先，計算每個給定實例xk的分數。 對于任意樹τj∈γh，在每個層次，將實例xk與分割點pd-1進行比較。如果xk小于pd-1，就將數據移至左邊的子樹；否則，就移至右邊的子樹。 因此，可得外部節點的分數：

如圖1 所示，假定實例x=2.50，首先與它的分割點值p=2.54 值進行比較，由于x=2.50＜2.54，它遍歷左邊樹，再與第二級的分割點值p=2.43 進行比較，由于x=2.50＞2.43，它遍歷右邊樹。

再計算實例xk的質量。 實例遍歷了所有樹，其在每棵具體樹上具有分數。 因此，可利用式(6)計算實例xk遍歷在所有樹上的平均分。

圖1 數據實例的遍歷示意圖

其中，j∈{0，…，t}。

最后，計算正常實例的范圍。 一個實例的質量(Mass)決定了該實例是否為異常。 先給正常數據樣本設置質量范圍[Minb，Maxb]。 如果某實例質量越出此范圍，則判定為異常。 圖2 給出了計算正常范圍的上限Minb和下限Maxb的過程。

圖2 算法過程

令η 為正常數據樣本、Ψ 為樣本尺寸、t 為樹的個數。 先依式(7)計算Mi和MΨ：

最后，依據μ(MΨ)和σΨ計算Minb、Maxb：

2.2 分割點的選擇

令Hmin和Hmax表示空間H 的上下限。 令rand 表示在[Hmin，Hmax]區 間 的 隨 機 數。 引 用 文 獻[9]的 分 割 算 法。 將分割點p 作為[minp，maxp]區間的中點，其定義如式(12)所示：

其中，r=2×max{(rand-Hmin)，(rand+Hmax)}。

2.3 測試階段

測試階段判斷每個新數據實例xk是否為異常。每個新數據實例xk遍歷γh內所有BSP 樹。 再計算Sk集的質量，再依據式(13)計算標志位：

如果Anom(xk)=0，則認為實例xk是正常的；否則，如果Anom(xk)=1，則認為實例xk為異常的。 整個過程如圖3 所示。

圖3 測試階段流程圖

3 性能分析

3.1 仿真環境

利用MATLAB R2018a 軟件建立仿真平臺，引用文獻[9]-[10]所設的BSP 樹，其參數為：t=100，φ=256，h=2。同時選擇文獻[11]提出的基于局部濾波器的檢測(Identifying Density-based Local Outliers，IDLO)和文獻[9]提出的質量估計(Mass Estimation，MAES)算法作為參照，并對比分析它們的性能。

主要考查真陽性率(True Positive Rate，TPR)、假陽性率(False Positive Rate，FPR)、曲線下面積(Area Under Curve，AUC)和F1 分數(F1 Sorce，F1S)。

TPR 反映了將異常實例準確地檢測為異常實例的準確性，其定義如式(14)所示：

其中，TP 表示假陽性率(False Positives，FP)，其等于正常的數據實例被錯誤地判定為異常實例；而偽陰性(False Negatives，FN)等于將異常實例錯誤地判定為正常實例的概率。

FPR 反映了將正常實例錯誤地檢測為異常實例的概率，其定義如式(15)所示：

其中，TN 為真陰性，其表示異常實例被錯誤地判定為正常實例。

而AUC 等于在不同點上的FPR 與FPR 之比。 此外，F1S 為準確率與召回率間的調和均值(Harmonic Mean)。F1S 的取值在0～1 之間。 F1S 值越高，算法性能越好，其定義如式(16)所示：

其中，pprecision等于正確檢測的異常實例與總的異常實例數之比，precall等于正確檢測的異常實例與總的數據實例之比。

此外，引用文獻[12]的數據集，包括溫度、濕度、電波和CO24 項樣本數據。

3.2 TPR 和FPR 性 能 分 析

圖4 TPR 性能

圖4、 圖5 分別顯示了4 項數據的TPR 和FPR。 由圖4 可知，提出的BSP-AD 算法對二氧化碳、電波、溫度和濕度4 項數據具有較高的TPR，這4 項的數據的TPR率分別達到0.93、0.79、1.00、1.00， 優于IDLO 和MAES算法[13]。

其中IDLO 算法對TPR 較低，其對二氧化碳、電波、溫度和濕度4 項數據的TPR 分別為0.01、0.01、1 和0.092。 且IDLO 算法對數據類型較敏感。

圖5 顯示了BSP-AD、IDLO 和MAES 對4 項數據的FPR 性能。 相比于IDLO 和MAES，提出的BSP-AD 算法的FPR 最低，低于0.1；而IDLO 和MAES 算法的FPR 相近，且較高，例如，IDLO 算法對濕度樣本數據的FPR 達到0.51。這些數據表明，BSP-AD 算法能夠有效地檢測異常數據，相比于IDLO 和MAES 算法，更能控制FPR[14-15]。

圖5 FPR 性能

3.3 F1S 性能

圖6 顯示了BSP-AD、IDLO 和MAES 算法對4 類數據的F1S 分數。 從圖5 可知，BSP-AD 算法的F1S 最高，且遠高于IDLO 和MAES 算法。 例如， 在溫度數據時，BSP-AD 的F1S 達 到1，而IDLO 和MAES 算 法 的F1S 分別只有0.38 和0.58。

圖6 F1S 的性能

3.4 計算成本和存儲成本的性能

考慮到節點屬于微型節點，計算和存儲能力有限。因此，異常檢測算法應具有低的復雜度和小的存儲成本。而BSP 樹能夠處理大量的數據，甚至是動態的數據流。 而IDLO 算法僅能處理靜態數據，并且計算成本高。

本文提出的BSP-AD 算法采用了BSP 樹，它的計算成本和存儲成本與MAES 算法相似。 BSP-AD 算法的計算成本為O(t×h(logn+Ψ))。 而IDLO 算法的計算成本約為O(r×n2)，其中r 為鄰居數，n 為數據實例的個數。

此外，BSP-AD 算法無需計算距離或者密度測量，并控制了訓練樹的個數，進而降低了存儲成本。 因此，BSP-AD 算法的存儲成本為O(t×h×Ψ)，而IDLO 算法的存儲成本為O(n)。

4 結論

本文針對無線傳感網絡中的異常數據檢測問題，提出基于二叉空間劃分的異常數據檢測BSP-AD 算法。BSP-AD 算法依據質量測量，并利用BSP 樹訓練和測試數據。 仿真結果表明，提出的BSP-AD 算法以較低的計算成本和存儲成本，獲取高的檢測精度。后期研究中，將利用不同節點間所感測的數據間的時空-相關性，進一步提高檢測精度。