基于MapReduce的H-mine算法*

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

基于Hadoop平台的TFIDF算法并行化研究

针对大数据集下文本分类算法在单机上训练和测试过程效率低下的问题,提出了基于Hadoop分布式平台的TFIDF文本分类算法,并给出了算法实现的具体流程。通过MapReduce编程模型实现了考虑到词在文档中位置的并行化TFIDF文本分类算法,并与传统串行算法进行了对比,同时在单机和集群模式下进行了实验。实验表明,使用并行化的TFIDF文本分类算法可实现对海量数据的高速有效分类,并使算法性能得到优化。     

基于MapReduce的Bagging决策树优化算法

针对经典C4.5决策树算法存在过度拟合和伸缩性差的问题,提出了一种基于Bagging的决策树改进算法,并基于MapReduce模型对改进算法进行了并行化。首先,基于Bagging技术对C4.5算法进行了改进,通过有放回采样得到多个与初始训练集大小相等的新训练集,并在每个训练集上进行训练,得到多个分类器,再根据多数投票规则集成训练结果得到最终的分类器;然后,基于MapReduce模型对改进算法进行了并行化,能够并行化处理训练集、并行选择最佳分割属性和最佳分割点,以及并行生成子节点,实现了基于MapReduce Job工作流的并行决策树改进算法,提高了对大数据集的分析能力。实验结果表明,并行Bagging决策树改进算法具有较高的准确度与敏感度,以及较好的伸缩性和加速比。     

基于MapReduce的高效用序列模式挖掘算法

由于数据规模的快速增长,高效用序列模式挖掘算法效率严重下降.针对这种情况,提出基于MapReduce的高效用序列模式挖掘算法HusMaR.算法基于MapReduce框架,使用效用矩阵高效地生成候选项;使用随机映射策略均衡计算资源;使用基于领域的剪枝策略来防止组合爆炸.实验结果表明,在大规模数据集下,算法取得了较高的并行效率.     

ABC_Kmeans聚类算法的MapReduce并行化研究

随着数据的海量增长,数据聚类算法的研究面临着海量数据挖掘和处理的挑战;针对K-means聚类算法对初始聚类中心的依赖性太强、全局搜索能力也差等缺点,将一种改进的人工蜂群算法与K-means算法相结合,提出了ABC_Kmeans聚类算法,以提高聚类的性能;为了提高聚类算法处理海量数据的能力,采用MapReduce模型对ABC_Kmeans进行并行化处理,分别设计了Map、Combine和Reduce函数;通过在多个海量数据集上进行实验,表明ABC_Kmeans算法的并行化设计具有良好的加速比和扩展性,适用于当今海量数据的挖掘和处理。     

基于Relief和BFO的并行支持向量机算法

针对大数据环境下并行支持向量机(SVM)算法存在冗余数据敏感、参数选取困难、并行化效率低等问题,提出了一种基于Relief和BFO算法的并行SVM算法RBFO-PSVM。首先,基于互信息和Relief算法设计了一种特征权值计算策略MI-Relief,剔除数据集中的冗余特征,有效地降低了冗余数据对并行SVM分类的干扰;接着,提出了基于MapReduce的MR-HBFO算法,并行选取SVM的最优参数,提高SVM的参数寻优能力;最后,提出核聚类策略KCS,减小参与并行化训练的数据集规模,并提出改进CSVM反馈机制的交叉融合级联式并行支持向量机CFCPSVM,结合MapReduce编程框架并行训练SVM,提高了并行SVM的并行化效率。实验表明,RBFO-PSVM算法对大型数据集的分类效果更佳,更适用于大数据环境。     

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

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

基于列存储的MapReduce分布式Hash连接算法

大数据具有规模大、深度大、宽度大、处理时间短、硬件系统普通化、软件系统开源化的特点。传统关系型数据库在对大数据进行操作时存在系统性能严重下降、计算效率提升有限以及可扩展性差等问题,因此引入MapReduce并行计算模型,提出一种大数据上基于列存储的MapReduce分布式Hash连接算法。首先,设计面向大数据的分布式计算模型,在设计的分片聚集并行连接的基础上,利用Hash连接以及动态探测方法优化了数据并行连接处理效率;然后,针对该算法开发了基于Hadoop的原型系统。通过实验证明,在大数据分析处理中,所提算法在执行时间和负载能力上都有很好的性能表现,也能提供良好的可扩展性。     

改进的并行关联规则增量挖掘算法

针对大数据环境下基于Can树(canonical order tree)的增量关联规则算法存在树结构空间占用过大、频繁模式挖掘效率不佳以及MapReduce集群并行化性能不足等问题,提出了一种基于粗糙集和归并剪枝方法改进的并行关联规则增量挖掘算法MR-PARIRM(MapReduce-based parallel association rules incremental mining algo-rithm using rough set and merge pruning).首先,设计了一种基于粗糙集的相似项合并策略RS-SIM(rough set based similar item merge)对数据集的相似项进行合并处理,并根据合并后的数据进行Can树构造,从而降低树结构的空间占用;其次,提出了一种归并剪枝策略MPS(merge pruning strategy)对树结构中的传播路径进行修剪合并,通过压缩频繁模式搜索空间来加快频繁项挖掘;最后,通过动态调度策略DSS(dynamic scheduling strategy)对异构式MapReduce集群中的计算任务进行动态调度,实现了负载均衡,有效提升了集群的并行化运算能力.最终的实验仿真结果表明,MR-PARIRM在大数据环境下具有相对较好的性能表现,适用于对大规模数据进行并行化处理.     

MR-GSpar:一种基于MapReduce的大图稀疏化算法

图的稀疏化是图聚类分析中数据预处理的关键操作,已得到广泛的关注.针对图数据日益普及、规模不断增大的现状,提出了一种基于MapReduce的面向大规模图的稀疏化算法,即MR-GSpar算法.该算法在MapReduce并行计算框架的基础上,通过对传统的最小哈希(Minhash)算法的并行化改造,使其可在分布式的集群环境中实现对大规模图数据的高效稀疏化处理.真实数据集上的实验表明了该算法的可行性与有效性.     

Coteries轨迹模式挖掘及个性化旅游路线推荐

Coterie是一种异步的组模式,要求在不等时间间隔约束下找出具有相似轨迹行为的组模式.而传统的轨迹组模式挖掘算法往往处理具有固定时间间隔采样约束的GPS数据,因此无法直接用于Coterie模式挖掘.同时传统组模式挖掘存在语义信息缺失问题,降低了个性化旅游路线推荐的完整度和准确度.为此,提出基于语义的距离敏感推荐策略（DRSS）和基于语义的从众性推荐策略（CRSS）.此外,随着社交网数据规模的不断增大,传统组模式聚类算法的效率受到了极大挑战,因此,为高效处理大规模社交网轨迹数据,使用带有优化聚类的MapReduce编程模型来挖掘Coterie组模式.实验结果证明,MapReduce编程模型下带优化聚类和语义信息的Coterie组模式挖掘,在个性化旅游路线推荐上优于传统组模式旅游路线推荐质量,且能有效处理大规模社交网轨迹数据.     

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

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

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

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

Paradigm and performance analysis of distributed frequent itemset mining algorithms based on Mapreduce

FrequentItemsetMining (FIM) is one of the most important data mining tasks and is the foundation of many data mining tasks. In Big Data era, centralized FIM algorithms cannot meet the needs of FIM for big data in terms of time and space, so Distributed Frequent Itemset Mining (DFIM) algorithms have been designed to meet the above challenges. In this paper, LocalGlobal and RedistributionMining which are two main paradigms of DFIM algorithm are discussed; Two algorithms of these paradigms on MapReduce named LG and RM are proposed while MapReduce is a popular distributed computing model, and also the related work is discussed. The experimental results show that the RM algorithm has better performance in terms of computation and scalability of sites, and can be used as the basis for designing the DFIM algorithm based on MapReduce. This paper also discusses the main ideas of improving the DFIM algorithms based on MapReduce.     

基于Bigtable与MapReduce的Apriori算法改进

为提高Apriori算法挖掘频繁项目集的效率,引进了Bigtable技术与MapReduce模型来对Apriori算法进行优化,设计出大数据环境下挖掘频繁项目集的新算法BM-Apriori算法。与单纯基于MapReduce模型的Apriori改进算法相比,新算法利用Bigtable的时间戳属性代替了键/值对的产生,只需扫描数据库一次即可,节约了模式匹配的时间。同时,BM-Apriori算法在项集列表中新增事务标号列,自动获取事务标号以计算支持度。将BM-Apriori算法在Hadoop平台上进行了实验,结果表明Bigtable技术的融入使得BM-Apriori算法具有更高的效率与可拓展性。     

DMFUCP:大规模轨迹数据通用伴随模式分布式挖掘框架

广泛应用的移动定位设备方便了用户位置数据的获取,轨迹数据量高速增长.通用伴随模式挖掘聚焦时空维度上的用户高相似度行为路径发现问题,基于大规模轨迹数据设计高效准确地伴随模式挖掘方法对发现用户偏好、构建新商业模式等具有重要意义,同时也极具挑战.一方面,海量且不断增长的轨迹数据要求伴随模式挖掘应具有良好的可扩展性,集中性挖掘...     

Hadoop云平台MapReduce模型优化研究

针对Hadoop平台MapReduce分布式计算模型运行机制中的顺序制约而产生的计算资源浪费问题,从提高平台中每个执行节点的细粒度并行数据处理角度出发,结合Java共享内存多线程编程技术,对该模型进行了优化,提出一种MapReduce+OpenMP粗细粒度相结合的分布式并行计算模型。并在由四个节点组成的Hadoop集群环境下对不同规模大小的出租车GPS轨迹数据分析处理,验证该模型的性能和效率,实验结果证明MapReduce+OpenMP分布式并行计算模型确实能够提高针对大数据集的计算效率,是对Hadoop平台大数据分析处理模型有效的完善和优化。     

基于MapReduce的分布式AP聚类算法

随着网络的普遍应用,网络中产生的数据急剧增长,大规模数据处理面临严峻挑战。本文在对AP聚类算法进行研究的基础上,利用MapReduce编程模型思想对AP聚类算法进行改进,设计在云平台Hadoop环境下运行的基于MapReduce的分布式AP聚类算法,并在实验中对不同规模的图数据进行聚类测试,实验结果表明分布式的AP聚类算法具有很好的时间效率和加速比。      

HFIM: a Spark-based hybrid frequent itemset mining algorithm for big data processing

Frequent itemset mining is one of the data mining techniques applied to discover frequent patterns, used in prediction, association rule mining, classification, etc. Apriori algorithm is an iterative algorithm, which is used to find frequent itemsets from transactional dataset. It scans complete dataset in each iteration to generate the large frequent itemsets of different cardinality, which seems better for small data but not feasible for big data. The MapReduce framework provides the distributed environment to run the Apriori on big transactional data. However, MapReduce is not suitable for iterative process and declines the performance. We introduce a novel algorithm named Hybrid Frequent Itemset Mining (HFIM), which utilizes the vertical layout of dataset to solve the problem of scanning the dataset in each iteration. Vertical dataset carries information to find support of each itemsets. Moreover, we also include some enhancements to reduce number of candidate itemsets. The proposed algorithm is implemented over Spark framework, which incorporates the concept of resilient distributed datasets and performs in-memory processing to optimize the execution time of operation. We compare the performance of HFIM with another Spark-based implementation of Apriori algorithm for various datasets. Experimental results show that the HFIM performs better in terms of execution time and space consumption.