黃 辰，張 蔚，呂 敏

(1.電子信息控制重點(diǎn)實(shí)驗(yàn)室，成都 610036；2.中國(guó)西南電子技術(shù)研究所，成都 610036)

0 引 言

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

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

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

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

1 典型相似度算法介紹

1.1 LCS算法

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

設(shè)X1、X2為給定的兩組序列，m、n分別為X1和X2的長(zhǎng)度，LLCS為兩組序列最長(zhǎng)公共子序列長(zhǎng)度，則LCS相似度計(jì)算公式為

(1)

1.2 GST算法

GST算法對(duì)兩組時(shí)間序列進(jìn)行貪婪式搜索，以找出盡可能多的匹配子序列，并求出最大公共子序列長(zhǎng)度LGST。

用GST算法計(jì)算相似度公式為

(2)

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

2 改進(jìn)相似度算法原理

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

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

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

Step2 將上述時(shí)間序列進(jìn)行一階差分變換后作為一維輸入?yún)?shù)序列。經(jīng)參數(shù)變換后的一維輸入?yún)?shù)序列可表示為

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

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

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

圖1 聚類及符號(hào)化示例圖

2.2 等價(jià)字符表映射

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

基于上述符號(hào)化序列建立時(shí)間序列的等價(jià)字符表。

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

(3)

表1 s級(jí)等價(jià)字符表

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

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

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

表2 2級(jí)等價(jià)字符表

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

結(jié)合等價(jià)字符表，采用動(dòng)態(tài)滑窗的方式搜索匹配子序列?；舅悸肥沁x擇其中一個(gè)序列為基準(zhǔn)，對(duì)另一個(gè)序列進(jìn)行滑窗搜索。

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

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

(2)字符比較判斷準(zhǔn)則

兩序列字符搜索時(shí)的比較判斷準(zhǔn)則為，若兩序列待比較字符相同或?qū)儆诘葍r(jià)字符，則兩序列待比較字符位置分別向后移動(dòng)一個(gè)序列單元重復(fù)上述比較；若不相同且不屬于等價(jià)字符，則只將待比較序列字符位置往后移動(dòng)一個(gè)單元，按照上述方法繼續(xù)比較，直至搜索到序列結(jié)束位置時(shí)輸出匹配子序列。

2.4 融合GST思想的LCS改進(jìn)算法

(1)最長(zhǎng)公共子序列長(zhǎng)度計(jì)算

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

Step1 使用上述動(dòng)態(tài)滑窗及字符比較判斷準(zhǔn)則對(duì)兩符號(hào)化序列開展搜索，搜索到序列末尾提取一次匹配子序列，對(duì)已提取的匹配子序列對(duì)應(yīng)字符打上已使用標(biāo)記，長(zhǎng)度分別記為L(zhǎng)M1、LM2。

Step2 重復(fù)Step 1，對(duì)未標(biāo)記數(shù)據(jù)進(jìn)行搜索，提取匹配子序列，得到匹配子序列累計(jì)長(zhǎng)度，分別記為ALen1、ALen2，此時(shí)

(4)

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

Step3 每搜索完一次后，對(duì)所有輸出的匹配子序列累計(jì)長(zhǎng)度進(jìn)行判斷，當(dāng)滿足下式則提前停止后繼搜索：

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

(5)

其中累計(jì)長(zhǎng)度分別加1是對(duì)應(yīng)回差分前原始時(shí)間序列長(zhǎng)度。

Step4 當(dāng)滿足搜索提前結(jié)束條件或提取完所有匹配子序列時(shí)結(jié)束搜索，計(jì)算最長(zhǎng)公共子序列長(zhǎng)度。

令LIGST(X1,X2)為改進(jìn)算法的最長(zhǎng)公共子序列長(zhǎng)度，所有搜索結(jié)束則有

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

(6)

(2)相似度計(jì)算

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

(7)

根據(jù)公式(2)可知，

(8)

(9)

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

根據(jù)上述計(jì)算流程推導(dǎo)出如下定理成立：

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

證明：由LCS、GST和本文改進(jìn)算法定義的最長(zhǎng)公共子序列長(zhǎng)度分別為L(zhǎng)LCS、LGST、LIGST，由LCS和GST算法定義可知，

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

(10)

則有

(11)

即LLCS≤LGST。

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

(12)

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

LIGST≥LGST≥LLCS。

(13)

由此可推出如下結(jié)論成立：

(14)

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

3 實(shí)驗(yàn)與分析

3.1 等長(zhǎng)隨機(jī)漏脈沖對(duì)比實(shí)驗(yàn)

選取脈沖重復(fù)周期(Pulse Repetition Interval，PRI)類型為參差的樣本序列進(jìn)行等長(zhǎng)隨機(jī)漏脈沖相似度算法對(duì)比實(shí)驗(yàn)。將序列的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ù)缺失個(gè)數(shù)kmax取3，按照漏脈沖數(shù)0、1、2、3的條件隨機(jī)生成1 000組待測(cè)數(shù)據(jù)，分別利用LCS、GST、本文算法分析等長(zhǎng)漏脈沖序列之間的相似度分布情況，結(jié)果如圖4所示。

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

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

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

(15)

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

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

表3 漏脈沖為0～3條件下的加權(quán)相似度對(duì)比表

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

表4 4種PRI類型的時(shí)間序列

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

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

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

3.2 非等長(zhǎng)隨機(jī)漏脈沖對(duì)比實(shí)驗(yàn)

選取4種不同PRI類型共8對(duì)時(shí)間序列進(jìn)行非等長(zhǎng)隨機(jī)漏脈沖對(duì)比實(shí)驗(yàn)，序列TOA參數(shù)如表5所示。

脈沖時(shí)間序列經(jīng)差分變換、量化處理及符號(hào)化處理后的結(jié)果如圖6所示。

圖6 不同脈沖時(shí)間序列符號(hào)化值對(duì)比圖

表5 不同類型脈沖時(shí)間序列

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

表6 各組脈沖時(shí)間序列相似度計(jì)算結(jié)果

不同類型脈沖時(shí)間序列相似度結(jié)果如圖7所示。

圖7 不同算法相似度結(jié)果對(duì)比圖

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

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

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

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