时间序列与聚类挖掘相关技术研究

论文摘要

数据挖掘及其应用已经渗透到多个学科，并在人工智能与机器学习、数据库、模式识别、生物信息学、神经计算等领域取得了丰硕的成果。同时，数据挖掘也不仅是科学家的兴趣所在，更多地得到了政府、工业界的密切关注。通过引入数据挖掘，可以大大提高生产力，取得社会的更大进步。世界上许多国家和地区的政府及工业界都希望掌握数据挖掘技术，提升国家和企业的科技含量，并最终取得领先的地位。 数据挖掘涉及的研究范围较为广泛，本文主要讨论了序列数据与聚类挖掘相关技术，主要的主要的研究成果如下： （1）给出小波变换在时间序列相似性查找中对距离上下界的一个严格估计，同时说明传统的算法只是本文下界的一部分。根据本文给出的小波变换的下界，相对于传统的算法，可以排除更多的不相似序列。根据给出的上界，可以直接判断出两条序列是否相似，进一步减少需要验证的原始序列的个数。 （2）在使用小波变换缩减维度解决高维时间序列查询时，传统的算法均使用变换后小波序列的前k个系数作为原始时间序列的一个近似估计。但是由于选择前k个系数不一定能很好地近似原始序列集合，可能对于中间某些系数的选取，可以更好的给出原始序列集合的一个表示。因此给出相关定理，说明选择小波系数集合的列平方和最大的k列，可以更好近似原始序列集合。 （3）对允许时间偏移的序列间相似性搜索，由于可以处理异常数据以及允许不同长度的时间序列间进行匹配，因此应用日益广泛。但是大部分研究都是基于两条时间序列间的全相似性匹配。给出了基于动态规划的子序列相似性搜索算法，对于给定的查询序列，可以搜索到长序列中和给定的查询序列最为相似的一段子序列。并进一步给出了两种优化算法，以减少子序列相似性搜索中距离矩阵需要计算的项的个数。 （4）时间序列的相似性搜索可以看成度量空间搜索的一种特例。提出一种新的度量空间索引数据结构，简称为bu-tree，它是基于自底向上的分层聚类来构造索引结构，而传统的度量空间数据结构大部分是基于自顶向下构造的方法。相对于传统的构造方法，bu-tree可以在更小的索引半径内包含更多的对象，这样有利于查询的筛选。给出了bu-tree的构造算法以及相应的范围查询算法。 （5）数据概要被用来压缩大规模的数据库，以便进行后续的分层聚类分析。bu-tree中每个节点也可以看成是一种数据概要。讨论了另一种常用的数据概要：数据泡。详细研究了递增数据泡的质量度量标准（数据概要指标）。当更新数据库时，我们指出哪些因素会影响数据概要指标的期望与均方差。基于这些因素，给出一个对数据泡进行递增维护的一个动态算法。 （6）讨论了系统级故障诊断中对测试序列的聚类分析算法。在基于聚类的集团理论的基础上，利用贪婪算法中不同贪婪准则提出了四个针对系统及故障的概率诊断算法。每种算法在较少的测试数情况下，均表现出较高的诊断正确率，且时间复杂度不高。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 时间序列相关研究
• 1.3 聚类相关研究
• 1.4 本文工作
• 1.4.1 研究内容与成果
• 1.4.2 组织结构
• 第二章 基于小波变换的序列间距离严格估算
• 2.1 简介
• 2.2 相关概念
• 2.3 使用小波变换的严格上下界
• 2.4 实验结果
• 2.5 小结
• 第三章 对时间序列查询的最优小波误差估计
• 3.1 简介
• 3.2 最优小波系数选择
• 3.3 实验结果
• 3.4 小结
• 第四章 允许时间偏移的子序列相似性搜索算法
• 4.1 简介
• 4.2 子序列相似性搜索算法
• 4.3 实验结果
• 4.4 小结
• 第五章 聚类算法在时间序列索引构造中的应用
• 5.1 引言
• 5.2 相关工作
• 5.3 一种新的索引树构造算法（bu-tree）
• 5.3.1 bu-tree的构造算法
• 5.3.2 bu-tree构造示例
• 5.4 实验结果
• 5.5 小结
• 第六章 一种数据概要的动态递增维护方法
• 6.1 引言
• 6.2 动态递增数据概要
• 6.3 实验结果
• 6.4 小结
• 第七章 对系统级故障诊断中测试序列的聚类分析算法
• 7.1 引言
• 7.2 基本概念
• 7.3 贪婪算法及相关定理
• 7.4 实验结果
• 7.5 小结
• 第八章 总结与展望
• 参考文献
• 博士期间发表论文情况
• 致谢