基于时间加权改进的LDTW算法

Improved LDTW algorithm based on time-weighting

在时间序列相似性度量研究中,动态时间弯曲(dynamic time warping,DTW)是最为常用的算法之一,但其存在病态对齐问题且未考虑时间属性影响。限制对齐路径长度DTW(DTW under limited warping path length,LDTW)和时间加权DTW(time-weighed DTW,TDTW)分别尝试解决上述两个问题中的一个,但未能同时解决DTW两方面的不足。为此提出一种综合时间权重的LDTW(time-weighting LDTW,TLDTW)算法。首先通过测量两个时间序列中时间点对的距离构建时间权值矩阵;然后在LDTW累计成本矩阵递归填充过程中融合对应的时间权值,以实现在考虑时间因素影响的同时保留有效抑制病态对齐特性。基于UCR数据集进行1-NN分类实验,实验结果显示基于TLDTW相似度量的分类准确率优于其他对比算法,且进一步对比验证了其可靠性。

DTW is one of the commonly used algorithms in time series similarity measurement.However,DTW has the shortcoming of pathological alignment and ignores the influence of time attribute.LDTW and TDTW have been proposed to handle two shortcomings of DTW separately,however they cannot be solved simultaneously by LDTW or TDTW independently.This paper proposed TLDTW algorithm.Firstly,it constructed time weight matrix by measuring the distance between points in two series.Secondly,it fused the corresponding time weights from time weight matrix into the recursive filling procedure for cumulative cost matrix of LDTW,thus it considered the time attribute and the problem of pathological alignment could still be suppressed.It conducted 1-NN classification experiment based on UCR dataset,and experimental results show that the classification accuracy based on TLDTW is better than other compared algorithms,and the reliability of TLDTW is verified by further comparison.