基于形狀特征的DTW距離相似性搜索算法

褚蓉　鈕焱

摘要：針對時間序列相似性研究中存在動態(tài)時間彎曲DTW復(fù)雜度過高與分段思想易造成特征丟失的問題，提出了一種基于形狀和升降性提取序列數(shù)據(jù)重要特征點的DTW相似性搜索算法，利用關(guān)鍵特征點快速篩選相似候選子序列集合，計算各個原始子序列的DTW距離，與改進的分段DTW距離度量方法進行實驗比較。結(jié)果表明，該方法提高了相似性搜索效率，并具備更高的相似度。

關(guān)鍵詞：時間序列；相似性；序列特征；升降標(biāo)識；動態(tài)時間彎曲

DOIDOI：10.11907/rjdk.172425

中圖分類號：TP312

文獻標(biāo)識碼：A文章編號文章編號：16727800（2018）003007803

英文摘要Abstract：In the research of time series similarity， the similarity measurement method of DTW distance is with higher complexity and the idea of segmenting will cause characteristic losing. This paper presents a dynamic match DTW distance similarity searching method based on shape feature and lifting identification， which extracts series shape key points， computing the DTW distance by the similar subsequence screened by lifting identification. Compared with the improved similarity measurement method based on segmented DTW distance，the results show that the method proposed by this paper improves the searching efficiency largely with higher similarity accuracy.

英文關(guān)鍵詞Key Words：time series； similarity； series feature； lifting identification； DTW

0引言

時間序列是按照時間順序排列的一系列觀測數(shù)據(jù)值，廣泛應(yīng)用于商業(yè)、經(jīng)濟、科學(xué)計算等多個熱門領(lǐng)域[1，2]。目前，基于時間序列的相似性搜索已有大量研究，如時間序列傅里葉變換、小波變換、各種分段計算和時間序列降維等方法[38]。但是，上述相似性搜索方法都是使用歐式距離作為度量計算公式，需要兩個相同長度的序列才能進行計算。動態(tài)時間彎曲（Dynamic Time Warping，DTW）技術(shù)的引入，開始廣泛應(yīng)用于相似性度量中，有效解決了歐式距離方法在時間軸伸縮和彎曲方面無法適用的弊端。

DTW技術(shù)最初廣泛應(yīng)用在語音識別領(lǐng)域，后來在時間軸上存在彎曲延伸的序列也可以利用該技術(shù)進行相似性距離計算。但是由于其核心計算方法為累積距離矩陣的動態(tài)規(guī)劃，導(dǎo)致計算復(fù)雜度較高，因此該方法無法很好地適用于海量時間序列的相似性度量[9]。很多研究人員致力于研究和提出多種基于DTW距離的改進方法，用于提高DTW距離計算的查詢效率。文獻[10]首先對原始數(shù)據(jù)序列進行篩選，對篩選處理后的序列再進行DTW精確計算，篩選方法主要包括設(shè)定DTW下界距離計算公式，用于排除下界距離超過閾值的序列，但存在距離公式的過濾性能與時間復(fù)雜度相互制約的問題；文獻[11]通過分段預(yù)處理各個原始數(shù)據(jù)序列，將各個分段的平均值作為時間彎曲距離，但存在序列搜索漏報和分段點特征不完整問題；文獻[12]提出了快速相似性搜索（FTW）算法，該算法通過限制彎曲路徑區(qū)域，結(jié)合動態(tài)規(guī)劃方法，增強了計算近似距離的準(zhǔn)確度；文獻[13]綜合符號化策略和原始序列分段技術(shù)，進一步提高了查詢相似序列集合的效率，而且符號策略更好地保留了關(guān)鍵的序列特征，但該方法要求相比較的兩個序列長度必須一致。

本文參考符號化思想[13，14]，提出基于序列形狀特征和上下標(biāo)識的DTW相似性搜索算法。該方法通過對提取的數(shù)據(jù)序列形狀添加預(yù)標(biāo)記，準(zhǔn)確快速確定相似性子序列集合，對篩選出的相似子序列集合進行精確的DTW距離計算，極大提高了篩選相似序列的效率。該方法已經(jīng)應(yīng)用于海洋平臺監(jiān)測數(shù)據(jù)庫的監(jiān)測數(shù)據(jù)趨勢相似性查詢中。

1形狀特征與特征標(biāo)記預(yù)處理

形狀特征和標(biāo)記算法的基本思路為：通過分析序列點前后數(shù)據(jù)形狀變化趨勢，提取時間序列的關(guān)鍵特征點，為方便數(shù)據(jù)計算，對提取出來的關(guān)鍵特征點進行數(shù)字標(biāo)記，獲得原始時間序列數(shù)據(jù)的關(guān)鍵特征序列。

1.1關(guān)鍵形狀特征序列

以時間點為基本順序特點的序列X={〈t1，x1〉，〈t2，x2〉，…，〈ti，xi〉，…，〈tn，xn〉}，序列長度為n，ti是序列的某個時間戳，xi是對應(yīng)時間戳序列點的具體數(shù)值。數(shù)據(jù)序列中一般包括兩種關(guān)鍵形狀特征點，其中，數(shù)據(jù)序列曲線有轉(zhuǎn)折和拐彎的點，通過判斷某個數(shù)據(jù)點兩側(cè)數(shù)據(jù)xi-1和xi+1大小值可得。如圖1（a）所示，A和B兩個點的序列變化趨勢是不一樣的，都是拐點。第二種是數(shù)據(jù)序列中數(shù)據(jù)變化斜度不一樣的點，這一類數(shù)據(jù)點的重要特征是兩側(cè)的數(shù)據(jù)變化趨勢差異非常明顯。為判斷某數(shù)據(jù)點是否為重要形狀特征點，本文通過計算各個數(shù)據(jù)點兩側(cè)的數(shù)據(jù)傾斜度獲得。如圖1（b）所示，該數(shù)據(jù)點兩側(cè)的斜度變化比較明顯，因此是可以反映數(shù)據(jù)形狀變化的重要特征點。

由于第二類形狀特征點不易識別，因此本文為了保證第二類關(guān)鍵特征點提取的完整性和準(zhǔn)確性，對原始數(shù)據(jù)序列進行各個數(shù)據(jù)值的差分計算，獲得數(shù)據(jù)連續(xù)的前后變化量Δ（xi-xi-1），再對獲得的前后變化量進行二次差分Δi-Δi-1，獲得二次差分變化序列T，對比變化序列數(shù)值與設(shè)定閾值δ的大小，進而識別該數(shù)據(jù)點是否可以列為二類關(guān)鍵形狀特征點。

由于閾值δ的大小對形狀特征點的提取有直接影響，同時更是判斷其是否是第二類特征點的主要依據(jù)，因此必須保證閾值提取的完備性和準(zhǔn)確性。根據(jù)差分?jǐn)?shù)值接近于0的序列對差分變化序列影響極其微弱的特性，將接近于0的微弱數(shù)據(jù)點直接忽略和排除，在差分變化序列中選取峰值最小的絕對數(shù)值為閾值δ。提取方法如式（1）。差分變化序列中如果大于閾值，則對應(yīng)的序列點xi為第二類關(guān)鍵特征點。

δ=MinMinPeak（Ti）Ti≥0

MaxPeak（Ti）Ti≤0（1）

1.2形狀特征序列預(yù)標(biāo)記

在篩選關(guān)鍵形狀特征序列時，首先通過形狀特征序列的上升和下降增減特征，對對應(yīng)的子序列進行標(biāo)記預(yù)處理，便于后續(xù)DTV數(shù)字化距離計算。使用數(shù)字（0、1）代表特征的趨勢，0表示下降，1表示上升（見圖2）。

算法詳細(xì)思路：

①首先提取原始數(shù)據(jù)序列的差分變化子序列T，選定閾值δ；

②數(shù)據(jù)序列X中的逐個數(shù)據(jù)點xi，i=1…n，執(zhí)行第③、④步；

③如果xi同時大于或小于xi-1和xi+1，說明該類數(shù)據(jù)點是第一類關(guān)鍵特征點；

④若xi不是第一類關(guān)鍵形狀特征點，則提取差分變化子序列Ti，如果Ti≥δ即說明數(shù)據(jù)點xi為第二類關(guān)鍵形狀特征點；

⑤根據(jù)特征點xi和xi+1的大小關(guān)系確定兩個數(shù)據(jù)點之間的序列增減升降性，并標(biāo)注1或0。

2基于序列特征與升降標(biāo)記的DTW距離相似性算法

基于序列特征與升降標(biāo)記序列匹配的DTW距離算法是指對原始數(shù)據(jù)R和待分析數(shù)據(jù)X分別進行關(guān)鍵特征形狀的提取和標(biāo)記，在關(guān)鍵標(biāo)記特征序列中進行形狀匹配，篩選與原始數(shù)據(jù)形狀近似的候選子序列集合。計算篩選出候選子序列集合的DTW距離相似度，最終獲得與原始數(shù)據(jù)序列相似度最高的子序列。

相似性搜索算法如下：通過對原始數(shù)據(jù)R和待分析數(shù)據(jù)X進行特征提取和預(yù)標(biāo)記算法，獲得原始特征序列R′、原始標(biāo)記序列R′l、待分析特征序列X′和待分析標(biāo)記序列X′l。同時構(gòu)建一個大小為k的堆U，ui≤u2i且ui≤u2i+1，i=1…k.

對于X′l中，逐個計算與R′l匹配的序列f，對每一個與f時間軸同步的序列段X′f與R′進行DTW距離相似度計算v，并使uk=v，自上向下更新U。

參照U中的相似度，從而得到與待分析數(shù)據(jù)序列最相似的k個子序列（C1，C2，…，Ck）。

在時間序列相似性搜索時，基于分段DTW的算法代價為cssc-sc+1=ss-s+c，c為分段的平均長度，s為分段待分析序列長度，s為分段原始序列長度，該算法的復(fù)雜度為Ο（ss）。但是基于序列形狀特征和標(biāo)記的DTW距離方法的復(fù)雜度為Ο（′′fm），′為原始數(shù)據(jù)特征序列長度，f為待相似子序列的平均長度，m為待相似序列的個數(shù)。假設(shè)時間序列數(shù)據(jù)的壓縮率相同，′=′s且′=s，則′′fm≤′′=ss。因此，本文提出的基于形狀特征和標(biāo)記的DTW距離算法比分段DTW距離算法的復(fù)雜度更低。

3實驗驗證

本文在海洋平臺長時間監(jiān)測的數(shù)據(jù)庫中，選取9月19-25日一周的慣導(dǎo)系統(tǒng)傳感器數(shù)據(jù)。由于海洋環(huán)境和平臺本身的因素，平臺自身存在一定規(guī)律的晃動和移動，而平臺上安裝的慣導(dǎo)系統(tǒng)傳感器所測量的平臺橫縱搖兩項關(guān)鍵平臺姿態(tài)數(shù)據(jù)呈現(xiàn)一定的跳動規(guī)律。該傳感器的工作頻率為30HZ，選取一周的慣導(dǎo)數(shù)據(jù)作為待分析數(shù)據(jù)序列，設(shè)定兩種算法的數(shù)據(jù)壓縮率都為90%，對以上數(shù)據(jù)，利用本文提出的搜索算法和分段DTW距離算法進行實驗對比分析。

3.1實例驗證與相似度比較

在海洋平臺數(shù)據(jù)中實際應(yīng)用了該算法，經(jīng)過算法應(yīng)用進行相似性查詢，獲得了20、25日的最佳相似時間序列（見圖3）。

針對搜索算法計算出的Top平均相似度，本文對兩種算法進行了比較，如圖4。共有7組平均相似度數(shù)據(jù)，基于分段DTW搜索算法的平均相似距離為0.20～0.34，而基于形狀特征和標(biāo)記的搜索算法的平均相似度為0.15～0.29，平均相似度整體提高約15%，從而證實本文相似性搜索算法具備更高的相似度。

3.2相似性序列篩選個數(shù)比較

為比較兩種算法在同一相似性距離閾值下篩選出的相似性子序列個數(shù)，本文首先預(yù)設(shè)閾值1.0，圖5展示了在同樣的數(shù)據(jù)樣本上對兩種對比算法進行相似性序列集合個數(shù)的對比結(jié)果?？梢缘贸霰疚牡乃阉魉惴黠@要優(yōu)于分段DTW算法。

3.3運行效率對比

通過對比本文搜索算法和分段DTW算法分別被預(yù)處理后實際搜索的執(zhí)行時間和效率，得出本文的DTW相似性搜索算法平均執(zhí)行時間更優(yōu)的結(jié)論，進一步驗證了算法復(fù)雜度結(jié)果。

4結(jié)語

針對DTW距離相似性計算算法復(fù)雜度過高和分段思想比較容易丟失特征的弊端，本文提出了基于形狀特征和標(biāo)記的DTW相似性搜索算法。該方法通過提取和標(biāo)記原始數(shù)據(jù)序列的特征序列，對快速獲取的相似子序列集合進行DTW距離計算，既可以保留原始數(shù)據(jù)特征完整，也可以提高相似性計算效率。并且基于大量真實的海洋平臺監(jiān)測數(shù)據(jù)，利用本文算法與分段的DTW距離算法進行多種性能比較實驗，實驗結(jié)果說明，本文提出的相似性搜索算法既可在計算效率上大大提高，也具備較高相似性準(zhǔn)確度，該算法和研究還為今后海洋平臺監(jiān)測數(shù)據(jù)的相似性研究提供了新的方法和思路。

參考文獻參考文獻：

[1]FU T C.A review on time series data mining[J]. Engineering Applications of Artificial Intelligence，2011，24（1）：164181.

[2]MARTIN S， HANNES O， JOSEF J， et al. Trendbased similarity search in timeseries data[C].Advances in Databases Knowledge and Data Applications， Second International Conference on IEEE，2010：97106.

[3]SERR J， ARCOS J L. An empirical evaluation of similarity measures for time series classification[J].Knowledgebased Systems，2014，67（3）：305314.