張建平,李 斌,劉學(xué)軍,胡 平

(南京工業(yè)大學(xué)電子與信息工程學(xué)院,南京 211816)

?

基于Hadoop的異常傳感數(shù)據(jù)時(shí)間序列檢測(cè)*

張建平,李 斌*,劉學(xué)軍,胡 平

(南京工業(yè)大學(xué)電子與信息工程學(xué)院,南京 211816)

無(wú)線傳感器網(wǎng)絡(luò)中,異常時(shí)間序列的研究具有十分重要的意義。針對(duì)傳統(tǒng)研究在海量數(shù)據(jù)環(huán)境中時(shí)間效率低下的問(wèn)題,提出了基于Hadoop的異常時(shí)間序列檢測(cè)算法。首先對(duì)時(shí)間序列進(jìn)行預(yù)處理,然后在Hadoop的MapReduce操作中調(diào)用動(dòng)態(tài)時(shí)間彎曲距離計(jì)算算法,實(shí)現(xiàn)了DTW距離計(jì)算的并行化,從而大大提高檢測(cè)速度。同時(shí)針對(duì)傳統(tǒng)DTW算法計(jì)算復(fù)雜度瓶頸問(wèn)題以及傳統(tǒng)約束方法準(zhǔn)確率較低問(wèn)題,提出了基于顯著特征匹配的局部約束算法,對(duì)彎曲路徑進(jìn)行局部限制,在確保準(zhǔn)確性的同時(shí)進(jìn)一步降低了時(shí)間、空間復(fù)雜度。Hadoop平臺(tái)下實(shí)驗(yàn)結(jié)果表明,該方法既提高了檢測(cè)速度,又保證了檢測(cè)準(zhǔn)確率。

無(wú)線傳感器網(wǎng)絡(luò);異常時(shí)間序列;Hadoop;局部約束;動(dòng)態(tài)時(shí)間彎曲

目前,物聯(lián)網(wǎng)技術(shù)作為一個(gè)新的技術(shù)熱點(diǎn)受到了廣泛的關(guān)注。在物聯(lián)網(wǎng)系統(tǒng)中,對(duì)傳感器海量采樣數(shù)據(jù)的處理顯得尤為重要。每個(gè)傳感器節(jié)點(diǎn)采集的數(shù)據(jù)可形成時(shí)間序列,而對(duì)時(shí)間序列的查詢及聚類在各種應(yīng)用領(lǐng)域中也逐漸成為核心數(shù)據(jù)操作,如語(yǔ)言識(shí)別領(lǐng)域、入侵檢測(cè)領(lǐng)域、金融領(lǐng)域等。在眾多的時(shí)間序列中,往往異常的時(shí)間序列是最具有研究?jī)r(jià)值的,而對(duì)異常時(shí)間序列的檢測(cè)通常轉(zhuǎn)化為對(duì)時(shí)間序列相似性的檢測(cè)。由Eamonn Keogh提出的動(dòng)態(tài)時(shí)間彎曲DTW(Dynamic Time Warping)距離方法,與傳統(tǒng)的Euclidean距離方法相比具有明顯的優(yōu)越性。DTW距離對(duì)那些帶有相似的底層模式但由于時(shí)間變形(如移位或延伸)彼此不同的序列具有很好的辨識(shí)度,因而大大提高了兩序列的檢測(cè)準(zhǔn)確性,但其具有較高的時(shí)間復(fù)雜度,在當(dāng)今大數(shù)據(jù)的環(huán)境下尤顯力不從心。因此,本文提出了一種基于Hadoop的異常時(shí)間序列檢測(cè)方法,采用MapReduce機(jī)制對(duì)海量時(shí)間序列進(jìn)行并行化處理,在提高檢測(cè)速度的同時(shí)又不顯著降低準(zhǔn)確性,同時(shí)引入基于顯著特征比對(duì)的局部約束方法(SDTW),進(jìn)一步降低了離群序列的時(shí)間復(fù)雜度。

本文后續(xù)內(nèi)容安排如下:第1節(jié)介紹了相關(guān)研究工作;第2節(jié)提出了一種基于Hadoop的離群時(shí)間序列檢測(cè)算法;第3節(jié)通過(guò)相關(guān)實(shí)驗(yàn)分析了該算法的性能;第4節(jié)總結(jié)了全文的工作,并進(jìn)行了展望。

1 相關(guān)工作

異常點(diǎn),又稱離群點(diǎn),是指明顯偏離其他對(duì)象的數(shù)據(jù)點(diǎn),這種偏離甚至引起人們懷疑它們產(chǎn)生于不同的機(jī)制[1-2]。相應(yīng)地,異常時(shí)間序列,是指采集到的與正常序列有很大差異的時(shí)間序列。時(shí)間序列為一系列隨著時(shí)間的變化而變化的數(shù)據(jù),這些數(shù)據(jù)可以描述隨著時(shí)間變化事物的某種狀態(tài)的變化。大部分的時(shí)間序列挖掘算法采用時(shí)間序列的相似性進(jìn)行研究,即將異常時(shí)間序列的挖掘轉(zhuǎn)化為求待檢測(cè)時(shí)間序列與標(biāo)準(zhǔn)時(shí)間序列的相似度。傳統(tǒng)的時(shí)間序列相似性度量方式采用歐式距離(Euclidean Distance),歐式距離最為簡(jiǎn)單直觀,但要求兩條時(shí)間序列長(zhǎng)度相同,且缺乏在時(shí)間軸上的伸縮性,因此動(dòng)態(tài)時(shí)間彎曲(DTW)距離作為一種新的度量方式被提出。Stan Salvador和Philip Chan[3]提出了一種FastDTW算法,它綜合了限制和數(shù)據(jù)抽樣兩種DTW常用的加速手段,對(duì)時(shí)間序列進(jìn)行粗粒度化、投影、細(xì)粒度化等操作,實(shí)現(xiàn)了DTW的加速,將時(shí)間、空間復(fù)雜度由傳統(tǒng)DTW算法的o(N2)降至o(N)。但由于采用了減少搜索空間的策略,FastDTW算法求得的彎曲時(shí)間路徑不一定是最佳路徑,因此算法在一定程度上影響了準(zhǔn)確性。李海林和楊麗彬[4]提出了一種增量動(dòng)態(tài)時(shí)間彎曲算法(IDTW),首先利用動(dòng)態(tài)時(shí)間彎曲方法對(duì)歷史時(shí)間數(shù)據(jù)進(jìn)行相似性度量,得到歷史最優(yōu)彎曲路徑及路徑中各元素的累積距離。然后通過(guò)逆向彎曲度量方法完成當(dāng)前序列的相似性度量,結(jié)合歷史數(shù)據(jù)信息找到與歷史彎曲路徑相交且度量時(shí)間序列距離為當(dāng)前最小值的新路徑,進(jìn)而實(shí)現(xiàn)增量動(dòng)態(tài)時(shí)間彎曲的相似性度量。此算法在分類準(zhǔn)確率和計(jì)算性能上都要優(yōu)于經(jīng)典動(dòng)態(tài)時(shí)間彎曲,但此算法對(duì)歷史數(shù)據(jù)的度量使得其在海量數(shù)據(jù)面前毫無(wú)優(yōu)勢(shì)。Thanawin Rakthanmanon和Bilson Campana[5]將4種新穎的方法結(jié)合在一起,在基于DTW算法的基礎(chǔ)上形成了一套UCR算法,不僅可以完成大規(guī)模時(shí)間序列的有效挖掘,同時(shí)解決了高層次的時(shí)間序列挖掘問(wèn)題。此外,該算法在時(shí)間序列數(shù)據(jù)流的實(shí)時(shí)監(jiān)控上也有很好的效果,同時(shí)降低了能耗。

基于以上研究,本文提出了一種基于Hadoop的異常傳感數(shù)據(jù)時(shí)間序列檢測(cè)算法。該算法利用了Hadoop集群,運(yùn)用MapReduce算法對(duì)擁有海量數(shù)據(jù)的時(shí)間序列進(jìn)行分布式運(yùn)算,大大降低算法的運(yùn)行時(shí)間,提高了時(shí)間序列的檢測(cè)效率。同時(shí),在計(jì)算DTW距離前,找出時(shí)間序列的顯著特征,對(duì)各時(shí)間序列的顯著特征進(jìn)行匹配以構(gòu)造局部約束,降低了DTW距離計(jì)算的空間搜索,從而與傳統(tǒng)DTW算法相比降低了時(shí)間、空間復(fù)雜度,且保留了應(yīng)有的準(zhǔn)確度。

2 相關(guān)定義及算法描述

2.1 MapReduce計(jì)算模型

Hadoop起源于Nutch項(xiàng)目,是Google公司的分布式文件系統(tǒng)GFS(Google File System)和MapReduce計(jì)算模型的開(kāi)源實(shí)現(xiàn)。Hadoop的核心是MapReduce計(jì)算框架,是一種并行編程模型和計(jì)算框架,用于并行計(jì)算大規(guī)模數(shù)據(jù)集,因此在處理海量數(shù)據(jù)上卓有成效[6-8]。

MapReduce模型中所有的Map操作彼此獨(dú)立并且完全并行,而且對(duì)于具有相同key值的中間鍵值對(duì),Reduce函數(shù)同樣可以執(zhí)行并行操作,因而有效提高了系統(tǒng)對(duì)數(shù)據(jù)并行化處理的能力[9]。MapReduce集群中的文件通常存儲(chǔ)在分布式文件系統(tǒng)(DFS)中,并進(jìn)行等大小分塊,傳送至集群上不同節(jié)點(diǎn)。執(zhí)行MapReduce任務(wù),用戶需要指定輸入文件、所需的Map任務(wù)數(shù)量和Reduce任務(wù)數(shù)量,并且提供Map和Reduce函數(shù),通常Map任務(wù)數(shù)與所給輸入文件分塊數(shù)相同[10]。MapReduce算法的執(zhí)行分為3個(gè)階段:Map階段、Shuffle/Sort階段和Reduce階段[11]。在Map階段,框架調(diào)用用戶自定義的Map函數(shù),處理所輸入的鍵值對(duì)list(k1,v1),同時(shí)生成一批新的鍵值對(duì)list(k2,v2)。在Shuffle/Sort階段,對(duì)Map階段輸出的結(jié)果按k2值進(jìn)行合并、分類,生成中間數(shù)據(jù)list(k2,list(vl2))。在Reduce階段,遍歷上階段生成的中間數(shù)據(jù),對(duì)每個(gè)唯一的k2,執(zhí)行用戶自定義的Reduce函數(shù),輸出新的鍵值對(duì)list(k3,v3)。圖1為MapReduce基本模型。

圖1 MapReduce基本模型

2.2 基于局部約束算法(SDTW)的動(dòng)態(tài)時(shí)間彎曲距離計(jì)算

時(shí)間序列通常都具有結(jié)構(gòu)特征,SDTW算法通過(guò)找出時(shí)間序列的顯著特征,對(duì)兩條時(shí)間序列的顯著特征進(jìn)行匹配,最終計(jì)算得出局部約束結(jié)果。根據(jù)局部約束結(jié)果可以得出局部約束邊帶大小及局部約束核位置。動(dòng)態(tài)時(shí)間彎曲距離的計(jì)算采用經(jīng)典的動(dòng)態(tài)規(guī)劃方法進(jìn)行計(jì)算。該算法提高了對(duì)彎曲路徑的搜索效率。

2.2.1 基于顯著特征匹配的局部約束算法(SDTW)

SIFT(Scale-Invariant Feature Transform)是一種檢測(cè)局部特征的算法,通常用于2維圖像檢索、三維重建[12]。本文提出一種近似SIFT算法,用于1維時(shí)間序列顯著特征的檢測(cè)。

近似SIFT算法首先檢測(cè)時(shí)間序列的特征點(diǎn)。在尺度空間中檢測(cè)出穩(wěn)定的特征點(diǎn)位置,需要將尺度空間在高斯差分中的極值與時(shí)間序列點(diǎn)進(jìn)行卷積。

定義1給定時(shí)間序列X,[xi,σ]為多尺度時(shí)間序列點(diǎn),則

①時(shí)間序列點(diǎn)的尺度空間為:L(xi,σ)=G(xi,σ)*X(i)=G(xi,σ)*xi,其中σ為時(shí)間尺度因子,σ取值越小,時(shí)間序列被平滑程度越小,對(duì)應(yīng)特征越細(xì);G(xi,σ)為一個(gè)可變尺度的一維高斯函數(shù),G(xi,σ)=(1/2πσ2)e-(xi)/2σ2。

②時(shí)間序列點(diǎn)高斯差分算子為:D(xi,σ)=L(xi,κσ)-L(xi,σ),其中κ[13]為常數(shù)。D(xi,σ)體現(xiàn)了時(shí)間序列點(diǎn)在不同尺度高斯平滑的差異,差異越大,成為特征點(diǎn)的可能越大。

定義2給定時(shí)間序列X,[xi,σ]為多尺度時(shí)間序列點(diǎn)(σ為時(shí)間尺度因子),若[xi,σ]的鄰居中有(1-ε)部分D(xj,σ)的值小于D(xi,σ),則稱[xi,σ]為特征點(diǎn)。(其中,ε為閾值,且是一個(gè)很小的正數(shù))。

圖2 特征點(diǎn)描述符的8維向量表征

時(shí)間序列特征點(diǎn)檢測(cè)完成后,需要對(duì)特征點(diǎn)進(jìn)行描述符的創(chuàng)建,即用一組向量將這個(gè)特征點(diǎn)描述出來(lái),這個(gè)描述符不僅包含特征點(diǎn),也包括了特征點(diǎn)周圍對(duì)其有貢獻(xiàn)的時(shí)間序列點(diǎn)。描述符的創(chuàng)建通過(guò)對(duì)特征點(diǎn)周圍區(qū)域分塊,計(jì)算塊內(nèi)梯度直方圖,生成具有獨(dú)特性的向量。時(shí)間序列中描述符通常采用4×2=8維向量表征,將特征點(diǎn)周圍區(qū)域分成4塊,每塊中計(jì)算兩個(gè)方向的梯度信息,如圖2所示。

特征點(diǎn)及特征點(diǎn)的描述符確定后,利用特征點(diǎn)的描述符進(jìn)行兩條時(shí)間序列特征點(diǎn)匹配對(duì)的查找。

定義3令s1,i為時(shí)間序列X1的特征點(diǎn),s2,j為時(shí)間序列X2的特征點(diǎn),若滿足以下條件:①兩個(gè)特征點(diǎn)的振幅差小于閾值τα;②兩個(gè)特征點(diǎn)的尺度比小于閾值τs;③不存在其他特征點(diǎn)s2,l,滿足上述兩種情況且描述符相似度滿足sim(s1,i,s2,j)×τd≤sim(s1,i,s2,l),其中τd為閾值(τd>1),則稱[s1,i,s2,j]為相匹配的特征點(diǎn)。

顯著特征匹配對(duì)確定后,兩條時(shí)間序列匹配特征的起始點(diǎn)與終止點(diǎn)構(gòu)成了特征的范圍邊界,利用這些信息即可計(jì)算局部相關(guān)約束[14]。如圖3所示,時(shí)間序列X,Y的顯著特征匹配對(duì)確定后,特征范圍邊界將每個(gè)時(shí)間序列分成一系列的連續(xù)區(qū)間,如圖區(qū)間A到E。局部約束的計(jì)算主要分為兩部分:自適應(yīng)核位置的確定和自適應(yīng)約束邊帶寬度的確定。

圖3 匹配特征范圍邊界

定義4給定時(shí)間序列X、Y,區(qū)間B,若B在時(shí)間序列X中的起始點(diǎn)和終止點(diǎn)分別為st(X,B)、end(X,B),在時(shí)間序列Y中分別為st(Y,B)、end(Y,B),且xi為X序列區(qū)間B中的任意一點(diǎn),則相對(duì)應(yīng)的候選點(diǎn)yj由下式可得:

(xi,yj)即確定了自適應(yīng)核位置。

定義5給定時(shí)間序列X、Y,時(shí)間序列X上的每個(gè)點(diǎn)xi,在時(shí)間序列Y上存在候選點(diǎn)yj且xi只與yj±ω/2范圍內(nèi)的點(diǎn)比較,其中ω為包含yj的區(qū)間寬度。

SDTW算法步驟如下:①求出輸入的時(shí)間序列的顯著特征點(diǎn);②創(chuàng)建匹配顯著特征點(diǎn)的描述符;③找出所要對(duì)比的一對(duì)時(shí)間序列的所有特征匹配對(duì);④利用所得特征匹配對(duì)計(jì)算局部約束:自適應(yīng)核位置和自適應(yīng)約束邊帶寬度。

2.2.2 基于SDTW算法的動(dòng)態(tài)時(shí)間彎曲距離計(jì)算

動(dòng)態(tài)時(shí)間彎曲(DTW)距離是一種允許在時(shí)間序列時(shí)間軸上彎曲的距離,與歐式距離不同的是,它不是完全的點(diǎn)對(duì)點(diǎn)距離,而是可以跳過(guò)若干點(diǎn)進(jìn)行匹配的距離,既保留了歐式距離的優(yōu)點(diǎn),同時(shí)也克服了它的不足。

設(shè)時(shí)間序列A,B長(zhǎng)度分別為m,n:A=(A1,A2,A3,…,Am);B=(B1,B2,B3,…,Bn)。則如圖4所示構(gòu)造一個(gè)m×n的網(wǎng)格,其中第i行j列記為,格代表的內(nèi)容為兩個(gè)時(shí)間序列點(diǎn)之間的歐氏距離值,記為dij(其中,dij=(Ai-Bj)2)。dij值越小,表明兩條時(shí)間序列的對(duì)象Ai、Bj之間越相似,因此這個(gè)網(wǎng)格也稱為時(shí)間序列A與B的匹配網(wǎng)格。動(dòng)態(tài)時(shí)間彎曲距離可以轉(zhuǎn)化成網(wǎng)格最優(yōu)路徑的計(jì)算,即從[1,1]出發(fā),對(duì)于若干滿足條件的路徑,計(jì)算每條路徑的距離之和,距離累加值最小的路徑為最優(yōu)路徑,通過(guò)動(dòng)態(tài)規(guī)劃的方法可實(shí)現(xiàn)這一過(guò)程。

圖4 序列A、B的匹配網(wǎng)格

定理1給定時(shí)間序列A=(A1,A2,A3,…,Am),B=(B1,B2,B3,…,Bn),dij=(Ai-Bj)2,則最優(yōu)路徑D如下:D=min{D,D,D}+dij

證明從<1,1>出發(fā),對(duì)于若干滿足條件的路徑,假設(shè)可以計(jì)算每條路徑到達(dá)時(shí)的累計(jì)距離值,則到達(dá)網(wǎng)格格點(diǎn)的上一個(gè)格點(diǎn)有且僅可能是,,及。又因?yàn)榫哂凶钚±塾?jì)距離值的路徑為最優(yōu)路徑,因此取3種累計(jì)距離的最小值即可。

基于SDTW算法的動(dòng)態(tài)時(shí)間彎曲距離計(jì)算是以DTW算法為基礎(chǔ),在時(shí)間序列的匹配中加入局部限定條件,減少累計(jì)距離的計(jì)算,從而降低路徑的搜索,具體偽代碼如下:

Function SDTW()

{

W=0; //初始化局部約束寬度

S=0; //初始化局部約束核位置

For(i=1;i

{

W=constraint_width(i); //時(shí)間序列A[i]所對(duì)應(yīng)的局部約束寬度 S=score_posi(i); //時(shí)間序列A[i]所對(duì)應(yīng)的核位置 For(j=s-w/2;j

{

Min=min{D,D,D}; //計(jì)算最小累計(jì)距離,累計(jì)距離不存在的不參與計(jì)算D=Min+dist(xi,yj); //計(jì)算動(dòng)態(tài)時(shí)間彎曲距離

}

}

}

2.3 基于Hadoop的異常時(shí)間序列檢測(cè)算法(HSDTW)

給定標(biāo)準(zhǔn)時(shí)間序列A,待檢測(cè)時(shí)間序列B1,B2,…,Bm,則B1,B2,…,Bm是否為異常時(shí)間序列的檢測(cè)分為兩個(gè)階段:(1)時(shí)間序列預(yù)處理階段;(2)Hadoop集群下計(jì)算階段。

第1階段時(shí)間序列的預(yù)處理

①將標(biāo)準(zhǔn)時(shí)間序列A按時(shí)間間隔(t,2t),(2t,3t),…,((n-1)t,nt)分成n份,且每份預(yù)處理為symbol_series=(symbol_normal,symbol_interval_nomal,value_normal)的形式。其中symbol_normal為時(shí)間序列標(biāo)記,時(shí)間序列A記為0;symbol_interval_nomal為時(shí)間序列時(shí)間段標(biāo)記,(t,2t),(2t,3t),…,((n-1)t,nt)依次記為t1至tn;value_normal為上述標(biāo)記下的時(shí)間序列內(nèi)容。

②同理將m條待檢測(cè)時(shí)間序列(B1,B2,…,Bm)依次按時(shí)間間隔t分成n份,且每份預(yù)處理為pending_series_Bi=(symbol_pending,symbol_interval_pending,value_pending)的形式.其中symbol_pending為時(shí)間序列標(biāo)記,時(shí)間序列B1～Bm依次記為1～m;symbol_interval_pending為時(shí)間序列時(shí)間段標(biāo)記;m個(gè)時(shí)間序列的時(shí)間間隔(t,2t),(2t,3t),…,((n-1)t,nt)全部依次記為t1至tn;value_normal為上述標(biāo)記下的時(shí)間序列內(nèi)容。

③將同一時(shí)間段的標(biāo)準(zhǔn)時(shí)間序列與不同的待檢測(cè)時(shí)間序列的預(yù)處理所得的內(nèi)容合并成一條記錄,即symbol_series+pending_series_Bi的形式,多條記錄形成的數(shù)據(jù)文件作為MapReduce的輸入。

第2階段將第1階段處理完成的數(shù)據(jù)文件存儲(chǔ)在HDFS上,數(shù)據(jù)自動(dòng)分塊至各個(gè)節(jié)點(diǎn),每個(gè)Map每次輸入一條記錄,迭代直至所有記錄處理完成,函數(shù)設(shè)計(jì)由3個(gè)部分組成:Map函數(shù)、Combine函數(shù)、Reduce函數(shù)。

①M(fèi)ap函數(shù)的設(shè)計(jì)

Map函數(shù)的輸入為〈k1,v1〉鍵值對(duì),k1是當(dāng)前樣本相對(duì)于輸入數(shù)據(jù)文件起始點(diǎn)的偏移量,v1為當(dāng)前樣本內(nèi)容。對(duì)本次時(shí)間段的兩條時(shí)間序列根據(jù)2.2節(jié)算法進(jìn)行DTW距離的計(jì)算,最終輸出〈k2,v2〉,其中k2為待檢測(cè)時(shí)間序列標(biāo)記symbol_pending,v2為兩時(shí)間序列之間的DTW距離。

②Combine函數(shù)的設(shè)計(jì)

Map任務(wù)的輸出結(jié)果通常保存在本地節(jié)點(diǎn)中,為了減少通訊代價(jià),采用combine操作,對(duì)Map任務(wù)的輸出進(jìn)行本地合并。在Combine函數(shù)的輸入〈k2,list(v2)〉中,k2為待檢測(cè)時(shí)間序列標(biāo)記symbol_pending,list(v2)是分配給標(biāo)記k2的兩時(shí)間序列DTW距離組成的鏈表,Combine函數(shù)將屬于同一標(biāo)記的DTW距離進(jìn)行相加運(yùn)算,最終輸出的〈k2,vl2〉中,k2為Combine函數(shù)的輸入,vl2為本地節(jié)點(diǎn)屬于k2的時(shí)間序列的DTW距離和。

③Reduce函數(shù)的設(shè)計(jì)

Reduce函數(shù)的輸入〈k2,list(vl2)〉中,k2為combine函數(shù)時(shí)間序列標(biāo)記,list(vl2)為各個(gè)combine函數(shù)輸出的中間結(jié)果組成的鏈表,Reduce函數(shù)將來(lái)自不同節(jié)點(diǎn)的相同k2值對(duì)應(yīng)的vl2值累加,同時(shí)定義參數(shù)flag,并將累加值與給定閾值ε比較,若累加值小于閾值,則k2值所代表的時(shí)間序列與標(biāo)準(zhǔn)時(shí)間序列相似,flag值為1;否則為離群時(shí)間序列,flag值為0。Reduce函數(shù)的輸出〈k3,v3〉對(duì)中,k3為Reduce函數(shù)的輸入值,v3為flag值。

對(duì)于Reduce函數(shù)的輸出〈k3,v3〉,若v3值為0,則此時(shí)間序列為離群時(shí)間序列,否則為非離群序列。

3 算法實(shí)驗(yàn)分析

本文實(shí)驗(yàn)部分采用10臺(tái)雙核計(jì)算機(jī)組建的Hadoop集群對(duì)時(shí)間序列進(jìn)行分析,操作系統(tǒng)為centos 6。其中一臺(tái)作為namenode,一臺(tái)作為secondarynamenode,其余8臺(tái)均作為datanode。每個(gè)節(jié)點(diǎn)Map的數(shù)量為8個(gè),Reduce的數(shù)量為1個(gè)。實(shí)驗(yàn)從算法的時(shí)間復(fù)雜度和準(zhǔn)確性兩方面討論算法的有效性,同時(shí)驗(yàn)證算法的加速比與可擴(kuò)展性。進(jìn)行對(duì)比的算法為標(biāo)準(zhǔn)DTW算法Classical_DTW、Sakoe-Chiba邊帶約束算法Sakoe-Chiba_DTW、局部約束算法SDTW,以及本文提出的基于Hadoop下的局部約束算法HSDTW。

3.1 算法的有效性分析

分別從算法的精確度和時(shí)間復(fù)雜度兩方面進(jìn)行了比較。為了驗(yàn)證HSDTW算法的有效性,本文將運(yùn)行在Hadoop集群上的HSDTW算法與串行的SDTW算法、Sakoe-Chiba_DTW算法、Classical_DTW算法采用5種不同大小的數(shù)據(jù)集進(jìn)行了詳細(xì)的對(duì)比。

3.1.1 精確度對(duì)比

精確度對(duì)比主要是對(duì)比不同算法執(zhí)行后結(jié)果的精確程度,即比較不同算法檢測(cè)到的正確的異常時(shí)間序列與實(shí)際異常時(shí)間序列的比值。實(shí)驗(yàn)對(duì)5組不同的數(shù)據(jù)集進(jìn)行多次檢測(cè),并將結(jié)果取平均值,圖5顯示了多次檢測(cè)所得結(jié)果。Sakoe-Chiba_DTW算法將時(shí)間序列的每個(gè)點(diǎn)與標(biāo)準(zhǔn)時(shí)間序列的ω%個(gè)點(diǎn)相比較,本次實(shí)驗(yàn)ω的取值有如下3種:20,10,6。而其他算法的ω取值均取決于局部約束計(jì)算結(jié)果。由圖5可知,本文提出的HSDTW算法的精確度較高,類似于SDTW的精確度,SDTW的精確度接近于Classical_DTW算法,而Sakoe-Chiba_DTW算法則展現(xiàn)出較差的準(zhǔn)確性,且隨著ω取值的降低,精確度越來(lái)越低。

圖5 不同算法精確度對(duì)比

3.1.2 時(shí)間復(fù)雜度對(duì)比

時(shí)間復(fù)雜度對(duì)比主要是比較不同算法執(zhí)行所需的時(shí)間,由于ω值越大,耗時(shí)越長(zhǎng),因此Sakoe-Chiba_DTW算法只取ω為20的情況進(jìn)行檢測(cè)。如圖6所示,在數(shù)據(jù)量較小的情況下,Sakoe-Chiba_DTW算法時(shí)間消耗較低卻以犧牲準(zhǔn)確性為前提,Classical_DTW算法雖然精確度很高,但以大量的時(shí)間消耗為代價(jià),SDTW算法在保持較高精確度的同時(shí)也具有較快的運(yùn)行速度,HSDTW算法與SDTW算法速度相似。但隨著數(shù)據(jù)量的越來(lái)越大,串行算法時(shí)間消耗明顯增大甚至導(dǎo)致溢出,而本文提出的HSDTW算法優(yōu)勢(shì)逐漸顯著,時(shí)間消耗低且在準(zhǔn)確性方面沒(méi)有明顯影響。

綜合對(duì)比這些算法的性能,本文提出的基于Hadoop下的局部約束算法HSDTW較好地兼顧了時(shí)間效率和算法精確度,具備較高的有效性。

圖6 不同算法時(shí)間復(fù)雜度對(duì)比

3.2 算法加速比分析

并行計(jì)算的性能通常通過(guò)加速比和可擴(kuò)展性兩方面來(lái)衡量。加速比的計(jì)算公式為Sp=Ts/Tp,其中Ts表示傳統(tǒng)串行算法所消耗的時(shí)間,Tp表示Hadoop平臺(tái)下的并行算法所消耗的時(shí)間。加速比越大,Hadoop平臺(tái)下并行算法的效率和性能提升越高。實(shí)驗(yàn)分別采用擁有10 000條記錄的數(shù)據(jù)集A、50 000條記錄的數(shù)據(jù)集B、100 000條記錄的數(shù)據(jù)集C在不同節(jié)點(diǎn)數(shù)的Hadoop集群下進(jìn)行檢測(cè),多次檢測(cè)后取平均值得加速比曲線如圖7所示。由圖可知,算法的加速比接近線性增長(zhǎng)。Hadoop集群中節(jié)點(diǎn)數(shù)越多,加速比越大,但增幅變緩;數(shù)據(jù)集數(shù)據(jù)量越大,加速比越大,即數(shù)據(jù)量越大,Hadoop平臺(tái)下的并行算法的優(yōu)勢(shì)越明顯。

圖7 算法加速比分析

3.3 算法可擴(kuò)展性分析

盡管隨著節(jié)點(diǎn)的增多,加速比在增大,但這并不能反映Hadoop集群的利用率。為此引入了擴(kuò)展率,擴(kuò)展率的計(jì)算公式為E=sp/n,其中sp為算法的加速比,n為節(jié)點(diǎn)個(gè)數(shù),擴(kuò)展率曲線如圖8所示。由圖可知,節(jié)點(diǎn)數(shù)越多,擴(kuò)展率隨之下降,這主要是由于節(jié)點(diǎn)的增多引起了通訊代價(jià)的增大。不過(guò),隨著數(shù)據(jù)量的增多,數(shù)據(jù)規(guī)模越來(lái)越大,可擴(kuò)展率反而在增大,這一結(jié)果進(jìn)一步驗(yàn)證了此算法在大數(shù)據(jù)集的上的性能優(yōu)勢(shì)。

圖8 算法可擴(kuò)展性分析

4 總結(jié)與展望

本文提出了一種基于Hadoop的異常傳感數(shù)據(jù)時(shí)間序列檢測(cè),與傳統(tǒng)異常時(shí)間序列檢測(cè)算法不同的是:首先引入了Hadoop集群,采用MapReduce機(jī)制對(duì)異常時(shí)間序列檢測(cè)算法進(jìn)行并行化處理,使海量異常時(shí)間序列的檢測(cè)變得高效。同時(shí)采用局部約束算法對(duì)傳統(tǒng)DTW算法進(jìn)行改進(jìn),減少最優(yōu)路徑的搜索空間,進(jìn)一步提升檢測(cè)速度。實(shí)驗(yàn)表明此算法既減少了時(shí)間上的計(jì)算開(kāi)銷,又保證了準(zhǔn)確率。本文接下來(lái)的工作是對(duì)算法的改進(jìn),進(jìn)一步提高算法的精確度,同時(shí),由于Hadoop平臺(tái)通常支持離線操作,如何實(shí)現(xiàn)低延遲也是將來(lái)需要進(jìn)一步深入研究的問(wèn)題,最后,本文研究還應(yīng)與具體實(shí)際應(yīng)用相結(jié)合,真正顯示算法的實(shí)用性。

[1] 唐琪,劉學(xué)軍. 無(wú)線傳感器網(wǎng)絡(luò)離群時(shí)間序列檢測(cè)研究[J]. 傳感技術(shù)學(xué)報(bào),2013,26(1):95-99.

[2]劉瑞琴,劉學(xué)軍. WSN中基于加速動(dòng)態(tài)時(shí)間彎曲的異常數(shù)據(jù)流檢測(cè)[J]. 傳感技術(shù)學(xué)報(bào),2013,26(6):887-893.

[3]Salvador S,Chan P. Toward Accurate Dynamic Time Warping in Linear Time and Space[J]. Intelligent Data Analysis,2007,11(5):561-580.

[4]李海林,楊麗彬. 基于增量動(dòng)態(tài)時(shí)間彎曲的時(shí)間序列相似性度量方法[J]. 計(jì)算機(jī)科學(xué),2013,40(4):227-230.

[5]Rakthanmanon T,Campana B,Mueen A,et al. Searching and Mining Trillions of Time Series Subsequences under Dynamic TimeWarping[C]//18th ACM SIGKDD Int Conf Knowledge Discovery and Data Mining. Beijing,China,2012:262-270.

[6]Lu W,Shen Y,Chen S,et al. Efficient Processing of k Nearest Neighbor Joins Using Mapreduce[J]. Proceedings of the VLDB Endowment,2012,5(10):1016-1027.

[7]Afrati F N,Fotakis D,Ullman J D. Enumerating Subgraph Instances Using Map-Reduce[C]//Data Engineering(ICDE),2013 IEEE 29th International Conference on IEEE. 2013:62-73.

[8]Vernica R,Carey M J,Li C. Efficient Parallel Set-Similarity Joins Using MapReduce[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. ACM,2010:495-506.

[9]He Q,Ma Y,Wang Q,et al. Parallel Outlier Detection Using kd-Tree Based on Mapreduce[C]//Cloud Computing Technology and Science(CloudCom),2011 IEEE Third International Conference on IEEE. 2011:75-80.

[10]Zhang C,Li F,Jestes J. Efficient Parallel kNN Joins for Large Data in MapReduce[C]//Proceedings of the 15th International Conference on Extending Database Technology. ACM,2012:38-49.

[11]趙彥榮,王偉平,孟丹,等. 基于Hadoop的高效連接查詢處理算法CHMJ[J]. 軟件學(xué)報(bào),2012,23(8):2032-2041.

[12]姜桂圓,張桂玲,張大坤. SIFT特征分布式算法提取[J]. 計(jì)算機(jī)研究與發(fā)展,2012,49(5):1130-1141.

[13]Lowe D G. Distinctive Image Features from Scale-Invariant Keypoints[J]. International Journal of Computer Vision,2004,60(2):91-110.

[14]Candan K S,Rossini R,Wang X,et al. sDTW:Computing DTW Distances Using Locally Relevant Constraints Based on Salient Feature Alignments[J]. Proceedings of the VLDB Endowment,2012,5(11):1519-1530.

張建平(1989),女,江蘇省南通市,碩士生,主要研究方向?yàn)閿?shù)據(jù)挖掘,異常檢測(cè),傳感器網(wǎng)絡(luò),zhangjianpingzl@163.com;

李斌(1979),男,江蘇省南京市,碩士,講師,主要研究方向包括數(shù)據(jù)庫(kù),傳感器網(wǎng)絡(luò)等,libean@139.com;

劉學(xué)軍(1971),男,江蘇省南京市,副教授,博士,主要研究方向包括數(shù)據(jù)庫(kù),數(shù)據(jù)挖掘,傳感器網(wǎng)絡(luò)等;

胡平(1962),男,江蘇南京市,副院長(zhǎng)/教授,主要研究領(lǐng)域?yàn)檫h(yuǎn)程教育研究、計(jì)算機(jī)智能等。

AbnormalTimeSeriesDetectioninWirelessSensorNetworkBasedonHadoop*

ZHANGJianping,LIBin,LIUXuejun,HUPing

(College of Electronic and Information Engineering,Nanjing Tech University,Nanjing 211816,China)

In wireless sensor network,the research of abnormal time series detection is of great significance. Due to the poor time efficiency of traditional research under big data,this paper proposes an algorithm about abnormal time series detection based on Hadoop. In this paper,time series are preprocessed firstly and then the DTW algorithm is called during MapReduce operation of Hadoop to realize the parallelization calculation of DTW distance. This measure improves the detection rate greatly. Meanwhile,to solve the bottleneck of computational complexity of classical DTW and the poor precision of the classical constraints,the paper also proposes locally relevant constraints based on salient feature alignments. It constraints the warping path locally to reduce the complexity of time and space further,it also ensures the precision of the algorithm at the same time. The results demonstrate that this algorithm not only decreases the time consumption,but also keeps a high precision.

wireless sensor network;abnormal time series;Hadoop;locally constraints;dynamic time warping

項(xiàng)目來(lái)源:國(guó)家公益性科研專項(xiàng)項(xiàng)目(201310162,201210022);連云港科技支撐計(jì)劃項(xiàng)目(SH1110)

2014-07-06修改日期:2014-10-30

TP393

:A

:1004-1699(2014)12-1659-07

10.3969/j.issn.1004-1699.2014.12.014