一種基于dbscan的異常數(shù)據(jù)檢測方法

0異常檢測技術(shù)目前，環(huán)境源的數(shù)量正在增加，導(dǎo)致環(huán)境突發(fā)事件事故和重大環(huán)境破壞等全球環(huán)境危機。環(huán)境保護已成為世界各國的一項重要任務(wù)?；跓o線傳感器網(wǎng)絡(luò)的環(huán)境監(jiān)測系統(tǒng),改變了傳統(tǒng)的人工管理方式,可以對監(jiān)控區(qū)域的水、氣、聲、動植物等環(huán)境因素實施長期、連續(xù)、自治的監(jiān)測及分析,不僅實現(xiàn)對環(huán)境參數(shù)的實時監(jiān)測,而且還可以分析出環(huán)境當(dāng)前及未來的變化趨勢,為環(huán)境保護提供科學(xué)的決策依據(jù)。在無線傳感器網(wǎng)絡(luò)環(huán)境監(jiān)測應(yīng)用中,為了及時監(jiān)測各種可能發(fā)生的突發(fā)事件(如森林火災(zāi)、大氣污染、山體滑坡等),必須特別關(guān)注傳感器節(jié)點采集到的異常測量值。例如,通常情況下,日平均氣溫很少超過40℃,而當(dāng)發(fā)生森林火災(zāi)時,傳感器節(jié)點采集的溫度值就會發(fā)生急劇變化,甚至達到100℃以上。因此,實時高效地檢測出異常數(shù)據(jù),并提供預(yù)警措施,具有十分重要的意義。然而,傳感器節(jié)點的異常數(shù)據(jù)不僅可能由外部事件引起,也有可能是由于節(jié)點本身的軟件或硬件故障引發(fā)的,例如,軟件缺陷、電池能量不足、電磁干擾以及傳感器故障等因素都會造成測量數(shù)據(jù)的異常。因此,除了需要快速檢測到異常數(shù)據(jù),還必須正確地分析產(chǎn)生異常數(shù)據(jù)的原因,減少監(jiān)測預(yù)警系統(tǒng)的誤報和漏報。國內(nèi)外關(guān)于無線傳感器網(wǎng)絡(luò)的測量數(shù)據(jù)異常檢測已有不少研究成果。文獻將無線傳感器網(wǎng)絡(luò)節(jié)點的測量數(shù)據(jù)錯誤分為傳感器故障和測量誤差兩類,并提出了自適應(yīng)的故障檢測、測量誤差消除和數(shù)據(jù)校正的方法,但該方法僅利用一個鄰居節(jié)點的測量數(shù)據(jù)是否變化來證明有無傳感器故障,導(dǎo)致其檢測精度不夠高。文獻從事件的空間相關(guān)性和時間相關(guān)性入手,提出了一種以局部檢測為主的分布式事件區(qū)域檢測算法,通過檢驗傳感器本地采樣值構(gòu)成的時間序列與事件隨機過程統(tǒng)計特征的符合程度實現(xiàn)容錯。該算法有效地減少了節(jié)點之間的數(shù)據(jù)交換,但沒有特別設(shè)計事件邊緣節(jié)點的檢測算法。文獻利用相鄰傳感器讀數(shù)上的空間相關(guān)性,提出了用局部檢測技術(shù)來識別離群傳感器節(jié)點和離群事件的方法,但由于沒有考慮傳感器讀數(shù)的時間相關(guān)性,檢測精度受限。文獻提出基于直方圖的離群點檢測算法,該算法通過收集數(shù)據(jù)分布的直方圖信息,刪除無關(guān)數(shù)據(jù),識別潛在的離群點從而減少了通信開銷。缺點是忽視了數(shù)據(jù)間的空間相關(guān)性,且僅對一維數(shù)據(jù)有效,不適合多維數(shù)據(jù)。文獻提出基于距離技術(shù)識別top-n離群點,并引入聚集樹結(jié)構(gòu)以避免廣播通信開銷。但由于只考慮了數(shù)據(jù)間的時間相關(guān)性,在離群點的不斷確認(rèn)過程中增加了網(wǎng)絡(luò)通信開銷,不適合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)改變和多維數(shù)據(jù)的情況。上述方法由于忽略了數(shù)據(jù)間的空間相關(guān)性或時間相關(guān)性,影響了檢測精度,雖然采取了減少通信量和計算量的措施,但仍然存在通信量、計算量大等問題,并且只對一維數(shù)據(jù)有效。文獻提出一個基于聚類的全局離群點檢測技術(shù)識別傳感器節(jié)點的異常數(shù)據(jù)?；诰垲惖姆椒ú恍枰獢?shù)據(jù)分布的先驗知識,可以使用增量模型,即能給系統(tǒng)提供新的數(shù)據(jù)實例并且進行離群點檢測。然而,對于簇寬度參數(shù)難以設(shè)置合理的值。另外,算法涉及到計算多變量數(shù)據(jù)中數(shù)據(jù)實例間的距離問題,計算復(fù)雜度偏高。在上述研究基礎(chǔ)上,本文提出了一種基于DBSCAN算法的異常數(shù)據(jù)檢測方法,該方法利用距離定義數(shù)據(jù)的相似度進行劃分聚類,在中心基站對訓(xùn)練時段內(nèi)節(jié)點上傳的數(shù)據(jù)采用DB-SCAN算法進行訓(xùn)練提取環(huán)境特征集然后發(fā)送給節(jié)點,節(jié)點根據(jù)特征集對采集的新數(shù)據(jù)進行異常數(shù)據(jù)檢測,并且對由環(huán)境特征變化引起的異常數(shù)據(jù)進行訓(xùn)練實現(xiàn)環(huán)境特征的動態(tài)實時更新。最后,本文基于真實節(jié)點構(gòu)建的無線傳感器網(wǎng)絡(luò)系統(tǒng),完成了多組實驗,實驗結(jié)果表明了本文方法的有效性和實用性。1基于dbscan的異常數(shù)據(jù)檢測方法在實際環(huán)境中,通過傳感器節(jié)點可以感知到多維屬性的傳感測量值,這些多維屬性的傳感測量值構(gòu)成的向量可以認(rèn)為是代表當(dāng)前環(huán)境特點的環(huán)境特征點。在一個給定的時間周期內(nèi)將時間劃分為多個時間片,則每個時間片內(nèi)的環(huán)境特征點集的典型特征是基本穩(wěn)定并且可以提取的稱之為環(huán)境特征,所有這些環(huán)境特征組成的集合稱為環(huán)境特征集。以此為依據(jù),本文引入數(shù)據(jù)挖掘中聚類的經(jīng)典思路,將在一個具體環(huán)境中一定時間周期內(nèi)采集的環(huán)境特征點集看作聚類算法所要操作的數(shù)據(jù)集。正常情況下環(huán)境特征在一段時間內(nèi)不會發(fā)生明顯的突變,因此,將時間維度上劃分的若干時間片內(nèi)的環(huán)境特征點集看作通過聚類算法所獲得的簇,將每個時間片內(nèi)的環(huán)境特征看作通過聚類算法得到的簇的數(shù)據(jù)特征,從而提出了基于DBSCAN的異常數(shù)據(jù)檢測方法。DBSCAN算法是一種典型的基于密度的空間聚類算法,下文中的空間是指傳感器網(wǎng)絡(luò)測量數(shù)據(jù)集,空間中的一點表示數(shù)據(jù)集中的一個數(shù)據(jù),MinPts為給定的正整數(shù)。以下介紹DB-SCAN算法的幾個基本概念。定義1空間中任意一點的鄰域是以該點為圓心、以ε為半徑的圓區(qū)域內(nèi)包含的點的集合,ε的值由用戶給定。定義2空間中某一點的鄰域內(nèi)包含點的最小個數(shù)為MinPts,則稱該點為核心點。定義3點p從點q直接密度可達,若它們滿足:2)q是核心點,即|Nε(q)|≥MinPts。定義4點p從點q密度可達,若存在一個點鏈p1,…,pn,其中p1=q,pn=p且pi+1從pi(i=1,…,n-1)直接密度可達。如圖2所示。定義5點p和點q是密度連接的,若存在一個點o,使得p和q都是從o密度可達的。如圖3所示。本文提出的異常數(shù)據(jù)檢測方法的基本流程如圖4所示,大體分為兩個階段,即訓(xùn)練階段和檢測階段。訓(xùn)練階段的目的是獲得一個合理的環(huán)境特征集,以備檢測階段使用。訓(xùn)練階段:傳感器節(jié)點以一定的采樣頻率采集數(shù)據(jù)發(fā)送給sink節(jié)點,通過sink節(jié)點向中心基站上傳數(shù)據(jù)包Data[m],這個過程一直持續(xù)到訓(xùn)練周期結(jié)束。其中每個數(shù)據(jù)包Data[m]由多個屬性(如溫度、濕度、大氣壓力等)的傳感數(shù)據(jù)組成,m表示屬性個數(shù)。在中心基站,對訓(xùn)練周期內(nèi)的數(shù)據(jù)利用DBSCAN算法進行訓(xùn)練,得到一個核心點集即環(huán)境特征集CorePts[n],n表示包含的核心點個數(shù)。檢測階段:節(jié)點每次采集到新傳感數(shù)據(jù)時,就與環(huán)境特征集CorePts[n]進行一次線性遍歷比較,如果數(shù)據(jù)在核心點的鄰域范圍內(nèi),認(rèn)為是正常的傳感數(shù)據(jù),如果不在任一核心點的鄰域內(nèi),則認(rèn)為是異常數(shù)據(jù),并將其上報給中心基站。1.1基于密度可達的聚類在訓(xùn)練階段,采用聚類算法DBSCAN來得到合理的環(huán)境特征集。其基本思想是從訓(xùn)練數(shù)據(jù)集D中的任意一個點P開始,查找D中所有關(guān)于訓(xùn)練半徑r和最小個數(shù)MinPts從P密度可達的點。若P是核心點,則其鄰域內(nèi)的所有點和P屬于同一個類,這些點將作為下一輪的考察對象(即種子點),并通過不斷查找從種子點密度可達的點來擴展它們所在的類,直至找到最大類為止;若P不是核心點,即沒有對象從P密度可達,則P被暫時地標(biāo)注為噪聲。然后,算法對D中每個點都重復(fù)上述過程,當(dāng)所有種子點都被考察過,類擴展過程就完成了。此時,把訓(xùn)練出的聚類結(jié)果傳遞給節(jié)點。算法的偽代碼描述如下:1.2異常數(shù)據(jù)面向未確定點異常數(shù)據(jù)檢測算法的核心思想是:將采集的傳感數(shù)據(jù)分別與核心點集中的核心點進行歐幾里德距離計算,如果得到的距離小于等于訓(xùn)練半徑r,則認(rèn)為該數(shù)據(jù)為正常數(shù)據(jù);如果對核心點集遍歷一次得到的距離仍大于r,則認(rèn)為該數(shù)據(jù)是異常數(shù)據(jù)。此時統(tǒng)計數(shù)據(jù)出現(xiàn)異常的連續(xù)次數(shù),當(dāng)數(shù)據(jù)異常連續(xù)出現(xiàn)的次數(shù)大于最小個數(shù)MinPts時,則發(fā)送警報顯示有異常情況。算法的偽代碼描述如下:其中,DataSet是節(jié)點每次采集的溫度、濕度和光照;CorePts[i]是利用DBSCAN算法訓(xùn)練得到的核心點集(每個核心點包含溫度、濕度和光照),ClusterNum為核心點個數(shù)。訓(xùn)練半徑r和最小個數(shù)MinPts是用戶確定的兩個全局密度參數(shù),這兩個參數(shù)往往不能唯一確定,需要根據(jù)數(shù)據(jù)點集的具體分布情況來作出合理的選擇。其中最小個數(shù)MinPts用于判斷是否發(fā)送警報。2結(jié)果2.1節(jié)點節(jié)點設(shè)計室內(nèi)環(huán)境相對于工廠、野外等監(jiān)測環(huán)境而言,非異常傳感數(shù)據(jù)的變化相對緩和,更易于看出算法的效果。另外,室內(nèi)環(huán)境更易于實現(xiàn)供電,因此可以不考慮節(jié)點由于能量不足造成的節(jié)點故障。因此,本文實驗中的節(jié)點均布設(shè)在室內(nèi)。實驗中采用的傳感器節(jié)點是寧波中科基于JN5139無線傳感器網(wǎng)絡(luò)實驗平臺開發(fā)的GANISJ節(jié)點,傳感器類型包括溫度、濕度和光照三種,軟件采用TI的ZigBee協(xié)議棧。傳感器參數(shù)如表1所示。我們采用ZigBee協(xié)議棧來實現(xiàn)節(jié)點之間的通信,其中Router節(jié)點負(fù)責(zé)采集傳感器的數(shù)據(jù),并將數(shù)據(jù)周期性地發(fā)送到Coordinator節(jié)點,而且Router設(shè)備還將自動地轉(zhuǎn)發(fā)網(wǎng)絡(luò)中其他節(jié)點的數(shù)據(jù)。Coordinator節(jié)點接收Router上報的數(shù)據(jù),并通過串口上傳到中心基站(一臺PC機),在PC機上完成聚類運算。實驗網(wǎng)絡(luò)拓?fù)鋱D如圖5所示。2.2異常數(shù)據(jù)檢測本文對人工異常數(shù)據(jù)和事件產(chǎn)生的異常數(shù)據(jù)進行檢測設(shè)計了三個實驗。實驗一用于驗證異常數(shù)據(jù)檢測算法是否能夠準(zhǔn)確地檢測出異常數(shù)據(jù);實驗二用于驗證異常數(shù)據(jù)檢測算法是否能夠及時地發(fā)送警報;實驗三驗證該算法是否能夠?qū)崟r地檢測出異常數(shù)據(jù)并發(fā)送警報。實驗的訓(xùn)練周期為一天24個小時,采集溫度、濕度和光照三個參數(shù)。節(jié)點的采樣頻率為10s,采集1個小時生成360個數(shù)據(jù)作為檢測集合。實驗相關(guān)參數(shù)為:DBSCAN算法訓(xùn)練的半徑r為2,鄰域范圍內(nèi)數(shù)據(jù)的最小個數(shù)MinPts為10。實驗一每隔3分鐘節(jié)點上的溫度傳感器產(chǎn)生一個異常數(shù)據(jù)(采用程序自動注入異常數(shù)據(jù)),因此1個小時應(yīng)該生成20個異常數(shù)據(jù)。因為節(jié)點自身的定時器存在一定的誤差,實際注入了17個異常數(shù)據(jù),如圖6中溫度子圖所示。從圖6的檢測結(jié)果中我們可以看到節(jié)點檢測出26個異常數(shù)據(jù),其中17個是因為溫度傳感器產(chǎn)生的異常數(shù)據(jù),另外9個異常數(shù)據(jù)是由于環(huán)境特征的變化不在已有的環(huán)境特征集中,屬于正常的變化。可以看出:本算法可以準(zhǔn)確地檢測出異常數(shù)據(jù),并且檢測結(jié)果證明利用DBSCAN算法進行訓(xùn)練得到的特征集可以有效地進行異常數(shù)據(jù)的檢測。實驗二人工每隔10分鐘左右隨機打開一次加濕器來影響濕度傳感器產(chǎn)生一次事件,每次持續(xù)1分鐘左右。考慮到加濕器關(guān)閉后,各個參數(shù)恢復(fù)到正常需要持續(xù)一段時間,因此實際加濕器只打開了4次,也即產(chǎn)生了4次事件異常。從圖7中我們可以看到當(dāng)有事件發(fā)生時,濕度的值發(fā)生明顯的突變,并且溫度與光照的值都發(fā)生相應(yīng)的改變,說明事件發(fā)生后各個參數(shù)之間的變化有一定的相關(guān)性(這種相關(guān)性是因為加濕器產(chǎn)生了較大的加濕煙霧,直接對光照產(chǎn)生影響)。圖7的檢測結(jié)果顯示:節(jié)點可以準(zhǔn)確地檢測出事件引起的異常數(shù)據(jù)并發(fā)送警報,本實驗的采樣頻率為10s,打開加濕器后節(jié)點在第三次采集數(shù)據(jù)時即30s左右就檢測到異常數(shù)據(jù),所以本文提出的異常數(shù)據(jù)檢測方法能夠及時、有效地檢測出事件并發(fā)出警報。實驗三人工打開加濕器,產(chǎn)生6次事件,每次持續(xù)1分鐘左右,程序注入5次異常數(shù)據(jù)。從圖8的檢測結(jié)果中我們看到,出現(xiàn)的5個人工異常數(shù)據(jù)節(jié)點可以實時地檢測出來,并且可以實時地檢測6次事件產(chǎn)生的異常數(shù)據(jù)并發(fā)送警報,所以該方法能夠?qū)崟r、準(zhǔn)確的檢測出事件產(chǎn)生的異常數(shù)據(jù)和人工異常數(shù)據(jù)并及時地發(fā)送警報。3異常數(shù)據(jù)檢測本文以傳感數(shù)據(jù)異常檢測和區(qū)分問題為研究對象,針對環(huán)境監(jiān)測應(yīng)用,利用DBSCAN算法對訓(xùn)練時段內(nèi)的數(shù)據(jù)進行訓(xùn)練提取環(huán)境特征集,節(jié)