陸 成 剛

(浙江工業(yè)大學(xué) 理學(xué)院，杭州 310023)

E-mail：luchenggang168@gmail.com

1 引 言

序列比對(duì)是矢量聚類(lèi)或模式分類(lèi)的基礎(chǔ)，它的核心功能是計(jì)算模式之間的相似(異)性的程度.無(wú)論哪一種聚類(lèi)分類(lèi)方法，本質(zhì)上都要基于某種內(nèi)置的距離運(yùn)算.常規(guī)的歐幾里德距離可以看作是一種靜態(tài)的序列比對(duì)，而經(jīng)典的DTW距離(DTW英文全稱(chēng)Dynamic Time Warping即動(dòng)態(tài)時(shí)間規(guī)整)則以動(dòng)態(tài)對(duì)齊模式的距離計(jì)算而聞名[1-3].數(shù)學(xué)上可以證明，DTW距離并不符合距離公理的三角形法則(但滿(mǎn)足非負(fù)性、對(duì)稱(chēng)性法則)，所以它并不支持使用算術(shù)平均來(lái)計(jì)算多個(gè)矢量的質(zhì)心(距離滿(mǎn)足三角形法則是使用算術(shù)平均計(jì)算該距離意義下質(zhì)心的必要條件)，也因此在k均值聚類(lèi)、模糊c均值聚類(lèi)等領(lǐng)域應(yīng)用受到限制[4,5].事實(shí)上，在DTW對(duì)齊模式下求兩個(gè)矢量的算術(shù)平均是可以得到它們的(基于DTW距離意義下的)質(zhì)心的，只是對(duì)于三個(gè)以上的矢量求它們的動(dòng)態(tài)對(duì)齊方式是比較困難的，這就是所謂的動(dòng)態(tài)規(guī)劃算法的“維數(shù)災(zāi)難”問(wèn)題[6-8].在兩個(gè)序列之間使用DTW計(jì)算距離具有一些不可多得的優(yōu)勢(shì)，如能適應(yīng)序列在時(shí)間軸上的伸縮變異，又能適應(yīng)參與比較的兩個(gè)序列長(zhǎng)度不一致的情況.在層次聚類(lèi)、kNN近鄰法、PCA聚類(lèi)、譜聚類(lèi)和DBSCAN聚類(lèi)法中只涉及計(jì)算兩兩之間的序列距離[9-13]，因而都可以使用DTW距離作為內(nèi)置.

2 DTW的重新理解

2.1 DTW距離

DTW是使用動(dòng)態(tài)規(guī)劃方法搜尋序列間足標(biāo)的一種最佳對(duì)應(yīng)使它們具有最小的距離.DTW距離主要使用在評(píng)估兩個(gè)數(shù)據(jù)序列之間的相似性上.特別是基于DTW距離的kNN匹配分類(lèi)法一度是近十幾年間序列分類(lèi)識(shí)別應(yīng)用領(lǐng)域的經(jīng)典標(biāo)配[16-18].如圖1示例了常規(guī)歐幾里德距離的靜態(tài)對(duì)應(yīng)和DTW距離的動(dòng)態(tài)對(duì)應(yīng)之間的差異：前者具有平行平均的對(duì)應(yīng)間隔、后者完全是不規(guī)則對(duì)應(yīng)的.

圖1 DTW動(dòng)態(tài)時(shí)間規(guī)整具有捕捉序列時(shí)長(zhǎng)動(dòng)態(tài)差異的特性

圖2 坐標(biāo)軸點(diǎn)陣的路徑

傳統(tǒng)的DTW距離算法是基于動(dòng)態(tài)規(guī)劃原理進(jìn)行的，引入狀態(tài)變量D(i,j)表示由P1=(1,1)到點(diǎn)(i,j)的最小距離，于是D(n,m)就是所求的DTW距離.狀態(tài)變量D(i,j)有遞推式D(i,j)=min{D(i-1,j-1),D(i-1,j),D(i,j-1)}+d(i,j)其中d(i,j)=|xi-yj|2或d(i,j)=|xi-yj|.根據(jù)遞推公式生成狀態(tài)矩陣(D(i,j))m×n，其中首行首列通過(guò)其唯一前鄰點(diǎn)來(lái)生成，取得最小值的最優(yōu)路徑由終點(diǎn)(n,m)逆溯到起點(diǎn)(1,1)而得到.取得路徑的逆溯過(guò)程的偽碼如下.

1) Path=NULL,(n,m)→Path;

2)i=n,j=m;

while(i>1 or j>1)

{

if(i==1) j=j-1;

else if(j==1) i=i-1;

else i, j get value from

min{D(i-1,j-1),D(i,j-1),D(i-1,j)};//將最小者對(duì)應(yīng)的足標(biāo)賦給i、j

(i,j)→Path;

}

3) Inverse(Path);//將Path中各點(diǎn)倒序;

2.2 DTW更新解讀

DTW距離求解法是基于狀態(tài)變量的遞推方程施行的，而遞推方程成立是利用了平方距離或曼哈頓距離的累計(jì)可加性.利用距離形式的累計(jì)可加性可以得出達(dá)到最優(yōu)值的路徑也具有保持最優(yōu)性的可加性(簡(jiǎn)稱(chēng)可加保優(yōu)性)，這就是定理1.

首先介紹路徑全分割：如圖3中路徑Path={P1,P2,…,PL}分割成多個(gè)片段，每個(gè)片段稱(chēng)謂子路徑(Subpath)，前后相鄰的子路徑共享一端點(diǎn)，所有子路徑的依次串接(共享的端點(diǎn)只計(jì)一點(diǎn))恢復(fù)為原路徑.

圖3 路徑的全分割示意圖：路徑Path被分割為4段子路徑Subpath，且第一條子路徑的起點(diǎn)P1，第4條子路徑的終點(diǎn)PL

定理1.設(shè)Path={P1,P2,…,PL}是DTW距離的(最優(yōu))路徑，則對(duì)該路徑的任何一個(gè)全分割，每條子路徑都是其自身起點(diǎn)到其自身終點(diǎn)的最優(yōu)路徑.反之，Path={P1,P2,…,PL}的任意一個(gè)全分割的每條子路徑都是其起點(diǎn)到其終點(diǎn)的最優(yōu)路徑，則Path={P1,P2,…,PL}是DTW距離的(最優(yōu))路徑.

證明：先證前面的結(jié)論，使用反證法，假設(shè){Pi,Pi+1,…,Pj}?{P1,P2,…,PL}是一條子路徑，并且{Pi,Pi+1,…,Pj}不是序列(x(Pi)x,x(Pi)x+1,…,x(Pj)x)和(y(Pi)y,y(Pi)y+1,…,y(Pj)y)間DTW距離對(duì)應(yīng)的最優(yōu)路徑.求得它們的DTW距離對(duì)應(yīng)的路徑不妨設(shè)為{Pi′,Pi′+1,…,Pj′}其中Pi′=Pi且Pj′=Pj，則{P1,P2,…,Pi-1,Pi′,Pi′+1,…,Pj′,Pj+1,…,PL}對(duì)應(yīng)的距離數(shù)值應(yīng)小于Path={P1,P2,…,PL} 對(duì)應(yīng)的距離數(shù)值，這與Path={P1,P2,…,PL}是DTW距離對(duì)應(yīng)的(最優(yōu))路徑矛盾.再證后面的結(jié)論，反之，Path={P1,P2,…,PL}本身也是它自己的一個(gè)全分割，它是最優(yōu)路徑，所以它是DTW距離的(最優(yōu))路徑.證畢.

引入始發(fā)路徑的概念：以端點(diǎn)(1,1)為起點(diǎn)的路徑稱(chēng)為始發(fā)路徑.如果對(duì)路徑上任意點(diǎn)作終點(diǎn)的始發(fā)路徑都是從(1,1)到該點(diǎn)的最優(yōu)路徑，則稱(chēng)該路徑具有始發(fā)保優(yōu)性.DTW距離路徑即具始發(fā)保優(yōu)性，此為推論1.

推論1.設(shè)Path={P1,P2,…,PL}是DTW距離的(最優(yōu))路徑，則以該路徑上任意點(diǎn)作終點(diǎn)的始發(fā)路徑都是從(1,1)到該點(diǎn)的最優(yōu)路徑.反之，如果Path={P1,P2,…,PL}滿(mǎn)足這樣的性質(zhì)：以該路徑上任意點(diǎn)作終點(diǎn)的始發(fā)路徑都是從(1,1)到該點(diǎn)的最優(yōu)路徑，則Path={P1,P2,…,PL}是DTW距離的(最優(yōu))路徑.

證明：在Path={P1,P2,…,PL}任取一點(diǎn)作始發(fā)路徑的終點(diǎn)，則該始發(fā)路徑與以該點(diǎn)作起點(diǎn)、(n,m)為終點(diǎn)的子路徑構(gòu)成原路徑的全分割，根據(jù)定理1，該始發(fā)路徑為最優(yōu)路徑.反之是顯然的.證畢.

圖4示意了始發(fā)最優(yōu)特性，一條最優(yōu)路徑上任意點(diǎn)作終點(diǎn)的框內(nèi)部分(路徑)都是最優(yōu)的.

圖4 始發(fā)最優(yōu)示意

3 DTW距離的缺陷

傳統(tǒng)的DTW距離隱含著一種缺陷，例如考慮使用DTW距離計(jì)算以下三段直流信號(hào)的匹配情況：A=(0.1,0.1)、B=(0.25,0.25,0.25,0.25)、C=(0.28,0.28,0.28)，信號(hào)A與B的DTW距離為0.6，其最優(yōu)匹配路徑的長(zhǎng)度為4；而信號(hào)C與A的DTW距離0.54，最優(yōu)匹配路徑的長(zhǎng)度為3.從我們直覺(jué)判斷信號(hào)B比信號(hào)C更接近A，但從DTW距離決定的相異性來(lái)看，反而是C比B更接近A.造成這個(gè)反直覺(jué)的效果是由于我們僅僅考慮了距離，而忽視了路徑長(zhǎng)度，假如以DTW距離相對(duì)路徑長(zhǎng)度的平均值而言，B比C更接近A.傳統(tǒng)DTW的缺陷是沒(méi)有考慮路徑長(zhǎng)度平均的距離，從而可能導(dǎo)致兩個(gè)同類(lèi)序列的距離大于兩個(gè)異類(lèi)序列的距離.這就違背了“距離大小決定相異程度”的準(zhǔn)則.定理2從理論上揭示了這種可能性.

圖5 信號(hào)重構(gòu)采樣后的DTW匹配

定理2.設(shè)對(duì)于序列S1其采樣周期為T(mén)，先將S1使用sinc插值恢復(fù)成模擬信號(hào)，再使用T/n的采樣周期離散化形成序列S2，S2長(zhǎng)度n倍于S1、但兩者仍屬同類(lèi)序列，可證S1和S2的DTW距離隨著n的增加而無(wú)限制增加，勢(shì)必將大于S1與任一確定的其它類(lèi)序列H的DTW距離.

圖6 同類(lèi)序列DTW距離隨著長(zhǎng)度差異變大而變大

可見(jiàn)考慮路徑長(zhǎng)度平均意義下的DTW距離是必要的，而這又牽涉到對(duì)于不滿(mǎn)足累計(jì)可加特性的距離形式的處理.

4 基于始發(fā)保優(yōu)的延拓

對(duì)序列X=(x1,x2,…,xn)與Y=(y1,y2,…,ym)，定義滿(mǎn)足端點(diǎn)條件、連續(xù)性和單調(diào)性的足標(biāo)對(duì)應(yīng)的路徑Path={P1,P2,…,PL}，提出三個(gè)組合優(yōu)化問(wèn)題

(1)

(2)

(3)

顯然平均距離、Pearson相關(guān)系數(shù)和Tanimoto系數(shù)不滿(mǎn)足累計(jì)可加性，組合優(yōu)化問(wèn)題式(1-3)的最優(yōu)解沒(méi)有保優(yōu)可加性結(jié)構(gòu).由于始發(fā)保優(yōu)特性易于算法實(shí)施，受此啟發(fā)，提出修正的最優(yōu)路徑問(wèn)題.考慮任意的終點(diǎn)為(μ,υ)的始發(fā)路徑，記作Path(μ,υ)，由此對(duì)應(yīng)的三個(gè)組合優(yōu)化問(wèn)題衍生為三族問(wèn)題，即

(4)

(5)

(6)

式(4-6)是三族優(yōu)化問(wèn)題，每族都考慮為μ=1,2,…,n;υ=1,2,…,m遍歷整個(gè)點(diǎn)陣時(shí)的一系列組合優(yōu)化問(wèn)題，由此開(kāi)發(fā)的算法稱(chēng)為始發(fā)保優(yōu)的序列比對(duì).當(dāng)只考慮(μ,υ)=(n,m)時(shí)式(4-6)蛻化為式(1-3)，可以理解為式(4-6)的解路徑是式(1-3)的解路徑附加滿(mǎn)足始發(fā)保優(yōu)性質(zhì)的解路徑.

由式(4-6)求得的系數(shù)不妨稱(chēng)作動(dòng)態(tài)平均距離、動(dòng)態(tài)Pearson系數(shù)和動(dòng)態(tài)Tanimoto系數(shù)，照例它們滿(mǎn)足距離公理的非負(fù)性法則和對(duì)稱(chēng)性法則，且序列X=Y時(shí)動(dòng)態(tài)平均距離為0，而動(dòng)態(tài)Pearson系數(shù)和動(dòng)態(tài)Tanimoto系數(shù)均為1.

lij：表示(x1,x2,…,xi)與(y1,y2,…,yj)依始發(fā)最優(yōu)特性計(jì)算絕對(duì)值最大Pearson相關(guān)系數(shù)時(shí)得到的對(duì)應(yīng)路徑的長(zhǎng)度；

再引入這些統(tǒng)計(jì)量的累計(jì)計(jì)算公式，設(shè)(i′,j′)是當(dāng)前點(diǎn)(i,j)的一個(gè)后繼，即(i′,j′)=(i+1,j)或者(i′,j′)=(i,j+1) 或者(i′,j′)=(i+1,j+1)，則

li′j′=lij+1

(7)

(8)

(9)

(10)

(11)

(12)

以上諸公式中式(7)是顯然的，式(8、10)是均值累計(jì)計(jì)算原理的應(yīng)用；式(9、11)本質(zhì)上也是均值的累計(jì)計(jì)算，只是在應(yīng)用式(8、10)結(jié)果基礎(chǔ)上再進(jìn)行累計(jì)計(jì)算；式(12)是內(nèi)積的累計(jì)計(jì)算，可以通過(guò)內(nèi)積的定義直接驗(yàn)證.由此得到(i′,j′)的絕對(duì)值Pearson相關(guān)系數(shù)

(13)

下面給出以式(5)作例子的動(dòng)態(tài)Pearson系數(shù)算法，其它兩族問(wèn)題的算法類(lèi)推可得.

動(dòng)態(tài)Pearson系數(shù)算法

2.令k=1，h=2,3,…,m；l1h=l1h-1+1，

c1h=0

ck1=0

4.令k=2,3,…,n，h=2,3,…,m；

當(dāng)(u,v)遍歷{(k-1,h-1),(k-1,h),(k,h-1)}得到三個(gè)|ctemp|中取最大的一個(gè)(在計(jì)算動(dòng)態(tài)平均距離時(shí)取最小的一個(gè)，而動(dòng)態(tài)Tanimoto系數(shù)也是取最大)，此時(shí)(u,v)=(u0,v0)為{(k-1,h-1),(k-1,h),(k,h-1)}里的具體的一個(gè)格點(diǎn).因而利用式(7-13)更新矩陣元素如下

lkh=lu0v0+1

6.對(duì)其它兩族優(yōu)化問(wèn)題可以施行同樣的算法，這類(lèi)算法可以總結(jié)為如圖7的四個(gè)模塊：首先是初始化，如以上算法的步驟1；其次對(duì)涉及到的統(tǒng)計(jì)量構(gòu)成的矩陣更新其首行首列，如以上步驟2、3；然后依據(jù)式(7)-式(13)的累計(jì)計(jì)算原理更新矩陣的其余部分，如以上步驟4；最后是輸出結(jié)果如以上步驟5.

圖7 動(dòng)態(tài)系數(shù)算法框架

Fig.7 Algorithm framework for dynamic mode

圖8-圖10示例了DTW距離與動(dòng)態(tài)平均距離、Pearson系數(shù)與動(dòng)態(tài)Pearson系數(shù)、以及Tanimoto系數(shù)和動(dòng)態(tài)Tanimoto系數(shù)的執(zhí)行效果的比較：

圖8 DTW距離與動(dòng)態(tài)平均距離的比較

圖9 Pearson系數(shù)與動(dòng)態(tài)Pearson系數(shù)的比較

圖10 Tanimoto系數(shù)與動(dòng)態(tài)Tanimoto系數(shù)的比較

在圖8-圖10中點(diǎn)劃線示例的是同一類(lèi)序列，粗實(shí)線代表另外一類(lèi).圖8的DTW距離和動(dòng)態(tài)平均距離的示例顯示相同類(lèi)別的序列距離反而比不同類(lèi)別的序列的距離遠(yuǎn)，而動(dòng)態(tài)平均距離則能正常地顯示同類(lèi)距離近、異類(lèi)遠(yuǎn).造成DTW距離度量失效的原因是DTW距離對(duì)序列長(zhǎng)度分布的不均勻程度比較敏感，從而引入了路徑長(zhǎng)度對(duì)距離數(shù)值的干擾.主要表現(xiàn)在同類(lèi)的序列、但長(zhǎng)度相差較大時(shí)，DTW距離的數(shù)值較大，“掩蓋”了它們本該相似的屬性.在算法測(cè)試部分，更多的序列測(cè)試證實(shí)了動(dòng)態(tài)平均距離優(yōu)于DTW距離.圖9、圖10使用長(zhǎng)度相同的序列作比較，常規(guī)Pearson系數(shù)和Tanimoto系數(shù)均在同類(lèi)序列顯示值為小、而異類(lèi)序列值為大，動(dòng)態(tài)計(jì)算的Pearson系數(shù)和Tanimoto系數(shù)能有效地“糾正”這個(gè)反常現(xiàn)象.

圖11 動(dòng)態(tài)平均距離的最優(yōu)路徑不滿(mǎn)足可加保優(yōu)性

圖12 動(dòng)態(tài)Pearson系數(shù)的最優(yōu)路徑不滿(mǎn)足可加保優(yōu)性

圖13 動(dòng)態(tài)Tanimoto系數(shù)的最優(yōu)路徑不滿(mǎn)足可加保優(yōu)性

式(4-6)是始發(fā)保優(yōu)原則衍生的三族優(yōu)化問(wèn)題，但解路徑依舊沒(méi)有傳統(tǒng)DTW路徑的可加保優(yōu)特性.假如在依式(4-6)的最優(yōu)模式中獲得的全局最優(yōu)路徑上任意取定一點(diǎn)，以此為界，構(gòu)造一個(gè)分割，那么從始發(fā)點(diǎn)到該點(diǎn)的最優(yōu)路徑與全局最優(yōu)路徑的前部分重合，而由該點(diǎn)到終點(diǎn)的最優(yōu)路徑與全局最優(yōu)路徑的后部分不一致，產(chǎn)生分叉.圖11-圖13分別示例了這個(gè)由分割點(diǎn)產(chǎn)生路徑分叉的現(xiàn)象.它證實(shí)了基于式(4-6)的序列比對(duì)法滿(mǎn)足始發(fā)保優(yōu)，但不滿(mǎn)足可加保優(yōu)特性.

最后對(duì)DTW距離、動(dòng)態(tài)平均距離、動(dòng)態(tài)Pearson系數(shù)、和動(dòng)態(tài)Tanimoto系數(shù)進(jìn)行算法復(fù)雜度分析，主要考慮算法框架中涉及到的矩陣變量的數(shù)目，因?yàn)樗汝P(guān)聯(lián)到緩存占用大小，又關(guān)聯(lián)到更新矩陣元素的計(jì)算量.這里不考慮臨時(shí)變量、輔助變量、以及編程時(shí)各種數(shù)據(jù)類(lèi)型占用內(nèi)存的差異.由于輸入序列段長(zhǎng)分別是m和n，所以一個(gè)矩陣變量的資源數(shù)目就是mn，它既是緩存開(kāi)銷(xiāo)的大小，也是計(jì)算量級(jí).表1顯示了四類(lèi)方法的計(jì)算資源的消耗量級(jí).易知，DTW只需更新距離矩陣，所以是1個(gè)mn單位，而動(dòng)態(tài)平均距離除了距離矩陣外，還需要更新路徑長(zhǎng)度矩陣，所以是2個(gè)mn單位；動(dòng)態(tài)Pearson方法包含路徑長(zhǎng)度矩陣、序列X和Y的均值以及方差的矩陣、內(nèi)積矩陣和Pearson系數(shù)矩陣共7個(gè)mn單位，類(lèi)似可得動(dòng)態(tài)Tanimoto系數(shù)方法的復(fù)雜度是3個(gè)mn單位.

表1 四類(lèi)比對(duì)方法的計(jì)算復(fù)雜度比較

Table 1 Computation complexity comparing for 4 alignment methods

比對(duì)方法DTW動(dòng)態(tài)平均距離動(dòng)態(tài)Pearson動(dòng)態(tài)Tanimoto內(nèi)存消耗mn2mn7mn3mn計(jì)算量級(jí)mn2mn7mn3mn

5 動(dòng)態(tài)平均距離的算法測(cè)試

相對(duì)來(lái)說(shuō)動(dòng)態(tài)平均距離具有最接近原始DTW方法的計(jì)算資源占用效率，而且兩者皆是距離屬性，可比度強(qiáng)，在算法測(cè)試階段專(zhuān)門(mén)以動(dòng)態(tài)平均距離作代表與DTW作算法效果比較.實(shí)驗(yàn)數(shù)據(jù)來(lái)源于國(guó)家環(huán)保部設(shè)立在浙江省環(huán)保廳的全國(guó)電離輻射測(cè)量監(jiān)測(cè)中心.測(cè)試集是包含4298例環(huán)境電離輻射時(shí)間序列的波峰樣本，它們已經(jīng)被人工標(biāo)注為4類(lèi).序列集的平均長(zhǎng)度為237.94點(diǎn)，根差為96.78，可見(jiàn)數(shù)據(jù)長(zhǎng)度的分布有較大的不均勻性.這原因其一是由于波峰段檢測(cè)提取技術(shù)的限制，造成波峰前后帶有較多或較少的平緩部分；其二是電離輻射劑量波峰本身由于環(huán)境因素如持續(xù)時(shí)長(zhǎng)不一的降水會(huì)導(dǎo)致波峰長(zhǎng)短不一的現(xiàn)象.我們采用層次聚類(lèi)法分別以DTW距離和動(dòng)態(tài)平均距離作內(nèi)置進(jìn)行聚類(lèi)，層次由底層向上層演進(jìn)，聚類(lèi)循環(huán)的停機(jī)閾值為類(lèi)數(shù)4.

圖14 序列聚類(lèi)算法的計(jì)數(shù)統(tǒng)計(jì)矩陣

如圖14(a)所示DTW距離內(nèi)置的聚類(lèi)結(jié)果統(tǒng)計(jì)，計(jì)數(shù)矩陣的非對(duì)角元數(shù)目較大，這表示算法的漏檢率、虛警率都較高；而圖14(b)顯示動(dòng)態(tài)平均距離作內(nèi)置的層次聚類(lèi)執(zhí)行效果較好，計(jì)數(shù)矩陣的非對(duì)角元數(shù)目較小.由表2統(tǒng)計(jì)DTW距離的平均F值僅為61.1%，而動(dòng)態(tài)平均距離可達(dá)到的平均F值為96.9%，平均F值比前者竟高達(dá)35.8%.通過(guò)對(duì)于4298例已標(biāo)注數(shù)據(jù)的算法測(cè)試，相對(duì)于DTW距離，就平均F值來(lái)說(shuō)動(dòng)態(tài)平均距離對(duì)算法性能的提升在35個(gè)百分點(diǎn)以上.

表2 對(duì)4298例序列進(jìn)行層次聚類(lèi)的定量分析

Table 2 Quantity analysis based on hierarchy clustering for 4298 samples

DTW距離類(lèi)別1類(lèi)別2類(lèi)別3類(lèi)別4動(dòng)態(tài)平均距離類(lèi)別1類(lèi)別2類(lèi)別3類(lèi)別4召回率100%47.5%46.2%54.6%100%96.1%95.8%95.8%正確率58.5%51.3%55.9%100%96.2%95.9%95.5%100%F值73.8%49.3%50.6%70.6%98.1%96.0%95.6% 97.9%

另使用6182例4類(lèi)別波峰段的標(biāo)注數(shù)據(jù)集進(jìn)行kNN最近鄰法分類(lèi)測(cè)試，該數(shù)據(jù)集段長(zhǎng)平均為180.7、根差為168.9.且與前面4298例數(shù)據(jù)集不同的是每條測(cè)試數(shù)據(jù)均含有外點(diǎn)成份，如圖15所示.電離輻射檢測(cè)儀器故障自動(dòng)重啟、分布式監(jiān)測(cè)網(wǎng)絡(luò)數(shù)據(jù)傳輸中斷等設(shè)備異常會(huì)造成電離輻射時(shí)間序列夾雜一定的隨機(jī)外點(diǎn)或噪聲.作為kNN法模板庫(kù)的樣本采用當(dāng)前全部被測(cè)數(shù)據(jù)集合之外的波峰段、且經(jīng)人工挑選而一律不含隨機(jī)外點(diǎn)成份.

圖15 6182例4種含外點(diǎn)的波峰段類(lèi)型示例，其中3個(gè)外點(diǎn)是突降型，另外一個(gè)突升型

從表3看出在6182例數(shù)據(jù)集所含具有較懸殊的信號(hào)長(zhǎng)度差別的動(dòng)態(tài)特性下，將DTW距離和動(dòng)態(tài)平均距離用于kNN模式分類(lèi)時(shí)，后者的識(shí)別精度顯著地優(yōu)于前者.

表3 對(duì)6182例數(shù)據(jù)集進(jìn)行kNN近鄰法分類(lèi)的定量分析

Table 3 Quantitative analysis of k nearest neighbor classification for 6182-samples set

類(lèi)別DTW距離類(lèi)別1類(lèi)別2類(lèi)別3類(lèi)別4動(dòng)態(tài)平均距離類(lèi)別1類(lèi)別2類(lèi)別3類(lèi)別4F值96.4%94.4%95.3%94.1%99.7%99.8%99.7%99.8%

表4 對(duì)杭州50年降雨數(shù)據(jù)進(jìn)行kNN近鄰法的豐澇旱適分類(lèi)

Table 4 Classification of the drought and waterlogging in the 50-year rainfall data of Hangzhou using the kNN

類(lèi)別DTW距離澇豐適少動(dòng)態(tài)平均距離澇豐適少F值98.6%99.2%97.8%96.4%99.8%99.4%99.6%99.2%

電離輻射波峰跟降雨及降雨持續(xù)時(shí)間有關(guān)，另考慮杭州近50年各年份日降雨量序列數(shù)據(jù)集，對(duì)部分整月數(shù)據(jù)進(jìn)行雨澇、豐水、適中和少雨等四個(gè)類(lèi)型標(biāo)注，并對(duì)其余整月數(shù)據(jù)進(jìn)行kNN近鄰法分類(lèi)，然后對(duì)分類(lèi)結(jié)果進(jìn)行人工核驗(yàn)，所得F值分析為表4，顯然動(dòng)態(tài)平均距離內(nèi)置的分類(lèi)器更優(yōu).

6 總 結(jié)

數(shù)據(jù)序列的比對(duì)是模式聚類(lèi)和識(shí)別的基礎(chǔ)，而遍歷數(shù)據(jù)的方式又是序列比對(duì)的基礎(chǔ).以DTW距離為代表的數(shù)據(jù)動(dòng)態(tài)對(duì)齊方式是一類(lèi)行之有效的數(shù)據(jù)遍歷方式，它突破了傳統(tǒng)靜態(tài)距離計(jì)算的局限，不僅能適應(yīng)時(shí)長(zhǎng)不一致的序列比對(duì)，更能捕捉到數(shù)據(jù)時(shí)長(zhǎng)伸縮的差異.如何將動(dòng)態(tài)比對(duì)下的距離計(jì)算拓展到非一般距離，如平均距離、Pearson相關(guān)系數(shù)、和Tanimoto相似系數(shù)等，是一個(gè)有趣而實(shí)用的課題.我們的研究工作圍繞著距離形式失去累計(jì)可加性時(shí)，如何使用類(lèi)似DTW算法的結(jié)構(gòu)去計(jì)算動(dòng)態(tài)平均距離、動(dòng)態(tài)Pearson系數(shù)和動(dòng)態(tài)Tanimoto系數(shù)，提出了始發(fā)保優(yōu)的概念，并將其施行于算法的設(shè)計(jì)，創(chuàng)建了一系列的序列比對(duì)方法.并以算法復(fù)雜度最低的動(dòng)態(tài)平均距離作代表進(jìn)行大量標(biāo)注數(shù)據(jù)集的層次聚類(lèi)測(cè)試，算法執(zhí)行效果較DTW內(nèi)置的聚類(lèi)法整體性能提升了35個(gè)百分點(diǎn)以上.且在使用kNN進(jìn)行序列匹配分類(lèi)測(cè)試時(shí)內(nèi)置動(dòng)態(tài)平均距離較DTW距離仍能取得更高的精度.將來(lái)如何將動(dòng)態(tài)平均距離內(nèi)置到k均值聚類(lèi)是一個(gè)更值得期待的工作.文獻(xiàn)[4,5]使用類(lèi)似最大期望法進(jìn)行基于DTW距離的k均值聚類(lèi)中心的生成，這個(gè)方法同樣適用于基于動(dòng)態(tài)平均距離的k均值聚類(lèi).我們計(jì)劃實(shí)現(xiàn)這種聚類(lèi)方法，并且基于動(dòng)態(tài)平均距離比DTW距離更吻合“距離大小決定相異程度”的原則，從而期待證明動(dòng)態(tài)平均距離在無(wú)監(jiān)督聚類(lèi)上比DTW距離具有更優(yōu)越的表現(xiàn).