孫景玉 石振國

摘 要：為了提高機(jī)器學(xué)習(xí)任務(wù)執(zhí)行效率并實(shí)現(xiàn)資源與任務(wù)的最佳匹配，在傳統(tǒng)調(diào)度問題理論基礎(chǔ)上對調(diào)度概念進(jìn)行拓展，提出一種新的問題解決方案。該解決方案包括基于任務(wù)數(shù)據(jù)相似性原理，對任務(wù)集進(jìn)行特征屬性提取，構(gòu)建以調(diào)度算法資源準(zhǔn)確率較高為評價(jià)目標(biāo)的數(shù)學(xué)模型。在考慮資源和任務(wù)匹配程度的前提下設(shè)計(jì)一種基于改進(jìn)的簡化粒子群優(yōu)化的模糊C均值聚類算法，根據(jù)任務(wù)聚類結(jié)果設(shè)計(jì)新的基于機(jī)器學(xué)習(xí)任務(wù)聚類的任務(wù)調(diào)度算法。實(shí)驗(yàn)結(jié)果表明，構(gòu)建的數(shù)學(xué)模型在大多數(shù)情況下性能良好，優(yōu)化的聚類算法調(diào)用算法準(zhǔn)確率比傳統(tǒng)方法約高0.3～0.8個(gè)百分點(diǎn)，能夠有效提高任務(wù)調(diào)度有效性。

關(guān)鍵詞：機(jī)器學(xué)習(xí);任務(wù)調(diào)度算法;特征屬性;C均值聚類算法

DOI：10. 11907/rjdk. 192349 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP301文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2020）005-0009-05

0 引言

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

通常而言，調(diào)度問題指在一定約束條件和優(yōu)化目標(biāo)函數(shù)約束下，將相關(guān)任務(wù)排列后利用有限資源完成一系列任務(wù)的過程。它廣泛存在于現(xiàn)實(shí)生活的各行各業(yè)，例如人力調(diào)度、衛(wèi)星調(diào)度[3]、負(fù)載均衡調(diào)度[4]等。在生產(chǎn)中就是組織執(zhí)行生產(chǎn)進(jìn)度計(jì)劃的工作，在車輛運(yùn)輸中就是在一定約束條件下制定行車路線使車輛有序到達(dá)指定地點(diǎn)[5]。

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

1 調(diào)度算法資源數(shù)學(xué)模型構(gòu)建

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

1.1 屬性向量二值化

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

其中，[ValueAi]是樣本數(shù)據(jù)中第i維的屬性，[CAi]為該維度上不同的屬性值。將每個(gè)實(shí)例屬性或者類標(biāo)簽按照式（1）進(jìn)行轉(zhuǎn)換，然后統(tǒng)計(jì)每個(gè)屬性值出現(xiàn)的頻率可得一項(xiàng)集，對兩個(gè)不同屬性取異或操作得到二項(xiàng)集合向量。二項(xiàng)集求取如式（2）所示。

1.3 平均互信息量

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

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

2 任務(wù)聚類

除通過分析任務(wù)集內(nèi)部特征構(gòu)建調(diào)度算法資源數(shù)學(xué)模型外，還需考慮任務(wù)需求及資源類型多樣，例如CPU、內(nèi)存等。任務(wù)類型有計(jì)算型任務(wù)、存儲型任務(wù)及網(wǎng)絡(luò)型任務(wù)等。因此，提出對任務(wù)端進(jìn)行聚類分析，設(shè)計(jì)一種基于改進(jìn)簡化粒子群優(yōu)化的模糊C均值聚類算法對任務(wù)進(jìn)行聚類處理，提高任務(wù)調(diào)度匹配程度。

2.1 簡化粒子群優(yōu)化算法

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

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

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

其中，[Pad]為所有個(gè)體最優(yōu)位置的均值。

2.2 基于改進(jìn)的簡化粒子群優(yōu)化模糊C均值聚類算法

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

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

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

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

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

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

Step3：根據(jù)適應(yīng)度函數(shù)計(jì)算種群個(gè)體適應(yīng)值，計(jì)算權(quán)重系數(shù)S，更新隸屬度矩陣并修正新的聚類中心。

Step4：計(jì)算目標(biāo)函數(shù)[JLFCM（U，S，V）]。

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

3 基于任務(wù)聚類的任務(wù)調(diào)度算法設(shè)計(jì)

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

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)準(zhǔn)備

本文實(shí)驗(yàn)數(shù)據(jù)采用UCI標(biāo)準(zhǔn)評測數(shù)據(jù)集，并采用交叉驗(yàn)證方法進(jìn)行實(shí)驗(yàn)。算法庫采用最常見的3種任務(wù)類型：分類模型算法包括決策樹模型、概率統(tǒng)計(jì)模型、懶惰模型等;回歸模型算法包括線性回歸、回歸樹、隨機(jī)森林等;聚類模型算法包括基于劃分聚類、基于層次聚類和基于密度聚類等。

4.2 實(shí)驗(yàn)過程與結(jié)果分析

4.2.1 樣本數(shù)據(jù)集特征向量

表2表示選取的部分樣本數(shù)據(jù)集概要信息。

4.2.2 調(diào)度算法資源數(shù)學(xué)模型評價(jià)

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

測試任務(wù)集調(diào)用算法準(zhǔn)確率如圖3所示，包括最佳、最差以及平均推薦準(zhǔn)確率?？梢钥闯?，測試任務(wù)集平均最佳調(diào)度準(zhǔn)確率約為82.15%，除個(gè)別任務(wù)數(shù)據(jù)集調(diào)度準(zhǔn)確結(jié)果不理想外，大部分測試數(shù)據(jù)集調(diào)用準(zhǔn)確率均能達(dá)到80%及以上。而且，與傳統(tǒng)“Win-Draw-Loss”策略（WDL）相比，該算法平均精度約高出0.3%～0.8%。

4.2.3 改進(jìn)的簡化粒子群模糊C均值聚類評價(jià)

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

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

5 結(jié)語

本文通過構(gòu)建調(diào)度算法資源數(shù)學(xué)模型并設(shè)計(jì)一種基于改進(jìn)的簡化粒子群優(yōu)化的模糊C均值聚類算法對任務(wù)內(nèi)部結(jié)構(gòu)特征及任務(wù)性能特點(diǎn)進(jìn)行分析，讓具有不同偏好的任務(wù)與具有相應(yīng)性能特點(diǎn)的資源進(jìn)行匹配，從而在一定程度上提高任務(wù)執(zhí)行效率。通過調(diào)用算法資源數(shù)學(xué)模型，為提交的任務(wù)數(shù)據(jù)集選擇算法庫中的適用算法。實(shí)驗(yàn)結(jié)果表明，大多數(shù)情況下該調(diào)度算法是有效可行的，改進(jìn)的聚類算法也能夠在一定程度上彌補(bǔ)FCM算法缺陷，從而有效提高任務(wù)調(diào)度有效性。

參考文獻(xiàn)：

[1] 陳凱，朱鈺. 機(jī)器學(xué)習(xí)及其相關(guān)算法綜述[J]. 統(tǒng)計(jì)與信息論壇， 2007， 22（5）：105-112.

[2] TOM M.MITCHELL. 機(jī)器學(xué)習(xí)（計(jì)算機(jī)科學(xué)叢書）[M]. 北京：機(jī)械工業(yè)出版社，2014.

[3] 陳宇. 基于典型任務(wù)的多星協(xié)同調(diào)度關(guān)鍵問題研究[D]. 武漢：武漢大學(xué)，2012.

[4] 馬亮，李曉. 基于改進(jìn)粒子群算法的云計(jì)算任務(wù)調(diào)度策略[J]. 計(jì)算機(jī)與現(xiàn)代化，2013， 11（9）：78-81.

[5] 李靜梅，王雪，吳艷霞. 一種改進(jìn)的優(yōu)先級列表任務(wù)調(diào)度算法[J]. 計(jì)算機(jī)科學(xué)，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] 曾子林，張宏軍，張睿，等. 基于元學(xué)習(xí)思想的算法選擇問題綜述[J]. 控制與決策，2014（6）：961-968.

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

[10] 徐盈盈，鐘才明. 基于集成學(xué)習(xí)的無監(jiān)督離散化算法[J]. 計(jì)算機(jī)應(yīng)用，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] 代明，鐘才明，龐永明，等. 基于數(shù)據(jù)集屬性相似性的聚類算法推薦[J]. 南京大學(xué)學(xué)報(bào)（自然科學(xué)版），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]. 浙江大學(xué)學(xué)報(bào)（工學(xué)版），2006，40（6）：1041-1044.

[19] 胡旺，李志蜀. 一種更簡化而高效的粒子群優(yōu)化算法[J]. 軟件學(xué)報(bào)，2007，18（4）：861-868.

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

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

（責(zé)任編輯：孫 娟）