基于DTW距离的相似性查询和shapelets分类算法研究

摘要

随着时间序列挖掘相关技术的不断发展，如何权衡算法效率与准确性成为研究人员关注的焦点。由于时间序列的高维性和复杂性特点，通常难以既高效又准确地对时间序列进行分析和处理。因此在不丢失关键信息的前提下，对时间序列进行适当的降维处理，降低算法中对数据维度依赖性极大的运算复杂度，以获得高效与准确两者的平衡有一定的理论意义和应用价值。
　　本文分析了时间序列挖掘算法的特点，重点对相似性查询和分类的关键技术进行了研究，分析比对了经典算法以及其存在的问题，提出基于滑动窗口分段的下界距离算法和基于高效子序列匹配的shapelets转化分类算法，从理论和实际数据两方面证明了改进算法的可行性和有效性。主要工作如下：
　　（1）时间序列基础算法分析。针对时间序列挖掘中的表示方法和距离度量方法进行了总结与分析，列举相应的经典算法进行详细说明，并对其进行比较。介绍并分析了时间序列相似性查询与分类的研究目的、算法原理、实际应用等相关内容。
　　（2）提出基于滑动窗口分段的下界距离算法。下界距离算法在提高时间序列相似性查询效率、减少冗余计算等方面起非常重要的作用，现有的基于点对累积近似表示法的下界算法，相似度计算的时间代价较小，但当时间序列振幅波动较大时，往往不能紧致地拟合时间序列。针对这一问题，在下界算法中引入滑动窗口分段表示法，提出一种基于滑动窗口分段的动态时间弯曲下界算法，构建拟合度更高的上下边界曲线，对时间序列进行过滤，筛除相似性较差的时间序列。该算法能够有效地简化时间序列相似度的计算过程，降低运算复杂度，提高相似性查询效率，且当时间序列的振幅波动较大时，取得较高计算精度与效率。
　　（3）提出基于高效子序列匹配的shapelets转化分类算法。由于大量复杂的距离计算，使得整个分类过程效率非常低，会耗费大量时间，现有的优化算法都无法彻底解决这个问题。针对这一问题，在shapelets分类算法中引入点对累积近似表示法和一种高效子序列匹配算法，提出一种基于高效子序列匹配的shapelets转化分类算法，先用点对累积近似表示法对数据进行适当的降维处理，之后用子序列匹配算法简化分类过程。高效子序列匹配算法可以与shapelets分类算法有效地结合，能够在保证较高分类准确度的同时，较好的简化算法计算过程，提高分类效率。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景与意义

1.2 时间序列研究现状

1.3 本文工作及章节安排

第二章 时间序列与相关算法

2.1 时间序列及相关定义

2.2 时间序列表示方法

2.3 时间序列相似性度量

2.4 时间序列应用

2.5 本章总结

第三章 基于滑动窗口分段的动态时间弯曲下界算法

3.1 动态时间弯曲距离算法

3.2 时间序列距离计算中的下界过滤算法

3.3 基于滑动窗口分段的动态时间弯曲下界算法

3.4 实验验证与结果分析

3.5 本章总结

第四章 基于高效子序列匹配的shapelets分类算法

4.1 数据转化与shapelets提取

4.2 高效子序列匹配算法

4.3 基于高效子序列匹配的shapelets分类算法

4.4 实验验证与结果分析

4.5 本章总结

第五章 总结与展望

5.1本文工作总结

5.2未来工作展望

参考文献

致谢

作者简历及攻读硕士学位期间发表的学术论文