賈瑞玉，王 瑞

(安徽大學 計算機科學與技術學院，安徽 合肥 230601)

基于EMD的時間序列相似性度量算法

賈瑞玉，王 瑞

(安徽大學 計算機科學與技術學院，安徽 合肥 230601)

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

時間序列；相似性；趨勢；向量距離

0 引 言

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

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

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

針對現(xiàn)有方法的一些不足，文中提出一種基于經(jīng)驗模態(tài)分解的相似性度量算法。用經(jīng)驗模態(tài)分解方法提取時間序列的趨勢信息，并在此基礎上進行時間序列的分段線性表示，然后用分段向量距離方法計算趨勢分段序列的相似性?；谮厔莸姆侄文苡行Ы档驮肼曈绊?，加權向量距離從數(shù)據(jù)趨勢上區(qū)分差異，比基于點距離的方法更穩(wěn)定，同時修正了用戶間可能存在的度量標準不統(tǒng)一的問題。

1 相關工作

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

2 基于EMD的相似度量方法

2.1EMD方法提取序列趨勢

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

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

(2)由極大值點構成的上包絡線和由極小值點構成的下包絡線關于時間軸對稱。

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

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

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

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

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

(1)

設重復執(zhí)行i次后，結果滿足IMF或閾值內的誤差。

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作為原始序列重復步驟1的篩選過程，直至滿足下列條件之一：

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

(2)rn成為單調函數(shù)，無法再從分解中得到IMF。

最后得到：

(5)

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

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

圖1為一個經(jīng)驗模態(tài)分解過程。其中，Signal是原始序列信號；imf1-imf5是分解過程的細節(jié)；res是分解后得到的趨勢序列。將imf信號累加可以基本擬合原始序列。

圖1 經(jīng)驗模態(tài)分解過程

圖2為原始序列與分解后的趨勢擬合序列對比圖。

圖2 原始序列與趨勢擬合序列對比

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

2.2基于EMD的向量距離

(6)

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

(7)

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

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

輸入：原始時間序列S1=，S2=。

Step1：使用EMD方法對原始序列進行經(jīng)驗模態(tài)分解；

Step2:擬合原始序列的趨勢序列；

Step3：對趨勢擬合序列進行分段，得到分段序列；

Step4：對不同序列的分段序列進行等長處理；

Step5：計算分段序列的向量序列；

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

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

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

3 實 驗

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

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

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

表1 文中方法的實驗結果

表2 形態(tài)距離法的實驗結果

表3 歐氏距離法的實驗結果

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

4 結束語

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

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

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

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

[4] 劉永志,皮德常,陳傳明.基于關鍵點的不同長度時間序列相似性度量[J].計算機工程與應用,2014,50(20):1-4.

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

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

[7] 吳虎勝,張鳳鳴,鐘 斌.基于二維奇異值分解的多元時間序列相似匹配方法[J].電子與信息學報,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].計算機應用,2012,32(10):2969-2972.

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

[12] 董曉莉,顧成奎,王正歐.基于形態(tài)的時間序列相似性度量研究[J].電子與信息學報,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)絡出版時間

時間：2017-08-01

國家自然科學基金資助項目(61202227)

賈瑞玉(1965-)，女，副教授，碩士研究生導師，研究方向為數(shù)據(jù)挖掘、智能軟件；王 瑞(1991-)，女，碩士研究生，研究方向為數(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