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

作     者：周兴华 

作者单位：南京理工大学 

学位级别：硕士

导师姓名：陆建峰

授予年度：2013年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：时间序列流 层次聚类 增量系统 频繁模式 多线程 

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