基于遺傳非負(fù)矩陣分解的任務(wù)自動(dòng)分配研究

毛 鵬， 章鳴雷， 胡傳杉(浙江工業(yè)大學(xué) 經(jīng)貿(mào)管理學(xué)院，浙江 杭州 310023)

基于遺傳非負(fù)矩陣分解的任務(wù)自動(dòng)分配研究

毛 鵬， 章鳴雷， 胡傳杉
(浙江工業(yè)大學(xué) 經(jīng)貿(mào)管理學(xué)院，浙江 杭州 310023)

隨著眾包模式的大量應(yīng)用，眾包平臺(tái)上的任務(wù)出現(xiàn)了爆炸性增長(zhǎng)，導(dǎo)致用戶很難在大量的任務(wù)中找到適合自己的任務(wù)。近年來(lái)，國(guó)內(nèi)外研究人員提出利用矩陣分解等算法來(lái)進(jìn)行任務(wù)自動(dòng)分配，其中非負(fù)矩陣分解由于可解釋性好，能夠緩解冷啟動(dòng)問題，準(zhǔn)確度較高等優(yōu)點(diǎn)受到了廣泛關(guān)注。然而，非負(fù)矩陣分解算法的目標(biāo)函數(shù)通常是不可微不連續(xù)的，且梯度搜索方法容易陷入局部最優(yōu)?；诖?，提出一種基于遺傳算法的非負(fù)矩陣分解算法來(lái)實(shí)現(xiàn)眾包平臺(tái)任務(wù)的自動(dòng)分配，利用遺傳算法的全局最優(yōu)性來(lái)提高算法的準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明本算法在低維空間比經(jīng)典的PMF算法，隨機(jī)初始化的NMF算法和TaskRec算法具有更好的準(zhǔn)確度。

遺傳算法；非負(fù)矩陣分解；眾包；任務(wù)分配

1 引言

眾包由杰夫·豪[1]在2006年首次提出，它指機(jī)構(gòu)把由員工執(zhí)行的工作任務(wù)，以自由自愿的形式交給非特定大眾網(wǎng)絡(luò)的方法。隨著眾包模式的流行，眾包平臺(tái)任務(wù)呈爆發(fā)式增長(zhǎng)，用戶的任務(wù)選擇越來(lái)越多，但是大量的任務(wù)信息也會(huì)使用戶迷失在信息的海洋，需要用更多的時(shí)間和精力來(lái)尋找適合的任務(wù)[2]。如果眾包平臺(tái)有合適的任務(wù)分配算法，把合適的任務(wù)自動(dòng)分配給合適的用戶，那么將極大提高企業(yè)和用戶的工作效率[3-5]。

Panagiotis等[6]對(duì)亞馬遜的AMT眾包平臺(tái)進(jìn)行了全面具體的分析，指出眾包平臺(tái)急需任務(wù)自動(dòng)分配功能。Ambati 等[7]提出了基于分類技術(shù)的任務(wù)自動(dòng)分配算法，但這種算法準(zhǔn)確度不高且任務(wù)分類對(duì)算法準(zhǔn)確度影響較大。Yuen等[5]在Ambati 的基礎(chǔ)上加入了用戶的任務(wù)選擇歷史數(shù)據(jù)，提出了TaskRank算法，然而TaskRank也需要對(duì)任務(wù)進(jìn)行分類，而有些任務(wù)可能同時(shí)屬于多種任務(wù)類型從而降低了算法準(zhǔn)確度，這種算法也不能對(duì)新任務(wù)進(jìn)行自動(dòng)分配。Yuen等[8-9]之后提出了用PMF算法進(jìn)行眾包平臺(tái)的任務(wù)自動(dòng)分配，但是由于分解后的矩陣元素存在負(fù)值從而可解釋差且算法準(zhǔn)確度不高。Mejdl Safran等人[10]提出了眾包平臺(tái)的實(shí)時(shí)任務(wù)分配算法，證明了算法的計(jì)算效率，但是并沒有說(shuō)明算法任務(wù)分配的準(zhǔn)確性。

基于這樣的現(xiàn)實(shí)，本文提出遺傳非負(fù)矩陣分解算法進(jìn)行任務(wù)自動(dòng)分配，根據(jù)用戶歷史任務(wù)完成情況，用戶搜索信息等信息通過VBA編程建立用戶-任務(wù)評(píng)分矩陣A，將其分解為用戶潛在特征矩陣W和任務(wù)潛在特征矩陣H，通過兩個(gè)矩陣乘積WH來(lái)預(yù)測(cè)矩陣A中對(duì)應(yīng)元素的缺失值，給定一連串的任務(wù)，我們通過預(yù)測(cè)分?jǐn)?shù)的高低給任務(wù)排序，將預(yù)測(cè)評(píng)分靠前的任務(wù)推薦給用戶。

2 模型描述

(1)

令 ：

E=A-WH，eij是矩陣E的第i行第j列元素，那么E的F2范數(shù)可以表示為：

(2)

(3)

(4)

(5)

(6)

這里的式(1)是本文算法迭代階段的評(píng)價(jià)函數(shù)，式(4)和(6)是算法初始化階段的評(píng)價(jià)函數(shù)。

3 用戶-任務(wù)評(píng)分矩陣的構(gòu)建

本文從數(shù)據(jù)集中篩選出任務(wù)ID、用戶ID和用戶對(duì)任務(wù)的完成狀態(tài)三列，按照表1的規(guī)則將用戶不同的任務(wù)完成狀態(tài)轉(zhuǎn)換為不同的非負(fù)數(shù)值，然后進(jìn)行VBA編程。首先，通過字典獲得Hit ID和Worker ID的所有清單；其次，把獲得的清單復(fù)制到矩陣結(jié)果表中；之后，通過字典獲取相同Hit ID和Worker ID的分值的最大值；最后，通過字典的遍歷來(lái)填充矩陣，從而建立用戶-任務(wù)評(píng)分矩陣。圖1闡明了用戶-任務(wù)矩陣的建立過程。

表1 用戶-任務(wù)評(píng)分矩陣的建立規(guī)則

圖1 用戶-任務(wù)評(píng)分矩陣的建立過程

4 傳統(tǒng)的非負(fù)矩陣分解算法

傳統(tǒng)的NMF算法使用梯度下降的方法進(jìn)行用戶-任務(wù)評(píng)分矩陣的分解，隨機(jī)初始化一個(gè)用戶潛在特征矩陣W和一個(gè)任務(wù)潛在特征矩陣H，然后按照式(7)(8)的乘性迭代公式交替優(yōu)化它們。

(7)

(8)

但是，這樣往往會(huì)導(dǎo)致算法陷入局部最小[12]，影響算法的準(zhǔn)確度。

5 基于遺傳算法的非負(fù)矩陣分解算法

本文算法隨機(jī)初始化T個(gè)矩陣種群，然后在限定的搜索空間進(jìn)行T個(gè)W和T個(gè)H的迭代優(yōu)化，相對(duì)一個(gè)W和一個(gè)H而言，搜索空間更廣，提高了算法的全局搜索能力。

令T代表種群個(gè)數(shù)，Pm表示矩陣的變異概率，Pc表示矩陣的交叉概率，s%表示矩陣W和H變異時(shí)矩陣元素發(fā)生變異的比例，k為分解矩陣的維度，迭代代數(shù)用gen表示，r為gen的最大值。

建立用戶-任務(wù)評(píng)分矩陣后，本文提出的基于遺傳算法的非負(fù)矩陣分解算法分為兩個(gè)部分：矩陣初始化和矩陣的迭代優(yōu)化。在矩陣分解的初始階段，用PMX交叉和單點(diǎn)變異，以式(4)、(6)為評(píng)價(jià)函數(shù)進(jìn)行兩個(gè)非負(fù)矩陣的迭代優(yōu)化直到指定的迭代次數(shù)，得到兩個(gè)初始化的非負(fù)子矩陣。在此基礎(chǔ)上，使用式(1)作為適應(yīng)度評(píng)價(jià)函數(shù)，以矩陣隨機(jī)行或列的交叉、矩陣固定比例元素的變異進(jìn)行初始化后兩個(gè)非負(fù)矩陣的迭代優(yōu)化直到指定的迭代次數(shù)，此時(shí)得到的兩個(gè)非負(fù)矩陣的乘積為原矩陣的近似矩陣。

5.1矩陣初始化階段

由式(3)和(5)可知，矩陣E任何一個(gè)行向量或者列向量的F2范數(shù)變小都會(huì)使矩陣E的F2范數(shù)變小，因此在初始化階段，最小化矩陣W每個(gè)行向量的F2范數(shù)使得式(4)值達(dá)到最小，在此基礎(chǔ)上最小化矩陣H的每個(gè)列向量的F2范數(shù)使得式(6)的值最小。

5.2矩陣迭代階段

5)選擇：若原數(shù)據(jù)以h%參與訓(xùn)練，那么B1,B2，…，B2T同樣以h%相對(duì)應(yīng)的元素、以公式(1)為評(píng)價(jià)函數(shù)進(jìn)行B1,B2，…，B2T的選擇，選擇出使得評(píng)價(jià)函數(shù)最小的前T個(gè)B1,B2，…，B2T，也就是找到了最優(yōu)的T個(gè)矩陣W和相應(yīng)的T個(gè)最優(yōu)的矩陣H；

6)回到第一步，繼續(xù)以同樣的遺傳操作進(jìn)行矩陣的迭代優(yōu)化，直到gen=r；

7)得到分解后的非負(fù)矩陣W和H；

至此，整個(gè)算法的初始化階段和迭代階段執(zhí)行完畢，將用戶-任務(wù)評(píng)分矩陣A分解得到一個(gè)非負(fù)的用戶潛在特征矩陣W和一個(gè)非負(fù)的任務(wù)潛在特征矩陣H。表2以偽代碼的形式說(shuō)明了算法的計(jì)算過程。

表2 基于遺傳算法的NMF算法框架

6 遺傳非負(fù)矩陣分解算法在眾包平臺(tái)任務(wù)自動(dòng)分配的應(yīng)用

為了方便解釋，假設(shè)目標(biāo)矩陣A是500*500的矩陣，隨機(jī)選取80%的矩陣元素作為訓(xùn)練集，那么剩下的20%的元素就作為測(cè)試集測(cè)試算法的準(zhǔn)確度。詳細(xì)步驟有以下幾步:

1)按照表1的規(guī)則，根據(jù)用戶不同的任務(wù)完成狀態(tài)將其轉(zhuǎn)換為0～5對(duì)應(yīng)的數(shù)值，在此基礎(chǔ)上利用VBA編程將數(shù)值化后的數(shù)據(jù)集轉(zhuǎn)換為矩陣的形式得到矩陣A；

2)隨機(jī)抽取矩陣A80%的元素作為訓(xùn)練集，其余20%元素作為測(cè)試集。

3)將矩陣A需要預(yù)測(cè)的20%的元素取值為0，得到矩陣B；

4)將B用本文提出的算法分解為用戶潛在特征矩陣W和任務(wù)潛在特征矩陣H，用W和H的乘積來(lái)近似原矩陣A；

5)將矩陣A未參與運(yùn)算的元素，即20%的測(cè)試集與矩陣W，H乘積WH相應(yīng)的元素進(jìn)行比較；

通過以上6個(gè)步驟，就完成了眾包任務(wù)自動(dòng)分配過程。

7 算法仿真實(shí)驗(yàn)

本文首先建立用戶-任務(wù)評(píng)分矩陣，然后通過基于遺傳算法的非負(fù)矩陣分解算法來(lái)預(yù)測(cè)矩陣的缺失值，給定一連串的任務(wù)，通過預(yù)測(cè)分?jǐn)?shù)的高低給任務(wù)排序，將預(yù)測(cè)評(píng)分高的任務(wù)優(yōu)先分配給用戶。本章將在Matlab的實(shí)驗(yàn)環(huán)境下驗(yàn)證算法的任務(wù)分配準(zhǔn)確度。

7.1實(shí)驗(yàn)參數(shù)設(shè)置

W和H的上下邊界限定在[0,max(A)]，變異概率取值為0.1，變異時(shí)矩陣元素發(fā)生隨機(jī)變異的比例為1%。交叉概率取值0.8，種群數(shù)量為100，迭代代數(shù)設(shè)置為500。文章代碼采用Matlab語(yǔ)言編寫，實(shí)驗(yàn)平臺(tái)為Intel(R)Core(TM)M330,4.00GB RAM,實(shí)驗(yàn)環(huán)境為Matlab2012.a(7.14.0.739)。

7.2實(shí)驗(yàn)結(jié)果驗(yàn)證指標(biāo)

本文采用均方根誤差RMSE和平均絕對(duì)誤差MAE兩個(gè)指標(biāo)來(lái)驗(yàn)證算法的任務(wù)自動(dòng)分配準(zhǔn)確度。對(duì)于測(cè)試集中的用戶w和任務(wù)h，awh表示用戶w對(duì)任務(wù)h的實(shí)際評(píng)分，Awh是遺傳非負(fù)矩陣分解算法的預(yù)測(cè)評(píng)分，那么RMSE和MAE可定義為：

(9)

(10)

這兩個(gè)指標(biāo)是評(píng)價(jià)算法分配準(zhǔn)確度最常用的評(píng)價(jià)指標(biāo)，RMSE和MAE值越小，表示任務(wù)分配越準(zhǔn)確。

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

本文的數(shù)據(jù)集與Man-Ching Yuen的數(shù)據(jù)集都取自NAACL 2010年公開的亞馬遜眾包平臺(tái)AMT上的數(shù)據(jù)。每次實(shí)驗(yàn)的結(jié)果都是取10次實(shí)驗(yàn)指標(biāo)的平均值。以RMSE和MAE兩個(gè)指標(biāo)與經(jīng)典的PMF算法，隨機(jī)初始化的NMF算法，Man-Ching Yuen等人的TaskRec算法作比較，實(shí)驗(yàn)結(jié)果如表3至表6所示。為了方便算法實(shí)驗(yàn)結(jié)果的描述，用大寫字母GN來(lái)表示本文提出的基于遺傳算法的非負(fù)矩陣分解算法。本文實(shí)驗(yàn)結(jié)果將從RMSE分析， MAE分析，GN算法與隨機(jī)初始化的非負(fù)矩陣分解算法比較，變異算子分析，交叉算子分析五個(gè)方面進(jìn)行詳細(xì)的數(shù)值分析，驗(yàn)證本文提出的算法準(zhǔn)確度和參數(shù)對(duì)算法準(zhǔn)確度的影響。

7.3.1RMSE指標(biāo)分析 本文在K=5和K=15的維度下驗(yàn)證GN算法的任務(wù)分配準(zhǔn)確度。通過表3、表4的實(shí)驗(yàn)數(shù)據(jù)，可以發(fā)現(xiàn)，在維度K=5時(shí)，GN的RMSE指標(biāo)優(yōu)于PMF 和TaskRec，在K=15時(shí)GN算法RMSE指標(biāo)好于TaskRec，部分好于PMF算法。具體來(lái)說(shuō)，本文提出的GN算法RMSE角度的準(zhǔn)確度比PMF算法平均提高了24.7%，比TaskRec算法平均提高了39.4%。

7.3.2MAE指標(biāo)分析 通過表5、表6的實(shí)驗(yàn)數(shù)據(jù)，可以發(fā)現(xiàn)，在維度等于5時(shí)，GN的MAE指標(biāo)好于PMF和TaskRec，在維度為15的時(shí)候，算法的準(zhǔn)確性部分優(yōu)于PMF，好于TaskRec。具體來(lái)說(shuō)，本文提出的基于遺傳算法的非負(fù)矩陣分解算法的MAE角度的準(zhǔn)確度比PMF算法平均提高了37.7%，比TaskRec算法平均提高了46.6%。

7.3.3GN算法與隨機(jī)初始化的NMF算法準(zhǔn)確度比較分析 傳統(tǒng)的矩陣分解算法在矩陣初始化階段是隨機(jī)初始化的，本文提出的GN算法使用遺傳算法進(jìn)行矩陣的初始化，由表3至表6可知，本文算法的RMSE角度的準(zhǔn)確度比隨機(jī)初始化的NMF算法平均提高了28.5%，MAE角度的準(zhǔn)確度比隨機(jī)初始化的NMF算法平均提高了35.6%。因此，使用遺傳算法進(jìn)行矩陣的初始化能夠顯著提高算法的準(zhǔn)確度。

7.3.4變異算子分析 在維度K=5，Pc=0.8的情形下測(cè)試不同的變異概率對(duì)指標(biāo)RMSE和MAE的影響。由圖2、圖3可知，當(dāng)變異概率值Pm從0.05逐漸增大的時(shí)候，RMSE和MAE值不斷下降，說(shuō)明算法的推薦準(zhǔn)確度不斷提高，然而當(dāng)變異概率Pm超過0.25并繼續(xù)增大時(shí)，RMSE和MAE指標(biāo)值也隨之增大，說(shuō)明推薦準(zhǔn)確度逐漸下降。因此，最優(yōu)的變異概率Pm大概是0.25左右。

7.3.5交叉算子分析 在維度K=5，Pm=0.1的情形下測(cè)試不同的交叉概率Pc對(duì)指標(biāo)RMSE和MAE值的影響。由圖4、圖5可知，當(dāng)交叉概率值Pc從0.3逐漸增大的時(shí)候，RMSE和MAE值不斷下降，說(shuō)明算法的推薦準(zhǔn)確度不斷提高，然而當(dāng)交叉概率Pc超過0.5并繼續(xù)增大時(shí)，RMSE和MAE指標(biāo)值也隨之增大，說(shuō)明推薦準(zhǔn)確度逐漸下降，最優(yōu)的交叉概率Pc大概是0.5左右。

表3 80%和60%訓(xùn)練集不同維度下RMSE指標(biāo)值

表4 40%和20%訓(xùn)練集不同維度下RMSE指標(biāo)值

表5 80%和60%訓(xùn)練集不同維度下MAE指標(biāo)值

表6 40%和20%訓(xùn)練集不同維度下MAE指標(biāo)值

圖2 變異概率Pm對(duì)RMSE的影響

圖3 變異概率Pm對(duì)MAE的影響

圖4 交叉概率Pc對(duì)RMSE的影響

圖5 交叉概率Pc對(duì)MAE的影響

8 結(jié)束語(yǔ)

本文針對(duì)眾包平臺(tái)任務(wù)自動(dòng)分配問題提出了一種基于遺傳算法的非負(fù)矩陣分解算法，利用遺傳算法的全局最優(yōu)性來(lái)提高算法的準(zhǔn)確度。

通過實(shí)際數(shù)據(jù)的測(cè)試，發(fā)現(xiàn)本文提出的算法在低維空間具有較好的準(zhǔn)確度。此外，由于本文算法直接在用戶-任務(wù)評(píng)分矩陣上進(jìn)行非負(fù)分解，因此分解后的非負(fù)子矩陣具有良好的解釋性，避免了復(fù)雜的任務(wù)分類且緩解了冷啟動(dòng)問題。

目前，眾包平臺(tái)任務(wù)自動(dòng)化分配還是一個(gè)較新的領(lǐng)域，未來(lái)可以從構(gòu)建眾包平臺(tái)進(jìn)行真實(shí)數(shù)據(jù)采集，采用高級(jí)推薦算法、大規(guī)模分布式計(jì)算等方法進(jìn)行研究。

[ 1 ] HOWE J. The rise of crowdsourcing[J]. Wired Magazine, 2006, 14(6): 176-183.

[ 2 ] 侯文華，郝琳娜.眾包模式-企業(yè)創(chuàng)新的新助力[M]. 北京：科學(xué)出版社，2016：1-101.

[ 3 ] STEFFEN S, SVENJA N, SEBASTIAN S. Perceived Task Similarities For Task Recommendation in Crowd-sourcing Systems[C]∥Proceedings of the 25th International Conference Companion on World Wide Web, 2016: 585-590.

[ 4 ] CHILTON L B, HORTON J J, MILLER R C. Task Search in a Human Computation Market[C]∥Proceedings of the ACM SIGKDD workshop on human computation, 2010: 1-9.

[ 5 ] YUEN M C, KING I, LEUNG K S. Task Matching in Crowd-sourcing[C]∥IEEE International Conferences on Internet of Things, and Cyber, Physical and Social Computing, 2011.

[ 6 ] PANAGIOTIS G. IPEIROTIS. Analyzing the Amazon mechanical turk market place[J]. XRDS: Crossroads, 2010, 17(2): 16-21.

[ 7 ] AMBATI V, VOGEL S, CARBONELL J. Towards task recommendation in micro-task markets[J]. Human computation, 2011(11): 11.

[ 8 ] YUEN M C, KING I, LEUNG K S. Task Recommendation in Crowdsourcing Systems[C]∥ACM, crowdkdd, 2012.

[ 9 ] YUEN M C, KING I, LEUNG K S. Taskrec: a task recommendation framework in crowd-sourcing systems[J]. Neural Processing Letters, 2015, 41(2): 223-238.

[10] MEJDL S, DUNREN, CHE. Real-time recommendation algorithms forcrowd-sourcing systems[J]. Applied Computing and Informatics, 2016: 124-133.

[11] 孟祥武，劉樹棟，張玉潔.社會(huì)化推薦系統(tǒng)研究[J]. 軟件學(xué)報(bào)，2015，26(6)：1356-1372.

[12] LEE D D, SEUNG H S. Algorithms for Non-negative Matrix Factorization[C]∥NIPS, 2001: 556-562.

ResearchonAutomaticAssignmentofTaskBasedonTheGeneticNMF

MAOPeng，ZHANGMinglei，HUChuanshan
(College of Economics and Management, Zhejiang University of Technology, Hangzhou 310023, China)

With the crowd-sourcing used widely, the task in crowd-sourcing platform has exploded, which makes it difficult for users to find appropriate tasks in a large number of tasks. In recent years, domestic and foreign researchers have proposed the use of matrix decomposition algorithm to carry out automatic assignment of tasks. Especially NMF has gained tons of attention because of its advantages, such as good explanation, accuracy and alleviating the cold start problem. However, the objective function of the NMF algorithm is usually non-differentiable and discontinuous, and the gradient search method is easy to fall into the local optimal. Based on this, this paper proposes a NMF algorithm based on genetic algorithm to realize the automatic allocation of the task in crowd-sourcing platform, and the global optimality of the genetic algorithm is used to improve the accuracy of the algorithm. The experimental results show that the proposed algorithm has better accuracy compared with the classical PMF algorithm, randomly initialized NMF and TaskRec algorithm in low dimensional space.

genetic algorithm; nonnegative matrix decomposition; crowd-sourcing; task assignment

TP 181

A

2017-04-13

毛鵬(1991—)，男，湖北咸寧人，碩士研究生，主要研究領(lǐng)域?yàn)檫z傳算法，推薦系統(tǒng)。E-mail：793944046@qq.com.

1005-9679(2017)05-0098-06