动态时间规整算法优化

叶科淮，陈 志，王仁杰，史佳成，胡 宸

（1.南京邮电大学 计算机学院、软件学院、网络空间安全学院，江苏南京 210023；2.南京邮电大学 通信与信息工程学院，江苏 南京 210003）

0 引言

时间序列数据在生活中随处可见，时间序列数据本质上反映的是某个或某些随机变量随时间不断变化的趋势。目前时间序列相似性度量常用方法是动态时间归整（Dy⁃namic Time Warping，DTW）算法，文献［1］证明出DTW 算法比欧几里得距离搜索算法更有效率，但该算法时间序列长度较长，两段时间序列长度相当时计算效率较低。本文通过分析现有DTW 算法优化方法，对算法进行扩展和改进。

DTW 基于动态规划（Dynamic Programming，DP）的思想，具有较高的时间复杂度且对噪声敏感，传统DTW 时间复杂度为O（mn），其中m、n 为时间序列长度。DTW 算法有很多变种，如多变量动态时间规整MDTW［2］、测量索引距离的IDTW［3］、可以解决传统DTW 奇异问题的DDTW［4］及WDTW 算法［5］等。

为提高DTW 度量效果，众多学者进行了相关研究。Salvador 等［6］提出的FastDTW 算法在粗粒度空间内执行DTW 算法，将复杂度优化至O（n），该算法在数据量极大的情况下十分有效，但是在求取DTW 距离时会产生较大误差；分块算法可优化效率，如对时间序列进行分块［7］、对动态规划产生的矩阵进行分块［8］等，但是也会带来一定误差；褚蓉等［9］提出一种基于形状与升降性提取序列数据重要特征点的DTW 相似性搜索算法，解决了分块带来的特征丢失问题；文献［10］展示了通过全局变量约束，限制搜索区域可行性；针对全局约束以减少计算时间的方法主要有Sakoe-Chiba 约束［11］与Itakura-Parallelogram 约束［12］；文献［13］根据后者应用情景，将全局约束范围由平行四边形转变为动态平行四边形；……