基于动态规划和DTW匹配的时间序列索引方法研究

发布时间：2017-08-20 15:03

  本文关键词：基于动态规划和DTW匹配的时间序列索引方法研究

  更多相关文章： 时间序列索引 动态时间规整 下界距离 中心时间序列

【摘要】：近些年,时间序列在包括金融、生物等领域得到广泛应用,越来越多的受到学者的关注和研究。在其众多的研究领域中,时间序列的相似性查询问题得到了较为广泛的研究,该问题常常转化为建立时间序列索引问题。尽管动态时间规整(DTW)是用于计算时间序列相似性的强有力工具,但是由于该算法不满足三角不等式,且时间复杂度较高,因此很难直接用于建立时间序列索引。为了解决DTW算法存在的问题,研究者引入了下界(low-bound)算法,并利用下界距离建立时间序列索引。下界距离严格小于等于DTW距离,其与DTW距离的接近程度(tightness)决定了索引的效果。本文对前人在时间序列索引问题上的研究做了综合性的回顾与评述,分析了现有算法的优点和存在的问题,并提出了一个全新的、基于动态规划的时间序列索引技术,建立了一种新型的索引树。算法利用DTW匹配关系对序列产生划分,提出了一种分段的索引结构,并给出了建立索引结构的算法。并根据索引结构的特点,给出了利用动态规划求解待查序列与索引结构的下界距离的方法,最后给出了相似性查询的过程。同时,为了更有效的建立索引,增加分段划分的有效性,提高索引效果,本文还提出了一种新型的计算两条时间序列中心的算法,并利用该算法为DBA算法求解初始解,从而优化了DBA算法求解多条时间序列的中心序列的效果。实验部分证明了本文提出的中心序列算法能够求解得到更有效的中心序列,在规整窗口较大时,本文的索引算法有着更接近DTW距离的下界距离,能够更有效的排除距离较大的序列,其索引效果要好于现有的索引算法。
【关键词】：时间序列索引 动态时间规整 下界距离 中心时间序列
【学位授予单位】：大连理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O211.61
【目录】：

• 摘要4-5
• Abstract5-8
• 1 绪论8-11
• 1.1 时间序列概述8-9
• 1.2 时间序列索引概述9-10
• 1.3 本文工作10
• 1.4 本文结构10-11
• 2 相关工作概述11-26
• 2.1 相似度衡量算法11-15
• 2.1.1 欧氏距离11-12
• 2.1.2 DTW距离12-15
• 2.2 下界距离算法15-21
• 2.2.1 LB_Yi下界距离15-16
• 2.2.2 LB_Kim下界距离16-17
• 2.2.3 LB_Keogh下界距离17-18
• 2.2.4 LB_NKim下界距离18-20
• 2.2.5 LB_NKeogh下界距离20-21
• 2.3 索引算法21-24
• 2.3.1 PAA降维介绍22-23
• 2.3.2 Keogh索引23-24
• 2.4 中心时间序列算法24-26
• 3 求解中心序列26-36
• 3.1 匹配度理论和剪枝定理26-27
• 3.2 两条时间序列的中心序列算法27-30
• 3.3 多条时间序列的中心序列算法30-32
• 3.4 实验验证32-36
• 3.4.1 两条时间序列的中心序列实验32-34
• 3.4.2 多条时间序列的中心序列实验34-36
• 4 索引技术36-45
• 4.1 降维36-38
• 4.2 上下界序列集38
• 4.3 上下界序列集的有效组合集38-41
• 4.4 建立索引树41-45
• 5 查询45-48
• 5.1 索引结构的下界距离45-46
• 5.2 查询过程46-48
• 6 实验48-57
• 6.1 数据集预处理48-49
• 6.2 下界距离与松紧程度49-52
• 6.3 排除序列能力52-53
• 6.4 时间消耗53-55
• 6.5 参数讨论55-56
• 6.6 本章小结56-57
• 结论57-58
• 参考文献58-61
• 攻读硕士学位期间发表学术论文情况61-62
• 致谢62-63

【参考文献】

中国期刊全文数据库 前1条

1 李海林;郭崇慧;;时间序列数据挖掘中特征表示与相似性度量研究综述[J];计算机应用研究;2013年05期

，

本文编号：707265