时间序列挖掘中索引与查询技术的研究

论文摘要

索引和查询是数据挖掘中各项任务的基础和关键问题。本文对时间序列挖掘中的索引和查询技术进行了研究,比较系统地研究了时间序列的查询方式、表示与索引和相似性度量等问题;提出了计算几何应用到时间序列挖掘的方法,实现了时间序列全序列匹配查询、模式查询、反向查询和异常检测,查询效率和准确性都有了比较大的提高。主要研究成果如下:1.时间序列查询方式利用计算几何中邻近问题的原理和方法,根据时间序列的构成要素,对时间序列的查询方式进行了系统地分类。按查询对象将时间序列查询分为点查询、模式查询和序列查询;按查询方式将时间序列查询分为范围查询、邻近查询和点对查询,拓宽了时间序列查询的方式,为序列挖掘提供了更加有力的工具。2.时间序列表示与索引在基于重要点分段的基础上,主要研究了时间序列的KL表示方法。利用Voronoi图对数据进行组织和管理,为时间序列查询提供了一种新的索引方法。同时,针对时间序列原始数据的反向查询,提出了一种新的时间序列索引方法—IC-索引。3.时间序列相似性查询系统地研究了时间序列各种查询方式的实现算法。提出了KL相似性度量,实现了全序列匹配查询;利用计算几何方法,实现了线性模式的邻近查询、最近模式对查询和最远模式对查询,算法在时间上都是最优的;提出了一种新的时间序列反向查询方法,查询效率和准确性都有比较大的提高。4.时间序列异常检测利用Voronoi图的基本原理,提出了一种基于密度的异常检测方法VOD,并应用到时间序列的线性模式异常检测,将现有算法的复杂性从O（n2）降低到O（nlogn）,检测效率和性能都有了很大的提高。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景和意义
• 1.1.1 数据挖掘概述
• 1.1.2 复杂类型数据挖掘问题
• 1.1.3 时间序列挖掘中的关键问题
• 1.2 国内外研究现状
• 1.2.1 传统的时间序列分析方法
• 1.2.2 时间序列的索引与查询
• 1.3 本文研究的主要内容与创新
• 1.3.1 主要研究内容与创新
• 1.3.2 研究方法
• 1.3.3 论文结构
• 第二章 时间序列查询概述
• 2.1 时间序列的概念
• 2.2 时间序列查询的分类
• 2.3 时间序列查询的方式
• 2.4 时间序列查询的Voronoi图方法
• 2.5 本章小结
• 第三章 时间序列的表示与索引
• 3.1 时间序列的表示方法
• 3.1.1 时间序列表示概述
• 3.1.2 时间序列表示的主要方法
• 3.1.3 基于重要点分段的KL表示方法
• 3.2 时间序列的索引技术
• 3.2.1 高维数据索引方法
• 3.2.2 时间序列的索引方法
• 3.3 实验与分析
• 3.4 本章小结
• 第四章 时间序列相似性查询
• 4.1 时间序列相似性查询概述
• 4.1.1 时间序列相似性的概念
• 4.1.2 相似性查询的完备性
• 4.1.3 相似性度量对索引的影响
• 4.1.4 时间序列的变形问题
• 4.2 时间序列的相似性度量
• 4.2.1 Minkowski距离
• 4.2.2 动态时间弯曲距离
• 4.2.3 编辑距离
• 4.2.4 其它距离
• 4.3 基于KL表示方法的全序列匹配查询
• 4.3.1 时间序列的KL相似性度量
• 4.3.2 全序列匹配查询算法
• 4.4 基于KL表示方法的线性模式查询
• 4.4.1 线性模式的KL相似性度量
• 4.4.2 线性模式的最近邻近查询
• 4.4.3 线性模式的最近模式对查询
• 4.4.4 线性模式的最远模式对查询
• 4.5 实验与分析
• 4.6 本章小结
• 第五章 时间序列反向查询
• 5.1 反向查询概述
• 5.2 反向查询的原理
• 5.2.1 IC-索引的原理
• 5.2.2 IC-索引的维护
• 5.2.3 IC-索引的实现
• 5.3 反向查询的实现
• 5.4 实验与分析
• 5.5 本章小结
• 第六章 时间序列异常检测
• 6.1 异常检测概述
• 6.1.1 异常的概念
• 6.1.2 异常检测的基本方法
• 6.2 基于Voronoi图的异常检测方法
• 6.2.1 基于密度的异常检测方法分析
• 6.2.2 基于Voronoi图的异常检测算法VOD
• 6.3 时间序列模式异常检测
• 6.3.1 时间序列异常的概念
• 6.3.2 时间序列异常检测的基本方法
• 6.3.3 线性模式异常检测的VOD方法
• 6.4 实验与分析
• 6.5 本章小结
• 第七章 总结与展望
• 7.1 全文总结
• 7.2 研究展望
• 参考文献
• 攻读博士学位期间发表的论文和参加的科研项目
• 致谢