基于分形的非平稳时间序列挖掘关键技术研究

摘要

随着计算机信息系统的日益普及，人们在日常事务处理和科学研究中积累了大量的各种类型的数据。在这些保存的数据中，绝大部分都是时间序列类型的数据，如金融证券市场中，每天的股票价格变化；零售行业POS系统中，某种商品每天的销售额；气象预报研究中，某一地区的每天气温与气压的读数以及生物医学中，某一症状病人在每个时刻的心跳变化等。如何对这些海量的时间序列数据进行分析处理，从中挖掘出蕴藏在数据信息背后的客观规律，这对于我们揭示事物发展变化的内部规律，发现不同事物之间的相互作用关系，为人们正确认识事物和科学决策提供依据等都具有十分重要的现实意义。在这种需求的大力推动下，时间序列数据挖掘就是为解决这一问题而出现的一种新型数据分析技术。利用时间序列数据挖掘技术，得到数据中蕴含的与时间相关的有用信息，实现知识的发现与规则的提取。
　　 本文针对非平稳时间序列数据挖掘技术中的时间序列表示方法、相似性查找、时间序列距离度量、序列分类和异常检测等关键技术进行了深入的分析研究。将网格和分形技术应用到非平稳时间序列挖掘任务中，既保留了时间序列的非线性和分形的重要特征，同时又实现了维度的约简。论文主要研究内容和创新点如下：
　　 1)时间序列表示方法研究首次将网格思想应用到MBR(minimum bounding rectangle)中，提出了一种基于MBR的高效时间序列表示法GMBR(Grid Minimum Bounding Rectangle)，同时将分形思想首次应用到APCA(Adaptive Piecewise Constant Approximation)中，提出了一种高精度的基于分形和符号化的时间序列表示方法FSPA(FractalSymbolic Piecewise Approximation)，前一种方法是将网格的思想引入到MBR中，能够保证在低开销的情况下有效提高查找的准确性；后一种方法是将分形理论和R/S方法应用到现有的时间序列表示方法中，既保留了时间序列的非线性和分形的重要特征，同时也实现了维度的约简。实验数据表明，这两种方法在相似性查找和分类任务等多种挖掘任务中均具有较高的效率。
　　 2)时间序列的距离度量方法研究分别提出了基于GMBR和FSPA表示法的时间序列距离度量公式，并给出了理论证明，证明了用我们所给出的距离度量公式计算两个时间序列间的距离要比原始序列间的欧式距离小，从而证明了这两种时间序列表示方法的可用性；这两种距离度量公式均以简约后的欧式距离公式为基础，基于GMBR的距离度量公式引入位运算，容易快速地计算出序列间的距离，且通常这些运算都可以通过硬件来实现；基于FSPA表示法的距离度量将分形维度应用到距离度量中，大大增加了时间序列相似性查找的精度。本文还给出了相似性挖掘任务的算法描述，通过实验数据表明，这两种方法在时间序列的相似性挖掘任务中具有较高的精度且需要较少的存储空间。
　　 3)时间序列的分类问题研究提出了基于FSPA表示法的时间序列分类方法。该分类方法引入了分形技术，能够有效地保留原序列的重要特征，同时将时间序列进行符号化表示，具有比初始数据低的距离度量。该分类方法共分为两步，首先利用分形和符号化的时间序列表示方法进行数据的转化，将数据转化成等长向量，然后在经过转化的等长数据集上使用一般的分类算法进行分类。将本文算法与领域无关算法进行了比较，并从训练样本大小、序列长度和噪声对两种算法的影响三个方面进行了分析研究。实验结果表明在训练数据较少时，使用本文提出的领域相关算法比较合适；另一方面，领域无关的算法受噪声的影响相对较少。
　　 4)时间序列异常检测研究在时间序列的GMBR表示的基础上，本文首次提出将基于距离和基于密度的时间序列检测方法结合，给出了时间序列模式异常的定义，并用“异常特征值”来衡量时间序列模式的异常程度。根据本文所提出的模式异常的定义，在强力搜索算法的基础之上提出了新的时间序列异常检测算法GMBR-DD(Grid Minimum BoundingRectangle-Discords Detect)，该算法将基于距离和基于密度的异常检测方法结合，能够高效地发现时间序列中的异常模式。通过三组实验数据，对本文提出的异常时间序列定义和时间序列的异常检测算法进行了验证，实验结果表明本文所提出的时间序列异常检测算法能够有效地发现时间序列的异常变动，为决策提供了很好的平台和有力的工具。

目录

文摘

英文文摘

第一章 绪 论

1.1 研究背景及意义

1.1.1 研究背景

1.1.2 研究意义

1.2 非平稳时间序列数据挖掘关键技术研究现状

1.2.1 数据挖掘概述

1.2.2 表示方法

1.2.3 相似性查找

1.2.4 相似性度量

1.2.5 聚类与分类

1.2.6 异常检测

1.3 论文的主要研究内容和创新点

1.4 论文的组织结构

第二章 非平稳时间序列表示方法研究

2.1 引言

2.2 时间序列的定义及其抽象表示

2.2.1 时间序列的定义及分类

2.2.2 时间序列的抽象表示

2.3 基于MBR和网格的时间序列表示方法GMBR

2.3.1 GMBR介绍

2.3.2 维度约简

2.3.3 MBR离散化

2.4 基于分形和符号的时间序列表示方法FSPA

2.4.1 分形理论和R/S法

2.4.2 APCA介绍

2.4.3 维度约简

2.4.4 FSPA表示法

2.5 小 结

第三章 非平稳时间序列相似性挖掘算法的研究

3.1 引言

3.2 问题描述及相关研究工作

3.2.1 相似性查找问题描述

3.2.2 主要难点与相关研究

3.3 基于GMBR的相似性查找研究

3.3.1 距离度量

3.3.2 相似性查找

3.4 基于FSPA的相似性查找研究

3.4.1 距离度量

3.4.2 相似性查找算法

3.5 仿真结果

3.5.1 仿真设置

3.5.2 仿真结果

3.6 小 结

第四章 非平稳时间序列的分类算法研究

4.1 引言

4.2 相关研究及问题描述

4.3 基于动态时间弯曲的分类算法

4.4 基于FSPA的时间序列分类方法研究

4.4.1 基于FSPA的数据转换

4.4.2 利用分类算法对时间序列进行分类

4.5 实验仿真与分析

4.6 小 结

第五章 非平稳时间序列异常检测研究

5.1 引言

5.2 本章的研究内容及相关工作

5.3 时间序列异常检测定义

5.4 时间序列异常检测算法

5.4.1 强力搜索法

5.4.2 基于距离和密度的的GMBR-DD算法

5.5 实验仿真与分析

5.5.1 加入高斯噪音的数据集

5.5.2 Keogh_data数据集

5.4.3 经济数据集

5.5 小结

第六章 总结与展望

6.1 总 结

6.2 展 望

参考文献

致谢

附录A 攻读博士学位期间发表的论文