基于Worker权重差分进化与Top-k排序的结果汇聚算法

doi:10.11959/j.issn.1000-436x.2021010

摘要/Abstract

摘要：

针对众包结果汇聚中最优排序结果选取的时效性问题，提出了 Worker 权重的高效快速汇聚算法。其中Worker权重的差分进化算法重点考虑众包Worker完成排序任务存在的差异性问题，基于目标函数和约束条件中Worker完成任务的不确定性和差异性影响，建立基于差分进化算法的Worker权重优化模型，获取多数据项场景下候选结果最优权重，实现Worker权重与任务对结果性能需求匹配的最大化；提出基于Top-k排序的优化模型求解算法，针对多数据项场景下候选结果的Top-k排序选取，在合适的k值下可快速求解上述模型，获得各Worker的优化权重。所提出的基于优化的 Worker 权重可实现结果汇聚的匹配性与匹配速度优化，即在提升结果汇聚速度的同时，具有优化的汇聚结果性能。定性分析证明了算法的正确性，仿真实验结果也验证了算法的效果，与相关算法对比，所提算法的综合性能最优。

关键词: 众包, 结果汇聚, 差分进化算法, 排序学习

Abstract:

To solve the problem of quickly obtaining the optimal ranking result in the crowdsourcing result aggregation, an efficient and effective aggregation algorithm of Worker’s weight was proposed.The Worker’s weight optimization model based on differential evolution algorithm focused on the uncertainties and differences of Workers completing ranking tasks, the uncertainties and differences were reflected in the objective function and constraint conditions of the model.This model obtained the optimal weight of candidate results, and maximized the matching between Worker’s weight and result performance.Then, the optimization model solving method based on Top-k ranking was proposed to quickly obtain the optimal Worker’s weight with the appropriate k value for specific multi-data items ranking scenario.The optimization of Worker’s weight could realize optimized performance and speed of the result aggregation.The correctness of the algorithm is verified by qualitative analysis, the effectiveness and efficiency of the algorithm is verified by the simulation results, and the comparison with the relevant algorithms shows the optimal comprehensive performance of the algorithm.

Key words: crowdsourcing, result aggregation, differential evolution algorithm, learning to rank

中图分类号:

TP393

邢玉萍, 詹永照. 基于Worker权重差分进化与Top-k排序的结果汇聚算法[J]. 通信学报, 2021, 42(1): 27-36.

Yuping XING, Yongzhao ZHAN. Result aggregation algorithm based on differential evolution and Top-k ranking in learning Worker’s weight[J]. Journal on Communications, 2021, 42(1): 27-36.

图/表 11

图1

表1

TREC-11A提交结果性能"

提交结果名称	MAP	P@10	RP
Iritsigr	$0 . 369$	0.626	$0 . 4122$
msPUMb	0.355	$0 . 64$	0.374 8
apl11Frm	0.33	0.594	0.353 7
ICTRouFT11Ub	0.25	0.526	0.302
ICTRouFT11Ua	0.243	0.522	0.294
msPUMs	0.239	0.438	0.263 9
Visa1T11	0.236	0.514	0.280 1
apl11Frsvm	0.218	0.462	0.255 6

表1

表2

TREC-11B提交结果性能"

提交结果名称	MAP	P@10	RP
msPUMb	$0 . 045$	0.122	$0 . 0804$
iritsigr	0.044	$0 . 124$	0.071 7
apl11Frsvm	0.043	0.12	0.077
apl11Frm	0.042	0.102	0.076 5
Visa1T11	0.028	0.098	0.051 5
ICTRouFT11Ub	0.025	0.074	0.047 2
ICTRouFT11Ua	0.024	0.072	0.047 2
msPUMs	0.006	0.018	0.011 3

表2

表3

TREC-10提交结果性能"

提交结果名称	MAP	P@10	RP
DLewis01rFa	$0 . 1682$	0.875	$0 . 1985$
DLewis01rUa	0.166 3	0.871 4	0.197 4
KUNr2	0.136 9	$0 . 8786$	0.166 2
KUNr1	0.135 6	0.809 5	0.171 1
apl10frn	0.121	0.833 3	0.156 1
clT10rtb	0.104 8	0.772 6	0.144 4
oraRO082801	0.104	0.785 7	0.143 1
apl10frs	0.103 8	0.761 9	0.141
mer10r1	0.092	0.727 4	0.126 3
clT10rta	0.077 8	0.719	0.117
jscbtafr2	0.046 6	0.609 5	0.083 1
jscbtafr1	0.042	0.654 8	0.076 5
VisaSent1T10	0.011 8	0.377 4	0.0174

表3

表4

汇聚结果的性能"

算法		TREC-11A			TREC-11B			TREC-10
算法	MAP	P@10	RP	MAP	P@10	RP	MAP	P@10	RP
BR	0.369	0.626	0.412 2	0.045	0.122	0.080 4	0.168 2	0.875	0.198 5
CombSUM	0.421 2	0.378	0.435 5	0.056 1	0.156	0.094 1	0.265 5	0.864 3	0.192 8
CombMNZ	0.425 4	0.373	0.436 7	0.058 9	0.154	0.097 9	0.277 8	0.865 5	0.198 9
GA	0.462 6	0.7	0.463	0.059 7	0.146 7	0.094 5	0.303 9	0.877 4	0.212 3
GA-100	0.460 6	0.701	0.461 4	0.057 3	0.144	0.092 8	0.302 2	0.873 8	0.211 9
GA-50	0.456 6	0.687 2	0.458	0.056 6	0.144 6	0.090 7	0.297 4	0.869	0.209 1
GA-25	0.462 6	0.698 6	0.462 5	0.055 2	0.145 8	0.088 6	0.300 6	0.882 4	0.210 5
GA-10	0.455 5	0.694 9	0.456 9	0.054 4	0.135	0.085 7	0.294 3	0.872 6	0.206 8
PSO	$0 . 4803$	$0 . 722$	$0 . 4749$	$0 . 0654$	0.168	$0 . 1031$	$0 . 3103$	$0 . 8851$	$0 . 2168$
PSO-100	$0 . 4791$	0.707	$0 . 4751$	0.063 7	0.172	$0 . 1021$	0.302 3	0.878 9	0.211 8
PSO-50	0.472 4	0.696	0.473 3	$0 . 0653$	0.164	0.100 6	0.306 3	0.882	0.214 3
PSO-25	0.476 2	0.704	0.473 7	0.064 9	0.162	0.101 2	0.302 7	0.876 8	0.211 3
PSO-10	0.469 9	0.699 4	0.471 5	0.063 3	$0 . 176$	0.097 2	0.3	0.870 9	0.209 8
DE	$0 . 4819$	$0 . 7207$	0.474 8	$0 . 0663$	$0 . 1733$	0.101 5	$0 . 3122$	$0 . 8861$	$0 . 2178$
DE-100	0.477 1	0.707 7	0.474	0.063 8	0.166 5	$0 . 1025$	$0 . 3092$	$0 . 8851$	$0 . 2161$
DE-50	0.474 5	0.705	0.474	0.064 4	0.164	0.099 4	0.307 6	0.876 2	0.215 1
DE-25	0.476	0.706	$0 . 4755$	0.064 9	0.164	0.100 4	0.306 6	0.879 5	0.214 7
DE-10	0.472 4	$0 . 7112$	0.474 4	0.063 7	$0 . 1727$	0.095 7	0.306 3	0.883 7	0.214 3

表4

表5

结果汇聚的运行时间"

算法	TREC-11A	TREC-11B	TREC-10
CombSUM	1.14 s	1.49 s	3.1 min
CombMNZ	2.04 s	3.3 s	6.5 min
GA	3.1 h	3.53 h	5.35 min
GA-100	854 s	866 s	52.8 min
GA-50	380 s	400 s	35.2 min
GA-25	158 s	189 s	28 min
GA-10	$58$ s	$58$ s	$17 . 6$ min
PSO	3.4 h	6.75 h	12.4 h
PSO-100	717 s	796 s	41.6 min
PSO-50	322 s	370 s	35.1 min
PSO-25	170 s	172 s	19.9 min
PSO-10	$53$ s	$64$ s	$19 . 7$ min
DE	3h	4.02 h	5.51 h
DE-100	678 s	862 s	37.9 min
DE-50	317 s	395 s	25.8 min
DE-25	147 s	184 s	19.8 min
DE-10	$51$ s	$63$ s	$16 . 4$ min

表5

图2

图3

图4

表6

不同迭代次数下不同算法结果汇聚的运行时间"

算法	TREC-11A					TREC-11B					TREC-10
算法	25	50	100	150	200	25	50	100	150	200	25	50	100	150	200
DE	27.8 min	51.5 min	1.54 h	2.27 h	3.02 h	30.7 min	58.2 min	1.93 h	3.01 h	4.02 h	56 min	1.56 h	2.83 h	4.08 h	5.35 h
PSO	28.3 min	57.9 min	1.96 h	2.76 h	3.45 h	47.3 min	1.58 h	3.22 h	5.18 h	6.75 h	1.58 h	2.93 h	6.02 h	9.21 h	12.4 h
GA	30.3 h	53.3 min	1.65 h	2.39 h	3.08 h	30.4 min	57 min	1.78 h	2.69 h	3.53 h	55.7 min	1.57 h	2.8 h	4.08 h	5.49 h
DE-10	10 s	17 s	29 s	$40$ s	$51$ s	12 s	$18$ s	$34$ s	$48$ s	63 s	12 min	13.6 min	16.9 min	19.1 min	19.6 min
PSO-10	$9$ s	$16$ s	$28$ s	43 s	53 s	12 s	21 s	36 s	49 s	62 s	11.7 min	11.7 min	13.3 min	16.1 min	19.9 min
GA-10	10 s	17 s	31 s	44 s	58 s	$10$ s	19 s	$34$ s	50 s	$62$ s	9.6 min	$10 . 5$ min	$13$ min	$15 . 5$ min	$17 . 6$ min

表6

图5

参考文献 35

[1]	JIN Y , CARMAN M , ZHU Y ,et al. A technical survey on statistical modelling and design methods for crowdsourcing quality control[J]. Artificial Intelligence, 2020,287: 103351.
[2]	WU O , YOU Q , XIA F ,et al. Listwise learning to rank from crowds[J]. ACM Transactions on Knowledge Discovery From Data, 2016,11(1): 1-39.
[3]	CHANG Y , CHEN J , CHO M H ,et al. Clustering from multiple uncertain experts[C]// Proceedings of the 34th International Conference on Machine Learning. New York:ACM Press, 2017: 674-683.
[4]	LI G , CHAI C , FAN J ,et al. CDB:a crowd-powered database system[J]. Proceedings of the VLDB Endowment, 2018,11(12): 1926-1929.
[5]	PARAMESWARAN A , BOYD S , GARCIA-MOLINA H ,et al. Optimal crowd-powered rating and filtering algorithms[J]. Proceedings of the VLDB Endowment, 2014,7(9): 685-696.
[6]	WANG S G , XIAO X K , LEE C H . Crowd-based deduplication:an adaptive approach[C]// International Conference on Management of Data. New York:ACM Press, 2015: 1263-1277.
[7]	LI K Y , ZHANG X H , LI G L ,et al. A rating-ranking method for crowdsourced top-k computation[C]// International Conference on Management of Data. New York:ACM Press, 2018: 975-990.
[8]	VUURENS J , VRIES A P , EICKHOFF C . How much spam can you take? An analysis of crowdsourcing results to increase accuracy[C]// SIGIR 2011 Workshop on Crowdsourcing for Information Retrieval. New York:ACM Press, 2011: 21-26.
[9]	ZHANG Y , DER SCHAAR M V . Reputation-based incentive protocols in crowdsourcing applications[C]// 2012 Proceedings IEEE INFOCOM. Piscataway:IEEE Press, 2012: 2140-2148.
[10]	GHOSH K , PARUI S K , MAJUMDER P . Learning combination weights in data fusion using genetic algorithms[J]. Information Processing ＆ Management, 2015,51(3): 306-328.
[11]	XU C L , HUANG C L , WU S L . Differential evolution-based fusion for results diversification of Web search[C]// International Conference on Web-age Information Management. Berlin:Springer, 2016: 429-440.
[12]	WANG W , ZHANG M . Tensor deep learning model for heterogeneous data fusion in Internet of things[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2020,4(1): 32-41.
[13]	CHATTERJEE S , MUKHOPADHYAY A , BHATTACHARYYA M . A weighted rank aggregation approach towards crowd opinion analysis[J]. Knowledge-Based Systems, 2018(149): 47-60.
[14]	THOMA S , THALHAMMER A , HARTH A ,et al. FusE:entity-centric data fusion on linked data[J]. ACM Transactions on the Web, 2019,13(2): 1-36.
[15]	FOX E A , SHAW J A . Combination of multiple searches[C]// The 2nd Text Retrieval Conference.[S.n.:s.l.], 1994: 243-252.
[16]	VOGT C C , COTTRELL G W . Fusion via a linear combination of scores[J]. Information Retrieval, 1999,1(3): 151-173.
[17]	THOMPSON P , . Description of the PRC CEO algorithms for TREC[C]// The First Text Retrieval Conference.[S.n.:s.l.], 1992: 337-342.
[18]	BARTELL B T , COTTRELL G W , BELEW R K . Automatic combination of multiple ranked retrieval systems[C]// 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,New York:ACM Press, 1994: 173-181.
[19]	VOGT C C , COTTRELL G W . Predicting the performance of linearly combined IR systems[C]// 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York:ACM Press, 1998: 190-196.
[20]	WU S L . Linear combination of component results in information retrieval[J]. Data and Knowledge Engineering, 2012,71(1): 114-126.
[21]	LILLIS D , TOOLAN F , COLLIER R ,et al. Probfuse:a probabilistic approach to data fusion[C]// 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York:ACM Press, 2006: 139-146.
[22]	WU S L , BI Y X , ZENG X Q ,et al. Assigning appropriate weights for the linear combination data fusion method in information retrieval[J]. Information Processing and Management, 2009,45(4): 413-426.
[23]	SHELDON D , SHOKOUHI M , SZUMMER M ,et al. Lambdamerge:merging the results of query reformulations[C]// The Fourth ACM International Conference on Web Search and Data Mining. New York:ACM Press, 2011: 795-804.
[24]	KOZOROVITSKY A K , KURLAND O . Cluster-based fusion of retrieved lists[C]// The 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York:ACM Press, 2011: 893-902.
[25]	HONG D , SI L . Mixture model with multiple centralized retrieval algorithms for result merging in federated search[C]// The 35th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York:ACM Press, 2012: 821-830.
[26]	LEE C J , AI Q Y , CROFT W B ,et al. An optimization framework for merging multiple result lists[C]// The 24th ACM International on Conference on Information and Knowledge Management, 2015: 303-312.
[27]	MOURAO A , MAGALHAES J . Low-complexity supervised rank fusion models[C]// Proceedings of the 27th ACM International Conference on Information and Knowledge Management. New York:ACM Press, 2018: 1691-1694.
[28]	LIANG S S , MARKOV I , REN Z C ,et al. Manifold learning for rank aggregation[C]// World Wide Web Conference.[S.n.:s.l.], 2018: 1735-1744.
[29]	WU S L , HUANG C L ,et al. Fusion-based methods for result diversification in Web search[J]. Information Fusion, 2019,45: 16-26.
[30]	郝晓辰, 王立元, 刘金硕 ,等. WSN中基于双群体差分进化的资源分配优化算法[J]. 通信学报, 2018,39(4): 68-75.
	HAO X C , WANG L Y , LIU J S ,et al. Resource allocation optimization algorithm based on double populations differential evolution in WSN[J]. Journal on Communications, 2018,39(4): 68-75.
[31]	MONTAGUE M , ASLAM J . Relevance score normalization for metasearch[C]// The Tenth International Conference on Information and Knowledge Management. New York:ACM Press, 2001: 427-433.
[32]	FRANKLIN M J , KOSSMANN D , KRASKA T ,et al. CrowdDB:answering queries with crowdsourcing[C]// The ACM SIGMOD International Conference on Management of Data. New York:ACM Press, 2011: 61-72.
[33]	LAN Y Y , NIU S Z , GUO J F ,et al. Is top-k sufficient for ranking?[C]// The 22nd ACM International Conference on Information ＆Knowledge Management. New York:ACM Press, 2013: 1261-1270.
[34]	PAL S , MITRA M , KAMPS J . Evaluation effort,reliability and reusability in XML retrieval[J]. Journal of the Association for Information Science and Technology, 2011,62(2): 375-394.
[35]	GAO Y , XU Y,L\| Y F . Pattern-based topics for document modelling in information filtering[J]. IEEE Transactions on Knowledge and Data Engineering, 2015,27(6): 1629-1642.