频繁模式增长算法FP-growth的优化研究

来源 :桂林电子科技大学 | 被引量 : 0次 | 上传用户:cumt12791
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
长期以来,挖掘频繁模式主要采用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;对于稠密数据集,优化算法的优势更加显著。  目前数据挖掘技术在国外应用非常广泛,但是国内在这方面的发展相对缓慢。作者在对本文提出和研究的各种算法进行比较和测试,这些工作也只是对数据挖掘中关联规则的相关算法进行的较为深入的研究,在今后的工作中将更加深化和具体地分析和研究。
其他文献
本文提出了一种新颖的安全评估方法——面向对象的安全评估方法。由于当前评估理论的匮乏,导致实际中相当多的安全评估不规范,随意,低效率。机构需要标准化的评估方法来指导相关
计算机技术、微电子技术、低功耗多传感器技术和无线通信等技术的迅猛发展,推动了无线传感器网络的快速发展。无线传感器网络由于自身的优点,引起了国内外学术界和社会的广泛
随着社会信息化水平的提高,以IC卡为关键技术的“一卡通”系统将在各行业信息管理系统建设中扮演越来越重要的角色。  所谓“一卡通”系统,一般认为就是以IC卡技术为核心,结合