李慧芳 黃姜杭 徐光浩 夏元清

云資源的按使用付費模式以及彈性擴展能力,為大規(guī)模科學(xué)應(yīng)用的分布式管理與高效執(zhí)行提供了快速、靈活、可擴展的部署環(huán)境[1-3].科學(xué)應(yīng)用的分布式管理與高效執(zhí)行的關(guān)鍵在于工作流調(diào)度,而調(diào)度算法的設(shè)計、調(diào)度性能的優(yōu)劣以及調(diào)度方案的可實施性,直接取決于任務(wù)執(zhí)行時間的估計精度[4-5].

在實際云數(shù)據(jù)中心環(huán)境下,大量、頻繁的用戶服務(wù)請求與響應(yīng),使數(shù)據(jù)中心的運行數(shù)據(jù)規(guī)模呈指數(shù)級增長.其中,工作流執(zhí)行日志數(shù)據(jù)包含了大量的任務(wù)執(zhí)行時間歷史及其相關(guān)影響因素數(shù)據(jù),并在數(shù)據(jù)驅(qū)動的任務(wù)執(zhí)行時間預(yù)測中發(fā)揮著重要作用.任務(wù)執(zhí)行時間的影響因素數(shù)據(jù),可根據(jù)其特征劃分為類別型數(shù)據(jù)和數(shù)值型數(shù)據(jù).類別型數(shù)據(jù)與任務(wù)和資源的多樣性、異構(gòu)性相關(guān),其數(shù)值離散且取值范圍廣,如任務(wù)名稱和機器ID 等;數(shù)值型數(shù)據(jù)則與云環(huán)境的動態(tài)特性相關(guān),其數(shù)值連續(xù),且在一定范圍內(nèi)波動,如資源利用率和網(wǎng)絡(luò)帶寬等.在大數(shù)據(jù)環(huán)境下,類別型數(shù)據(jù)的高維稀疏特性會擴大模型的搜索空間,數(shù)值型數(shù)據(jù)的低維稠密特性會降低部分特征之間的差異性,從而加大了模型尋優(yōu)和學(xué)習(xí)的難度,給任務(wù)執(zhí)行時間預(yù)測帶來了巨大挑戰(zhàn)[6].

本文提出了一種基于多維度特征融合(Multidimensional feature fusion,MDFF)的云工作流任務(wù)執(zhí)行時間預(yù)測算法.針對類別型數(shù)據(jù)和數(shù)值型數(shù)據(jù)的特點,設(shè)計不同的特征提取方法,分別提取類別型和數(shù)值型特征.同時,通過將提取的特征和原始數(shù)據(jù)特征進行有選擇地融合,并采用輕量梯度提升機算法對融合特征進行挖掘與利用,實現(xiàn)云工作流任務(wù)執(zhí)行時間的精準(zhǔn)預(yù)測.

本文的主要貢獻如下:

1)構(gòu)建具有注意力機制的堆疊殘差循環(huán)網(wǎng)絡(luò),將類別型數(shù)據(jù)從高維稀疏空間映射到低維稠密空間,通過減小搜索空間,提升模型對類別型數(shù)據(jù)的解析能力,同時增強模型對類別型特征的關(guān)注度,以有效提取類別型特征,提高預(yù)測精度.

2)引入極限梯度提升算法,對數(shù)值型數(shù)據(jù)進行離散化編碼,通過將過于稠密的數(shù)值型數(shù)據(jù)稀疏化,突出特征之間的差異性,避免模型訓(xùn)練陷入局部最優(yōu)的可能,提升模型的非線性信息表達能力,有效提取數(shù)值型特征,改善預(yù)測精度.

3)設(shè)計多維異質(zhì)特征融合策略,將具有注意力機制的堆疊殘差循環(huán)網(wǎng)絡(luò)提取的類別型特征、極限梯度提升(Extreme gradient boosting,XGB)模型提取的數(shù)值型特征與原始樣本數(shù)據(jù)進行選擇性融合,以充分挖掘與利用任務(wù)執(zhí)行時間的多維度特征,學(xué)習(xí)更全面的任務(wù)執(zhí)行時間知識,降低預(yù)測誤差.

1 研究現(xiàn)狀

傳統(tǒng)的云計算任務(wù)執(zhí)行時間估計方法,大多基于微分測量[7]、相似性分析[8-9]以及數(shù)學(xué)表達式[10-11]等統(tǒng)計學(xué)習(xí)算法,忽略了云資源的動態(tài)變化以及云環(huán)境的復(fù)雜特性,難以實現(xiàn)任務(wù)執(zhí)行時間的準(zhǔn)確估計.隨著機器學(xué)習(xí)的不斷發(fā)展,數(shù)據(jù)驅(qū)動的執(zhí)行時間預(yù)測方法被廣泛應(yīng)用于各種云應(yīng)用場景.近年來,研究人員一直在探索如何將各種機器學(xué)習(xí)算法(如傳統(tǒng)機器學(xué)習(xí)、深度學(xué)習(xí)與集成學(xué)習(xí)算法)應(yīng)用于云計算任務(wù)執(zhí)行時間預(yù)測,以從海量、異構(gòu)、復(fù)雜和多維的工作流任務(wù)執(zhí)行數(shù)據(jù)中挖掘出更有效的信息.

基于傳統(tǒng)機器學(xué)習(xí)的云工作流任務(wù)執(zhí)行時間預(yù)測,大多采用多元線性回歸、支持向量回歸等早期機器學(xué)習(xí)算法.Nouri 等[12]和Tahvili 等[13]建立了任務(wù)執(zhí)行時間及其影響因素的多元回歸模型,實現(xiàn)任務(wù)執(zhí)行時間的估計.可是,多元線性回歸模型更適合捕捉線性關(guān)系,難以學(xué)習(xí)工作流任務(wù)執(zhí)行時間及其影響因素之間的非線性關(guān)系.Park 等[14]與鄭婷婷等[15]利用支持向量回歸,進行任務(wù)執(zhí)行時間預(yù)測.但是,支持向量回歸采用二次規(guī)劃計算支持向量,導(dǎo)致很大的內(nèi)存和時間開銷,特別是在大數(shù)據(jù)樣本時,其模型訓(xùn)練時間過長.

深度學(xué)習(xí)具有超強的特征映射能力,能夠從海量數(shù)據(jù)中學(xué)習(xí)并挖掘數(shù)據(jù)之間的非線性關(guān)系,為數(shù)據(jù)驅(qū)動的任務(wù)執(zhí)行時間預(yù)測提供了新思路[16-17].伍章俊等[18]和Nadeem 等[19]采用徑向基函數(shù)(Radial basis function,RBF)神經(jīng)網(wǎng)絡(luò),構(gòu)建了云工作流活動執(zhí)行時間預(yù)測模型.但是,RBF 網(wǎng)絡(luò)是一種單隱含層的前饋網(wǎng)絡(luò),難以有效學(xué)習(xí)序列數(shù)據(jù)驅(qū)動的任務(wù)執(zhí)行時間變化趨勢相關(guān)的知識,不適用于云環(huán)境下的任務(wù)執(zhí)行時間預(yù)測.因此,Rehse 等[20]引入循環(huán)神經(jīng)網(wǎng)絡(luò)(Recurrent neural network,RNN),通過捕捉任務(wù)執(zhí)行時間的變化趨勢來進行任務(wù)運行時間預(yù)測.Zhu 等[21]提出了基于長短時記憶網(wǎng)絡(luò)(Long short-term memory,LSTM)的預(yù)測方法,解決RNN 因梯度爆炸/消失而引起的預(yù)測精度降低問題.Bi 等[22]選擇Savitzky-Golay 濾波器,濾除原始數(shù)據(jù)序列的極值點和噪聲干擾,并利用LSTM 進行任務(wù)執(zhí)行時間預(yù)測.

神經(jīng)網(wǎng)絡(luò)(Neural network,NN)強大的非線性擬合能力和大數(shù)據(jù)學(xué)習(xí)能力,使基于深度學(xué)習(xí)的任務(wù)執(zhí)行時間預(yù)測效果得到了明顯改善,但是,NN固有的層級連接結(jié)構(gòu)和大量神經(jīng)元計算,不僅使優(yōu)化超平面變得十分復(fù)雜,也大大增加了模型尋優(yōu)的難度,從而影響預(yù)測精度.此外,這些研究工作大多基于單一機器學(xué)習(xí)算法,即使特征空間包含非常有效的信息,但是單一模型有限的學(xué)習(xí)能力,很難找到最優(yōu)解,直接影響預(yù)測精度[23].

集成學(xué)習(xí)可以綜合相同/不同模型的學(xué)習(xí)能力,為云計算任務(wù)執(zhí)行時間預(yù)測開辟了新的途徑.一些學(xué)者將多個單一模型有機結(jié)合,通過不同模型的優(yōu)勢互補來增強集成模型的學(xué)習(xí)能力,并減少預(yù)測誤差.鄭顧平等[24]綜合線性、非線性和多項式回歸等擬合技術(shù),搭建了基于參數(shù)變化的云應(yīng)用程序執(zhí)行時間預(yù)估模型.類似地,李帥標(biāo)等[25]將樸素貝葉斯、支持向量回歸和LSTM 有機結(jié)合,通過Stacking策略進行模型融合,提出了一種業(yè)務(wù)過程剩余時間預(yù)測算法.Nadeem 等[26]通過集成局部學(xué)習(xí)和進化計算,實現(xiàn)了對e-Science 工作流執(zhí)行時間的預(yù)測.Hilman 等[27]基于LSTM和K 最近鄰技術(shù),設(shè)計了在線增量學(xué)習(xí)方法,用于工作流任務(wù)運行時間預(yù)測.Gao 等[28]采用基于受限玻爾茲曼機(Restricted Boltzmann machine,RBM)堆疊的深度置信網(wǎng)絡(luò)(Deep belief network,DBN),建立了并發(fā)請求云服務(wù)響應(yīng)時間與虛擬機資源之間的映射模型.Pham等[29]提出了基于隨機森林(Random forest,RF)的兩階段預(yù)測算法,實現(xiàn)對云工作流任務(wù)執(zhí)行時間的估計.實踐證明,在大多數(shù)情況下,集成方法的預(yù)測精度優(yōu)于單一機器學(xué)習(xí)算法.因此,本文利用集成學(xué)習(xí)方法解決大數(shù)據(jù)驅(qū)動的云工作流任務(wù)執(zhí)行時間預(yù)測問題.

集成學(xué)習(xí)在大數(shù)據(jù)驅(qū)動的云計算任務(wù)執(zhí)行時間預(yù)測方面取得了一定效果,但它們大多基于仿真數(shù)據(jù),且仿真環(huán)境難以模擬云環(huán)境下資源的動態(tài)接入、撤離以及網(wǎng)絡(luò)的不穩(wěn)定性.因此,仿真數(shù)據(jù)給出的離散型或者連續(xù)型任務(wù)執(zhí)行時間的影響因素數(shù)據(jù),其取值都在一定范圍內(nèi),使得類別型數(shù)據(jù)和數(shù)值型數(shù)據(jù)難以區(qū)分.也就是說,仿真數(shù)據(jù)與實際云數(shù)據(jù)中心環(huán)境下的工作流執(zhí)行日志數(shù)據(jù)存在很大差異.然而,現(xiàn)有采用仿真數(shù)據(jù)的集成學(xué)習(xí)方法往往忽略了這種差異性,在對類別型和數(shù)值型數(shù)據(jù)進行相似處理的基礎(chǔ)上,進行云計算任務(wù)執(zhí)行時間預(yù)測.現(xiàn)有的集成學(xué)習(xí)方法存在以下問題:1)對類別型數(shù)據(jù)的解析能力不足,即類別型數(shù)據(jù)的高維稀疏特性使搜索空間過大,模型很難找到最優(yōu)解,從而影響預(yù)測精度;2)缺乏足夠的非線性表達能力,且模型學(xué)習(xí)困難、易于陷入局部最優(yōu),難以應(yīng)對數(shù)值型數(shù)據(jù)的低維稠密特性所帶來的特征差異性降低問題,影響預(yù)測效果;3)直接對提取到的特征進行學(xué)習(xí),導(dǎo)致學(xué)習(xí)效率低甚至學(xué)到無效或錯誤信息,影響預(yù)測結(jié)果的準(zhǔn)確性.

2 相關(guān)理論基礎(chǔ)

本節(jié)介紹本文算法涉及的主要理論基礎(chǔ),即XGB算法[30]和輕量梯度提升機(Light gradient boosting machine,LGBM)算法[31].

2.1 極限梯度提升算法

作為梯度提升機(Gradient boosting machine,GBM)的一種高效實現(xiàn),XGB 利用梯度提升技術(shù),通過迭代生成殘差下降的決策樹(即基學(xué)習(xí)器),將低精度的基學(xué)習(xí)器組合成一個較高精度的強學(xué)習(xí)器,并利用正則化和二階泰勒展開防止過擬合,提高了模型的泛化能力.因此,XGB 模型能獲得較好且不同的特征表達,適合處理取值范圍固定、數(shù)值連續(xù)的數(shù)值型數(shù)據(jù).

數(shù)據(jù)集D={(Xi,Yi)}含有n個樣本和m個特征,其中Xi為第i個樣本的輸入向量,Yi為Xi對應(yīng)的輸出,Yi∈R,i=1,2,···,n.假設(shè)XGB 模型由K棵樹集成,其預(yù)測函數(shù)如下:

式中,l為可導(dǎo)凸函數(shù),表示預(yù)測值和真實值Yi的差異. Ω (·) 是正則化懲罰項,用以避免樹的結(jié)構(gòu)過于復(fù)雜、平滑學(xué)習(xí)權(quán)重并緩解過擬合.

在XGB 模型迭代添加樹的過程中,第t次的目標(biāo)函數(shù)可表示為:

2.2 輕量梯度提升機

LGBM 基于單邊梯度采樣(Gradient-based one-side sampling,GOSS)和互斥特征捆綁技術(shù)(Exclusive feature bundling,EFB),能夠在不損失預(yù)測精度的情況下加速梯度提升過程,提高模型訓(xùn)練效率.因此,相比于XGB 模型,LGBM 模型易于擴展、訓(xùn)練效率高,更適合處理特征維度高、數(shù)據(jù)量大的數(shù)據(jù),滿足云工作流任務(wù)執(zhí)行時間預(yù)測問題的需求.

作為一種在保證精度的前提下能減少數(shù)據(jù)量的算法,GOSS 在決策樹迭代生成過程中根據(jù)梯度絕對值對數(shù)據(jù)進行排序,選取前a% 個樣本,并在剩余的樣本數(shù)據(jù)中隨機采樣b個樣本.在計算信息增益時,通過對采樣的小梯度數(shù)據(jù)乘以系數(shù)(1-a)/b,來緩解甚至消除數(shù)據(jù)分布的影響,使算法更加關(guān)注訓(xùn)練不足的實例.在分割點d分割特征j的信息增益的計算如式(7)所示:

式中,I、(d)和(d) 分別為葉子節(jié)點d及其左右兩個子節(jié)點上的樣本個數(shù);Al和Ar分別為d的左、右兩個子節(jié)點上的大梯度樣本集合;Bl和Br分別為d的左、右兩個子節(jié)點上的小梯度樣本集合;?i為第i個樣本Xi的梯度.

通過將互斥的特征綁定為單一特征,EFB 從捆綁的特征中構(gòu)建直方圖,達到了在不損失精度的情況進行特征降維的目的.首先,EFB 計算并判斷特征之間的互斥程度,若兩個特征之間的互斥程度之和小于設(shè)定的閾值,則綁定它們的特征,減少參與訓(xùn)練的特征數(shù),提高模型訓(xùn)練效率.其中,兩個特征是否互斥及其互斥程度,可按式(8)和式(9)進行判斷:

式中,和分別為樣本i的第u和第v個特征的數(shù)值,E為判斷兩個特征互斥程度的閾值.

3 基于多維度特征融合的云工作流任務(wù)執(zhí)行時間預(yù)測

現(xiàn)有的任務(wù)執(zhí)行時間預(yù)測算法缺乏有效的非線性表達能力和高維稀疏數(shù)據(jù)解析能力,導(dǎo)致任務(wù)執(zhí)行時間預(yù)測精度低,難以滿足大數(shù)據(jù)環(huán)境下的云工作流任務(wù)執(zhí)行時間預(yù)測要求.為此,本文提出了一種基于多維度特征融合的云工作流任務(wù)執(zhí)行時間預(yù)測算法.首先,針對類別型數(shù)據(jù)xCa和數(shù)值型數(shù)據(jù)xNu,設(shè)計異質(zhì)特征提取器,實現(xiàn)對類別型特征和數(shù)值型特征的有效提取.其次,有選擇地融合原始數(shù)據(jù)特征和提取到的特征,為預(yù)測模型提供更全面、更深層的融合知識.最后,基于融合特征數(shù)據(jù)構(gòu)建預(yù)測模型,實現(xiàn)對云工作流任務(wù)執(zhí)行時間的精準(zhǔn)預(yù)測.本文基于多維度特征融合的云工作流任務(wù)執(zhí)行時間預(yù)測模型如圖1 所示,主要包括特征提取、特征融合和預(yù)測3 個部分.

圖1 基于多維度特征融合的云工作流任務(wù)執(zhí)行時間預(yù)測模型Fig.1 The multi-dimensional feature fusion-based runtime prediction model for cloud workflow tasks

3.1 基于SARR 的類別型特征提取

基于神經(jīng)網(wǎng)絡(luò)的預(yù)測任務(wù),通常包括特征提取和預(yù)測兩個步驟.為充分挖掘類別型數(shù)據(jù)相關(guān)的知識,本文MDFF 算法采用具有注意力機制的堆疊殘差循環(huán)網(wǎng)絡(luò)(Stacked attention residual recurrent neural network,SARR)提取類別型特征.在RNN 網(wǎng)絡(luò)的基礎(chǔ)上,通過引入注意力機制和添加殘差連接,構(gòu)建堆疊殘差循環(huán)網(wǎng)絡(luò),設(shè)計基于SARR的類別型特征提取器.

SARR 包括Embedding 模塊、門控循環(huán)單元(Gate recurrent unit,GRU)模塊和LSTM 模塊三個部分,如圖2 所示.圖2 中,Embedding 模塊包含基于RNN 的Embedding 單元;GRU 模塊包括GRU 單元、Attention 單元以及殘差連接;LSTM模塊包含LSTM 單元、Attention 單元以及殘差連接.

圖2 基于SARR 的類別型特征提取器Fig.2 The SARR-based Categorical feature extractor

SARR 在不增加網(wǎng)絡(luò)層數(shù)的情況下,解決了梯度消失可能引起的網(wǎng)絡(luò)退化問題,能夠提取與任務(wù)執(zhí)行時間顯著相關(guān)的特征,并通過為最終的預(yù)測器提供更有效的特征,改善預(yù)測精度.

3.2 基于XGB 的數(shù)值型特征提取

基于梯度提升機的預(yù)測方法,通常包括特征提取和預(yù)測兩個步驟.為充分挖掘數(shù)值型數(shù)據(jù)相關(guān)的知識,本文設(shè)計了基于XGB 的數(shù)值型特征提取器,如圖3 所示.其中,從每一個XGB 基學(xué)習(xí)器的根節(jié)點到葉子節(jié)點所進行的運算為特征提取過程,從所有基學(xué)習(xí)器的葉子節(jié)點到輸出節(jié)點的計算屬于預(yù)測過程.

圖3 基于XGB 的數(shù)值型特征提取器Fig.3 The XGB-based Numerical feature extractor

然后,通過樹的結(jié)構(gòu)函數(shù)q(·) 尋找每個數(shù)值型向量在每棵樹的每個分支最深一層中所屬葉子的下標(biāo),并標(biāo)記為1,對每個數(shù)值型向量進行離散化編碼.結(jié)構(gòu)函數(shù)q(·) 如式(14)所示:

式中,Tk為第k棵樹的葉子節(jié)點數(shù)量.利用XGB對數(shù)值型向量進行離散化編碼后獲得的新向量,即為數(shù)值型特征向量

3.3 多維異質(zhì)特征融合

在提取的類別型特征和數(shù)值型特征基礎(chǔ)上,本文進一步提出了多維異質(zhì)特征融合策略,旨在同時收集低維和高維特征信息之間的交互信息,使預(yù)測模型學(xué)習(xí)到更全面且有效的任務(wù)執(zhí)行時間知識,降低預(yù)測誤差.

本文提出的多維異質(zhì)特征融合策略,包含特征拼接、特征重要性計算、特征排序和篩選幾個步驟.首先,將SARR 與XGB 模型提取到的特征向量與原始輸入向量進行拼接,得到一個式(15)所示的新輸入向量xfu1,且xfu1∈R1×(NCa+NNu+NSARR+NXGB):

然后,利用xfu1訓(xùn)練LGBM 模型,用于計算不同特征的重要性,并按重要性對特征進行排序:

式中,xi為拼接向量xfu1中的第i維特征,fimp(·)為特征重要性計算與排序函數(shù),Nsplit(xi) 為整個特征重要性排序模型生成過程中xi被選取為分裂節(jié)點的次數(shù).最后,從排序表中篩選出更具判別力的特征,構(gòu)成用于任務(wù)執(zhí)行時間預(yù)測的多維度融合輸入特征向量

式中,threshold為特征篩選閾值,且xi被選為分裂點的次數(shù)越多,說明xi對預(yù)測結(jié)果的貢獻越大.

3.4 云工作流任務(wù)執(zhí)行時間預(yù)測

在獲得多維異質(zhì)融合特征的基礎(chǔ)上,本文采用LGBM 模型對多維異質(zhì)特征進行充分挖掘與利用,以精準(zhǔn)地預(yù)測任務(wù)執(zhí)行時間,為大數(shù)據(jù)環(huán)境下的云工作流調(diào)度提供決策支持.

本文基于多維度特征融合的云工作流任務(wù)執(zhí)行時間預(yù)測方法,包括3 個部分:1)針對類別型數(shù)據(jù)和數(shù)值型數(shù)據(jù),設(shè)計不同的特征提取方法,分別提取類別型和數(shù)值型特征;2)將提取到的特征數(shù)據(jù)與原始數(shù)據(jù)進行選擇性融合,為預(yù)測模型提供更全面的特征輸入;3)構(gòu)建基于融合特征的預(yù)測模型,獲得云工作流任務(wù)執(zhí)行時間預(yù)測結(jié)果.整體流程如下:

步驟1.輸入云工作流任務(wù)執(zhí)行時間數(shù)據(jù)集D={(Xi,Yi)},其中,Xi為第i個樣本的任務(wù)執(zhí)行時間影響因素向量;Yi為第i個樣本的任務(wù)執(zhí)行時間.

步驟2.將一個輸入數(shù)據(jù)向量Xi劃分為類別型數(shù)據(jù)向量xCa和數(shù)值型數(shù)據(jù)向量xNu,即Xi={xCa,xNu}.

步驟3.利用類別型數(shù)據(jù)向量xCa,訓(xùn)練SARR模型,不斷調(diào)整參數(shù),直至獲得誤差最小的SARR 模型.

步驟4.對訓(xùn)練好的SARR 模型,去掉其輸出層以及輸出層的所有連接參數(shù),得到類別型特征提取器,并對xCa進行特征提取,獲得類別型特征向量.

步驟5.利用數(shù)值型數(shù)據(jù)向量xNu,訓(xùn)練XGB模型,并對xNu進行特征提取,獲得初始數(shù)值型特征向量

步驟6.利用類別型特征向量和初始數(shù)值型特征向量訓(xùn)練LGBM 評判模型.

步驟7.調(diào)整XGB 模型參數(shù),重復(fù)步驟5～6,直至LGBM 評判模型的誤差穩(wěn)定在一定范圍內(nèi),且波動不超過5%;挑選出使LGBM 評判模型誤差最小的XGB 模型參數(shù),并基于該組參數(shù)訓(xùn)練XGB模型.

步驟8.對訓(xùn)練好的XGB 模型,去掉其輸出層以及輸出層的所有連接參數(shù),獲得數(shù)值型特征提取器,并對xNu進行特征提取,獲得最終數(shù)值型特征向量

步驟9.構(gòu)建多維異質(zhì)特征融合器,將類別型數(shù)據(jù)向量xCa、數(shù)值型數(shù)據(jù)向量xNu、類別型特征向量和數(shù)值型特征向量進行融合,獲得融合后的特征向量

步驟10.基于融合特征向量利用網(wǎng)格尋優(yōu)算法訓(xùn)練LGBM 預(yù)測模型,直至獲得誤差最小的LGBM 模型,并將其作為預(yù)測器.

步驟11.取出類別型特征提取器、數(shù)值型特征提取器、多維異質(zhì)特征融合器和預(yù)測器,構(gòu)建基于多維度特征融合的云工作流任務(wù)執(zhí)行時間預(yù)測模型.

步驟12.輸出云工作流任務(wù)執(zhí)行時間預(yù)測模型.

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

為了驗證所提出的基于多維度特征融合的云工作流任務(wù)執(zhí)行時間預(yù)測模型的有效性,本文選擇2018 年阿里巴巴集群數(shù)據(jù)集行進行仿真實驗,通過在不同指標(biāo)下與6 種基線預(yù)測方法進行對比說明本文方法的優(yōu)越性.

4.1 實驗配置

4.1.1 數(shù)據(jù)集

本文實驗數(shù)據(jù)來源于阿里巴巴2018 年集群運行日志數(shù)據(jù)集Cluster-trace-v2018[32].Cluster-tracev2018 記錄了阿里巴巴某個生產(chǎn)集群中約4 000 臺服務(wù)器8 天的運行詳細(xì)日志,具體可查閱https://github.com/alibaba/clusterdata/blob/master/Clu ster-trace-v2018.

在進行云工作流任務(wù)執(zhí)行時間預(yù)測前,本文對Cluster-trace-v2018 數(shù)據(jù)集進行了預(yù)處理.首先,分析Cluster-trace-v2018 數(shù)據(jù)集,尋找任務(wù)執(zhí)行時間相關(guān)的關(guān)鍵屬性,并根據(jù)這些關(guān)鍵屬性匹配不同數(shù)據(jù)表中的數(shù)據(jù),獲得包含任務(wù)執(zhí)行時間和相關(guān)影響因素的數(shù)據(jù)集.其次,對該數(shù)據(jù)集存在的異常值和缺失值進行處理,獲得包含22 155 組云工作流任務(wù)的執(zhí)行時間及其對應(yīng)的所有影響因素數(shù)據(jù),即最終可用于檢驗算法的云工作流任務(wù)執(zhí)行時間數(shù)據(jù)集.最后,在獲取的數(shù)據(jù)集上隨機抽取17 724 組數(shù)據(jù)構(gòu)成訓(xùn)練集,將剩余的4 431 組數(shù)據(jù)作為測試集.

4.1.2 對比算法

為了驗證MDFF 的有效性和優(yōu)越性,本文選取了六種對比算法,包括深度興趣網(wǎng)絡(luò)(Deep interest network,DIN)[33]、深度交叉網(wǎng)絡(luò)(Deep &cross network,DCN)[34]、深度因子分解機(Deep factorization machine,DeepFM)[35]、寬度與深度模型(Wide &Deep,W&D)[36]、兩階段預(yù)測方法(Two stage approach,TSA)[37]和梯度提升樹與線性回歸的結(jié)合方法(Gradient boosting decision tree+linear regression,GBDT+LR)[38].其中,DIN和DCN 側(cè)重于類別型數(shù)據(jù)的處理,其數(shù)值型特征提取能力弱;TSA 以及GBDT+LR 偏向于數(shù)值型數(shù)據(jù)的處理,類別型特征的提取能力弱;Deep-FM和W&D 能同時提取類別型特征和數(shù)值型特征.所有方法采用的參數(shù)組合均為使預(yù)測效果最好的參數(shù)組合,其具體模型結(jié)構(gòu)或參數(shù)設(shè)置如下:

在DIN 中,嵌入單元1和2 的維度分別為82和80,Dense 單元的神經(jīng)元個數(shù)為16,隱含神經(jīng)元個數(shù)為32,激活函數(shù)為Relu,輸出層神經(jīng)元個數(shù)為1,激活函數(shù)為Relu;最大迭代次數(shù)為500,批量大小為100,優(yōu)化器為Adam.

DCN 的嵌入維度為8,網(wǎng)絡(luò)的隨機失活(Dropout)比例均為0.5,隱含層的神經(jīng)元個數(shù)為64-64,領(lǐng)域維度設(shè)為原始特征維度,交叉寬度設(shè)為領(lǐng)域維度與嵌入維度的乘積;最大迭代次數(shù)為450,批量大小為100,批量標(biāo)準(zhǔn)化因子為1,批量標(biāo)準(zhǔn)化衰減因子為0.95,學(xué)習(xí)率為0.01,L2正則化系數(shù)為0.01,優(yōu)化器為Adam.

DeepFM 的嵌入維度為80,其因子分解機和網(wǎng)絡(luò)的隨機失活(Dropout)比例分別為1和0.5,網(wǎng)絡(luò)部分的神經(jīng)元個數(shù)為32-32,激活函數(shù)為Relu;最大迭代次數(shù)為500,批量大小為100,批量標(biāo)準(zhǔn)化因子為1,批量標(biāo)準(zhǔn)化衰減因子為0.995,學(xué)習(xí)率為0.01,L2正則化系數(shù)為0.01,優(yōu)化器為Adam.

在W&D 中,Wide 部分采用線性回歸方法,并選用默認(rèn)參數(shù).Deep 部分采用含兩個隱含層的神經(jīng)網(wǎng)絡(luò),其結(jié)構(gòu)為325-100-50-1,網(wǎng)絡(luò)部分神經(jīng)元個數(shù)為32-32,激活函數(shù)為Relu.最大迭代次數(shù)為500,批量大小為100,優(yōu)化器為Adam.

在TSA 中,第1 階段預(yù)測采用隨機森林,基學(xué)習(xí)器數(shù)量為200,最大樹深度為7;第2 階段采用線性回歸,且選用默認(rèn)參數(shù).

在GBDT+LR 中,GBDT 部分的基學(xué)習(xí)器數(shù)量為150,LR 部分采用線性回歸,且選取默認(rèn)參數(shù).

在MDFF 中,類別型特征提取模型SARR 的嵌入單元1和2 的維度分別為82和80,Dense 單元神經(jīng)元個數(shù)為16,GRU 單元和LSTM 單元的神經(jīng)元個數(shù)均為32,最大迭代次數(shù)為400,批量大小為100,隨機失活(Dropout)比例為0.15,激活函數(shù)為Relu,優(yōu)化器為Adam.數(shù)值型特征提取模型XGB 的基學(xué)習(xí)器數(shù)量為30,學(xué)習(xí)率為0.15,最大樹深度為8,列采樣比例為0.4.任務(wù)執(zhí)行時間預(yù)測模型LGBM 的學(xué)習(xí)率為0.15,基學(xué)習(xí)器數(shù)量為1 000,最大樹深度為9,最多葉子結(jié)點個數(shù)為31,列采樣比例為0.4.

4.1.3 評價指標(biāo)

為了檢驗本文MDFF 算法的預(yù)測精度,本文選取了平均絕對誤差(Mean absolute error,MAE)、均方根誤差(Root mean square error,RMSE)、均方根對數(shù)誤差(Root mean square log error,RMSLE)和決定系數(shù)(R square,R2)四種評價指標(biāo)[39-40],并在這些評價指標(biāo)的基礎(chǔ)上,設(shè)計了預(yù)測精度差值δ和預(yù)測精度改善比例η兩個指標(biāo),分別用于反映MDFF 算法的預(yù)測精度提升的數(shù)值大小以及提升程度.

1) MAE 表示目標(biāo)真實值和預(yù)測值之差的平均絕對值,用于度量兩個變量之間的差異.MAE具有較強的可解釋性和魯棒性,且MAE的值越小,說明預(yù)測模型的性能越好.MAE的具體計算如式(18)所示:

式中,n為樣本數(shù)量,分別為第i個樣本的真實值和預(yù)測值.

2) RMSE 表示目標(biāo)真實值和預(yù)測值的樣本標(biāo)準(zhǔn)差,用于度量模型的預(yù)測誤差大小.RMSE 與數(shù)值范圍緊密相關(guān),相對于MAE 來說,RMSE 對數(shù)值預(yù)測的錯誤更加敏感,但魯棒性較弱.RMSE 的值越小,說明預(yù)測模型的性能越好.計算公式如下:

3) RMSLE.鑒于RMSE 容易被數(shù)值較大的樣本所主導(dǎo),RMSLE 在RMSE 的基礎(chǔ)上增加了取對數(shù)操作,以便在保持RMSE 敏感性的基礎(chǔ)上,對模型進行公平地評價.RMSLE 的值越小,說明預(yù)測模型的性能越好.計算公式如下:

4) R2 通過數(shù)據(jù)的變化來表征一個預(yù)測算法的擬合程度.R2 的值越大,說明預(yù)測模型的性能越好.計算公式如下:

5)預(yù)測精度差值δ用于表示本文MDFF 算法預(yù)測精度提升的數(shù)值大小.計算公式如下:

6)預(yù)測精度提升比例η表示MDFF 算法的預(yù)測精度改善程度.計算公式如下:

4.2 實驗結(jié)果分析

為了避免隨機性,本文采用10 次實驗結(jié)果的平均值進行性能比較.針對不同的評價指標(biāo),分別計算所有方法的MAE、RMSE、RMSLE和R2 值,如圖4～7 所示.由圖4～圖6 可知,本文MDFF 算法的MAE、RMSE、RMSLE 值達到了最小,說明其預(yù)測結(jié)果的平均絕對誤差和均方根誤差更小,且對大數(shù)值樣本的偏向性最小.由圖7 可知,MDFF 的R2 值最大,說明該算法的擬合程度最好.

圖4 不同方法的MAEFig.4 MAE comparisons among different methods

圖5 不同方法的RMSEFig.5 RMSE comparisons among different methods

圖6 不同方法的RMSLEFig.6 RMSLE comparisons among different methods

圖7 不同方法的R2Fig.7 R2 comparisons among different methods

由圖4～7 結(jié)果,可以得出以下結(jié)論:

1)由于DIN、DCN、TSA和GBDT+LR 要么側(cè)重提取類別型特征,要么側(cè)重提取數(shù)值型特征,而忽略另外一類特征,使模型很難獲得全面的特征知識.因此,其模型對特征的非線性表達能力和解析能力不足.在本文提出的MDFF 算法中,針對類別型數(shù)據(jù)和數(shù)值型數(shù)據(jù)的特點,分別設(shè)計不同的特征提取器,有效地從原始數(shù)據(jù)中提取類別型特征和數(shù)值型特征,挖掘更全面的任務(wù)執(zhí)行時間知識,提高了工作流任務(wù)執(zhí)行時間的預(yù)測精度.在上述四類評價指標(biāo)下,MDFF 算法的預(yù)測性能均優(yōu)于四類對比算法,即DIN、DCN、TSA和GBDT+LR.

值得注意的是,注意力機制的引入,使得DIN的RMSE和R2 僅次于MDFF,預(yù)測誤差波動相對較小且獲得了較好的擬合效果.這也說明了本文采用具有注意力機制的SARR 模型,在提取類別型特征方面的有效性.由于梯度提升算法對數(shù)值型數(shù)據(jù)進行了離散化編碼,所以GBDT+LR 的RMSE和R2 值僅次于DIN,且預(yù)測誤差較小,達到了較好的擬合效果,這說明本文設(shè)計的基于XGB 的特征提取算法,能夠有效地提取數(shù)值型特征.

2)雖然DeepFM和W&D 算法能同時提取類別型特征和數(shù)值型特征,但是與本文MDFF 算法相比,其預(yù)測結(jié)果相對較差.主要原因如下:a)本文提出的MDFF 算法,通過具有堆疊循環(huán)網(wǎng)絡(luò)結(jié)構(gòu)、注意力機制和殘差連接的SARR 模型,將類別型數(shù)據(jù)從高維稀疏的特征空間映射到低維稠密的特征空間,提高了模型對類別型特征的關(guān)注度.因此,與DeepFM和W&D 采用DNN 進行類別型特征提取相比,MDFF 算法能夠更有效地提取類別型特征;b) DeepFM和W&D 分別采用因子分解機和線性回歸模型提取數(shù)值型特征,而本文MDFF 算法利用XGB 對數(shù)值型數(shù)據(jù)進行離散化編碼,通過對過于稠密的輸入向量空間進行稀疏化處理,提高了特征之間的差異性,從而能更有效地提取數(shù)值型特征.此外,通過異質(zhì)多維度特征融合策略,本文MDFF 算法能夠有效避免因直接使用類別型特征和數(shù)值型特征而引入冗余信息或者噪聲的可能性.總的來說,SARR和XGB 的使用,使得MDFF具有更強的提取類別型和數(shù)值型特征的能力,結(jié)合多維異質(zhì)特征融合策略,MDFF 不僅能夠提取有效的深層特征,還能學(xué)習(xí)更全面的任務(wù)執(zhí)行時間知識,使預(yù)測性能得到了明顯改善.

為了進一步說明本文提出的MDFF 算法與對比算法在不同指標(biāo)上的精度提升程度,表1和表2給出了MDFF 與其他對比算法在四種性能指標(biāo)下的差值和性能提升比例.

由表1和表2 可以看出,不同算法在不同性能指標(biāo)下具有不同的性能表現(xiàn),且MDFF 與對比算法的性能差值以及MDFF 算法的性能提升比例也不相同,但相對來說,本文提出的MDFF 算法在不同性能指標(biāo)下的表現(xiàn)更優(yōu).這也說明了MDFF 具有更強的類別型和數(shù)值型特征提取能力,同時對特征進行重要性排序并有選擇性地融合,大大提高了預(yù)測性能.

表1 預(yù)測精度的差值Table 1 The difference of prediction performance

表2 預(yù)測精度提升的比例(%)Table 2 The proportion of performance improvement (%)

在上述性能指標(biāo)的對比中,本文提出的MDFF 算法都能取得良好的性能表現(xiàn),即MDFF 算法具有較強的異質(zhì)特征提取與融合能力,獲得了更高的預(yù)測精度.與各類對比算法相比,MDFF 算法主要有以下3 個方面的優(yōu)勢:1) MDFF 算法采用SARR提取類別型特征,將類別型數(shù)據(jù)從高維稀疏的特征空間映射到低維稠密的特征空間,避免了搜索空間過大的問題,提高了模型對類別型特征的關(guān)注度.因此,相對于普通DNN 網(wǎng)絡(luò),MDFF 算法能更有效地、更具針對性地提取類別型特征;2) MDFF 采用XGB 提取數(shù)值型特征,即借助于XGB 對數(shù)值型數(shù)據(jù)進行離散化編碼,并對過于稠密的輸入向量空間進行稀疏化處理,提高了特征之間的差異性,實現(xiàn)了數(shù)值型特征的有效提取;3) MDFF 采取多維異質(zhì)特征融合策略,對SARR和XGB 提取到的特征進行有選擇性地融合,以充分挖掘與利用多維度特征,為任務(wù)執(zhí)行時間的預(yù)測提供更全面有效的知識,改善了預(yù)測性能.由此可見,通過類別型特征和數(shù)值型特征的有效提取與融合,MDFF 算法的預(yù)測精度得到了明顯提升.

綜上所述,本文提出的基于多維度特征融合的預(yù)測算法預(yù)測平均誤差、預(yù)測誤差波動和預(yù)測偏向性更小,不僅對類別型特征和數(shù)值型特征有較強的解析和表達能力,而且能夠?qū)Ξ愘|(zhì)特征進行充分地挖掘與利用,實現(xiàn)了對云工作流任務(wù)執(zhí)行時間的精準(zhǔn)預(yù)測,可以滿足大數(shù)據(jù)環(huán)境下的云工作流任務(wù)執(zhí)行時間估計需求.

5 結(jié)束語

云計算中的工作流調(diào)度和資源配置依賴于任務(wù)執(zhí)行時間的準(zhǔn)確估計.本文針對工作流任務(wù)執(zhí)行時間預(yù)測問題,提出了一種基于多維度特征融合的預(yù)測方法.首先,構(gòu)建具有注意力機制的堆疊殘差循環(huán)網(wǎng)絡(luò),對類別型數(shù)據(jù)進行特征提取,增強了模型對類別型數(shù)據(jù)的解析能力.其次,引入XGB 對數(shù)值型數(shù)據(jù)進行離散化編碼,提取數(shù)值型特征,提高了模型的非線性表達能力.然后,融合提取到的特征和原始樣本特征,獲得多維異質(zhì)特征,給預(yù)測模型提供了更全面的任務(wù)執(zhí)行時間知識.最后,利用LGBM 對多維異質(zhì)特征進行充分挖掘,構(gòu)建預(yù)測模型,實現(xiàn)對云工作流任務(wù)執(zhí)行時間的精準(zhǔn)預(yù)測,并采用阿里巴巴的集群數(shù)據(jù)集進行了實驗驗證.實驗結(jié)果表明,該方法優(yōu)于現(xiàn)有的基線預(yù)測算法,在MAE、RMSE、RMSLE 以及R2 四種評價指標(biāo)下,均達到了更好的性能.因此,本文所提出的基于多維度特征融合的預(yù)測方法,能夠滿足大數(shù)據(jù)環(huán)境下云工作流任務(wù)執(zhí)行時間預(yù)測的需求.然而,本文僅在集群數(shù)據(jù)集上進行了預(yù)測模型的搭建,如何將預(yù)測模型部署到實際云數(shù)據(jù)中心,實現(xiàn)工作流任務(wù)執(zhí)行時間的在線預(yù)測,仍需進一步探索研究.