基于COFI-Tree的N-最有兴趣项目集挖掘算法

BOMO算法采用递归构造条件子树,在挖掘大数据集时耗时较长,执行效率低,为了解决这一不足,文中给出一种基于COFI-Tree的挖掘N-最有兴趣项目集算法。算法采用COFI-Tree结构,无需递归构造条件子树FP-Tree,在同一时间内只有一个COFI-Tree在内存,并且有效地减少了其运算时间。通过对两种算法进行对比分析,实验结果得出：该算法比BOMO算法程序执行时间明显缩短;在挖掘大数据集时执行效率显著提高,尤其是k〈4时,性能最好。由此可见,改进后的算法是可行有效的。     

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

FP-growth算法是目前较高效的频繁模式挖掘算法之一,该算法不产生候选项集,但递归构造“条件FP-Tree”的CPU 开销和存储很大.为此提出了一种频繁模式挖掘算法IFPmine.首先,为了节省内存空间,采用了约束子树的挖掘方法;其次,采用了数组技术来减少树的遍历时间,从而提高算法的效率.实验结果表明,IFP算法是一种较有效的频繁模式挖掘算法,其挖掘效率优于STFP-树算法和FP-树算法,而需要的内存却少于STFP-树和FP-树算法.     

基于OWSFP-Tree的最大频繁项目集挖掘算法

为了解决FP-Max算法挖掘最大频繁项目集时递归生成条件模式树和超集检验的问题,提出了基于单向有序FP-Tree的NCFP-Max算法.该算法在挖掘过程中采用预剪枝策略减少挖掘结点,利用单向有序FP-Tree避免每次存储当前挖掘出的频繁项目集之前都需要超集检验,利用项目表格避免递归生成条件模式树减少时空资源.实验结果表明,在事务条数多、项的数量大的情况下,NCFP-Max算法的挖掘时间比FP-Max算法缩短了50％左右.     

基于FP-Tree的共享前缀频繁项集挖掘算法

在数据挖掘中发现关联规则是一个基本问题,而发现频繁项集是关联规则挖掘中最基本、最重要的问题。提出了基于FP-Tree的共享前缀频繁项集挖掘算法－FP-SPMA算法。构造FP-Tree来压缩事务数据库,通过共享前缀和前瞻剪枝快速减小候选项集,无需递归构造条件模式树,算法性能有明显的提高。     

一种基于排序的基因表达数据频繁闭合模式挖掘算法

频繁闭合模式是频繁模式的无损压缩,因此采用频繁闭合模式的挖掘来代替频繁模式挖掘,可以适当的压缩计算和存储开销。文中针对已有的面向基因表达数据集频繁闭合模式挖掘算法CARPENTER多次扫描数据集转置表带来巨大开销的缺陷,提出了基于排序的频繁闭合模式挖掘算法SFCP。在真实数据集上的实验结果表明,该算法效率比CARPENTER算法高。     

改进的频繁模式挖掘算法

FP-growth算法是关联规则挖掘中一种经典的算法,它不需要产生候选集,只需要扫描事务数据库两次来构建项目头表和FP-Tree.但该算法项节点查询比较耗时,而且要递归生成条件FP-tree,所以内存开销大.针对上述问题,文中提出了一种基于FP-growth的新的频繁模式挖掘算法MGFP-growth.其思想是:首先算法弃用项目头表,使用二维矩阵存储事务的信息,按照矩阵列进行分组,并建立parenttrace关系;最后利用存储在数组中的gourp信息可以快速的构建频繁模式树,从而进行频繁项集的挖掘.实验表明,该算法只对事务数据库扫描一次,同时利用分组将项存储,节省了内存空间,有效解决了传统算法的固有缺陷,提高了算法效率.     

基于FPMAX的最大频繁项目集挖掘改进算法

挖掘事务数据库中的最大频繁项目集是数据挖掘领域一个重要的研究方向。基于FP-tree的FPMAX算法是目前较为高效与稳定的最大频繁项目集挖掘算法之一。然而对于稠密数据库中的挖掘,FPMAX会产生大量的冗余递归过程,导致额外的条件FP-tree构造开销。而且在支持度较低时,FPMAX则会因用于超集检测的全局MFI-tree较为庞大而导致超集检测的性能下降。为此提出FPMAX的改进算法FPMAX-reduce,其通过采用基于事务共同后缀的前瞻剪枝策略来减少挖掘过程中的冗余递归过程。 当递归过程中产生的新条件FP-tree规模较小时,FPMAX-reduce通过构造条件MFI-tree来减小后续超集检测遍历的开销。性能试验表明,FPMAX-reduce算法通过有效的前瞻剪枝,在稠密事务数据库以及低支持度的情况下至多可将递归过程减少至原算法的一半以下,进而有效地提高了FPMAX算法的效率。     

基于FP-Tree快速挖掘频繁项集

发现频繁项集是关联规则挖掘中最基本、最重要的问题.目前已有两类频繁项集挖掘算法,然而由于其内在的复杂性,这一问题并未完全解决.提出了一种基于FP-Tree的频繁项集挖掘算法,该算法通过计算FP-Tree中非叶子节点的频繁子孙集和频繁前缀,组合生成频繁项集,无需递归构造每个频繁项的条件模式树,节约了时间和内存空间,算法性能在一定程度上得到了提高.     

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

基于FP-T ree的FP-M ax算法在挖掘最大频繁集时需多次递归建立条件模式树耗费大量存储空间,这大大降低了算法的挖掘效率。提出了一种基于改进FP-T ree的最大频繁集快速挖掘算法-FP-EM ax算法。该算法无需建立条件模式库大大减少了存储空间开销,采用预剪枝策略减少条件模式树的构造次数及子集检测次数,从而算法的挖掘效率大大提高。最后通过实验证明FP-EM ax算法在支持度较小的情况下较之于FP-M ax及同类算法具有更好的性能。     

基于粒度计算的频繁闭项目集挖掘

针对现有频繁闭项目集挖掘算法存在的不足,提出了一种基于粒度计算的频繁闭项目集挖掘算法。通过混合进制数的变化来生成候选项目集,避免使用了复杂的数据结构,减少了内存和CPU的开销;利用粒度计算的分而治之思想来计算频繁闭项目集的支持度,避免了多次重复扫描数据库,减少了计算复杂度和I/O开销。实验结果表明该算法比经典的频繁闭项目集挖掘算法快速而有效。     

FCIM:一种新的闭模式挖掘算法

闭模式挖掘在关联规则挖掘算法中获得了较广的应用,提出一种新的挖掘频繁闭项目集的算法,该算法可以充分利用挖掘过程中已获取的信息,直接使用FP-Tree产生闭项目集,实验结果表明该算法是有效的。     

基于矩阵伪投影策略的频繁项集挖掘方法

挖掘频繁项集是数据挖掘应用中关键的问题。经典的FP-growth算法利用FP-tree有效的压缩了数据集的规模,但是在挖掘过程中需要反复递归构造条件FP-tree成为限制算法效率的瓶颈。本文通过将FP-tree映射成矩阵,通过在矩阵自身上进行伪投影得到条件模式阵,避免了递归构造FP-tree,从而节约了内存消耗和计算时间。     

Fast and memory efficient mining of frequent closed itemsets

This paper presents a new scalable algorithm for discovering closed frequent itemsets, a lossless and condensed representation of all the frequent itemsets that can be mined from a transactional database. Our algorithm exploits a divide-and-conquer approach and a bitwise vertical representation of the database and adopts a particular visit and partitioning strategy of the search space based on an original theoretical framework, which formalizes the problem of closed itemsets mining in detail. The algorithm adopts several optimizations aimed to save both space and time in computing itemset closures and their supports. In particular, since one of the main problems in this type of algorithms is the multiple generation of the same closed itemset, we propose a new effective and memory-efficient pruning technique, which, unlike other previous proposals, does not require the whole set of closed patterns mined so far to be kept in the main memory. This technique also permits each visited partition of the search space to be mined independently in any order and, thus, also in parallel. The tests conducted on many publicly available data sets show that our algorithm is scalable and outperforms other state-of-the-art algorithms like CLOSET+ and FP-CLOSE, in some cases by more than one order of magnitude. More importantly, the performance improvements become more and more significant as the support threshold is decreased.     

在单向FP-tree上挖掘频繁闭项集

频繁闭项集提供了频繁项集的一种完整的、最小表示。针对稠密数据集,提出一种基于单向FP-tree的频繁闭项集挖掘算法Unid_FP-FCI。该算法在挖掘过程中只生成被约束子树,而它是一种虚拟的树结构,在原有的单向FP-tree基础上用三个很小的数组来表示,因而避免了以往算法需递归构造条件FP-tree来计算频繁闭项集的弊端,极大地降低了内存空间和时间开销,提高了挖掘效率。     

An improved frequent pattern growth method for mining association rules

Many algorithms have been proposed to efficiently mine association rules. One of the most important approaches is FP-growth. Without candidate generation, FP-growth proposes an algorithm to compress information needed for mining frequent itemsets in FP-tree and recursively constructs FP-trees to find all frequent itemsets. Performance results have demonstrated that the FP-growth method performs extremely well. In this paper, we propose the IFP-growth (improved FP-growth) algorithm to improve the performance of FP-growth. There are three major features of IFP-growth. First, it employs an address-table structure to lower the complexity of forming the entire FP-tree. Second, it uses a new structure called FP-tree⁺ to reduce the need for building conditional FP-trees recursively. Third, by using address-table and FP-tree⁺ the proposed algorithm has less memory requirement and better performance in comparison with FP-tree based algorithms. The experimental results show that the IFP-growth requires relatively little memory space during the mining process. Even when the minimum support is low, the space needed by IFP-growth is about one half of that of FP-growth and about one fourth of that of nonordfp algorithm. As to the execution time, our method outperforms FP-growth by one to 300 times under different minimum supports. The proposed algorithm also outperforms nonordfp algorithm in most cases. As a result, IFP-growth is very suitable for high performance applications.     

在单向FP—tree上挖掘最大频繁项集

针对稠密数据集．提出一种基于单向FP—tree的最大频繁项集挖掘算法Unid_FP-Max2。该算法在挖掘过程中只生成被约束子树,而它是一种虚拟的树结构,在原有的单向FP—tree基础上用三个很小的数组来表示．因而避免了以往算法需递归构造条件FP—tree来计算最大频繁项集的弊端,极大的降低了内存空间和时间开销,提高了挖掘效率。实验表明,与FP—Max算法相比。算法的效率提高了1倍以上。     

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

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