基于EMD分解重構(gòu)的1-NN-SPMDTW時間序列分類方法

唐登林 陳毅俊

(1.貴州商學(xué)院財政金融學(xué)院 貴州 貴陽 550004；2.貴州商學(xué)院財政金融學(xué)院 貴州 貴陽 550004)

時間序列是一種普遍存在的數(shù)據(jù)類型，對時間序列數(shù)據(jù)的挖掘是目前的研究熱點之一，其中時間序列分類(Time-series Classification，TSC)問題吸引了眾多學(xué)科的研究者，出現(xiàn)在了包括數(shù)據(jù)挖掘，醫(yī)學(xué)，金融學(xué)，統(tǒng)計學(xué)，機器學(xué)習，信號處理，環(huán)境科學(xué)，計算生物學(xué)，圖像處理，化學(xué)計量學(xué)等眾多研究領(lǐng)域.

一、相關(guān)工作

以DTW為基礎(chǔ)的TSC算法存在的主要問題是DTW計算量很大、耗時較長，同時在理論上看，分類精度存在著改進空間.有關(guān)加速DTW分類速度和提升分類精度的研究可以概括為以下三個方面：一是，通過改進傳統(tǒng)的DTW技術(shù)，設(shè)計新的DTW技術(shù)并與1-NN算法或其他分類算法相結(jié)合，如文獻[1-4].二是，因為彎曲窗口(Warping Window)的大小影響著DTW的搜索空間，因此尋找最優(yōu)彎曲窗口可以提升計算的速度，同時相對緊湊的彎曲窗口能夠提升分類精度[20].例如，文獻[21]利用搜索范圍下邊界查找表和根據(jù)斜率推導(dǎo)上邊界的方法，控制搜索路徑，在一定程度上提高了運算效率.文獻[22]提出了基于DTW距離和時間距離的雙距離最佳彎曲窗口學(xué)習方法，文獻[23]將全局約束與提前終止技術(shù)相結(jié)合建立了動態(tài)彎曲窗口，文獻[24]利用啟發(fā)式搜索方法為每一類別的時間序列尋找最優(yōu)彎曲窗口邊界.三是，將傳統(tǒng)DTW與其他算法相結(jié)合，如文獻[18]利用數(shù)據(jù)塊消減技術(shù)減少訓(xùn)練數(shù)據(jù)從而提高1NN-DTW分類算法的速度，文獻[25]將序列分段方法與DTW相結(jié)合，提出了特征點分段彎曲時間距離，文獻[26]在不考慮計算時間的情況下，將測試集樣本與每個訓(xùn)練集樣本的DTW距離作為支持向量機(SVM)的輸入特征值，并與符號聚合近似法(SAX)相結(jié)合提升了TSC分類精度.文獻[27]先利用分段聚合近似方法(PAA)對數(shù)據(jù)降維，將原序列轉(zhuǎn)化為時序段平均值序列，然后計算DTW距離.

以上研究工作拓展了DTW技術(shù)在時間序列數(shù)據(jù)挖掘上的應(yīng)用，為本文的研究奠定了理論基礎(chǔ).本文提出的基于EMD分解重構(gòu)的1-NN-SPMDTW時間序列分類方法，首先運用EMD分解重構(gòu)曲線良好的去噪能力，對時間序列進行平滑處理，并利用特定的方法找到關(guān)鍵極值點；然后在一定坐標間隔閾值以內(nèi)，采用特殊點對選取規(guī)則對兩兩時間序列的極值點進行匹配，相互匹配的極值點稱為特殊點對；最后以計算的特殊點匹配DTW距離作為相似性度量，并結(jié)合最近鄰算法實現(xiàn)分類.該方法操作簡單，可調(diào)參數(shù)少，在適當?shù)膮?shù)設(shè)置下能夠?qū)崿F(xiàn)時間序列分類精度和計算速度兩方面的提升.

二、背景知識

在本節(jié)中，我們主要介紹動態(tài)時間彎曲方法和動態(tài)彎曲距離的相關(guān)知識，并對EMD分解和重構(gòu)做簡要闡述.

(一)動態(tài)時間彎曲(dynamictimewarping)

給定兩個時間序列，Q={q1,q2,…,qn}和C={c1,c2,…,cm}，其長度分別為n和m.事先定義一個n行m列的距離矩陣D，其中元素dij=d(qi,cj)=(qi-cj)2表示qi和cj之間的距離.W={w1,w2,…,wK}(max(n,m)≤K≤n+m-1)是一條彎曲路徑，元素wK=(i,j)表示序列Q中的qi與序列C中的cj相匹配.彎曲路徑定義了Q和C之間的一種映射關(guān)系，并且滿足以下兩個約束條件：

邊界條件：w1=(1,1)，wK=(n,m)，即要求W起始于距離矩陣的左下角，終止于右上角.

單調(diào)連續(xù)條件：若wk=(a,b)，wk-1=(a′,b′)，則0≤a-a′≤1,0≤b-b′≤1.這要求W在時間上只能向前發(fā)展，并且每次只能增加0或1.

滿足以上條件的彎曲路徑存在多條，我們尋找一條累計距離最小的路徑，稱之為DTW路徑，其值為DTW距離.

(1)

DTW距離可通過動態(tài)規(guī)劃方法求得：

(2)

計算DTW距離時的搜索空間需要遍歷整個距離矩陣D，因此計算需求較大，復(fù)雜度為O(n*m).

(二)經(jīng)驗?zāi)B(tài)分解(empirical mode decomposition)

經(jīng)驗?zāi)B(tài)分解(EMD)是一種時頻處理算法，能夠根據(jù)數(shù)據(jù)自身的特征通過迭代的方式自適應(yīng)地獲取基函數(shù)和分解層次，特別適用于非平穩(wěn)、非線性數(shù)據(jù)的處理[28].

EMD算法的目的是將復(fù)雜數(shù)據(jù)分解為若干個本征模函數(shù)(IMF)，每個IMF刻畫了原數(shù)據(jù)不同時間尺度上的特征.IMF必須滿足以下兩個條件：(1)函數(shù)在整個時間范圍內(nèi)，局部極值點和過零點的數(shù)目必須相等，或最多相差一個；(2)在任意時刻點，上包絡(luò)線和下包絡(luò)線的平均值必須為零.

EMD方法的分解過程如下：

(1)找到x(t)的所有極大值、極小值點并在極值點間用三次樣條函數(shù)進行插值，得到上、下包絡(luò)線emax(t)和emin(t).

(2)計算上下包絡(luò)的均值m1(t)=(emax(t)+ emin(t))/ 2，從x(t)中減去m1(t)得到第一個分量d1(t)，即：d1(t)= x(t)- m1(t).如果d1(t)滿足IMF的兩個條件，則IMF1(t)= d1(t)；否則，把d1(t)看作新的數(shù)據(jù)，其包絡(luò)平均值為m11(t)，得到d11(t)= d1(t)-m11(t)，重復(fù)這個“篩分”過程k次，直到第k次的d1k(t)是本征模函數(shù)，則：IMF1(t)= d1k(t).

(3)原數(shù)據(jù)x(t)減去第一個本征模函數(shù)IMF1(t)，則得到一個新數(shù)據(jù)序列r1= x(t)-IMF1(t)，對r1進行如上所述的“篩分”過程，這樣不斷重復(fù)便可得：r1-IMF2(t)= r2,…,rn-1-IMFn(t)= rn.當余項rn是一個常數(shù)或者單調(diào)函數(shù)，不能再分解出本征模函數(shù)時停止分解，則有：

(3)

分量IMF1(t),IMF2(t),…,IMFn(t)分別包含了數(shù)據(jù)從高到低的不同頻率成分，而rn則表示了原數(shù)據(jù)的中心趨勢.文獻[29]提出對信號EMD分解后得到的本征模函數(shù)分量重構(gòu)原數(shù)據(jù)可以達到消噪的目的.由于噪聲大多數(shù)存在于低階IMF里，所以可以根據(jù)實際需要將若干個高階IMF分量以及余項rn進行疊加，得到重構(gòu)數(shù)據(jù)，實現(xiàn)去噪處理。公式為：

(4)

三、利用EMD分解重構(gòu)的曲線尋找特殊點對

由上一小節(jié)可知，“合理的”特殊點對的引入能提升速度和精度，因此特殊點對的選擇十分重要.極值點作為時間序列中較為重要的點，蘊含著時間序列的重要信息，是研究者們較為關(guān)注的一類點.由于噪聲和異常值擾動等原因，時間序列往往存在多個極值點，因此并不是所有的極值點都有意義，需要過濾掉那些沒有意義的極值點.如文獻[30]利用重要性標志算法(EIIR)和極值點判斷算法(JEP)來尋找極值點.本文利用EMD分解重構(gòu)曲線尋找有意義的極值點，是一種較為新穎的方法.為了敘述方便，我們稱“有意義的極值點”為“特殊點”.

將EMD分解后的IMF進行重構(gòu)時，應(yīng)當確定選取哪些IMF分量和選取的數(shù)量.很多學(xué)者提出了不同的方法和選擇標準，如皮爾遜相關(guān)系數(shù).我們利用EMD方法的目的是通過EMD分解重構(gòu)在眾多的極值點中找到數(shù)量較少的有代表性的極值點，因此我們利用公式(4)，通過簡單地疊加若干個高階IMF重構(gòu)出EMD曲線.以ECG200數(shù)據(jù)為例，原序列x(t)以及重構(gòu)的x11(t)、x12(t)和x13(t)的曲線如圖4所示.為了便于觀察，我們將x12(t)和x13(t)分別向下平移了1個和2個單位.

圖1 ECG200的原序列和重構(gòu)序列

在圖1中我們發(fā)現(xiàn)，重構(gòu)的x11(t)就是原序列x(t)；與原序列x(t)相比，x12(t)較為平滑，極值點數(shù)量變少，能夠較好地還原x(t)的性質(zhì)；x13(t)極值點數(shù)量更少，但是其極值點的坐標與x(t)存在一定的偏差.因此我們考慮將x12(t)和 x13(t)各自的優(yōu)點相結(jié)合，使如下過程找到x(t)中的特殊點.

找到x13(t)曲線上所有的極值點坐標，若點A為x13(t)的一個極大值，坐標為maxA，其相鄰的前后兩個極小值坐標為minA1，minA2，則在區(qū)間[(minA1+maxA)/2,(maxA+minA2)/2]內(nèi)尋找x12(t)曲線上的極大值點和最大值點(若點A為序列中出現(xiàn)的第一個極值，則minA1=1，為序列的左端點坐標；若點A為序列中出現(xiàn)的最后一個極值，則minA2等于序列的右端點坐標).若此區(qū)間內(nèi)某一極大值同時為最大值，則該點為極大值特殊點，否則此區(qū)間內(nèi)不存在特殊點.同理，若點B為x13(t)曲線上的一個極小值，坐標為minB，其相鄰的前后兩個極大值坐標為maxB1，maxB2，則在區(qū)間[(maxB1+minB)/2,(minB+maxB2)/2]內(nèi)尋找x12(t)曲線上的極小值點和最小值點(若點B為序列中出現(xiàn)的第一個極值，則minB1為序列的左端點坐標；若點B為序列中出現(xiàn)的最后一個極值，則minB2等于序列的右端點坐標).若此區(qū)間內(nèi)某一極小值同時為最小值，則該點為極小值特殊點，否則此區(qū)間內(nèi)不存在特殊點.

利用這種尋找過程可以找到任意單個時間序列中所有的極大值特殊點和極小值特殊點，所找的特殊點數(shù)量不超過x13(t)曲線的極值點數(shù)量.因此，IMF疊加的數(shù)量以重構(gòu)曲線的極值點數(shù)量作為判斷標準.為了便于描述，我們將利用x12(t)和x13(t)尋找特殊點的過程，記為“x12(t)←x13(t)”.若x13(t)中的極值點數(shù)量較多時，我們有兩種方法可以選擇，一是舍去x13(t)中坐標間隔小于一定數(shù)值的極值點，二是利用x12(t)和x14(t)來尋找特殊點，即“x12(t)←x14(t)”，尋找過程相同，不再贅述.

單個時間序列中特殊點分為兩類，分別是極大值特殊點和極小值特殊點，當計算兩個時間序列的SPMDTW距離時，將某一時間序列的極大值特殊點與另一時間序列的極大值特殊點相互配對，形成極大值特殊點對；將該時間序列的極小值特殊點與另一時間序列的極小值特殊點相互配對，形成極小值特殊點對.為了避免病態(tài)匹配，造成不合理的結(jié)果，我們設(shè)定坐標間隔閾值(interval)，只有在間隔閾值以內(nèi)的極大值特殊點對和極小值特殊點對才能相互匹配.某些情況下，間隔閾值以內(nèi)形成了該序列的一個極大值特殊點對應(yīng)于另一序列的幾個極大值特殊點，為了造成不必要的麻煩，舍去該區(qū)間內(nèi)的所有配對.同理，適用于極小值特殊點對的匹配.我們將這種匹配規(guī)則稱為特殊點對選取規(guī)則。