时间序列数据挖掘相似性度量和周期模式挖掘研究

摘要

随着信息技术的飞速发展，数据挖掘受到越来越多的关注。时序数据在现实生活中广泛存在，如金融市场、工业过程、科学试验、医疗、气象、水文、生物信息等，而且存储规模呈现爆炸式增长。因此对时间序列数据挖掘问题进行深入研究是非常必要和富有挑战性的。目前的时间序列数据挖掘技术尚处于起步阶段，挖掘算法有待扩充和完善。本文在综述了时间序列数据挖掘研究发展概况后，对目前的主要方法进行了总结评述，在重新描述、相似性比较和周期模式挖掘几个方面进行了深入研究。最后在总结全文的基础上，指出了本文有待深入研究的若干问题。本文的创新性工作主要包括以下内容： 1)提出了基于形态的时间序列相似性度量方法。本方法在时间序列分段线性化的基础上，采用了基于斜率相对变化的符号化重新描述方法，可以有效描述序列形态的动态变化趋势；同时提出了一个与之对应的距离度量公式，克服了点距离度量中存在的对各种扰动敏感的缺陷。实验证明，本方法还具有时间多分辨率特征，可以比较在不同时间分辨率下的时间序列的相似程度。 2)提出了局部分段动态时间扭曲算法。经典动态时间扭曲算法(DTW)在时间序列相似性度量中具有重要作用，但由于计算复杂度较高，很难应用于实际数据库中。本文提出了一个新的算法-局部分段动态时间扭曲算法。在对时间序列进行分段线性化的基础上，将每一个段视为一个整体，应用经典的动态时间扭曲算法，通过设置补偿系数，保证了算法的精度。实验表明，本算法能够在计算精度几乎没有损失的情况下，有效地提高经典DTW算法的效率。 3)提出了一种高效的时间序列异步周期1-模式挖掘算法。本算法设计了一种基于2进制编码的映射算法，并提出了改进的点乘算法，可以通过一次计算发现一个事件在序列中出现的所有位置；并且，本算法用并行计算替代了原算法中的串行计算方法，显著减少了数据的运算和存储次数。实验证明，本算法在完全不降低原算法准确性的基础上，显著提高了算法效率。 4)首次提出了时间序列局部周期频繁模式的概念及其挖掘算法。不同于现有的所有周期挖掘算法，本算法不但能够挖掘出贯穿时间序列全局的频繁发生的周期模式，而且能够发现只在某个局部频繁发生的周期模式。本算法首先将时间序列划分为局部集合，然后基于数据自行找出序列中隐藏的潜在周期，生成局部周期频繁1-模式，最后在每一个有交叉的局部上，应用最大命中子模式树算法合成复杂模式输出。实验证明，本算法可以有效地发现时间序列中的局部周期频繁模式，其中的剪切算法和周期阈值公式能够有效提高算法效率。

目录

文摘

英文文摘

声明

第一章 绪论

1.1选题背景和研究意义

1.2数据挖掘综述

1.2.1数据库知识发现和数据挖掘比较及其发展过程

1.2.2数据挖掘的过程

1.2.3数据挖掘系统的分类

1.2.4数据挖掘的功能

1.3时问序列数据挖掘

1.3.1时间序列数据挖掘与传统时间序列分析

1.3.2时间序列数据挖掘的研究现状

1.4时间序列数据挖掘重新描述研究综述

1.4.1离散傅立叶变换

1.4.2离散小波变换

1.4.3奇异值分解算法

1.4.4分段描述算法

1.4.5界标模型

1.4.6字符串表示

1.4.7其他表示法

1.5时间序列数据挖掘相似性度量研究综述

1.5.1欧氏距离

1.5.2动态扭曲距离

1.5.3编辑距离

1.6时间序列周期模式挖掘进展综述

1.6.1周期模式分类

1.6.2部分周期模式研究

1.6.3潜在周期发现算法研究

1.6.4复杂模式生成算法研究

1.7本文的主要内容和创新点

1.7.1本文的主要内容

1.7.2本文的创新点

第二章 本文相关概念和算法介绍

2.1时间序列

2.2相似性度量

2.2.1欧氏距离

2.2.2动态时间扭曲距离

2.2.3分段线性表示

2.2.4模式距离

2.3时间序列周期模式挖掘的相关定义

2.4 SMCA算法

2.4.1问题定义

2.4.2 SMCA算法介绍

2.5最大子模式命中集算法

2.5.1类Apriori算法

2.5.2最大子模式命中集算法

2.6本章小结

第三章 基于形态的时间序列相似性度量研究

3.1引言

3.2基于形态的时间序列重新描述

3.2.1分段线性化和确定模式区分阈值

3.2.2规范化处理

3.2.3形态描述

3.2.4齐序列处理

3.3时间序列的形态距离

3.4仿真实验

3.4.1人工合成数据

3.4.2股票时间序列

3.5本章小结

第四章 局部分段动态时间扭曲算法研究

4.1引言

4.2经典的DTW算法

4.3局部动态时间扭曲(LSDTW)算法

4.3.1分段线性化算法

4.3.2任意两段之间DTW距离的计算规律

4.3.3任意两段之间DTW距离的计算公式

4.3.4局部分段动态时间扭曲(LSDTW)距离公式

4.4仿真实验

4.4.1人工数据库

4.4.2实际数据库

4.4.3仿真实验结果

4.5本章小结

第五章 时间序列异步周期模式挖掘算法研究

5.1引言

5.2相关概念定义

5.3 1-模式挖掘算法

5.3.1映射算法

5.3.2改进的点乘算法

5.3.3潜在周期检测算法

5.3.4 1-模式生成算法

5.4算法比较

5.4.1位置序列生成算法比较

5.4.2潜在周期发现算法比较

5.4.3有效段生成算法比较

5.5仿真实验

5.5.1人工数据

5.5.2实际数据

5.6本章小结

第六章 时间序列局部周期频繁模式挖掘算法研究

6.1引言

6.2相关概念定义

6.3局部周期频繁模式挖掘算法

6.3.1局部剪切算法

6.3.2潜在周期生成算法

6.3.3局部周期频繁段发现算法

6.3.4复杂模式生成算法

6.4仿真实验

6.4.1人工数据

6.4.2实际数据

6.5本章小结

第七章 总结和展望

7.1全文总结

7.2研究前景与展望

参考文献

发表论文和参加科研情况说明

致谢