首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 172 毫秒
1.
基于改进FP-树的最大项目集挖掘算法*   总被引:1,自引:0,他引:1       下载免费PDF全文
挖掘最大频繁项目集是多种数据挖掘应用中的关键问题。FP-growth算法是目前最有效的频繁模式挖掘算法之一,其在挖掘最大项目集时要递归生成大量的条件FP-树,存在时空效率不高的问题。于是结合改进的FP-树,提出了一种快速挖掘最大项目集的算法。该算法利用改进的FP-树是单向的且每个节点只保留指向父节点的指针,可以节约大量的存储空间;同时引入项目序列集和它的基本操作,使挖掘最大频繁项目集时不生成含大量候选项目的集合或条件FP-树,可以快速地挖掘出所有的最大频繁项目集。实例分析证明所提出的算法是可行的。  相似文献   

2.
一种基于FP-tree的最大频繁项目集挖掘算法   总被引:7,自引:0,他引:7  
刘乃丽  李玉忱  马磊 《计算机应用》2005,25(5):998-1000
挖掘关联规则是数据挖掘领域中的重要研究内容,其中挖掘最大频繁项目集是挖掘关联规则中的关键问题之一,以前的许多挖掘最大频繁项目集算法是先生成候选,再进行检验,然而候选项目集产生的代价是很高的,尤其是存在大量长模式的时候。文中改进了FP-树结构,提出了一种基于FP-tree的快速挖掘最大频繁项目集的算法DMFIA-1,该算法不需要生成最大频繁候选项目集,比DMFIA算法挖掘最大频繁项目集的效率更高。改进的FP-树是单向的,每个结点只保留指向父结点的指针,这大约节省了三分之一的树空间。  相似文献   

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

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

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

6.
文章针对挖掘最大频繁项目集问题,提出了一个基于FP-树的快速算法DMFP,该算法引入了FP-树最大深度和非频繁2-项集,采用自顶向下和自底向上的双向搜索策略来预先对候选集进行有效剪枝,该算法的执行效率较其它同类算法有明显改进。  相似文献   

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

8.
一种改进的基于FP-树的最大目标频繁项集挖掘算法   总被引:1,自引:0,他引:1       下载免费PDF全文
目前,基于FP-树的最大频繁项集挖掘算法存在的一个问题是FP-树的规模过大,遍历树需耗费大量的运行时间,并且挖掘出来的很多频繁项集是用户不感兴趣的,过多的无用频繁 模式影响了挖掘的效率。本文提出一种排序紧缩非冗余的STFP-树,以及基于STFP-树的最大目标频繁项集挖掘算法STFP-MAX。该算法在满足用户需求的基础上有效地缩小了FP--树的规模,又加快了搜索的速度,从而提高了挖掘的效率。  相似文献   

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

10.
个性化书目推荐系统中的一个改进算法-FP_MAXMN算法   总被引:1,自引:0,他引:1  
郭亮 《福建电脑》2008,24(8):100-101
用挖掘最大频繁模式集代替挖掘频繁模式集是近年提出的一个新策略。本文主要是通过对基于FP_Tree的最大频繁模式挖掘问题的研究。根据频繁模式树的共享特性和最大频繁模式的特性给出了基于自底向上分治策略,先挖掘候选最大频繁模式再判断子集的算法--FP_MAXMN算法。  相似文献   

11.
Mining maximal frequent patterns (MFPs) is an approach that limits the number of frequent patterns (FPs) to help intelligent systems operate efficiently. Many approaches have been proposed for mining MFPs, but the complexity of the problem is enormous. Therefore, the run time and memory usage are still large. Recently, the N-list structure has been proposed and verified to be very effective for mining FPs, frequent closed patterns, and top-rank-k FPs. Therefore, this paper uses the N-list structure for mining MFPs. A pruning technique is also proposed to prune branches to reduce the search space. This technique is applied to an algorithm called INLA-MFP (improved N-list-based algorithm for mining maximal frequent patterns) for mining MFPs. Experiments were conducted to evaluate the effectiveness of the proposed algorithm. The experimental results show that INLA-MFP outperforms two state-of-the-art algorithms for mining MFPs.  相似文献   

12.
尹远  张昌  文凯  郑云俊 《计算机应用》2018,38(12):3438-3443
在数据挖掘中,通过挖掘最大频繁项集来代替挖掘频繁项集可以大大地提升系统的运行效率。针对现有的最大频繁项集挖掘算法的运行时间消耗仍然很大的问题,提出了一种基于DiffNodeset结构的最大频繁项集挖掘(DNMFIM)算法。首先,采用了一种新的数据结构DiffNodeset来实现求交集以及支持度的快速计算;其次,引入一种新的线性复杂度的连接方法来降低两个DiffNodeset在连接过程中的复杂度,避免了多次的无效计算;然后,将集合枚举树作为搜索空间,同时采用多种优化剪枝策略来缩小搜索空间;最后,再结合最大频繁项集挖掘算法(MAFIA)中所使用的超集检测技术来有效地提高算法的准确性。实验结果表明,DNMFIM算法在时间效率方面性能优于MAFIA与基于N-list的MAFIA(NB-MAFIA),该算法在不同类型数据集中进行最大频繁项集挖掘时均有良好的效果。  相似文献   

13.
基于改进FP-树的最大模式挖掘算法   总被引:2,自引:0,他引:2  
频繁模式挖掘是数据挖掘领域中的一个非常重要的分支,但是由于其内在的计算复杂性,挖掘密集型数据的频繁模式完全集非常困难而且数量往往大得惊人,难以理解和应用。最大频繁模式(最大模式)压缩隐含了所有的频繁模式,存储所占用的空间远远小于完全集,因而最大模式挖掘具有十分重要的意义。该文改进了传统的FP-树结构并提出了一种有效的基于改进FP-树的最大模式挖掘算法IFP-M ax;通过引入后缀子树的概念,算法在挖掘过程中不用生成最大频繁模式候选集,从而大大提高了算法的时间效率和空间可伸缩性。实验表明,IFP-M ax的挖掘速度比M AFIA和GenM ax大约快一个数量级。  相似文献   

14.
Mining sequential patterns by pattern-growth: the PrefixSpan approach   总被引:12,自引:0,他引:12  
Sequential pattern mining is an important data mining problem with broad applications. However, it is also a difficult problem since the mining may have to generate or examine a combinatorially explosive number of intermediate subsequences. Most of the previously developed sequential pattern mining methods, such as GSP, explore a candidate generation-and-test approach [R. Agrawal et al. (1994)] to reduce the number of candidates to be examined. However, this approach may not be efficient in mining large sequence databases having numerous patterns and/or long patterns. In this paper, we propose a projection-based, sequential pattern-growth approach for efficient mining of sequential patterns. In this approach, a sequence database is recursively projected into a set of smaller projected databases, and sequential patterns are grown in each projected database by exploring only locally frequent fragments. Based on an initial study of the pattern growth-based sequential pattern mining, FreeSpan [J. Han et al. (2000)], we propose a more efficient method, called PSP, which offers ordered growth and reduced projected databases. To further improve the performance, a pseudoprojection technique is developed in PrefixSpan. A comprehensive performance study shows that PrefixSpan, in most cases, outperforms the a priori-based algorithm GSP, FreeSpan, and SPADE [M. Zaki, (2001)] (a sequential pattern mining algorithm that adopts vertical data format), and PrefixSpan integrated with pseudoprojection is the fastest among all the tested algorithms. Furthermore, this mining methodology can be extended to mining sequential patterns with user-specified constraints. The high promise of the pattern-growth approach may lead to its further extension toward efficient mining of other kinds of frequent patterns, such as frequent substructures.  相似文献   

15.
挖掘最大频繁模式的新方法   总被引:11,自引:0,他引:11  
刘君强  孙晓莹  王勋  潘云鹤 《计算机学报》2004,27(10):1328-1334
由于其内在的计算复杂性,挖掘密集型数据集的频繁模式完全集非常困难,解决方案之一是挖掘最大频繁模式集.该文在频繁模式完全集挖掘算法Opportune Project基础上,提出了挖掘最大频繁模式的新算法MOP.它采用宽度与深度优先相结合的混合搜索策略,能恰当地选择不同的支持集表示和投影方法,将闭合性剪裁和一般性剪裁相结合,并适时前窥,实现搜索与剪裁效率最优化.实验表明,MOP效率是MaxMiner的2~8倍,比MAFIA高2个数量级以上.  相似文献   

16.
序列模式在基因分析、金融预测等方面有着重要的应用,是数据挖掘的一个主要分支,鉴于数据流应用的日益增多。本文在研究传统序列模式挖掘算法的基础上,提出了一种基于可扩展滑动窗口和贝叶斯概率过滤的面向数据流的序列模式挖掘算法(BMSP—DS算法),目的是简化序列模式发现的中间结果,提高挖掘效率.以便在小的存储空间和低的运算时间内快速发现流数据的频繁序列模式,同时算法也减少了因主观支持度取值不当对模式发现造成的负面影响,实验结果表明,该算法是可行、较优的.  相似文献   

17.
基于FP-tree的最大频繁项目集挖掘算法   总被引:1,自引:0,他引:1  
最大频繁项目集挖掘是数据挖掘领域最重要的基本问题之一,在分析已有算法的基础上提出了FP-MMFI算法,它是对FP-growth算法在最大频繁项目集挖掘上的扩展.提出了频繁路径的概念,用它可以有效地对FP-tree进行压缩和缩小搜索空间,同时使用投影的方法对超集检测进行了优化,减少了项目匹配的次数.最后实验结果表明,该算法在性能上优于已有的同类算法.  相似文献   

18.
MAFIA: a maximal frequent itemset algorithm   总被引:4,自引:0,他引:4  
We present a new algorithm for mining maximal frequent itemsets from a transactional database. The search strategy of the algorithm integrates a depth-first traversal of the itemset lattice with effective pruning mechanisms that significantly improve mining performance. Our implementation for support counting combines a vertical bitmap representation of the data with an efficient bitmap compression scheme. In a thorough experimental analysis, we isolate the effects of individual components of MAFIA including search space pruning techniques and adaptive compression. We also compare our performance with previous work by running tests on very different types of data sets. Our experiments show that MAFIA performs best when mining long itemsets and outperforms other algorithms on dense data by a factor of three to 30.  相似文献   

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

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号