邢玉萍，詹永照

（1.江蘇大學計算機科學與通信工程學院，江蘇 鎮(zhèn)江 212013；2.江蘇省工業(yè)網(wǎng)絡安全技術(shù)重點實驗室，江蘇 鎮(zhèn)江 212013）

1 引言

眾包[1]利用群體Worker 的智慧解決問題，已成為數(shù)據(jù)處理的有力機制，特別是非結(jié)構(gòu)化數(shù)據(jù)，如圖像、視頻和文本，出現(xiàn)了使用人工完成數(shù)據(jù)處理的任務，包括排序[2]、聚類[3]、最大值求解[4]、過濾[5]和去重[6]等。

目前，傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)和搜索引擎難以較好地完成排序任務，例如對全球大學排名排序、某領(lǐng)域權(quán)威論文排序，原因有以下幾點。1) 相對封閉世界的假設，即數(shù)據(jù)都已存儲在數(shù)據(jù)庫里，不在數(shù)據(jù)庫里的數(shù)據(jù)就是不存在的，并且數(shù)據(jù)庫中缺少明確標注的相關(guān)信息，不能根據(jù)模糊標準進行匹配、排序或聚合結(jié)果。但是互聯(lián)網(wǎng)環(huán)境下信息量急劇增加，未存儲在數(shù)據(jù)庫的數(shù)據(jù)并不意味著不存在，人們有能力在多個搜索引擎和參考資料等工具的幫助下，找到目前沒有的信息。2) 缺乏對語義的理解，特別是排序任務，并不能很好地從數(shù)據(jù)庫中將相關(guān)信息提取出來自動排序。但是，人們卻比較擅長這些計算機很難或者不可能完成的任務。

快速獲得高質(zhì)量的解決方案是眾包請求者的目的。完成任務的Worker 主要來自普通大眾，一般不具有提供高質(zhì)量解決方案的特征，因此請求者通常采用任務冗余發(fā)放的算法，將相同任務發(fā)放給多個Worker，然后對Worker 的提交結(jié)果進行匯聚得到合適的解決方案。發(fā)布排序任務一般有2 種形式：1) 將任務拆分成微任務，以成對比較的形式進行分發(fā)，利用推理減少任務量，這種方式在任務量大時任務拆分困難、代價大、完成時間和完成質(zhì)量難以保證[7]；2) 直接發(fā)布該排序任務，由不同Worker 獨立完成。由于不同Worker 在不同專業(yè)領(lǐng)域可能具有不同水平，有的甚至無法完成某些任務，為了得到高質(zhì)量的匯聚結(jié)果，需要從有噪聲的答案中推斷出高質(zhì)量的結(jié)果。結(jié)果匯聚算法的優(yōu)劣直接決定任務的完成質(zhì)量，一般以二次眾包或者統(tǒng)計算法自動完成。常用的基于統(tǒng)計的結(jié)果匯聚算法包括Listwise 算法和數(shù)據(jù)融合算法，這2 類算法都考慮了待排序?qū)ο蟮呐琶?位置信息。

Listwise 算法將一個任務下的所有數(shù)據(jù)項的排序結(jié)果列表作為一個訓練樣例，全面考慮一個任務下不同數(shù)據(jù)項之間的序列關(guān)系，優(yōu)化目標是輸出的匯聚結(jié)果和輸入的提交結(jié)果損失函數(shù)最小或者性能最優(yōu)。文獻[8]指出，合適的眾包Worker 約占Worker 總數(shù)的55%，其平均準確率約為75%，因此，基于Listwise 的結(jié)果匯聚算法容易受到不合格Worker（如惡意Worker 和搭便車Worker[9]）提交結(jié)果的影響，從而降低匯聚結(jié)果的質(zhì)量。Listwise算法的模型復雜度和訓練時間的長短依賴于待排序數(shù)據(jù)項的數(shù)量階乘，訓練復雜度很高[2]。

數(shù)據(jù)融合算法的優(yōu)化目標是匯聚結(jié)果的性能最大化。線性組合（LC,linear combination）算法是一類有監(jiān)督的數(shù)據(jù)融合算法，其一般流程為：首先多個Worker 給出訓練任務中待排序數(shù)據(jù)項的全排序結(jié)果，然后選擇模型依據(jù)標注信息訓練出所有Worker 的優(yōu)化權(quán)重向量，最后用該權(quán)重向量對測試排序任務進行結(jié)果匯聚。文獻[10-11]分別使用遺傳算法和差分進化算法獲得優(yōu)化的權(quán)重向量，但是這類基于演化計算的算法解決眾包結(jié)果匯聚任務存在以下2 個問題。

1) 即使是合格的Worker，也很難給出所有數(shù)據(jù)項的準確全排序，排序結(jié)果會存在很多噪聲，并且增加Worker 的額外負擔。實際應用中，Worker能夠很快給出Top-k數(shù)據(jù)項，例如，在圖像檢索任務中，給定1 000 張餐館的照片，希望找到最吸引人和最能描述該餐館的Top-k照片。使用基于Top-k的排序可以降低任務難度，Worker 能在給出更準確的排序結(jié)果的同時，甄別出不合格的Worker。如果Worker 在訓練任務的Top-k排序上是不合格的，那么該Worker 在測試任務上依然是不合格的。

2) 基于演化計算的算法即使在排序列表很短的情況下，在解空間尋優(yōu)依然是NP-hard 問題，存在耗時過長的問題，不能有效應用于實時性要求較高的結(jié)果匯聚場合。相比全排序，基于Top-k能快速學習出各Worker 的權(quán)重。

針對上述2 個問題，本文提出基于Worker 權(quán)重的差分進化和Top-k排序的結(jié)果匯聚算法。該算法更合理地考慮各個Worker 的差異性和不確定性，且快速有效地提高匯聚結(jié)果的質(zhì)量。這項研究具有較好的理論意義和現(xiàn)實價值。

本文主要的研究工作如下。

1) 建立眾包排序任務結(jié)果匯聚的Worker 權(quán)重優(yōu)化模型，實現(xiàn)Worker 權(quán)重與任務對結(jié)果性能需求匹配的最大化。針對多任務分配中眾包Workrer完成排序任務存在差異性問題，基于目標函數(shù)和約束條件中Worker 完成任務的不確定性和差異性影響，建立基于差分進化算法的Worker 權(quán)重優(yōu)化模型，獲取多數(shù)據(jù)項場景下候選結(jié)果最優(yōu)權(quán)重。該模型是一個非凸、非線性、多元優(yōu)化問題，很難直接獲得最優(yōu)解。

2) 提出基于Top-k排序的優(yōu)化模型求解算法。針對多數(shù)據(jù)項場景下候選結(jié)果的Top-k排序選取，在合適的k值下可快速對1)中模型求解，獲得各Worker 的優(yōu)化權(quán)重。所提算法可實現(xiàn)結(jié)果匯聚的匹配性與匹配速度優(yōu)化，即在提升結(jié)果匯聚速度的同時，具有優(yōu)化的匯聚結(jié)果性能。通過定性分析證明算法的正確性。

3) 仿真實驗結(jié)果表明，所提算法在大幅提升結(jié)果匯聚速度的同時，具有優(yōu)化的匯聚結(jié)果性能。與相關(guān)算法對比，所提算法綜合性能最優(yōu)。

2 相關(guān)工作

近20 多年來，數(shù)據(jù)融合在物聯(lián)網(wǎng)[12]、信息檢索/Web 搜索、眾包[13]、推薦[14]等多個不同的研究領(lǐng)域和應用中得到了廣泛的研究和應用。研究者致力于數(shù)據(jù)融合算法的研究，提出了一系列算法，如無監(jiān)督的CombSUM[15]和CombMNZ[15]算法，有監(jiān)督的LC 算法[16]。權(quán)重分配是影響LC 算法匯聚結(jié)果性能的最主要的因素。

文獻[17]首先提出將LC 算法用于文本數(shù)據(jù)融合，將各個提交結(jié)果的性能作為LC 算法的權(quán)重，然而實驗結(jié)果表明該權(quán)重分配策略并不優(yōu)于使用相同權(quán)重的CombSUM 算法。文獻[18]使用共軛梯度優(yōu)化各個提交結(jié)果的權(quán)重，最大化匯聚結(jié)果性能，該算法的不足在于非常耗時、僅能夠匯聚2～3 個提交結(jié)果、針對指定任務各個提交結(jié)果僅返回前15 個數(shù)據(jù)項。文獻[19-20]基于多元線性回歸模型優(yōu)化各個提交結(jié)果的權(quán)值，實現(xiàn)匯聚結(jié)果性能的最大化。文獻[21]提出ProbFuse 算法，該算法根據(jù)數(shù)據(jù)項在排序列表中的位置估計數(shù)據(jù)項的相關(guān)概率。文獻[22]利用各個提交結(jié)果性能的冪函數(shù)作為權(quán)重分配策略優(yōu)化匯聚結(jié)果的性能，并提出混合權(quán)重分配權(quán)重模式（權(quán)重是性能和差異性的乘積）優(yōu)化匯聚結(jié)果的性能，該算法的不足在于數(shù)據(jù)項更新快的環(huán)境下效率較低。文獻[23]提出基于神經(jīng)網(wǎng)絡的權(quán)重分配策略。文獻[24]基于聚類算法提出ClustFuse 算法。文獻[25]基于期望最大化算法提出MixModel 算法。文獻[26]基于深度神經(jīng)網(wǎng)絡提出Lambda-Merge 算法。文獻[27]基于無監(jiān)督的RRF 和Condorcet 算法提出具有低復雜度的融合算法。文獻[28]基于數(shù)據(jù)項的相似性，使用CombSUM 和CombMNZ 算法進行結(jié)果匯聚。

文獻[10]提出GA-Fusion，采用遺傳算法在權(quán)重空間尋找各個提交結(jié)果的最優(yōu)權(quán)值，實驗結(jié)果表明，GA-Gusion 的性能優(yōu)于前面所提的數(shù)據(jù)融合算法，包括CombSUM、CombMNZ、Z-score、LC、LC2、多元線性回歸、MixModel、ClustFuse、LambdaMerge 等。文獻[11]采用基于差分進化算法尋找最優(yōu)權(quán)值提高匯聚結(jié)果性能。文獻[29]提出面向多樣性任務基于性能、差異性和互補性的線性加權(quán)融合算法，實驗結(jié)果表明所提算法并不優(yōu)于DE 和GA 算法。

文獻[10-11]采用基于演化學習的算法，通過不斷地迭代優(yōu)化權(quán)值提高匯聚結(jié)果的性能，然而，這種基于演化學習算法的不足在于求解時需要在解空間進行大規(guī)模的探索，運行時間很長，不能滿足一些實時性要求高的應用場景的要求。本文研究眾包排序任務實時結(jié)果匯聚問題，能夠既快又好地獲得匯聚結(jié)果。

3 系統(tǒng)模型和框架

LC 算法按各Worker 提交結(jié)果的貢獻度賦予權(quán)重，將2 個或多個排序列表進行線性組合融合在一起，生成一個單一排序列表[28]。因此，如果一個提交結(jié)果具有良好的性能，或者對最終匯聚結(jié)果性能的提升起到了重要作用，那么在結(jié)果匯聚時被賦予較大的權(quán)重；反之，則被賦予較小的權(quán)重。

假設有m個Worker 節(jié)點，分別用w1,w2,…,wm表示，對于給定任務q，各Worker 節(jié)點wi提交一個結(jié)果列表，對所有提交結(jié)果進行匯聚得到匯聚結(jié)果πq。由于各個Worker 排序具有不確定性，各個Worker 的排序質(zhì)量有好有差，因此引入衡量多Worker 排序質(zhì)量的權(quán)重xi(1≤i≤m)表示數(shù)據(jù)項的排序結(jié)果更確定的得分。在多個Worker 參與的眾包排序任務q中，對數(shù)據(jù)項(1≤j≤mq)的融合排序應以多個Worker 對數(shù)據(jù)項的排序得分進行加權(quán)考慮，從而得到更確定的排序結(jié)果。因此數(shù)據(jù)項融合排序得分可表示為

以所有任務匯聚結(jié)果π={πq|1≤q≤|Q|}的平均精度均值（MAP,mean average precision）性能最優(yōu)原則進行融合排序優(yōu)化，建立目標優(yōu)化函數(shù)為

其中，X=[x1,x2,…,xm]T表示各個Worker 的權(quán)重向量；D={τi|i∈[1,m]}表示各個Worker 的提交結(jié)果集合，Dq表示所有Worker 第q個子任務的提交結(jié)果集合，rk(X,Dq,t)函數(shù)返回匯聚結(jié)果排序為t的數(shù)據(jù)項，匯聚結(jié)果排序以式(1)由X對Dq得分加權(quán)融合得到；ldt表示數(shù)據(jù)項dt標注得分，正確為1，否則為0；I{·}表示指示函數(shù)，I{true}=1，I{false}=0；M q表示任務q匯聚結(jié)果中相關(guān)數(shù)據(jù)項總數(shù)，mq表示該任務匯聚結(jié)果數(shù)據(jù)項總數(shù)，|Q|表示子任務q的數(shù)量。

式(2)的任務是找到權(quán)重向量X*使匯聚結(jié)果π的MAP 性能最優(yōu)，由于π根據(jù)權(quán)重向量X加權(quán)得分降序排序，而優(yōu)化目標使用π中數(shù)據(jù)項的位置信息，因此該優(yōu)化函數(shù)是一個非凸、非線性、多元優(yōu)化問題，無法直接對X求導，也不能使用基于梯度下降的相關(guān)算法求最優(yōu)值，因此，采用基于差分進化算法（DE,differential evolution）和Top-k排序的結(jié)果匯聚算法計算式(2)的最優(yōu)值，將優(yōu)化目標映射為DE 算法的適應度函數(shù)f(X)的最大值，即

其中，mq的取值需依據(jù)Top-k中的k值設定。利用DE 良好的尋優(yōu)性能求解最優(yōu)權(quán)重向量X*和最優(yōu)匯聚結(jié)果π。

利用上述模型以及已有m個Worker 在|Q|個任務的提交結(jié)果，按照式(2)的優(yōu)化模型訓練出各個Worker 的權(quán)重，根據(jù)式(1)得分降序排序獲得匯聚結(jié)果?；贒E 和Top-k排序的結(jié)果匯聚框架如圖1所示。請求者將訓練排序任務嵌入真實排序任務發(fā)布到眾包平臺，平臺將任務分配給多個Worker 獨立完成，Worker 努力工作后向平臺提交結(jié)果。平臺收到所有提交結(jié)果后通過訓練任務學習優(yōu)化的Worker 權(quán)重向量X，將X用于真實任務的結(jié)果匯聚，得到優(yōu)化的匯聚結(jié)果。平臺向請求者提交匯聚結(jié)果后，請求者向各個Worker 支付相應報酬。

圖1 基于DE 和Top-k排序的結(jié)果匯聚框架

4 算法設計

訓練任務中使用差分進化算法基于Top-k排序相比全排序進行Worker 權(quán)重學習優(yōu)點明顯，其潛在假設是：1) Top-k排序上的訓練和全排序上的訓練一樣好；2) Top-k排序上的運行速度相比全排序上的運行速度有顯著提高。因此，為了驗證假設的正確性，對Top-k排序和全排序的基于差分進化的結(jié)果匯聚算法進行理論和實驗分析。在分析之前，首先介紹基于Worker 權(quán)重差分進化與Top-k排序的結(jié)果匯聚算法。

DE 是一種基于向量的適者生存、優(yōu)勝劣汰算法[30]，由NP（種群規(guī)模）個m（參與匯聚的Worker人數(shù)）維參數(shù)個體X（權(quán)重向量）在搜索空間進行并行搜索，基本操作包括變異、交叉和選擇。假設工作者wt(1≤t≤m)的提交結(jié)果為τ t，則τ t的Top-k排序表示為=?；赪orker 權(quán)重差分進化和Top-k排序的結(jié)果匯聚算法（簡稱DE-k算法）如算法1 所示。

算法1DE-k算法

算法種群初始化操作中，種群個體Xi,g在可行解空間內(nèi)隨機取值，由于LC 算法賦給各個Worker的權(quán)重區(qū)間為[0,1]，且參與匯聚的所有Worker 的權(quán)重和為1，因此各Worker 的權(quán)重初始取值為

其中，xi,j表示個體Xi,g中第j個Worker 的權(quán)重，rand()函數(shù)返回[0,1]的隨機數(shù)。步驟1)～步驟5)根據(jù)隨機生成的初始種群進行結(jié)果匯聚，生成最優(yōu)權(quán)重向量初值。步驟8)～步驟15)對上一代種群中的每個個體執(zhí)行差分變異和交叉操作。步驟16)為選擇操作，選擇原個體向量Xi,g和實驗個體向量Ui,g+1中適應度值大的個體進入下一代種群，從而保證經(jīng)過一次迭代后種群總體性能得到提升。為了保證解的有效性，即在進化過程中保證每個個體中的元素滿足。步驟 17)對Xi,g+1中元素使用Sum-to-1[31]算法進行歸一化處理，即

步驟18)更新最優(yōu)權(quán)重向量X*。步驟21)利用最優(yōu)權(quán)重向量X*使用LC 算法得到最優(yōu)匯聚結(jié)果。

5 性能定性分析

5.1 匯聚結(jié)果性能分析

Top-k學習在信息檢索、信息過濾、物聯(lián)網(wǎng)、信息安全、眾包[32]等領(lǐng)域均有廣泛的應用。文獻[33]從理論和實驗2 個方面驗證基于Top-k排序能夠獲得和全排序同樣的訓練效果，并指出隨著k的增長，測試算法的性能迅速增加到一個穩(wěn)定的值，例如，當k=10 時，Ranking SVM、RankNet 和ListMLE 這3 種算法性能達到穩(wěn)定；當k=20 時，RankBoost 性能達到穩(wěn)定。

文獻[10]通過實驗表明，Top-k包含了用戶最關(guān)注的信息，僅用Top-k排序作為基于遺傳算法的權(quán)重學習的訓練集合，與全排序作為訓練集合相比性能并沒有顯著降低。此外，Pal 等[34]發(fā)現(xiàn)，如果每個任務僅選擇Top-k數(shù)據(jù)項作為實現(xiàn)TREC 評價池的依據(jù)，那么評估的質(zhì)量不會受到影響，即排在Top-k的數(shù)據(jù)項含有豐富的信息，較好地代表了長列表形式結(jié)果的性能。當使用MAP 等位置相關(guān)的評價指標進行評估時，這一點會更加突出，并且，MAP 仍然是評價排序問題中重要的性能指標。

LC 算法按各個Worker 提交結(jié)果的重要性賦予該Worker 相應的權(quán)重，并未更合理地考慮各個權(quán)重的進一步優(yōu)化。所提模型考慮Worker 完成排序任務存在不確定性和差異性問題，以目標函數(shù)和約束條件中Worker 完成任務的不確定性和差異性影響為基礎，建立基于DE 算法和Top-k的Worker 權(quán)重優(yōu)化模型。該模型綜合權(quán)衡各個Worker 的提交結(jié)果，利用DE-k算法迭代求解，確定各個Worker的優(yōu)化權(quán)重，提高匯聚結(jié)果的性能，使融合結(jié)果MAP 性能最優(yōu)，因此DE-k算法求解后確定的優(yōu)化權(quán)重向量能達到優(yōu)化的匯聚結(jié)果。

綜上所述，通過Top-k排序包含的豐富信息和DE 算法良好的尋優(yōu)性能，DE-k算法可實現(xiàn)優(yōu)化的匯聚結(jié)果性能。

5.2 時間耗費與匯聚性能權(quán)衡分析

基于DE-k的結(jié)果匯聚算法中，用m表示參與結(jié)果匯聚的Worker 人數(shù)，k表示提交結(jié)果列表的長度，NP 表示種群規(guī)模，G表示迭代次數(shù)。該算法的時間復雜度為O(mkNPG)，其與變量m、k、NP、G都成正比關(guān)系。因此，降低m、k、NP、G能夠降低結(jié)果匯聚的運行時間，但是參與匯聚的Worker 人數(shù)m和種群規(guī)模NP 選定之后不再發(fā)生變化，一般采用對DE 算法進行剪枝和降低G的迭代次數(shù)來減少結(jié)果匯聚的運行時間，而忽略了降低k減少權(quán)重向量的學習時間。全排序優(yōu)化將花費大量的訓練時間，而基于Top-k選擇適當?shù)膋可加快速度。例如，Worker 提交結(jié)果τ的長度為1 000，取k=10 參與權(quán)重的訓練，則理論上運行速度提升約1 000/10=100 倍，而匯聚結(jié)果性能接近高性能；若原提交結(jié)果列表越長，則結(jié)果匯聚運行時間降低越多，即DE-k算法可提升結(jié)果匯聚速度。

5.1節(jié)和5.2節(jié)的定性分析證明了DE-k算法在獲得優(yōu)化的匯聚結(jié)果性能的同時可提升結(jié)果匯聚的速度。

6 實驗結(jié)果分析

6.1 數(shù)據(jù)集及對比算法

實驗數(shù)據(jù)集為TREC-10 和TREC-11 的Routing filtering Task 的提交結(jié)果集。TREC-10 Routing filtering（簡稱TREC-10）共有84 個Topic。TREC-11 Routing filtering 共有100 個Topic（前50 個和后50個Topic），分別由專業(yè)和非專業(yè)評估人員評估，為了更準確地描述匯聚后結(jié)果的性能，將該結(jié)果集分成2 個結(jié)果集，標記為TREC-11A 和TREC-11B，每個結(jié)果集分別有50 個Topic。

仿真數(shù)據(jù)集包括TREC-10 的13 個提交結(jié)果和TREC-11 的8 個提交結(jié)果。詳細信息如表1～表3所示，按照提交結(jié)果的MAP 值降序排列。評價指標為MAP、P@10 和召回率（RP,recall precision）。

表1 TREC-11A 提交結(jié)果性能

表2 TREC-11B 提交結(jié)果性能

表3 TREC-10 提交結(jié)果性能

對比算法為CombSUM[14]、CombMNZ[14]、基于DE 的結(jié)果匯聚算法[11]、基于粒子群優(yōu)化的結(jié)果匯聚算法、基于粒子群優(yōu)化和Top-k排序的結(jié)果匯聚算法、基于遺傳算法的結(jié)果匯聚算法[10]、基于遺傳算法和Top-k排序的結(jié)果匯聚算法[10]。

6.2 實驗結(jié)果和分析

下面，分別在 TREC-11A、TREC-11B 和TREC-10 數(shù)據(jù)集對不同算法的匯聚結(jié)果進行分析和比較，并從3 個方面驗證所提算法在數(shù)據(jù)集上綜合性能最優(yōu)：相同迭代次數(shù)下不同算法結(jié)果匯聚的性能和運行時間的分析與對比、不同迭代次數(shù)下不同算法結(jié)果匯聚性能和運行時間的分析與對比，以及高性能系統(tǒng)的比較。

6.2.1 相同迭代次數(shù)下不同算法結(jié)果匯聚的性能和運行時間的分析與對比

本節(jié)實驗中，訓練在每個子任務的提交結(jié)果Top-k分別為10、25、50、100 和1 000（全排序）處進行，而測試在匯聚結(jié)果排序深度為1 000（全排序）處進行。使用5 折交叉驗證，迭代次數(shù)都為200。PSO-k和GA-k（k∈{10,25,50,100}）分別表示使用基于粒子群優(yōu)化算法和Top-k排序的結(jié)果匯聚算法以及基于遺傳算法和Top-k排序的結(jié)果匯聚算法。DE、PSO 和GA 表示使用提交結(jié)果的全排序作為訓練集，分別基于差分進化算法、粒子群優(yōu)化算法和遺傳算法的結(jié)果匯聚算法。BR 表示所有Worker 中MAP 性能最優(yōu)的提交結(jié)果。CombSUM和 CombMNZ 分別表示使用 CombSUM 和CombMNZ 算法進行結(jié)果匯聚。除了BR、CombSUM和CombMNZ，表4 中的數(shù)據(jù)都是8 次單獨實驗結(jié)果的平均值，其中加粗數(shù)據(jù)表示該列最優(yōu)的3 個值。

表4 數(shù)據(jù)表明，以MAP 為性能評價指標，所有結(jié)果匯聚算法的性能都優(yōu)于最優(yōu)Worker 的提交結(jié)果（BR）；DE-k和PSO-k性能相似，優(yōu)于GA、GA-k、CombMNZ、CombSUM；DE-k、PSO-k和GA-k算法分別與DE、PSO 和GA 算法相比，性能損失分別為[0.98%,4.01%]、[0.15%,3.42%]和[0,9.65%]，這些數(shù)據(jù)表明，基于Top-k的結(jié)果匯聚相比全排序性能損失不明顯；DE-k性能優(yōu)于PSO-k、GA-k，具有較好的穩(wěn)定性，且在其他性能指標P@10 和RP 下也具有上述相似的結(jié)論。

運行時間包括數(shù)據(jù)裝載、權(quán)重學習和結(jié)果匯聚的運行時間。表5 中數(shù)據(jù)為表4 中不同算法對應的運行時間。以運行時間為評價指標，全排序下，DE、PSO 和GA 完成一次結(jié)果匯聚至少需要3 h 以上，且數(shù)據(jù)集越大，運行時間越長，不能滿足實時結(jié)果匯聚的要求；DE 算法和GA 算法運行時間相似，遠低于PSO 算法的運行時間；CombSUM 算法和CombMNZ 算法不需要權(quán)重學習，運行時間最短。當k=10 時，在TREC11-A 和TREC11-B 數(shù)據(jù)集中，DE-10、PSO-10 和GA-10 在51～64 s 內(nèi)完成結(jié)果匯聚，相比全排序速度提升191～380倍；在TREC-10數(shù)據(jù)集中，3 種算法分別在16.4 min、19.7 min 和17.6 min 完成結(jié)果匯聚，相比全排序速度分別提升20 倍、38 倍和18 倍，偏離預計的100 倍左右（1 000/10）。通過對CombSUM 和CombMNZ 算法運行時間分析發(fā)現(xiàn)，這2 種算法的運行時間分別是3.1 min 和6.5 min，原因在于較大的數(shù)據(jù)集數(shù)據(jù)裝載耗費時間較多。當k分別為25、50 和100 時，具有相似的結(jié)論。實驗結(jié)果表明，DE-k運行時間相比PSO-k、GA-k運行時間少；隨著k值的減小，運行時間顯著減少，當k=10 時，DE-10 的運行時間在3 個數(shù)據(jù)集上相比全排序分別降低了98.6%、99.6%、95%，大幅降低了運行時間。

上述實驗結(jié)果表明，基于Top-k排序的優(yōu)化模型求解算法，在合適的k值下可快速得到性能好的匯聚結(jié)果，但是性能略有損失，原因在于使用較少的基本事實進行訓練評估。其中，DE-k算法從性能和運行時間兩方面在3 個數(shù)據(jù)集上具有顯著的優(yōu)勢，綜合性能最優(yōu)。

表4 匯聚結(jié)果的性能

6.2.2 不同迭代次數(shù)下不同算法結(jié)果匯聚的性能和運行時間的分析與對比

表4 和表5 中數(shù)據(jù)表明，基于Top-k排序是加快結(jié)果匯聚運行時間的有效算法，但是該算法的運行時間仍遠高于不需要權(quán)重訓練的CombSUM 和CombMNZ 算法的運行時間。

表5 結(jié)果匯聚的運行時間

圖2～圖4 和表6 中數(shù)據(jù)都是采用5 折交叉驗證、8 次實驗的平均值，迭代次數(shù)分別為25、50、100、150 和200，觀察迭代次數(shù)對不種算法的匯聚結(jié)果的性能和運行時間的影響。

圖2 TREC-11A 中不同算法在不同迭代次數(shù)下匯聚結(jié)果性能

圖2～圖4 表明，①不同迭代次數(shù)下，以MAP為性能評價指標，DE、PSO、DE-10 和PSO-10 始終優(yōu)于GA、GA-10、BR、CombSUM 和CombMNZ；DE-10 和DE 穩(wěn)定性最好，隨著迭代次數(shù)的增加，性能越來越好；當?shù)螖?shù)達到100 時，DE 超過所有算法的性能，DE-10 優(yōu)于PSO-10、GA-10、BR、CombSUM 和CombMNZ。②不同算法的性能折線波動不明顯，說明迭代次數(shù)從200 次減少到25 次的過程中，性能變化不大，而DE-10 變化最??；DE-10 在3 個數(shù)據(jù)集、迭代次數(shù)為25 次的匯聚結(jié)果的性能分別是200 次迭代匯聚結(jié)果性能的99.98%、99.93%和99.33%。其他算法也具有相似的結(jié)論。上述結(jié)果表明，隨著迭代次數(shù)的減少，DE-10 的性能下降不顯著。

圖3 TREC-11B 中不同算法在不同迭代次數(shù)下匯聚結(jié)果性能

圖4 TREC-10 中不同算法在不同迭代次數(shù)下匯聚結(jié)果性能

表6 數(shù)據(jù)表明，所有算法的運行時間和迭代次數(shù)呈線性關(guān)系，運行時間隨著迭代次數(shù)的減少而線性減少。基于Top-k的DE-10、PSO-10 和GA-10進行 25 次迭代的運行時間在 TREC-11A 和TREC-11B 數(shù)據(jù)集中為9～12 s，在TREC-10 數(shù)據(jù)集中為9.6～12 min，相比200 次迭代的運行時間得到顯著下降，滿足任務結(jié)果匯聚實時性的要求。

表6 不同迭代次數(shù)下不同算法結(jié)果匯聚的運行時間

綜上所述，DE-10 通過降低迭代次數(shù)，以性能輕微損失為代價，顯著降低運行時間。相比PSO-10和GA-10，DE-10 在保證高質(zhì)量的匯聚結(jié)果的前提下達到了實時結(jié)果匯聚的要求。

6.2.3 和高質(zhì)量提交結(jié)果的性能分析與對比

自2002 年TREC-11 會議以來，信息過濾技術(shù)飛速發(fā)展，目前查到的最新關(guān)于使用TREC-11 數(shù)據(jù)集進行實驗的文獻是2015 年Yang 等[35]發(fā)表的。該文獻使用最大匹配模式主題模型MPBTM 大幅提高系統(tǒng)的MAP 性能。將MPBTM 作為高質(zhì)量專家提交結(jié)果，并與本文算法進行對比，如圖5 所示。

圖5 高性能系統(tǒng)和文中算法性能對比

以MAP 為性能評價指標，MPBTM 的性能是0.478，優(yōu)于BR 的0.369，相比BR 提高29.54%，也優(yōu)于CombSUM、CombMNZ、GA、GA-10 和PSO-10 的性能，低于DE 和PSO 的性能，略高于DE-10 的性能，即DE-10 相比MPBTM 性能下降不顯著。但是DE 和PSO 耗時過長，而基于Top-k訓練的DE-10 卻能夠?qū)崿F(xiàn)實時結(jié)果匯聚，即通過匯聚多個低質(zhì)量的提交結(jié)果能夠達到高質(zhì)量專家提交結(jié)果的性能。

綜上，本節(jié)驗證了DE-k能夠?qū)崿F(xiàn)對多個低質(zhì)量提交結(jié)果進行結(jié)果匯聚得到高質(zhì)量的提交結(jié)果，同時滿足實時性要求，相比其他算法，綜合性能最優(yōu)。

7 結(jié)束語

本文針對眾包Worker 完成任務存在一定的不確定性和差異性，并考慮在提升結(jié)果匯聚質(zhì)量的同時又具有較快的匯聚速度，提出了基于Worker 權(quán)重的差分進化和Top-k排序的結(jié)果匯聚算法。該算法首先對訓練任務所有結(jié)交結(jié)果的Top-k排序通過基于差分進化算法的優(yōu)化模型學習Worker 優(yōu)化的權(quán)重向量，然后基于優(yōu)化的權(quán)重向量使用LC 算法對真實任務進行結(jié)果匯聚。該算法在權(quán)重學習階段，僅在信息足夠豐富且更確定的Top-k數(shù)據(jù)項集合中進行，相比全排序，可以減少訓練噪聲，大幅減少運算量，提升權(quán)重學習的速度。結(jié)果匯聚階段利用優(yōu)化的權(quán)重向量進行加權(quán)匯聚，可避免Worker的差異性而提升結(jié)果匯聚質(zhì)量。所提算法在獲得優(yōu)化的匯聚結(jié)果性能的同時，能夠提升結(jié)果匯聚速度。定性分析證明了所提算法的正確性，仿真實驗結(jié)果也驗證了所提算法效果，與相關(guān)算法對比，所提算法的綜合性能最優(yōu)。