序列模式挖掘的并行算法研究

论文摘要

序列模式挖掘是指从序列数据库中发现相对于时间或者其它顺序的高频率序列。其最初动机是想通过在带有交易时间属性的交易数据库中发现频繁项目序列以发现一个时间段内的客户购买行为规律。近年来序列模式挖掘已经成为数据挖掘的一个重要方向,其应用范围已不局限于交易数据库,在DNA分析等尖端科学研究领域、Web访问等新型应用数据源等众多方面都得到了针对性研究。文中结合R.Agrawal和R.Srikant提出的序列模式挖掘的有关定义和R.Wille提出的概念格理论,提出了频繁概念的定义;根据序列模式并行挖掘的需要提出了搜索空间划分理论,其中包括搜索空间、子搜索空间、等价子搜索空间和最大子搜索空间的定义。序列模式挖掘的数据有如下特点:数据量大,数据分布存储。已有的大部分序列模式挖掘算法没有综合考虑到数据的上述特点。本文针对序列模式挖掘数据的这些特点,结合并行理论,提出了一个分布式并行算法SPP(Sequential Pattern Parallel)。本算法遵循模式缩减的原则,利用分治策略实现并行操作,在每台处理器上运用搜索空间划分理论和频繁概念构造频繁项集,运用图深度优先搜索方法构造频繁序列。算法只需扫描数据库两遍,不需要生成候选序列,大大减少了数据库访问时间,提高了序列模式挖掘的效率。不过本文采用是静态负载平衡,还有待改进。基于自己设计的随机数据生成程序和不同的消息结构,本文在具体的并行环境中模拟了算法SPP,并在单机中实现了AprioriAll算法。实验证明,相比于AprioriAll,SPP算法具有良好的加速比和效率。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 选题背景与意义
• 1.2 序列模式挖掘并行算法的研究现状
• 1.2.1 基于Apriori-like 串行算法的并行算法
• 1.2.2 基于SPADE 串行算法的并行算法
• 1.2.3 基于树投影的并行算法
• 1.2.4 本节小结
• 1.3 论文主要内容
• 第2章 序列模式挖掘
• 2.1 序列模式的基本概念
• 2.2 研究现状
• 2.2.1 序列模式的扩展
• 2.2.2 序列模式挖掘算法
• 2.2.3 实际应用
• 2.3 经典算法
• 2.3.1 AprioriAll 算法
• 2.3.2 PrefixSpan 算法
• 2.4 本章小结
• 第3章 并行理论
• 3.1 并行计算机体系结构
• 3.1.1 单指令流多数据流
• 3.1.2 多指令流多数据流
• 3.2 并行计算模型
• 3.2.1 PRAM 模型
• 3.2.2 BSP 模型
• 3.2.3 LogP 模型
• 3.3 并行算法编程模型
• 3.3.1 数据并行模型
• 3.3.2 消息传递模型
• 3.3.3 两种模型比较
• 3.4 并行编程环境
• 3.4.1 PVM
• 3.4.2 MPI
• 3.4.3 MPI 与PVM 比较
• 3.5 并行算法基础
• 3.5.1 基本概念
• 3.5.2 并行算法的性能
• 3.5.3 并行算法设计原则
• 3.5.4 并行算法一般设计方法
• 3.6 本章小结
• 第4章 序列模式并行挖掘算法SPP
• 4.1 算法概述
• 4.2 算法理论
• 4.2.1 频繁概念
• 4.2.2 减少模式数量的观点
• 4.2.3 搜索空间划分
• 4.3 算法详解
• 4.3.1 生成和分配频繁1-项集
• 4.3.2 构造频繁项集
• 4.3.3 生成局部频繁项集关联图
• 4.3.4 生成频繁序列
• 4.4 复杂性分析
• 4.5 本章小结
• 第5章 实验与分析
• 5.1 并行环境
• 5.2 实验数据
• 5.3 采用的消息结构
• 5.4 MPI 函数
• 5.5 实验与性能分析
• 5.6 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢