基于遺傳非負矩陣分解的任務自動分配研究

毛 鵬， 章鳴雷， 胡傳杉(浙江工業大學 經貿管理學院，浙江 杭州 310023)

基于遺傳非負矩陣分解的任務自動分配研究

毛 鵬， 章鳴雷， 胡傳杉
(浙江工業大學 經貿管理學院，浙江 杭州 310023)

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

遺傳算法；非負矩陣分解；眾包；任務分配

1 引言

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

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

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

2 模型描述

(1)

令 ：

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

(2)

(3)

(4)

(5)

(6)

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

3 用戶-任務評分矩陣的構建

本文從數據集中篩選出任務ID、用戶ID和用戶對任務的完成狀態三列，按照表1的規則將用戶不同的任務完成狀態轉換為不同的非負數值，然后進行VBA編程。首先，通過字典獲得Hit ID和Worker ID的所有清單；其次，把獲得的清單復制到矩陣結果表中；之后，通過字典獲取相同Hit ID和Worker ID的分值的最大值；最后，通過字典的遍歷來填充矩陣，從而建立用戶-任務評分矩陣。圖1闡明了用戶-任務矩陣的建立過程。

表1 用戶-任務評分矩陣的建立規則

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

4 傳統的非負矩陣分解算法

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

(7)

(8)

但是，這樣往往會導致算法陷入局部最小[12]，影響算法的準確度。

5 基于遺傳算法的非負矩陣分解算法

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

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

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

5.1矩陣初始化階段

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

5.2矩陣迭代階段

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

6)回到第一步，繼續以同樣的遺傳操作進行矩陣的迭代優化，直到gen=r；

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

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

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

6 遺傳非負矩陣分解算法在眾包平臺任務自動分配的應用

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

1)按照表1的規則，根據用戶不同的任務完成狀態將其轉換為0～5對應的數值，在此基礎上利用VBA編程將數值化后的數據集轉換為矩陣的形式得到矩陣A；

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

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

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

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

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

7 算法仿真實驗

本文首先建立用戶-任務評分矩陣，然后通過基于遺傳算法的非負矩陣分解算法來預測矩陣的缺失值，給定一連串的任務，通過預測分數的高低給任務排序，將預測評分高的任務優先分配給用戶。本章將在Matlab的實驗環境下驗證算法的任務分配準確度。

7.1實驗參數設置

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

7.2實驗結果驗證指標

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

(9)

(10)

這兩個指標是評價算法分配準確度最常用的評價指標，RMSE和MAE值越小，表示任務分配越準確。

7.3實驗結果分析

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

7.3.1RMSE指標分析 本文在K=5和K=15的維度下驗證GN算法的任務分配準確度。通過表3、表4的實驗數據，可以發現，在維度K=5時，GN的RMSE指標優于PMF 和TaskRec，在K=15時GN算法RMSE指標好于TaskRec，部分好于PMF算法。具體來說，本文提出的GN算法RMSE角度的準確度比PMF算法平均提高了24.7%，比TaskRec算法平均提高了39.4%。

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

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

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

7.3.5交叉算子分析 在維度K=5，Pm=0.1的情形下測試不同的交叉概率Pc對指標RMSE和MAE值的影響。由圖4、圖5可知，當交叉概率值Pc從0.3逐漸增大的時候，RMSE和MAE值不斷下降，說明算法的推薦準確度不斷提高，然而當交叉概率Pc超過0.5并繼續增大時，RMSE和MAE指標值也隨之增大，說明推薦準確度逐漸下降，最優的交叉概率Pc大概是0.5左右。

表3 80%和60%訓練集不同維度下RMSE指標值

表4 40%和20%訓練集不同維度下RMSE指標值

表5 80%和60%訓練集不同維度下MAE指標值

表6 40%和20%訓練集不同維度下MAE指標值

圖2 變異概率Pm對RMSE的影響

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

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

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

8 結束語

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

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

目前，眾包平臺任務自動化分配還是一個較新的領域，未來可以從構建眾包平臺進行真實數據采集，采用高級推薦算法、大規模分布式計算等方法進行研究。

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

[ 2 ] 侯文華，郝琳娜.眾包模式-企業創新的新助力[M]. 北京：科學出版社，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] 孟祥武，劉樹棟，張玉潔.社會化推薦系統研究[J]. 軟件學報，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—)，男，湖北咸寧人，碩士研究生，主要研究領域為遺傳算法，推薦系統。E-mail：793944046@qq.com.

1005-9679(2017)05-0098-06