基于BIRCH 聚類算法的高維傳感器數(shù)據(jù)異常檢測(cè)?

趙 嬌

(綿陽(yáng)職業(yè)技術(shù)學(xué)院電子與信息學(xué)院，四川 綿陽(yáng) 621000)

將傳感器節(jié)點(diǎn)分布在目標(biāo)范圍中，利用節(jié)點(diǎn)收集的周邊環(huán)境參數(shù)[1]，能有效挖掘自然環(huán)境內(nèi)的突發(fā)事件和傳感器網(wǎng)絡(luò)的運(yùn)行狀態(tài)。高維傳感器數(shù)據(jù)流具有數(shù)據(jù)量大、無(wú)法準(zhǔn)確估測(cè)的特點(diǎn)，為增強(qiáng)無(wú)線傳感網(wǎng)絡(luò)的可靠性，對(duì)其采集的傳感器數(shù)據(jù)實(shí)施異常檢測(cè)變得格外重要[2]。和處理一般低維數(shù)據(jù)不同，高維數(shù)據(jù)處理具有更高的時(shí)間復(fù)雜度[3]，異常檢測(cè)時(shí)會(huì)面臨極大挑戰(zhàn)。

相關(guān)學(xué)者對(duì)此問(wèn)題的研究?jī)?nèi)容如下:神顯豪等[4]在歸一化處理數(shù)據(jù)后，將其擬作卷積神經(jīng)網(wǎng)絡(luò)輸入值，改進(jìn)卷積層特征面與全連接層參數(shù)，通過(guò)卷積層學(xué)習(xí)異常數(shù)據(jù)特征。此方法在數(shù)據(jù)量采集時(shí)需要消耗大量時(shí)間，無(wú)法完成實(shí)時(shí)檢測(cè)預(yù)期目標(biāo)。席亮等[5]使用無(wú)向圖結(jié)構(gòu)提取樣本關(guān)聯(lián)特征，利用雙路自編碼器融合樣本初始特征和關(guān)聯(lián)特征，提出基于高斯混合模型的估計(jì)網(wǎng)絡(luò)，通過(guò)閾值計(jì)算實(shí)現(xiàn)數(shù)據(jù)異常檢測(cè)。但方法融合樣本特征時(shí)沒(méi)有消除冗余數(shù)據(jù)，異常檢測(cè)結(jié)果精度不高。Kim D 等[6]提出無(wú)監(jiān)督異常檢測(cè)方法，該方法使用來(lái)自船用發(fā)動(dòng)機(jī)的傳感器流來(lái)檢測(cè)異常系統(tǒng)行為，基于集成的異常檢測(cè)方法，并行訓(xùn)練幾個(gè)具有不同超參數(shù)的異常檢測(cè)器，然后在異常檢測(cè)階段組合其結(jié)果。該方法的準(zhǔn)確性較高，但耗時(shí)較長(zhǎng)。

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

1 基于分簇處理的高維傳感器數(shù)據(jù)采集方法

高維傳感器數(shù)據(jù)采集即傳感器從待測(cè)目標(biāo)環(huán)境中得到數(shù)據(jù)并安置在節(jié)點(diǎn)存儲(chǔ)器內(nèi)，節(jié)點(diǎn)處理器利用某種方法在存儲(chǔ)器中獲取數(shù)據(jù)的流程。具體來(lái)說(shuō)，數(shù)據(jù)采集就是在節(jié)點(diǎn)處理器傳遞采集指令后，智能傳感器板塊接收采集指令并實(shí)施采集工作。在此過(guò)程中，使用線性回歸法采集數(shù)據(jù)，經(jīng)過(guò)如下:

部署于監(jiān)控區(qū)域的傳感器節(jié)點(diǎn)，可按照節(jié)點(diǎn)信息的關(guān)聯(lián)性分割為多個(gè)簇，并假設(shè)處于相同簇內(nèi)的兩個(gè)隨機(jī)節(jié)點(diǎn)數(shù)據(jù)為顯著線性關(guān)聯(lián)。設(shè)定傳感器網(wǎng)絡(luò)一個(gè)簇中涵蓋i個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)同時(shí)采集，采集獲得長(zhǎng)度是N的信號(hào)矢量，則節(jié)點(diǎn)相對(duì)的一階差分信號(hào)序列為:

式中，xi(k)代表節(jié)點(diǎn)i第k個(gè)時(shí)段的信號(hào)，Δxi(k)表示節(jié)點(diǎn)i第k個(gè)時(shí)段的一階差分信號(hào)。

若節(jié)點(diǎn)i、j為處在相同簇的節(jié)點(diǎn)，因相同簇內(nèi)隨機(jī)兩個(gè)節(jié)點(diǎn)的數(shù)據(jù)為顯著線性關(guān)聯(lián)，節(jié)點(diǎn)j的一階差分信號(hào)序列和節(jié)點(diǎn)i的完全相等，記作:

式中，α0、α1均表示回歸指數(shù)，b是節(jié)點(diǎn)元素順從均值為0 的高斯分布。

節(jié)點(diǎn)i使用等間隔策略[7]采集高維傳感器數(shù)據(jù)，將采集后的信號(hào)矢量xi通過(guò)多跳路由傳輸?shù)骄W(wǎng)關(guān)節(jié)點(diǎn)，使用高斯隨機(jī)矩陣Φ投影節(jié)點(diǎn)j的一階差分信號(hào)，計(jì)算公式為:

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

倘若處于監(jiān)控范圍的傳感器節(jié)點(diǎn)數(shù)量為B，則網(wǎng)關(guān)節(jié)點(diǎn)接收的數(shù)據(jù)可采用N×B矩陣來(lái)描述:

矩陣X的各列代表一個(gè)傳感器節(jié)點(diǎn)采集獲取的信號(hào)矢量，矩陣X的各行代表全部傳感器節(jié)點(diǎn)相同時(shí)段采集值組成的信號(hào)矢量。網(wǎng)關(guān)節(jié)點(diǎn)接收到數(shù)據(jù)后，可得到隨機(jī)兩個(gè)節(jié)點(diǎn)間的相關(guān)指數(shù)[8]，記作:

為驗(yàn)證節(jié)點(diǎn)i、j之間是否存在線性關(guān)聯(lián)，使用樣本的相關(guān)指數(shù)dij創(chuàng)建一個(gè)驗(yàn)證統(tǒng)計(jì)指標(biāo):

使用平均相關(guān)度衡量節(jié)點(diǎn)i和多個(gè)節(jié)點(diǎn)集合D＝{d1，d2，…，dn}的相關(guān)程度:

將節(jié)點(diǎn)i、j依次劃分至2 個(gè)簇內(nèi)，空間相關(guān)性強(qiáng)的傳感器節(jié)點(diǎn)被分割在相同簇中，執(zhí)行以上步驟就能夠?qū)⒁粋€(gè)規(guī)模較大的簇分割成若干個(gè)小簇，直至各個(gè)簇中節(jié)點(diǎn)之間符合相關(guān)性需求為止，以此完成高維傳感器數(shù)據(jù)采集任務(wù)。

2 基于分割點(diǎn)選擇與區(qū)間標(biāo)準(zhǔn)化的數(shù)據(jù)歸一化處理

采集傳感器節(jié)點(diǎn)數(shù)據(jù)后，通常會(huì)對(duì)數(shù)據(jù)實(shí)施預(yù)處理，預(yù)處理涵蓋數(shù)據(jù)清洗、特征提取、歸一化等操作。歸一化是數(shù)據(jù)分析領(lǐng)域中的核心技術(shù)，能去除特征屬性之間的量綱影響，本文使用分割點(diǎn)選擇與區(qū)間標(biāo)準(zhǔn)化兩個(gè)步驟完成傳感器數(shù)據(jù)歸一化處理[9]。

利用分割點(diǎn)預(yù)設(shè)獲取傳感器數(shù)據(jù)特征屬性內(nèi)的u－1 個(gè)候選分割點(diǎn)，利用式(8)推算候選分割點(diǎn)聯(lián)合信息增益，信息增益最大值所對(duì)應(yīng)的分割點(diǎn)為最佳分割點(diǎn)，提升歸一化整體質(zhì)量。

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

對(duì)傳感器網(wǎng)絡(luò)異常數(shù)據(jù)的不同屬性特征實(shí)施標(biāo)準(zhǔn)化，記作:

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

選取分割點(diǎn)后，使用式(10)進(jìn)行區(qū)間變換[10]，完成數(shù)據(jù)歸一化全過(guò)程。

3 BIRCH 聚類算法下高維傳感器數(shù)據(jù)異常檢測(cè)實(shí)現(xiàn)

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

高維傳感器異常值通常為極大異常和極小異常，傳感器數(shù)據(jù)序列較高的觀測(cè)值證明數(shù)據(jù)內(nèi)存在異常現(xiàn)象，較低的觀測(cè)值為正常數(shù)據(jù)。極大異常對(duì)分割小型數(shù)據(jù)集合的數(shù)據(jù)擾動(dòng)較大，但中位數(shù)不會(huì)受到分布數(shù)列的極值影響，更能呈現(xiàn)小型集合的數(shù)據(jù)特點(diǎn)。將傳感器數(shù)據(jù)序列的中位數(shù)異常作為異常檢測(cè)的判定條件，計(jì)算過(guò)程為:

式中，Wlmp表示第m個(gè)子集內(nèi)隨機(jī)p點(diǎn)的觀測(cè)值，MI(wlm)是第m個(gè)子集的中位數(shù)。若p點(diǎn)的觀測(cè)值高于中位數(shù)，則傳感器節(jié)點(diǎn)數(shù)據(jù)存在異常；反之無(wú)異?，F(xiàn)象發(fā)生。

為實(shí)現(xiàn)準(zhǔn)確快速的高維傳感器數(shù)據(jù)異常檢測(cè)目標(biāo)，提出基于BIRCH 聚類[12]的高維傳感器數(shù)據(jù)異常檢測(cè)方法。BIRCH 算法僅需一次掃描數(shù)據(jù)集即可達(dá)到聚類目標(biāo)，聚類特征(Clustering Feature，CF)與聚類特征樹(shù)(CF 樹(shù))是該算法最為重要的計(jì)算步驟。

BIRCH 算法通過(guò)CF 描述不同節(jié)點(diǎn)簇的數(shù)據(jù)，假設(shè)某個(gè)簇內(nèi)涵蓋F個(gè)N維數(shù)據(jù)點(diǎn)，此簇的聚類特征被設(shè)定為如下三元組:

式中，F(xiàn)是此簇內(nèi)數(shù)據(jù)點(diǎn)的總和，LC 表示數(shù)據(jù)點(diǎn)的線性總和，SST 為數(shù)據(jù)點(diǎn)的平方和。

CF 樹(shù)保存了不同層次的聚類簇特征，是一棵高度平衡樹(shù)，CF 樹(shù)內(nèi)包含根節(jié)點(diǎn)、枝節(jié)點(diǎn)與葉節(jié)點(diǎn)，樹(shù)的各節(jié)點(diǎn)是通過(guò)多個(gè)聚類特征構(gòu)成。

將傳感器數(shù)據(jù)序列Wl分割成P個(gè)簇:

式中，wli表示簇內(nèi)的因子，wlij是第i個(gè)簇的第j個(gè)觀測(cè)值。

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

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

式中，H表示子節(jié)點(diǎn)最大值，CFi是特征節(jié)點(diǎn)第i個(gè)聚類屬性，Childi代表當(dāng)前節(jié)點(diǎn)的下個(gè)子節(jié)點(diǎn)。

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

通常情況下，數(shù)據(jù)聚類的結(jié)果被展現(xiàn)為球形簇狀架構(gòu)，球形簇表示在數(shù)據(jù)空間內(nèi)的s個(gè)數(shù)據(jù)因素勻稱分布且呈球狀。但高維傳感器數(shù)據(jù)序列無(wú)球形簇特征，因此要將其變換為球狀計(jì)算形式，創(chuàng)建中時(shí)特征矢量概念，將傳感器數(shù)據(jù)序列變換為球形簇單元，變換過(guò)程如式(19)～式(21)所示，進(jìn)而輸出準(zhǔn)確的異常檢測(cè)結(jié)果。

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

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

圖1 基于BIRCH 聚類算法的高維傳感器數(shù)據(jù)異常檢測(cè)流程圖

分析圖1 可知，通于BIRCH 聚類算法中的聚類特征樹(shù)描述不同節(jié)點(diǎn)簇的數(shù)據(jù)，獲取CF 樹(shù)內(nèi)部節(jié)點(diǎn)均衡因子、葉節(jié)點(diǎn)均衡因子與簇半徑臨界值。將高維傳感器數(shù)據(jù)序列變換為球狀計(jì)算形式，實(shí)現(xiàn)高維傳感器數(shù)據(jù)序列均勻分布，再將傳感器數(shù)據(jù)序列的中位數(shù)異常作為異常檢測(cè)的判定條件，通過(guò)分層聚類挖掘異常數(shù)據(jù)，實(shí)現(xiàn)準(zhǔn)確的高維傳感器數(shù)據(jù)異常檢測(cè)。

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證本文方法的有效性，設(shè)計(jì)高維傳感器數(shù)據(jù)異常檢測(cè)仿真實(shí)驗(yàn)。仿真平臺(tái)為MATLAB R2010a，對(duì)比方法為文獻(xiàn)[4]方法、文獻(xiàn)[5]方法及文獻(xiàn)[6]方法。設(shè)網(wǎng)絡(luò)簇首壓縮比是0.3，節(jié)點(diǎn)分布范圍為300 m×700 m 的矩形區(qū)域，匯聚節(jié)點(diǎn)坐標(biāo)是(150 m，350 m)，實(shí)驗(yàn)參數(shù)設(shè)定如表1 所示。

表1 傳感網(wǎng)絡(luò)仿真實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)采用車聯(lián)網(wǎng)高維數(shù)據(jù)M1，人工設(shè)定故障節(jié)點(diǎn)與誤差節(jié)點(diǎn)數(shù)據(jù)集，讓故障節(jié)點(diǎn)數(shù)據(jù)在較長(zhǎng)時(shí)段內(nèi)維持不變，誤差節(jié)點(diǎn)數(shù)據(jù)保持變化并和相同采集時(shí)間的正常節(jié)點(diǎn)數(shù)據(jù)有顯著偏差。為直觀展現(xiàn)方法對(duì)異常數(shù)據(jù)檢測(cè)的性能優(yōu)劣，從檢出率、誤報(bào)率、檢測(cè)時(shí)間三個(gè)方面在不同數(shù)據(jù)規(guī)模下進(jìn)行測(cè)驗(yàn)。檢出率是方法準(zhǔn)確評(píng)估異常節(jié)點(diǎn)的概率，計(jì)算過(guò)程為:

式中，C表示檢測(cè)輸出的異常節(jié)點(diǎn)個(gè)數(shù)，r是異常節(jié)點(diǎn)的實(shí)際數(shù)量。

誤報(bào)率是正常節(jié)點(diǎn)被判斷成異常節(jié)點(diǎn)的數(shù)量和傳感網(wǎng)絡(luò)正常節(jié)點(diǎn)的比值，記作:

式中，S′是無(wú)線傳感網(wǎng)絡(luò)的全部節(jié)點(diǎn)，A′表示異常節(jié)點(diǎn)數(shù)量。

4.2 實(shí)驗(yàn)分析

將節(jié)點(diǎn)異常概率作為檢出率與誤報(bào)率的衡量指標(biāo)，從現(xiàn)實(shí)意義而言，在保證無(wú)線傳感網(wǎng)絡(luò)正常使用前提下，節(jié)點(diǎn)異常概率值通常為10%～30%。四種方法伴隨節(jié)點(diǎn)異常概率變化得到的異常數(shù)據(jù)檢出率結(jié)果如圖2 所示。

圖2 四種方法異常檢測(cè)的檢出率對(duì)比

從圖2 看出，隨著節(jié)點(diǎn)異常率的持續(xù)升高，四種方法均不同程度出現(xiàn)檢出率下降趨勢(shì)，在節(jié)點(diǎn)異常概率為30%時(shí)，本文方法的異常檢出率為95%，高于文獻(xiàn)方法，證明其受到外部節(jié)點(diǎn)異常干擾的影響較小，計(jì)算穩(wěn)定性強(qiáng)。

圖3 為四種方法異常檢測(cè)誤報(bào)率對(duì)比。

圖3 四種方法異常檢測(cè)的誤報(bào)率對(duì)比

觀察圖3 可知，隨著節(jié)點(diǎn)異常概率的增多，誤報(bào)率也隨之升高，本文方法誤報(bào)率最小，最終穩(wěn)定在0.35%。文獻(xiàn)[4]方法在卷積層學(xué)習(xí)時(shí)會(huì)產(chǎn)生一定數(shù)量邊緣節(jié)點(diǎn)，并將部分邊緣點(diǎn)誤報(bào)成異常值，導(dǎo)致其誤報(bào)率偏高。文獻(xiàn)[5]方法利用無(wú)向圖結(jié)構(gòu)提取樣本關(guān)聯(lián)特征時(shí)，沒(méi)有考慮樣本時(shí)間序列特征，無(wú)法完成預(yù)期檢測(cè)精度。文獻(xiàn)[6]方法的誤報(bào)率相對(duì)較低，但仍高于本文方法。

圖4 為四種方法異常檢測(cè)時(shí)長(zhǎng)對(duì)比的仿真結(jié)果，實(shí)驗(yàn)次數(shù)為1 000 次，每200 次記錄一次數(shù)據(jù)。

圖4 四種方法異常檢測(cè)耗時(shí)對(duì)比

從圖4 能夠看出，相同實(shí)驗(yàn)環(huán)境下，當(dāng)數(shù)據(jù)量達(dá)到1 000 Mbyte 時(shí)，本文方法耗時(shí)為1.5 min，低于文獻(xiàn)對(duì)比方法。分析其原因?yàn)?，本文方法通過(guò)分割點(diǎn)選擇與和區(qū)間標(biāo)準(zhǔn)化步驟歸一化處理傳感數(shù)據(jù)，能夠降低數(shù)據(jù)檢測(cè)計(jì)算量，從而縮減運(yùn)算時(shí)間。

5 結(jié)束語(yǔ)

針對(duì)當(dāng)前高維傳感器數(shù)據(jù)異常檢測(cè)效率慢、精度差等問(wèn)題，提出基于BIRCH 聚類算法的高維傳感器數(shù)據(jù)異常檢測(cè)方法。所提方法在精準(zhǔn)采集高維傳感器數(shù)據(jù)的同時(shí)，運(yùn)用歸一化處理降低計(jì)算復(fù)雜度，使用BIRCH 聚類將數(shù)據(jù)特征分類，得到高維傳感器數(shù)據(jù)序列異常數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明，本文方法對(duì)異常節(jié)點(diǎn)檢測(cè)的檢出率為95%，誤報(bào)率為0.35%，數(shù)據(jù)量為1 000 Mbyte 時(shí)本文方法耗時(shí)為1.5 min，與文獻(xiàn)對(duì)比方法相比，本文方法對(duì)高維傳感器數(shù)據(jù)異常檢測(cè)的性能更優(yōu)，能夠?qū)崿F(xiàn)預(yù)期的異常檢測(cè)目標(biāo)。