劉苗苗，周從華，張 婷

（1.江蘇大學(xué) 計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013；2.無錫市婦幼保健院，江蘇 無錫 214002）

0 概述

時間序列是當(dāng)前非常普遍且與時間相關(guān)的高維數(shù)據(jù)，是目前生活中比較常見的一種數(shù)據(jù)類型［1］，同時也是數(shù)據(jù)挖掘領(lǐng)域中主要的研究對象，它廣泛存在于金融股票、航天氣象、醫(yī)療診斷分析等領(lǐng)域中［2］。時間序列的相似性度量用來衡量不同時間序列之間的相互關(guān)系，從中挖掘有用信息并將其結(jié)果用于分類、聚類、模式發(fā)現(xiàn)等方面，使其更好地應(yīng)用于社會生產(chǎn)實(shí)踐。例如在醫(yī)療服務(wù)行業(yè)中，通過對醫(yī)療檢測數(shù)據(jù)所形成的時間序列（如心電圖數(shù)據(jù)）進(jìn)行分類研究，可以發(fā)現(xiàn)具有相同或相似的患者在身體機(jī)能方面的“共性”變化趨勢，在此基礎(chǔ)上研究并制定更加合理的治療方案，實(shí)現(xiàn)智慧醫(yī)療。相似性度量是數(shù)據(jù)挖掘相關(guān)領(lǐng)域研究的基礎(chǔ)和前提，其度量效果將直接影響后續(xù)時間序列聚類、分類等相關(guān)研究的精度。因此，針對時間序列數(shù)據(jù)的相似性度量已經(jīng)成為時間序列數(shù)據(jù)挖掘領(lǐng)域相關(guān)研究的熱點(diǎn)之一［3］。

時間序列是在一定的時間內(nèi)記錄一個或多個屬性伴隨時間變化的數(shù)據(jù)，對具有單個屬性采樣得到的序列稱為一元時間序列（UTS），對具有多個屬性采樣得到的序列稱為多元時間序列（MTS）［4］。目前對一元時間序列的研究相對較多，已逐漸形成了較為成熟的理論和方法，而多元時間序列的理論和方法尚不完善［5］。多元時間序列由多個不同的變量維度組成，其結(jié)構(gòu)比單一變量復(fù)雜得多，如果只是看成多個變量維度的簡單疊加，則容易忽略變量的內(nèi)在相關(guān)性及變量序列的形態(tài)特性，導(dǎo)致相似性度量不準(zhǔn)確，尤其是對具有強(qiáng)內(nèi)在相關(guān)性的多元時間序列數(shù)據(jù)。而在現(xiàn)實(shí)生活中，多元時間序列更為常見，例如：股票的漲跌變化趨勢受多種因素的影響［6］；醫(yī)學(xué)中患者某個疾病的確診一般也是通過多個生理指標(biāo)共同體現(xiàn)出來；某地的天氣狀況一般要考慮溫度、濕度、氣壓等因素。因此，對多元時間序列的研究更具有重要的理論和現(xiàn)實(shí)意義。多元時間序列具有的高維、復(fù)雜、動態(tài)、高噪聲等特性，如果直接對原始數(shù)據(jù)進(jìn)行相關(guān)研究，將產(chǎn)生挖掘結(jié)果不準(zhǔn)確、時間效率低下以及研究結(jié)論可信度較低等問題［7］。因此，在進(jìn)行相似性度量之前，需要對多元時間序列進(jìn)行特征表示，提取多元時間序列的主要特征，利用轉(zhuǎn)換后的特征代替原始數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘任務(wù)。

相似性度量是時間序列聚類和分類研究中必不可少的關(guān)鍵步驟，其作用是對時間序列的變化、形狀和距離進(jìn)行相似性度量，針對不同領(lǐng)域數(shù)據(jù)的序列特征將有其相適應(yīng)的相似性度量函數(shù)［8］。目前針對MTS 常見的的相似性度量方法主要有歐式距離（Euclidean Distance，ED）［9］和動態(tài)時間彎曲距離（Dynamic Time Warping，DTW）［10］距離。歐式距離具有計(jì)算簡單、時間復(fù)雜度低的優(yōu)點(diǎn)，但只能度量長度相同的時間序列，而且對時間序列形態(tài)變化很敏感，不能辨別序列之間的形狀相似性，無法反映趨勢動態(tài)變化幅度的相似性。動態(tài)時間彎曲距離是基于動態(tài)規(guī)劃的思想，避免了歐氏距離存在的不足，不僅能夠避免歐氏距離一對一匹配的問題，而且通過扭曲序列實(shí)現(xiàn)了時間序列之間“一對多”的映射，因此，可以對任意等長或不等長時間序列進(jìn)行相似性度量，并且DTW 對時間序列偏移、幅度變化等情況也有很強(qiáng)的魯棒性。然而，DTW 不僅時間復(fù)雜度高，在相似性匹配過程中也容易出現(xiàn)因一味地追求最小距離而對時間序列過渡的拉伸或壓縮的現(xiàn)象，從而影響度量精度。

目前關(guān)于相似性度量方法的改進(jìn)大多是基于動態(tài)時間彎曲展開的，一般包括對計(jì)算效率的改進(jìn)、算法度量精度的提升以及與其他方法融合的改進(jìn)等。文獻(xiàn)［11］提出趨勢距離（TD）方法，首先通過對全部變量進(jìn)行提取特征，然后進(jìn)行分段和特征擬合，提取分段區(qū)間的斜率、長度作為特征，最后使用DTW 距離度量特征矩陣之間的距離，在多個數(shù)據(jù)集上都取得了較好的度量結(jié)果，但當(dāng)數(shù)據(jù)規(guī)模較小、序列趨勢變化不明顯時，效果不佳。之后，文獻(xiàn)［12］又提出分段線性擬合的動態(tài)時間彎曲相似性度量（PLRDTW），使用DTW 對多維分段擬合后的時間序列進(jìn)行度量，在數(shù)據(jù)規(guī)模大、連續(xù)性變量的序列上具有較好的效果，但實(shí)驗(yàn)結(jié)果受參數(shù)的選擇影響較大。此外，由于只選取了分段的均值作為原始序列的特征表示，并不能體現(xiàn)出序列的趨勢特征，因此應(yīng)用范圍有限。DTW 在計(jì)算多元時間序列最佳彎曲路徑時，雖能較好地反映時間序列形態(tài)變化問題，但在尋求最小彎曲路徑的過程中容易出現(xiàn)不合理的匹配使得序列過渡壓縮和拉伸，從而影響度量精度。

針對DTW 計(jì)算復(fù)雜度高及在匹配的過程中出現(xiàn)過度拉伸和壓縮的問題，本文提出一種基于分段特征及自適應(yīng)加權(quán)的DTW 相似性度量方法。首先對原始時間序列在各個變量維度上進(jìn)行整體分段，選取分段區(qū)間的斜率、最大值、最小值以及時間跨度作為每一段的特征表示，分段特征表示不僅可以實(shí)現(xiàn)對原時間序列的大幅降維，還可以較為準(zhǔn)確地體現(xiàn)序列的值域和形態(tài)特征。然后使用分段后的時間序列特征矩陣進(jìn)行相似性度量，以大幅降低計(jì)算復(fù)雜度，提高計(jì)算效率。在DTW 計(jì)算最佳彎曲路徑的過程中為每個點(diǎn)設(shè)置代價權(quán)重來限制序列中點(diǎn)列的重復(fù)使用次數(shù)，改善序列一對多的情形。

1 多元時間序列分段和特征表示

一種高效的時間序列特征表示方法能大幅提高時間序列數(shù)據(jù)挖掘的效率［13］。由于時間序列一般具有時序變化、數(shù)值差異及形態(tài)多樣性的特性，因此可以用X={xi(t)}，i=1，2，…，m，t=1，2，…，n表示。當(dāng)m=1 時表示UTS，當(dāng)m≥2 時表示MTS。由于一般原始時間序列數(shù)據(jù)具有海量性和復(fù)雜性［14］，因此需要對多元時間序列進(jìn)行分段特征表示，提取序列的特征信息，對數(shù)據(jù)進(jìn)行降維以降低存儲成本和計(jì)算成本。一個簡單的做法是：將1 個MTS 分解成多個UTS，再對每個一元時間序列進(jìn)行分段特征表示。但這種方法忽略了MTS 中各變量之間的相關(guān)性，因?yàn)槭挛餇顟B(tài)的刻畫往往需要多個變量共同確定，并且變量之間通常存在一定的相關(guān)性，多元時間序列不能看作是多個單變量時間序列的簡單疊加［15］。因此，在對多元時間序列分段時，需要同時在所有變量維度上進(jìn)行分段操作，這樣可以避免將各個變量割裂開來，保持了分段后變量之間的相關(guān)性。本文將采用基于誤差的自底向上分段方法［16］對多元時間序列進(jìn)行多維分段擬合，首先將長度為n的序列分成n/2 段，接著遞歸地計(jì)算2 個相鄰分段合并后的擬合誤差，然后繼續(xù)合并擬合誤差最小的相鄰分段，當(dāng)全部的擬合誤差都大于給定的閾值時停止合并。

設(shè)多元時間序列有M個變量維度，Pm表示第m維變量在包含I個數(shù)據(jù)點(diǎn)分段上的擬合線段，則第m維變量在當(dāng)前分段的擬合標(biāo)準(zhǔn)差定義為：

評估M維的擬合誤差，對所有變量的擬合標(biāo)準(zhǔn)誤差進(jìn)行加權(quán)求和，即可得到當(dāng)前分段的擬合標(biāo)準(zhǔn)誤差：

由于不同變量的量綱和特征存在差異，在模式匹配中的重要性也不完全相同，因此式（2）在計(jì)算擬合段的總誤差時，加入了變量維度的權(quán)重系數(shù)。ωm表示第m個變量的誤差權(quán)重值，且滿足這里計(jì)算的分段擬合標(biāo)準(zhǔn)誤差是在全部變量上的總誤差，以達(dá)到多維分段的目的。

在對多元時間序列進(jìn)行多維分段線性擬合后，擬合線段的斜率和時間跨度反映了原始序列的形態(tài)特征，分段上所有數(shù)據(jù)點(diǎn)的最大值最小值反映了原始序列的值域特征，因此，選擇擬合線段的斜率k、分段區(qū)間內(nèi)的最大值E、最小值e以及分段時間跨度d作為某一變量維度上一個分段的特征。當(dāng)一個含有M個變量的序列被分成N段時，該序列可用如下特征矩陣表示：

在度量2 條多元時間序列相似性時，為了消除不同特征之間的量綱差異對度量結(jié)果帶來的影響，需要對特征矩陣進(jìn)行標(biāo)準(zhǔn)化處理，對斜率k、最大值E、最小值e和時間跨度d的標(biāo)準(zhǔn)化方法分別如式（4）～式（7）所示：

其中：式（4）將斜率轉(zhuǎn)化為角度；式（5）和式（6）將值域特征歸一化；式（7）將時間跨度轉(zhuǎn)化為時間跨度與時間長度的比值。在標(biāo)準(zhǔn)化處理后，得到轉(zhuǎn)換后的特征矩陣如式（8）所示：

多維分段特征表示不僅保留了特征間的關(guān)聯(lián)性，而且達(dá)到了降維的目的。

2 基于自適應(yīng)的動態(tài)時間彎曲距離

在時間序列數(shù)據(jù)分段線性特征表示完成后，特征矩陣即可看作原始多元時間序列在多維分段之后的特征序列，將以前針對點(diǎn)和點(diǎn)的相似性度量方法用于子段和子段之間，該處理方法大幅降低了計(jì)算復(fù)雜度，減少了計(jì)算時間。經(jīng)過特征提取和轉(zhuǎn)換后，多元時間序列特征矩陣的行數(shù)是相同的，即它們的變量維度是一一對應(yīng)的關(guān)系；由于分段數(shù)量可能不同，矩陣的列數(shù)不同即序列的長短不一。DTW 能通過對時間軸的彎曲解決2 個不等長序列之間相似性度量的問題，因此可以用于特征矩陣之間的比較。本文以每段的特征值作為輸入值，利用動態(tài)時間彎曲來度量2 條序列的相似度。

DTW 在計(jì)算多元時間序列最佳彎曲路徑時，雖能通過動態(tài)彎曲體現(xiàn)序列形態(tài)特征，但是為了獲得最小的累積距離，DTW 距離可能會將一個時間序列上的多個點(diǎn)映射到另一個時間序列上的一個點(diǎn)，出現(xiàn)不合理的匹配。這使得時間序列過度拉伸和壓縮，導(dǎo)致重要的特征信息丟失，因此為了追求最小距離使時間序列過渡扭曲，將無法精準(zhǔn)得測量2 條時間序列的距離，從而影響度量的精度，如圖1 所示。

圖1 動態(tài)時間彎曲距離的過渡扭曲匹配Fig.1 Transition distortion matching of dynamic time warping distance

本文提出基于分段特征及自適應(yīng)加權(quán)的多元時間序列相似性度量（ASW-DTW）方法。該方法為每個序列點(diǎn)賦予代價權(quán)值，并且該權(quán)值是在計(jì)算過程中自行確定的，無需增加額外的計(jì)算成本。在動態(tài)規(guī)劃求解最佳彎曲路徑的過程中，自適應(yīng)地調(diào)整每個點(diǎn)的權(quán)值，使得特征點(diǎn)使用次數(shù)愈多，權(quán)重系數(shù)值愈大。在后文計(jì)算匹配路徑的過程中將有選擇地使用這些點(diǎn)，從而有效減少重復(fù)點(diǎn)的使用次數(shù)。

對于經(jīng)過特征提取和標(biāo)準(zhǔn)化處理之后的特征矩陣，可以使用X=[x1，x2，…，xN]來表示，其中，xi表示多維分段后第i個擬合段上M個變量的特征信息，其可以看作DTW 距離中的一個序列點(diǎn)。2 個多元時間序列特征矩陣X和Y中的2 個擬合段xi、yj第m維變量之間的距離為：

由于在度量2 個擬合段之間的距離時，不同特征的權(quán)重不同，因此要為每個特征賦予權(quán)重以突出不同特征的重要性，且權(quán)重參數(shù)滿足：

則2 個擬合段上DTW 中的基礎(chǔ)距離定義為：

多元時間序列不同變量維度代表的意義不同，重要性也有所差異，因此在比較時對不同變量分配不同的權(quán)重。其中ωm表示第m個變量的權(quán)重值，且所有變量的權(quán)重和為1，即ωm的值滿足：

在ASW-DTW 距離中，第i個擬合段的自適應(yīng)代價權(quán)重定義如下：

其中：k是一個正參數(shù)，用來調(diào)整代價函數(shù)ci(t)的效果，k值越大，ci(t)的效果越強(qiáng)，k值越小，ci(t)的效果越弱；t表示每個點(diǎn)在時間序列中使用的次數(shù)，因此代價函數(shù)與t成正比，即當(dāng)t較大時，代價函數(shù)也較大。同時，考慮到當(dāng)2 條序列長度不同，特別是長度差異明顯時，多對1 的情況將會更普遍，此時對畸形匹配的容忍度應(yīng)該較大，因此引入序列的長度比值r，其定義如下：

其中：N和N′分別表示2 條序列的長度。當(dāng)2 條序列的長度差異越大時，即r越小，代價權(quán)重ci(t)的衰減速率也就越小。

引入代價權(quán)值信息之后，采用動態(tài)規(guī)劃計(jì)算2 條多元時間序列之間的ASW-DTW 距離，計(jì)算公式如下：

ASW-DTW 算法是在原DTW 算法的基礎(chǔ)上增加了自適應(yīng)的動態(tài)權(quán)值。該算法用于尋找2 條序列上每個點(diǎn)之間的最優(yōu)對齊匹配關(guān)系，對于長度分別為m、n的2 條時間序列X、Y之間的匹配關(guān)系可以用彎曲路徑S={s1，s2，…，sK}表示，一般情況下存在著多條彎曲路徑，有效的彎曲路徑必須滿足以下3 個條件：

1）邊界性：s1=(1，1)，sK=(m，n)。

2）單調(diào)性：給定sk=(i，j)和sk+1=(i′，j′)，有i′≥i，j′≥。

3）連續(xù)性：給定sk=(i，j)和sk+1=(i′，j′)，有i′≤i+1，j′≤j+1。

選取彎曲路徑中連續(xù)元素的基礎(chǔ)距離之和，可得到該路徑的累積距離。在式（15）中，ASW-DTW（i，j）表示第i個擬合段和第j個擬合段之間的ASW-DTW 累計(jì)距離，且ASW-DTW（1，1）=dbase（x1，y1）；ci（t）表示了第i個擬合段當(dāng)前的權(quán)重，即當(dāng)某點(diǎn)被重復(fù)使用時，賦給基礎(chǔ)距離一個與該點(diǎn)使用次數(shù)有關(guān)的權(quán)重。通過上式不斷迭代以判斷下一步的走向，使得累計(jì)距離最小，以便得到最優(yōu)彎曲路徑。

當(dāng)ASW-DTW 取值為①時，表示引入代價權(quán)重的動態(tài)時間彎曲下的最優(yōu)路徑選擇經(jīng)過(xi，yj-1)→(xi，yj)，即點(diǎn)xi被重復(fù)使用，則對xi增加權(quán)重，增大該路徑的距離。

當(dāng)ASW-DTW 取值為②時，表示引入代價權(quán)重的動態(tài)時間彎曲下的最優(yōu)路徑選擇經(jīng)過(xi-1，yj-1)→(xi，yj)，即沒有點(diǎn)被重復(fù)使用。

當(dāng)ASW-DTW 取值為③時，引入代價權(quán)重的動態(tài)時間彎曲下的最優(yōu)路徑選擇經(jīng)過(xi-1，yj)→(xi，yj)，即yj被重復(fù)使用，則對yj增加權(quán)重，增大該路徑的距離。

綜上所述，采用ASW-DTW 算法計(jì)算2 條多元時間序列之間的最優(yōu)彎曲距離步驟如下：

1）對多元時間序列進(jìn)行多維分段特征表示，標(biāo)準(zhǔn)化處理后，得到如式（8）的特征矩陣。

2）以特征矩陣作為ASW-DTW 算法的輸入，計(jì)算特征矩陣之間的動態(tài)彎曲距離。詳細(xì)算法如下：

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

編譯工具Python3.6.0，操作系統(tǒng)Windows8，CPU/Intel?CoreTMi5-3337U雙核處理器，主頻1.8 GHz，內(nèi)存8 GB，硬盤容量1T。

3.2 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)方法

為了便于比較時間序列通過相似性度量的聚類性能，本文選取UCI 數(shù)據(jù)集中已知分類結(jié)果的多元時間序列作為研究對象，采用k-近鄰的方法進(jìn)行聚類實(shí)驗(yàn)。選用Australian Sign Language（ASL）［17］、EEG［18］、Robot Execution Failure（REF）［19］和Japanese Vowels（JV）［20］4組數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其中：ASL 是包含22 個特征的手語信號數(shù)據(jù)集，選擇前8 種語意對應(yīng)的216 個序列作為實(shí)驗(yàn)數(shù)據(jù)集；EEG 是采集了2 類人群（alcoholic 和control）的腦電圖數(shù)據(jù)，選取前2 位測試者的前11 次測試作為實(shí)驗(yàn)數(shù)據(jù)；REF 是對機(jī)器進(jìn)行故障采集的數(shù)據(jù)集，采樣周期為21 ms，包含6 個離散型變量，該數(shù)據(jù)集包含5 個子數(shù)據(jù)集，實(shí)驗(yàn)選取第1 個子數(shù)據(jù)集LP1 進(jìn)行實(shí)驗(yàn)，已知LP1 數(shù)據(jù)集分為4 類，共有88 個樣本，樣本屬于6×15 的矩陣，屬于時間跨度較小、體現(xiàn)某些狀態(tài)點(diǎn)的多元時間序列；JV用12個變量刻畫了日文元音的發(fā)音過程，包含9 個測試者的發(fā)音數(shù)據(jù)，每個測試者發(fā)音30 次，共270 個樣本。序列長度范圍為7～29，屬于小規(guī)模的多元時間序列。數(shù)據(jù)集基本信息如表1 所示。

表1 數(shù)據(jù)集信息Table 1 Datasets information

實(shí)驗(yàn)采用留一交叉驗(yàn)證結(jié)合k-近鄰法。首先對具有n個序列的數(shù)據(jù)集進(jìn)行特征提取，從中選取1 個序列x作為輸入序列。然后采用某種相似性度量方法找出與x最相似的k個序列（k分別取1、5 和10）。在找出的k個序列中，計(jì)算與x同類的序列個數(shù)n0，計(jì)算分類準(zhǔn)確率為：

對于數(shù)據(jù)集中其他多元時間序列，依次作為輸入序列，可以得到n個相似性度量的準(zhǔn)確率。計(jì)算平均準(zhǔn)確率為：

并將其作為度量有效性的比較依據(jù)。

在ASW-DTW 距離度量中，度量結(jié)果是由數(shù)據(jù)點(diǎn)之間的基礎(chǔ)距離累計(jì)的結(jié)果，并且由式（9）可知，參數(shù)β、λ、γ的選擇也將直接影響到多元時間序列基礎(chǔ)距離的度量。因此，為了確定最佳參數(shù)組合，本文以ASL數(shù)據(jù)集為例，選擇不同的β、λ、γ，使用KNN 分類討論不同的參數(shù)選擇對算法準(zhǔn)確度的影響，最終找到最佳參數(shù)組合，提高度量精度。這里，k取值為5，即使用基于ASW-DTW 距離度量的KNN 方法從測試集中找出5 個與輸入序列距離最近的序列，計(jì)算評均準(zhǔn)確率。為了不失一般性，先假設(shè)各個變量的重要性相同，即各個變量維度上的權(quán)重ωm相等，在變量維度上不存在差異。在分段擬合標(biāo)準(zhǔn)誤差cost取0.03 時，權(quán)重衰減速率k取值0.05。分別在分段特征參數(shù)β、λ、γ取不同值的情況下，計(jì)算平均查準(zhǔn)率。由于在2個參數(shù)確定的情況下滿足式（10）的條件，第3 個參數(shù)將是確定的，因此γ值并未直接給出，例如當(dāng)β=0.0、λ=0.0 時，則有γ=1.0。不同參數(shù)下的平均查準(zhǔn)率如圖2 所示。

圖2 ASL 數(shù)據(jù)集不同β、λ、γ 選擇下的平均查準(zhǔn)率Fig.2 Average precision rate under different β，λ，γ choices in ASL dataset

從圖2 可知，當(dāng)β=0.6、λ=0.3、γ=0.1 時，平均查準(zhǔn)率最高，達(dá)到0.94。可以看出，在β取值較低時，查準(zhǔn)率隨著λ 的增大而增大，說明在不注重序列趨勢差異時，序列的值域差異對距離度量的影響占主導(dǎo)地位，同時，圖2 中最前側(cè)一列（λ=0）的查準(zhǔn)率均比其他列低，也說明了序列之間值域差異在度量序列距離時的重要性。實(shí)驗(yàn)結(jié)果表明，將值域特征加入到多元時間序列特征的必要性。

為了驗(yàn)證ASW-DTW 算法在多元時間序列相似性度量時的準(zhǔn)確性，本文分別在4 個數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對比，分別基于ASW-DTW、DTW、PD、TD 和SVD 的KNN 算法在進(jìn)行相似性查找時的平均準(zhǔn)確率。針對每個數(shù)據(jù)集，均選擇最優(yōu)的參數(shù)組合，參數(shù)確定方法同實(shí)驗(yàn)1，參數(shù)選擇結(jié)果如表2 所示。

表2 不同數(shù)據(jù)集下β、λ、γ 選擇情況Table 2 Selection of β，λ，γ under different dataset

每種方法分別取k=1，5，10，將數(shù)據(jù)集中每個數(shù)據(jù)依次作為測試數(shù)據(jù)輸入，并計(jì)算平均準(zhǔn)確率，實(shí)驗(yàn)結(jié)果如表3～表6 所示（粗體表示最優(yōu)值）。

表3 ASL 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Table 3 Experimental results of ASL dataset

表4 EEG 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Table 4 Experimental results of EEG dataset

表5 REF-LP1 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Table 5 Experimental results of REF-LP1 dataset

表6 JV 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Table 6 Experimental results of JV dataset

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

由表3～表6 在4 種數(shù)據(jù)集上分別用5 種度量方法的平均準(zhǔn)確率可以看出，不同k值下的ASW-DTW 方法在4 個數(shù)據(jù)集上均能取得不錯的平均準(zhǔn)確率，特別是在ASL 和EEG 數(shù)據(jù)集上明顯優(yōu)于PD 方法和SVD 方法。并且可以看出ASW-DTW 相比于DTW，平均準(zhǔn)確率有一定幅度的提升，說明在這2 個數(shù)據(jù)集上，DTW 的畸形匹配問題影響了距離度量結(jié)果，而自適應(yīng)代價權(quán)重DTW 有效地避免了該問題。在REF-LP1 和JV 這樣的小規(guī)模數(shù)據(jù)集上，ASW-DTW 依然能取得不錯的結(jié)果。在這2 個數(shù)據(jù)集上，ASW-DTW 算法相對于DTW的結(jié)果提升不大，原因在于：ASW-DTW算法在改善2條時間序列多對一的過渡匹配時，與數(shù)據(jù)集本身的特點(diǎn)密切相關(guān)，說明在這2 個數(shù)據(jù)集上序列沒有出現(xiàn)過渡的拉伸或壓縮。同時注意到，由于JV 數(shù)據(jù)集序列長度較小，趨勢變化不明顯，TD 算法的度量結(jié)果較差，TD算法已經(jīng)喪失了其有效性，但通過表6可知，ASW-DTW仍能通過減小趨勢差異權(quán)重，增加值域特征差異權(quán)重的方式取得較好的度量結(jié)果。

3.4 計(jì)算復(fù)雜度比較

對于序列長度分別為m和n的2 條時間序列X和Y，由于DTW 距離需要在m×n的矩陣上尋找最優(yōu)彎曲路徑，因此計(jì)算復(fù)雜度為O（m×n）。假設(shè)對X、Y時間序列進(jìn)行多維分段和特征表示后，長度分別為m′和n′，則分段后的時間序列進(jìn)行相似性度量的計(jì)算復(fù)雜度為O（m′×n′）。由此可知，計(jì)算復(fù)雜度主要取決于時間序列特征的長度，可用式（18）比較算法的計(jì)算復(fù)雜度：

對于給定的數(shù)據(jù)集，本文使用特征序列的平均壓縮率（CR）的平方來近似表示式（18）中的η，近似比較DTW 與ASW-DTW 方法的計(jì)算復(fù)雜度，結(jié)果如表7 所示。

表7 不同數(shù)據(jù)集下ASW-DTW 與DTW 計(jì)算復(fù)雜度比較Table 7 Comparison of ASW-DTW and DTW computational complexity under different datasets

此外，為了更精準(zhǔn)地比較計(jì)算復(fù)雜度，分別記錄ASW-DTW 和DTW 的計(jì)算時間，并利用它們的時間比來比較計(jì)算復(fù)雜度，如圖3 所示。

圖3 計(jì)算復(fù)雜度比較Fig.3 Comparison of computational complexity

實(shí)驗(yàn)數(shù)據(jù)對比結(jié)果表明，特征序列壓縮率的平方CR2可近似比較算法的計(jì)算復(fù)雜度。由于時間序列在進(jìn)行分段特征表示后，特征序列長度小于原時間序列，并且結(jié)合表7 和圖3 可以看出，基于分段特征的時間序列進(jìn)行相似性度量能較大幅度地降低計(jì)算復(fù)雜度。

4 結(jié)束語

針對DTW 尋找路徑過程中時間復(fù)雜度高且容易出現(xiàn)一對多情形，本文提出一種基于分段加權(quán)特征的多元時間序列相似性度量方法。對原始時間序列在各個變量維度上統(tǒng)一進(jìn)行分段，選取分段后擬合線段的斜率、分段區(qū)間的最大值和最小值以及時間跨度作為多元時間在序列的特征表示，比較準(zhǔn)確地刻畫出多元時間序列不同時刻的趨勢和值域信息，實(shí)現(xiàn)對原時間序列的大幅降維。針對DTW 算法在相似性度量過程中追求最小距離容易出現(xiàn)一對多的情形，本文對每個點(diǎn)賦予代價權(quán)重，在匹配過程中通過賦給基礎(chǔ)距離自適應(yīng)代價權(quán)重來限制序列中點(diǎn)列的使用來減少不合理匹配情況，以此改善DTW 中時間點(diǎn)過度拉伸或壓縮以達(dá)到較好的匹配效果。實(shí)驗(yàn)結(jié)果表明，預(yù)處理后的時間序列明顯減小了算法的計(jì)算復(fù)雜度，提高了計(jì)算效率。因此，基于分段特征的ASW-DTW 不僅降低了計(jì)算復(fù)雜度，而且在多個數(shù)據(jù)集上能取得較高的查準(zhǔn)率，并且該方法可以通過調(diào)整擬合特征值的權(quán)重來適應(yīng)不同的數(shù)據(jù)集。下一步將研究根據(jù)變量的重要性對變量的權(quán)重進(jìn)行選擇，通過優(yōu)化模型參數(shù)選擇方法，將ASW-DTW 方法以最優(yōu)的參數(shù)組合應(yīng)用在各個領(lǐng)域的多元時間序列數(shù)據(jù)挖掘任務(wù)中。