基于MapReduce的频繁项集并行挖掘算法

现有FP-growth频繁集挖掘算法在处理大数据时存在时空效率不高的问题,且内存的使用随着数据的增加已经无法满足把待挖掘数据压缩存储在单个内存中,为此,提出一种基于MapReduce模型的频繁项集并行挖掘算法。该算法采用一种基于key/value键值对直接扫描value寻找条件模式基的方式,同时通过在原有FP-tree树节点中新增一个带频繁项前缀的域空间来构建一颗新的条件模式树NFP-tree,使得对一项频繁项的条件模式基进行一次建树一次遍历就可以得到相应的频繁项集。对所提出的算法在Hadoop平台进行了验证与分析,实验结果表明该算法效率较传统FP-growth算法平均提高16.6%。     

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

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

标签集约束近似频繁模式的并行挖掘

近似频繁模式衍生于频繁模式,综合了频繁项集与频繁子图的特点。针对该模式的研究集中在无标签图上,其应用场景主要为社交网络、语义网络、智能电网等。近似频繁模式挖掘过程同时涉及频繁项集挖掘和频繁子图挖掘,因此已有的处理频繁模式挖掘算法无法较好地解决近似频繁模式挖掘问题。基于近似频繁模式结构,将其拓展到带标签图中,引入标签集约束,并设计标签集约束近似频繁模式挖掘算法LCPP（Label-Constraint Proximity Pattern）,该算法并行部署在MapReduce计算模型中,弥补了开源pFP算法处理大规模数据时效率不高的缺点。实验结果验证了该算法的有效性和可扩展性,表明了LCPP算法是pFP算法的极佳补充。     

基于MapReduce的海量数据挖掘技术研究

MapReduce是一种编程模型,可以运行在异构环境下,编程简单,不必关心底层实现细节,用于大规模数据集的并行运算。将MapReduce应用在数据挖掘的三个算法中：朴素贝叶斯分类算法、K-modes聚类算法和ECLAT频繁项集挖掘算法。实验结果表明,在保证算法准确率的前提下,MapReduce可以有效提高海量数据挖掘工作的效率。     

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

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

基于MapReduce的Top-k高效用模式挖掘算法

摘 要: 高效用模式挖掘被广泛应用于数据挖掘领域。为了挖掘指定数量的高效用模式,一些基于树结构和效用表结构的top-k高效用挖掘算法被提出,但前者在挖掘过程中产生了大量候选模式,后者在效用模式增长时需要进行多次比较。同时,由于在信息社会,数据量呈爆炸性增长。因此,在数据集过大的情况下,挖掘高效用模式需以大量存储空间以及计算开销为代价。为了解决这两个问题,基于MapReduce的top-k高效用模式挖掘算法（TKHUP_MaR）被提出。该算法通过两次扫描数据库,利用三次MapReduce来实现并行top-k高效用模式的挖掘。通过实验表明TKHUP_MaR 算法在并行挖掘top-k高效用模式的过程中是有效的。     

一种基于MapReduce的频繁闭项集挖掘算法

频繁闭项集的挖掘是发现数据项之间关联规则的一种有效方式。当前以MapReduce模式为基础的云计算平台为解决海量数据中的关联规则挖掘问题提供新的解决思路。文中提出并实现一种基于Hadoop云计算平台的频繁闭项集的并行挖掘算法。该算法主要包括并行计数、构造全局频繁项表、并行挖掘局部频繁闭项集和并行筛选全局频繁闭项集四个步骤。在多个数据集上的实验表明,该方法能较大提高数据挖掘的效率,具有较好的加速比。     

基于MapReduce的并行抽样路径K-匿名隐私保护算法

K-匿名算法及现存K-匿名改进算法大多使用牺牲时间效率降低发布数据信息损失量的方法实现数据的匿名化,但随着数据量的急剧增长,传统的数据匿名化方法已不适用于对较大数据的处理。针对K-匿名算法在单机执行过程中产生大量频繁项集和重复搜索数据表的缺点,将MapReduce模型引入到抽样泛化路径K-匿名算法中对其进行优化。该方法兼具MapReduce及抽样泛化算法的优点,高效分布式匿名化数据集,降低发布数据集信息损失量,提高数据的可用性。实验结果表明:当数据量较大时,该优化算法在时间效率及数据精度方面有显著提高。     

一种基于后缀项表的并行闭频繁项集挖掘算法

对现有的基于MapReduce的并行频繁项集挖掘算法进行了研究, 提出一种基于后缀项表的并行闭频繁项集挖掘算法, 通过后缀项表的引入及以闭频繁项集挖掘的形式, 减少组分间的数据传送量, 提高挖掘效率。实验表明, 该算法可以有效缩短平均挖掘时间, 对于高维大数据具有较好的性能。     

基于MapReduce的H-mine算法*

频繁模式挖掘是一种非常有效的从数据中获取知识的方法,但是随着大数据时代的来临,现有算法及其计算环境的运算速度、内外存容量面临严峻挑战。针对以上问题,本文紧密结合MapReduce模型提供的高效分布式编程和运行框架,在深入分析H-mine频繁模式挖掘算法的基础上,通过对H-mine算法频繁模式挖掘过程的并行化改进,提出了一种新颖的基于MapReduce模型的H-mine算法（简称：MRH-mine）。MRH-mine算法实现了对H-mine算法在分布式运行环境下的改造,实验表明该算法在面对数据大规模增长的情况下,具有良好的性能和扩展性。