劉苗苗，周從華，張 婷

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

0 概述

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

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

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

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

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

1 多元時(shí)間序列分段和特征表示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）以特征矩陣作為ASW-DTW 算法的輸入，計(jì)算特征矩陣之間的動(dòng)態(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)方法

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

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

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

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

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

在ASW-DTW 距離度量中，度量結(jié)果是由數(shù)據(jù)點(diǎn)之間的基礎(chǔ)距離累計(jì)的結(jié)果，并且由式（9）可知，參數(shù)β、λ、γ的選擇也將直接影響到多元時(shí)間序列基礎(chǔ)距離的度量。因此，為了確定最佳參數(shù)組合，本文以ASL數(shù)據(jù)集為例，選擇不同的β、λ、γ，使用KNN 分類討論不同的參數(shù)選擇對(duì)算法準(zhǔn)確度的影響，最終找到最佳參數(shù)組合，提高度量精度。這里，k取值為5，即使用基于ASW-DTW 距離度量的KNN 方法從測(cè)試集中找出5 個(gè)與輸入序列距離最近的序列，計(jì)算評(píng)均準(zhǔn)確率。為了不失一般性，先假設(shè)各個(gè)變量的重要性相同，即各個(gè)變量維度上的權(quán)重ωm相等，在變量維度上不存在差異。在分段擬合標(biāo)準(zhǔn)誤差cost取0.03 時(shí)，權(quán)重衰減速率k取值0.05。分別在分段特征參數(shù)β、λ、γ取不同值的情況下，計(jì)算平均查準(zhǔn)率。由于在2個(gè)參數(shù)確定的情況下滿足式（10）的條件，第3 個(gè)參數(shù)將是確定的，因此γ值并未直接給出，例如當(dāng)β=0.0、λ=0.0 時(shí)，則有γ=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 時(shí)，平均查準(zhǔn)率最高，達(dá)到0.94?？梢钥闯觯讦氯≈递^低時(shí)，查準(zhǔn)率隨著λ 的增大而增大，說(shuō)明在不注重序列趨勢(shì)差異時(shí)，序列的值域差異對(duì)距離度量的影響占主導(dǎo)地位，同時(shí)，圖2 中最前側(cè)一列（λ=0）的查準(zhǔn)率均比其他列低，也說(shuō)明了序列之間值域差異在度量序列距離時(shí)的重要性。實(shí)驗(yàn)結(jié)果表明，將值域特征加入到多元時(shí)間序列特征的必要性。

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

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

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

對(duì)于給定的數(shù)據(jù)集，本文使用特征序列的平均壓縮率（CR）的平方來(lái)近似表示式（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ì)算時(shí)間，并利用它們的時(shí)間比來(lái)比較計(jì)算復(fù)雜度，如圖3 所示。

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

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

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

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