一种改进的FP-Growth算法及其在业务关联中的应用

基于FP-树的FP-Growth算法在挖掘频繁模式过程中需要递归地产生大量的条件FP-树,效率不高,并且不太适合应用在移动通信业务交叉销售等具有业务约束的关联规则挖掘中。因此,提出了基于项目约束的频繁模式树ICFP-树和直接在此树上进行挖掘的新算法——ICFP-Mine。理论分析和实验结果表明,ICFP-Mine算法在内存占用和时间开销等方面比FP-Growth算法更优越,在移动通信业务交叉销售领域的应用中取得了较好的效果。     

FP-Growth算法的改进

基于FP树的FP-Growth算法在挖掘频繁模式过程中需要两次扫描事务集来建立FP树,这不仅降低了算法的效率,而且给数据库服务器带来负担.在原有经典FP-Growth算法的基础上,提出一种基于二维表的方法对原算法进行改进,改进算法通过使用二维向量记录频繁度仅需遍历一次事务集,从而省略FP-Growth算法在生成新条件FP树时对条件模式基的第一次遍历,大大缩短了建立FP树的时间.实验结果表明,该算法的改进优于经典算法.     

基于改进FP-tree的最大频繁项集挖掘算法

现有的最大频繁项集挖掘算法在挖掘过程中需要进行超集检测,基于FP-tree的算法需要递归的建立条件频繁模式树,挖掘效率不高.提出了一种基于改进FP-tree高效挖掘最大频繁项集的算法(MMFI).该算法修改了FP-tree结构并采用NBN策略,在挖掘过程中既不需要进行超集检测也不需要递归的建立条件频繁模式树.算法分析和实验结果表明,该算法是一种有效、快速的算法.     

基于FP-Growth的入侵检测研究

数据挖掘可以利用各种分析工具从海量数据中发现模型和数据间的关系并做出预测。为了解决入侵检测在不降低精度的同时提高检测速度的问题,提高算法的效率,将FP-Growth算法应用于入侵检测系统中,提出对FP-Growth算法改进FP-tree的头表结构并引入关键属性来挖掘原始审计数据中的频繁模式,实验结果表明改进后的算法比传统的关联算法在入侵检测中的应用效果更好。可以看出,将FP-Growth算法应用于入侵检测中是可行的。     

无项头表的FP-Growth算法

针对FP-Growth算法中频繁模式树的遍历低效问题,提出了一种无项头表的频繁模式增长算法。该算法利用递归回溯的方式遍历频繁模式树以求取条件模式基,解决了对同一树路径多次重复遍历的问题。从理论分析和实际挖掘能力两方面,将新算法与FP-Growth算法进行了对比。结果表明,新算法有效减少了条件模式基的搜索开销,使频繁模式挖掘的效率提高了2~5倍,在时间和空间性能上均优于FP-Growth算法。将该算法应用于通信告警关联规则挖掘,较快地挖掘出了关联规则结果,且正确规则的覆盖率达到了83.3%。     

基于循环十字链表的频繁模式挖掘算法

FP-growth算法是当前挖掘频繁模式的有效算法之一,但FP树的节点占用空间较大,长时间占用内存不释放,挖掘过程中需要产生大量的条件FP树,因而时空效率不理想.提出了一种循环十字链表结构用作存储事务数据库,而不生成FP树,在挖掘频繁项集的过程中,这种链表结构逐步缩小,减少了内存的使用率,通过构建排序的条件频繁模式树挖掘频繁项集.理论分析和实验表明基于这种结构的排序条件频繁模式树挖掘频繁项集具有较好的时空效率.     

基于特定模式树的用户行为关联规则挖掘算法

Apriori算法是关联规则挖掘的通用算法,它能满足绝大多数的应用,但是在某些方面,如入侵检测中挖掘用户活动记录等具有特定模式的记录时,计算最大频繁集会产生大量冗余的、无趣的规则.论文在Apriori算法的基础上针对上述情况提出了一种基于特定模式树的算法,消除无趣项的产生,通过递归挖掘模式树获得最大频繁集.整个过程只需要扫描一次数据库,进一步提高了算法效率.     

一种基于FP-Growth的频繁项目集并行挖掘算法

FP-Growth算法是基于FP树挖掘频繁项目集的经典算法,为提高FP-Growth算法挖掘大规模数据频繁项目集的效率,提出了一种基于FP-Growth的频繁项目集并行挖掘算法FPPM。该算法基于Map/Reduce并行模型,在每个计算节点上首先构造局部频繁模式树,并对之进行挖掘得到局部频繁项目集,然后合并局部频繁项目集以得到全局频繁项集,由于此时得到的结果并不完备,所以对合并后未达到最小支持度阈值的项目集,重新计算其支持数。介绍了FPPM算法的设计思想,测试了其性能。实验结果表明FPPM算法具有较好的可扩展性。     

基于压缩FP-树和数组技术的频繁模式挖掘算法

FP-growth算法是目前较高效的频繁模式挖掘算法之一.它只需扫描数据库两次,而且不需要产生和测试候选集,避免了这些费时的工作,因此该算法具有较高的效率.然而,FP-growth算法需要递归地生成大量的条件FP-树,这耗费了大量的存储空间和时间.综合已有的几项优势技术,提出了一种频繁模式挖掘算法CFPmine. 一是采用了基于压缩FP-树的约束子树的挖掘方法,避免在挖掘过程中生成条件FP-树,减少内存占用;二是采用基于数组的技术,减少FP-树的遍历时间,提高算法的效率.另外,在算法中还实现了统一的内存管理.实验结果表明,CFPmine是一个高效的频繁模式挖掘算法,其性能优于Apriori,Eclat和FP-growth算法,而需要的内存却少于FP-growth算法.     

基于节点表的FP-Growth算法改进

针对FP-Growth算法在构建FP-tree过程中需要对事务数据库扫描两次,同时在利用FP-tree挖掘频繁项集过程中产生大量条件模式基和条件模式树的问题,提出一种改进的FP-Growth算法。该算法只需扫描一次事务数据库,就能构建一棵无相同节点的新的FP-tree;弃用项头表,新增与新的FP-tree关联的节点表,将构建新的FP-tree过程中"多余"的项信息存入节点表;利用新的FP-tree和节点表挖掘频繁项集。实验结果表明了该算法的可行性和有效性,其提高了数据挖掘的效率。