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

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

Abstract

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

CLC Number:

TP393

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.

Figures/Tables 11

提交结果名称	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

提交结果名称	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

提交结果名称	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

算法		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

算法	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

算法	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

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

Result aggregation algorithm based on differential evolution and Top-k ranking in learning Worker’s weight

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 35

Related Articles 5

Metrics

Recommended 0

[1]	Bin LIU,Ruixing FAN,Haoran LIU,Liyue ZHANG,Haiyu WANG,Chunlan ZHANG. Bayesian network structure learning algorithm based on hybrid binary salp swarm-differential evolution algorithm [J]. Journal on Communications, 2019, 40(7): 151-161.
[2]	Feng ZENG,Runhua WANG,Jia PENG,Zhigang CHEN. Game-theoretical analysis of mobile contributors in mobile crowd sourcing network with word of mouth mode [J]. Journal on Communications, 2019, 40(3): 125-138.
[3]	Rong LIU,Bo CHEN,Ling YU,Ya-shang LIU,Si-yuan CHEN. Overview of detection techniques for malicious social bots [J]. Journal on Communications, 2017, 38(Z2): 197-210.
[4]	Zhi-qiang GAO,Yu-tao WANG. Survey on differential privacy and its progress [J]. Journal on Communications, 2017, 38(Z1): 151-155.
[5]	Zhi-kai XU,Hong-li ZHANG,Xiang-zhan YU,Zhi-gang ZHOU. Combinatorial double auction-based allocation of retrieval tasks in Internet of Things [J]. Journal on Communications, 2015, 36(12): 47-56.