论文部分内容阅读
长期以来,挖掘频繁模式主要采用Apriori算法及其改进形式,这类算法需要产生大量候选项集,并反复扫描数据库,降低了挖掘的效率。FP-growth算法是一种基于模式增长的频繁模式挖掘算法,避免了大量候选项集的产生,只需扫描数据库两次。效率比Apriori算法快一个数量级。然而,此算法在挖掘频繁模式时不可避免地需要递归地创建附加数据结构(如条件FP-tree,项头表),并且每当模式增长时就要创建一次。动态地创建如此大量的附加数据结构,将耗费大量时间和空间。 本文提出了 FP-growth算法的一种优化方法:基于升序 FP-tree的挖掘算法SAFP-merge。其通过采用基于支持度计数升序排列的频繁1-项集的构造策略,和引入第一棵子树及扩展频繁集等概念,使整个挖掘过程直接在初始生成的升序FP-tree中进行,而不需要另外递归创建条件FP-tree和项头表。挖掘时,首先挖掘第一棵子树;然后将第一棵子树根结点的所有分支与升序FP-tree的其他分支归并,并同时剪掉第一棵子树;最后对新的升序FP-tree递归调用挖掘过程,直到树只有一棵子树,且已经挖掘完该子树。为了验证SAFP-merge算法的性能,我们在一定的实验条件下对优化算法SAFP-merge和FP-growth算法进行了测试,实验结果表明:使用相同的稀疏数据集,优化算法速度是 FP-growth算法的3倍,而所需要的存储空间比FP-growth算法节省了1/3;对于稠密数据集,优化算法的优势更加显著。 目前数据挖掘技术在国外应用非常广泛,但是国内在这方面的发展相对缓慢。作者在对本文提出和研究的各种算法进行比较和测试,这些工作也只是对数据挖掘中关联规则的相关算法进行的较为深入的研究,在今后的工作中将更加深化和具体地分析和研究。