Similarity Algorithm Based on Three Way Decision of Time Warping Distance

DOI：10.11896/j.issn.1002-137X.2017.09.007

 作者 单位 E-mail 徐健锋 同济大学计算机科学与技术系 上海201804南昌大学软件学院 南昌330047 940jianfeng_x@tongji.edu.cn 何宇凡 南昌大学软件学院 南昌330047 张远健 同济大学计算机科学与技术系 上海201804 汤涛 南昌大学软件学院 南昌330047

动态时间弯曲距离算法(DTW)是目前公认的最有效的时间序列相似性计算方法之一,但是较高的时间复杂度一直是其主要缺点。快速弯曲距离算法(FTW)能有效提高DTW的计算速度,但是该算法对不同粒度时间序列剪枝的行为是典型的二支决策,与人类处理不确定问题时普遍采用的三支判断不同。因此,通过将三支决策理论引入到DTW算法的优化工作中,建立了DTW三支决策模型；然后对DTW三支决策模型中的决策阈值α和β进行了基于误识别率的推导,并且给出了具体求解阈值α和β的模拟退火算法；最后基于上述理论提出了基于弯曲距离三支决策的时序相似性算法(3WD-DTW)。通过对比实验表明,与FTW算法相比,3WD-DTW算法在保持较快的计算速度的前提下明显提升了计算准确度,使其接近DTW的水平。

Dynamic time warping (DTW) is widely accepted as one of the most effective methods for the similarity measurement of time series,but suffers from high time complexity.Fast search method for dynamic time wrapping (FTW) is demonstrated to accelerate DTW.The core of pruning is however a typical two-way decision rather than three-way decision,which is different from actions taken with uncertain issues.By incorporating three-way decision,an optimized DTW model three-way decision DTW (3WD-DTW) is developed first.The decision thresholds α,β are derived by solving an optimization problem with the objective of minimizing error rate.A novel simulated annealing algorithm is thus proposed.Finally,similarity algorithm based on three way decision of time warping distance is presented.Experiments show that 3WD-DTW is comparable in computing complexity as compared to FTW.In terms of accuracy,3WD-DTW outperforms FTW significantly and approximates to DTW.