基于自适应搜索窗口的序列相似比对算法

发布时间：2021-01-25 11:44

　　DTW（Dynamic Time Warping）算法被广泛应用于序列数据比对,以度量序列间距离,但算法较高的时间复杂度限制了其在长序列比对上的应用。提出基于自适应搜索窗口的序列相似比对算法（ADTW）,算法利用分段聚集平均（Piecewise Aggregate Approximation,PAA）策略进行序列抽样得到低精度序列,然后计算低精度序列下的比对路径,并根据低精度距离矩阵上的梯度变化预测路径偏差,限制路径搜索窗口的拓展范围;随后算法逐步提高序列精度,并在搜索窗口内修正路径、计算新的搜索窗口,最终,实现DTW距离和相似比对路径的快速求解。对比FastDTW,ADTW算法在同等度量准确率下提高计算效率约20%,其时间复杂度为O（n）。 

【文章来源】：计算机工程与应用. 2019,55(02)北大核心

【文章页数】：7 页

【图文】：

准确率测试

tion[J].RemoteSensingofEnvironment，2015，158：478-491.[6]LohrerJ，LienkampM.BuildingrepresentativevelocityprofilesusingFastDTWandspectralclustering[C]//Inter-nationalConferenceonITSTelecommunications，2016：45-49.计算开销时间消耗/s空间占用/MBDTW1.2×1047.6×104IPBand8.7×1035.4×104SCBand5.3×1033.3×104ADTW11.917.5表3ADTW与DTW、全局约束算法计算开销对比12345678910序列长度/1052001000内存占用/MBADTWFastDTW(r=10)图5ADTW与FastDTW空间占用测试12345678910序列长度/105100500时间消耗/sADTWFastDTW(r=10)图6ADTW与FastDTW时间消耗测试（下转第71页）范纯龙，等：基于自适应搜索窗口的序列相似比对算法59

rofilesusingFastDTWandspectralclustering[C]//Inter-nationalConferenceonITSTelecommunications，2016：45-49.计算开销时间消耗/s空间占用/MBDTW1.2×1047.6×104IPBand8.7×1035.4×104SCBand5.3×1033.3×104ADTW11.917.5表3ADTW与DTW、全局约束算法计算开销对比12345678910序列长度/1052001000内存占用/MBADTWFastDTW(r=10)图5ADTW与FastDTW空间占用测试12345678910序列长度/105100500时间消耗/sADTWFastDTW(r=10)图6ADTW与FastDTW时间消耗测试（下转第71页）范纯龙，等：基于自适应搜索窗口的序列相似比对算法59

【参考文献】：
期刊论文
[1]PSO优化BP神经网络的混沌时间序列预测[J]. 卢辉斌,李丹丹,孙海艳.  计算机工程与应用. 2015(02)



本文编号：2999162