張海濤，李志華，孫 雅，張華偉

（1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無錫214122；2.江南大學(xué)物聯(lián)網(wǎng)應(yīng)用技術(shù)教育部工程研究中心，江蘇無錫214122）

0 引 言

時(shí)間序列是以時(shí)間為坐標(biāo)軸的一串觀測數(shù)據(jù)的有序集合，具有明顯的變化趨勢特征，如持續(xù)上升、波峰、波谷等。相似性度量是數(shù)據(jù)挖掘的基礎(chǔ)，針對時(shí)間序列數(shù)據(jù)的相似性度量已經(jīng)成為時(shí)間序列數(shù)據(jù)挖掘的研究熱點(diǎn)之一［1，2］。歐氏距離（euclidean distance，ED）［3］和動態(tài)時(shí)間彎曲距離（dynamic time warping，DTW）［4］是用于時(shí)間序列相似性度量的兩種經(jīng)典方法。歐式距離以計(jì)算簡單、通用性好著稱，但只能處理等長度的時(shí)間序列，并且無法識別時(shí)間序列的變化趨勢；動態(tài)時(shí)間彎曲距離較好地克服了歐式距離的不足，支持時(shí)間序列的動態(tài)彎曲，但該方法計(jì)算復(fù)雜、時(shí)間復(fù)雜度高，限制了其應(yīng)用范圍。文獻(xiàn)［5］提出了符號聚合近似（symbolic aggregate appro Ximation，SAX）方法，首先對時(shí)間序列進(jìn)行符號化，然后對符號化后的數(shù)據(jù)進(jìn)行相似性度量，具有簡單易用、不依賴于具體實(shí)驗(yàn)數(shù)據(jù)等特點(diǎn)。

本文通過研究時(shí)間序列數(shù)據(jù)的變化趨勢特征，概括出時(shí)間序列可能的變化趨勢集合，并對其進(jìn)行符號編碼，在此基礎(chǔ)上通過研究時(shí)間序列變化趨勢的度量問題，提出了時(shí)間序列變化趨勢的相似性度量（similarity measure of variation－trends，SMVT）方法。方法具有趨勢特征描述客觀、可快速有效地對時(shí)間序列數(shù)據(jù)進(jìn)行壓縮、能從變化趨勢的角度對時(shí)間序列數(shù)據(jù)進(jìn)行有效性度量等優(yōu)點(diǎn)，并且SMVT滿足距離的3種屬性，豐富了時(shí)間序列數(shù)據(jù)度量方法的家族成員。通過借助模式識別領(lǐng)域的層次聚類方法對SMVT度量方法進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明該方法具有有效性、高效性和實(shí)用性特點(diǎn)。

1 分段聚合近似方法簡介

給定時(shí)間序列S＝｛s1，s2，…sn｝其中n是其長度。將它轉(zhuǎn)變成長度為w的時(shí)間序列S’＝｛s’1，s’2，…s’w｝，其中w＜n，并且s’j（j＝1，2…w）滿足

上述過程稱為分段聚合近似（piecewise aggregate approximation，PAA）［6］，分段聚合近似是時(shí)間序列相似性度量中應(yīng)用比較廣泛的數(shù)據(jù)降維方法［7，8］，該方法在時(shí)間序列的處理上有著非常多的有點(diǎn)，如具有較高的壓縮率，可快速有效地實(shí)現(xiàn)數(shù)據(jù)降維，解決時(shí)間序列數(shù)據(jù)量龐大的問題；對噪聲數(shù)據(jù)有較好的去噪能力，分段過程在消除噪聲的同時(shí)對時(shí)間序列起到數(shù)據(jù)平滑處理的作用。

2 時(shí)間序列變化趨勢的相似性度量

SMVT方法的總體思想是:以分段聚合近似為變換函數(shù)對時(shí)間序列進(jìn)行數(shù)據(jù)降維，然后根據(jù)時(shí)間序列的變化趨勢對序列數(shù)據(jù)進(jìn)行符號化，并在此基礎(chǔ)上，通過定義趨勢距離來度量時(shí)間序列之變化趨勢的相似性。

2.1 時(shí)間序列變化趨勢的符號化

對于時(shí)間序列來說，工程應(yīng)用中更多地關(guān)注它的變化趨勢，如持續(xù)上升、持續(xù)下降、波峰等。本文從時(shí)間序列的實(shí)際變化出發(fā)，經(jīng)過統(tǒng)計(jì)分析，得出詳細(xì)的時(shí)間序列變化趨勢有9種:TF＝｛持續(xù)下降，下降后平穩(wěn)，波谷，平穩(wěn)后下降，持續(xù)平穩(wěn)，平穩(wěn)后上升，波峰，上升后平穩(wěn)，持續(xù)上升｝，并把TF符號化成｛A，B，C，D，E，F(xiàn)，G，H，I｝這樣的字符集合，其中符號與TF中的變化趨勢一一對映，即TF＝｛A，B，C，D，E，F(xiàn)，G，H，I｝。

假設(shè)有時(shí)間序列S＝｛s1，s2，…si，…sn｝其中n是其長度，則si（i＝2，3…n－1）取實(shí)際采樣值，并且對應(yīng)的可能變化趨勢vk∈TF（k＝i－1）可以通過時(shí)間序列的趨勢－符號編碼字典（見表1）來符號化。其中，Xmax為時(shí)間序列S中任意兩個下標(biāo)相鄰的數(shù)據(jù)sj，sj＋1（j＝1，2…n－1）之間差值的最大值，abs為取絕對值，ε（0＜ε＜1）是趨勢區(qū)分閾值，在實(shí)驗(yàn)中根據(jù)經(jīng)驗(yàn)來設(shè)定

在趨勢－符號編碼詞典中，對于任意兩個趨勢符號vx和vy（vx，vy∈TF）的比較，通過式（4）來實(shí)現(xiàn)

其中，asc（vx）和asc（vy）分別計(jì)算趨勢符號vx和vy所對應(yīng)字母的ASCII值。

表1 趨勢－符號編碼詞典

時(shí)間序列的重新描述是時(shí)間序列相似性度量的前提。以趨勢－符號編碼詞典為基礎(chǔ)，首先提出時(shí)間序列的趨勢符號化方法（trend symbolization method，TSM），該方法依據(jù)時(shí)間序列的變化趨勢特征對時(shí)間序列進(jìn)行符號化，將時(shí)間序列轉(zhuǎn)換為趨勢序列。對于時(shí)間序列S，其TSM符號化方法的步驟概括如下:

步驟1 根據(jù)式（1）對時(shí)間序列S進(jìn)行數(shù)據(jù)降維處理，得到長度為w的時(shí)間序列S’＝｛s’1，s’2，…s’w｝；

步驟2 根據(jù)趨勢－符號編碼詞典（見表1），對時(shí)間序列S’進(jìn)行趨勢符號化，得到長度為w－2的趨勢序列V＝｛v1，v2，…vw－2｝。

為更好地說明TSM方法，取長度為128的時(shí)間序列如圖1中S1所示，對其進(jìn)行符號化。首先，使用式（1）對時(shí)間序列S1進(jìn)行數(shù)據(jù)降維處理，在此取w為16，則可以得到長度16的時(shí)間序列，如圖1中的S2所示；然后，根據(jù)表1的編碼詞典進(jìn)行符號化，取ε的值為0.05，最后得到長度為14的趨勢序列｛G，A，A，B，F(xiàn)，I，I，I，I，H，E，D，A，A｝，如圖1中的S3所示。

圖1 時(shí)間序列的趨勢符號化方法過程

2.2 趨勢距離

受文獻(xiàn)［9］的啟發(fā)，本文給出趨勢距離（trend－distance，TD）的定義，從變化趨勢的角度對時(shí)間序列進(jìn)行相似性度量。

假定兩個趨勢序列，V1＝｛v11，v12，…，v1i…，v1M｝（i＝1，2…M）和V2＝｛v11，v22，…，v2j…，v2N｝（j＝1，2…N），它們之間的趨勢距離TD（V1，V2）定義如下。

定義:Dist（0，0）＝0

其中，μd，μi和μr（i，j）分別為插入、刪除和替換3種操作的代價(jià)，文中μd和μi的值均為1，由式（6）、（7）可知0＜μr（i，j）≤1；max（V1）和min（V1）分別為趨勢序列V1中所有數(shù)據(jù)的最大值和最小值，max（V2）和min（V2）分別為趨勢序列V2中所有數(shù)據(jù)的最大值和最小值；abs（max（V1）－min（V2））是max（V1）－min（V2）的絕對值，abs（min（V1）－max（V2））是min（V1）－max（V2）的絕對值，σmax為這兩個絕對值中的最大值。

顯然，不難看出，趨勢距離計(jì)算的是從趨勢序列V1轉(zhuǎn)換到趨勢序列V2的最小編輯操作代價(jià)，適用于長度不等的趨勢序列之間的相似性度量。

以下我們來討論趨勢距離的非負(fù)性、對稱性和三角不等式特性。

若增加一個趨勢序列V3，參考編輯距離的性質(zhì)［10－12］，根據(jù)趨勢距離的定義可知趨勢距離的非負(fù)性和對稱性顯然是成立的，即很容易滿足:

非負(fù)性:TD（V1，V2）≥0，當(dāng)且僅當(dāng)V1＝V2時(shí)，TD（V1，V2）＝0；

對稱性:TD（V1，V2）＝TD（V2，V1）。

對于趨勢距離的三角不等式特性，證明如下:

設(shè)TD（V1，V2）＝d1，TD（V2，V3）＝d2，TD（V1，V3）＝d3，則只需證明d2≤d1＋d3。

證明:從趨勢序列V2轉(zhuǎn)換到趨勢序列V3操作如下:先從V2轉(zhuǎn)換到V1，趨勢距離為TD（V2，V1），由對稱性可知，TD（V2，V1）＝TD（V1，V2）＝d1；然后從V1轉(zhuǎn)換到V3，趨勢距離為TD（V1，V3）＝d3；于是趨勢序列V2通過d1＋d3的編輯操作代價(jià)可以轉(zhuǎn)換到V3。又知趨勢序列V2和V3的趨勢距離是從V2轉(zhuǎn)換到V3的最小編輯操作代價(jià)，故有d2≤d1＋d3。即滿足三角不等式特性。

趨勢距離與編輯距離的主要區(qū)別在于:編輯距離中，插入、刪除及替換3種操作的代價(jià)均為1；趨勢距離中，插入和刪除操作的代價(jià)也為1，而對于替換操作，根據(jù)式（7）計(jì)算其代價(jià)。如，有趨勢序列V1＝｛A，B，D｝、V2＝｛A，B，E｝和V3＝｛A，B，F(xiàn)｝。根據(jù)趨勢序列中每個數(shù)據(jù)的意義，可知從V1轉(zhuǎn)換到V2的操作代價(jià)應(yīng)小于從V1轉(zhuǎn)換到V3的操作代價(jià)，對于V1、V2、V3之間的相似性度量，無論使用編輯距離還是趨勢距離，從V1轉(zhuǎn)換到V2和從V1轉(zhuǎn)換到V3均只需進(jìn)行替換操作。在編輯距離中，從V1轉(zhuǎn)換到V2與從V1轉(zhuǎn)換到V3的替換操作代價(jià)均為1；而在趨勢距離中，從V1轉(zhuǎn)換到V2的替換操作代價(jià)為abs（DE）/4＝0.25，而從V1轉(zhuǎn)換到V3的替換操作代價(jià)為abs（D－F）/5＝0.4?？梢姡厔菥嚯x可以更精確地描述趨勢序列間的差異。

2.3 SMVT方法

時(shí)間序列變化趨勢的相似性度量方法（SMVT）概括如下:

步驟1 通過時(shí)間序列的趨勢符號化方法（TSM）將時(shí)間序列符號化；

步驟2 根據(jù)趨勢距離的定義，針對符號化的時(shí)間序列，度量其相似性。

3 仿真實(shí)驗(yàn)及分析

3.1 實(shí)驗(yàn)數(shù)據(jù)簡介

為了檢驗(yàn)本文提出的時(shí)間序列相似性度量方法—SMVT方法的有效性、高效性和實(shí)用性，仿真實(shí)驗(yàn)使用兩組時(shí)間序列數(shù)據(jù)樣本，具體見表2。

表2 實(shí)驗(yàn)數(shù)據(jù)簡介

實(shí)驗(yàn)中對實(shí)驗(yàn)數(shù)據(jù)用式（9）的極差標(biāo)準(zhǔn)化方法進(jìn)行預(yù)處理

其中，min（S）和max（S）分別為時(shí)間序列S中所有數(shù)據(jù)的最小值和最大值，處理后時(shí)間序列S中所有數(shù)據(jù)的變化區(qū)間在［0，1］之間。

圖2 樣本一中類別一的數(shù)據(jù)

圖3 樣本一中類別二的數(shù)據(jù)

圖4 樣本一中類別三的數(shù)據(jù)

3.2 實(shí)驗(yàn)結(jié)果及分析

本文實(shí)驗(yàn)軟環(huán)境為Matlab 2009b，Windows 7旗艦版操作系統(tǒng)；硬環(huán)境為3.20GHz CPU、4GB內(nèi)存的PC機(jī)。

為加強(qiáng)趨勢距離的可理解性，舉如下例子說明，對樣本一數(shù)據(jù)，采用本文提出的方法進(jìn)行仿真實(shí)驗(yàn)，取w＝30，ε＝0.05，使用TSM方法對圖2中的b、c和圖4中的g、h所示數(shù)據(jù)進(jìn)行符號化，得到相應(yīng)的趨勢序列為:

進(jìn)一步使用趨勢距離計(jì)算上述4個趨勢序列之間的距離可得:

TD（Vb，Vc）＝2.5，TD（Vb，Vg）＝7.875，TD（Vb，Vh）＝7，TD（Vc，Vg）＝7.625，TD（Vc，Vh）＝4.75，TD（Vg，Vh）＝3.625。由文獻(xiàn)［13］的層次聚類方法可見，圖2（b）和圖2（c）所示的數(shù)據(jù)為一類，圖4（a）和圖4（b）所示的數(shù)據(jù)為一類。

對時(shí)間序列數(shù)據(jù)進(jìn)行聚類是指通過相似性或相異性度量，將時(shí)間序列數(shù)據(jù)進(jìn)行歸類計(jì)算。為了驗(yàn)證本文提出的時(shí)間序列相似性度量方法的有效性、高效性和實(shí)用性特點(diǎn)，我們設(shè)計(jì)4種時(shí)間序列的相似性度量實(shí)驗(yàn)方案（見表3所述）。并對4種方案得到的數(shù)據(jù)結(jié)果采用文獻(xiàn)［13］的層次聚類方法進(jìn)行分析，利用文獻(xiàn)［14］的方法計(jì)算聚類準(zhǔn)確率。用方案一、方案三和方案四的實(shí)驗(yàn)結(jié)果檢驗(yàn)SMVT方法的有效性，用方案一、方案二和方案四的實(shí)驗(yàn)結(jié)果檢驗(yàn)SMVT方法的高效性，用方案一、方案二、方案三和方案四的實(shí)驗(yàn)結(jié)果檢驗(yàn)SMVT方法的實(shí)用性。具體聚類結(jié)果如圖5和圖6所示，實(shí)驗(yàn)結(jié)果見表4和表5。

圖5 樣本一聚類結(jié)果

圖6 樣本二聚類結(jié)果

表3 時(shí)間序列的相似性度量實(shí)驗(yàn)方案

表4 樣本一實(shí)驗(yàn)結(jié)果分析

表5 樣本二實(shí)驗(yàn)結(jié)果分析

由圖5，圖6所示的方案一、方案三和方案四的聚類結(jié)果可知:相比于歐式距離、動態(tài)時(shí)間彎曲距離，方案四所述SMVT方法用樣可以適用于時(shí)間序列的數(shù)據(jù)挖掘，而且具有較好的聚類結(jié)果，這說明本文提出的SMVT方法是有效地。

通過方案一、方案二和方案四的實(shí)驗(yàn)結(jié)果（見表4和表5）比較可知:相對于方案一和方案二，方案四的聚類效果最優(yōu)，且聚類時(shí)間與方案一和方案二相近，可見方案四中所述SMVT方法在時(shí)間序列的聚類實(shí)驗(yàn)上表現(xiàn)出一定的高效性。

通過方案一、方案二、方案三和方案四實(shí)驗(yàn)結(jié)果比較（見表4和表5）不難看出:方案一的聚類速度最快，但聚類準(zhǔn)確率最低；方案二相對于方案一來說，聚類準(zhǔn)確率有所提升，但聚類時(shí)間也相應(yīng)增加；方案三在4種方案中，聚類準(zhǔn)確率最高，但聚類時(shí)間遠(yuǎn)高于其它3個方案；方案四的聚類準(zhǔn)確率高于方案一和方案二，略低于方案三，但聚類時(shí)間略高于方案一和方案二，遠(yuǎn)小于方案三。從時(shí)間和準(zhǔn)確率兩個方面綜合考慮，方案四在保持較高聚類準(zhǔn)確率的同時(shí)，也較少地占用了聚類時(shí)間?？梢姡琒MVT方法在時(shí)間序列聚類實(shí)驗(yàn)上綜合性能比較好，相對其它的時(shí)間序列相似性度量方法具有較強(qiáng)的實(shí)用性。

4 結(jié)束語

時(shí)間序列的相似性度量是時(shí)間序列挖掘的關(guān)鍵環(huán)節(jié)。本文提出的SMVT方法，依據(jù)變化趨勢對時(shí)間序列進(jìn)行符號化，將時(shí)間序列轉(zhuǎn)變?yōu)橄鄳?yīng)的趨勢序列，并以此為基礎(chǔ)，通過定義趨勢距離來度量時(shí)間序列間的相似性。實(shí)驗(yàn)結(jié)果表明，該方法可以很好地從變化趨勢的角度對時(shí)間序列進(jìn)行相似性度量，效果明顯，具有有效性、高效性和實(shí)用性特點(diǎn)，可應(yīng)用于時(shí)間序列的數(shù)據(jù)挖掘計(jì)算。

［1］Lhermitte S，Verbesselt J，Verstraeten W W.A comparison of time series similarity measures for classi fi cation and change detection of ecosystem dynamics［J］.Remote Sesing of Environment，2011，115:3129－3152.

［2］Tak－chung Fu.A review on time series data mining［J］.Engineering Application of Artificial Intelligence，2012，24（1）:164－181.

［3］XIE Fuding，LI Ying，SUN Yan，et al.Improved symbolization time series method［J］.Computer Engineering and Design，2012，33（10）:3950－3953（in Chinese）.［謝福鼎，李迎，孫巖，等.改進(jìn)的符號化時(shí)間序列處理方法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2012，33（10）:3950－3953.］

［4］Somaya Adwan，Hamzah Arof.On improving dynamic time warping for pattern matching［J］.Measurement，2012，45（6）:1609－1620.

［5］Antonio Canelas，Rui Neves，Nuno Horta.A SAX－GA approach to evolve investment strategies on financial markets based on pattern discovery techniques［J］.Expert Systems with Application，2013，40（5）:1579－1590.

［6］Nguyen Quoc Viet Hung，Duong Tuan Anh.An imporvement of PAA for dimensionality reduciton in large time databases［G］.LNCS 5351:PRICAI 2008:Trends in Artificial Intelligence.Berlin:Springer Berlin heidelberg，2008:698－707.

［7］LI Guiling，WANG Yuanzhen，YANG Linquan，et al.Research on similarity measure for time series based on SAX［J］.Application Research of Computers，2012，29（3）:893－896（in Chinese）.［李桂玲，王元珍，楊林權(quán)，等.基于SAX的時(shí)間序列相似性度量方法［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（3）:893－896.］

［8］LI Hailin，GUO Chonghui.Piecewise cloud approximation for time series mining［J］.Knowledge－Based Systems，2011，24（5）:492－500（in Chinese）.［李海林，郭崇慧.基于形態(tài)特征的時(shí)間序列符號聚合近似方法［J］.模式識別與人工智能，2011，24（5）:665－672.］

［9］Alexandr Andoni，Robert Krauthgamer.The computational hardness of estimating edit distance［J］.Society for Industrail and Application Mathemetics，2010，39（6）:2398－2429.

［10］LIU Kun，YANG Jie.Trajectory distance metric based on edit distance［J］.Journal of Shanghai Jiaotong University，2009，43（11）:1725－1729（in Chinese）.［劉坤，楊杰.基于編輯距離的軌跡相似性度量［J］.上海交通大學(xué)學(xué)報(bào)，2009，43（11）:1725－1729.］

［11］Alexandr Andoni，Robert Krauthgamer.The smoothed complexity of edit distance［J］.ACM Transactions on Algorithms，2012，8（4）.

［12］DAI Dongbo.Sequence clustering algorithms based on global and local similarity［J］.Journal of Software，2010，21（4）:702－717（in Chinese）.［戴東波.基于整體和局部相似性的序列聚類算法［J］.軟件學(xué)報(bào)，2010，21（4）:702－717.］

［13］Jiawei Han，Micheline Kamberi.Data mining:Concepts and techniques［M］.3rd ed.USA:Morgan Kaufmann，2011:457－469.

［14］LI Zhigang，NIU Qiang.An improved symbolization time series cluster method［J］.Microelectronics ＆Computer，2012，29（11）（in Chinese）.［李志剛，牛強(qiáng).一種改進(jìn)的符號化時(shí)間序列聚類方法［J］.微電子學(xué)與計(jì)算機(jī)，2012，29（11）.］