摘要
DTW(Dynamic Time Warping)算法被广泛应用于序列数据比对,以度量序列间距离,但算法较高的时间复杂度限制了其在长序列比对上的应用。提出基于自适应搜索窗口的序列相似比对算法(ADTW),算法利用分段聚集平均(Piecewise Aggregate Approximation,PAA)策略进行序列抽样得到低精度序列,然后计算低精度序列下的比对路径,并根据低精度距离矩阵上的梯度变化预测路径偏差,限制路径搜索窗口的拓展范围;随后算法逐步提高序列精度,并在搜索窗口内修正路径、计算新的搜索窗口,最终,实现DTW距离和相似比对路径的快速求解。对比FastDTW,ADTW算法在同等度量准确率下提高计算效率约20%,其时间复杂度为O(n)。
DTW(Dynamic Time Warping)has been widely used in series data alignment to measure the distance between series, but the high time complexity limits its application in long series alignment. This paper proposes a similarity alignment algorithm for series based on adaptive search window(ADTW). The algorithm uses Piecewise Aggregate Approximation(PAA)strategy to obtain low-precision series, then computes the alignment path under low-precision series and predicts the path deviation according to the gradient variation on the low-precision distance matrix, limits the scope of the path search window. Then it improves the series accuracy gradually, modifies the path in the search window and calculates a new search window. Finally, it realizes fast solutions of DTW distances and warping path. Compared with FastDTW, the ADTW algorithm can improve the computational efficiency by about 20% with the same measurement precision and the time complexity is O(n).
作者
范纯龙
崔宇斌
滕一平
FAN Chunlong;CUI Yubin;TENG Yiping(College of Computer Science,Shenyang Aerospace University,Shenyang 110136,China)
出处
《计算机工程与应用》
CSCD
北大核心
2019年第2期54-59,71,共7页
Computer Engineering and Applications
基金
国家自然科学基金(No.61303016)
