李孜穎，石振國

（南通大學(xué)信息科學(xué)技術(shù)學(xué)院，江蘇南通 226001）

（*通信作者電子郵箱chinaemail@sohu.com）

0 引言

隨著近些年數(shù)據(jù)爆發(fā)式的增長，越來越多的人將注意力集中到了大數(shù)據(jù)領(lǐng)域。大數(shù)據(jù)具有容量巨大、種類繁多、來源復(fù)雜、價值密度低等特征［1］，對此，市面上也出現(xiàn)了很多通用底層大數(shù)據(jù)系統(tǒng)來處理大數(shù)據(jù)，如Hadoop、Spark 等［2］。然而對于多數(shù)大數(shù)據(jù)系統(tǒng)，內(nèi)部任務(wù)的劃分標準不一，對大數(shù)據(jù)任務(wù)資源的分配也缺乏一定合理性，大數(shù)據(jù)任務(wù)處理流程存在不規(guī)范的問題。因此，本文將任務(wù)調(diào)度理論引入到大數(shù)據(jù)任務(wù)處理中，幫助建立合理的大數(shù)據(jù)任務(wù)管理體系，從而規(guī)范大數(shù)據(jù)任務(wù)處理流程，提高大數(shù)據(jù)任務(wù)處理效率。

調(diào)度即是一種時間、空間上的排序。例如車站對班車的排班是一種調(diào)度，操作系統(tǒng)將進程提交給中央處理器（Central Processing Unit，CPU）也是一種調(diào)度。大數(shù)據(jù)的處理過程也可以看作是一種任務(wù)調(diào)度，即根據(jù)實際的大數(shù)據(jù)任務(wù)和資源情況，將資源分配給相應(yīng)的大數(shù)據(jù)任務(wù)加以執(zhí)行的過程，而任務(wù)調(diào)度的關(guān)鍵則在于如何精準地劃分任務(wù)以及合理高效地為任務(wù)分配資源。

任務(wù)調(diào)度問題在許多不同領(lǐng)域中都有一定的研究［3-9］。例如，文獻［7］針對廣域信息管理系統(tǒng)，提出一種多服務(wù)質(zhì)量（Quality of Service，QoS）約束條件的蟻群優(yōu)化任務(wù)調(diào)度算法；文獻［8］針對移動云計算中有向無環(huán)圖（Directed Acyclic Graph，DAG）模型的任務(wù)調(diào)度問題，提出了一種能效任務(wù)調(diào)度算法；文獻［9］針對對等網(wǎng)絡(luò)環(huán)境，提出一種能有效利用網(wǎng)絡(luò)資源的基于相似度的任務(wù)調(diào)度算法等。

上述文獻均是對任務(wù)調(diào)度問題的研究，但將任務(wù)調(diào)度理論與大數(shù)據(jù)相結(jié)合還不多見。本文將大數(shù)據(jù)任務(wù)的處理看作是一種任務(wù)調(diào)度，并以此為基礎(chǔ)，提出一種面向大數(shù)據(jù)任務(wù)的調(diào)度方法模型。本文工作主要有：

1）針對大數(shù)據(jù)任務(wù)劃分標準不統(tǒng)一、處理流程不規(guī)范的問題，在大數(shù)據(jù)任務(wù)處理中引入任務(wù)調(diào)度理論，建立合理的任務(wù)管理體系，精準劃分任務(wù)，規(guī)范任務(wù)流程，提高大數(shù)據(jù)處理效率。

2）針對大數(shù)據(jù)容量巨大、種類和來源復(fù)雜、噪聲多的問題，引入粗糙集中的決策表屬性約簡方法，提出一種基于互信息的大數(shù)據(jù)決策表約簡模型，從而減少大數(shù)據(jù)分析任務(wù)的數(shù)據(jù)量，提高大數(shù)據(jù)分析效率。

3）針對大數(shù)據(jù)任務(wù)資源分配缺乏一定合理性的問題，引入模糊數(shù)學(xué)中的模糊綜合評價方法，將模糊綜合評價的結(jié)果作為對任務(wù)分配資源的依據(jù)，提高任務(wù)資源分配合理性。

4）針對大數(shù)據(jù)任務(wù)的處理，提出一種面向大數(shù)據(jù)任務(wù)的調(diào)度方法模型，并給出算法具體流程和步驟，從而實現(xiàn)對大數(shù)據(jù)任務(wù)的調(diào)度。

5）將所提出的面向大數(shù)據(jù)任務(wù)的調(diào)度方法模型應(yīng)用在實際數(shù)據(jù)集中測試，并對測試結(jié)果進行分析；實驗結(jié)果表明，該調(diào)度模型能夠有效提高處理大數(shù)據(jù)任務(wù)的效率。

1 大數(shù)據(jù)任務(wù)分析及處理方法

1.1 大數(shù)據(jù)任務(wù)分析

在現(xiàn)代主流的大數(shù)據(jù)系統(tǒng)中，大數(shù)據(jù)任務(wù)通常用DAG 表示［10］，其中頂點是大數(shù)據(jù)任務(wù)，連接頂點的邊是大數(shù)據(jù)任務(wù)之間的關(guān)系。不可避免的，大數(shù)據(jù)任務(wù)間要共享集群資源，對此，按照什么樣的標準劃分大數(shù)據(jù)任務(wù)并為其分配資源就成為了一個十分重要的問題。

在現(xiàn)代大數(shù)據(jù)系統(tǒng)中，通?？蓪⒋髷?shù)據(jù)任務(wù)分為四大類，即數(shù)據(jù)采集、數(shù)據(jù)處理與集成、數(shù)據(jù)分析以及數(shù)據(jù)解釋［11］。在大數(shù)據(jù)處理的過程中，由于經(jīng)過數(shù)據(jù)采集任務(wù)所得到的數(shù)據(jù)，其數(shù)據(jù)結(jié)構(gòu)各不相同，因此需要對采集到的數(shù)據(jù)處理成統(tǒng)一標準格式的數(shù)據(jù)，并將處理后的數(shù)據(jù)進行存儲。數(shù)據(jù)完成預(yù)處理任務(wù)后，需要選用合適的數(shù)據(jù)分析方法對這些處理過的數(shù)據(jù)進行分析，并通過可視化等技術(shù)，將數(shù)據(jù)分析的結(jié)果向用戶展示。

1.2 決策表的相關(guān)概念

決策表是用來描述和分析過程化決策情形的一種表格狀表示方式［12］。在決策表中，以行、列的形式來描述和表示決策規(guī)則和知識信息。決策表概念的系統(tǒng)化定義如下。

定理1設(shè)ai(i=1，2，…，m)表示可供選擇的決策行為，AS是ai的集合。θkj(j=1，2，…，n)是一個邏輯表達式，Sj表示θkj的集合。用xij表示實施決策ai后，自然狀態(tài)是θj的決策結(jié)果，xij={0，1}。決策表DT即可用來表示一個從θj到xij的映射。由定理1 可知，一個決策結(jié)果在決策表模型中是由一個或多個Sj表示的，即每一個xij對應(yīng)輸入的不同Sj，不同的Sj會形成不同的xij。

在定理1 所述經(jīng)典決策表模型中，只有行為和結(jié)果，對于一些復(fù)雜的系統(tǒng)，往往有多種不同的行為同時起作用，在這種情況下，不能僅僅考慮行為與結(jié)果，對此，有帶權(quán)重的決策表模型［13］如下：

定理2設(shè)Ai(i=1，2，…，m)表示可供選擇的第i個決策行為集，Sj(j=1，2，…，n)表示第j個結(jié)果集。用Xij表示決策集Ai對結(jié)果集Sj的權(quán)重集，且

引入變量P[j]表示各結(jié)果集發(fā)生的可能性，則

設(shè)閾值為q，則

1.3 基于互信息的大數(shù)據(jù)決策表約簡模型

屬性約簡又稱知識約簡，是指為了保留最小屬性數(shù)的特征子集，在不改變知識庫分類能力的前提下，刪除冗余知識的過程［14］。當前數(shù)據(jù)庫系統(tǒng)通?？梢詫?shù)據(jù)進行插入、查找、分類等操作，但是想要知曉數(shù)據(jù)間到底有著怎樣的內(nèi)在聯(lián)系卻很困難，而屬性約簡可以更好地幫助發(fā)現(xiàn)數(shù)據(jù)其中的聯(lián)系［15-19］。

在決策表中，為了了解各種條件屬性對于決策重要性的影響，可以計算條件屬性與決策屬性間的互信息［20］，因此可以利用互信息對決策表進行屬性約簡。

根據(jù)式（6），可通過計算決策屬性D與條件屬性a之間互信息的大小，來衡量條件屬性對于決策的重要性?；バ畔⒅翟酱?，該屬性對于決策起到的重要性也就越大。對于決策表的約簡，有下述定理：

定理3在相容決策表DT中，A?C，當且僅當MI(D：C)=MI(D：A)時，A是C相對于決策屬性集D的一個約簡，且A相對于D是獨立的。［22］

根據(jù)定理3，本文提出基于互信息的大數(shù)據(jù)決策表約簡算法，算法從初始的條件屬性集開始，循環(huán)并逐步刪去冗余屬性。本文算法具體步驟如下：

輸出DT的約簡結(jié)果AR。

Step1 計算DT的互信息MI（D：C）。

Step2 從C中隨機選取一個條件屬性ai，計算出對于每一個ai∈C，其互信息MI(D：{ai})的值，并按照升序進行排列。

Step3 令A(yù)R=DT，重復(fù)以下操作直至循環(huán)結(jié)束：

Step3.1 計算MI(D：AR-{ai})的值。

Step3.2 如果MI(D：C)=MI(D：AR-{ai})，ai可約簡，令A(yù)R=AR-{ai}；反之，ai不可約簡，AR不變。

Step4 循環(huán)結(jié)束，得到約簡結(jié)果AR。

1.4 模糊綜合評價法

在模糊數(shù)學(xué)的所有綜合評價法之中，模糊綜合評價法是常用的一種方法。根據(jù)模糊數(shù)學(xué)中的隸屬度原理，模糊綜合評價法可以將對事物的定性評價轉(zhuǎn)變成對事物的定量評價，因此該方法也經(jīng)常用于為受到多種因素影響的事物進行全面的綜合評價［23］。

針對大數(shù)據(jù)任務(wù)調(diào)度系統(tǒng)，任務(wù)的調(diào)度結(jié)果也是受多種因素影響，具有不確定性和模糊性，因此可用模糊綜合評價法來對任務(wù)進行分類，將對任務(wù)評價的結(jié)果作為對任務(wù)進行調(diào)度的結(jié)果。

模糊綜合評價步驟［24］如下：

1）確定評價對象。

2）確定評價指標集U。

評價指標集是指評價者對被評價對象進行評價所依照的評價指標的集合，可能會存在多級指標，且U={u1，u2，…，un}。

3）確定評價等級（評語集）V。

不同的評價者對不同的評價對象可能會有不同的評價等級。評語集就是這些所有可能的評價結(jié)果的集合。且V={v1，v2，…，vm}。

4）確定評價指標的權(quán)重W。

各評價指標的權(quán)重大小，反映了各評價指標對于評價結(jié)果的重要程度大小。由于各評價指標權(quán)重大小的不同，可能導(dǎo)致最終得到的評價結(jié)果差異很大，因此如何確定評價指標的權(quán)重是模糊綜合評價中至為關(guān)鍵的一步。權(quán)重W=(w1，w2，…，wn)，且各評價因素的權(quán)重總和為1，即1(wi＞0)。

常用的確定權(quán)重的方法主要有德爾菲法確定權(quán)重法、層次分析（Analytic Hierarchy Process，AHP）確定權(quán)重法、熵值確定權(quán)重法等。

德爾菲法確定權(quán)重法［25］是根據(jù)專家的知識、經(jīng)驗、綜合分析能力等，對各項評價指標判斷、分析并為其賦予權(quán)值，該方法是最常用的確定權(quán)重方法。

將定性與定量相結(jié)合是AHP［26］的特點，核心是定量描述決策者的經(jīng)驗和判斷，增強決策依據(jù)，提高決策準確性。為綜合計算各指標的權(quán)重系數(shù)，AHP建立了等級評價指標體系，根據(jù)同等級的指標直接相對重要性來衡量。

熵值確定權(quán)重法［27］是一種客觀的賦權(quán)法，通過對各項指標進行觀測，并根據(jù)所觀測得到的信息大小確定各項指標權(quán)重。信息熵是信息論中對信息的不確定性的一種量化度量，信息熵公式為

其中：p表示隨機變量x的輸出概率。通過式（7）可以看出，信息量越大，變量x的不確定性越小，信息熵也就越?。环粗嗳?。因此可以使用信息熵來衡量各指標的變異程度，從而計算出各項指標的權(quán)重。

針對大數(shù)據(jù)任務(wù)，采用層次分析法AHP 確定各評價指標的權(quán)重。

5）建立模糊關(guān)系矩陣R。

單因素模糊評價［28］即逐個對被評事物依據(jù)評價指標集U進行量化，也就是得到評價對象ui(i=1，2，…，n)對每個評價結(jié)果的隸屬度(R|ui)，進而可以得到模糊關(guān)系矩陣R，即

6）合成模糊綜合評價結(jié)果矢量。

對多個評價指標進行綜合評價，選用適當?shù)哪：铣伤阕?，將模糊?quán)重W與各被評事物的模糊關(guān)系矩陣R進行合成，可以得到各被評價事物的模糊綜合評價結(jié)果矢量B，且

常見的模糊合成算子有M(∧，∨)、M(·，∨)、M(∧，⊕)、M(·，⊕)四種［23］，這四種算子的特點如表1所示。

表1 四種模糊合成算子的特點Tab.1 Features of four fuzzy synthetic operators

針對大數(shù)據(jù)任務(wù)的特性，采用加權(quán)平均型的模糊合成算子M(·，⊕)，對于多個被評價對象，可以依據(jù)其等級位置進行排序。

2 面向大數(shù)據(jù)任務(wù)的調(diào)度方法模型

2.1 任務(wù)調(diào)度模型原理

由于歷史調(diào)度任務(wù)中，資源使用情況以及執(zhí)行時間均已知。根據(jù)K近鄰思想［29］，對于輸入的新實例，若在訓(xùn)練集中能找到與該實例最相鄰的k個實例，并且這些實例多數(shù)屬于某個類，就把該輸入的新實例分類到這個類中。若兩個任務(wù)數(shù)據(jù)集的模糊綜合評價結(jié)果相近，可以認為這兩個任務(wù)數(shù)據(jù)集的資源使用情況以及執(zhí)行時間也相近。

當要執(zhí)行新的大數(shù)據(jù)任務(wù)數(shù)據(jù)集時，先對其進行屬性約簡，再對其進行模糊綜合評價，根據(jù)評價結(jié)果調(diào)度分配資源。該流程如圖1所示。

圖1 調(diào)度策略流程Fig.1 Scheduling strategy flowchart

2.2 任務(wù)調(diào)度模型算法

有n個歷史任務(wù)的數(shù)據(jù)集DS={DS1，DS2，…，DSn}

Step1 對DS進行屬性約簡，得到約簡后的結(jié)果DS′；對DS′進行模糊綜合評價，得到評價后的結(jié)果DS″={DS"1，DS"2，…，DS"n}。

Step2 輸入新任務(wù)P，對P進行屬性約簡，得到約簡后的結(jié)果Q。

Step3 對Q進行模糊綜合評價，得到評價結(jié)果B。

Step4 遍歷DS″，找出與B最為相近的DSj"。

Step5 根據(jù)DSj"的歷史資源分配和歷史任務(wù)執(zhí)行情況生成工作流，預(yù)估并為P分配資源。

3 實驗與結(jié)果分析

3.1 實驗過程

為評估本文所提出的算法，采用基于Apache Hadoop平臺的Oozie［30］框架進行任務(wù)調(diào)度。

實驗選取UCI（University of California Irvine）［31］數(shù)據(jù)庫中的10 個數(shù)據(jù)集，將其中70%的數(shù)據(jù)集用作訓(xùn)練數(shù)據(jù)集，30%的數(shù)據(jù)集用作測試數(shù)據(jù)集。通過所提出的基于互信息的屬性約簡方法對UCI 數(shù)據(jù)集進行屬性約簡，之后對屬性約簡后的數(shù)據(jù)集進行模糊綜合評價，以模糊綜合評價結(jié)果在測試集上預(yù)測的實際表現(xiàn)來評估本文算法。實驗所選取的數(shù)據(jù)集信息如表2所示，其中：m表示約簡前的條件屬性個數(shù)，M表示約簡后的條件屬性個數(shù)。

將各數(shù)據(jù)集的樣本數(shù)u1、類別數(shù)u2、約簡后的條件屬性數(shù)u3、數(shù)據(jù)集要執(zhí)行的任務(wù)類型u4作為評價對象，即指標集U={u1，u2，u3，u4}。將各數(shù)據(jù)集與歷史調(diào)度任務(wù)數(shù)據(jù)集的相似度1～5 作為評語集，其中5 表示最為相似，1 表示最不相似，即評語集V={1，2，3，4，5}。對U中的每一個ui做單因素判斷，確定ui對每個評價結(jié)果的隸屬度(R|ui)，進而確定模糊關(guān)系矩陣R，即各數(shù)據(jù)集從不同的單指標來看對各等級模糊子集的隸屬程度。

單因素評價獲得模糊關(guān)系矩陣后，為評價指標集中的各個指標在評價目標中的不同地位和作用，在控制實驗樣本和實驗環(huán)境不變的前提下，各評價因素的權(quán)值變化如圖2 所示，得到各評價因素的最優(yōu)權(quán)值W=(0.1，0.1，0.2，0.6)。

表2 實驗所用數(shù)據(jù)集信息Tab.2 Information of datasets used in experiments

用W對R中不同的行進行綜合，得到該被評事物從總體上來看對各等級模糊子集的隸屬程度，即模糊綜合評價結(jié)果向量B。以B的結(jié)果為基礎(chǔ)，生成工作流并提交給Oozie 進行調(diào)度。

圖2 各評價因素的權(quán)值變化Fig.2 Weight changes of different evaluation factors

3.2 實驗結(jié)果與分析

為評估本文算法效果，將樸素貝葉斯（Naive Bayes，NB）算法、誤差反向傳播（error Back Propagation，BP）算法、均方根傳遞（Root Mean Square Prop，RMSProp）算法與本文算法進行對比。其中：NB 算法是一種利用概率統(tǒng)計進行分類的算法；BP 算法是一種按照誤差逆向傳播算法訓(xùn)練的多層前饋神經(jīng)網(wǎng)絡(luò)算法，在實際中被廣泛采用；RMSProp算法加入衰減系數(shù)控制歷史信息獲取，是一種有效且實用的神經(jīng)網(wǎng)絡(luò)優(yōu)化算法。不同算法的預(yù)測準確度對比實驗結(jié)果如表3所示。

整體來看，本文算法在平均預(yù)測準確度上比NB 算法高7.42 個百分點，比BP 算法高5.16 個百分點，比RMSProp 算法高3.74 個百分點，這是由于屬性約簡保留了最小屬性數(shù)的特征子集，在不改變知識庫分類能力的同時，去除了數(shù)據(jù)集中的噪聲，從而提高了預(yù)測精度。結(jié)合不同的數(shù)據(jù)集分析，對于特征數(shù)較少的數(shù)據(jù)集如Iris、Balance scale，本文算法的預(yù)測精度略高于其他三種；對于特征數(shù)較多的數(shù)據(jù)集如Ionosphere、Sonar等，本文算法較其他算法在預(yù)測精度上有顯著提高。

為評估本文所提調(diào)度算法性能，將HCPFS（Heterogeneous Critcal Path First Synthesis）算法［32］和HIPLTS（Heterogeneous Improved Priority List for Task Scheduling）算法［33］與本文算法進行對比。采用調(diào)度長度下界比（Schedule Length Ratio，SLR）、加速比作為算法評估指標，SLR和加速比sr的計算公式如下所示：

表3 不同算法的預(yù)測準確度對比實驗結(jié)果 單位：%Tab.3 Experimental results comparison of prediction accuracy by different algorithms unit：%

使用Oozie 按照文獻［34］提供的方法生成隨機任務(wù)圖。具體設(shè)置參數(shù)如下：

1）節(jié)點數(shù)nodes={20，30，40，50，60，70，80，90，100}；

2）節(jié)點出度outdegree={1，2，5，20}；

3）通信計算比（Communication to Computation Ratio，CCR），CCR={0.1，0.2，0.5，1，2，5，10}；

4）圖形狀參數(shù)α={0.5，1.0，2.0}；

5）處理器計算開銷β={0.1，0.2，0.25，0.5，0.6，0.75，1}。

三種調(diào)度算法平均SLR和平均sr的實驗對比結(jié)果如圖3所示。

圖3 三種調(diào)度算法平均SLR和sr的實驗對比結(jié)果Fig.3 Experimental results comparison of average SLR and sr by three scheduling algorithms

通過實驗數(shù)據(jù)可以看出，相較于HCPFS 算法和HIPLTS算法，本文算法的平均SLR分別下降了12.14%和4.56%，平均sr分別提升了7.14%和42.56%，說明本文算法具有更好的任務(wù)調(diào)度性能，能夠有效提高任務(wù)調(diào)度效率。

4 結(jié)語

針對大數(shù)據(jù)處理流程中如何合理高效分配資源的問題，本文引入任務(wù)調(diào)度理論，提出了一種面向大數(shù)據(jù)任務(wù)的調(diào)度方法。該方法結(jié)合粗糙集理論，引入決策表模型進行屬性約簡，從而去除不重要和冗余屬性以保持知識分類的不變，提高大數(shù)據(jù)任務(wù)處理的效率；同時引入模糊綜合評價方法，將模糊綜合評價結(jié)果作為對任務(wù)進行調(diào)度的依據(jù)，提高任務(wù)資源分配合理性。通過在UCI 數(shù)據(jù)集上的實驗結(jié)果分析表明，該算法能有效提高預(yù)測精度；通過與HCPFS 算法和HIPLTS 算法實驗對比，表明本文算法能有效提高大數(shù)據(jù)系統(tǒng)中任務(wù)調(diào)度的效率。接下來的工作是考慮使用機器學(xué)習(xí)方法進行模糊綜合評價，優(yōu)化算法生成工作流的流程，提高算法性能。