[發明專利]一種基于最小平均距離的動態時間規整方法

在審

• 申請號: 201710498730.2
• 申請日: 2017-06-27
• 公開（公告）號: CN107451598A
• 公開（公告）日: 2017-12-08
• 發明（設計）人: 陸成剛
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 杭州斯可睿專利事務所有限公司33241
• 代理人: 王利強

技術領域

本發明涉及一種動態時間規整方法。

背景技術

距離是度量兩段時間序列相異(似)性的常用方法。由于序列值在時間軸上分布會有平移、伸縮，從而導致直接的點對點計算會有偏離常識性判斷的風險。例如，對于兩個序列(a,a,b,b,a)和(a,b,b,a,a)模式，在實際應用或工程實踐中需要判斷為一致，但使用距離計算其數值為2|a-b|。使用傳統的動態時間規整算法計算距離所得值為0，這是比較符合實際工程的需要的。但是傳統動態時間規整算法也有弊端，例如，考慮使用動態時間規整距離計算以下三段直流信號的匹配情況：

A＝(0.1,0.1)

B＝(0.25,0.25,0.25,0.25)

C＝(0.28,0.28,0.28)

信號A與B的動態時間規整距離為0.6，動態時間規整路徑的長度為4；而信號C與A的動態時間規整距離0.54，動態時間規整路徑的長度為3。從我們直覺判斷信號B與A比信號C與A更接近，但從動態時間規整距離決定的相異性來看，反而是C比B更接近A。造成這個反直覺的效果是我們僅僅考慮了距離，而忽視了路徑長度，假如以動態時間規整距離相對路徑長度的平均值而言，B比C更接近A。

發明內容

為了克服已有技術動態時間規整方式的誤識率較高的不足,本發明提供了一種誤識率較低的基于最小平均距離的動態時間規整方法。

本發明解決其技術問題所采用的技術方案是：

一種基于最小平均距離的動態時間規整方法，包括以下步驟：

1)對于兩段時間序列

S＝(s₁,s₂,...,s_n)

T＝(t₁,t₂,...,t_m)

創建平均距離矩陣其中是點(1,1)到點(i,j)的最小平均距離，是起點(1,1)到終點(n,m)的平均距離，也是時間序列S和T的基于最小平均距離的最優匹配距離。從起點(1,1)到終點(n,m)的最優匹配路徑P＝(p₁,p₂,......,p_l)，其中p_i＝(q_i,r_i)，而1＜＝q_i＜＝n,1＜＝r_i＜＝m，與傳統動態時間規整算法一樣，滿足如下的條件：

單調性：

q_i-1≤q_i且r_i-1≤r_i

連續性：

q_i-1＝q_i或q_i-1+1＝q_i且r_i-1＝r_i或r_i-1+1＝r_i

邊界條件：

p₁＝(1,1)p_l＝(n,m)

再創建路徑長度矩陣l＝(l(i,j))_n×m，其中l(i,j)點(1,1)到點(i,j)的最小平均距離的路徑長度，自然而l(n,m)＝l為路徑長度矩陣滿足的單調性、連續性、和邊界條件且為S和T的匹配距離(路徑長度平均距離)，它是所有的從起點(1,1)到終點(n,m)的可能的路徑里平均距離最小的；這樣的路徑長度l滿足max(n,m)≤l≤n+m-1，任意的路徑數目的一個下界值為：

num(P)＞2·3^min(m，n)-3；

2)求的動態規劃的過程如下：

2.1)初始化

2.2)對平均距離矩陣進行首行首列的賦值，首行取與其同行前列的近鄰進行加權組合計算算術平均，首列取與其同列前行的近鄰進行加權組合計算算術平均；

2.3)對平均距離矩陣進行非首行、非首列的賦值，先將當前點取與其前行前列的三鄰點分別進行組合并計算算術平均，在得到的三個平均值中選取最小的那個，作為當前點的平均距離值；并將當前點的路徑長度值在被選中的那個鄰點的長度值基礎上增加1；

2.4)輸出和l(n,m)。