一種基于等價字符的不完整時間序列相似度算法*

黃 辰，張 蔚，呂 敏

(1.電子信息控制重點實驗室，成都 610036；2.中國西南電子技術研究所，成都 610036)

0 引 言

時間序列的相似度算法是從時間序列中發(fā)現(xiàn)數(shù)據對象間相關程度和緊密程度的重要手段，是數(shù)據挖掘領域中重要的研究課題[1]。時間序列的相似度算法，即綜合評定兩個時間序列間關聯(lián)程度的一種方法。兩個時間序列特征越接近，它們的相似度越高。

相似度分析廣泛運用于預處理[2]、信號處理[3]、聚類[4]、分類[5]、模式識別[6]、關聯(lián)分析[7-8]、軌跡判斷[9]、文本比較[10]等領域。在計算兩組時間序列關系時，相似度度量所采用的數(shù)據特征和所選取的方法將直接影響數(shù)據計算效果。因此，根據數(shù)據特點選取相適應的相似度度量方法，對于提升相似度計算的準確性而言具有重要意義。目前，典型的相似度算法有基于最長公共子序列(Longest Common Subsequence，LCS)、基于貪婪字符串匹配(Greedy String Tiling，GST)[11-12]算法等。LCS和GST算法不要求待比較序列長度相等，且能處理具有少量強噪聲的序列[9]。

文獻[8]針對不等長序列的關聯(lián)問題，提出了基于滑動窗口的最優(yōu)匹配增權法，并驗證了算法對不等長序列數(shù)據關聯(lián)的有效性。文獻[13]提出了基于漲落模式(Frequent Pattern，F(xiàn)P)的時間序列相似性度量研究方法，能有效支持識別多種相似性形變，以FP保存原序列的趨勢變化信息，利用LCS算法計算漲落模式的相似度。

現(xiàn)有的相似度算法均在一定程度上解決了數(shù)據的相似度計算問題，但對于不完整時間序列而言并沒有采取針對性的解決思路，因此并未達到理想效果。本文在充分研究現(xiàn)有算法的基礎上，針對不完整時間序列的相似度計算問題，利用差分變換、量化處理、符號化處理、等價字符變換以及LCS、GST算法思想，提出了適用于不完整時間序列相似度計算的改進算法，并與典型的LCS、GST相似度算法進行了對比分析。

1 典型相似度算法介紹

1.1 LCS算法

LCS算法是將兩組時間序列分別刪去0個或多個字符，但不改變剩余序列順序后得到最長的相同子序列。

設X1、X2為給定的兩組序列，m、n分別為X1和X2的長度，LLCS為兩組序列最長公共子序列長度，則LCS相似度計算公式為

(1)

1.2 GST算法

GST算法對兩組時間序列進行貪婪式搜索，以找出盡可能多的匹配子序列，并求出最大公共子序列長度LGST。

用GST算法計算相似度公式為

(2)

式中：M、N分別代表匹配子序列在X1、X2中的起始及結束位置，Len代表匹配長度，titles代表所有匹配長度全集。

2 改進相似度算法原理

準確獲取不完整時間序列間的最長公共子序列長度，是完成相似度計算的重要工作。對時間序列進行參數(shù)變換和符號化處理，計算并建立等價字符表，在此基礎上滑窗搜索不完整序列間的相似部分，能更準確地計算出不完整序列間的最長公共子序列長度，并基于改進后的相似度公式計算出相似度值。

2.1 參數(shù)變換和符號化處理

通過參數(shù)變換和符號化處理將原始時間序列的比較轉換為字符串之間的比較，以降低輸入數(shù)據的信息量，便于后續(xù)理解和計算，其步驟如下：

Step2 將上述時間序列進行一階差分變換后作為一維輸入參數(shù)序列。經參數(shù)變換后的一維輸入參數(shù)序列可表示為

Step3 采用層次凝聚聚類(Hierarchical Agglomerative Clustering，HAC)方法對上述輸入參數(shù)序列進行非均勻矢量量化，量化完成后對所有量化值依次打上符號標簽(為計算方便取數(shù)字形式)即為符號化序列。

設有如下兩個時間序列：完整時間序列X1=(0,132,265,397,626,758,891,1 023)和不完整時間序列X2=(0,132,397,626,758,891,1 023)。

時間序列經一階差分變換后分別為DX1=(132,133,132,229,132,133,132)、DX2=(132,265,229,132,133,132)。令距離閾值ε=1，按上述方法處理后得到符號化序列LX1=(1,1,1,2,1,1,1)；LX2=(1,3,2,1,1,1)。其中，符號值c1=1,c2=2,c3=3。參數(shù)變換后的聚類及符號化如圖1所示。

圖1 聚類及符號化示例圖

2.2 等價字符表映射

在時間序列的采樣過程中，由于各種原因可能會有數(shù)據缺失的情況發(fā)生，為此本文提出了一種等價字符表映射技術以解決最長公共子序列提取不準確的問題。

基于上述符號化序列建立時間序列的等價字符表。

定義1 設s為差值級數(shù)，k為時間序列連續(xù)缺失數(shù)據的實際個數(shù)，kmax為最大連續(xù)缺失數(shù)據的個數(shù)，m、n分別是兩組時間序列的長度，在符號化序列的時間特征參數(shù)滿足如下條件時建立等價字符表：

(3)

表1 s級等價字符表

等價字符表創(chuàng)建流程如圖2所示。

圖2 等價字符表創(chuàng)建流程圖

令kmax=3，由圖2流程及公式(3)可得到，2.1節(jié)例子創(chuàng)建的2級等價字符表如表2所示。

表2 2級等價字符表

2.3 動態(tài)滑窗搜索

結合等價字符表，采用動態(tài)滑窗的方式搜索匹配子序列。基本思路是選擇其中一個序列為基準，對另一個序列進行滑窗搜索。

動態(tài)滑窗是指搜索窗口的大小和位置在匹配計算的過程中是隨時間變化的。本文采用的動態(tài)滑窗在每一次比較時，窗口起始位置由向后移動一個序列單元，結束位置為序列末尾。動態(tài)滑動搜索窗口如圖3所示。

圖3 動態(tài)滑動搜索窗口

(2)字符比較判斷準則

兩序列字符搜索時的比較判斷準則為，若兩序列待比較字符相同或屬于等價字符，則兩序列待比較字符位置分別向后移動一個序列單元重復上述比較；若不相同且不屬于等價字符，則只將待比較序列字符位置往后移動一個單元，按照上述方法繼續(xù)比較，直至搜索到序列結束位置時輸出匹配子序列。

2.4 融合GST思想的LCS改進算法

(1)最長公共子序列長度計算

在上述符號化處理、等價字符映射的基礎上，綜合考慮LCS、GST算法思想，進一步提出一種融合GST思想的LCS改進算法，滑窗搜索并提取所有非重復的匹配子序列，通過判斷多次搜索得到的匹配子序列累計長度計算最長公共子序列長度。具體步驟如下：

Step1 使用上述動態(tài)滑窗及字符比較判斷準則對兩符號化序列開展搜索，搜索到序列末尾提取一次匹配子序列，對已提取的匹配子序列對應字符打上已使用標記，長度分別記為LM1、LM2。

Step2 重復Step 1，對未標記數(shù)據進行搜索，提取匹配子序列，得到匹配子序列累計長度，分別記為ALen1、ALen2，此時

(4)

式中：t為搜索次數(shù)計數(shù)，T為當前最大搜索次數(shù)。

Step3 每搜索完一次后，對所有輸出的匹配子序列累計長度進行判斷，當滿足下式則提前停止后繼搜索：

min(ALen1+1,ALen2+1)=min(m,n)。

(5)

其中累計長度分別加1是對應回差分前原始時間序列長度。

Step4 當滿足搜索提前結束條件或提取完所有匹配子序列時結束搜索，計算最長公共子序列長度。

令LIGST(X1,X2)為改進算法的最長公共子序列長度，所有搜索結束則有

LIGST(X1,X2)=min(ALen1,ALen2)+1。

(6)

(2)相似度計算

由公式(1)、(4)、(6)可得，相似度計算公式為

(7)

根據公式(2)可知，

(8)

(9)

采用上述方式，2.1節(jié)例子的符號化數(shù)據搜索一次得到匹配子序列為(1,1,1,2,1,1,1)、(1,3,2,1,1,1)，匹配子序列累計長度分別為7、6。對其進行判斷，滿足公式(5)，因此停止后繼搜索，此時根據公式(6)、(7)求得最長公共子序列長度為7，兩序列相似度為0.933。

根據上述計算流程推導出如下定理成立：

定理1 令Sim1、Sim2和Sim3分別為時間序列X1和X2按LCS、GST和本文改進算法定義的相似度，則有Sim3≥Sim2≥Sim1。

證明：由LCS、GST和本文改進算法定義的最長公共子序列長度分別為LLCS、LGST、LIGST，由LCS和GST算法定義可知，

LLCS=match(M,N,LenLCS)∈titles，

(10)

則有

(11)

即LLCS≤LGST。

由本文改進算法定義，如果兩序列滿足等價字符條件，則等價字符對應的序列長度加入到最長公共子序列長度的計算中，因此有min(LM1,LM2)≥LenLCS，進一步得到

(12)

結合公式(2)、(7)～(9)可得

LIGST≥LGST≥LLCS。

(13)

由此可推出如下結論成立：

(14)

基于以上不等式，由相似度定義可推出Sim3≥Sim2≥Sim1。

3 實驗與分析

3.1 等長隨機漏脈沖對比實驗

選取脈沖重復周期(Pulse Repetition Interval，PRI)類型為參差的樣本序列進行等長隨機漏脈沖相似度算法對比實驗。將序列的TOA歸一化到0起始，序列TOA參數(shù)為X=(0,50.3,117.4,175.9,245.9,296.2,363.3,421.8,491.8,542.1,609.2,667.7,737.7,788,855.1,913.6)，最大連續(xù)缺失個數(shù)kmax取3，按照漏脈沖數(shù)0、1、2、3的條件隨機生成1 000組待測數(shù)據，分別利用LCS、GST、本文算法分析等長漏脈沖序列之間的相似度分布情況，結果如圖4所示。

(a)漏脈沖數(shù)為0

由圖4(a)可見，當序列為完整序列時，三種算法相似度計算值相等，而當序列為不完整序列時，隨著漏脈沖數(shù)量的增加，不完整程度隨之升高，相似度計算值總體會有所下降。通過分析圖4(b)～(d)相似度分布情況可知，本文算法的相似度更高。

設圖4中相似度精度取0.01，i=1,2,…,100，simi為第i個相似度值，numi為simi對應的統(tǒng)計次數(shù)，利用加權平均法可計算出相似度在多組統(tǒng)計中的算術平均數(shù)。加權平均相似度計算公式為

(15)

式中：simi=0.01×i；sum為總的測試次數(shù)，在本實驗中sum為1 000。

將圖4中的相似度分布進行加權平均計算，結果如表3所示，可見，本文算法相比典型算法有10%以上的性能提升。

表3 漏脈沖為0～3條件下的加權相似度對比表

進一步地，選取4種典型PRI類型(A、B、C、D分別代表組變、參差、復合和滑變)的脈沖時間序列進行等長隨機漏脈沖相似度算法對比實驗，歸一化后的序列TOA參數(shù)如表4所示。

表4 4種PRI類型的時間序列

根據以上的測試方法，分別比較4種類型數(shù)據加權相似度隨序列漏脈沖數(shù)量的變化情況，如圖5所示。

圖5 4種數(shù)據類型的相似度對比圖

可見，對于不同類型的測試數(shù)據，取相同長度的完整脈沖序列，隨著漏脈沖數(shù)量從1增加至3，LCS、 GST方法計算出的相似度下降相對明顯，本文算法的加權平均相似度高于其余兩類算法。

3.2 非等長隨機漏脈沖對比實驗

選取4種不同PRI類型共8對時間序列進行非等長隨機漏脈沖對比實驗，序列TOA參數(shù)如表5所示。

脈沖時間序列經差分變換、量化處理及符號化處理后的結果如圖6所示。

圖6 不同脈沖時間序列符號化值對比圖

表5 不同類型脈沖時間序列

利用本文方法計算上述序列對的相似度，與LCS、GST算法進行對比，結果如表6所示。

表6 各組脈沖時間序列相似度計算結果

不同類型脈沖時間序列相似度結果如圖7所示。

圖7 不同算法相似度結果對比圖

以上總的相似度對比結果表明，在時間序列存在數(shù)據缺失情況時，利用本文方法計算得到的相似度高于LCS和GST算法，針對存在數(shù)據缺失的時間序列具有更好的效果。

4 結束語

本文研究了一種基于等價字符的不完整時間序列相似度算法，通過挖掘時間序列之間的內在規(guī)律提高一定數(shù)據缺失情況下的時間序列相似度計算準確性，在等長漏脈沖條件下，當脈沖缺失1～3個時，相比LCS、GST算法，本文算法的相似度計算結果有10%以上的提高。而非等長脈沖缺失對比分析表明，本文算法能有效提高對比序列的相似度結果。

雖然基于等價字符的方法能在序列不完整情況下能得到更接近于完整序列情況下的相似度計算結果，但漏脈沖數(shù)量會直接影響計算結果的可靠程度。因此，下一步工作可根據序列的不完整程度，研究相似度結果的置信度評估方法。