FP-growth算法的一种优化实现

研究工作者已经提出了许多对事务数据库中频繁模式、关联规则的挖掘算法.早期算法有Apriori算法,然而该算法利用候选项集找频繁项集,而候选项集的产生往往是非常耗时的.JianweiHan等人提出了一种改进的算法,FP-growth算法.该算法不产生候选项集,效率比Apriori算法提高了近一个数量级.在描述FP-growth算法的基础上,具体讨论了如何优化数据结构,有效的实现该算法.     

Mining Maximal Frequent Patterns in a Unidirectional FP-tree

Becausemining complete set of frequent patterns from dense database could be impractical, an interesting alternative has been proposed recently. Instead of mining the complete set of frequent patterns, the new model only finds out the maximal frequent patterns, which can generate all frequent patterns. FP-growth algorithm is one of the most efficient frequent-pattern mining methods published so far. However,because FP-tree and conditional FP-trees must be two-way traversable, a great deal memory is needed in process of mining. This paper proposes an efficient algorithm Unid_FP-Max for mining maximal frequent patterns based on unidirectional FP-tree. Because of generation method of unidirectional FP-tree and conditional unidirectional FP-trees, the algorithm reduces the space consumption to the fullest extent. With the development of two techniques：single path pruning and header table pruning which can cut down many conditional unidirectional FP-trees generated recursively in mining process, Unid_ FP-Max further lowers the expense of time and space.     

基于FP_tree的最大频繁模式挖掘算法的改进

基于条件模式树的最大频繁模式挖掘算法在挖掘过程中将扫描事务数据库两次,且产生了大量的候选项目集,产生最大频繁模式过程中比较次数较多,总体效率较低.提出改进后的最大频繁模式挖掘策略,利用二维表保存事务出现项目的情况,通过最大频繁模式的相关性质减少了挖掘的项数及产生的频繁模式集,减少比较的次数.     

半结构化文档数据流的快速频繁模式挖掘

为了提高半结构化文档数据流的挖掘效率,对原有挖掘算法StreamT进行了改进,提出了一种半结构化文档数据流的快速频繁模式挖掘算法--FStreamT.该算法针对利用集合存储候选频繁模式效率较低的缺点,采用枚举树存储候选频繁模式,可以有效地提高对候选频繁模式集合进行查找和更新的效率,同时利用频繁模式的单调性和枚举树的特点减小了维护负边界的搜索空间,从而提高了整个算法的效率.理论分析和实验结果表明,算法FStreamT与算法StreamT相比具有较高的效率,是有效可行的.     

An efficient hybrid algorithm for mining Web frequent access patterns

We propose an cfficienl hybrid algorithm WDHP in this paper for mining frequent access patterns. WDHP adopts the techniques of DHP optimize its performance, which is using hash the to filter candidate set and trimming database. Whenever the database is trimmed to a size tess than a specified threshold, the algorithm puts the database into main memory By constructing a tree. and finds frequent patterns on the tree. The experiment shows that WDHP outperform algorithm DHP and main memory basedalgorithm WAP in execution efficieucy.     

一种基于模式增长的频繁模式挖掘算法

提出了一种基于模式增长的频繁模式挖掘算法(简称为PGMiner算法).这种算法是一种深度挖掘的算法,不产生任选项集,便于发现较长的模式,避免了Apriori和FP-growth方法存在的问题.通过一种简单的索引结构在映射数据库中不断地增加模式长度.这种索引结构占用较少的内存,使得这种基于内存的算法有很高的执行效率.采用现实数据集以及IBM人工数据集对PGMiner算法进行测试.试验结果显示,对于一般类型的特别是较为稀疏的数据集,PGMiner算法比Apriori和FP-growth方法有更好的性能.     

一种基于频繁模式有向无环图的数据流频繁模式挖掘算法

频繁模式挖掘中基于FP-growth的算法需要扫描两次事务数据库,预先给定支持度,且不支持时间敏感型数据。本文提出了一种基于频繁模式有向无环图的数据流频繁模式挖掘算法,它根据事务到来的时间给每个事务一个序号,每个事务中的数据项在存储前按数据项的顺序进行调整,频繁模式有向无环图的构建遵循这个顺序并用序号来记录事务与数据项的包含关系,模式增长过程只需要增加有向边上的序号。通过逆向遍历带有相同序号的有向边,产生条件模式基,根据动态定义的阈值抽取条件模式基信息,一次扫描数据库得到频繁模式。实验结果表明,本文算法的执行效率优于FP-growth算法,且存储节点的数目明显减少。     

基于FP-tree挖掘密集型数据最大频繁模式算法

Fp-growth算法是当前挖掘频繁项目集算法中速度最快,应用最广,并且不需要候选集的一种挖掘关联规则的算法.但是,Fp-growth算法也存在着算法结构复杂和空间利用率低等缺点.在FP-tree结构的基础上提出了密集型数据最大频繁模式挖掘算法FP-DMax.算法FP-DMax只需要2次扫描数据库,在挖掘过程中不产生候选项集,大大提高了算法的时空效率.实验表明,算法FP-DMax在挖掘密集型数据最大频繁模式方面是高效的.     

基于合并FP树的频繁模式挖掘算法

FP-growth算法是一个挖掘频繁模式的有效算法,但它在挖掘过程中需要产生大量的条件FP树,因此其时空效率不够理想。提出了DFP-mine算法,通过在改进的FP树上合并子树来挖掘频繁模式,并在挖掘过程中结合了自顶向下和自底向上的双向搜索策略。理论分析和实验表明本文提出的算法具有较好的时空效率。     

基于格的快速频繁项集挖掘算法

随着数据库规模的增加或支持度阈值的减少,频繁模式的数量将以指数形式增长,FP-growth算法运行的时空效率将大为降低.本文提出一种基于格的快速频繁项集挖掘算法LFP-growth,算法利用等价关系将原来的搜索空间（格）划分成若干个较小的子空间（子格）,通过子格间的迭代分解,将对网格P(I)的频繁项集挖掘转化为对多个子格的并集进行的约束频繁项集挖掘.实验结果和理论分析表明,在挖掘大型数据库时,LFP-growth算法的时间和空间性能均优于FP-growth算法.     

基于投影数据库的序列模式挖掘增量式更新算法

针对序列模式挖掘中的增量挖掘问题,提出一种序列模式更新算法ISPBP.算法引入序列数据库结构来存储从原始数据库中挖掘出的所有项、最大频繁模式以及它们的支持数,采用间接拼接方法,只需处理增量数据库,避免了对更新后数据库的重新计算.对于因增量数据库新产生的频繁模式,利用了在增量数据库中出现的频繁项集来减小投影数据库,进一步提高了算法的效率.理论分析和实验表明,算法是有效可行的,并且增量数据库越大,算法在效率上的优越性越明显,算法ISPBP优于传统增量式更新算法.     

基于最频繁项提取和候选集剪枝的THIMFUP算法

针对FBCM(基于矩阵压缩FUP(fast update algorithm))算法在项集挖掘过程中存在频繁扫描原频繁项集库, 并生成大量候选集的问题, 提出一种通过提取数据库中最频繁项的方法, 以降低对原频繁项集库的扫描次数； 并通过候选集剪枝思想, 减少算法整体运行过程中的候选集生成, 以提高频繁项集的挖掘速度. 实验结果表明, 在相同实验条件下, 该算法的效率比FBCM算法效率提高15%以上, 最高达60%.     

基于改进频繁模式树的最大频繁项目集更新挖掘算法

在挖掘最大频繁项目集的过程中,通过改变最小支持度阈值可以挖掘更有用的最大频繁项目集,为此提出了一种最大频繁项目集更新挖掘算法UAMMFI(Updating Algorithm for Mining Maximal Frequent Itemsets)。算法基于改进后的频繁模式树结构,在更新挖掘过程中,不需产生候选项目集和条件模式树,并且充分利用先前已挖掘的最大频繁项目集中包含的信息,快速更新挖掘出最小支持度阈值变化后的最大频繁项目集。实验结果表明,算法能够高效更新挖掘最大频繁项目集。     

一种基于MapReduce的并行FP-growth算法

FP-growth算法是不产生候选集的关联规则挖掘算法,在许多领域中具有很高的实际应用价值。然而经典的FP-growth算法是内存驻留算法,只能处理小数据集,在面对海量数据集时显得无能为力。对经典FP-growth算法中FP-tree的结构和挖掘过程进行了改进,分析了FP-tree单路径和多路径的不同挖掘方法,提出了一个剪枝策略,在挖掘过程中减少了部分分支的迭代次数。然后利用云计算的MapReduce编程技术,对改进的FP-growth算法的各个步骤并行化。实验结果表明改进的算法在处理不同的数据集时有一定的优势,然后经过MapReduce模型并行化后,提高了对海量数据的处理能力和效率,并且具有较好的加速比和良好的扩展性。     

基于数组的关联规则挖掘算法的研究

频繁项集的挖掘效率是关联规则产生的关键.针对经典Apriori算法的瓶颈,提出一种改进算法,通过数组结构来保存项集信息,只须扫描一遍数据库减少了时间开销.在自连接前进行项目计数,减少参加连接的项集数量,减少了候选项集的数量.通过实例证明,改进算法的效率更高.     

基于最长前缀频繁子路径树的Web日志挖掘算法

现有的Web日志频繁访问路径挖掘算法往往不能在追求时间效率的同时准确挖掘出符合用户浏览顺序的频繁路径.提出了有效挖掘Web日志中频繁访问路径的算法,将事务数据库转换为Web访问路径树,根据支持度进行剪枝构造最长前缀频繁子路径树,然后进行频繁路径挖掘,实验证实了此方法的有效性,并分析了支持度设置对频繁路径生成的影响.     

基于模式矩阵的FP-growth改进算法

数据挖掘中关联挖掘算法比较典型的有Apriori和FP—growth算法．实验和研究证明FP—growth算法优于Apriori算法．但是针对大型数据库这两种算法都存在着较大缺陷，不仅要两次或多次扫描数据库，而且很难处理支持度和数据变化等关联规则更新问题．作者提出了基于模式矩阵的FP—growth改进算法，它至多扫描数据库一次，特别在更新问题上不用重新扫描数据库．通过实验结果分析，验证了这种改进算法相对于原有FP—growth算法的优势，特别在大数据集下，大大降低了挖掘的时间复杂度．     

A Novel Incremental Mining Algorithm of Frequent Patterns for Web Usage Mining

Because data warehouse is frequently changing, incremental data leads to old knowledge which is mined formerly unavailable. In order to maintain the discovered knowledge and patterns dynamically, this study presents a novel algorithm updating for global frequent patterns-IPARUC. A rapid clustering method is introduced to divide database into n parts in IPARUC firstly, where the data are similar in the same part. Then, the nodes in the tree are adjusted dynamically in inserting process by ＂pruning and laying back＂ to keep the frequency descending order so that they can be shared to approaching optimization. Finally local frequent itemsets mined from each local dataset are merged into global frequent itemsets. The results of experimental study are very encouraging. It is obvious from experiment that IPARUC is more effective and efficient than other two contrastive methods. Furthermore, there is significant application potential to a prototype of Web log Analyzer in web usage mining that can help us to discover useful knowledge effectively, even help managers making decision.     

基于有向图的关联规则挖掘算法研究

为了提高关联规则挖掘效率,提出了一种基于有向图的频繁项目集挖掘算法DGBFIG(Directed graph -based frequent itemsets generation)．该算法采用位矢量技术构造有向图,表示项与项之间的频繁关系,并在有向图的基础上递归产生频繁项集,从而只需扫描数据库2次,不产生候选集,从而大大提高了关联规则挖掘算法的效率．最后从空间和时间的复杂度分析了该算法的效率．     

事务模式树分层挖掘算法及其应用

从事务数据、时间序列数据等数据库中挖掘频繁模式已在数据挖掘领域中得到了广泛地研究．针对目前已有的Apriori算法和频繁模式增长算法在时间和空间等方面的复杂性和低效性，提出了一种新的数据结构——事务模式树，用来存放待挖掘的事务信息，同时给出一种基于该数据结构的挖掘算法——事务模式树分层挖掘算法．最后，把该算法应用于保险业务．结果表明,该算法简单高效，值得推广.