基于改进的FP-tree的频繁模式挖掘算法

FP-growth算法是一种基于FP-tree数据结构的高效的频繁模式挖掘算法,它不产生候选集。构造频繁模式树FP-tree需扫描数据库两次,在第二遍扫描中还扫描了那些仅包含了非频繁项的事务,针对此问题,在深入分析了FP-tree特性的基础上, 改进了FP-tree构造过程,同时用一种基于Hash表的辅助存储结构,节省了项目查找时间,提高了挖掘效率。     

基于FS-tree的频繁模式挖掘算法

关联规则挖掘是数据挖掘中的一个重要研究方向,用于发现项集之间的关联性。FP-growth算法通过构造FP-tree产生频繁集,由于其不生成候选集从而大大降低了搜索开销,其缺点是占用大量的内存空间。基于FP-growth的算法思想,提出基于FS-tree（频繁1-项子树）的频繁模式挖掘算法,通过将FP-tree拆分为多棵FS-tree,使算法的空间复杂度明显减小。实验表明,该算法是有效的。     

基于MapReduce的频繁项集并行挖掘算法

现有FP-growth频繁集挖掘算法在处理大数据时存在时空效率不高的问题,且内存的使用随着数据的增加已经无法满足把待挖掘数据压缩存储在单个内存中,为此,提出一种基于MapReduce模型的频繁项集并行挖掘算法。该算法采用一种基于key/value键值对直接扫描value寻找条件模式基的方式,同时通过在原有FP-tree树节点中新增一个带频繁项前缀的域空间来构建一颗新的条件模式树NFP-tree,使得对一项频繁项的条件模式基进行一次建树一次遍历就可以得到相应的频繁项集。对所提出的算法在Hadoop平台进行了验证与分析,实验结果表明该算法效率较传统FP-growth算法平均提高16.6%。     

高效FP-TREE创建算法

如何从大型数据库中挖掘关联规则是数据挖掘的一个重要的问题。FP-growth是一个著名的不产生候选集的高效频繁模式挖掘算法，它使用专门的数据结构FP-tree。为了进一步提高FP-grown算法效率，提出一个新的并行算法PFPTC，可以并发地创建子FP-tree，以及一个FP-tree合并算法称作FP-merge，可以将两个FP-tree合并为一个。     

改进的频繁模式挖掘算法

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

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

对于频繁项集挖掘,采用一种FP-数组技术来减少FP-tree的遍历时间,减少数据集的扫描次数,在此基础上提出了一种基于FP-tree进行频繁项集挖掘的FP-growth+算法,提高了算法的效率。最后的实验证明了该算法的有效性。     

一种基于升序FP-tree的频繁模式挖掘算法

本文提出了一种基于升序FP-tree的频繁模式挖掘算法,该算法按照支持度升序构造升序FP-tree,并通过在其中搜索扩展频繁集及归并子树来挖据频繁模式。实验表明,与FP-growth算法相比,算法的挖掘速度提高了将近2倍,此外新算法还具有比较好的伸缩性。     

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

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

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

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

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

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

在FP-树中挖掘频繁模式而不生成条件FP-树

FP-growth算法是目前已发表的最有效的频繁模式挖掘算法之一．然而，由于在挖掘频繁模式时需要递归地生成大量的条件FP-树，其时空效率仍然不够高．改进了FP-树结构，提出了一种基于被约束子树挖掘频繁项集的有效算法．改进的FP-树是单向的，每个结点只保留指向父结点的指针，这大约节省了三分之一的树空间．通过引入被约束子树(可以用3个很小的数组表示)，算法在挖掘频繁模式时不生成条件FP-树，从而大大提高了频繁模式挖掘的时空效率．实验表明，与FP-growth算法相比，算法的挖掘速度提高了1倍以上，而所需的存储空间减少了一半．此外，随着数据库规模的增大，算法具有很好的可伸缩性．对于稠密数据集，算法也具有良好的性能．     

基于改进FP-树的最大项目集挖掘算法*

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题。FP-growth算法是目前最有效的频繁模式挖掘算法之一,其在挖掘最大项目集时要递归生成大量的条件FP-树,存在时空效率不高的问题。于是结合改进的FP-树,提出了一种快速挖掘最大项目集的算法。该算法利用改进的FP-树是单向的且每个节点只保留指向父节点的指针,可以节约大量的存储空间;同时引入项目序列集和它的基本操作,使挖掘最大频繁项目集时不生成含大量候选项目的集合或条件FP-树,可以快速地挖掘出所有的最大频繁项目集。实例分析证明所提出的算法是可行的。     

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-树的频繁模式高效挖掘算法

FP-growth算法是目前较高效的频繁模式挖掘算法之一。在FP-growth算法中,FP-树及条件FP-树的构造和遍历占了算法绝大部分的时间,如果能减少这方面的时间,则有望进一步改善算法的效率。本文给出了一个频繁模式挖掘算法SFP-growth。算法通过将FP-树有序化及采用高效排序算法等措施来提高FP-树构造的效率,从而使算法达到较高的效率。实验结果表明,SFP-growth是一个高效的频繁模式挖掘算法,其性能优于Apriori、Eclat和FP-growtn算法。     

一种改进的加权频繁项集挖掘算法

FP-growth算法是挖掘频繁项集的经典算法,它利用FP-树这种紧凑的数据结构存储事务数据库与频繁项集挖掘相关的全部信息,但对于挖掘加权频繁项集并不合适。分析了现有加权频繁项集挖掘算法中存在的问题,并对FP-树进行改进,构造新的加权FP-树,提出了有效挖掘加权频繁项集的算法。最后举例说明了算法的挖掘过程,并通过实验验证了算法的有效性。     

新型频繁项集快速挖掘模式树的方法*

在FP_growth算法中,FP_tree及条件FP_tree的构造和遍历占了算法绝大部分的时间,为了能减少这方面的时间,提出了一种新型快速的方法——改进的层次频繁模式树（inproved hierarchy FP_tree,IHFP_tree）。该方法采用首先对数据库扫描一遍,产生每个项的等价类;然后去掉不频繁项,对等价类进行重新改写;最后再创建FP_tree。引入层次频繁模式的概念,在挖掘过程中大大提高了算法的时空效率。与其他频繁模式挖掘的常用算法进行了时间复杂度和空间复杂度的比较,实验表明,IHFP     

一种直接在Trans-树中挖掘频繁模式的新算法

Frequent pattern mining plays an essential role in many important data mining tasks. FP-growth is a very efficient algorithm for frequent pattern mining. However, it still suffers from creating conditional FP-tree separately and recursively during the mining process. In this paper, we propose a new algorithm, called Least-Item-First Pat-tern Growth (LIFPG), for mining frequent patterns. LIFPG mines frequent patterns directly in Trans-tree withoutusing any additional data structures. The key idea is that least items are always considered first when the current pat-tern growth. By this way, conditional sub-tree can be created directly in Trans-tree by adjusting node-links and re-counting counts of some nodes. Experiments show that, in comparison with FP-Growth, our algorithm is about fourtimes faster and saves half of memory;it also has good time and space scalability with the number of transactions,and has an excellent performance in dense dataset mining as well.