快速挖掘全局频繁项目集

分布式环境中，全局频繁项目集的挖掘是数据挖掘中最重要的研究课题之一．传统的全局频繁项目集挖掘算法采用Apriori算法框架，须多遍扫描数据库并产生大量的候选项目集，且通过传送局部频繁项目集求全局频繁项目集的网络通信代价高．为此，提出了一种分布数据库的全局频繁项目集快速挖掘算法——FMAGF.FMAGF算法采用传送条件频繁模式树或条件模式基来挖掘全局频繁项目集，可有效地减小网络通信量，提高全局频繁项目集挖掘效率．理论分析和实验结果表明提出的算法是有效可行的．     

快速更新全局频繁项目集

数据挖掘中的频繁项目集更新算法研究是重要的研究课题之一.目前已有的频繁项目集更新算法主要针对单机环境,有关分布式环境下的全局频繁项目集的更新算法的研究尚不多见.为此,提出了快速更新全局频繁项目集算法(fast updating algorithm for globally frequent itemsets,简称FUAGFI).该算法主要考虑数据库记录增加时全局频繁项目集的更新情况.FUAGFI利用已建立的各局部频繁模式树(frequent pattern tree,简称FP-tree)及已挖掘的全局频繁项目集,可有效地降低网络通信量,提高全局频繁项目集的更新效率.实验结果表明,所提出的更新算法是行之有效的.     

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

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

全局频繁闭项目集挖掘算法研究

频繁闭项目集挖掘是数据挖掘研究中的一个重要研究课题.目前已有的频繁闭项目集挖掘算法主要针对单机环境,有关分布式环境下的全局频繁闭项目集挖掘算法的研究尚不多见.为此,本文提出了一种快速挖掘全局频繁闭项目集算法,并对其更新问题进行了研究;提出了一种相应的频繁闭项目集增量式更新算法,该算法将充分利用先前的挖掘结果来节省发现新的全局频繁闭项目集的时间开销.实验结果表明算法是有效的.     

一种分布式全局频繁闭项目集快速挖掘更新算法

在数据挖掘研究中,频繁闭项目集挖掘成为重要的研究方向.目前已有的频繁闭项目集挖掘算法主要针对单机环境,有关分布式环境下的全局频繁闭项目集挖掘算法的研究尚不多见.针对无共享体系结构数据水平分布的情况,提出了一种分布式快速挖掘全局频繁闭项目集增量式更新算法,算法通过对各节点候选频繁项目集进行预处理,有效地降低网络通信量,提高全局频繁闭项目集挖掘算法的效率,该算法充分利用前次挖掘结果来发现新的全局频繁闭项目集,具有较高的效率.理论分析和实验结果表明算法是有效的.     

基于FP-Tree的最大频繁项目集挖掘及更新算法

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题,之前的很多研究都是采用Apriori类的候选项目集生成-检验方法.然而,候选项目集产生的代价是很高的,尤其是在存在大量强模式和/或长模式的时候.提出了一种快速的基于频繁模式树(FP-tree)的最大频繁项目集挖掘DMFIA(discover maximum frequent itemsets algorithm)及其更新算法UMFIA(update maximum frequent itemsets algorithm).算法UMFIA将充分利用以前的挖掘结果来减少在更新的数据库中发现新的最大频繁项目集的费用.     

分布式环境下约束性关联规则的快速挖掘

研究人员针对单机环境提出了约束性关联规则的挖掘算法,但它们不适用于分布式环境.为此本文讨论分布式环境下约束性关联规则的快速挖掘技术,提出一种基于分布式环境的约束性关联规则快速挖掘算法DCAR,其中包括局部约束性频繁项目集挖掘算法MLFC和全局约束性频繁项目集挖掘算法MGFC.该算法根据布尔约束条件产生向导集,采用一种新的候选项集生成函数Reorder-gen,该函数通过向导集高效地产生分布式环境中满足约束条件的、数量较少且完备的候选项集,并且求解全局约束性频繁项集过程中,传送局部候选项集支持数的通信量为O(n),从而提高了算法的挖掘效率.将本文提出的算法加以实现,实验结果表明DCAR算法高效可行,其效率大约是DMA-IC算法的2-3倍.     

改进的基于频繁模式树的最大频繁项集挖掘算法——FP-MFIA

针对最大频繁项目集挖掘算法(DMFIA)当候选项目集维数高而最大频繁项目集维数较低的情况下要产生大量的候选项目集的缺点,提出了一种改进的基于频繁模式树(FP-tree)结构的最大频繁项目集挖掘算法--FP-MFIA。该算法根据FP-tree的项目头表,采用自底向上的搜索策略逐层挖掘最大频繁项目集,从而加速每次对候选集计数的操作。在挖掘时根据每层的条件模式基产生维数较低的非频繁项目集,尽早对候选项目集进行剪枝和降维,可大量减少候选项目集的数量。同时在挖掘时充分利用最大频繁项集的性质,减少搜索空间。通过算法在不同支持度下挖掘时间的对比可知,算法FP-MFIA在最小支持度较低的情况下时间效率是DMFIA以及基于降维的最大频繁模式挖掘算法(BDRFI)的2倍以上,说明FP-MFIA在候选集维数较高的时候优势明显。     

最大频繁项目集的快速更新

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题．为克服基于Apriori的最大频繁项目集挖掘算法存在的不足，DMFIA采用FP-tree存储结构及自顶向下的搜索策略，有效地提高了最大频繁项目集的挖掘效率．但对于频繁项目多而最大频繁项目集维数相对较小的情况，DMFIA要经过多层搜索且在每一层产生大量的候选项目集，因而影响算法的执行效率．为此，该文提出了DMFIA的改进算法IDMFIA(the Improved algorithm of DMFIA)．IDMFIA采用自顶向下和自底向上双向搜索策略，可尽早修剪掉较短最大频繁项目集的超集和较长最大频繁项目集的子集．另外，该文还提出最大频繁项目集更新算法FUMFIA(Fast Updating Maximum Frequent Itemsets Algorithm)，该算法充分利用已建立的FP-tree和已挖掘的最大频繁项目集，可对已挖掘的最大频繁项目集进行高效维护．实验结果表明，IDMFIA和FUMFIA可有效提高最大频繁项目集的挖掘和更新效率．     

一种网格环境下的FP-树分布式构造算法

针对分布式环境下FP-tree的构造及合并,给出了一种网格环境下FP-tree的分布式构造算法GridDBMA。该算法中,各站点根据全局项目头表,独立构造局部频繁模式树BFP-tree,然后,利用合并算法将各局部树合并为一棵全局频繁模式树,并在全局频繁模式树上提取出所求的频繁项目集,通过对传统频繁模式树的存储结构的改进,减少了树的规模及站点间的网络通信量,并使树的遍历更加方便有效,提高了合并效率,从而提高了整个频繁项目集的挖掘效率。最后,采用天体光谱数据作为形式背景,实验验证了该算法的正确性和有效性。     

基于FP树的全局最大频繁项集挖掘算法

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

Distributed Mining of Maximal Frequent Itemsets on a Data Grid System

In this paper, we propose a new algorithm, named Grid-based Distributed Max-Miner (GridDMM), for mining maximal frequent itemsets from databases on a Data Grid. A frequent itemset is maximal if none of its supersets is frequent. GridDMM is specifically suitable for use in Grid environments due to low communication and synchronization overhead. GridDMM consists of a local mining phase and a global mining phase. During the local mining phase, each node mines the local database to discover the local maximal frequent itemsets, then they form a set of maximal candidate itemsets for the top-down search in the subsequent global mining phase. A new prefix-tree data structure is developed to facilitate the storage and counting of the global candidate itemsets of different sizes. We built a Data Grid system on a cluster of workstations using the open-source Globus Toolkit, and evaluated the GridDMM algorithm in terms of performance, scalability, and the overhead of communication and synchronization. GridDMM demonstrates better performance than other sequential and parallel algorithms, and its performance is scalable in terms of the database size and the number of nodes. This research was supported in part by LexisNexis, NCR and AFRL/Wright Brothers Institute (WBI).     

Efficient mining of maximal frequent itemsets from databases on a cluster of workstations

In this paper, we propose two parallel algorithms for mining maximal frequent itemsets from databases. A frequent itemset is maximal if none of its supersets is frequent. One parallel algorithm is named distributed max-miner (DMM), and it requires very low communication and synchronization overhead in distributed computing systems. DMM has the local mining phase and the global mining phase. During the local mining phase, each node mines the local database to discover the local maximal frequent itemsets, then they form a set of maximal candidate itemsets for the top-down search in the subsequent global mining phase. A new prefix tree data structure is developed to facilitate the storage and counting of the global candidate itemsets of different sizes. This global mining phase using the prefix tree can work with any local mining algorithm. Another parallel algorithm, named parallel max-miner (PMM), is a parallel version of the sequential max-miner algorithm (Proc of ACM SIGMOD Int Conf on Management of Data, 1998, pp 85–93). Most of existing mining algorithms discover the frequent k-itemsets on the kth pass over the databases, and then generate the candidate (k + 1)-itemsets for the next pass. Compared to those level-wise algorithms, PMM looks ahead at each pass and prunes more candidate itemsets by checking the frequencies of their supersets. Both DMM and PMM were implemented on a cluster of workstations, and their performance was evaluated for various cases. They demonstrate very good performance and scalability even when there are large maximal frequent itemsets (i.e., long patterns) in databases.

基于DDMINER分布式数据库系统中频繁项目集的更新

给出了一种分布式数据挖掘系统的体系结构DDMINER，对分布式数据库系统中频繁项目集的更新问题进行探讨，既考虑了数据库中事务增加的情况，又考虑了事务删除的情况；提出了一种基于DDMINER的局部频繁项目集的更新算法ULF和全局频繁项目集的更新算法UGF．该算法能够产生较少数量的候选频繁项目集，在求解全局频繁项目集过程中，传送候选局部频繁项目集支持数的通信量为O(n)；将文章提出的算法用Java语言加以实现，并对算法性能进行了研究；实验结果表明这些算法是正确、可行的，并且具有较高的效率．     

快速挖掘分布式数据库全局最大频繁项集

提出一种快速挖掘分布式数据库全局最大频繁项集算法（FMMH）．FMMFI算法首先设置了中心节点,并以各个节点构建局部FP-tree,采用挖掘最大频繁项目集算法（DMHA）快速挖掘局部最大频繁项集;然后与中心节点交互以实现数据汇总：最终获得全局最大频繁项集．FMMFI算法采用自上而下的剪枝策略,能大幅减少候选项集,降低通信量．理论分析和实验结果表明,FMMFI算法是有效的．     

快速挖掘频繁项集的并行算法

传统的挖掘频繁项集的并行算法存在数据偏移、通信量大、同步次数较多和扫描数据库次数较多等问题。针对这些问题，提出了一种快速挖掘频繁项集的并行算法(FPMFI)。FPMFI算法让各计算机节点独立地计算局部频繁项集，然后与中心节点交互实现数据汇总，最终获得全局频繁项集。理论分析和实验结果表明FPMFI算法是有效的。     

最小支持度变化时分布式数据库中频繁项目集更新

讨论分布式数据库系统中最小支持度变化时频繁项目集如何高效更新问题，提出了一种基于最小支持度变化的局部频繁项目集的更新算法ULFS和全局频繁项目集的更新算法UGFS．该算法能够充分利用已挖掘的结果．并且产生较少数量的候选频繁项目集，在求解全局频繁项目集过程中．候选局部频繁项目集支持数的通信量为O(n)．将文章提出的算法用Java加以实现．并时算法性能进行了研究．实验结果表明这些算法是可行、有效的．并且具有较快的速度．