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

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

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

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

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

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

1 引言

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

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

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

2 模型描述

(1)

令 ：

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

(2)

(3)

(4)

(5)

(6)

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

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

本文從數(shù)據(jù)集中篩選出任務(wù)ID、用戶ID和用戶對任務(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的分值的最大值；最后，通過字典的遍歷來填充矩陣，從而建立用戶-任務(wù)評分矩陣。圖1闡明了用戶-任務(wù)矩陣的建立過程。

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

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

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

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

(7)

(8)

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

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

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

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

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

5.1矩陣初始化階段

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

5.2矩陣迭代階段

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

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

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

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

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

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

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

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

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

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

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

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

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

7 算法仿真實驗

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

7.1實驗參數(shù)設(shè)置

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

7.2實驗結(jié)果驗證指標(biāo)

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

(9)

(10)

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

7.3實驗結(jié)果分析

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

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

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

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

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

7.3.5交叉算子分析 在維度K=5，Pm=0.1的情形下測試不同的交叉概率Pc對指標(biāo)RMSE和MAE值的影響。由圖4、圖5可知，當(dāng)交叉概率值Pc從0.3逐漸增大的時候，RMSE和MAE值不斷下降，說明算法的推薦準(zhǔn)確度不斷提高，然而當(dāng)交叉概率Pc超過0.5并繼續(xù)增大時，RMSE和MAE指標(biāo)值也隨之增大，說明推薦準(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對RMSE的影響

圖3 變異概率Pm對MAE的影響

圖4 交叉概率Pc對RMSE的影響

圖5 交叉概率Pc對MAE的影響

8 結(jié)束語

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

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

目前，眾包平臺任務(wù)自動化分配還是一個較新的領(lǐng)域，未來可以從構(gòu)建眾包平臺進(jìn)行真實數(shù)據(jù)采集，采用高級推薦算法、大規(guī)模分布式計算等方法進(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] 孟祥武，劉樹棟，張玉潔.社會化推薦系統(tǒng)研究[J]. 軟件學(xué)報，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)域為遺傳算法，推薦系統(tǒng)。E-mail：793944046@qq.com.

1005-9679(2017)05-0098-06