基于Hadoop的不確定異常時間序列檢測*

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

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

基于Hadoop的不確定異常時間序列檢測*

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

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

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

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

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

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

1 相關(guān)工作

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

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

圖1 不確定時間序列

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

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

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

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

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

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

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

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

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

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

2.2 不確定時間序列的DTW距離計算（UDTW）

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

定理1 給定兩個相互獨立的不確定數(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 給定不確定時間序列X、Y，則最優(yōu)動態(tài)時間彎曲距離UDTW＜i,j＞如下：

2.3 基于Hadoop的不確定異常時間序列檢測算法（HUDTW）

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

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

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

定義4

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

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

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

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

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

法（HUDTW）

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

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

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

Step 1 對所有不確定時間序列進行EDC壓縮處理。

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

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

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

①Map函數(shù)

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

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

②Combine函數(shù)

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

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

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

③Reduce函數(shù)

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

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

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

Step 5 對于Reduce函數(shù)的輸出k3,v3，若v3值為1，則此時間序列為離群時間序列，否則為非離群序列。

3 算法實驗分析

本文實驗部分采用10臺雙核計算機組建的Hadoop集群對不確定時間序列進行分析，操作系統(tǒng)為centos 6。其中一臺作為namenode，一臺作為secondarynamenode，其余8臺均作為datanode。每個節(jié)點Map的數(shù)量為8個，Reduce的數(shù)量為1個。實驗首先采用默認(rèn)Hadoop集群從算法的時間復(fù)雜度和準(zhǔn)確性兩方面討論算法的有效性。進行對比的算法為面向不確定時間序列的分類方法UDTWL、概率性邊界范圍查詢方法PBRQ、以及本文提出的基于Hadoop的不確定異常時間序列檢測算法HUDTW。然后對比默認(rèn)Hadoop集群及本文提出的優(yōu)化集群在不同數(shù)據(jù)量下的時間復(fù)雜度，驗證優(yōu)化集群的時間高效性。實驗采用的數(shù)據(jù)為無線傳感器采集數(shù)據(jù)，且由于傳感器采集的數(shù)據(jù)具有顯著大數(shù)據(jù)特征，因而十分適合Hadoop平臺下開發(fā)應(yīng)用，所以實驗也進一步驗證了本算法在WSN環(huán)境中的高效應(yīng)用。

3.1 算法的有效性分析

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

3.1.1 精確度對比

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

圖2 不同算法精確度對比

3.1.2 時間復(fù)雜度對比

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

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

3.2 對比分析

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

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

4 總結(jié)與展望

本文提出了一種基于Hadoop的不確定異常時間序列檢測算法，采用Hadoop框架對海量時間序列進行并行化處理，提高檢測速度，同時引入不確定時間序列壓縮表示法，并提出基于期望距離的不確定時間序列的距離度量UDTW，進一步提升檢測速度。實驗證明此算法既減少了時間上的計算開銷，又保證了準(zhǔ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é)軍.基于冗余點壓縮的趨勢異常序列檢測［J］.傳感技術(shù)學(xué)報，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］ 吳紅華，劉國華，王偉.不確定時間序列的相似性匹配問題［J］.計算機研究與發(fā)展，2014，51（8）：1802-1810.

［8］ 王佳林，王斌，楊曉春.面向不確定時間序列的分類方法［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］鄭曉薇，項明，張大為，等.基于節(jié)點能力的Hadoop集群任務(wù)自適應(yīng)調(diào)度方法［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-），女，江蘇南通人，碩士生，主要研究方向為數(shù)據(jù)挖掘，異常檢測，傳感器網(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

項目來源：國家公益性科研專項項目（201310162，201210022）；連云港科技支撐計劃項目（SH1110）

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