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

Yuping XING; Yongzhao ZHAN

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

您当前的位置：

首页 >

文章列表页 >

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

Papers | 更新时间：2024-06-05

- Result aggregation algorithm based on differential evolution and Top-k ranking in learning Worker’s weight
- Journal on Communications Vol. 42, Issue 1, Pages: 27-36(2021)
- 作者机构：
  
  1. 江苏大学计算机科学与通信工程学院，江苏镇江 212013
  2. 江苏省工业网络安全技术重点实验室，江苏镇江 212013
- 作者简介：
- 基金信息：
  
  The National Key Research and Development Program of China(2017YFB1400703);The China Postdoctoral Science Foundation(2019M651738);The National Natural Science Foundation of China(61702230)
- DOI：10.11959/j.issn.1000-436x.2021010
  CLC： TP393
- Online First：2021-01，
  
  Published：25 January 2021
- 稿件说明：
移动端阅览
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.
DOI：

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. DOI： 10.11959/j.issn.1000-436x.2021010.

摘要

针对众包结果汇聚中最优排序结果选取的时效性问题，提出了 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.

关键词

Keywords

references

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

ZHANG Y , DER SCHAAR M V . Reputation-based incentive protocols in crowdsourcing applications [C ] // 2012 Proceedings IEEE INFOCOM . Piscataway:IEEE Press , 2012 : 2140 - 2148 .

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 .

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 .

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 .

CHATTERJEE S , MUKHOPADHYAY A , BHATTACHARYYA M . A weighted rank aggregation approach towards crowd opinion analysis [J ] . Knowledge-Based Systems , 2018 ( 149 ): 47 - 60 .

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 .

FOX E A , SHAW J A . Combination of multiple searches [C ] // The 2nd Text Retrieval Conference .[S.n.:s.l. ] , 1994 : 243 - 252 .

VOGT C C , COTTRELL G W . Fusion via a linear combination of scores [J ] . Information Retrieval , 1999 , 1 ( 3 ): 151 - 173 .

THOMPSON P , . Description of the PRC CEO algorithms for TREC [C ] // The First Text Retrieval Conference .[S.n.:s.l. ] , 1992 : 337 - 342 .

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 .

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 .

WU S L . Linear combination of component results in information retrieval [J ] . Data and Knowledge Engineering , 2012 , 71 ( 1 ): 114 - 126 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

WU S L , HUANG C L , et al . Fusion-based methods for result diversification in Web search [J ] . Information Fusion , 2019 , 45 : 16 - 26 .

郝晓辰 , 王立元 , 刘金硕 , 等 . 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 .

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 .

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 .

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 .

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 .

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 .

Views

1151

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Privacy-preserving task matching scheme for crowdsourcing

Maritime moving target localization method based on improved differential evolution with GNSS-based passive multistatic radar

Bayesian network structure learning algorithm based on hybrid binary salp swarm-differential evolution algorithm

Overview of detection techniques for malicious social bots

Survey on differential privacy and its progress

Related Author

FU Zhangjie

JIANG Qin

WANG Wei

DING Siyang

SONG Fuyuan

CHEN Wu

YANG Yang

MAO Yi

Related Institution

School of Computer Science, Nanjing University of Information Science & Technology

School of Information and Communications Engineering, Xi’an Jiaotong University

Key Laboratory of Maritime Intelligent Cyberspace Technology (Hohai University), Ministry of Education

Department of Land Surveying and Geo-Informatics, The Hong Kong Polytechnic University

School of Information Science and Engineering, Yanshan University

AI问答

⁰