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

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

基于FP-tree最大频繁项集的FP-MFI算法研究

由于基于Fp-tree的DMFIA算法在生成最大频繁项目集时会产生大量的候选频繁项集,通过改进传统的FP-tree结构,并提出了一种基于改进FP-tree的最大频繁模式挖掘算法FP-MFI,该算法不需要生成最大频繁候选项目集,改进的FP-tree是单向的,每个节点只保留了指向父节点的指针,可节约树空间.实验结果表明FP-MFI算法在数据库中频繁项目很多,而每一个事务中频繁项目很少的情况下,比同样基于FP-tree的DMFIA算法挖掘最大频繁项目集的效率更高.     

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

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

关联规则中基于降维的最大频繁模式挖掘算法

基于FP-tree的最大频繁模式挖掘算法是目前较为高效的频繁模式挖掘算法,针对这些算法需要递归生成条件FP-tree、产生大量候选最大频繁项集等问题,在分析FPMax、DMFIA算法的基础上,提出基于降维的最大频繁模式挖掘算法(BDRFI)。该算法改传统的FP-tree为数字频繁模式树DFP-tree,提高了超集检验的效率;采用的预测剪枝策略减少了挖掘的次数;基于降低项集维度的挖掘方式,减少了候选项的数目,避免了递归地产生条件频繁模式树,提高了算法的效率。实验结果表明,BDRFI的效率是同类算法的2~8倍。     

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

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

有效的不确定数据概率频繁项集挖掘算法

针对已有概率频繁项集挖掘算法采用模式增长的方式构建树时产生大量树节点,导致内存空间占用较大以及发现概率频繁项集效率低等问题,提出了改进的不确定数据频繁模式增长(PUFP-Growth)算法。该算法通过逐条读取不确定事务数据库中数据,构造类似频繁模式树(FP-Tree)的紧凑树结构,同时更新项头表中保存所有尾节点相同项集的期望值的动态数组。当所有事务数据插入到改进的不确定数据频繁模式树(PUFP-Tree)中以后,通过遍历数组得到所有的概率频繁项集。最后通过实验结果和理论分析表明:PUFP-Growth算法可以有效地发现概率频繁项集;与不确定数据频繁模式增长(UF-Growth)算法和压缩的不确定频繁模式挖掘(CUFP-Mine)算法相比,提出的PUFP-Growth算法能够提高不确定数据概率频繁项集挖掘的效率,并且减少了内存空间的使用。     

一种基于FP-tree的频繁项集增量更新算法

针对频繁项集增量更新的问题,提出算法FIU。该算法将保存了数据库事务的FP-tree存储在磁盘上,当挖掘新支持度阈值的频繁项集时,只需从磁盘上读入FP-tree,再挖掘新支持度阈值下的频繁项集。当新增数据库事务记录后,首先建立新项目表,然后根据新项目表建立新增事务记录的FP-tree,读入存储在磁盘上的FP-tree,抽取出所有的事务记录,再插入到新FP-tree中．从而得到增量更新后的FP-tree。最后在增量更新后的FP-tree上挖掘频繁项集。实验证明,FIU算法执行时间不随数据库大小变化,与其他算法相比有较好的性能。     

改进的频繁项集挖掘算法及其应用研究

频繁模式增长(FP-growth)算法是挖掘频繁项集的经典算法,解决了挖掘频繁项集时需多次扫描数据库且产生大量候选项集的问题,但大多数基于FP-growth思想的算法在生成频繁项集时存在过程复杂、占用空间多的问题。为此,提出一种基于前序完全构造链表(PF-List)的频繁项集挖掘算法(PFLFIM)。该算法使用PF-List表示项集,通过简单比较和连接两个PF-List挖掘频繁项集,避免复杂的连接操作;使用包含索引、提前停止交集和父子等价策略对搜索空间进行优化,减少空间占用。通过实验验证,相比于FIN算法和negFIN算法,该算法在运行时间和内存占用方面具有更好的性能。将该算法应用于高校人力资源管理系统中进行关联规则挖掘,寻找影响人才发展的因素,为高校人才引进和选拔提供决策支持。     

MLFI：新的最大长度频繁项集挖掘方法

在理解现有的最大长度频繁项集挖掘问题的定义,探索最大长度频繁项集的几个具体应用后,提出了一种新的基于FP-tree（Frequent Pattern tree）结构的最大长度频繁项集挖掘方法——MLFI算法。该算法仅对初始的FP-tree实现遍历操作,从而完成对最大长度频繁项集的挖掘。在算法整个执行过程中,仅用到了一棵初始的FP-tree。理论分析和实验证明,该算法加快了挖掘速度,提高了挖掘效率。     

基于有序FP-tree的最大长度频繁项集挖掘算法

频繁项集的挖掘受到大量候选频繁项集和较高计算花费的限制,只挖掘最大长度频繁项集已满足很多应用。提出一种基于有序FP-tree结构挖掘最大长度频繁项集的算法。即对有序FP-tree的头表进行改造,增加一个max-level域,记录该项在有序FP-tree中的最大高度。挖掘时仅对max-level 大于等于已有最大长度频繁项集长度的项进行遍历,不产生条件模式基,无需递归构造条件FP-tree,且计算出最大长度频繁项集的支持度。实验结果表明该算法挖掘效率高、速度快。     

A new algorithm for fast mining frequent itemsets using N-lists

Mining frequent itemsets has emerged as a fundamental problem in data mining and plays an essential role in many important data mining tasks.In this paper,we propose a novel vertical data representation called N-list,which originates from an FP-tree-like coding prefix tree called PPC-tree that stores crucial information about frequent itemsets.Based on the N-list data structure,we develop an efficient mining algorithm,PrePost,for mining all frequent itemsets.Efficiency of PrePost is achieved by the following three reasons.First,N-list is compact since transactions with common prefixes share the same nodes of the PPC-tree.Second,the counting of itemsets’ supports is transformed into the intersection of N-lists and the complexity of intersecting two N-lists can be reduced to O(m + n) by an efficient strategy,where m and n are the cardinalities of the two N-lists respectively.Third,PrePost can directly find frequent itemsets without generating candidate itemsets in some cases by making use of the single path property of N-list.We have experimentally evaluated PrePost against four state-of-the-art algorithms for mining frequent itemsets on a variety of real and synthetic datasets.The experimental results show that the PrePost algorithm is the fastest in most cases.Even though the algorithm consumes more memory when the datasets are sparse,it is still the fastest one.     

基于B-list的快速频繁模式挖掘算法

针对现有的频繁模式挖掘算法存在建树复杂、挖掘效率低等问题,提出一种基于构造链表（B-list）的频繁模式挖掘（BLFPM）算法。BLFPM使用一种新的数据结构B-list表示频繁项集,通过连接两个k-1-频繁项集的B-list可以快速得到k-项集的支持度,避免了多次扫描数据库;针对连接两个B-list时间复杂度高的问题,给出了一种线性时间复杂度的连接方法,提高了BLFPM的时间效率;同时,BLFPM采用集合枚举树代表搜索空间,并使用子集非频繁剪枝策略,减小了频繁模式挖掘的搜索空间,提高了算法的执行速度。实验结果表明,与NSFI算法和prepost算法相比,BLFPM的时间效率提高约12%到29%,空间效率提高约10%到24%,对稀疏数据库或稠密数据库进行频繁模式挖掘均可以得到良好的效果。     

Fast mining frequent itemsets using Nodesets

Node-list and N-list, two novel data structure proposed in recent years, have been proven to be very efficient for mining frequent itemsets. The main problem of these structures is that they both need to encode each node of a PPC-tree with pre-order and post-order code. This causes that they are memory-consuming and inconvenient to mine frequent itemsets. In this paper, we propose Nodeset, a more efficient data structure, for mining frequent itemsets. Nodesets require only the pre-order (or post-order code) of each node, which makes it saves half of memory compared with N-lists and Node-lists. Based on Nodesets, we present an efficient algorithm called FIN to mining frequent itemsets. For evaluating the performance of FIN, we have conduct experiments to compare it with PrePost and FP-growth¹, two state-of-the-art algorithms, on a variety of real and synthetic datasets. The experimental results show that FIN is high performance on both running time and memory usage.     

一种基于频繁模式树的最大频繁项目集挖掘算法

目前提出的频繁项目集挖掘算法大多基于Apriori算法思想,这类算法会产生巨大的候选集并且重复扫描数据库.针对这一问题,给出一种基于频繁模式树的最大频繁项目集挖掘算法FP-MFIA,该算法利用频繁模式树对最大频繁项目集进行检索,通过位图建树的方法有效的减少了扫描数据库的次数,从而节省了CPU的执行时间.另外,此算法运用独特的最大频繁项目集判断策略,同时运用投影技术进行超集检测,提高了遍历的效率,实验结果表明该算法是快速有效的.     

基于FP-Tree的最大频繁项目集挖掘及更新算法

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题,之前的很多研究都是采用Apriori类的候选项目集生成-检验方法.然而,候选项目集产生的代价是很高的,尤其是在存在大量强模式和/或长模式的时候.提出了一种快速的基于频繁模式树(FP-tree)的最大频繁项目集挖掘DMFIA(discover maximum frequent itemsets algorithm)及其更新算法UMFIA(update maximum frequent itemsets algorithm).算法UMFIA将充分利用以前的挖掘结果来减少在更新的数据库中发现新的最大频繁项目集的费用.     

MAXFP-M iner: 利用FP- tree 快速挖掘最大频繁项集

为提高频繁项集的挖掘效率，提出了最大频繁项集树的概念和基于FP-tree的最大频繁项集挖掘算法MAXFP-Miner，首先建立了FP-tree，在此基础上建立最大频繁项集树MAXFP-tree，MAXFP-tree中包含了所有最大频繁项集，缩小了搜索空间，提高了算法的效率，算法分析和实验表明，该算法特别适合于挖掘稠密型及具有长频繁项集的数据集。     

基于FP树的全局最大频繁项集挖掘算法

挖掘最大频繁项集是多种数据挖掘应用了更新最大频繁候选项集集合,需要反复地扫描整个数据库,而且大部分算法是单机算法,全局最大频繁项集挖掘算法并不多见.为此提出MGMF算法,该算法利用FP-树结构,类似FP-树挖掘方法,一遍就可以挖掘出所有的最大频繁项集,并且超集检测非常简单、快捷.另外MGMF算法采用了分布式PDDM算法播报消息的思想,具有很好的拓展性和并行性.实验证明MGMF算法是有效可行的.     

改进的基于频繁模式树的最大频繁项集挖掘算法——FP-MFIA

针对最大频繁项目集挖掘算法(DMFIA)当候选项目集维数高而最大频繁项目集维数较低的情况下要产生大量的候选项目集的缺点,提出了一种改进的基于频繁模式树(FP-tree)结构的最大频繁项目集挖掘算法--FP-MFIA。该算法根据FP-tree的项目头表,采用自底向上的搜索策略逐层挖掘最大频繁项目集,从而加速每次对候选集计数的操作。在挖掘时根据每层的条件模式基产生维数较低的非频繁项目集,尽早对候选项目集进行剪枝和降维,可大量减少候选项目集的数量。同时在挖掘时充分利用最大频繁项集的性质,减少搜索空间。通过算法在不同支持度下挖掘时间的对比可知,算法FP-MFIA在最小支持度较低的情况下时间效率是DMFIA以及基于降维的最大频繁模式挖掘算法(BDRFI)的2倍以上,说明FP-MFIA在候选集维数较高的时候优势明显。     

基于频繁模式树的分布式关联规则挖掘算法

提出一种基于频繁模式树的分布式关联规则挖掘算法(DMARF).DMARF算法设置了中心结点,利用局部频繁模式树让各计算机结点快速获取局部频繁项集,然后与中心结点交互实现数据汇总,最终获得全局频繁项集.DMARF算法采用顶部和底部策略,能大幅减少候选项集,降低通信量.理论分析和实验结果均表明了DMARF算法是快速而有效的.