时间序列挖掘相关算法研究及应用

随着计算机与信息技术的普及和大容量存储技术的发展，人们在日常事务处理和科学研究中逐渐积累了大量的宝贵数据。这些数据背后蕴藏着对决策有重要参考价值的信息。如何充分有效地利用这些历史数据，从中提取出用户需要的信息正成为当今数据挖掘领域广泛关注的热点问题。 时间序列数据反映了属性值在时间或空间顺序上的特征。利用时间序列数据挖掘(Time Series Data Mining，简称TSDM)，可以获得数据中蕴含的与时间相关的有用信息，实现知识的提取。由于时间序列的数据类型复杂且具有高维性、噪声干扰及波动性等特点，因此时间序列挖掘是数据挖掘中的一个重要研究方向。目前重点的研究内容包括时间序列的模式表示、时间序列的相似性查询、时间序列的聚类和分类、时间序列的异常检测等。 本文在国内外时间序列数据挖掘最新研究的基础上，以石油工业领域中测井和录井色谱数据序列的分析处理为实际应用背景，对时间序列挖掘中的线性拟合、在线划分、相似性度量、时态频繁模式挖掘四个方面的问题进行了研究分析，提出一些算法和解决方案，取得一定成果。主要工作和创新之处有： 1．提出了一种基于关键点的时间序列线性拟合表示方法。该算法在扫描数据的过程中利用单调序列中三个连续数据形成的夹角和非单调序列中的极值点，从序列中挑选反映趋势变化的关键点，实现时间序列的线性拟合。实验结果表明该算法拟合效果良好，剔除了噪音干扰，并能够精确定位单调序列中的突变转折点，发现序列中的尖峰状态。 2．提出了一种基于层次聚类的在线序列分割算法。该算法利用数据序列的有序性特征，构造了一种存储划分特征的链表结构，一次扫描数据库完成数据序列的在线划分，时间复杂度为O(n)。同时，利用链表结构中保存的划分特征信息，历史信息的快速查询成为可能。实验结果表明此算法具有良好的划分性能和可扩展性能。 3．提出了一种基于关键点动态时间弯曲距离的相似性度量方法。该方法在时间序列线性拟合的基础上，仅使用序列中的关键点用于弯曲距离矩阵计算。实验结果表明：基于关键点的动态时间弯曲距离度量方法在准确性上优于欧氏距离，与经典的动态时间弯曲距离近似，但明显提高了检索速度。 4．对FP-growth算法进行改进，使之适用于时态约束下的频繁模式挖掘。由于经典的频繁模式挖掘算法FP-growth没有考虑时间向量的影响，无法直接应用于时态频繁模式的挖掘。改进后的算法构造了一种用于存储频繁模式时态属性的双树结构。利用这种双树结构，两次扫描数据库实现时态频繁项目的有效挖掘。实验结果表明该算法是有效的和可扩展的。 5．针对目前石油工业领域中各类数据序列的特点和实际的应用需求，给出时间序列挖掘算法在测井和录井数据序列中的应用样例。实验结果显示：①数据序列在线划分算法实现了测井曲线的快速粗划分和分段信息的快速查询；②数据序列线性分段拟合方法能够有效捕获色谱和测井数据序列中的尖峰子序列，准确定位序列中的变化转折点，忽略变化细微的数据点，在保持序列形态不变的同时极大地降低了数据存储量。 全文共分为七个章节，第一章对时间序列挖掘进行了综述，包括其应用背景、国内外研究进展等；第二章至第五章从四个方面展开了算法研究探讨：时间序列的线性拟合、时间序列的在线划分、时间序列的相似性度量和时态频繁模式挖掘；第六章在上述研究的基础上，给出了序列挖掘算法在石油测井和录井数据序列中的应用实例；最后一部分，即第七章，对全文进行总结，并提出了进一步的研究思路。