最大频繁模式的快速挖掘与更新算法

挖掘和更新最大频繁模式是多种数据挖掘应用中的关键问题。之前的许多研究都是采用Apriori类的候选生成-检验方法或基于FP-Tree的方法,而产生大量候选和动态创建大量FP-Tree的代价太高,特别是在支持度阈值较小或存在长模式时。因此,文章提出了一种最大频繁模式的快速挖掘算法DMFP及更新算法IUMFP。DMFP算法利用前缀树压缩存放数据,并通过调整前缀树中节点信息和节点链直接在前缀树上采用深度优先的策略进行挖掘,而不需要创建条件模式树,从而大大提高了挖掘效率。算法IUMFP充分利用以前的挖掘结果减少发现更新数据中新的最大频繁模式的代价。     

一种最大频繁模式的快速挖掘算法

挖掘最大频繁模式是多种数据挖掘应用中的关键问题。提出一种挖掘最大频繁模式的快速算法,该算法利用前缀树压缩存放数据,并通过调整前缀树中节点信息和节点链直接在前缀树上采用深度优先的策略进行挖掘,而不需要创建条件模式树,从而大大提高了挖掘效率。     

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

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

一种基于压缩前缀树的频繁模式挖掘算法

针对FP-growth算法存在动态维护复杂、在挖掘过程中需要递归地创建大量的条件频繁模式树,导致时空效率不高等不足,本算法在压缩前缀树的基础上,通过调整树中节点信息和节点链,采用深度优先的策略挖掘频繁模式,无需任何附加的数据结构,极大地减少了系统资源的消耗,减少树的规模和遍历次数,挖掘效率大大提高。     

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

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

一种基于事务树的快速频繁项集挖掘与更新算法

挖掘频繁项集是数据挖掘研究中的关键问题。基于FP-Tree的挖掘及其更新算法无需生成候选项目集因而效率明显高于Aprbri类算法，但FP-Tree结构存在动态维护复杂、必须两次扫描数据库等缺点。因此，本文提出一种基于事务树Trans-Tree的新算法。该算法通过引入一种新结构一事务树Trans-Tree来压缩存放数据的相关信息且易于更新，挖掘算法只需对数据库扫描一次。而且更新算法只需对新增数据扫描一次，无需扫描原始数据，从而大大提高了频繁项集的挖掘和维护效率。     

约束频繁模式树及其构造方法研究

频繁模式挖掘是影响关联规则挖掘效率的主要步骤.采用一阶谓词逻辑作为用户感兴趣的背景知识表示技术,提出一种基于背景知识的频繁模式树-CFP-Tree(Constrain Frequent Pattern Tree),并给出了其构造算法CFPT-Construct,从而提高关联规则挖掘结果的针对性,降低了FP-Tree构造的复杂性,有效地解决了FP-Tree构造算法中数据存储的瓶颈问题.最后以国家天文台提供的天体光谱数据作为数据集,实验验证了算法的有效性、针对性和高效率.     

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

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

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

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

改进的频繁模式挖掘算法

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

一种基于F-矩阵的最大频繁项目集快速挖掘算法

最大频繁项目集挖掘是多种数据挖掘应用研究的一个重要方面,最大频繁项目集的快速挖掘算法研究是当前研究的热点。传统的最大频繁项目集挖掘算法要多遍扫描数据库并产生大量的候选项目集。为此,该文提出了基于F-矩阵的最大频繁项目集快速挖掘算法FMMFIBFM,FMMFIBFM采用FP-tree的存储结构,仅须扫描数据库两遍且不产生候选频繁项目集,有效地提高了频繁项目集的挖掘效率。实验结果表明,FMMFIBFM算法是有效可行的。     

基于频繁链表的频繁集的挖掘算法

自从1989年提出KDD以来,关联规则的挖掘一直是人工智能及数据库领域关注的焦点,尤其是项目决策者渴求的制胜法宝。挖掘关联规则的前提是频繁集的挖掘,目前典型的频繁集挖掘算法以Appriori算法为代表。在Appriori算法的基础上提出了一些可行的方法,所有这些算法不外乎达到两个目的:①在穷举的基础上,设法删除对关联规则不太有效的频繁集,减少候选频繁集的数量,达到提高挖掘算法性能的目的。②直接挖掘最大频繁集,以最大频繁集为基础挖掘感兴趣     

Towards a new approach for mining frequent itemsets on data stream

Mining frequent patterns on streaming data is a new challenging problem for the data mining community since data arrives sequentially in the form of continuous rapid streams. In this paper we propose a new approach for mining itemsets. Our approach has the following advantages: an efficient representation of items and a novel data structure to maintain frequent patterns coupled with a fast pruning strategy. At any time, users can issue requests for frequent itemsets over an arbitrary time interval. Furthermore our approach produces an approximate answer with an assurance that it will not bypass user-defined frequency and temporal thresholds. Finally the proposed method is analyzed by a series of experiments on different datasets.     

基于模式增长的不确定数据的频繁模式挖掘算法

为提高不确定数据频繁模式(FP)挖掘算法的时空效率,提出了基于最大概率的不确定频繁模式挖掘(UFPM-MP)算法。首先,利用事务项集中的最大概率值预估期望支持数;然后,使用该期望支持数与最小期望支持数阈值进行比较,以确定某一项集是否为候选频繁项集,并对候选项集建立子树以递归挖掘频繁模式。实验中,UFPM-MP算法与AT-Mine算法进行了对比,并在6个典型的数据集上进行实验验证。实验结果表明,UFPM-MP算法的时空效率得到了提高,稀疏数据集上提高约30%,稠密数据集上的效率提高更为明显(约3~4倍)。预估期望支持数的策略有效地减少了子树和头表项的数量,从而提高了算法的时空效率;且最小期望支持数越小,或需要挖掘的频繁模式越多的时候,算法的时间效率提高越多。     

一种直接在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.     

不产生候选的快速投影频繁模式树挖掘算法

1.概述近年来,对事务数据库、时序数据库和各种其它类型数据库中的频繁模式挖掘的研究越来越普及。许多先前的研究都是采用Apriori或类似的候选产生—检查迭代算法,使用候选项集来找频繁项集。这些算法都基于一种重要的反单调的Apriori性质:任何非频繁的(k—1)-项集都不可能是频繁k-项集的子集。因此,如果一个候选k-项集的(k—1)-子集不在频繁(k—1)-项集中,则该候选也不可能是频繁的,从而可     

基于哈希的B+树结构的频繁模式挖掘

提出了一种基干改进的B 树结构及一种新的数据挖掘算法，HB-Minc，该算法通过构造哈希函数，获得B 树的关键字，并在B 树的叶子结点上构建链表结构，记录卡H关关键字的项集及频数，这样在无需产生巨大的候选项集的情况下，挖掘出频繁模式，且具有较高的时间效率。