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

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

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

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

【圖文】：

準(zhǔn)確率測(cè)試

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

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

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



本文編號(hào)：2999162