并行化频繁项集挖掘及其在数据流中的研究

论文摘要

频繁模式挖掘是数据挖掘中的一项重要任务,通过挖掘频繁模式,我们可以发现隐藏在数据中的有趣的相关和关联。频繁项集的挖掘作为频繁模式挖掘中的一类,它可以广泛应用在关联规则挖掘、聚类、分类和预测、入侵检测、相关性分析等等许多种数据挖掘任务中。由于数据挖掘在开始被提出时就是面向海量数据的,庞大的搜索空间使得许多传统的数据挖掘算法的效率并不理想。高性能并行环境为数据挖掘的发展开辟了一条新的路径,研究并行环境下的数据挖掘并行算法成为了数据挖掘界的热点。频繁项集挖掘也不例外,经过这些年的研究,并行化的频繁项集挖掘算法已经取得了一些成果。本文提出了一种基于分布式并行环境的频繁项集挖掘算法HPFP-Miner. HPFP-Miner算法是一种类FP-Growth算法,通过将数据库压缩到一个数据结构上进行挖掘。算法利用两次数据库扫描,在各并行结点上建立HPFP-tree和HPFP-forest.各节点只需要挖掘本地HPFP-tree,最后将挖掘结果统一到一个共享文件中。通讯集中在建树阶段,整个挖掘过程不需要节点间的同步,大大减少了通讯量,提高了算法的效率。由于数据流在日常生活中的广泛应用,数据流频繁项集挖掘受到了人们的关注。数据流有着快速变化的、海量的和无限的等特点,必须建立新的数据结构和算法对其进行挖掘。本文在上述算法的基础上,提出了基于滑动窗口的并行化的数据流频繁项集挖掘算法PFIMSD算法。算法仅通过一次扫描将当前窗口的所有数据压缩到并行节点上的PSD-tree上,窗口滑动时用增量的方法在PSD-tree上添加和删除相应分支。实验证明PFIMSD算法有着很好的时间效率和扩展性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状和遇到的问题
• 1.3 本文研究内容和创新之处
• 1.4 本文组织结构
• 第二章 频繁项集挖掘理论及研究现状
• 2.1 频繁项集挖掘的基本概念
• 2.2 传统的频繁项集挖掘算法
• 2.2.1 Apriori算法
• 2.2.2 FP-Growth算法
• 2.3 MPI并行算法的设计
• 2.3.1 MPI介绍
• 2.3.2 并行算法的设计
• 2.4 并行频繁项集挖掘
• 2.4.1 Count Distribution算法
• 2.4.2 Data Distribution算法
• 2.4.3 MLFPT算法
• 2.4.4 PFP-tree算法
• 第三章 并行频繁项集挖掘算法
• 3.1 HPFP-Miner算法的主要贡献
• 3.2 HPFP-tree和HPFP-forest
• 3.3 HPFP-forest的负载平衡策略
• 3.4 HPFP-Miner算法
• 3.5 HPFP-Miner的实验分析
• 3.6小结
• 第四章 并行挖掘数据流频繁项集
• 4.1 数据流概述
• 4.1.1 什么是数据流
• 4.1.2 数据流处理模型
• 4.2 数据流频繁项集挖掘
• 4.2.1 BTS算法
• 4.2.2 MOMENT算法
• 4.2.3 NewMoment算法
• 4.3 数据流频繁项并行挖掘算法（PFIMSD）
• 4.3.1 PFIMSD算法的主要贡献
• 4.3.2 问题描述
• 4.3.3 两个重要的数组
• 4.3.4 PSD-Tree及其挖掘算法
• 4.3.5 PFIMSD算法的实验分析
• 4.3.6 小结
• 第五章 总结及展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 硕士研究生期间的科研成果
• 致谢