论文部分内容阅读
关联规则挖掘是数据挖掘中的重要方法,目前主流的关联规则挖掘算法有Apriori算法、Eclat算法、Fp-growth算法等。上述算法存在如下问题：(1)Apriori算法存在大量I/O操作以及生成大量的候选项集；(2)对于Eclat算法,当事务数据库很大时,垂直数据结构<item,tid-set>无法存储于内存。当事务数据库中事务数很大时,tid-set长度很大,tid-set求交时间增加,算法性能下降；(3)Fp-growth算法需要频繁的构造条件模式基,且当支持度阈值较小时,Fp-tree的压缩能力有所下降,大量的冗余的存在使得算法性能开始下降。本文基于上述问题研究若干新技术来提升关联规则挖掘的效率。首先,本文通过阅读大量文献,研究已有算法的优缺点和思想方法,提出新的数据结构PE_Graph图：用有向图压缩存储事务数据库,能够用于快速搜索频繁项集；Tid-tree树：用类Fp-tree对tid-set重新编码,实现垂直数据结构的高度压缩,大大减小了tid-set求交时间：MP-tree树：通过频繁路径后缀实现PE_Graph图路径扩展的高效剪枝。接着,本文提出了频繁项集挖掘算法并对其进行了一系列的改进：(1)基于FPE_Graph图和Tid-tree树提出了两个新的频繁项集挖掘算法PF_search算法和PR search算法。理论分析及实验结果表明PF_search算法和PR_search算法存在大量的冗余路径扩展,且PR_search算法采用的逆向深度搜索策略优于PF_search算法采用的正向深度搜索策略,同时提出了FPE_Graph图的锥形分布假设。(2)为了对(1)中存在的冗余路径进行有效的剪枝,本文提出了新的数据结构MP-tree树,基于该树设计出了K路剪枝Fp-search算法,本文通过频繁率来刻画算法的剪枝性能,通过理论分析可以得出K路剪枝的剪枝能力e的理论值,从而量化了剪枝能力的评估,有效的证明算法剪枝性能和指导算法的改进。尽管K路剪枝Fp-search算法的时间性能非常优秀,但是它带来了额外的空间消耗,即MP-tree的空间规模O(N)(N为所有频繁项集的个数),当N值较大时,算法剪枝空间复杂度较高。(3)基于(2)中存在的问题,提出了减小剪枝空间复杂度的混合剪枝算法Fpmix2_search算法、Fpmixk_search算法,混合剪枝算法在保证时间性能的同时,大大降低了剪枝带来的额外空间消耗,但混合剪枝存在性能受节点划分方式的影响,且不适合并行化等缺点。(4)基于(3)中的问题,本文提出了新的算法FNMP-search算法,该算法剪枝空间复杂度极小,且能够实现高效的剪枝。(5)最后实现了Fp-search系列算法的并行化算法(本文称PF_search算法、PR_search算法、K路剪枝Fp-search算法、Fpmix2_search算法、Fpmixk_search算法、FNMP-search算法为Fp-search系列算法)。最后,通过五个经典的真实数据集对Fp-search系列算法性能有效性和高效性进行验证实验表明,Fp-search系列算法性能优于Fp-growth算法,且其中以FNMP-search算法最优,并行性能最优。