面向機器學習任務的調度方法研究

孫景玉 石振國

摘 要：為了提高機器學習任務執行效率并實現資源與任務的最佳匹配，在傳統調度問題理論基礎上對調度概念進行拓展，提出一種新的問題解決方案。該解決方案包括基于任務數據相似性原理，對任務集進行特征屬性提取，構建以調度算法資源準確率較高為評價目標的數學模型。在考慮資源和任務匹配程度的前提下設計一種基于改進的簡化粒子群優化的模糊C均值聚類算法，根據任務聚類結果設計新的基于機器學習任務聚類的任務調度算法。實驗結果表明，構建的數學模型在大多數情況下性能良好，優化的聚類算法調用算法準確率比傳統方法約高0.3～0.8個百分點，能夠有效提高任務調度有效性。

關鍵詞：機器學習;任務調度算法;特征屬性;C均值聚類算法

DOI：10. 11907/rjdk. 192349 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP301文獻標識碼：A 文章編號：1672-7800（2020）005-0009-05

0 引言

近年來，隨著計算機計算能力的不斷提升，機器學習作為人工智能的核心技術之一，在越來越多的領域取得了令人矚目的成果。作為一門涉及概率論、統計學、凸分析等多領域的交叉學科[1-2]，其具有非常廣泛的應用范圍。與此同時，飛速發展的互聯網也迎來了如何對大量閑置資源加以合理利用的巨大挑戰。在相對較低調度成本以及相對較高資源利用率的前提下實現任務的合理高效管理，并對任務進行準確、有效、高質量的調度執行已成為越來越多領域不斷追求的目標。

通常而言，調度問題指在一定約束條件和優化目標函數約束下，將相關任務排列后利用有限資源完成一系列任務的過程。它廣泛存在于現實生活的各行各業，例如人力調度、衛星調度[3]、負載均衡調度[4]等。在生產中就是組織執行生產進度計劃的工作，在車輛運輸中就是在一定約束條件下制定行車路線使車輛有序到達指定地點[5]。

本文在現有理論基礎上對任務調度策略進行研究，對調度概念加以創新拓展，打破以往僅憑借經驗處理機器學習任務并匹配適用資源的局限，將機器學習任務與調度相結合構造一種針對機器學習任務與適用資源之間的調度方法模型。機器學習任務形式多樣，但是追根究底都是對數據的處理與學習。不同的樣本數據即為不同的機器學習任務，如何為提交任務調度適用資源即為本文研究目標所在。本文首先介紹基于任務的數據相似性原理，提取能夠反映數據集內部結構特點的特征屬性，構建以調度算法資源準確率較高為評價目標的數學模型;然后在考慮資源和任務匹配程度的前提下設計一種基于改進簡化粒子群優化的模糊C均值聚類算法，根據任務聚類結果設計新的基于機器學習任務聚類的任務調度算法;最后通過實驗分析驗證該解決方案的可行性。

1 調度算法資源數學模型構建

調度算法資源數學模型構建是機器學習任務在執行過程中的重要步驟。Schaffer[6]提出每個機器學習任務依次調用可供選擇的算法，然后選取準確率較高的算法;Brodley[7]提出以專家知識為基礎的算法選擇方案。本文對樣本數據進行分析，提取能夠反映樣本數據內部結構的特征屬性[8]，從而得到一種衡量新任務與樣本庫中數據集之間關系的度量數學模型。該模型主要由二進制化向量、屬性統計特征向量以及平均互信息量[9]3部分組成。通過與樣本庫中的數據集進行對比，考量該任務與樣本庫中樣本集之間的關系，幫助機器學習任務調用適用算法，在一定程度上優化了任務與資源匹配合理性，能夠有效提高調度算法資源效率。

1.1 屬性向量二值化

二值化算法只能針對離散數據進行處理，因此需對連續數據加以轉換。為了盡可能地保持數據的內在結構，本文采用基于集成學習的無監督離散化算法[10]和Song等[11]提出的離散化方法相結合的方式提取特征向量。該方法利用集成方式將CAIM算法離散化后的結果集成并得到最小子區間，采用保持近鄰特征的方式合并子區間，直到合并過程波動最大時離散化停止。算法離散化的樣本數據在不同維度上的區間可視為不同屬性，將原始樣本數據D轉換到屬性空間，并將屬性值轉換為0和1，構成樣本數據的二值化空間DB。在二進制化過程中，為保證沒有語義信息丟失，需對屬性個數予以擴充，并根據式（1）進行轉換。

其中，[ValueAi]是樣本數據中第i維的屬性，[CAi]為該維度上不同的屬性值。將每個實例屬性或者類標簽按照式（1）進行轉換，然后統計每個屬性值出現的頻率可得一項集，對兩個不同屬性取異或操作得到二項集合向量。二項集求取如式（2）所示。

1.3 平均互信息量

在概率論和信息論中，兩個隨機變量的互信息（Mutual Information，MI）是變量間相互依賴性的量度。Jakulin等[14-16]的研究表明可通過屬性間的交互分析數據集;Pritam等[17-18]也指出統計交互信息有助于深入分析數據集的潛在結構以及屬性之間的關系。不同于相關系數，互信息并不局限于實值隨機變量，它決定著聯合分布p（X，Y）和分解邊緣分布乘積 p（X）p（Y） 的相似程度。兩個離散隨機變量X和Y的互信息定義如式（7）所示。

其中，[d{Vi，Vj}]、[d{Ai，Aj}]、[d{Ii，Ij}]分別為任務樣本數據集的二進制化屬性、統計特征屬性和平均互信息量屬性向量距離，Pa1、Pa2和Pa3分別為各屬性向量距離參數。通過此數學模型，對比任務集與歷史樣本庫中數據集之間的相似性程度以及映射關系，找到最佳適用資源。

2 任務聚類

除通過分析任務集內部特征構建調度算法資源數學模型外，還需考慮任務需求及資源類型多樣，例如CPU、內存等。任務類型有計算型任務、存儲型任務及網絡型任務等。因此，提出對任務端進行聚類分析，設計一種基于改進簡化粒子群優化的模糊C均值聚類算法對任務進行聚類處理，提高任務調度匹配程度。

2.1 簡化粒子群優化算法

PSO算法是1995年由Kennedy & Eberhart首次提出的一種模擬鳥的群體智能優化算法。它首先初始化一群隨機粒子，然后通過不斷迭代找到問題最優解，具有收斂速度快、容易實現、調整參數少等優點。

迭代過程中，粒子速度及位置更新如式（10）所示。

其中，[χid]是粒子當前位置，[Pid]是搜索歷史中最優點位置，[pgd]是整個種群中當前最優解位置，[c]為學習因子，[ω]表示粒子移動快慢程度。雖然目前大多數PSO改進算法都是基于“位置”與“速度”概念，但是粒子移動速度大小并不能有效地趨近最優解位置，反而可能造成粒子進化方向偏離，從而導致后期收斂緩慢、收斂精度低。文獻[19]與文獻[20]證明基本粒子群優化算法在進化過程中與粒子速度無關，簡化粒子群算法結構使得搜索過程僅由位置向量控制，避免了人為確定參數而影響粒子收斂速度和收斂精度。簡化后的粒子群算法更新如式（11）所示。

其中，[Pad]為所有個體最優位置的均值。

2.2 基于改進的簡化粒子群優化模糊C均值聚類算法

FCM算法是基于目標函數的聚類過程，能夠更加真實地反映客觀世界，但也存在對初始值敏感和容易陷入局部最優的缺陷。針對FCM算法缺點，本文提出基于拉普拉斯加權系數[21]和PSO算法的優化搜索能力對此進行改進，通過計算樣本元素與聚類中心的距離獲得權系數，有效提高聚類性能。目標函數改為如式（12）所示。

為了達到自適應效果，從模糊矩陣u中分離出樣本矩陣[C=[cij，0]]，[cij]表示模糊矩陣每列的最小值，矩陣C的映射函數[A=（Ai，icci-Ai）] 。求取兩個簇中心的歐式距離[dij=Ai-Aj]，[lij=i-1nMjk-Aji=1nMik-Ai]，若[dij]、[lij]小于事先給定參數值，則進行合并，隨機生成新的聚類中心，重新進行迭代計算。

在利用PSO算法進行優化求解時，算法中個體確定、編碼以及適應度函數是解決問題的關鍵。選取每個粒子由K個聚類中心組成，維數為[w]。對聚類中心[Mi（i=1，2，？k）]進行編碼，編碼長度可表示為[K×w]。個體適應度函數定義為[f=1（1+Jm）]，其中[Jm]為樣本點到聚類中心的距離和，[Jm]值越小，個體適應度越高，適應度值大小代表了選取此聚類中心后聚類效果好壞。當算法滿足最優解對應的目標值保持不變或者小于設定的閾值[ε]時，算法終止。

綜上所述，改進的簡化粒子群優化模糊C均值聚類算法（ISPO）求解過程如下：

Step1：初始化聚類中心V，并對算法相關參數，如聚類數目c、模糊因子m的值，迭代誤差[ε]等參數賦值。

Step2：按照編碼原則生成初始種群。

Step3：根據適應度函數計算種群個體適應值，計算權重系數S，更新隸屬度矩陣并修正新的聚類中心。

Step4：計算目標函數[JLFCM（U，S，V）]。

Step5：判斷是否滿足終止條件，否則迭代執行過程。

3 基于任務聚類的任務調度算法設計

任務調度算法設計如下：對每一個歷史樣本數據集進行屬性計算，獲得對應調度算法資源的度量值，將兩者對應關系保存到數據庫中;然后依次應用算法庫中的算法，對算法性能進行評估，將評估結果最好的算法列為適用算法并保存到數據庫中，當有新的任務需要執行時，根據精確度、執行時間、CPU占用以及內存使用情況等需求特性，對數據庫中調度算法資源度量值進行排序后調用適用算法;再利用改進的簡化粒子群優化的模糊C均值聚類算法對任務進行聚類處理。任務調度算法步驟如圖1所示。

4 實驗及結果分析

4.1 實驗準備

本文實驗數據采用UCI標準評測數據集，并采用交叉驗證方法進行實驗。算法庫采用最常見的3種任務類型：分類模型算法包括決策樹模型、概率統計模型、懶惰模型等;回歸模型算法包括線性回歸、回歸樹、隨機森林等;聚類模型算法包括基于劃分聚類、基于層次聚類和基于密度聚類等。

4.2 實驗過程與結果分析

4.2.1 樣本數據集特征向量

表2表示選取的部分樣本數據集概要信息。

4.2.2 調度算法資源數學模型評價

針對同一任務可能適用多種不同算法資源的情況，實驗基于K最近鄰算法思想，從數據庫中選出k個與輸入任務數據集最相似的數據集，再根據數據庫中數據集與算法之間的映射關系選出適用算法。k值的不同可能導致最終結果不同，因此設置鄰居個數k為1～9，計算所有測試數據集調用適用算法后的準確率均值并記錄實驗結果。由圖2發現，準確率隨著鄰居個數k的不斷增大先迅速上升后趨于平緩。由此可知，當鄰居個數超過某一界限時，調度算法的準確率變化趨于穩定。因此，為了節約成本，鄰居個數k值選擇圖2中趨于平緩的界值即可。

測試任務集調用算法準確率如圖3所示，包括最佳、最差以及平均推薦準確率。可以看出，測試任務集平均最佳調度準確率約為82.15%，除個別任務數據集調度準確結果不理想外，大部分測試數據集調用準確率均能達到80%及以上。而且，與傳統“Win-Draw-Loss”策略（WDL）相比，該算法平均精度約高出0.3%～0.8%。

4.2.3 改進的簡化粒子群模糊C均值聚類評價

為了測試算法性能，本文利用UCI數據庫中經典Iris和Wine數據集，將改進的簡化粒子群模糊C均值聚類算法IPFCM與傳統FCM算法以及傳統PSO算法優化的模糊聚類算法PFCM進行比較。在實驗中設置粒子群規模為50，聚類數目為3，模糊因子為2，對每種算法做30次實驗并取平均值，結果如表5所示。

從整體角度分析，傳統FCM算法方差較大，容易受初值選取影響，而且目標函數值下降迅速，容易陷入局部最小值，聚類效果較差。PFCM算法采用了優化處理，聚類效果較好，但是可能出現早熟收斂情況。本文改進的IPFCM算法提高了優化搜索能力，避免了人為確定參數而影響粒子收斂速度和收斂精度，從而在準確率方面優于傳統FCM算法和PFCM算法。由圖4和表5實驗結果可以發現，不同搜索過程適應度函數不同，目標函數也會不同。并且，IPFCM算法在精確到一定程度時，搜索速度相對較快，聚類效果更好。

5 結語

本文通過構建調度算法資源數學模型并設計一種基于改進的簡化粒子群優化的模糊C均值聚類算法對任務內部結構特征及任務性能特點進行分析，讓具有不同偏好的任務與具有相應性能特點的資源進行匹配，從而在一定程度上提高任務執行效率。通過調用算法資源數學模型，為提交的任務數據集選擇算法庫中的適用算法。實驗結果表明，大多數情況下該調度算法是有效可行的，改進的聚類算法也能夠在一定程度上彌補FCM算法缺陷，從而有效提高任務調度有效性。

參考文獻：

[1] 陳凱，朱鈺. 機器學習及其相關算法綜述[J]. 統計與信息論壇， 2007， 22（5）：105-112.

[2] TOM M.MITCHELL. 機器學習（計算機科學叢書）[M]. 北京：機械工業出版社，2014.

[3] 陳宇. 基于典型任務的多星協同調度關鍵問題研究[D]. 武漢：武漢大學，2012.

[4] 馬亮，李曉. 基于改進粒子群算法的云計算任務調度策略[J]. 計算機與現代化，2013， 11（9）：78-81.

[5] 李靜梅，王雪，吳艷霞. 一種改進的優先級列表任務調度算法[J]. 計算機科學，2014， 41（5）：20-23.

[6] SCHAFFER C. Selecting a classification method by cross validation[J]. ?Machine Learning， 1993，13（1）：135-143.

[7] BRODLEY C E. Recursive automatic bias selection for classifier construction[J]. Machine Learning，1995，20（1/2）：63-94.

[8] 曾子林，張宏軍，張睿，等. 基于元學習思想的算法選擇問題綜述[J]. 控制與決策，2014（6）：961-968.

[9] 劉娟，朱翔鷗，劉文斌. 基于交互信息的數據集特征結構研究[J]. 模式識別與人工智能，2014， 27（1）：82-88.

[10] 徐盈盈，鐘才明. 基于集成學習的無監督離散化算法[J]. 計算機應用，2014， 34（8）：2184-2187.

[11] SONG Q，WANG G，WANG C. Automatic recommendation of classification algorithms based on data set characteristics[J]. ?Pattern Recognition， 2012，45（7）：2672-2689.

[12] 代明，鐘才明，龐永明，等. 基于數據集屬性相似性的聚類算法推薦[J]. 南京大學學報（自然科學版），2016，52（5）：908-917.

[13] GOMES D，CASTRO L N D. Clustering algorithm selection by meta-learning systems： a new distance-based problem characterization and ranking combination methods[M]. Elsevier Science Inc. ，2015.

[14] YIN Z，LI J，ZHANG Y，et al. Functional brain network analysis of schizophrenic patients with positive and negative syndrome based on mutual information of EEG time series[J]. ?Biomedical Signal Processing and Control，2017（31）：331-338.

[15] JAKULIN A，BRATKO I. Testing the significance of attribute interactions[C]. New York：Proceedings of The 21th International Conference on Machine Learning，2004：52-59.

[16] JAKULIN A，BRATKO I. Analyzing attribute dependencies[C]. The 7th European Conference on Principles and Practice of Knowledge Discovery in Databases（PKDD），2003：229-240.

[17] CHANDA P，CHO Y R，ZHANG A，et al. Mining of attribute interactions using information theoretic metrics[C]. Miami：IEEE International Conference on Data Mining Workshops，2009：350-355.

[18] 賈平，代建華，潘云鶴，等. 一種基于互信息增益率的新屬性約簡算法[J]. 浙江大學學報（工學版），2006，40（6）：1041-1044.

[19] 胡旺，李志蜀. 一種更簡化而高效的粒子群優化算法[J]. 軟件學報，2007，18（4）：861-868.

[20] 熊眾望，羅可. 基于改進的簡化粒子群聚類算法[J]. 計算機應用研究，2014，31（12）：3550-3552.

[21] 黃鵬飛. 拉普拉斯加權聚類算法的研究[D]. 南京：南京航空航天大學，2009.

（責任編輯：孫 娟）