改進貝葉斯分類算法的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