發(fā)布時間：2021-01-25 11:44

　　DTW（Dynamic Time Warping）算法被廣泛應用于序列數(shù)據(jù)比對,以度量序列間距離,但算法較高的時間復雜度限制了其在長序列比對上的應用。提出基于自適應搜索窗口的序列相似比對算法（ADTW）,算法利用分段聚集平均（Piecewise Aggregate Approximation,PAA）策略進行序列抽樣得到低精度序列,然后計算低精度序列下的比對路徑,并根據(jù)低精度距離矩陣上的梯度變化預測路徑偏差,限制路徑搜索窗口的拓展范圍;隨后算法逐步提高序列精度,并在搜索窗口內修正路徑、計算新的搜索窗口,最終,實現(xiàn)DTW距離和相似比對路徑的快速求解。對比FastDTW,ADTW算法在同等度量準確率下提高計算效率約20%,其時間復雜度為O（n）。 

【文章來源】：計算機工程與應用. 2019,55(02)北大核心

【文章頁數(shù)】：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優(yōu)化BP神經(jīng)網(wǎng)絡的混沌時間序列預測[J]. 盧輝斌,李丹丹,孫海艷.  計算機工程與應用. 2015(02)



本文編號：2999162