基于提前终止的加速时间序列弯曲算法

计算机应用 ›› 2010, Vol. 30 ›› Issue (4): 1068-1071.

基于提前终止的加速时间序列弯曲算法

陈胜利¹,李俊奎²,刘小东²

1. 西安财经学院信息学院
2.

收稿日期:2009-08-26 修回日期:2009-11-09 发布日期:2010-04-15 出版日期:2010-04-01
通讯作者: 陈胜利
基金资助:
国家发展与改革委员会“安全智能数据整合平台开发及产业化”项目

Early abandon to accelerating exactly warping matching of time series

Received:2009-08-26 Revised:2009-11-09 Online:2010-04-15 Published:2010-04-01

摘要/Abstract

摘要： 动态时间弯曲(DTW)距离是时间序列相似搜索的一种重要距离度量，但其精确计算是一个性能瓶颈。针对此问题，提出一种名为EA_DTW的方法用于加速DTW距离的精确计算，该方法在计算累积距离矩阵中每个方格的距离时都判断其是否超过阈值，一旦超过则提前终止其余相关方格的距离计算;并对EA_DTW的过程进行了理论分析。实验对比表明，EA_DTW能够提高DTW的计算效率，在阈值与DTW距离相比较小时更加明显。

关键词: 时间序列, 相似搜索, 动态弯曲距离, 提前终止

Abstract: Dynamic Time Warping (DTW) is one of the important distance measures in similarity searching of time series; however, the exact calculation has become a bottleneck. An approach named EA_DTW was proposed. The method checked if value of the cell in cumulative distance matrix exceeded the threshold and if so, it would terminate the calculation of other related cells. The theoretical analysis on the process of EA_DTW was made. The empirical experimental results show that EA_DTW outperforms the dynamic DTW calculation in terms of calculation time, and is much better when the threshold is below the real DTW distance.

Key words: time series, similarity search, Dynamic Time Warping (DTW), early abandon

陈胜利李俊奎刘小东. 基于提前终止的加速时间序列弯曲算法[J]. 计算机应用, 2010, 30(4): 1068-1071.

[1]	李洋莹, 陈智军, 张子豪, 游兰. 基于改进Elman神经网络的制糖企业原糖需求预测模型[J]. 计算机应用, 2021, 41(7): 2113-2120.
[2]	李国荣, 冶继民, 甄远婷. 基于新的鲁棒相似性度量的时间序列聚类[J]. 计算机应用, 2021, 41(5): 1343-1347.
[3]	张凌哲, 黄向东, 乔嘉林, 勾王敏浩, 王建民. 面向时序数据的两阶段日志结构合并树文件合并框架[J]. 计算机应用, 2021, 41(3): 618-622.
[4]	曹阳, 闫秋艳, 吴鑫. 不平衡时间序列集成分类算法[J]. 计算机应用, 2021, 41(3): 651-656.
[5]	马停停, 冀天娇, 杨冠羽, 陈阳, 许文波, 刘宏图. 基于长短时记忆神经网络的手足口病发病趋势预测[J]. 计算机应用, 2021, 41(1): 265-269.
[6]	钱斌, 郑楷洪, 陈子鹏, 肖勇, 李森, 叶纯壮, 马千里. 基于残差连接长短期记忆网络的时间序列修复模型[J]. 计算机应用, 2021, 41(1): 243-248.
[7]	肖勇, 郑楷洪, 郑镇境, 钱斌, 李森, 马千里. 基于多尺度跳跃深度长短期记忆网络的短期多变量负荷预测[J]. 计算机应用, 2021, 41(1): 231-236.
[8]	高世乐, 王滢, 李海林, 万校基. 基于矩阵画像的金融时序数据预测方法[J]. 计算机应用, 2021, 41(1): 199-207.
[9]	郭秀婷, 朱昶胜, 张生财, 赵奎鹏. 分形插值在风速时间序列中的应用[J]. 计算机应用, 2020, 40(9): 2628-2633.
[10]	胡珉, 白雪, 徐伟, 吴秉键. 多维时间序列异常检测算法综述[J]. 计算机应用, 2020, 40(6): 1553-1564.
[11]	霍纬纲, 王慧芳. 基于自编码器和隐马尔可夫模型的时间序列异常检测方法[J]. 计算机应用, 2020, 40(5): 1329-1334.
[12]	姜逸凡, 叶青. 基于孪生神经网络的时间序列相似性度量[J]. 计算机应用, 2019, 39(4): 1041-1045.
[13]	王金策, 邓越萍, 史明, 周云飞. 多时间尺度时间序列趋势预测[J]. 计算机应用, 2019, 39(4): 1046-1052.
[14]	周翔宇, 程勇, 王军. 基于改进深度信念网络的农业温室温度预测方法[J]. 计算机应用, 2019, 39(4): 1053-1058.
[15]	朱跃龙, 朱晓晓, 王继民. 基于子序列全连接和最大团的时间序列模体发现算法[J]. 计算机应用, 2019, 39(2): 414-420.