基于正交变换的时间序列索引

论文摘要

时间序列的相似性度量和索引查询是数据挖掘技术的关键和基础。本文首先对时间序列数据挖掘技术进行了较系统的文献总结,仔细分析并比较了现有的相关技术,然后,阐述了其中的几个基本问题,即时间序列的降维、相似性度量以及时间序列的索引等,对这些方面的优缺点以及适用范围等进行了说明,然后针对这几个方面,进行了较为深入的研究,提出了基于R*-tree的分层树索引结构以及正交变换的索引方案,并通过实验进行了验证。时间序列数据通常有以下几方面的特点：海量性、复杂性以及噪声干扰等,如果直接在原始序列上进行搜索,则会出现计算量大,并且准确度、可靠性等都难以得到保证。目前,针对时间序列的表示,国内外的研究者已经提出了很多算法。算法的基本步骤首先提取时间序列的特征值或特征矩形,实现数据的降维,然后将提取该时间序列的特征值或特征矩形建立高效的索引结构,从而使时间序列的查询效率得到很大的提高。基于R*-tree的分层树索引结构给出了一种新的时间序列索引结构,将时间序列分段表示,逐段建立不同层次的类R*-tree索引结构。基于该结构给出了相应的插入和查询算法,并在理论上证明,算法在DTW相似性度量意义上,具备非漏报性质。实验结果表明,该算法较传统树状索引结构在维数较高、数据量较大等情况下,具有更高的检索性能。本文简要的回顾一下时间序列变换以及索引技术。通过对R-tree、R*-tree以及X-tree的介绍,呈现出一幅完整而有序的检索结构发展过程图,它们依次都是在上述树状结构的基础之上,针对缺陷的一种完善与扩充,使其具有更高的效率与适用性。基于正交变换的时间序列,首先根据正交多项式提取特征值,然后采用分层索引建立检索树。分层树通过较低的时间复杂度来建立索引结构,算法依旧能保持良好的时空复杂度。同时在理论上证明,文本提出的算法在DTW相似性度量意义上,具备非漏报性质。实验结果表明,与基于离散小波变换和离散傅里叶变换的时间序列相似查询所作的对比实验表明,所提的算法可以获得高的查询效率。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 时间序列数据挖掘的研究现状
• 1.2.1 时间序列的相似性研究现状
• 1.2.2 时间序列的索引研究现状
• 1.3 本文的主要工作和论文的组织结构
• 2 时间序列相关的基本理论
• 2.1 时间序列
• 2.2 时间序列降维
• 2.3 时间序列相似性度量
• 2.3.1 欧氏距离
• 2.3.2 DTW距离
• 2.3.3 最长公共子序列
• 2.3.4 子序列匹配
• 2.4 本章总结
• 3 分层树的索引结构
• 3.1 概述
• 3.1.1 相关符号
• 3.1.2 问题定义
• 3.2 分层索引算法
• 3.2.1 分层索引结构定义
• 3.2.2 分层树插入
• 3.2.3 分层树查询
• 3.3 不漏查证明
• 3.4 实验与结果分析
• 3.5 本章小结
• 4 基于正交变换的索引方案
• 4.1 概述
• 4.1.1 索引结构分类
• 4.1.2 时间序列索引
• 4.2 数据建模
• 4.3 相似性匹配
• 4.3.1 建立索引
• 4.3.2 相似性查询
• 4.4 不漏查证明
• 4.5 实验与结果分析
• 4.6 本章小结
• 5 总结与展望
• 5.1 总结
• 5.2 进一步的工作
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢