賈瑞玉，王 瑞

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601)

基于EMD的時(shí)間序列相似性度量算法

賈瑞玉，王 瑞

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601)

時(shí)間序列本身具有高維、高噪聲的特點(diǎn)。在進(jìn)行相似性度量之前，需要對(duì)序列進(jìn)行特征表示。針對(duì)時(shí)間序列相似性度量工作中,使用分段線性表示方法對(duì)序列進(jìn)行特征表示，分段擬合效果依賴于劃分粒度，若分段數(shù)和分段點(diǎn)選取不當(dāng)，可能導(dǎo)致擬合效果不佳、難以準(zhǔn)確反映序列整體形態(tài)趨勢(shì)的問題，提出一種新的基于趨勢(shì)的相似性度量方法。該方法將經(jīng)驗(yàn)?zāi)B(tài)分解方法與分段線性表示方法相結(jié)合，首先用經(jīng)驗(yàn)?zāi)B(tài)分解方法過濾細(xì)節(jié)信息，提取序列的主要形態(tài)趨勢(shì)，得到趨勢(shì)擬合序列。在此基礎(chǔ)上，再用分段線性表示方法對(duì)趨勢(shì)擬合序列進(jìn)行分段表示，減少擬合結(jié)果對(duì)劃分粒度的依賴性。最后給出序列的分段向量距離計(jì)算方法,對(duì)趨勢(shì)分段序列計(jì)算加權(quán)向量距離，得到不同序列之間的相似性。仿真實(shí)驗(yàn)表明，該算法穩(wěn)定有效、對(duì)噪聲不敏感。

時(shí)間序列；相似性；趨勢(shì)；向量距離

0 引 言

時(shí)間序列是一組與時(shí)間相關(guān)的高維數(shù)據(jù)，在金融、商業(yè)、醫(yī)學(xué)及社會(huì)科學(xué)等領(lǐng)域中廣泛存在，如股市行情、Web訪問量、腦電圖分析和氣象變化數(shù)據(jù)等[1-2]。時(shí)間序列相似性度量是時(shí)間序列的聚類、預(yù)測(cè)及相似性搜索的基礎(chǔ)，所以時(shí)間序列的相似性研究具有重要的現(xiàn)實(shí)意義和廣泛的應(yīng)用前景[3]。由于時(shí)間序列具有數(shù)據(jù)量巨大、噪聲含量多、短期起伏、非穩(wěn)態(tài)等特點(diǎn)，對(duì)這類數(shù)據(jù)進(jìn)行挖掘分析的難度較大，因此時(shí)間序列的近似表示與相似性度量成為時(shí)間序列數(shù)據(jù)挖掘的研究熱點(diǎn)[4-5]。

基于分段思想的序列表示方法能較好地保留時(shí)間序列的全局特征，降低數(shù)據(jù)維度，并且計(jì)算效率高，因此被廣泛應(yīng)用。研究人員也提出了很多時(shí)間序列的相似性度量方法。

歐氏距離具有直觀、高效的優(yōu)點(diǎn)，但對(duì)數(shù)據(jù)的平移非常敏感，且計(jì)算精度不高[6]。吳虎勝等[7]提出了一種基于二維奇異值分解的相似匹配方法，其本質(zhì)是用二維奇異值分解對(duì)序列進(jìn)行特征描述，然后計(jì)算歐氏距離。Berndt和Chen等[8-9]將動(dòng)態(tài)彎曲距離用于時(shí)間序列的相似性度量，克服了歐氏距離無法反映數(shù)據(jù)整體發(fā)展趨勢(shì)的缺點(diǎn)，并且可以處理不同長(zhǎng)度的時(shí)間序列，但是存在復(fù)雜度較高的問題。劉彤彤等[10]提出了基于窗口斜率表示的相似性算法，以每個(gè)窗口內(nèi)最大最小幅值差與窗口寬度的比值作為序列的特征信息，進(jìn)行相似性分析。李海林等[11]提出的基于多維形態(tài)表示的時(shí)間序列相似性度量方法，利用正交多項(xiàng)式的基向量形成的特征空間對(duì)序列進(jìn)行特征表示，進(jìn)而計(jì)算相似度。但特征空間的選擇對(duì)相似性度量結(jié)果影響較大。董曉莉等[12]提出的七元模式形態(tài)距離雖然保留了時(shí)間序列的分段趨勢(shì)信息，但本質(zhì)上是基于對(duì)序列分段模式的有限劃分，因此，任意兩個(gè)序列對(duì)應(yīng)分段間的距離值都是離散的，相似匹配的精確程度依賴于模式劃分粒度。

針對(duì)現(xiàn)有方法的一些不足，文中提出一種基于經(jīng)驗(yàn)?zāi)B(tài)分解的相似性度量算法。用經(jīng)驗(yàn)?zāi)B(tài)分解方法提取時(shí)間序列的趨勢(shì)信息，并在此基礎(chǔ)上進(jìn)行時(shí)間序列的分段線性表示，然后用分段向量距離方法計(jì)算趨勢(shì)分段序列的相似性?；谮厔?shì)的分段能有效降低噪聲影響，加權(quán)向量距離從數(shù)據(jù)趨勢(shì)上區(qū)分差異，比基于點(diǎn)距離的方法更穩(wěn)定，同時(shí)修正了用戶間可能存在的度量標(biāo)準(zhǔn)不統(tǒng)一的問題。

1 相關(guān)工作

因?yàn)闀r(shí)間序列具有數(shù)據(jù)量巨大、增長(zhǎng)速度快、含有大量噪聲等特點(diǎn)，因此在分析時(shí)間序列數(shù)據(jù)之前需要進(jìn)行維度約簡(jiǎn)。由Keogh等[13]提出的PLR分段線性表示方法具有良好的數(shù)據(jù)壓縮作用。PLR方法的基本思想是選取序列中的局部極值點(diǎn)或拐點(diǎn)，若該點(diǎn)與端點(diǎn)的比值大于參數(shù)ε，則該點(diǎn)被認(rèn)為是重要點(diǎn)。將所有重要點(diǎn)用直線連接，即可得到基于重要點(diǎn)的分段時(shí)間序列。參數(shù)ε的大小決定了分段表示的劃分粒度。

2 基于EMD的相似度量方法

2.1EMD方法提取序列趨勢(shì)

經(jīng)驗(yàn)?zāi)B(tài)分解方法(Empirical Mode Decomposition，EMD)是Hilbert-Huang等提出的適用于非平穩(wěn)時(shí)間信號(hào)分析的方法。它的核心思想是將被分析的數(shù)據(jù)分解成多個(gè)具有不同特征的數(shù)據(jù)序列組合，每個(gè)數(shù)據(jù)序列具有一個(gè)本征模函數(shù)(Intrinsic Mode Function,IMF)信號(hào)。Huang等定義IMF必須滿足以下兩個(gè)條件[14]：

(1)序列數(shù)據(jù)的極值點(diǎn)個(gè)數(shù)和過零點(diǎn)個(gè)數(shù)相差不超過1；

(2)由極大值點(diǎn)構(gòu)成的上包絡(luò)線和由極小值點(diǎn)構(gòu)成的下包絡(luò)線關(guān)于時(shí)間軸對(duì)稱。

滿足以上條件的信號(hào)即為IMF信號(hào)。如果信號(hào)不滿足上述條件，則需要進(jìn)行分解操作，進(jìn)行平穩(wěn)化處理，將原始信號(hào)分解成多個(gè)滿足IMF的子信號(hào)。

若原始序列信號(hào)用X(t)表示，則分解過程主要分為以下三個(gè)步驟：

步驟1：找出原始序列中的局部極大值和局部極小值，通過三次樣條插值分別得到由極大值構(gòu)成的上包絡(luò)線U(t)和由極小值構(gòu)成的下包絡(luò)線L(t)，將序列中的所有信號(hào)點(diǎn)都包含在兩條包絡(luò)線之間，上包絡(luò)線和下包絡(luò)線的平均值為m1(t)。原始序列和上下包絡(luò)線的平均值包絡(luò)線差值為h1，如果序列h1不滿足IMF的條件或者給定閾值，執(zhí)行步驟2，否則執(zhí)行步驟3。

步驟2：將h1作為原始信號(hào)重復(fù)執(zhí)行步驟1，直至執(zhí)行結(jié)果滿足IMF條件或給定閾值。

h11(t)=h1(t)-m11(t)

(1)

設(shè)重復(fù)執(zhí)行i次后，結(jié)果滿足IMF或閾值內(nèi)的誤差。

h1i(t)=h1(i-1)(t)-m1i(t)

(2)

步驟3：如果序列h1i(t)滿足IMF條件，則將其表示為：

c1(t)=h1i(t)

(3)

r1=X(t)-c1(t)

(4)

其中，r1為殘留分量。將r1作為原始序列重復(fù)步驟1的篩選過程，直至滿足下列條件之一：

(1)rn或者cn小于給定閾值；

(2)rn成為單調(diào)函數(shù)，無法再?gòu)姆纸庵械玫絀MF。

最后得到：

(5)

其中，X(t)表示原始時(shí)間序列信號(hào)；Ci(t)表示滿足IMF的子信號(hào)；rn(t)為趨勢(shì)序列。

因?yàn)镋MD分解過程是依據(jù)原始數(shù)據(jù)信息進(jìn)行的，因此分解的信號(hào)隱含數(shù)據(jù)的真實(shí)信息，rn(t)體現(xiàn)了序列的真實(shí)趨勢(shì)。

圖1為一個(gè)經(jīng)驗(yàn)?zāi)B(tài)分解過程。其中，Signal是原始序列信號(hào)；imf1-imf5是分解過程的細(xì)節(jié)；res是分解后得到的趨勢(shì)序列。將imf信號(hào)累加可以基本擬合原始序列。

圖1 經(jīng)驗(yàn)?zāi)B(tài)分解過程

圖2為原始序列與分解后的趨勢(shì)擬合序列對(duì)比圖。

圖2 原始序列與趨勢(shì)擬合序列對(duì)比

直接對(duì)原始序列進(jìn)行分段表示的計(jì)算量較大，而且容易受噪聲影響。擬合序列能在保留基本趨勢(shì)的基礎(chǔ)上過濾噪聲，降低數(shù)據(jù)維度。對(duì)擬合序列使用PLR分段表示方法，提取到的分段序列趨勢(shì)特征更準(zhǔn)確，能夠提高相似性度量的準(zhǔn)確性。

2.2基于EMD的向量距離

(6)

分段向量距離區(qū)間為[0,2],不同分段向量之間夾角越大，向量距離越大，相似度越低；夾角越小，向量距離越小，相似度越高。當(dāng)向量距離為0時(shí)，表示兩個(gè)向量方向完全一致，即兩個(gè)分段的趨勢(shì)完全相同；向量距離為2時(shí)，表示兩個(gè)分段趨勢(shì)完全相反。通過分段相似度可以得到兩個(gè)序列的整體相似度：

(7)

為了提高計(jì)算結(jié)果的準(zhǔn)確性，在相似度公式中引入權(quán)重(ti+1-ti)/tn，表示分段i的相似性si在整體相似性中所占的權(quán)重。其中，tn表示整個(gè)序列的長(zhǎng)度，ti+1-ti表示分段i的長(zhǎng)度。(ti+1-ti)/tn越大，對(duì)整體相似度的影響越大，加權(quán)后得到的結(jié)果能夠更精確地反映相似度。

2.3基于EMD的相似性度量算法

輸入：原始時(shí)間序列S1=，S2=。

Step1：使用EMD方法對(duì)原始序列進(jìn)行經(jīng)驗(yàn)?zāi)B(tài)分解；

Step2:擬合原始序列的趨勢(shì)序列；

Step3：對(duì)趨勢(shì)擬合序列進(jìn)行分段，得到分段序列；

Step4：對(duì)不同序列的分段序列進(jìn)行等長(zhǎng)處理；

Step5：計(jì)算分段序列的向量序列；

Step6：計(jì)算不同向量序列之間的相似度。

輸出：S1和S2的相似度Sim。

使用EMD提取序列趨勢(shì)之后進(jìn)行分段表示，減少了噪聲的影響，能夠更準(zhǔn)確地反映序列的形態(tài)變化特征，使分段表示提取的趨勢(shì)特征更準(zhǔn)確。向量距離根據(jù)不同分段的發(fā)展趨勢(shì)區(qū)分差異，比基于點(diǎn)距離的方法精確，比基于形態(tài)距離的方法靈活。

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

實(shí)驗(yàn)選取Intel Core(TM) i5-3210M CPU@2.50 GHz，內(nèi)存為4 GB的電腦，操作系統(tǒng)為Microsoft Windows7，開發(fā)工具為MATLAB。采用三種股票在2005年至2010年之間的每日收盤價(jià)格時(shí)間序列進(jìn)行實(shí)驗(yàn)。第一組數(shù)據(jù)S1是標(biāo)普500指數(shù)數(shù)據(jù)(S&P500)，第二組數(shù)據(jù)S2是滬深300指數(shù)數(shù)據(jù)，第三組數(shù)據(jù)S3是上證指數(shù)數(shù)據(jù)，每條時(shí)間序列包含1 500個(gè)數(shù)據(jù)點(diǎn)。圖3是三種時(shí)間序列原始數(shù)據(jù)的走勢(shì)圖。為防止度量標(biāo)準(zhǔn)不統(tǒng)一對(duì)結(jié)果造成影響，在預(yù)處理過程中會(huì)將數(shù)據(jù)統(tǒng)一映射到[0,1]區(qū)間。

圖3 三種股票數(shù)據(jù)的走勢(shì)圖

對(duì)比方法采用歐氏距離方法和形態(tài)距離方法。歐氏距離方法和形態(tài)距離方法直接使用PLR分段方法，將預(yù)處理后的序列分別壓縮至50、100和150段，然后進(jìn)行距離計(jì)算。文中方法先利用EMD進(jìn)行數(shù)據(jù)分解，擬合原始序列，再使用PLR方法對(duì)擬合序列進(jìn)行壓縮分段表示，最后使用加權(quán)向量距離計(jì)算相似度。實(shí)驗(yàn)結(jié)果如表1～3所示。

表1 文中方法的實(shí)驗(yàn)結(jié)果

表2 形態(tài)距離法的實(shí)驗(yàn)結(jié)果

表3 歐氏距離法的實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果表明，加權(quán)向量距離和形態(tài)距離方法結(jié)果一致，無論將數(shù)據(jù)壓縮到50段、100段還是150段，結(jié)果均是S2與S3的距離最小，沒有受壓縮程度的影響，歐氏距離方法在壓縮到150段時(shí)認(rèn)為S1與S3最相似。對(duì)比圖3中的數(shù)據(jù)形態(tài)走勢(shì)圖可以發(fā)現(xiàn)，加權(quán)向量距離和形態(tài)距離結(jié)果正確，但是歐氏距離在150段時(shí)沒有正確區(qū)分序列的趨勢(shì)差異，計(jì)算結(jié)果出現(xiàn)誤差。雖然本次實(shí)驗(yàn)中形態(tài)距離和向量距離結(jié)果均正確，但是形態(tài)距離方法的劃分粒度不同，度量結(jié)果也會(huì)有差異，因此不夠穩(wěn)定。基于EMD的向量距離方法雖然多了提取序列趨勢(shì)的步驟，但是減少了分段表示的計(jì)算量，而且計(jì)算結(jié)果穩(wěn)定有效，適用于序列的相似分析和相關(guān)研究。

4 結(jié)束語(yǔ)

針對(duì)現(xiàn)有方法的一些不足，提出了基于EMD的向量距離相似性度量方法。實(shí)驗(yàn)結(jié)果表明，該方法能夠在降低噪聲影響的同時(shí)提取序列的趨勢(shì)信息，向量距離能夠有效度量時(shí)間序列的形態(tài)趨勢(shì)相似度，而且不需要?jiǎng)澐中螒B(tài)模式，避免了形態(tài)距離方法劃分標(biāo)準(zhǔn)不統(tǒng)一、度量結(jié)果不穩(wěn)定的問題，同時(shí)克服了歐氏距離對(duì)數(shù)據(jù)平移敏感的缺陷。下一步工作主要是考慮如何減少計(jì)算時(shí)間，并將該度量方法應(yīng)用到時(shí)間序列的聚類分析中。

[1] 張海濤,李志華,孫 雅,等.時(shí)間序列的層次分段及相似性度量[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(10):147-151.

[2] 朱揚(yáng)勇,戴東波,熊 赟.序列數(shù)據(jù)相似性查詢技術(shù)研究綜述[J].計(jì)算機(jī)研究與發(fā)展,2010,47(2):264-276.

[3] 涂 輝,劉 麗,張正金.改進(jìn)DTW算法的心電信號(hào)相似性度量[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(16):215-218.

[4] 劉永志,皮德常,陳傳明.基于關(guān)鍵點(diǎn)的不同長(zhǎng)度時(shí)間序列相似性度量[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(20):1-4.

[5] 尚福華,馬 楠,杜睿山.基于形態(tài)特征的測(cè)井曲線相似性搜索研究[J].計(jì)算機(jī)應(yīng)用研究,2013,30(4):1076-1078.

[6] 張 勇,王元珍,曹忠升.基于形態(tài)擬合的時(shí)間序列距離計(jì)算[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版,2012,40(8):72-76.

[7] 吳虎勝,張鳳鳴,鐘 斌.基于二維奇異值分解的多元時(shí)間序列相似匹配方法[J].電子與信息學(xué)報(bào),2014,36(4):847-854.

[8] Berndt D J,Clifford J.Using dynamic time warping to find patterns in time series[C]//Working notes of the knowledge discovery in databases workshop.[s.l.]:[s.n.],1994:359-370.

[9] Chen Y,Hu B,Keogh E,et al.DTW-D:time series semi-supervised learning from a single example[C]//ACM SIGKDD international conference on knowledge discovery and data mining.[s.l.]:ACM,2013:383-391.

[10] 劉彤彤,戴 敏,李忠義.基于窗口斜率表示法的心電波形相似性分析[J].計(jì)算機(jī)應(yīng)用,2012,32(10):2969-2972.

[11] 李海林,郭崇慧.基于多維形態(tài)特征表示的時(shí)間序列相似性度量[J].系統(tǒng)工程理論與實(shí)踐,2013,33(4):1024-1034.

[12] 董曉莉,顧成奎,王正歐.基于形態(tài)的時(shí)間序列相似性度量研究[J].電子與信息學(xué)報(bào),2007,29(5):1228-1231.

[13] Keogh E J,Pazzani M J.An enhanced representation of time series which allows fast and accurate classification,clustering and relevance feedback[C]//International conference on knowledge discovery & data mining.[s.l.]:[s.n.],1998:27-31.

[14] Huang N E,Shen Z,Long S R,et al.The empirical mode decomposition and the hilbert spectrum for nonlinear and non-stationary time series analysis[J].Proceedings of the Royal Society A Mathematical Physical & Engineering Sciences,1998,454(1971):903-995.

ASimilarityMeasureAlgorithmforTimeSeriesBasedonEMD

JIA Rui-yu，WANG Rui

(School of Computer Science and Technology,Anhui University,Hefei 230601,China)

The time series itself has characteristics of high dimension and high noise.It is necessary to represent the sequence before the similarity measure.When using piecewise linear representation method for feature representation,piecewise fitting results depend on the partition granularity.If the segmentation number and segmentation points are not proper selection,which may lead to poor fitting and could not accurately reflect the overall trend of the sequence form.Therefore,aiming at the problem,a new method of similarity measurement based on the trend is proposed which combines the empirical mode decomposition with piecewise linear representation.Firstly,filtering details by empirical mode decomposition,extracting main morphological trend of the sequence,the trend fitting sequence is gained.On this basis,use of piecewise linear representation for fitting the trend sequence,the dependence of the fitting result on the partition granularity is reduced.Finally,the calculation method of piecewise vector distance is given.The similarity between different sequences can be obtained by calculating the weighted vector distance of the trend segment sequence.Simulation results show that the proposed algorithm is stable and effective,and not sensitive to noise.

time series;similarity;trend;vector distance

2016-11-03

2017-03-15 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-08-01

國(guó)家自然科學(xué)基金資助項(xiàng)目(61202227)

賈瑞玉(1965-)，女，副教授，碩士研究生導(dǎo)師，研究方向?yàn)閿?shù)據(jù)挖掘、智能軟件；王 瑞(1991-)，女，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘、智能數(shù)據(jù)處理。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1550.026.html

TP301

A

1673-629X(2017)11-0071-04

10.3969/j.issn.1673-629X.2017.11.015