频繁闭项集并行挖掘算法的研究与实现

论文摘要

关联规则挖掘是数据挖掘领域中的一个重要分支,其任务是发现所有满足最小支持度和最小置信度阈值的强规则。近年来,其在市场营销、决策辅助等领域广泛而成功的应用,使其成为数据挖掘研究中的一个热点。频繁模式挖掘是关联规则挖掘的关键,也是关联规则挖掘研究的重点。在关联规则挖掘中,常用的频繁模式有频繁项集、频繁闭项集以及最大频繁项集。最初,关联规则是通过挖掘频繁项集来产生的,然而频繁项集的规模往往较大,这严重的影响了关联规则的挖掘效率。由于频繁闭项集的数量远小于频繁项集,而且通过频繁闭项集能得到所有的频繁项集,通过频繁闭项集产生的关联规则能得到所有的规则,因此当前通常的做法是使用频繁闭项集代替频繁项集来挖掘关联规则。然而,为了加快关联规则产生的速度,仅仅有频繁闭项集是不够的,还需要将频繁闭项集之间的包含关系用某种有效的数据结构保存起来,比如频繁闭项集格。通过格,一个项集能够容易的找到它所有的子集和超集,从而加快规则产生的速度。并行化是提高问题解决效率的有效方法。随着数据集规模的不断增大,为了更有效的解决关联规则挖掘的实际问题,并行技术被引入其中,并得到了广泛而深入的研究。然而现有的关联规则并行挖掘算法,几乎都是针对频繁项集的,而对于频繁闭项集的并行挖掘算法几乎没有。本文对关联规则挖掘进行了一般性的论述;分析了国内外研究的现状;研究了典型的频繁项集、频繁闭项集挖掘算法以及频繁项集并行挖掘算法的算法思想和优缺点;提出了并行挖掘频繁闭项集的有效算法P-CHARM,以及并行挖掘频繁闭项集并建格的有效算法P-Q-CFIsL。P-CHARM有两个版本,P-CHARM I和P-CHARM II。其中,P-CHARM II是P-CHARM I的改进。P-Q-CFIsL是Q-CFIsL的并行化,Q-CFIsL是本课题组提出的快速挖掘频繁闭项集并建格的有效算法。本文通过实验证明了P-CHARM和P-Q-CFIsL的有效性。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 论文的选题和意义
• 1.2 国内外研究现状
• 1.3 论文的主要内容
• 2 关联规则挖掘概述
• 2.1 问题描述
• 2.1.1 基本概念
• 2.1.2 频繁项集vs 频繁闭项集
• 2.1.3 搜索空间和搜索方式
• 2.1.4 数据表示形式和支持度计数方式
• 2.2 频繁项集算法概述
• 2.2.1 Apriori 算法
• 2.2.2 FP-Growth 算法
• 2.2.3 Eclat 算法
• 2.3 频繁闭项集算法概述
• 2.3.1 A-Close 算法
• 2.3.2 Closet 算法
• 2.4 小结
• 3 并行挖掘频繁项集的策略和算法
• 3.1 概述
• 3.1.1 并行挖掘分类
• 3.1.2 所面临的问题
• 3.2 几种并行挖掘频繁项集的算法
• 3.2.1 基于Apriori 的并行算法
• 3.2.2 基于FP-growth 的并行算法
• 3.2.3 基于垂直数据表示方式的并行算法
• 3.3 小结
• 4 P-CHARM：并行挖掘频繁闭项集的有效算法
• 4.1 基本概念
• 4.2 CHARM 算法
• 4.2.1 CHARM 算法描述
• 4.2.2 CHARM 算法示例
• 4.2.3 CHARM 算法优化
• 4.3 P-CHARM 算法设计
• 4.3.1 P-CHARM I
• 4.3.2 P-CHARM II
• 4.4 实验分析
• 4.5 小结
• 5 P-Q-CFIsL:并行挖掘频繁闭项集并构建其格的有效算法
• 5.1 Q-CFIsL 算法
• 5.1.1 基本概念
• 5.1.2 快速寻找preC
• 5.1.3 Q-CFIsL 设计与实现
• 5.1.4 一个例子
• 5.2 P-Q-CFIsL 算法设计
• 5.3 P-Q-CFIsL 实验分析
• 5.4 小结
• 6 总结
• 致谢
• 参考文献
• 附录