基于滑动窗口分段的动态时间弯曲下界算法  

Lower Bound Algorithm of Dynamic Time Warping Based on Sliding Window Fragment

作　　者：孙宏伟[1] 王会青[1] 张建辉[1] 

机构地区：[1]太原理工大学计算机科学与技术学院,太原030024

出　　处：《小型微型计算机系统》2016年第4期768-772,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61373101;61402318)资助;博士点基金项目(20131402120009)资助;山西省科技攻关项目(20130313012-2)资助;校青年团队项目(2013T049)资助

摘　　要：下界算法可以简化时间序列相似性查询的计算过程.现有的基于点对累积近似表示法的下界算法,相似度计算的时间代价较小,但当时间序列振幅波动较大时,往往不能紧致地拟合时间序列.针对这一问题,在下界算法中引入滑动窗口分段表示法,提出一种基于滑动窗口分段的动态时间弯曲下界算法,构建拟合度更高的上下边界曲线,对时间序列进行过滤,筛除相似性较差的时间序列.实验结果表明,该算法能够有效地简化时间序列相似度的计算过程,降低时间复杂度,提高相似性查询效率,且当时间序列的振幅波动较大时,相似度计算的紧致度和修剪率更高.Lower bound algorithm can simplify the calculation process of time series＇ similarity searching.Existing lower bound algorithm based on piecewise aggregate approximation fragment notation,which can calculate similarity degree at lowcost,but when the variation of time series＇ amplitude turns larger,it cannot fit the time series tightly.Aiming at the problem,the sliding windowfragment notation is introduced into lower bound algorithm,and a lower bound algorithm of dynamic time warping based on sliding windowfragment is proposed,to build upper and lower boundary curve with higher degree of fitting,filter the time series and screen out the time series with lowsimilarity.The algorithm is proved to be effective to simplify the calculation process of time series＇ similarity by the results,to reduces the time complexity and improve the efficiency of similarity searching,and when the variation of time series＇ amplitude turns larger,it has higher tightness and pruning power to calculate similarity degree.

关 键 词：动态时间弯曲距离 下界距离 点对累积近似 滑动窗口分段 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]