改进贝叶斯分类算法的MapReduce并行调度算法

梁宇轩， 邢永山， 张 千

(中国石油大学(华东) 计算机与通信工程学院，青岛 266580)

改进贝叶斯分类算法的MapReduce并行调度算法

梁宇轩， 邢永山， 张 千

(中国石油大学(华东) 计算机与通信工程学院，青岛 266580)

在分析作业划分及现有调度策略的基础上，提出了改进贝叶斯分类算法的作业调度策略，对贝叶斯分类调度算法及MapReduce默认调度方式处理大规模数据时面临的问题进行了阐述，详细地介绍了该改进算法的具体思路和整体流程，描述了该改进算法的具体实现，分析了该调度算法相对其它调度算法的优势。通过实验验证采用改进的贝叶斯调度算法与常用调度算法执行速度进行比较，取得了较好的效果。

贝叶斯分类算法; MapReduce; 地震资料处理; 并行调度

0 引言

地震资料处理的的数据信息属于海量数据，如果要将大量的数据信息进行并行处理，需要计算机具备较强的系统性能。在对石油专业技术领域中已有的地震资料数据并行处理调度器进行深入探究的过程中，利用贝叶斯调度算法对并行环节进行全面改进与优化，能够科学高效的选取最合理的任务将其与slave节点相结合。可以有效地避免因设置固定的无经验参数，使得系统运作的效率受到严重的影响[1]。贝叶斯调度算法在具体操作中也具有一定的不足，该技术算法将作业任务分配到不同的队列进行处理时的欠缺体现如下：

1)reduce任务在操作过程中所输入数据，实际上就是map任务在运作时输出的中间结果，map输出的数据在本地磁盘中进行有效地存储。也就是说，reduce任务在运作过程中，诸多的时间都是在进行copy数据阶段的操作。单炮地震资料数据在实际操作时的任务量十分庞大，若较多的节点同时进行copy操作，会大大降低系统运行的效率[2]。

2) 预先设置的系统资源参数分配属于固定值的设置形式，在实践应用中未能够有针对性的发挥作用[3]。

3) 贝叶斯调度算法在应用过程中，是根据某一时刻负载状况，把作业按其质量进行划分，质量较好的作业队列中的作业任务会一直进行调度，较差质量的作业任务将会被丢弃，这种操作形式未能够对系统的实时负载平衡方面进行综合思考，而且某时刻的坏作业对于后续关键作业环节会造成极为严重性的影响，将会使得整个作业在运作过程中无法有效地实施[4-5]。

1 改进贝叶斯调度算法的基本思想

结合传统贝叶斯调度算法在具体应用过程中的欠缺之处，进行技术优化的贝叶斯调度算法将作业任务按照合理的技术形式进行划分，将并发粒度比较理想的作业按其有效性，划分为多个队列操作形式，并分配到与计算量相匹配协调系统资源。在对地震资料数据信息采取技术操作的过程中，将JobTracker队列中作业按负载状况综合性地分析与思考，决定采取什么样的技术手段能够确保对作业任务有效地并行处理，进而合理地降低通信数据信息的花费[6-7]。

Hadoop所对应的进程速率计算为式(1)。

progressRate=progressScore/t

(1)

式中：progressScore为已完成任务进度默认值；当前任务所花费的时间为t，进而估算出此作业从当前到完成所花费的剩余时间(式(2))。

(2)

为了描述算法的执行流程，我们定义该调度算法常用的作业描述词以及判定条件如下。

定义1 慢任务：节点中某个task进度值比同job中的task平均进度的临界值要低，用参数SlowTaskPoint表示，取值为25%。

定义2 好作业：计算概率不会造成TaskTracker作业产生过载情况的就是好作业，好作业将在系统中优先进行调度。

定义3 等待作业：导致TaskTracker出现过载的作业为等待作业，这种形式的作业会滞后运行调度。

定义4 作业属性：将作业大小、道数值设置为作业属性的基本变量。

定义5 资源属性：该属性表示的是一个计算节点在具体运作时资源的基本状态。

在实际应用过程中，本文的计量值选取了具有代表性的节点剩余CPU使用率、系统内部剩余的内存、硬盘可用空间大小这些基本的参数。

定义6过载条件判定：调度算法负载阈值HighLoad和LowLoad这两个参数值设置为87%和66%。

对上述基本属性进行分析，任何一个属性在实际应用中都存在一个边界区域，临近此区域将会造成节点过载的情况，全部临界区域相近的点有机的构成一个超平面[8]，且作业属性、数据信息的资源需要采取独立的方式进行分析与假设，采用优化后的朴素贝叶斯分类器能够合理有效地对作业任务进行处理[9]。

改进贝叶斯作业在调度过程中，目标函数f(x)在有效的集合V中按照指定的技术方式进行取值。

V={gjob，wjob}

(3)

其中：Gjob为好作业；wjob为等待作业

按照朴素贝叶斯定理实现作业分类，最终的计算方式为式(4)。

(4)

实例νj相关属性值可由上述定义描述。

贝叶斯公式经过一定形式的变换，获取到具体的公式为式(5)。

(5)

将稀疏矩阵所存在的问题综合分析，在给定目标值的情况下对每个属性相互独立性条件进行定义

(6)

式(5)中P(a,…,an)在为固定值，需要对其大小进行综合性分析与对比，将其简化后的形式如式(7)。

(7)

式(7)在条件独立性假设条件下，可简化为式(8)。

(8)

式中，对于∀νj∈{gjob,wjob},在对应最大值情况下，νj取值gjob时将该job确认为好作业，νj取值wjob将该job确认为等待作业。

对于∀νj∈{gjob,wjob}、∀i∈[1,n]，估算P(νi)比较容易得到，计算P(ai|νj)的计算量比要计算P(a1,…,an|νj)要小得多，它们均可在不同作业类别与属性数据训练样本集中组合，来获得概率值或者直接设置默认概率值。

这样如果节点产生空闲，作业调度服务器依照心跳信息对闲置状态进行发现，利用改进的贝叶斯调度算法在作业队列中，选取作业任务按其上述的算法公式对其科学有效地划分。通常情况下，这种改进的作业调度算法能够精准高效的获取到适当的作业任务[10-11]。

2 改进贝叶斯调度算法的流程

通过改进贝叶斯调度算法的综合分析与阐述，采用简单的学习过程或设置默认概率，结合过载与心跳信息，将该参数作为调节因子进行具体地应用，系统在实践操作过程通过自适应地调节形式，以不同属性值在任务操作时的基本情况为核心，对其先验概率大小进行判定[12]，所对应的实时调度算法操作流程如图1所示。

在整个操作过程中，对地震资料数据信息的综合分析与调度，能够有效地获取到经过优化改进的贝叶斯调度算法流程(图2)。

图1 改进的贝叶斯调度算法流程图Fig.1 The flowchart of improved the Bayes scheduling algorithm

图2 贝叶斯算法改进的并行调度流程图Fig.2 The flowchart of parallel scheduling based on improved Bayes algorithm

根据图2能够清晰地判定出，经过改进的贝叶斯调度算法的基本步骤：

1) JobTracker需要在TaskTracker中定时有效地获取到相应的心跳信息，结合心跳信息实时对作业任务及节点属性等参数进行相应的处理。

2) 通过上个步骤的操作，能够判断某个节点是否为空闲节点的参数条件，如果不是空闲节点可以停止操作；如果是空闲节点，需要在此环节中调入作业，继续步骤3)的操作。

3) JobTracker周期性地对集群内部执行的任务进行综合性的分析与计算，并且需要综合性的将所计算获取到的节点的任务状态与慢任务进行结合，对临界值SlowTaskPoint深入分析和对比，如果运作过程中有慢任务，需要在其中对慢任务进行有效地处理；没有慢任务存在的情况下，直接操作步骤4)即可。

4) 针对章任务划分后的作业队列，在队列有效的选取除本地节点数据相对应的任务执行，如果不对划分后的数据信息进行科学性的处理，需要进行步骤5)的操作。

5) 通过改进的贝叶斯调度计算算法，利用最大概率方式有效地获取到最佳的作业，将其有效的划分为4操作步骤：①JobTracker作用是对TaskTracker的心跳信息进行有效的接收；② 结合设置操作过程中相应的过载条件和学习阶段相应的属性概率，对上次通过贝叶斯分类调度方式所实施的TaskTracker的任务在具体操作过程中的执行状况进行全面的分析与对比，进而能够重新生成每一种属性在最佳状态中的概率值；③在系统中最长的等待队列中进行作业的选取，通过公式(8)的最大概率估计，有效的明确作业的划分；④如果获取到的计算作业是好作业，需要将此类作业分配至资源节点对其进行专业性的处理，有效的实现此阶段的调度，反之继续进行③作业的分析与判。

6) 在TaskTracker任务中有效的实施之后，该TaskTracker需要结合心跳信息，把任务的实际情况向JobTracker进行传送，继续步骤1)～步骤6)的操作。

3 实验测试

将改进的贝叶斯调度算法在应用过程中，与MapReduce常用的FIFO、公平调度以及计算能力调度的三种调度算法进行对比。

FIFO调度算法在实施过程中十分地简便，而公平份额调度算法与计算能力调度算法则需要在任务服务器上设置最多同时运行的任务数目，并且需要增加对逐个资源的描述，不仅增加提交任务的难度及工作量，对没有经验的管理员来言，每更换一批任务是非常大的难题，若参数设置不合适也会对整体运行性能造成不利影响。因此，在测试中需要对CPU设置占用较多的参数方式，因而减少对公平调度算法和计算能力调度算法的性能影响[13]。

在测试中，笔者采用节点的静态分配与全局数组存储资源，通过简单的训练学习，设置在等待作业与好作业的属性概率，分别计算600、500、400及200炮地震资料数据，并对各炮集处理结果进行比较，在实验操作过程中相应炮集数据处理的对比结果如图4所示。

图3 处理不同炮数据的调度算法比较Fig.3 Comparison of different scheduling algorithms in processing mass gun data

根据图4中的数据信息能够分析出，FIFO调度算法在实际应用中的处理效率分布与直线较为相近，与同种类型的作业运作情况相比，在安全稳定性方面较为理想，但调度算法运作效率比较差。改进的调度算法在实际应用中，首先对简单的学习过程进行一定的优化，随着操作过程中数据信息的不断增加，运行时间与其他三种调度算法相比具有一定显著性的功能特性。

4 结论

将改进的贝叶斯分类调度技术操作算法与系统默认调度算法进行综合性的分析与对比，发现此算法的优势体现如下：

1) 通过自适应的对相应属性特征，设置默认概率值进行调整，在节点出现空闲的情况下，本地慢任务可以优先进行技术操作。

2) 对相应任务操作过程中的最大估计剩余时间进行分析，对慢任务的认定不是通过简单的进度值来确定，而是某个task的进度值小于同一job下task平均进度某一百分比时才认定为慢任务。

3) 在慢任务未出现的情况下，将优先调度静态作业队列中相关的任务执行，进一步提高Map并行任务的速度，避免频繁交互通信及复制数据，最大限度减小云计算环境的资源浪费。

将上述调度算法与地震资料数据信息处理相结合，这种技术方式能够合理地减少数据信息在不同节点间中进行数据处理的资源消耗，大大增强算法的运算效率。

[1] 邢永山.基于云计算的并行调度的研究[D].青岛：中国石油大学(华东),2012. XING Y S. Study on parallel dispatching based on cloud computing [D]. Qingdao: China University of Petroleum (East China), 2012.(In Chinese)

[2] LU HAO,LIN JUN,ZENG XIAO-XIAN.Research and application of improved naive bayesian classification algorithm[J].Journal of Hunan University Natural Sciences,December 2012,39(12):56-61.

[3] JIN L-C,WAN W-G,CUI B.A new multimedia classification approach: Bayesian of inductive cognition algorithm based on dirichlet process[J].Imaging Science Journal,December 2010,58(6):331-339.

[4] AL BATAINEH,MOHAMMAD,AL-QUDAH ZOUHAIR.A novel gene identification algorithm with Bayesian classification[J].Biomedical Signal Processing and Control,January 1,2016,31(4):6-15.

[5] KIM HYUN-CHUL,GHAHRAMANI, ZOUBIN.Bayesian Gaussian process classification with the EM-EP algorithm[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(12):1948-1959.

[6] WANG X Z.A layered Bayesian network intrusion detection algorithm[J].Metallurgical and Mining Industry,2015,7(9):724-732.

[7] ZHANG YU,ZHOU GUOXU,JIN JING.Sparse Bayesian classification of EEG for brain-computer interface[J].IEEE Transactions on Neural Networks and Learning Systems,September 23,2015,30(8)：99-102.

[8] GOPAL SIDDHARTH,YANG YIMING.Hierarchical bayesian inference and recursive regularization for large-scale classification[J].ACM Transactions on Knowledge Discovery from Data,2015, 9(31):136-140.

[9] LI ZHI QIANG,YANG DE QUAN,TAN YUAN.An improved naive Bayesian classification algorithm for sentiment classification of microblogs[J].Applied Mechanics and Materials.2014,43(5):3614-3620.

[10]RIDGWAY JAMES,ALQUIER PIERRE.Chopin Nicolas PAC-Bayesian AUC classification and scoring[J].Advances in Neural Information Processing Systems,2014,21(1):658-666.

[11]DU CHANGYING,HE JIA,ZHUANG FUZHEN.Nonparametric bayesian multi-task large-margin classification[J].Frontiers in Artificial Intelligence and Applications,2014, 63(2): 255-260.

[12]SALAMA KHALID M,FREITAS, ALEX A.Classification with cluster-based Bayesian multi-nets using Ant Colony Optimisation[J].Swarm and Evolutionary Computation,2014, 18:54-70.

[13]HU DIE,WAN MENG.Common bayesian network for classification of EEG-based multiclass motor imagery BCI[J].IEEE Transactions on Systems,June 2016,46(6):843-854.

Parallel scheduling algorithm with improved Bayesian classification algorithm

LIANG Yuxuan, XING Yongshan, ZHANG Qian

(School of Computer and Communication Engineering, China University of Petroleum (East China), Qingdao 266580, China)

Based on the analysis of job partitioning and existing scheduling strategies, we proposes a job scheduling strategy that improves the Bayesian classification algorithm, and expounds the problems faced by the Bayesian classifier and the MapReduce default scheduling method in dealing with large-scale data in this paper. The concrete idea and the whole process of the improved algorithm, describes the concrete realization of the improved algorithm, and analyzes the advantages of the algorithm compared with other scheduling algorithms are introduced. The experimental results show that the improved Bayesian scheduling algorithm is more effective than the conventional scheduling algorithm.

Bayesian classification algorithm; MapReduce seimic data; processing; parallel scheduling

2016-12-17 改回日期：2017-03-08

国家自然基金(61671482)

梁宇轩(1996-)，男，硕士,研究方向为高性能计算,E-mail：liangh@upc.edu.cn。

张千(1980-)，女，博士，副教授，研究方向为高性能计算，E-mail：zhangqian@upc.edu.cn。

1001-1749(2017)03-0411-05

TP 319

A

10.3969/j.issn.1001-1749.2017.03.18