基于MapReduce的预处理高效Skyline算法

现有基于MapReduce的算法不能高效地解决大数据的Skyline查询问题。针对这种情况,提出一种高效的预处理Skyline查询算法MRFS(MapReduce based Filter Skyline),对大数据集进行预处理,提取支配能力较强的小点集组成比较点集,在算法开始前用比较点集对原始数据集进行过滤,排除掉一大部分不能成为Skyline结果集的数据对象;再对过滤后的数据集在Map阶段并行计算出局部Skyline集;最后合并到一个Reduce任务,得到最终的Skyline结果集。在不同数据分布下对该算法进行系统实验,结果表明算法比现有的算法在时间效率上提高了20%~30%。     

基于改进人工蜂群算法与MapReduce的大数据聚类算法

针对大数据聚类算法计算效率与聚类性能较低的问题,提出了一种基于改进人工蜂群算法与MapReduce的大数据聚类算法。将灰狼优化算法与人工蜂群算法结合,同时提高人工蜂群算法的搜索能力与开发能力,该策略能够有效地提高聚类处理的性能;采用混沌映射与反向学习作为ABC种群的初始化策略,提高搜索的解质量;将聚类算法基于Hadoop的MapReduce编程模型实现,通过最小化类内距离的平方和实现对大数据的聚类处理。实验结果表明,该算法有效地提高了大数据集的聚类质量,同时加快了聚类速度。     

基于Hadoop的多特征协同过滤算法研究

协同过滤是互联网推荐系统的核心技术,针对协同过滤推荐算法中推荐精度和推荐效率以及数据可扩展性问题,采用灰色关联相似度,设计和实现了一种基于Hadoop的多特征协同过滤推荐算法,使用贝叶斯概率对用户特征属性进行分析,根据分析结果形成用户最近邻居集合,通过Hadoop中的MapReduce模型构建预测评分矩阵,最后基于邻居集和用户灰色关联度形成推荐列表.实验结果表明,该算法提高了推荐的有效性和准确度,且能有效支持较大数据集.     

基于MapReduce的文本层次聚类并行化

针对传统的层次聚类算法在处理大规模文本时可扩展性不足的问题,提出基于MapReduce编程模型的并行化文本层次聚类算法。将基于文本向量分量组特征统计的垂直数据划分算法应用于MapReduce的数据分发,将MapReduce的排序特性应用于合并点的选择,使得算法更加高效,同时有利于提高聚类精度。实验结果表明了利用该算法进行大规模文本聚类的有效性及良好的可扩展性。     

基于MapReduce与相关子空间的局部离群数据挖掘算法

针对高维海量数据,在MapReduce编程模型下,提出了一种基于相关子空间的局部离群数据挖掘算法.该算法首先利用属性维上的局部稀疏程度,重新定义了相关子空间,从而能够有效地刻画各种局部数据集上的分布特征;其次,利用局部数据集的概率密度,给出了相关子空间中的局部离群因子计算公式,有效地体现了相关子空间中数据对象不服从局部数据集分布特征的程度,并选取离群程度最大的N个数据对象定义为局部离群数据;在此基础上,采用LSH分布式策略,提出了一种MapReduce编程模型下的局部离群数据挖掘算法;最后,采用人工数据集和恒星光谱数据集,实验验证了该算法的有效性、可扩展性和可伸缩性.     

一种MapReduce架构下基于遗传算法的K-Medoids聚类

由互联网时代快速发展而产生的海量数据给传统聚类方法带来了巨大挑战,如何改进聚类算法从而获取有效信息成为当前的研究热点。K-Medoids是一种常见的基于划分的聚类算法,其优点是可以有效处理孤立、噪声点,但面临着初始中心敏感、容易陷入局部最优值、处理大数据时的CPU和内存瓶颈等问题。为解决上述问题,提出了一种MapReduce架构下基于遗传算法的K-Medoids聚类。利用遗传算法的种群进化特点改进K-Medoids算法的初始中心敏感的问题,在此基础上,利用MapReduce并行遗传K-Medoids算法提高算法效率。通过带标签的数据集进行实验的结果表明,运行在Hadoop集群上的基于MapReduce和遗传算法的K-Medoids算法能有效提高聚类的质量和效率。     

Nutch中PageRank的并行实现

针对目前Nutch搜索引擎中没有实现PageRank计算的缺憾,在分析和研究经典PageRank算法的基础上,通过设置控制站外与站内链接的比重因子a对该算法进行了改进.利用MapReduce处理大数据集的优势,在Nutch机群系统上设计并实现了基于MapReduce的PageRank分布式并行算法.实验结果表明,处理的数据量越大,机群中的节点越多,计算PageRank的效率越高;另外,该分布式并行算法具有较好的可扩展性.     

基于列存储的MapReduce并行连接算法

针对传统关系型数据库在对大数据进行操作时,系统性能严重下降、计算效率提升有限以及可扩展性差等问题,引入MapReduce并行计算模型,提出一种大数据上基于列存储的MapReduce并行连接算法。设计面向大数据的分布式计算模型,包括MapReduce分布式环境下的列存储文件格式MCF,采用协同定位策略实现对分布式存储的优化。使用分片聚集和子连接启发式优化方法,实现大数据在MapReduce分布式环境下并行连接算法。实验结果证明,在大数据分析处理中,该算法在执行时间和负载能力上有着较好的优化性能,同时具有良好的可扩展性。     

基于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算法对大型数据集的分类效果更佳,更适用于大数据环境。     

YARM:基于MapReduce的高效可扩展的语义推理引擎

随着语义网的快速发展,RDF语义数据大量涌现.大规模RDF语义数据推理的一个主要问题是计算量大、完成计算需要消耗很长的时间.显然,传统的单机语义推理引擎难以处理大规模的语义数据.另一方面,现有的基于MapReduce的大规模语义推理引擎,缺乏对算法在分布和并行计算环境下执行效率的优化,使得推理时间仍然较长.此外,现有的推理引擎大多存在可扩展性方面的不足,难以适应大规模语义数据的增长需求.针对现有的语义推理系统在执行效率和可扩展性方面的不足,文中提出了一种基于MapReduce的并行化语义推理算法和引擎YARM.为了实现分布和并行计算环境下的高效推理,YARM做出了以下4点优化:(1)采用合理的数据划分模型和并行化算法,降低计算节点间的通信开销;(2)优化推理规则的执行次序,提升了推理计算速度;(3)设计了简洁的去重策略,避免新增作业处理重复数据;(4)设计实现了一种新的基于MapReduce的并行化推理算法.实验结果表明,在真实数据集和大规模合成数据集上,YARM的执行速度比当前最新的基于MapReduce的推理引擎快10倍左右,同时YARM还表现出更好的数据和系统可扩展性.     

基于MapReduce和IFOA的并行密度聚类算法

针对大数据下密度聚类算法中存在的数据划分不合理、参数寻优能力不佳、并行性能较低等问题,提出一种基于IFOA的并行密度聚类算法(density-based clustering algorithm by using improve fruit fly optimization based on MapReduce,MR-DBIFOA)。首先,该算法基于KD树,提出网格划分策略(divide gird based on KD tree,KDG)来自动划分数据网格;其次在局部聚类中,提出基于自适应搜索策略(step strategy based on knowledge learn,KLSS)和聚类判定函数(clustering criterion function,CCF)的果蝇群优化算法(improve fruit fly optimization algorithm,IFOA);然后根据IFOA进行局部聚类中最优参数的动态寻优,从而使局部聚类的聚类效果得到提升;同时结合MapReduce模型提出局部聚类算法DBIFOA(density-based clustering algorithm using IFOA);最后提出了基于QR-tree的并行合并局部簇算法(cluster merging algorithm by using MapReduce,MR-QRMEC),实现局部簇的并行合并,使算法整体的并行性能得到加强。实验表明,MR-DBIFOA在大数据下的并行效率更高,且聚类效果更好。     

基于人工蜂群算法和XGBoost的网络入侵检测方法研究

为了降低网络入侵检测系统的虚警率,提出一种混合式网络入侵检测方法,将人工蜂群(ABC)算法用于特征提取,XGBoost算法用于特征分类和评价。选择和定义不同的场景和攻击类型,并设计混合式网络拓扑;对预处理后的数据,采用ABC算法进行特征提取,利用XGBoost算法将需要评价的特征进行分类;得到特征的最优子集,利用这些特征完成网络异常检测。在多个公开数据集上的实验结果表明,该混合方法在准确度和检测率方面优于其他方法,且其时间复杂度和空间复杂度较低,表现出较高的检测效率。     

基于数据流的k-近邻连接算法

k-近邻连接查询是空间数据库中一种常用的操作,该查询处理过程涉及连接和最近邻查询两个复杂操作.传统的集中式k-近邻连接查询算法已不能适应当前呈爆炸式增长的数据规模,设计分布式k-近邻连接查询算法成为了目前亟需解决的问题.现有的分布式k-近邻连接查询算法都包括了多轮串行的MapReduce任务,而每个MapReduce任务均需要读写分布式文件系统,导致MapReduce不能有效表达多个任务之间的依赖关系,因此算法效率低下.首先提出了一种基于数据流的计算框架,该框架建立在MapReduce之上,将数据处理过程按照数据流图建模.在该框架基础上,提出了一种高效的k-近邻连接算法,它利用空间填充曲线将多维数据映射为一维数据,从而将k-近邻连接查询转化为一维范围查询.实验结果表明,该算法的可扩展性较高,且效率比现有算法更优.     

奇偶直方图负载均衡超立方对等云MapReduce模型*

针对传统MapReduce算法结构在处理大数据时,负载均衡性能不理想的缺点,设计了一种具有负载均衡机制的层次MapReduce模型。该模型利用超立方拓扑结构对MapReduce的映射操作进行改进,通过特定算法将八个结构化的数据中心链接到一个对等的云环境结构中,并使用奇偶直方图组合采样方式的均衡划分方法,实现在用户请求下的节点工作负荷指数均衡。最后,基于Hadoop框架对所提算法进行仿真实验,结果显示本文所提算法结构相对于原始MapReduce结构,具有更高的并行计算的资源利用率,以及更佳的容错和负载均衡性能,综合性能得到有效提升。     

基于MapReduce的改进的Apriori算法及其应用研究

随着移动通信和互联网技术的迅猛发展,如何高效地分析移动用户的需求并及时推送有用信息成为数据挖掘领域的热点之一。针对上述问题,提出一种基于云计算Hadoop平台的分布式关联规则MRS-Apriori算法。该方法在经典Apriori算法的基础上优化了数据库编码规则,增加了判断标记Judgemark来判断事务项是否频繁,提高了MRS-Apriori算法在连接时扫描数据库的效率。在编码的基础上,采用Hadoop平台下的MapReduce编程框架模型实现并行化处理,提高了迭代时连接步骤的效率,降低了大规模数据样本运算的时间开销。实验结果表明,改进的MRS-Apriori算法可以有效地减少运算时间,在处理大规模数据集上具有较高的准确性。     

基于Isolation Forest的并行化异常探测设计

异常探测具有广泛的应用,受到了工业界和学术界的共同关注。在众多异常探测方法中,Isolation Forest算法具有执行效率高、探测准确度好的特点,获得了众多应用。但是,传统Isolation Forest算法难以处理大规模数据。为解决此问题,设计了一种基于云计算平台的算法。具体地,使用Hadoop分布式存储系统和MapReduce分布式计算框架设计并实现了基于Isolation Forest的并行化异常探测算法PIFH。通过将探测模型构建和数据异常评价的过程并行化,提升了PIFH算法探测异常的执行效率,扩展了其应用范围。利用真实世界数据集验证了所提算法的执行效率和可扩展性。     

基于两阶段改进遗传算法的一类特殊LRP问题研究

提出了一种带有随机开关的两阶段改进遗传算法并应用于集成化物流中的定位 运输路线安排 (LRP)优化问题. 该方法采用随机开关控制遗传算法中的变异运算, 实现了空间的有效搜索, 并且在一定程度上, 避免了“局部最优现象”的发生. 通过计算机仿真实验, 证明了该算法求解LRP问题的有效性和准确性.     

基于分组和IGSA的并行密度聚类算法

针对并行密度聚类算法在处理大数据集时存在伸缩困难、参数寻优能力不佳、并行化效率较低等问题,提出一种基于分组和重力搜索优化算法(improve gravitational search algorithm,IGSA)的并行密度聚类算法(densi-ty-based clustering algorithm based on groups and improve gravitational search,MR-GDBIGS).首先,该算法设计了基于图形的分组策略(grouping strategy based on pattern,GSP)来有效划分数据,加速邻域搜索,解决了处理大数据集时伸缩困难的问题;其次,在局部聚类中提出基于位置更新函数(position update function,PUF)的重力搜索优化算法,动态寻找局部聚类中的最优参数,提升了局部聚类的效果;最后,提出基于覆盖树的并行局部簇合并策略(cluster merging strategy by using MapReduce,MR-CTMC),在实现局部簇并行化合并的同时加快了合并局部簇的收敛速度,提升了算法整体的并行化效率.实验结果表明,MR-GDBIGS算法在处理大数据时的聚类效果更佳,且并行化性能更好.