基于二叉空間劃分的異常數(shù)據(jù)檢測(cè)算法

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

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

0 引言

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

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

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

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

通過BSP 樹和質(zhì)量等級(jí)的測(cè)量可檢測(cè)異常。 文獻(xiàn)[9]最初利用MassAD 算法進(jìn)行質(zhì)量估計(jì)，它將數(shù)據(jù)實(shí)例劃分為嚴(yán)重異常至完全正常。然而，相比于高質(zhì)量數(shù)據(jù)，低質(zhì)量數(shù)據(jù)屬異常的概率更高。

為此，提出基于二叉空間劃分的異常數(shù)據(jù)檢測(cè)(Binary Space Partition-based Anomaly Detection，BSP-AD)算法。BSP-AD 算法利用二叉空間劃分訓(xùn)練數(shù)據(jù)，構(gòu)成正常數(shù)據(jù)的區(qū)間范圍，再通過此區(qū)間范圍檢測(cè)異常數(shù)據(jù)。 仿真結(jié)果表明，提出的BSP-AD 算法能夠準(zhǔn)確地檢測(cè)異常數(shù)據(jù)，并控制數(shù)據(jù)存儲(chǔ)成本和計(jì)算成本。

1 系統(tǒng)模型

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

樹中每個(gè)節(jié)點(diǎn)代表一個(gè)子空間。 用md表示在子空間內(nèi)正常數(shù)據(jù)實(shí)例的個(gè)數(shù)，而d 表示子空間的深度。 令pd表示深度為d 的子空間的分割點(diǎn)。

令xni表示在訓(xùn)練階段中第i 個(gè)正常數(shù)據(jù)實(shí)例。 用φ項(xiàng)數(shù)據(jù)實(shí)例構(gòu)成集η，即|η|=φ：

每個(gè)實(shí)例xk有t 分。 為此，令Sk表示分?jǐn)?shù)集：

例如，S1(xk)表示在樹τ1中實(shí)例xk的分?jǐn)?shù)，S2(xk)表示在樹τ2中實(shí)例xk的分?jǐn)?shù)。

依式(4)將所有樹上的分?jǐn)?shù)進(jìn)行融合，再傳輸至實(shí)例xk：

2 BSP-AD 算法

BSP-AD 算法由訓(xùn)練和測(cè)試兩個(gè)階段構(gòu)成。 在訓(xùn)練階段，利用正常數(shù)據(jù)實(shí)例建立參考樹，并定義異常檢測(cè)的主要參數(shù)。 而測(cè)試階段，判斷給定數(shù)據(jù)為正?；虍惓！?/p>

2.1 訓(xùn)練階段

首先，計(jì)算每個(gè)給定實(shí)例xk的分?jǐn)?shù)。 對(duì)于任意樹τj∈γh，在每個(gè)層次，將實(shí)例xk與分割點(diǎn)pd-1進(jìn)行比較。如果xk小于pd-1，就將數(shù)據(jù)移至左邊的子樹；否則，就移至右邊的子樹。 因此，可得外部節(jié)點(diǎn)的分?jǐn)?shù)：

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

再計(jì)算實(shí)例xk的質(zhì)量。 實(shí)例遍歷了所有樹，其在每棵具體樹上具有分?jǐn)?shù)。 因此，可利用式(6)計(jì)算實(shí)例xk遍歷在所有樹上的平均分。

圖1 數(shù)據(jù)實(shí)例的遍歷示意圖

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

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

圖2 算法過程

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

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

2.2 分割點(diǎn)的選擇

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

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

2.3 測(cè)試階段

測(cè)試階段判斷每個(gè)新數(shù)據(jù)實(shí)例xk是否為異常。每個(gè)新數(shù)據(jù)實(shí)例xk遍歷γh內(nèi)所有BSP 樹。 再計(jì)算Sk集的質(zhì)量，再依據(jù)式(13)計(jì)算標(biāo)志位：

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

圖3 測(cè)試階段流程圖

3 性能分析

3.1 仿真環(huán)境

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

主要考查真陽性率(True Positive Rate，TPR)、假陽性率(False Positive Rate，F(xiàn)PR)、曲線下面積(Area Under Curve，AUC)和F1 分?jǐn)?shù)(F1 Sorce，F(xiàn)1S)。

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

其中，TP 表示假陽性率(False Positives，F(xiàn)P)，其等于正常的數(shù)據(jù)實(shí)例被錯(cuò)誤地判定為異常實(shí)例；而偽陰性(False Negatives，F(xiàn)N)等于將異常實(shí)例錯(cuò)誤地判定為正常實(shí)例的概率。

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

其中，TN 為真陰性，其表示異常實(shí)例被錯(cuò)誤地判定為正常實(shí)例。

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

其中，pprecision等于正確檢測(cè)的異常實(shí)例與總的異常實(shí)例數(shù)之比，precall等于正確檢測(cè)的異常實(shí)例與總的數(shù)據(jù)實(shí)例之比。

此外，引用文獻(xiàn)[12]的數(shù)據(jù)集，包括溫度、濕度、電波和CO24 項(xiàng)樣本數(shù)據(jù)。

3.2 TPR 和FPR 性 能 分 析

圖4 TPR 性能

圖4、 圖5 分別顯示了4 項(xiàng)數(shù)據(jù)的TPR 和FPR。 由圖4 可知，提出的BSP-AD 算法對(duì)二氧化碳、電波、溫度和濕度4 項(xiàng)數(shù)據(jù)具有較高的TPR，這4 項(xiàng)的數(shù)據(jù)的TPR率分別達(dá)到0.93、0.79、1.00、1.00， 優(yōu)于IDLO 和MAES算法[13]。

其中IDLO 算法對(duì)TPR 較低，其對(duì)二氧化碳、電波、溫度和濕度4 項(xiàng)數(shù)據(jù)的TPR 分別為0.01、0.01、1 和0.092。 且IDLO 算法對(duì)數(shù)據(jù)類型較敏感。

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

圖5 FPR 性能

3.3 F1S 性能

圖6 顯示了BSP-AD、IDLO 和MAES 算法對(duì)4 類數(shù)據(jù)的F1S 分?jǐn)?shù)。 從圖5 可知，BSP-AD 算法的F1S 最高，且遠(yuǎn)高于IDLO 和MAES 算法。 例如， 在溫度數(shù)據(jù)時(shí)，BSP-AD 的F1S 達(dá) 到1，而IDLO 和MAES 算 法 的F1S 分別只有0.38 和0.58。

圖6 F1S 的性能

3.4 計(jì)算成本和存儲(chǔ)成本的性能

考慮到節(jié)點(diǎn)屬于微型節(jié)點(diǎn)，計(jì)算和存儲(chǔ)能力有限。因此，異常檢測(cè)算法應(yīng)具有低的復(fù)雜度和小的存儲(chǔ)成本。而BSP 樹能夠處理大量的數(shù)據(jù)，甚至是動(dòng)態(tài)的數(shù)據(jù)流。 而IDLO 算法僅能處理靜態(tài)數(shù)據(jù)，并且計(jì)算成本高。

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

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

4 結(jié)論

本文針對(duì)無線傳感網(wǎng)絡(luò)中的異常數(shù)據(jù)檢測(cè)問題，提出基于二叉空間劃分的異常數(shù)據(jù)檢測(cè)BSP-AD 算法。BSP-AD 算法依據(jù)質(zhì)量測(cè)量，并利用BSP 樹訓(xùn)練和測(cè)試數(shù)據(jù)。 仿真結(jié)果表明，提出的BSP-AD 算法以較低的計(jì)算成本和存儲(chǔ)成本，獲取高的檢測(cè)精度。后期研究中，將利用不同節(jié)點(diǎn)間所感測(cè)的數(shù)據(jù)間的時(shí)空-相關(guān)性，進(jìn)一步提高檢測(cè)精度。