柳月強(qiáng) 張建鋒 祝麒翔 楊會君

(西北農(nóng)林科技大學(xué)信息工程學(xué)院 陜西 楊凌 712100)

0 引 言

傳感器持續(xù)采集的數(shù)據(jù)構(gòu)成數(shù)據(jù)流，每一個傳感器所產(chǎn)生的數(shù)據(jù)流具有連續(xù)、實時、高速等特征[1]。受傳感器數(shù)據(jù)概念漂移、運行環(huán)境以及傳感器部署方案等因素的影響，傳感器數(shù)據(jù)具有不確定性[2]。應(yīng)用異常檢測技術(shù)對部署在同一物理環(huán)境下的多個傳感器數(shù)據(jù)流進(jìn)行分析，將在一定程度上提高傳感器數(shù)據(jù)的準(zhǔn)確性和有效性[3]。傳感器在對物理環(huán)境進(jìn)行感知的過程中可獲得在時間上連續(xù)的離散點，數(shù)據(jù)觀測值與時間之間的關(guān)聯(lián)關(guān)系稱之為數(shù)據(jù)的時間相關(guān)性，傳感器數(shù)據(jù)流也稱為時間序列。在傳感器網(wǎng)絡(luò)部署中往往會利用不同類型的多個傳感器對物理空間進(jìn)行全面感知，這些不同類型的傳感器數(shù)據(jù)間具有的關(guān)聯(lián)關(guān)系稱為數(shù)據(jù)的空間相關(guān)性。根據(jù)無線傳感器網(wǎng)絡(luò)(WSN)的特點，將異常檢測的方法分為基于統(tǒng)計、基于分類、基于聚類、基于近鄰等方法。單傳感器數(shù)據(jù)流通常利用數(shù)據(jù)的時間相關(guān)性進(jìn)行異常檢測，多應(yīng)用基于統(tǒng)計分析、基于最近鄰距離等方法進(jìn)行異常檢測[4-5]。多傳感器數(shù)據(jù)流同時具有時間和空間相關(guān)性，通常應(yīng)用基于聚類的方法進(jìn)行檢測，在應(yīng)用聚類的過程中往往會忽略傳感器的時間相關(guān)性。

單傳感器數(shù)據(jù)流異常檢測是多傳感器數(shù)據(jù)流異常檢測的基礎(chǔ)。段青玲等[6]應(yīng)用滑動窗口和支持向量回歸相結(jié)合的方法，預(yù)測傳感器的測量值，確定置信區(qū)間，根據(jù)傳感器的實測值是否在區(qū)間內(nèi)來判斷數(shù)據(jù)是否異常。苑進(jìn)等[7]采用高斯過程對溫室中真實傳感器數(shù)據(jù)進(jìn)行單步預(yù)測，通過計算數(shù)據(jù)區(qū)間差異度來判斷異常，以上方法均無法對傳感器數(shù)據(jù)的多維度、屬性關(guān)聯(lián)等因素進(jìn)行預(yù)測。Sarvani等[8]應(yīng)用K-means算法對具有5個屬性的鳶尾花數(shù)據(jù)進(jìn)行聚類分析，與傳統(tǒng)方法相比，基于聚類的孤立點剔除(ORC)技術(shù)取得了更好的效果。而DBSCAN空間算法以其對小樣本數(shù)據(jù)聚類速度快、有效處理噪聲點、發(fā)現(xiàn)任意形狀等優(yōu)勢備受關(guān)注，在異常檢測技術(shù)領(lǐng)域也有研究，但目前應(yīng)用較少。

本文提出一種基于時空相關(guān)性的多傳感器數(shù)據(jù)異常檢測方法，首先利用最近鄰距離差算法實現(xiàn)數(shù)據(jù)流在時間序列上的孤立點和孤立群檢測；再應(yīng)用DBSCAN聚類算法對最近鄰距離差異常處理后的數(shù)據(jù)集進(jìn)行空間相關(guān)性聚類，實現(xiàn)多傳感器數(shù)據(jù)流的異常檢測。

1 相關(guān)定義與技術(shù)

1.1 異常點定義

異常點是指當(dāng)前數(shù)據(jù)觀測值與其他歷史數(shù)據(jù)觀測值之間有較大偏差的離群點，是一種由不同于正常的機(jī)制所產(chǎn)生的點[9]。不同的異?，F(xiàn)象將會導(dǎo)致不同的數(shù)據(jù)異常，采取的措施也會有所不同。Shikha等[10]通過對物聯(lián)網(wǎng)環(huán)境的研究，將產(chǎn)生異常的原因分為兩種，即事件和錯誤。

(1)事件：指與預(yù)定義的“通常行為”相比，物理環(huán)境狀態(tài)突然發(fā)生劇烈變化。一類是人類所不能控制的自然災(zāi)害如地震、火山等；另一類是由人類自身活動導(dǎo)致物聯(lián)網(wǎng)系統(tǒng)受到攻擊而無法工作。事件通常持續(xù)時間較長，同時會改變傳感器數(shù)據(jù)的歷史模式。

(2)錯誤：指由于傳感器數(shù)據(jù)噪聲、數(shù)據(jù)概念漂移，導(dǎo)致無線傳感網(wǎng)絡(luò)傳輸丟幀、網(wǎng)絡(luò)延緩等而造成觀測值不匹配且反復(fù)出現(xiàn)的一種變化。

本文只研究因錯誤導(dǎo)致的異常現(xiàn)象，將異常點定義為點異常、集體異常和關(guān)聯(lián)異常，其定義如下。

點異常：指單數(shù)據(jù)的實例與數(shù)據(jù)的正常模式不同，也可稱為數(shù)據(jù)跳躍。該異常點的觀測值與近鄰觀測值差異明顯，最易識別；集體異常：指一組連續(xù)的數(shù)據(jù)實例，其模式與整個正常模式不同；關(guān)聯(lián)異常：指數(shù)據(jù)實例在特定場景下發(fā)生的異常，也可稱為條件異常。

1.2 相關(guān)技術(shù)

最近鄰距離差的基本思想是度量對象之間的近鄰性，異常對象是指近鄰度較小的對象[12]。算法的優(yōu)點在于時間復(fù)雜度低，可以有效地應(yīng)用于時間序列異常檢測。近鄰距離差算法適合用于各種維度的數(shù)據(jù)集，假設(shè)數(shù)據(jù)集X的數(shù)據(jù)對象總數(shù)為N，數(shù)據(jù)維度為M，數(shù)據(jù)集X可表達(dá)為:

X={xi|xi∈RM,1≤i≤N}

(1)

其中數(shù)據(jù)對象xi為：

xi={xi1,xi2,…,xiM}

(2)

相鄰對象之間的距離為：

Dij={|Xi-Xj|,1≤i≤N,1≤j≤N}

(3)

該方法在判斷異常的過程中需要設(shè)置數(shù)據(jù)的鄰差閾值，通過鄰差閾值與測量值的比較來判斷是否異常，由于數(shù)據(jù)在不同的情況下波動不均衡，所以固定的閾值將會對數(shù)據(jù)的異常檢測造成不好的影響。

DBSCAN是一種將足夠密度區(qū)域作為聚類中心，不斷生長該區(qū)域的基于密度的空間聚類算法，其聚類原理如圖1所示，參數(shù)Eps為圓半徑，參數(shù)MinPts為鄰域內(nèi)樣本點數(shù)，在本例中MinPts≥4。圖中以A點為核心點，Eps為半徑，鄰域A中包含A、a1、a2、a34個點，選擇Eps鄰域的邊界點繼續(xù)拓展鄰域得到新的邊界點如點B、點C所示，隨著樣本點不斷擴(kuò)散，N在所有鄰域之外，則被標(biāo)記為離群點。圖中A在a1鄰域內(nèi)，A與a1直接密度可達(dá)，A同時也在a3鄰域內(nèi)，所以a1與a3密度可達(dá)。點C與a3密度可達(dá)，a3與a1密度可達(dá)，則可知點C與a1密度相連，進(jìn)而尋找到密度相連對象的最大集合即為聚類結(jié)果。由于DBSCAN算法采用的是全局參數(shù)，在處理不平衡數(shù)據(jù)時聚類效果不穩(wěn)定且在大樣本聚類中收斂時間長，因此降低全局參數(shù)影響是DBSCAN算法首要解決的問題[11]。

圖1 DBSCAN算法原理圖

2 基于時空相關(guān)性的異常檢測算法

本文針對環(huán)境傳感器數(shù)據(jù)的特點，應(yīng)用參數(shù)優(yōu)化來提升算法性能，將改進(jìn)后的K近鄰距離差(KNND)與聚類算法(PO_DBSCAN)結(jié)合，從時間和空間兩個角度分析多傳感器數(shù)據(jù)異常檢測的問題。在檢測數(shù)據(jù)的時間相關(guān)性中，應(yīng)用最近鄰距離差算法的動態(tài)閾值克服傳感器數(shù)據(jù)在時間序列上波動不均勻的問題，通過K個近鄰點的距離差排序計算數(shù)據(jù)異常得分，然后采用得分最高點的2K個近鄰點的距離均值來優(yōu)化鄰差閾值，完成異常檢測。在DBSCAN算法中，采用滑動窗口模型為多傳感器數(shù)據(jù)流設(shè)置固定的窗口大小和窗口重疊率，將數(shù)據(jù)集劃分為等量小樣本。DBSCAN算法聚類的參數(shù)可根據(jù)窗口內(nèi)部樣本特征設(shè)置，克服算法采用全局參數(shù)、大樣本收斂慢的問題，完成異常檢測。本文算法包括最近鄰距離差算法、DBSCAN算法參數(shù)優(yōu)化與異常檢測三部分。

2.1 KNND參數(shù)優(yōu)化

傳統(tǒng)的最近鄰距離差算法對局部數(shù)據(jù)不均勻波動的處理具有局限性，受文獻(xiàn)[12]的啟發(fā)，本文提出一種新的基于K近鄰距離差的異常檢測方法。通過參數(shù)優(yōu)化，將會有效地解決各個傳感器在時間序列上的異常問題，其步驟如下。

Step1獲取所有傳感器數(shù)據(jù)流，按照式(3)計算數(shù)據(jù)之間的距離差Dij。

Step2設(shè)置近鄰參數(shù)K，以K為窗口大小，窗口滑動步長為1，初始化異常得分S=0。

Step3對窗口內(nèi)點之間的距離差進(jìn)行排序，選擇距離差較大的q個點為距離優(yōu)勝點，并對其異常得分S加1，滑動窗口循環(huán)求出各個點的異常得分S。

Step4統(tǒng)計標(biāo)記異常得分為K的點，并求出該點左右相鄰的2K-1個點距離差的平均值mean。

Step5對異常得分為K的點進(jìn)行判斷，根據(jù)環(huán)境數(shù)據(jù)的不突變性和因錯誤導(dǎo)致異常的可控性，定義距離差超過均值的1.5倍則標(biāo)記該點為異常點。

Step6由Step 5可以確定數(shù)據(jù)中的點異常，判斷點異常處鄰近點的距離差正負(fù)變化情況，正負(fù)交替則將該點標(biāo)記為異常點，直到有連續(xù)單一變化則異常停止，該過程捕獲的連續(xù)異常點數(shù)大于K則將連續(xù)數(shù)據(jù)標(biāo)記為集體異常，反之為點異常。

Step7多維異常數(shù)據(jù)整合處理，對點異常通過近似值代替，消除異常；集體異常不做修改。

Step8整理數(shù)據(jù)，將K近鄰距離算法檢測并處理的數(shù)據(jù)集作為聚類算法的輸入。

2.2 DBSCAN參數(shù)優(yōu)化

基礎(chǔ)的DBSCAN算法采用全局唯一參數(shù)Eps和MinPts實現(xiàn)聚類，受文獻(xiàn)[13]采用局部參數(shù)進(jìn)行聚類的影響，本文提出一種基于滑動窗口數(shù)據(jù)劃分技術(shù)實現(xiàn)數(shù)據(jù)集在小樣本數(shù)據(jù)上利用局部參數(shù)進(jìn)行密度聚類的方法。PO_DBSCAN聚類算法流程如圖2所示。

圖2 PO_DBSCAN算法流程

PO_DBSCAN聚類算法的聚類過程由三部分組成，分別是參數(shù)更新、聚類、異常檢測。

參數(shù)更新過程中設(shè)置聚類窗口的大小并計算窗口內(nèi)各屬性間的平均距離差，以K為MinPst鄰域內(nèi)點的個數(shù)，以屬性間的歐氏距離為半徑Eps，保證數(shù)據(jù)在單獨情況下聚類無誤。其公式為：

(4)

式中：yi為屬性的平均距離差；M為滑動窗口的大小。

聚類過程中采用DBSCAN算法進(jìn)行聚類，針對屬性間相關(guān)性不一致的問題，通過給每一個屬性分配權(quán)重來降低對聚類效果的影響，權(quán)重WXY通過相關(guān)系數(shù)計算，其公式如下：

(5)

(6)

式中:Cov(X,Y)為屬性X與屬性Y的協(xié)方差；Var(X)為屬性X的方差；Var(Y)為屬性Y的方差。

異常檢測過程將對聚類結(jié)果進(jìn)行分析，在聚類過程中將首次被標(biāo)記為異常點的對象記為候選異常點，并設(shè)置異常得分加1(初值為0)，候選異常點進(jìn)入下一次循環(huán)，繼續(xù)進(jìn)行聚類標(biāo)記，更新異常得分，異常得分S與聚類次數(shù)C(聚類次數(shù)為滑動窗口重疊率的倒數(shù))相等則標(biāo)記為異常點，反之為正常點。

2.3 ODSTC異常檢測算法

綜上所述，ODSTC算法首先利用KNND算法進(jìn)行異常檢測與處理，然后利用PO_DBSCAN算法進(jìn)行聚類檢測并標(biāo)記，最后對所有異常點以及異常點類型進(jìn)行統(tǒng)一標(biāo)記，算法框架如算法1所示。

算法1基于時空相關(guān)性的多傳感器數(shù)據(jù)異常檢測

輸入：校試驗示范站信息服務(wù)體系項目多傳感器數(shù)據(jù)集。

輸出：通過算法檢測重新標(biāo)記的異常點以及異常點所屬的類型。

1.應(yīng)用滑動窗口技術(shù)劃分傳感器數(shù)據(jù)流

2.基于KNND算法對傳感器數(shù)據(jù)流進(jìn)行時間特性上異常檢測

3.對KNND算法檢測出來的異常點用不同的處理方式進(jìn)行處理

4.將處理后的數(shù)據(jù)集，再次利用滑動窗口模型劃分多傳感器數(shù)據(jù)流，作為聚類的輸入

5.PO_DBSCAN異常檢測算法對多傳感數(shù)據(jù)流進(jìn)行異常檢測

6.對聚類異常檢測出來的異常進(jìn)行標(biāo)記

7.異常點統(tǒng)一標(biāo)識，并標(biāo)記異常點類型

2.4 ODSTC算法性能分析

算法的性能分析往往從時間效率和空間效率兩個角度進(jìn)行，隨著計算機(jī)速度與容量的不斷提升，空間效率已經(jīng)不再是關(guān)注重點，故本文著重從時間效率進(jìn)行分析。

KNND算法將數(shù)據(jù)進(jìn)行劃分，然后再對滑動窗口內(nèi)的點進(jìn)行排序，隨著窗口的滑動來檢測異常點。算法的時間頻度可表示為：

f(n)=(n-w)·w·logw

(7)

式中：n為算法輸入規(guī)模；常數(shù)w為滑動窗口大小，滑動步長為1。所以KNND算法的時間復(fù)雜度T1(n)為：

T1(n)=O(f(n))=O(n-w)=O(n)

(8)

DBSCAN算法的時間復(fù)雜度為找出半徑Eps鄰域中的點所需要的時間，在最壞情況下其時間復(fù)雜度是O(n2)。PO_DBSCAN算法是采用滑動窗口對數(shù)據(jù)進(jìn)行劃分，其時間頻度可表示為：

(9)

式中:n為算法輸入規(guī)模，w為滑動窗口大小，即w2為常數(shù)，x為常數(shù)，即滑動步長為w/x，所以DBSCAN算法的時間復(fù)雜度T2(n)為:

(10)

ODSTC算法的時間復(fù)雜度為KNND與PO_DBSCAN算法時間復(fù)雜度之和，由加法法則可將ODSTC算法的時間復(fù)雜度表示為:

T(n)=O(max(f(n),g(n)))=O(n)

(11)

由此可知，ODSTC的時間復(fù)雜度呈線性增長，隨著處理數(shù)據(jù)樣本量的增大，時間效率比基礎(chǔ)的DBSCAN算法效率更高。在KNND算法中參數(shù)利用了時間序列的數(shù)據(jù)的不突變特性，PO_DBSCAN算法利用了多維數(shù)據(jù)的空間相關(guān)特性。充分考慮了數(shù)據(jù)相關(guān)性，有效地挖掘出數(shù)據(jù)的潛在關(guān)系，對提高算法檢測的準(zhǔn)確率具有積極意義。

3 實驗及結(jié)果分析

為了評估ODSTC算法的性能，本文采用西北農(nóng)林科技大學(xué)試驗示范站的環(huán)境數(shù)據(jù)進(jìn)行實驗。實驗在Inter(R)Core(TM)i5-6400 CPU，主頻2.70 GHz，內(nèi)存8 GB，操作系統(tǒng)Windows 10環(huán)境下進(jìn)行，編程環(huán)境采用MATLAB 2016a。分別實現(xiàn)了DBSCAN、PO_DBSCAN、KNND以及ODSTC算法，并根據(jù)不同規(guī)模數(shù)據(jù)集和不同算法進(jìn)行對比實驗。

3.1 數(shù)據(jù)集

環(huán)境數(shù)據(jù)集于2017年5月到2017年10月在西北農(nóng)林科技大學(xué)千陽蘋果試驗示范站采集。環(huán)境傳感器采集周期為10分鐘，采集的物理量包括空氣溫度、空氣濕度、總輻射、風(fēng)向、風(fēng)速、降雨量、土壤溫度、土壤濕度，構(gòu)成具有8個屬性的數(shù)據(jù)集。本文所采集的數(shù)據(jù)是集成在一個開發(fā)板上的多個傳感器分別采集的多維數(shù)據(jù)。根據(jù)數(shù)據(jù)之間的相關(guān)性強(qiáng)度，本文選取物理量空氣溫度、空氣濕度、總輻射、風(fēng)速四個強(qiáng)相關(guān)的屬性進(jìn)行相關(guān)性實驗。在進(jìn)行對比實驗中，本文采用四組不同規(guī)模的數(shù)據(jù)集進(jìn)行驗證實驗，實驗樣本記錄為1 440～8 640條，涉及數(shù)據(jù)點數(shù)為5 760～69 120個。千陽蘋果試驗示范站的環(huán)境相關(guān)數(shù)據(jù)均結(jié)合實際情況經(jīng)過專家標(biāo)記，異常來源均為錯誤，異常點分三類依次標(biāo)。數(shù)據(jù)集詳細(xì)信息如表1所示。

表1 實驗數(shù)據(jù)集

3.2 性能評價

為了衡量算法特性，本文引入性能指標(biāo)檢測率TPR(True Positive Rate)、誤報率FPR(False Positive Rate)和運行時間T。TPR是用來衡量異常值被正確標(biāo)記的概率，F(xiàn)PR是用來衡量正常值被錯誤標(biāo)記的概率，計算如下：

(12)

(13)

式中：TP表示被正確檢測出的異常值；TN表示未被檢測出來的異常值；FP表示正常值被檢測為異常值；FN表示正常值被檢測為正常值。

3.3 參數(shù)設(shè)置

基于時空相關(guān)性數(shù)據(jù)異常檢測算法分為三個步驟：首先應(yīng)用KNND檢測；然后應(yīng)用PO_DBSCAN算法進(jìn)行聚類異常檢測；最后對異常檢測結(jié)果進(jìn)行統(tǒng)一標(biāo)記。整個算法在運行過程中需要設(shè)置的參數(shù)有：近鄰點個數(shù)K、KNND檢測滑動窗口大小w1、KNND檢測窗口滑動重疊率d1、聚類檢測滑動窗口大小w2、聚類檢測滑動窗口重疊率d2。在聚類過程中因為數(shù)據(jù)的冗余影響聚類效果，滑動窗口根據(jù)數(shù)據(jù)的變化規(guī)律以及DBSCAN算法不適合大樣本聚類的特點設(shè)定，近鄰閾值參數(shù)Threshold等于2K個近鄰元素距離差均值mean，聚類參數(shù)MinPts等于K，Eps計算見式(4)。算法所需設(shè)置的參數(shù)詳細(xì)信息如表2所示。

表2 ODSTC算法參數(shù)

3.4 實驗結(jié)果分析

實驗采用4個數(shù)據(jù)集對三種不同算法進(jìn)行對比，檢測率和誤報率為數(shù)據(jù)集中三類異常點的平均值，詳細(xì)如表3所示?？梢钥闯?，本文所提出的ODSTC算法在TPR性能和FPR性能上較DBSCAN和PO_DBSCAN均有提升，隨著數(shù)據(jù)集的增大，算法的FPR平均降低0.3個百分點。對比文獻(xiàn)[14]與本文PO_DBSCAN算法，算法識別的準(zhǔn)確率提升了2個百分點。對比數(shù)據(jù)集QY_3與QY_4可以發(fā)現(xiàn)，當(dāng)算法中不相關(guān)屬性增加，算法的TPR約下降6個百分點，算法性能有所降低。由此可知本文算法在處理相關(guān)數(shù)據(jù)集時具有良好的檢測效率，但是針對數(shù)據(jù)中的不相關(guān)數(shù)據(jù)集其性能仍有待提升。綜上，本文算法與其他異常點檢測算法對比可得，前者的準(zhǔn)確率提升較大，且誤檢率也有明顯的降低。算法的檢測效率滿足應(yīng)用需求。

表3 異常檢測算法性能對比 %

本文截取數(shù)據(jù)集QY_1中空氣溫度的數(shù)據(jù)的檢測結(jié)果進(jìn)行統(tǒng)計，其中點異常17個，聚集異常58個，關(guān)聯(lián)異常17個，檢測率為98.5%，誤報率1.5%。為了更清晰地描述異常點被標(biāo)記情況，本文截取空氣溫度數(shù)據(jù)的前180個樣本點進(jìn)行繪圖，檢測結(jié)果如圖3所示?？諝鉁囟葦?shù)據(jù)的異常均在短時間內(nèi)發(fā)生(每個樣本采集間隔10 min)，導(dǎo)致異常的原因均為錯誤。

圖3 溫度數(shù)據(jù)異常檢測結(jié)果

實驗時間效率T通過對具有相等屬性，不同樣本數(shù)的數(shù)據(jù)集QY_1、QY_2、QY_3進(jìn)行對比驗證，對比結(jié)果如圖4所示。DBSCAN算法的運行時間增長速度最快，PO_DBSCAN與ODSTC算法的運行時間增長較慢，在數(shù)據(jù)集達(dá)到8 440小時，即數(shù)據(jù)點數(shù)達(dá)到337 760個時，PO_DBSCAN與ODSTC算法的運行時間少于DBSCAN算法的運行時間。結(jié)合前文對算法時間復(fù)雜度的分析可知，DBSCAN算法時間復(fù)雜度為O(n2)，PO_DBSCAN與ODSTC的時間復(fù)雜度為O(n)。當(dāng)樣本量增大到一定程度，PO_DBSCAN與ODSTC算法的時間效率較DBSCAN算法必然會有所提高。圖中PO_DBSCAN與ODSTC算法的運行時間差別較小，由此可知，KNND算法時間復(fù)雜度較低。綜上，ODSTC可用于多傳感器數(shù)據(jù)流的異常檢測。

圖4 異常檢測算法時間效率對比

4 結(jié) 語

本文提出的時空相關(guān)性數(shù)據(jù)異常檢測算法(ODSTC)結(jié)合了最近鄰算法與聚類算法的思想，針對環(huán)境數(shù)據(jù)的特點對算法的參數(shù)進(jìn)行優(yōu)化，克服了最近鄰距離閾值固定與聚類參數(shù)全局性及收斂速度慢等問題，提高了異常檢測的效率。實驗結(jié)果表明，ODSTC算法對多傳感器數(shù)據(jù)流的檢測準(zhǔn)確率更高，算法的時間效率也會隨著樣本量的增加而提高。針對具有相關(guān)性的多傳感器數(shù)據(jù)流，其效果滿足現(xiàn)行環(huán)境的使用。從實驗結(jié)果同樣也可看出，當(dāng)相關(guān)性較低的數(shù)據(jù)屬性加入后，算法的效率有所降低，今后研究將進(jìn)一步考慮不相關(guān)數(shù)據(jù)流的特征，提取頻域特征，結(jié)合當(dāng)?shù)貧夂蜃兓卣?，從不同維度進(jìn)行對照分析。