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

发布时间：2017-07-15 23:18

  本文关键词：基于DTW距离的时间序列相似性查询和shapelets分类算法研究

  更多相关文章： 时间序列 相似性查询 分类 动态时间弯曲距离 滑动窗口分段表示 高效子序列匹配

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

• 摘要3-5
• ABSTRACT5-10
• 第一章 绪论10-16
• 1.1 研究背景与意义10-11
• 1.2 时间序列研究现状11-14
• 1.2.1 相似性查询11-13
• 1.2.2 时间序列分类13-14
• 1.3 本文工作及章节安排14-16
• 第二章 时间序列与相关算法16-28
• 2.1 时间序列及相关定义16-18
• 2.2 时间序列表示方法18-20
• 2.2.1 非数据自适应方法19
• 2.2.2 数据自适应方法19-20
• 2.2.3 基于模型的方法20
• 2.3 时间序列相似性度量20-25
• 2.3.1 基于形状的度量21-22
• 2.3.2 基于编辑的度量22-23
• 2.3.3 基于特征的度量23-24
• 2.3.4 基于模型的度量24-25
• 2.4 时间序列应用25-27
• 2.4.1 时间序列相似性查询的应用25-26
• 2.4.2 时间序列分类的应用26-27
• 2.5 本章总结27-28
• 第三章 基于滑动窗口分段的动态时间弯曲下界算法28-40
• 3.1 动态时间弯曲距离算法28-30
• 3.2 时间序列距离计算中的下界过滤算法30-32
• 3.3 基于滑动窗口分段的动态时间弯曲下界算法32-35
• 3.3.1 PAA与SW时间序列表示法32-33
• 3.3.2 早弃策略33
• 3.3.3 基于LB_SW算法的相似性查询33-35
• 3.4 实验验证与结果分析35-38
• 3.4.1 实验平台和数据35
• 3.4.2 实验结果及分析35-38
• 3.5 本章总结38-40
• 第四章 基于高效子序列匹配的shapelets分类算法40-52
• 4.1 数据转化与shapelets提取40-42
• 4.1.1 图形转化时间序列40-41
• 4.1.2 最优shapelets的提取41-42
• 4.2 高效子序列匹配算法42-43
• 4.3 基于高效子序列匹配的shapelets分类算法43-46
• 4.4 实验验证与结果分析46-51
• 4.4.1 实验平台和数据46-47
• 4.4.2 实验结果及分析47-51
• 4.5 本章总结51-52
• 第五章 总结与展望52-54
• 5.1 本文工作总结52-53
• 5.2 未来工作展望53-54
• 参考文献54-58
• 致谢58-60
• 作者简历及攻读硕士学位期间发表的学术论文60

【相似文献】

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

1 刘芬;郭躬德;;基于符号化聚合近似的时间序列相似性复合度量方法[J];计算机应用;2013年01期

2 尹洪胜;刘秀荣;钱建生;华钢;;时间序列相似性定义延拓[J];计算机工程与应用;2008年25期

3 王国仁;葛健;徐恒宇;郑若石;;基于二分频率变换的序列相似性查询处理技术[J];软件学报;2006年02期

4 蒋嵘;基于形态表示的时间序列相似性搜索[J];计算机研究与发展;2000年05期

5 吴绍春;吴耿锋;王炜;蔚赵春;;寻找地震相关地区的时间序列相似性匹配算法[J];软件学报;2006年02期

6 戴东波;熊峗;朱扬勇;;基于参考集索引的高效序列相似性查找算法[J];软件学报;2010年04期

7 魏莲;变换域时间序列相似性搜索[J];河北理工学院学报;2004年04期

8 朱天;白似雪;;基于模式距离度量的时间序列相似性搜索[J];微计算机信息;2007年30期

9 毛云建;杜秀华;;基于形态特征的时间序列相似性搜索算法[J];计算机仿真;2008年01期

10 刘培华;王立宏;;一种改进的事件序列相似性计算公式[J];计算机工程与应用;2009年07期

中国重要会议论文全文数据库 前3条

1 卓明;王丽珍;谭旭;;基于时间序列相似性搜索的预测算法[A];第十九届全国数据库学术会议论文集（技术报告篇）[C];2002年

2 邱均平;王菲菲;;时间序列相似性查询与索引方法研究[A];2009年中国索引学会年会暨学术研讨会论文集[C];2009年

3 李凤敏;李前忠;张俊萍;;基于离散增量和协变判别式识别小鼠蛋白质亚细胞定位[A];第十一次中国生物物理学术大会暨第九届全国会员代表大会摘要集[C];2009年

中国博士学位论文全文数据库 前1条

1 李俊奎;时间序列相似性问题研究[D];华中科技大学;2008年

中国硕士学位论文全文数据库 前10条

1 左芳;十二株放线菌系统发育的研究[D];河北大学;2007年

2 孙宏伟;基于DTW距离的时间序列相似性查询和shapelets分类算法研究[D];太原理工大学;2016年

3 涂俐兰;基于快速沃尔什变换的生物序列相似性比对[D];华中科技大学;2004年

4 陈伟;生物信息学中的序列相似性比对算法[D];中国海洋大学;2006年

5 李明亮;时间序列相似性聚类算法研究[D];湖南大学;2010年

6 王克龙;离散小波变换分析蛋白质序列相似性[D];四川大学;2004年

7 刘芳;基于信息离散度的DNA序列相似性分析研究[D];湖南大学;2009年

8 孙达辰;基于DTW的时间序列相似性搜索的研究[D];大庆石油学院;2010年

9 杜洪波;时间序列相似性查询及异常检测算法的研究[D];沈阳工业大学;2008年

10 朱天;关于时间序列相似性及时序规则发现的研究[D];南昌大学;2007年

，

本文编号：546233