基于MR框架的不確定時(shí)間序列相似性計(jì)算方法

李成為，王 嶼，鄭迪威

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

0 引 言

不確定時(shí)間序列(uncertain time series)是按照時(shí)間戳先后順序排列的記錄值的序列，在每個(gè)時(shí)間戳的序列值都是未知的或者不可預(yù)料的。不確定時(shí)間序列數(shù)據(jù)廣泛應(yīng)用于定位服務(wù)[1]、醫(yī)療數(shù)據(jù)分析[2]、時(shí)序數(shù)據(jù)庫[3]、無線傳感器網(wǎng)絡(luò)[4]等等。不確定性的產(chǎn)生是由于數(shù)據(jù)采集和環(huán)境方面的誤差[5]、使用了預(yù)測技術(shù)[6-7]，以及對于測量屬性的多次讀取數(shù)據(jù)[8]等因素。

在不確定時(shí)間序列數(shù)據(jù)處理的諸多任務(wù)和問題中，不確定時(shí)間序列相似性計(jì)算是其很重要的一個(gè)部分[9]。對于不確定時(shí)間序列相似性計(jì)算方法，主要從兩個(gè)方向進(jìn)行研究：一個(gè)是參考最初為確定性時(shí)間序列數(shù)據(jù)提出的相似性計(jì)算算法來進(jìn)行改造[10-11]；一個(gè)是根據(jù)不確定時(shí)間序列的特性，融合傳統(tǒng)的確定性時(shí)間序列相似性算法思想，提出專門適用于不確定時(shí)間序列的相似性算法[6-7,12-14]。文中主要對第二個(gè)方向進(jìn)行研究。

在傳統(tǒng)的確定性時(shí)間序列相似性計(jì)算方法中，DTW由于不要求兩個(gè)序列等長，并且兩個(gè)序列求差值的點(diǎn)可以一對多或多對一，廣泛用于計(jì)算各種情況的時(shí)間序列相似性。文獻(xiàn)[8]針對經(jīng)典DTW算法具有較高計(jì)算時(shí)間和空間損耗的問題，提出解決流檢測問題的ShortestDTW算法；文獻(xiàn)[14]通過多次在一些超平面上的投影來組織序列，提出了FastDTW算法，但該算法需要預(yù)先知道不同對象之間的距離，屬于一種粗獷的過濾方式，會帶來許多不相似的噪音；文獻(xiàn)[15]基于DTW原理提出了TD算法，對時(shí)間跨度較大且體現(xiàn)一個(gè)連續(xù)、完整過程的時(shí)間序列數(shù)和時(shí)間跨度較小、體現(xiàn)狀態(tài)點(diǎn)的時(shí)間序列數(shù)據(jù)具有一定的計(jì)算效果；文獻(xiàn)[16]提出一種將特征提取和降維進(jìn)行融合的PLA-SDTW算法，可解決高維時(shí)間復(fù)雜度的問題。

針對時(shí)間序列數(shù)據(jù)具有較大數(shù)據(jù)量的特點(diǎn)[17]，近年來已有研究工作嘗試使用MapReduce計(jì)算框架[18]計(jì)算時(shí)間序列的相似性。文中基于傳統(tǒng)DTW算法，通過融入MR計(jì)算框架，提出一種不確定時(shí)間序列的相似性計(jì)算算法。該算法在不確定時(shí)間序列計(jì)算規(guī)模大時(shí)，并行計(jì)算每個(gè)子矩陣的動態(tài)時(shí)間規(guī)整距離，在獲得與原DTW同等的匹配效果的同時(shí)，可使計(jì)算時(shí)間復(fù)雜度大為縮小。

1 基礎(chǔ)知識

1.1 時(shí)間序列相似性計(jì)算

給定一個(gè)收集好的時(shí)間序列C={S1,S2,…,SN},其中N表示時(shí)間序列的數(shù)量，查詢函數(shù)定義為：RQ(Q,C,ε)={S|S∈C|distance(Q,S)≤ε}，其中ε是使用者提供的距離閾值。

(1)DTW距離。

給定兩個(gè)時(shí)間序列Q和C,它們的長度分別為n和m，將這兩個(gè)時(shí)間序列記為：Q=,C=。它們之間的DTW距離的遞歸定義為：

其中，φ表示空時(shí)間序列；First(Q)表示時(shí)間序列Q的第一個(gè)元素；Rest(Q)表示時(shí)間序列Q除第一個(gè)元素外其他元素組成的子序列；dist2(x,y)為兩點(diǎn)x和y的距離，通常采用歐氏距離進(jìn)行計(jì)算。DTW的計(jì)算復(fù)雜度為O(nm)，計(jì)算代價(jià)較高，所以有研究人員對距離進(jìn)行了變形處理。

(2)FastDTW距離。

先將兩個(gè)時(shí)間序列粗粒度化，在遞歸到最底層后尋找最短DTW路徑，然后每次細(xì)粒度擴(kuò)展r個(gè)單位(r為半徑)，即將路徑及其周圍的點(diǎn)逐步細(xì)粒度化，并再次尋找最短DTW路徑，最終求出原始序列間的DTW距離。

FastDTW的細(xì)粒度化計(jì)算過程如圖1所示。

圖1 FastDTW的細(xì)粒度化計(jì)算過程

第一幅圖表示在遞歸最底層階段執(zhí)行DTW算法。第二幅圖表示在遞歸返回階段，將第一幅圖求得的路徑經(jīng)過的方格進(jìn)行細(xì)分，并且向左右，上下，以及左上右下的斜對角方向擴(kuò)展r個(gè)單位，重新執(zhí)行DTW算法得到的新路徑。以此類推，直到最后求得最終的路徑。

1.2 不確定時(shí)間序列及其期望距離

不確定時(shí)間序列的每個(gè)元素x都可以表示為x=r(x)+ε(x)，其中r(x)表示該元素的真實(shí)值，ε(x)表示該元素的誤差，是服從某一連續(xù)型分布函數(shù)或某離散型分布的隨機(jī)變量。不確定時(shí)間序列T定義為一系列隨機(jī)值的集合T=，其中ti是在時(shí)間戳i對實(shí)數(shù)值的隨機(jī)變量建模。

期望距離[19]可以用來計(jì)算兩個(gè)不確定時(shí)間序列數(shù)據(jù)之間的距離，該算法是用所有可能出現(xiàn)的計(jì)算結(jié)果的均值加上誤差值來代表這兩個(gè)不確定時(shí)間序列之間的距離。期望距離的具體定義如下：兩個(gè)時(shí)間序列X,Y(其中至少有一個(gè)是不確定時(shí)間序列)的概率分布為f(x)、f(y)，則它們的期望距離為：

其中，pointsdis(x,y)可以用‖x-y‖2表示，即x2+y2-2|xy|，可以推導(dǎo)出：

上述公式即表明了期望距離可以用時(shí)間序列中各個(gè)時(shí)間點(diǎn)之間的距離的期望和方差來表示，由此可以大大減少不確定時(shí)間序列之間點(diǎn)與點(diǎn)之間距離的計(jì)算量。

2 MR-FastDTW算法

FastDTW算法通過粗細(xì)粒度化的變化，在計(jì)算路徑時(shí)，首先計(jì)算遞歸最底層的路徑，并在返回階段，圍繞著上一階段得出的路徑拓展相應(yīng)范圍的計(jì)算矩陣，減少DTW暴力求解所造成的無用計(jì)算帶來的損耗。

算法1描述了FastDTW的計(jì)算過程：

算法1:FastDTW算法

Input:長度分別為|X|和|Y|的兩段時(shí)間序列X和Y；

閾值Radius//最粗分辨率的最小值

Output:時(shí)間序列X和Y之間的最小DTW距離;X與Y之間的規(guī)整路徑

1.Integer minTSsize=radius+2

2.IF(|X|≤minTSsize OR |Y|≤minTSsize)

3.RETURN DTW(X,Y)

4.ELSE

5.TimeSeries shrunkX=X.reduceByHalf()

6.TimeSeries shrunkY=Y.reduceByHalf()

7.WarpPath lowResPath=FastDTW(shrunkX, shrunkY,radius)

8.SearchWindow window=Exp[andeResWindow(lowResPath,X,Y,radius)]

9.RETURN DTW(X,Y,window)

針對FastDTW計(jì)算方法在遞歸返回階段執(zhí)行到一定程度后，文中采用MR計(jì)算框架簡化相似性計(jì)算，提出了MR-FastDTW算法，以提升運(yùn)行速度。

對于一個(gè)給定的不確定時(shí)間序列，在FastDTW算法執(zhí)到第1步和第12步時(shí)，MR-FastDTW算法采用了期望距離來執(zhí)行不確定性數(shù)據(jù)的相似性計(jì)算。在執(zhí)行MR計(jì)算框架時(shí)，對于遞歸到一定程度后即第12步，對矩陣進(jìn)行分塊處理，分塊好的矩陣進(jìn)行Map處理，產(chǎn)生相應(yīng)的值對，然后用Reduce對這些生成的鍵值對進(jìn)行處理，執(zhí)行遞歸細(xì)粒度化，并在新的搜索矩陣上面執(zhí)行上述步驟，以此重復(fù)，得到最后的結(jié)果。該算法的詳細(xì)步驟如下：

1.輸入采集到的序列A、待檢測的確定時(shí)間序列B。

2：執(zhí)行FastDTW算法，DTW計(jì)算過程使用期望距離來計(jì)算。當(dāng)粗粒度進(jìn)行到第n(n>3)次細(xì)粒度化時(shí)，把細(xì)粒度化好的矩陣放入MR計(jì)算框架中執(zhí)行計(jì)算。

3：執(zhí)行MR計(jì)算。

(1)由于DTW的計(jì)算矩陣是n*m矩陣，將序列X劃分為長度分別為[m/p]的p個(gè)子序列X0,X1,…,Xp-1，將序列Y劃分為長度分別為[n/q]的q個(gè)子序列Y0,Y1,…,Yq-1。于是就構(gòu)造了p*q個(gè)子矩陣Mf*g,f[1,p],g[1,q]。每個(gè)子矩陣的規(guī)模為[m*n]/[p*q]。

(2)每個(gè)子矩陣求的路徑作為key值，編號作為value值進(jìn)行排序。

(3)排序過后的值傳入Reduce部分，進(jìn)行路徑匯總篩選，并規(guī)約在一起得出總的動態(tài)規(guī)約路徑。

算法2描述了MR-DTW的計(jì)算過程：

算法2：MR-DTW算法

Input:時(shí)間序列X,Y,規(guī)約窗口window,p,q

Output:MR-DTW(X,Y,window)//需要加上window參數(shù)

1.INTEGERn/q,m/p

2.DTW(n2,m2)

3.MAP://MAP階段

4.E((1,2,…,n/q),m/p)→HDFS //D1*1最后一行的值

5.E(n/q,(1,2,…,m/p))→HDFS→HDFS//D1*1最后一列

6.HDFS[E((1,2,…,n/q),m/p)]→Matrix((n/q,n/q+1,…,n/q*2),m/p)

7.D(n/q*2,m/p)

8.//讀取HDFS中的D1*1最后一行，存入D2*1的第0行

9.HDFS[E(n/q,(1,2,…,m/p))]→Matrix(n/q,(m/p,m/p+1,…,m/p*2))

10.D(n/q*2,m/p*2)

11.//讀取HDFS中的D1*1最后一列 ，存入D1*2的第0列

12.E(n/q,(m/p,m/p+1,…,m/p*2))→HDFS

13.E((n/q,n/q+1,…,n/q*2),m/p)→HDFS

14.//將第D1*2的最后一列和D1*2的最后一行存到HDFS

15.//…并行計(jì)算子矩陣,中間重復(fù)步驟

16.HDFS[E((n*(q-2)/q,n*(q-2)/q+1,n(q-1)/q),m)]→Matrix((n(q-1)/q,n(q-1)/q+1,…,n),m)

17.HDFS[E(n,(m*(p-2)/p,m*(p-2)/p+1,…,m(p-1)/p))]→Matrix(n,(m*(p-1)/p,m*(p-1)/p+1,…,m))

18.D(n,m)

19.//獲取子矩陣D(f-1)*g的最后一行以及矩陣Df*(g-1)的最后一列，存入到Df*g的第0行第0列，計(jì)算Df*g

20. SORT: //SORT階段

21.Sort(D(n/q,m/p),…,D(n,m))//對p*q個(gè)矩陣的值排序

22.REDUCE://REDUCE階段

23.Combime(key) according to the sort result

24．//根據(jù)sort結(jié)果，篩選鏈接每個(gè)小矩陣的值

25.Return DTW(n,m)

把MP-DTW算法與FastDTW算法相結(jié)合，得到了基于MR計(jì)算框架的MR-FastDTW算法。算法3描述了MR-FastDTW的計(jì)算過程：

算法3：MR-FastDTW算法

Input:長度分別為|X|和|Y|的兩段不確定時(shí)間序列X和Y，F(xiàn)astDTW擴(kuò)展半徑r，起始執(zhí)行并行算法閾值num

Output:MR-FastDTW動態(tài)彎曲矩陣距離

1.Integer minTSsize=radius+2

2.IF(|X|≤minTSsize OR |Y|≤minTSsize)

3.RETURN DTW(X,Y)

4.ELSE

5.TimeSeries shrunkX=X.reduceByHalf()

6.TimeSeries shrunkY=Y.reduceByHalf()

7.WarpPath lowResPath=FastDTW(shrunkX,shrunkY,radius)

8.SearchWindow window=Exp[andeResWindow(lowResPath,X,Y,radius)]

9.IF NUM

10.RETURN DTW(X,Y,window)

11.ELSE

12.RETURN MR-DTW(X,Y,window)

3 實(shí)驗(yàn)驗(yàn)證

3.1 測試數(shù)據(jù)集的選擇

從UCR數(shù)據(jù)集中隨機(jī)抽取8組數(shù)據(jù)作為實(shí)驗(yàn)測試數(shù)據(jù)集。8組數(shù)據(jù)的具體構(gòu)成見表1。

表1 由UCR數(shù)據(jù)集構(gòu)建的不確定時(shí)間序列

3.2 算法精確度和復(fù)雜度的比較

實(shí)驗(yàn)采用4臺計(jì)算機(jī)通過路由器組建Hadoop集群，每臺計(jì)算機(jī)的內(nèi)存為4 GB，處理器為Intel i5-6500，操作系統(tǒng)為Win7。一臺作為主節(jié)點(diǎn)，三臺作為數(shù)據(jù)節(jié)點(diǎn)。使用表1中的數(shù)據(jù)集人工合成不確定時(shí)間序列，對MR-FastDTW算法與傳統(tǒng)的DTW算法和FastDTW算法進(jìn)行比較。

(1)精確度對比。

精確度是對比不同算法之間準(zhǔn)確性的標(biāo)準(zhǔn)，即不同算法檢測的結(jié)果與實(shí)際不確定時(shí)間序列的結(jié)果相比較的準(zhǔn)確程度。由于不確定數(shù)據(jù)存在誤差，所以對每組實(shí)驗(yàn)數(shù)據(jù)測十次，并取均值。再用不同的算法單次讀取該數(shù)據(jù)，并與均值進(jìn)行比較。DTW算法未對數(shù)據(jù)進(jìn)行任何限制處理，所以得到的結(jié)果精確度最高；FastDTW算法采用了粒度化的方法對數(shù)據(jù)集進(jìn)行了限制處理，精確度略有下降，但仍有較高的準(zhǔn)確度；MR-FastDTW算法的精確度與FastDTW算法的精確度基本一致，也表現(xiàn)出較高的準(zhǔn)確度。精確度比較如圖2所示。

圖2 相似性算法的精確度比較

(2)時(shí)間復(fù)雜度對比。

時(shí)間復(fù)雜度主要是不同算法執(zhí)行同組數(shù)據(jù)所消耗的時(shí)間。時(shí)間復(fù)雜度的比較如圖3所示。

圖3 相似性算法的時(shí)間復(fù)雜度比較

從圖3可以看出，當(dāng)數(shù)據(jù)量很小時(shí)，三種算法沒有太大的差異。當(dāng)參與計(jì)算的數(shù)據(jù)量逐步增加時(shí)，DTW算法其時(shí)間消耗隨數(shù)據(jù)規(guī)模的增大開始非線性增長，F(xiàn)astDTW算法和MR-FastDTW算法的時(shí)間消耗表現(xiàn)平穩(wěn)。當(dāng)數(shù)據(jù)量規(guī)模超過900時(shí)，DTW算法時(shí)間消耗會急劇增長，F(xiàn)astDTW算法由于是串行計(jì)算，時(shí)間消耗有所增大，而MR-FastDTW算法由于是并行處理，時(shí)間消耗最小。

4 結(jié)束語

提出了基于MR計(jì)算框架的MR-FastDTW算法，解決了FastDTW在遞歸返回段執(zhí)行到一定程度后計(jì)算量大的問題，在提高計(jì)算速度的同時(shí)，提高了計(jì)算準(zhǔn)確性。

需要指出的是，目前MR-FastDTW算法在執(zhí)行過程中需要使用閾值，它控制著遞歸返回段進(jìn)行到何種程度時(shí)再進(jìn)行MapReduce計(jì)算，因此閾值是MR-FastDTW算法實(shí)現(xiàn)的一個(gè)關(guān)鍵點(diǎn)。但是，閾值的取值目前還沒有一個(gè)嚴(yán)格的范圍標(biāo)準(zhǔn)，當(dāng)前只是大概取程序在遞歸返回階段執(zhí)行到三分之一時(shí)刻的值，這只是經(jīng)驗(yàn)值，缺乏嚴(yán)格的論證和理論依據(jù)。此外，該算法在執(zhí)行矩陣拆分以及合并計(jì)算值時(shí)，操作還稍顯繁瑣。所有這些都將是未來工作中需要改進(jìn)的地方。