Spark平台的分布式阶段自适应关联规则挖掘算法

为满足日益增长的海量数据挖掘需求,迫切需要设计一种能够在多台机器上运行的分布式关联规则挖掘算法。Apriori这种高度迭代算法在Hadoop平台上运行时每次迭代执行大量的磁盘I/O操作,大大影响并限制了算法的运行效率。本文利用Spark对分布式计算内置支持的特点,在Spark平台上设计并实现一种分布式关联规则挖掘算法,称为阶段式自适应挖掘算法(Staged Adaptive Apriori)。算法使用自适应的数据集部分处理的策略对频繁项集进行高效挖掘,在每次迭代前初步评估执行时间,并采用较为合适的方法来减少时间和空间的复杂性,是一种基于数据集性质的自适应关联规则挖掘算法。实验结果表明了算法的有效性。     

基于项编码的分布式频繁项集挖掘算法

Apriori算法是解决频繁项集挖掘最常用的算法之一,但多轮迭代扫描完整数据集的计算方式,严重影响算法效率且难以并行化处理。随着数据规模的持续增大,这一问题日益严重。针对这一问题,提出了一种基于项编码和Spark计算框架的Apriori并行化处理方法——IEBDA算法,利用项编码完整保存项集信息,在不重复扫描完整数据集的情况下完成频繁项集挖掘,同时利用Spark的广播变量实现并行化处理。与其他分布式Apriori算法在不同规模的数据集上进行性能比较,发现IEBDA算法从第一轮迭代后加速效果明显。结果表明,该算法可以提高大数据环境下的多轮迭代的频繁项集挖掘效率。     

一种基于MapReduce模型的高效频繁项集挖掘算法

由于互联网技术急速发展及其用户迅速地增加,很多网络服务公司每天不得不处理TB级甚至更大规模的数据量。在如今的大数据时代,如何挖掘有用的信息正变成一个重要的问题。关于数据挖掘(Data Mining)的算法在很多领域中已经被广泛运用,挖掘频繁项集是数据挖掘中最常见且最主要的应用之一,Apriori则是从一个大的数据集中挖掘出频繁项集的最为典型的算法。然而,当数据集比较大或使用单一主机时,内存将会被快速消耗,计算时间也将急剧增加,使得算法性能较低,基于MapReduce的分布式和并行计算则被提出。文中提出了一种改进的MMRA (Matrix MapReduce Algorithm)算法,它通过将分块数据转换成矩阵来挖掘所有的频繁k项集;然后将提出的算法和目前已经存在的两种算法(one-phase算法、k-phase算法)进行比较。采用Hadoop-MapReduce作为实验平台,并行和分布式计算为处理大数据集提供了一个潜在的解决方案。实验结果表明,改进算法的性能优于其他两种算法。     

挖掘最大频繁项集的事务集迭代算法

发现最大频繁项目集是数据挖掘应用中的关键问题;提出一种新的基于事务集迭代的求最大频繁项集算法,该算法在每次迭代时,通过对输入事务集的两次扫描,生成所有阶数的候选项集和频繁项集;每次迭代后又生成新的事务集作为下一次迭代的输入,而候选最大频繁项集集合则随着迭代不断地趋于完整。该算法不需要生成K-1阶候选项集或频繁树,有别于已有的经典算法;同时由于用于迭代的事务集的数据量会快速缩减,从而也可有效降低算法的时间复杂度。实验表明在大数据量和小最小支持度时该算法更为有利。     

一种挖掘加权频繁项集的改进算法

分析了New-Apriori和MWFI（Mining Weighted Frequent Itemsets）算法之不足,提出了一种挖掘加权频繁项集的New-MWFI算法。该算法按属性的权值对事务进行分类,并依次求出每个类别内的加权频繁项集。由于每个类别内的频繁项集满足Apriori性质,因而可以利用Apriori算法或其他改进算法进行挖掘,从而克服了原来算法的不合理和效率低下的缺陷。实验表明该算法能更有效地从数据集中挖掘出加权频繁项集。     

基于散列的频繁项集分组算法

Apriori算法是频繁项集挖掘的经典算法。针对Apriori算法的剪枝操作和多次扫描数据集的缺点,提出了基于散列的频繁项集分组(HFG)算法。证明了2-项集剪枝性质,采用散列技术存储频繁2-项集,将Apriori算法剪枝操作的时间复杂度从O(k×|Lk|)降低到O(1);定义了首项的子项集概念,将数据集划分为以Ii为首项的数据子集并采用分组索引表存储,在求以Ii为首项的频繁项集时,只扫描以Ii为首项的数据子集,减少了对数据集扫描的时间代价。实验结果表明,由于HFG算法的剪枝操作产生了累积效益,以及分组扫描排除了无效的项集和元组,使得HFG算法在时间性能方面与Apriori算法相比有较大提高。     

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

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

IABS:一个基于Spark的Apriori改进算法

Apriori算法是关联规则挖掘中最经典的算法之一,其核心问题是频繁项集的获取。针对经典Apriori算法存在的需多次遍历事务数据库及需产生候选项集等问题,首先通过转换存储结构、消除候选集产生过程等方法对Apriori算法进行优化,同时,随着大数据时代的到来,数据量与日俱增,传统算法面临巨大挑战,因此,又将优化的Apriori与Spark相结合,充分利用Spark的内存计算、弹性分布式数据集等优势,提出了IABS(Improved Apriori algorithm based on Spark)。通过与已有的同类算法进行比较,IABS的数据可扩展性和节点可扩展性得以验证,并且在多种数据集上平均获得了23.88%的性能提升,尤其随着数据量的增长,性能提升更加明显。     

一种基于无向项集图的频繁项集挖掘算法

分析了Apriori算法关于发现频繁项集的方法及其效率,提出了一种基于无向项集图的频繁项集挖掘优化算法。该算法只需要扫描数据库一次,不产生候选项目集,也不使用逐层迭代的方法,大大提高了频繁项集的发现效率。     

一种基于单事务项集组合的频繁项集挖掘算法

Apriori是挖掘频繁项集的基本算法,目前该算法及其优化变种都没有解决候选项及重复扫描事务数据库的问题.文章通过对Apriori及其优化算法的深入探究,提出了一种基于单事务组合项集的挖掘算法,该算法在一个事务内部对"数据项"进行组合,在事务数据库中对所有相同"项集"进行计数.不经过迭代过程,不产生候选项集,所有频繁项集的挖掘过程只需对事务数据库一次扫描,提高了频繁项集挖掘效率.     

基于改进的关联规则挖掘算法的研究

A priori算法是经典的关联规则挖掘算法,它利用逐层搜索的迭代方法完成频繁模式的挖掘工作,反复进行连接剪枝操作,思路简单易操作,但也伴随着产生庞大候选集,多次扫描数据库产生巨大I/O开销的问题,提出一种改进算法:基于矩阵的关联规则挖掘算法,同A priori算法比较,该算法只需扫描一遍数据库,就可直接查找k-频繁项集,尤其是当频繁项集较高的时候,该算法具有更高的执行效率,在大数据量的情况下更具有可行性。     

基于动态项集计数的加权频繁项集算法

基于Apriori的加权频繁项集挖掘算法存在扫描数据集次数多的问题。为此,提出一种基于动态项集计数的加权频繁项集算法。该算法采用权值键树的数据结构和动态项集计数的方法,满足向下闭合特性,并且动态生成候选频繁项集,从而减少扫描数据集的次数。实验结果证明,该算法生成的加权频繁项集具有较高的效率和时间性能。     

改进的频繁项集挖掘算法

频繁项集挖掘是数据挖掘中的一个重要研究课题。在分析Apriori算法与FP-growth 算法特点的基础上,提出了一种改进的频繁项集挖掘算法,即索引生成频繁项集算法IGFA。IGFA算法基于Apriori算法并通过 “索引二元组”生成候选集,减免了候选集的大量冗余,实验及结果分析表明该算法有效提高了频繁项集的挖掘效率。     

并行挖掘频繁项目集新算法——MREclat

针对Eclat算法在挖掘海量数据中的频繁项目集时存在的内存和计算资源不足等问题,提出了基于Map/Reduce计算模型的并行挖掘算法--MREclat。首先,将水平型数据库转换成垂直型数据库;然后,将转换后的数据按2-项集的前缀分发到各个计算节点上,且在分发数据时引入了均衡策略;接着,在各个计算节点上求出以某一前缀开头的所有频繁项目集;最后,合并各个节点的结果得到所有频繁项目集。介绍了MREclat的设计思想,研究了算法的运行性能。实验结果表明,MREclat算法效率大约是PEclat算法的2倍,加速比性能比PEclat算法提高了64%。     

一种基于上三角项集矩阵的频繁项集挖掘算法*

分析了Apriori算法关于发现频繁项集的方法及其效率,提出了一种基于上三角项集矩阵的频繁项集挖掘优化算法。本算法只需要扫描数据库一次,不产生候选项目集,也不使用逐层迭代的方法,大大提高了频繁项集的发现效率。     

一种基于上三角项集矩阵的频繁项集挖掘算法

分析了Apriori算法关于发现频繁项集的方法及其效率,提出了一种基于上三角项集矩阵的频繁项集挖掘优化算法。本算法只需要扫描数据库一次,不产生候选项目集,也不使用逐层迭代的方法,大大提高了频繁项集的发现效率。     

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

目前已提出了许多基于Apriori算法思想的频繁项目集挖掘算法,这些算法可以有效地挖掘出事务数据库中的短频繁项目集,但对于长频繁项目集的挖掘而言,其性能将明显下降.为此,提出了一种频繁闭项目集挖掘算法MFCIA,该算法可以有效地挖掘出事务数据库中所有的频繁项目集,并对其更新问题进行了研究,提出了一种相应的频繁闭项目集增量式更新算法UMFCIA,该算法将充分利用先前的挖掘结果来节省发现新的频繁闭项目集的时间开销.实验结果表明算法MFCIA是有效可行的.     

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

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

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

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

一种新的最大频繁项目集挖掘算法

最大频繁项目集挖掘是数据挖掘领域最重要的基本问题之一,在分析已有算法的基础上,提出了一种新的挖掘最大频繁项目集的算法,实验表明该算法在性能上优于已有的同类算法。