长度分布悬殊的序列比对法

摘要

经典的动态时间规整算法（Dynamic Time Warping,DTW）对长度相差剧烈的两个序列之间的相异（似）性度量会引入长度的影响,这种影响在多对序列之间匹配时造成度量数值上的失衡从而导致DTW度量相似性的失效.该文分析了这种失效性的来源,提出祛除长度差异影响的均值DTW法.和传统DTW法相比,均值DTW是其非平凡的推广,因而无法直接使用基于动态规划原理的算法.基于该文给出的动态规划的匹配路径数目计算,强调了枚举法施加于均值DTW的不可行性.在引入均值的累计计算技巧后,将均值DTW纳入传统的基于动态规划原理的算法框架,实现了等价于DTW计算复杂性、双倍于DTW存储占用的均值DTW算法.该算法相比于DTW在电离辐射时间序列的聚类实验中将算法结果的精度指标至少提升了50%以上.该文的创新性在于:1)首次发现了DTW可能失效的长度差异因素; 2)提出了均值DTW的概念; 3)首次提出了动态路径数目的定量计算方法; 4)给出均值DTW的加窗限制版本.