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

（南京工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211800）

基于Hadoop的不確定異常時(shí)間序列檢測(cè)*

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

（南京工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211800）

無線傳感器網(wǎng)絡(luò)中，傳感器的采集與無線網(wǎng)絡(luò)的傳輸?shù)染赡軒頃r(shí)間序列的不確定性，而大數(shù)據(jù)時(shí)代的到來使得傳統(tǒng)不確定異常時(shí)間序列檢測(cè)研究面臨時(shí)間效率低下的問題，為此提出基于Hadoop的不確定異常時(shí)間序列檢測(cè)算法。首先對(duì)不確定時(shí)間序列進(jìn)行壓縮變換，使不確定數(shù)據(jù)量大大減少，然后利用MapReduce架構(gòu)調(diào)用基于期望距離的不確定時(shí)間序列下的DTW算法，實(shí)現(xiàn)算法的并行化處理，降低算法時(shí)間復(fù)雜度。同時(shí)針對(duì)Hadoop集群任務(wù)級(jí)調(diào)度分配方法在運(yùn)行中負(fù)載分配不均現(xiàn)象，提出Hadoop集群優(yōu)化方法，明顯縮減集群總?cè)蝿?wù)時(shí)間，使得節(jié)點(diǎn)資源的利用更為合理。Hadoop平臺(tái)下實(shí)驗(yàn)結(jié)果驗(yàn)證顯示，該方法既提高了檢測(cè)速度，又保證了檢測(cè)準(zhǔn)確率。

無線傳感器網(wǎng)絡(luò)；不確定異常時(shí)間序列；Hadoop集群優(yōu)化；壓縮；動(dòng)態(tài)時(shí)間彎曲；期望距離

上世紀(jì)90年代開始，異常時(shí)間序列的檢測(cè)搜索開始被廣泛研究，而隨著科學(xué)技術(shù)的發(fā)展，這一問題的研究越來越為人們所關(guān)注，它廣泛應(yīng)用于各個(gè)鄰域，如傳感器網(wǎng)絡(luò)監(jiān)控、運(yùn)動(dòng)物體追蹤以及股票數(shù)據(jù)分析等。然而，現(xiàn)今大部分對(duì)異常時(shí)間序列的研究?jī)H僅停留在確定性時(shí)間序列的研究上，但現(xiàn)實(shí)生活中，對(duì)移動(dòng)對(duì)象的處理等產(chǎn)生的不確定性時(shí)間數(shù)據(jù)越來越多［1-2］。例如，在無線傳感器網(wǎng)絡(luò)中，無線傳感器網(wǎng)絡(luò)設(shè)備產(chǎn)生的數(shù)據(jù)天生就帶有不確定性，網(wǎng)絡(luò)傳輸過程中由于丟包等原因?qū)е陆邮盏降臄?shù)據(jù)往往也是不確定的。而傳統(tǒng)的異常時(shí)間序列檢測(cè)算法并不能直接應(yīng)用于不確定數(shù)據(jù)上，因此對(duì)傳統(tǒng)算法的改進(jìn)以及對(duì)新的適用算法的提出迫在眉睫。同時(shí)，不確定時(shí)間序列通常都具備長(zhǎng)度長(zhǎng)、數(shù)據(jù)量大的特點(diǎn)，大數(shù)據(jù)下的不確定異常時(shí)間序列檢測(cè)研究顯得尤為重要。因此本文提出一種基于Hadoop的不確定異常時(shí)間序列檢測(cè)算法，采用Hadoop框架對(duì)海量時(shí)間序列進(jìn)行并行化處理，提高檢測(cè)速度的同時(shí)確保檢測(cè)的準(zhǔn)確度。同時(shí)對(duì)不確定時(shí)間序列進(jìn)行壓縮預(yù)處理，并對(duì)預(yù)處理結(jié)果提出基于期望距離的不確定時(shí)間序列的距離度量UDTW，進(jìn)一步降低異常檢測(cè)的算法復(fù)雜度。此外，針對(duì)Hadoop集群任務(wù)級(jí)調(diào)度分配方法在運(yùn)行中負(fù)載分配不均現(xiàn)象，本文還提出Hadoop集群優(yōu)化方法，縮減集群總?cè)蝿?wù)時(shí)間，使得節(jié)點(diǎn)資源的利用更為合理。

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

1 相關(guān)工作

時(shí)間序列可以視為一個(gè)多維空間點(diǎn)，每個(gè)維度表示一個(gè)時(shí)間瞬間［3］。異常時(shí)間序列，通常被簡(jiǎn)單描述為傳感器等采集到的時(shí)間序列中與正常序列有較明顯差異的時(shí)間序列［4］。在之前的研究中，絕大數(shù)研究仍集中在確定時(shí)間序列上。通常確定時(shí)間序列為一條由確定的n維點(diǎn)組成的序列，相應(yīng)地，不確定時(shí)間序列則是一條不確定的n維點(diǎn)序列，如圖1所示。而隨著科技的發(fā)展，在實(shí)際應(yīng)用中，數(shù)據(jù)的各種不確定性使得不確定數(shù)據(jù)越來越多，這些不確定數(shù)據(jù)產(chǎn)生了大量的不確定時(shí)間序列，而時(shí)間序列中，異常時(shí)間序列的檢測(cè)在序列的挖掘中又有著不可或缺的顯著地位。Johannes A?falg等［5］于2009年首次提出一種概率性邊界范圍查詢（PBRQ）方法，定義兩條不確定時(shí)間序列之間的距離不確定，分別給定距離閾值α、概率閾值λ，認(rèn)為若待檢測(cè)不確定時(shí)間序列W與標(biāo)準(zhǔn)時(shí)間序列S之間的距離小于閾值α的概率大于等于閾值λ，即

PBRQα,λ（W,DB）=｛W∈DB|Pr（DIST（W,S）≤α）≥λ｝則待檢測(cè)時(shí)間序列與標(biāo)準(zhǔn)時(shí)間序列相似，否則為異常時(shí)間序列。該方法準(zhǔn)確地定義了不確定異常時(shí)間序列的檢測(cè)方法，但由于兩條不確定時(shí)間序列的距離是由大量可能的距離組成，因此，時(shí)間復(fù)雜度相對(duì)很高。Yuchen Zhao等［6］提出了不確定時(shí)間序列的小波分解構(gòu)造方法，針對(duì)不確定數(shù)據(jù)集占用大量存儲(chǔ)空間的問題提出Haar小波分解方法，將不確定數(shù)據(jù)進(jìn)行壓縮變換，同時(shí)采用兩種不同的模式優(yōu)化不確定性，此方法提高了查詢效率，但并沒有給出具體的不確定異常序列檢測(cè)方法。吳紅華、劉國(guó)華等［7］在Haar小波對(duì)數(shù)據(jù)壓縮變換的基礎(chǔ)上，對(duì)得到的不確定性時(shí)間序列概率維作縱向處理，提出一種選代表方法，采用概率最大法、均值法等選出一條確定的時(shí)間序列，并進(jìn)行降維、索引，根據(jù)查詢序列和數(shù)據(jù)庫中的時(shí)間序列各自的不確定性進(jìn)行組合，分別提出對(duì)應(yīng)組合的相似性匹配算法，但該算法并未考慮海量數(shù)據(jù)下時(shí)間復(fù)雜度高的問題，因此有待完善。

圖1 不確定時(shí)間序列

基于以上研究，本文提出一種基于Hadoop的不確定異常時(shí)間序列檢測(cè)算法，構(gòu)建Hadoop集群，運(yùn)用MapReduce算法對(duì)時(shí)間序列進(jìn)行分布式運(yùn)算，降低算法的運(yùn)行時(shí)間，使得大數(shù)據(jù)下的異常時(shí)間序列檢測(cè)變得高效。同時(shí)對(duì)不確定時(shí)間序列進(jìn)行壓縮處理，使原始的不確定性數(shù)據(jù)量大大減少，降低存儲(chǔ)空間。并對(duì)預(yù)處理得到的不確定時(shí)間序列采用基于期望距離的不確定時(shí)間序列的距離度量UDTW，計(jì)算不確定時(shí)間序列的DTW距離，從而簡(jiǎn)化不確定時(shí)間序列的建模，進(jìn)一步降低存儲(chǔ)代價(jià)。此外，針對(duì)當(dāng)前Hadoop集群固有的任務(wù)級(jí)調(diào)度分配方法在運(yùn)行中負(fù)載分配不均現(xiàn)象，采用基于節(jié)點(diǎn)能力的任務(wù)自適應(yīng)調(diào)度分配方法對(duì)集群進(jìn)行優(yōu)化，使得集群總?cè)蝿?wù)時(shí)間明顯縮減，各節(jié)點(diǎn)負(fù)載更加均衡，節(jié)點(diǎn)資源的利用更為合理。

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

2.1 不確定時(shí)間序列壓縮法（EDC）概述

通常時(shí)間序列為確定的n維點(diǎn)序列，而不確定時(shí)間序列在每個(gè)時(shí)間點(diǎn)上的取值是不確定的，這些數(shù)據(jù)點(diǎn)的可能取值由一系列取樣點(diǎn)組成，每個(gè)取樣點(diǎn)以一定的概率出現(xiàn)或服從某種分布，因此每個(gè)時(shí)間點(diǎn)上的取值用一個(gè)隨機(jī)變量表示，不確定時(shí)間序列被認(rèn)為是具有時(shí)間特性的隨機(jī)變量的有序序列。

定義1（不確定時(shí)間序列）已知不確定時(shí)間序列XU，時(shí)間長(zhǎng)度為n，每個(gè)時(shí)刻的樣本觀察值個(gè)數(shù)為s，則不確定時(shí)間序列可表示為：

其中，ti為第i個(gè)時(shí)刻，Vi為第i個(gè)時(shí)刻觀察值的集合，記為Vi=｛Vi,1,Vi,2,...,Vi,s｝。

由于不確定時(shí)間序列每個(gè)時(shí)刻可能值較多，往往數(shù)據(jù)量很大，因此時(shí)間序列的有效壓縮對(duì)后續(xù)時(shí)間序列的深入計(jì)算與分析必不可少。本文提出不確定時(shí)間序列壓縮表示方法，對(duì)不確定時(shí)間序列每個(gè)時(shí)刻的可能觀察值，采用均值等表示形式對(duì)樣本觀察值進(jìn)行壓縮表示，避免直接存儲(chǔ)不確定時(shí)間序列的所有可能值。

用四元組代替原始數(shù)據(jù)，得到不確定時(shí)間序列的壓縮表示法，減少了數(shù)據(jù)量并降低了存儲(chǔ)空間。同時(shí)由于本文后續(xù)不確定時(shí)間序列的DTW距離計(jì)算中涉及每個(gè)時(shí)刻樣本觀察值均值、方差計(jì)算，此種壓縮方法也為DTW距離計(jì)算提供了計(jì)算基礎(chǔ)，減少了算法的整體計(jì)算量。此外，若每個(gè)時(shí)刻的可能觀察值增多，原有的四元組仍能有效表示可能值增多下的不確定時(shí)間序列，避免重復(fù)計(jì)算，降低計(jì)算成本。例1展示了這一過程。

例1 已知不確定時(shí)間序列XU，由n個(gè)形如（ti,si,Ei,Di）的四元組壓縮表示，t1時(shí)刻樣本觀察值為a1,a2,......,as1共s1個(gè)，樣本觀察值均值為E1，樣本觀察值平方和為D1，若此時(shí)t1時(shí)刻樣本觀察值個(gè)數(shù)增加為s1+1，新增觀察值為as1+1，則樣本觀察值均值為

值增加時(shí)，不確定時(shí)間序列可由原始四元組壓縮表示方法線性計(jì)算得出。

2.2 不確定時(shí)間序列的DTW距離計(jì)算（UDTW）

從概率角度，不確定數(shù)據(jù)通常被認(rèn)為是一個(gè)隨機(jī)變量，因此不確定數(shù)據(jù)X、Y之間的距離為隨機(jī)變量X、Y上的某個(gè)函數(shù)，因此，利用隨機(jī)變量X、Y的距離函數(shù)定義的隨機(jī)變量Z的期望來度量X、Y之間的距離是一種自然的想法［8］。

定理1 給定兩個(gè)相互獨(dú)立的不確定數(shù)據(jù)X、Y，且度量方式為歐式度量，則X、Y之間的期望距離為：ED（X,Y）=（E（X）-E（Y）2+D（X）+D（Y）。其中，E（X）為X的期望，D（X）為X的方差。

證明：

定義3 給定不確定時(shí)間序列X、Y，則最優(yōu)動(dòng)態(tài)時(shí)間彎曲距離UDTW＜i,j＞如下：

2.3 基于Hadoop的不確定異常時(shí)間序列檢測(cè)算法（HUDTW）

2.3.1 Hadoop簡(jiǎn)介及Hadoop集群優(yōu)化

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

Hadoop框架中，每個(gè)作業(yè)被分割成等大小任務(wù)塊傳送至不同節(jié)點(diǎn)，所有任務(wù)完成才標(biāo)志著作業(yè)的完成［11］。MapReduce的工作框架由一個(gè)主節(jié)點(diǎn)和多個(gè)從節(jié)點(diǎn)組成，JobTracker運(yùn)行在主節(jié)點(diǎn)上，Task-Tracker運(yùn)行于從節(jié)點(diǎn)。JobTracker將作業(yè)分成Map任務(wù)與Reduce任務(wù)，當(dāng)TaskTracker發(fā)出請(qǐng)求時(shí)，JobTracker分配任務(wù)給從節(jié)點(diǎn)執(zhí)行。由于JobTracker監(jiān)聽到任務(wù)請(qǐng)求后就會(huì)分配相應(yīng)的任務(wù)，不管節(jié)點(diǎn)處理能力的高低，因此會(huì)出現(xiàn)：弱節(jié)點(diǎn)負(fù)載過重、剩余任務(wù)分配不合理、優(yōu)勢(shì)節(jié)點(diǎn)資源浪費(fèi)等情況［12］。為避免此現(xiàn)象發(fā)生，本文以節(jié)點(diǎn)當(dāng)前的負(fù)載狀態(tài)作為參考標(biāo)準(zhǔn)，評(píng)價(jià)節(jié)點(diǎn)計(jì)算資源的利用程度，節(jié)點(diǎn)根據(jù)評(píng)價(jià)值再對(duì)運(yùn)行任務(wù)的數(shù)量進(jìn)行調(diào)整，達(dá)到集群優(yōu)化的效果。節(jié)點(diǎn)的權(quán)值代表節(jié)點(diǎn)處理任務(wù)的能力，本文定義的節(jié)點(diǎn)權(quán)值與以下三個(gè)方面有關(guān)：節(jié)點(diǎn)性能、任務(wù)特征、節(jié)點(diǎn)失效率。

定義4

①若Hadoop集群中有n個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)性能為N，任務(wù)特征為T，節(jié)點(diǎn)失效率為F［13］，則節(jié)點(diǎn)i的權(quán)值為：②若Hadoop集群中有n個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)i的權(quán)值為Wi，所有節(jié)點(diǎn)中最大權(quán)值為Wmax，則節(jié)點(diǎn)的權(quán)值比例參數(shù)為：

集群優(yōu)化主要分為兩部分：一、JobTracker端任務(wù)分配，二、TaskTracker端的自適應(yīng)調(diào)節(jié)。當(dāng)Tasktracker請(qǐng)求分配任務(wù)時(shí)，將該節(jié)點(diǎn)的權(quán)值比例參數(shù)Pi傳遞給JobTracker，JobTracker根據(jù)該節(jié)點(diǎn)的空閑slot數(shù)numslot及權(quán)值比例參數(shù)給該節(jié)點(diǎn)分配基本任務(wù)數(shù)（也稱最小任務(wù)數(shù)）numtask，式（2）可計(jì)算基本任務(wù)數(shù)：

TaskTracker獲取基本任務(wù)后，會(huì)存在剩余的slot槽，若剩余槽數(shù)大于節(jié)點(diǎn)第一次分配任務(wù)后的剩余槽數(shù)，節(jié)點(diǎn)繼續(xù)請(qǐng)求分配任務(wù)，否則由目前節(jié)點(diǎn)負(fù)載狀態(tài)決定是否繼續(xù)申請(qǐng)任務(wù)。

定義5 若周期讀取TaskTracker節(jié)點(diǎn)的CPU利用率、內(nèi)存使用率、網(wǎng)絡(luò)利用率分別為Ucpu、 Umem、Unet，且CPU、內(nèi)存和網(wǎng)絡(luò)帶寬在當(dāng)前節(jié)點(diǎn)負(fù)載中所占的比重分別為 fcpu、fmem、fnet，則節(jié)點(diǎn)負(fù)載狀態(tài)為：

比較負(fù)載狀態(tài)Load與節(jié)點(diǎn)負(fù)載閾值Threshold，若Load＜Threshold，繼續(xù)分配任務(wù)，否則停止申請(qǐng)。2.3.2 基于Hadoop的不確定異常時(shí)間序列檢測(cè)算

法（HUDTW）

由于不確定時(shí)間序列的可能世界較多，因此不確定時(shí)間序列數(shù)據(jù)量相對(duì)確定時(shí)間序列要大的多，而隨著大數(shù)據(jù)時(shí)代的到來，傳統(tǒng)檢測(cè)算法已無法保證時(shí)間上的高效性，因此本文提出了基于Hadoop的不確定異常時(shí)間序列檢測(cè)算法，采用分布式計(jì)算方法降低檢測(cè)時(shí)間，提高檢測(cè)效率。給定標(biāo)準(zhǔn)不確定時(shí)間序列與待檢測(cè)不確定時(shí)間序列，則判斷待檢測(cè)不確定時(shí)間序列是否為異常時(shí)間序列首先要將時(shí)間序列進(jìn)行分段處理，并整合形成文件上傳至hdfs文件系統(tǒng)，然后進(jìn)行MapReduce并行運(yùn)算，最終輸出結(jié)果。算法詳細(xì)步驟如下：

輸入：采集到的標(biāo)準(zhǔn)不確定時(shí)間序列A，待檢測(cè)不確定時(shí)間序列B1，B2，…，Bm

輸出：異常時(shí)間序列標(biāo)志flag

Step 1 對(duì)所有不確定時(shí)間序列進(jìn)行EDC壓縮處理。

Step 2 將標(biāo)準(zhǔn)不確定時(shí)間序列A按時(shí)間間隔t分成n份，并處理為series=＜s，s_in，v＞的形式。其中s為時(shí)間序列A標(biāo)記，記為0；s_in為時(shí)間序列時(shí)間段標(biāo)記，（t，2t），…，（n-1）t，nt）依次記為t1至tn；v為上述標(biāo)記下的時(shí)間序列內(nèi)容。

Step 3 同理將m條待檢測(cè)時(shí)間序列（B1，B2，…，Bm）依次按時(shí)間間隔t分成n份，處理為Pseries=＜Ps，Ps_in，Pv＞的形式.其中Ps為時(shí)間序列標(biāo)記，B1～Bm依次記為1～m；Ps_in為時(shí)間序列時(shí)間段標(biāo)記，m條待檢測(cè)時(shí)間序列的時(shí)間間隔（t，2t），…，（n-1）t，nt）全部依次記為t1至tn；Pv為上述標(biāo)記下的時(shí)間序列內(nèi)容。

Step 4 將s_in值與Ps_in值相同的記錄合并成一條記錄，多條記錄形成的數(shù)據(jù)文件上傳至hdfs，執(zhí)行MapReduce函數(shù)，函數(shù)由三個(gè)部分組成：Map函數(shù)、Combine函數(shù)、Reduce函數(shù)。

①M(fèi)ap函數(shù)

方法：對(duì)當(dāng)前時(shí)間段的標(biāo)準(zhǔn)不確定時(shí)間序列與m條待檢測(cè)不確定時(shí)間序列根據(jù)2.3.2節(jié)算法分別進(jìn)行DTW距離的計(jì)算

輸出：k2,v2。k2為待檢測(cè)時(shí)間序列標(biāo)記，v2為兩時(shí)間序列之間的DTW距離。

②Combine函數(shù)

輸入：k2,list（v2）。k2為待檢測(cè)時(shí)間序列標(biāo)記，list（v2）是分配給標(biāo)記k2的兩時(shí)間序列DTW距離組成的鏈表

方法：將屬于同一標(biāo)記的DTW距離進(jìn)行相加運(yùn)算

輸出：k2,vl2。k2為Combine函數(shù)的輸入，vl2為本地節(jié)點(diǎn)屬于k2的不確定時(shí)間序列的DTW距離和。

③Reduce函數(shù)

輸入：k2,list（vl2）。k2為combine函數(shù)時(shí)間序列標(biāo)記，list（vl2）為各個(gè)combine函數(shù)輸出的中間結(jié)果組成的鏈表，

方法：將不同節(jié)點(diǎn)的相同k2值對(duì)應(yīng)的vl2值累加，定義參數(shù) flag，將累加值與給定閾值ε比較，若累加值小于閾值，則k2值所代表的時(shí)間序列與標(biāo)準(zhǔn)時(shí)間序列相似，flag值為0；否則為離群時(shí)間序列，flag值為1。

輸出：k3,v3。k3為Reduce函數(shù)的輸入值，v3為 flag值。

Step 5 對(duì)于Reduce函數(shù)的輸出k3,v3，若v3值為1，則此時(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)首先采用默認(rèn)Hadoop集群從算法的時(shí)間復(fù)雜度和準(zhǔn)確性兩方面討論算法的有效性。進(jìn)行對(duì)比的算法為面向不確定時(shí)間序列的分類方法UDTWL、概率性邊界范圍查詢方法PBRQ、以及本文提出的基于Hadoop的不確定異常時(shí)間序列檢測(cè)算法HUDTW。然后對(duì)比默認(rèn)Hadoop集群及本文提出的優(yōu)化集群在不同數(shù)據(jù)量下的時(shí)間復(fù)雜度，驗(yàn)證優(yōu)化集群的時(shí)間高效性。實(shí)驗(yàn)采用的數(shù)據(jù)為無線傳感器采集數(shù)據(jù)，且由于傳感器采集的數(shù)據(jù)具有顯著大數(shù)據(jù)特征，因而十分適合Hadoop平臺(tái)下開發(fā)應(yīng)用，所以實(shí)驗(yàn)也進(jìn)一步驗(yàn)證了本算法在WSN環(huán)境中的高效應(yīng)用。

3.1 算法的有效性分析

算法的有效性從算法的時(shí)間復(fù)雜度及算法的準(zhǔn)確性兩反面進(jìn)行對(duì)比，為準(zhǔn)確驗(yàn)證算法的有效性，本次實(shí)驗(yàn)采集五組不同大小數(shù)據(jù)集分別采用運(yùn)行在Hadoop集群上的HUDTW算法、串行UDTWL算法、串行PBRQ算法測(cè)試算法的時(shí)間復(fù)雜度和精確度。

3.1.1 精確度對(duì)比

精確度對(duì)比是比較不同算法檢測(cè)不確定異常時(shí)間序列的準(zhǔn)確程度，即對(duì)比檢測(cè)到的正確的不確定異常時(shí)間序列與實(shí)際不確定異常時(shí)間序列的比值。實(shí)驗(yàn)采集五組大小不同的數(shù)據(jù)集進(jìn)行多次檢測(cè)取平均值，對(duì)三種不同算法的精確度進(jìn)行了科學(xué)比對(duì)，圖2為多次檢測(cè)所得結(jié)果。由圖可知，PBRQ算法未對(duì)數(shù)據(jù)進(jìn)行任何降維處理，取完整的數(shù)據(jù)信息進(jìn)行檢測(cè)，因而精確性極高，本文提出的HUDTW算法檢測(cè)結(jié)果與之類似，同樣展現(xiàn)了較高的準(zhǔn)確度，UDTWL算法由于采用減枝方法一定程度上降低了算法的精確度。

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

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

時(shí)間復(fù)雜度對(duì)比主要是不同算法執(zhí)行所消耗的時(shí)間的對(duì)比。從理論上分析，PBRQ算法為最原始的判定方法，由于兩條不確定時(shí)間序列的距離是由大量可能的距離組成，而PBRQ算法未對(duì)時(shí)間序列進(jìn)行任何降維處理，因此，時(shí)間復(fù)雜度相對(duì)很高。UDTWL算法為一種面向不確定時(shí)間序列的分類方法，對(duì)不確定時(shí)間序列采用DTW距離進(jìn)行度量，由于該算法采用了下屆函數(shù)等對(duì)算法進(jìn)行很好的減枝，因而復(fù)雜度低于傳統(tǒng)的PBRQ算法。而本文提出的HUDTW算法則采用Hadoop并行框架，與上述串行算法相比復(fù)雜度自然大幅下降。實(shí)驗(yàn)結(jié)果由圖3可知，數(shù)據(jù)量很小時(shí)，UDTWL算法時(shí)間消耗低卻犧牲了精確度，PBRQ算法精確度雖高，卻是以很高的時(shí)間復(fù)雜度為代價(jià)，HUDTW算法則在確保準(zhǔn)確性的同時(shí)維持了低時(shí)間復(fù)雜度。隨著數(shù)據(jù)量逐漸增大，串行算法時(shí)間消耗急劇增長(zhǎng)甚至導(dǎo)致溢出，而本文提出的HUDTW算法優(yōu)勢(shì)逐漸明顯，不僅時(shí)間復(fù)雜度低，而且維持了較高的精確度。

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

3.2 對(duì)比分析

由于默認(rèn)Hadoop集群假想環(huán)境仍為同構(gòu)的集群系統(tǒng)，當(dāng)各節(jié)點(diǎn)執(zhí)行能力存在差異時(shí)，易形成過多的備份任務(wù)被推測(cè)執(zhí)行，造成資源浪費(fèi)，引起不必要的時(shí)間消耗。而本文提出的優(yōu)化集群能使各節(jié)點(diǎn)自適應(yīng)地對(duì)運(yùn)行的任務(wù)量進(jìn)行調(diào)整，明顯縮短集群任務(wù)的完成時(shí)間。實(shí)驗(yàn)采用默認(rèn)Hadoop集群及優(yōu)化集群（Hadoop_OP）分別執(zhí)行不確定異常時(shí)間序列檢測(cè)算法，數(shù)據(jù)量分別為1.0 Gbyte、1.5 Gbyte、2.0 Gbyte、2.5 Gbyte、3.0 Gbyte，算法在相同數(shù)據(jù)下多次執(zhí)行取平均值，對(duì)比結(jié)果如圖4所示。圖4中，棕色線條代表默認(rèn)Hadoop集群的運(yùn)行時(shí)間，而黃色線條則代表優(yōu)化集群的運(yùn)行時(shí)間，不同數(shù)據(jù)下，優(yōu)化集群的運(yùn)行時(shí)間明顯低于默認(rèn)Hadoop集群，優(yōu)化效果顯著。

圖4 不同集群時(shí)間復(fù)雜度對(duì)比

4 總結(jié)與展望

本文提出了一種基于Hadoop的不確定異常時(shí)間序列檢測(cè)算法，采用Hadoop框架對(duì)海量時(shí)間序列進(jìn)行并行化處理，提高檢測(cè)速度，同時(shí)引入不確定時(shí)間序列壓縮表示法，并提出基于期望距離的不確定時(shí)間序列的距離度量UDTW，進(jìn)一步提升檢測(cè)速度。實(shí)驗(yàn)證明此算法既減少了時(shí)間上的計(jì)算開銷，又保證了準(zhǔn)確率。本文接下來的工作是對(duì)算法的改進(jìn)，進(jìn)一步提高算法的精確度，同時(shí)進(jìn)一步思考Hadoop集群的優(yōu)化過程。

［1］ Aggarwal C C，Yu P S.A Survey of Uncertain Data Algorithms and Applications［J］.IEEE Transactions on Knowledge and Data Engineering，2009，21（5）：609-623.

［2］ Zuo Y，Liu G，Yue X，et al.Similarity Matching over Uncertain Time Series［C］//2011 Seventh International Conference on Computational Intelligence and Security（CIS），IEEE，2011：1357-1361.

［3］ Wang Y，Wang P，Pei J，et al.A Data-Adaptive and Dynamic Segmentation Index for whole Matching on Time Series［J］.Proceedings of the VLDB Endowment，2013，6（10）：793-804.

［4］ 李斌，劉瑞琴，劉學(xué)軍.基于冗余點(diǎn)壓縮的趨勢(shì)異常序列檢測(cè)［J］.傳感技術(shù)學(xué)報(bào)，2014，27（3）：401-408.

［5］ A?falg J，Kriegel H P，Kr?ger P，et al.Probabilistic Similarity Search for Uncertain Time Series［C］//Scientific and Statistical Database Management.Springer Berlin Heidelberg，2009：435-443.

［6］ Zhao Y，Aggarwal C，Yu P.On Wavelet Decomposition of Uncertain Time Series Data Sets［C］//Proceedings of the 19th ACM International Conference on Information and Knowledge Management.ACM，2010：129-138.

［7］ 吳紅華，劉國(guó)華，王偉.不確定時(shí)間序列的相似性匹配問題［J］.計(jì)算機(jī)研究與發(fā)展，2014，51（8）：1802-1810.

［8］ 王佳林，王斌，楊曉春.面向不確定時(shí)間序列的分類方法［J］.計(jì)算機(jī)研究與發(fā)展，2011，48（suppl）：31-39.

［9］ 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.

［10］Afrati F N，F(xiàn)otakis D，Ullman J D.Enumerating Subgraph Instances Using Map-Reduce［C］//Data Engineering（ICDE），2013 IEEE 29th International Conference on.IEEE，2013：62-73.

［11］Fischer M J，Su X，Yin Y.Assigning Tasks for Efficiency in Hadoop［C］//Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures.ACM，2010：30-39.

［12］Chen Y，Alspaugh S，Borthakur D，et al.Energy Efficiency for Large-Scale Mapreduce Workloads with Significant Interactive Analysis［C］//Proceedings of the 7th ACM European Conference on Computer Systems.ACM，2012：43-56.

［13］鄭曉薇，項(xiàng)明，張大為，等.基于節(jié)點(diǎn)能力的Hadoop集群任務(wù)自適應(yīng)調(diào)度方法［J］.計(jì)算機(jī)研究與發(fā)展，2012，51（3）：618-626.

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

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

張建平（1989-），女，江蘇南通人，碩士生，主要研究方向?yàn)閿?shù)據(jù)挖掘，異常檢測(cè)，傳感器網(wǎng)絡(luò)；

Uncertain Abnormal Time Series Detection Based on Hadoop*

LI Bin*，ZHANG Jianping，LIU Xuejun
（College of Computer Science of Technology，Nanjing Tech University，Nanjing 211800，China）

In wireless sensor network，data collection of sensors and wireless network transmission all can produce uncertain time series.The arrival of big data age makes the detecting of uncertain abnormal time series face the problem of poor efficiency of time.So this paper proposes an algorithm about uncertain abnormal time series detection based on Hadoop.In this paper，uncertain time series are firstly compressed so that the uncertain data can be reduced greatly.Then the DTW algorithm of uncertain time series based on expected distance is called during MapReduce operation of Hadoop to realize the parallelization calculation of this algorithm.This measure reduces the time complexity greatly.Meanwhile，to solve the uneven load distribution exists in current Hadoop inherent task-level scheduling methods；the paper also proposes a method of Hadoop optimization.It not only reduces the total task completion time，but also makes the node resource utilization more reasonable.The results demonstrate that this algorithm not only decreases the time consumption，but also keeps a high precision.

wireless sensor network；uncertain abnormal time series；Hadoop optimization；compress；dynamic time warping；expected distance EEACC：7230

TP393

A

1004-1699（2015）07-1066-07

10.3969/j.issn.1004-1699.2015.07.021

項(xiàng)目來源：國(guó)家公益性科研專項(xiàng)項(xiàng)目（201310162，201210022）；連云港科技支撐計(jì)劃項(xiàng)目（SH1110）

2014-12-16 修改日期：2015-04-26