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

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

【文章頁數(shù)】：7 頁

【圖文】：

準(zhǔn)確率測試

tion[J].RemoteSensingofEnvironment，2015，158：478-491.[6]LohrerJ，LienkampM.BuildingrepresentativevelocityprofilesusingFastDTWandspectralclustering[C]//Inter-nationalConferenceonITSTelecommunications，2016：45-49.計(jì)算開銷時(shí)間消耗/s空間占用/MBDTW1.2×1047.6×104IPBand8.7×1035.4×104SCBand5.3×1033.3×104ADTW11.917.5表3ADTW與DTW、全局約束算法計(jì)算開銷對比12345678910序列長度/1052001000內(nèi)存占用/MBADTWFastDTW(r=10)圖5ADTW與FastDTW空間占用測試12345678910序列長度/105100500時(shí)間消耗/sADTWFastDTW(r=10)圖6ADTW與FastDTW時(shí)間消耗測試（下轉(zhuǎn)第71頁）范純龍，等：基于自適應(yīng)搜索窗口的序列相似比對算法59

rofilesusingFastDTWandspectralclustering[C]//Inter-nationalConferenceonITSTelecommunications，2016：45-49.計(jì)算開銷時(shí)間消耗/s空間占用/MBDTW1.2×1047.6×104IPBand8.7×1035.4×104SCBand5.3×1033.3×104ADTW11.917.5表3ADTW與DTW、全局約束算法計(jì)算開銷對比12345678910序列長度/1052001000內(nèi)存占用/MBADTWFastDTW(r=10)圖5ADTW與FastDTW空間占用測試12345678910序列長度/105100500時(shí)間消耗/sADTWFastDTW(r=10)圖6ADTW與FastDTW時(shí)間消耗測試（下轉(zhuǎn)第71頁）范純龍，等：基于自適應(yīng)搜索窗口的序列相似比對算法59

【參考文獻(xiàn)】：
期刊論文
[1]PSO優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的混沌時(shí)間序列預(yù)測[J]. 盧輝斌,李丹丹,孫海艷.  計(jì)算機(jī)工程與應(yīng)用. 2015(02)



本文編號：2999162