徐健锋,何宇凡,张远健,汤涛.基于弯曲距离三支决策的时序相似性算法[J].计算机科学,2017,44(9):40-44, 61
基于弯曲距离三支决策的时序相似性算法
Similarity Algorithm Based on Three Way Decision of Time Warping Distance
投稿时间:2016-07-27  修订日期:2016-09-07
DOI:10.11896/j.issn.1002-137X.2017.09.007
中文关键词:  三支决策,动态时间弯曲,模拟退火,决策阈值
英文关键词:Three-way decision,Dynamic time warping,Simulated annealing,Decision threshold
基金项目:本文受国家自然科学基金:粒计算中的不确定性分析与研究(61273304),上海市中医药三年行动计划重点项目:中医目诊仪(临床诊疗设备)开发研究(ZY3-CCCX-3-6002)资助
作者单位E-mail
徐健锋 同济大学计算机科学与技术系 上海201804;南昌大学软件学院 南昌330047 940jianfeng_x@tongji.edu.cn 
何宇凡 南昌大学软件学院 南昌330047  
张远健 同济大学计算机科学与技术系 上海201804  
汤涛 南昌大学软件学院 南昌330047  
摘要点击次数: 209
全文下载次数: 136
中文摘要:
      动态时间弯曲距离算法(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.
查看全文  查看/发表评论  下载PDF阅读器