[發(fā)明專利]基于匈牙利算法的眾包平臺新任務(wù)多目標推薦方法

在審

• 申請?zhí)枺?/td>: 201910375357.0
• 申請日: 2019-05-07
• 公開（公告）號: CN110276655A
• 公開（公告）日: 2019-09-24
• 發(fā)明（設(shè)計）人: 姚香娟;鞏敦衛(wèi);施智敏;楊焱;黨向盈;侯婷婷;魏昌卿;趙倩;趙晴
• 申請（專利權(quán)）人: 中國礦業(yè)大學(xué)
• 主分類號: G06Q30/06
• 分類號: G06Q30/06
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.基于匈牙利算法的眾包平臺新任務(wù)多目標推薦方法，其特征在于如下步驟：

步驟1：提出評估用戶在優(yōu)化目標下完成新任務(wù)效率的方法；

由于新任務(wù)可利用的信息有限，根據(jù)眾包平臺任務(wù)數(shù)據(jù)信息與用戶信息，構(gòu)建用戶與新任務(wù)的聯(lián)系；通過任務(wù)標題和需求文本尋找用戶記錄中的相似任務(wù)，基于相似任務(wù)構(gòu)建用戶與新任務(wù)的聯(lián)系；選取評價指標對用戶在優(yōu)化目標下完成相似任務(wù)的效率進行評價，作為用戶在優(yōu)化目標下完成新任務(wù)效率的估計值；

步驟1.1：尋找相似任務(wù)

選用基于向量空間模型VSM的TF-IDF方法將新任務(wù)和用戶交易記錄中已完成任務(wù)的標題和需求描述文本轉(zhuǎn)化為向量表示，利用余弦相似度分別計算任務(wù)標題文本和需求描述文本間的相似度；最后，采用熵權(quán)法給兩個相似度值賦予權(quán)重，計算其線性加權(quán)和作為任務(wù)間的相似度，設(shè)任務(wù)j₁,j₂的相似度為S(j₁,j₂)，令

S(j₁,j₂)＝δS₁(j₁,j₂)+(1-δ)S₂(j₁,j₂)

其中S₁(j₁,j₂)為j₁,j₂標題文本相似度，δ為S₁(j₁,j₂)的權(quán)重，S₂(j₁,j₂)為j₁,j₂需求描述文本相似度，1-δ為S₂(j₁,j₂)的權(quán)重；將與第j項新任務(wù)相似度大于α的第i個用戶交易記錄中的已完成任務(wù)ST_ij作為第j項新任務(wù)的相似任務(wù)；

步驟1.2：評價用戶在優(yōu)化目標下完成相似任務(wù)的效率

選取優(yōu)化目標下的評價指標：設(shè)Ind_kl表示第k個目標的第l個評價指標；質(zhì)量目標的度量指標包括任務(wù)需求描述文本字符數(shù)(Ind₁₁)、任務(wù)關(guān)注用戶數(shù)(Ind₁₂)和提供方案用戶數(shù)(Ind₁₃)；時間目標的度量指標包括任務(wù)規(guī)定完成時間(Ind₂₁)、中標用戶完成時間/任務(wù)規(guī)定完成時間(Ind₂₂)和方案篩選時間/方案數(shù)(Ind₂₃)；成本目標的度量指標包括總額度(Ind₃₁)和獎勵額度(Ind₃₂)；使用模糊綜合評價法評價用戶完成相似任務(wù)的效率；計算用戶在目標下完成相似任務(wù)的效率；若第i個用戶交易記錄中滿足條件的相似任務(wù)數(shù)大于1，取相似任務(wù)指標值的均值作為ST_ij在指標下的取值進行計算；

設(shè)為在指標Ind_kl下第i個用戶完成ST_ij的效率，ST_ij在指標Ind_kl下的取值為若指標值越大效率越大，則

若指標值越小效率越大，則

其中

求得之后，采用熵權(quán)法為指標設(shè)置權(quán)重，設(shè)ω_kl為指標Ind_kl的權(quán)重，為第i個用戶在指標Ind_kl下完成ST_ij的效率，為第i個用戶在第k個目標下完成ST_ij的效率，則

將用戶完成相似任務(wù)的效率作為用戶完成新任務(wù)效率的估計值，若第i個用戶交易記錄中滿足條件的相似任務(wù)數(shù)量為0，說明用戶沒有參與過與新任務(wù)類似的任務(wù)，此時記第i個用戶完成新任務(wù)的效率值為0；

步驟1.3：估計用戶在優(yōu)化目標下完成新任務(wù)的效率

m個用戶對應(yīng)第j項新任務(wù)的相似任務(wù)集合為{ST_1j，ST_2j，ST_3j，…，ST_mj}，若第i個用戶完成ST_ij對應(yīng)的效率滿足

這表明第i位用戶曾完成過與第j項新任務(wù)同類型的任務(wù)，且是所有用戶完成記錄中效率最高的，因此用戶完成相似任務(wù)的效率可以度量用戶完成新任務(wù)的效率；并且用戶完成相似任務(wù)的效率值越高，用戶完成新任務(wù)的效率值就越高；因此可以將用戶完成相似任務(wù)的效率值作為用戶完成新任務(wù)效率的估計值，則有第i個用戶在第k個目標下完成第j項任務(wù)的效率值

其中，k＝1表示質(zhì)量效率，k＝2表示時間效率，k＝3表示成本效率；此時有，效率值越大代表用戶與該任務(wù)匹配度越高；

步驟2：給出眾包新任務(wù)推薦問題的多目標優(yōu)化模型；

設(shè)眾包平臺有n項處于待選擇狀態(tài)的新任務(wù)，欲推薦給空選狀態(tài)的m(m≥n)個用戶；在推薦過程中，同時考慮3個目標，即質(zhì)量、時間和成本；若將第j項任務(wù)推薦給第i個用戶，則令x_ij＝1，否則令x_ij＝0；這樣，一個推薦方案就可以表示為如下矩陣

X＝(x_ij)_m×n

第i個用戶在第k個目標下完成第j項新任務(wù)的效率

其中k＝1時表示質(zhì)量效率，k＝2時表示時間效率，k＝3時表示成本效率；基于此建立新任務(wù)推薦問題的多目標優(yōu)化模型；

在眾包平臺中，用戶數(shù)遠遠大于任務(wù)；考慮到用戶完成一項任務(wù)需要花費一定時間，所以在一次推薦過程中為每個用戶推薦且僅推薦一項任務(wù)；若用戶選擇參與某項任務(wù)，則該用戶在下次推薦時處于非空選狀態(tài)，否則進入下次推薦過程，則

其中，若第j項任務(wù)推薦給第i個用戶則x_ij＝1，否則x_ij＝0；此外，同一項任務(wù)可以推薦給多個用戶，假設(shè)第j項任務(wù)可由u_j個人共同完成，則

對第k個目標，其目標函數(shù)值為

F^k(X)表示在推薦方案X下的總效率值，即在推薦方案X下m個用戶在第k個目標下完成n項新任務(wù)的效率值總和；因此，可以將眾包新任務(wù)推薦問題轉(zhuǎn)化為用戶在三個目標下完成新任務(wù)效率函數(shù)值最大化問題；

綜上所述，建立眾包新任務(wù)推薦問題的數(shù)學(xué)模型如下：

其中x_ij＝1表示將第j項任務(wù)推薦給第i個用戶，否則x_ij＝0；

步驟3：用匈牙利算法來對步驟2所建立的模型進行求解；

所述眾包新任務(wù)推薦問題的匈牙利算法求解方法，其特征在于以下步驟：

步驟3.1：效率合成矩陣的構(gòu)建

由構(gòu)建目標k下的效率矩陣

并采用加權(quán)法將多目標優(yōu)化問題轉(zhuǎn)化為單目標優(yōu)化問題；令

則c_ij為用戶在3個目標下完成新任務(wù)的綜合效率；其中，w_k為第k個目標的權(quán)重，權(quán)重值由德爾菲法確定；基于此，構(gòu)建用戶完成新任務(wù)的效率合成矩陣

C＝(c_ij)_m×n

步驟3.2：基于匈牙利算法的求解

設(shè)n項任務(wù)都已推薦一位用戶，則剩余m-n位用戶還可選擇n項任務(wù)中的任一個，則每項任務(wù)最多還可能有m-n位用戶參與；因此，不妨假設(shè)每項任務(wù)都有另外m-n個同樣的復(fù)制任務(wù)，而每位用戶完成復(fù)制任務(wù)與完成該任務(wù)的效率值相同；此時，總?cè)蝿?wù)數(shù)為n(m-n+1)，大于用戶數(shù)m；再假設(shè)還有n(m-n+1)-m＝(m-n)(n-1)個用戶，他們完成任何任務(wù)的效率均為0；這樣，任務(wù)數(shù)與用戶數(shù)相等，問題轉(zhuǎn)化為將n(m-n+1)項任務(wù)推薦給n(m-n+1)個用戶，使得每項任務(wù)由且僅由一個用戶完成，符合傳統(tǒng)指派問題的條件，可由匈牙利算法求解；

基于上述過程，可得C的擴展效率矩陣為

其中矩陣第一行C的個數(shù)為m-n+1；第二行中的0表示(m-n)(n-1)行n列的零矩陣；

設(shè)對A進行求解所得矩陣為

X＝(x_ij)_{n(m-n+1)×n(m-n+1)}

而眾包任務(wù)推薦問題的解可根據(jù)X前m行中值為1的元素位置決定；若x_ij＝1，且i≤m，此時1≤j≤n(m-n+1)，將j表示為

j＝pn+q(0≤p≤m-n,1≤q≤n)

當p＝0時，j＝q，表示第i位用戶被推薦完成第q項任務(wù)；當1≤p≤m-n時，表示第i位用戶被推薦完成第q項任務(wù)的復(fù)制任務(wù)；綜上，當0≤p≤m-n時，第i位用戶被推薦完成第q項任務(wù)。