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

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

基于FP-Growth改进算法的云服务器故障数据分析

针对云服务器使用过程中参数异常的问题,介绍了云服务器的参数数据获取、数据清洗整理和有效分析过程。针对现有频繁模式增长(FP-Growth)算法中存在的条件FP-tree构建过程过于冗余以及数据量级越大处理效率越低的问题,提出了一种改进的FP-Growth算法,引入数组标记策略,每个FP-tree节点只保留指向父节点的指针。改进算法在挖掘过程中无需生成条件FP-tree,减少了时空消耗。实验结果表明,改进后的FP-Growth并行算法能够有效地提高云平台虚拟机异常数据的关联分析效率,并且改进算法也适用于较大规模数据集的数据挖掘工作。     

分布式并行关联规则挖掘算法研究

关联规则挖掘算法FP-Growth虽然效率比Apriori要快一个数量级,但存在频繁模式树可能过大而内存无法容纳和数据挖掘过程串行处理等两大缺点。提出一种分布式并行关联规则挖掘算法,该算法针对分布式应用数据架构,不需要产生全局FPtree,避免全局FP-tree可能过大而内存无法容纳的问题,算法在各个主要步骤上都实现了并行处理。算法测试结果和分析表明,与传统的关联规则挖掘算法FP-Growth相比,该算法通过多节点分布式并行处理显著提高了执行效率和处理能力。     

Hadoop下负载均衡的频繁项集挖掘算法研究

频繁项集挖掘FIM(Frequent Itemsets Mining)是关联规则挖掘算法的重要组成部分。而经典Apriori和FP-Growth算法在海量数据处理时面临内存占用、计算性能等方面的瓶颈。基于Hadoop云计算平台,提出适用大数据处理的频繁项集挖掘HBFP(High Balanced parallel FP-growth)算法,设计后缀模式转换的数据分割及均衡任务分组方案,使计算节点本地拥有计算所依赖的数据,实现不同节点相互独立的并行数据挖掘方法,并保证算法全局的负载均衡特性。实验数据表明,HBFP算法能均匀地将计算量分散至不同计算节点,并行且相互独立地进行FP-Growth挖掘过程,算法效率提高了约12%,算法全局稳定性及效率取得提升。     

基于Spark的并行FP-Growth算法优化及实现

为了进一步提高在Spark平台上的频繁模式增长（FP-Growth）算法执行效率,提出一种新的基于Spark的并行FP-Growth算法——BFPG。首先,从频繁模式树（FP-Tree）规模大小和分区计算量对F-List分组策略进行改进,保证每个分区负载总和近似相等;然后,通过创建列表P-List对数据集划分策略进行优化,减少遍历次数,降低时间复杂度。实验结果表明,BFPG算法提高了并行FP-Growth算法挖掘效率,且算法具有良好的扩展性。     

分布环境中的并行频繁模式挖掘算法

频繁模式的并行挖掘算法是数据挖掘中重要的研究课题。目前已经提出的并行算法大多是基于Apriori或基于FP-tree。由于两者的固有局限性,而且在计算过程中需要多次同步,因而具有较低的性能。文章提出了一种基于分布数据库的并行挖掘算法。该算法尽可能地让每个处理器独立地挖掘,每个处理器基于前缀树采用深度优先搜索的策略挖掘局部频繁模式集,并通过相关性质尽量减少候选全局频繁模式的规模,减少网络的通信量和同步次数以提高挖掘效率。     

基于FP-tree最大频繁项集的FP-MFI算法研究

由于基于Fp-tree的DMFIA算法在生成最大频繁项目集时会产生大量的候选频繁项集,通过改进传统的FP-tree结构,并提出了一种基于改进FP-tree的最大频繁模式挖掘算法FP-MFI,该算法不需要生成最大频繁候选项目集,改进的FP-tree是单向的,每个节点只保留了指向父节点的指针,可节约树空间.实验结果表明FP-MFI算法在数据库中频繁项目很多,而每一个事务中频繁项目很少的情况下,比同样基于FP-tree的DMFIA算法挖掘最大频繁项目集的效率更高.     

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

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

基于负载均衡和冗余剪枝的并行FP-Growth算法

针对现有的并行FP-Growth算法在数据并行分组时存在数据冗余和负载不均的问题,提出了基于负载估算和冗余剪枝的优化算法。首先,在采用高频策略分组时,引入节点任务估算方法,把每个分组中最大模式树的最长路径和支持度作为该分组的估计值,将估计值远大于其他节点的分组进行分割,平均到其他分组中,并且对不同分 组中重复的列表元素进行截断,去除冗余数据。实验表明,本文提出的算法能够有效防止并行化的数据倾斜,减少数据冗余,在时间和空间复杂度上要低于以前的并行化FP-Growth算法。     

一种基于FP-Growth的频繁项目集并行挖掘算法

FP-Growth算法是基于FP树挖掘频繁项目集的经典算法,为提高FP-Growth算法挖掘大规模数据频繁项目集的效率,提出了一种基于FP-Growth的频繁项目集并行挖掘算法FPPM。该算法基于Map/Reduce并行模型,在每个计算节点上首先构造局部频繁模式树,并对之进行挖掘得到局部频繁项目集,然后合并局部频繁项目集以得到全局频繁项集,由于此时得到的结果并不完备,所以对合并后未达到最小支持度阈值的项目集,重新计算其支持数。介绍了FPPM算法的设计思想,测试了其性能。实验结果表明FPPM算法具有较好的可扩展性。     

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

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

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

无项头表的FP-Growth算法

针对FP-Growth算法中频繁模式树的遍历低效问题,提出了一种无项头表的频繁模式增长算法。该算法利用递归回溯的方式遍历频繁模式树以求取条件模式基,解决了对同一树路径多次重复遍历的问题。从理论分析和实际挖掘能力两方面,将新算法与FP-Growth算法进行了对比。结果表明,新算法有效减少了条件模式基的搜索开销,使频繁模式挖掘的效率提高了2~5倍,在时间和空间性能上均优于FP-Growth算法。将该算法应用于通信告警关联规则挖掘,较快地挖掘出了关联规则结果,且正确规则的覆盖率达到了83.3%。     

基于Spark框架的FP-Growth大数据频繁项集挖掘算法

针对大数据中的频繁项集挖掘问题,提出一种基于Spark框架的FP-Growth频繁项集并行挖掘算法。首先,根据垂直布局思想将数据按照事务标识符垂直排列,以此解决扫描整个数据集的缺陷。然后,通过FP-Growth算法构建频繁模式树,并生成频繁1-项集。接着,通过扫描垂直数据集来计算项集的支持度,从而识别出非频繁项,并将其从数据集中删除以降低数据尺寸。最后,通过迭代过程来生成频繁 -项集。在标准数据集上的实验结果表明,该算法能够有效挖掘出频繁项集,在执行时间方面具有很大的优越性。     

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

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

Batch incremental processing for FP-tree construction using FP-Growth algorithm

In the present scenario of global economy and World Wide Web, large sets of evolving and distributed data can be handled efficiently by incremental data mining. Frequent patterns are very important in knowledge discovery and data mining process, such as mining of association rules, correlations. FP-tree is a very versatile data structure used for mining of frequent patterns in knowledge discovery and data mining process. FP-tree is a compact representation of transaction database that contains frequency information of all relevant frequent patterns (FP) of the database. All of the existing incremental frequent pattern mining algorithms, such as AFPIM, CATS, CanTree, CP-tree, and SPO-tree, perform incremental mining by processing one transaction of the incremental part of database at a time and updating it to the FP-tree of initial (original) database. Here, in this paper, we propose a novel method that takes advantage of FP-tree representation of incremental transaction database for incremental mining. We propose a batch incremental processing algorithm BIT_FPGrowth that restructures and merges two small consecutive duration FP-trees to obtain a FP-tree of the FP-Growth algorithm. Our BIT_FPGrowth uses FP-tree as preprocessed data repository to get transactions (i.e., item-sets), unlike other sequential incremental algorithms that read transactions from database. BIT_FPGrowth algorithm takes less time for constructing FP-tree. Our experimental results show that, as the size of the database increases, increase in runtime of BIT_FPGrowth is much less and is least of all the other algorithms.     

基于FIUT的并行频繁项集增量更新算法

针对目前大数据快速增加的环境下,海量数据的频繁项集挖掘在实际中所面临的增量更新问题,在频繁项超度量树算法（frequent items ultrametric trees,FIUT）的基础上,引入MapReduce并行编程模型,提出了一种针对频繁项集增量更新的面向大数据的并行算法。该算法通过检查频繁超度量树叶子节点的支持度来确定频繁项集,同时采用准频繁项集的策略来优化并行计算过程,从而提高数据挖掘效率。实验结果显示,所提出的算法能快速完成扫描和更新数据,具有较好的可扩展性,适合于在动态增长的大数据环境中进行关联规则相关数据挖掘。     

基于事务映射区间求交的高效频繁模式挖掘算法

关联规则挖掘是数据挖掘重要研究课题,大数据处理对关联规则挖掘算法效率提出了更高要求,而关联规则挖掘的最耗时的步骤是频繁模式挖掘。针对当前频繁模式挖掘算法效率不高的问题,结合Apriori算法和FP-growth算法,提出一种基于事务映射区间求交的频繁模式挖掘算法IITM（interval interaction and transaction mapping）,只需扫描数据集两次来生成FP树,然后扫描FP树将每个项的ID映射到区间中,通过区间求交来进行模式增长。该算法解决了Apriori算法需要多次扫描数据集,FP-growth算法需要迭代地生成条件FP树来进行模式增长而带来的效率下降的问题。在真实数据集上的实验显示,在不同的支持度下IITM算法都要要优于Apriori、FP-growth以及PIETM算法。     

基于Spark的并行频繁模式挖掘算法

在大数据环境下Apriori频繁模式挖掘算法在数据处理过程具有预先设定最小阈值、时间复杂度高等缺陷, 为此采用多阶段挖掘策略实现并行化频繁模式挖掘算法PTFP-Apriori。首先将预处理数据以模式树的形式存储,通过最为频繁的[k]个模式得到最优阈值。然后根据该值删除预期不能成长为频繁的模式以降低计算规模,并利用弹性分布式数据集RDD完成统计项集支持度计数、候选项集生成的工作。实验分析表明相比于传统的频繁模式挖掘算法,该算法具有更高的效率以及可扩展性。