时间序列流的层次聚类和频繁模式的挖掘算法研究

摘要

时间序列挖掘是数据挖掘领域中最具挑战性的十大研究方向之一。时间序列流是一种连续、高速、无限、时变的按照时间排列的有序序列。连续性要求挖掘算法扫描次数少;高速性要求挖掘算法的实时性高;数据量的无限性要求挖掘算法能够缓存数据，并分批装载进主存中;数据内容的时变性要求挖掘算法具有处理概念漂移的能力，能够反映出数据的演化性质。由于时间序列流的复杂特性，时间序列流的挖掘研究仍处于探索阶段，本文将从层次聚类系统和序列频繁模式挖掘两个方面开展研究。
　　由于层次聚类算法具有自适应确定聚类数目、适合多种类型的簇结构和效率高等多种优点，使得它在数据流聚类研究中应用广泛。本文重点研究了数据流层次聚类中的ODAC(the Online Divisive Agglomerative Clustering)算法。ODAC算法是一个时间序列流增量式聚类算法，采用自顶向下策略构建簇的一个层次树状结构。但它存在两种问题:噪音数据影响聚类结果和处理概念漂移时重构簇结构代价过大。本文提出了一种基于粗糙集理论的改进算法ODRC(the Online Divisive Rough Clustering)。ODRC算法分为两个阶段:第一阶段根据时间序列流样本生成子簇的层次结构，第二阶段利用限制容差关系模型扩展子簇的粗糙集定义，从而获得子簇结构基于粗糙集的等价划分。该算法能够获得比原算法更加合理的簇结构，增强了对时间序列流中概念漂移现象的处理能力。实验结果表明了该方法的可行性和有效性。
　　序列模式挖掘作为数据挖掘领域的研究热点之一，其任务是从序列数据库中挖掘出频繁序列供决策者做出决策。本文引入了一种基于滑动窗口技术的序列模式挖掘算法MFI-TransSW，该算法采用比特序列实现滑动窗口操作，较好解决了在数据一遍扫描和有限内存空间的限制下实现快速处理的难题。针对MFI-TransSW算法在频繁模式生成阶段计算效率不高的情况，本文提出了一种基于窗口划分成固定数目段的多线程算法MFI-MultiSW。MFI-MultiSW算法采用线性链表结构存储当前候选项集和窗口内事务的信息，并在线性链表的基础上采用多线程方法生成频繁模式。实验结果表明，改进算法相比原算法具有较高的执行效率，尤其在多核环境中，性能提升更为显著。

目录

声明

摘要

1 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．3 主要工作与创新之处

1．4 论文组织结构

2 时间序列流层次聚类算法的分析

2．1 传统层次流聚类算法

2．1．1 分解型层次聚类法-BIRCH算法

2．1．2 凝聚型层次聚类法-CURE算法

2．2 时间序列相似性度量的主要方法

2．2．1 基于形状的相似度

2．2．2 基于特征的相似度

2．2．3 基于模型的相似度

2．2．4 符号时序数据的相似度

2．3 时间序列流聚类

2．4 在线分裂合并聚类算法ODAC

2．4．1 ODAC的算法框架

2．4．2 增量式相似性度量

2．4．3 算法步骤

2．5 ODAC算法的评估

2．5．1 控制层次结构增长的标准

2．5．2 概念漂移的处理

2．5．3 算法复杂度分析

2．6 本章小结

3 基于粗糙集理论的ODAC改进算法

3．1 ODAC算法的缺陷

3．2 基于粗糙集理论的聚类研究

3．2．1 粗糙集理论

3．2．2 利用粗糙集的概念进行聚类

3．3 在线分裂粗糙聚类算法ODRC

3．3．1 限制容差关系模型

3．3．2 一个实例

3．3．3 ODRC的算法框架

3．3．4 算法步骤

3．4 ODRC算法的评估

3．4．1 概念漂移的处理

3．4．2 算法复杂度分析

3．5 本章小结

4 时间序列流聚类实验

4．1 实验数据介绍

4．2 聚类质量分析

4．3 时间效率分析

4．4 算法参数评估

4．5 本章小结

5 时间序列流频繁模式挖掘算法的研究

5．1 频繁模式挖掘算法的数据流处理模型

5．2 滑动窗口模型的频繁模式挖掘算法

5．3 MFI-TransSW算法

5．3．1 算法主体思想

5．3．2 MFI-TransSW算法缺陷

5．4 改进算法MFI-MultiSW

5．4．1 算法改进技术

5．4．2 频繁模式挖掘过程

5．4．3 频繁模式中的时序限制

5．5 实验结果

5．6 本章小结

6 总结和展望

6．1 研究正作总结

6．2 工作展望

致谢

参考文献

附录