基于工人长短期时空偏好的众包任务分配
作者:
作者简介:

王府鑫(1998-), 男, 硕士, CCF学生会员, 主要研究领域为机器学习, 时空众包数据分析;王宁(1967-), 女, 博士, 教授, 博士生导师, CCF专业会员, 主要研究领域为人工智能赋能的数据管理, 大数据与群智计算, 数据挖掘;曾奇雄(1996-), 男, 博士生, 主要研究领域为数据库查询优化, 人工智能赋能的数据管理, 时空众包

通讯作者:

王宁, E-mail: nwang@bjtu.edu.cn

中图分类号:

TP311

基金项目:

国家重点研发计划(2018YFC0809800)


Long- and Short-term Spatio-temporal Preference-aware Task Assignment in Crowdsourcing
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [22]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    近年来, 随着移动设备的计算能力和感知能力的提高, 基于位置信息的时空众包应运而生, 任务分配效果的提升面临许多挑战, 其中之一便是如何给工人分配他们真正感兴趣的任务. 现有的研究方法只关注工人的时间偏好而忽略了空间因素对偏好的影响, 仅关注长期偏好却忽略了短期偏好, 同时面临历史数据稀疏导致的预测不准的问题. 研究基于长短期时空偏好的任务分配问题, 从长期和短期两个角度以及时间和空间两个维度全面考虑工人的偏好, 进行时空众包任务分配, 提高任务的成功分配率和完成效率. 为提升时空偏好预测的准确性, 提出分片填充的张量分解算法(SICTD)减小偏好张量的空缺值占比, 提出时空约束下的ST-HITS算法, 综合考虑工人短期活跃范围, 计算短期时空偏好. 为了在众包任务分配中最大化任务总收益和工人偏好, 设计基于时空偏好的贪心与Kuhn-Munkres (KM)算法, 优化任务分配的结果. 在真实数据集上的大量实验结果表明, 提出的分片填补张量分解算法对时间和空间偏好的RMSE预测误差较基线算法分别下降22.55%和24.17%; 在任务分配方面, 提出的基于偏好的KM算法表现出色, 对比基线算法, 在工人总收益和工人完成任务平均偏好值上分别提升40.86%和22.40%.

    Abstract:

    With the development of mobile services’ computing and sensing abilities, spatial-temporal crowdsourcing, which is based on location information, comes into being. There are many challenges to improving the performance of task assignments, one of which is how to assign workers the tasks that they are interested in. Existing research methods only focus on workers’ temporal preference but ignore the impact of spatial factors on workers’ preference, and they only focus on long-term preference but ignore workers’ short-term preference and face the problem of inaccurate predictions caused by sparse historical data. This study analyzes the task assignment problem based on long-term and short-term spatio-temporal preference. By comprehensively considering workers’ preferences from both long-term and short-term perspectives, as well as temporal and spatial dimensions, the quality of task assignment is improved in task assignment success rate and completion efficiency. In order to improve the accuracy of spatio-temporal preference prediction, the study proposes a sliced imputation-based context-aware tensor decomposition algorithm (SICTD) to reduce the proportion of missing values in preference tensors and calculates short-term spatio-temporal preference through the ST-HITS algorithm and short-term active range of workers under spatio-temporal constraints. In order to maximize the total task reward and the workers’ average preference for completing tasks, the study designs a spatio-temporal preference-aware greedy and Kuhn-Munkres (KM) algorithm to optimize the results of task assignment. Extensive experimental results on real datasets show the effectiveness of the long- and short-term spatio-temporal preference-aware task assignment framework. Compared with baselines, the RMSE prediction error of the proposed SICTD for temporal and spatial preferences is decreased by 22.55% and 24.17%, respectively. In terms of task assignment, the proposed preference-aware KM algorithm significantly outperforms the baseline algorithms, with the workers’ total reward and average preference for completing tasks averagely increased by 40.86% and 22.40%, respectively.

    参考文献
    [1] 童咏昕, 袁野, 成雨蓉, 陈雷, 王国仁. 时空众包数据管理技术研究综述. 软件学报, 2017, 28(1): 35-58. http://www.jos.org.cn/1000-9825/5140.htm
    Tong YX, Yuan Y, Cheng YR, Chen L, Wang GR. Survey on spatiotemporal crowdsourced data management techniques. Ruan Jian Xue Bao/Journal of Software, 2017, 28(1): 35–58 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5140.htm
    [2] Wang DJ, Deng SG, Xu GD. Sequence-based context-aware music recommendation. Information Retrieval Journal, 2018, 21(2): 230–252. [doi: 10.1007/s10791-017-9317-7]
    [3] Chen R, Chang YS, Hua QY, Gao QL, Ji X, Wang B. An enhanced social matrix factorization model for recommendation based on social networks using social interaction factors. Multimedia Tools and Applications, 2020, 79(19): 14147–14177. [doi: 10.1007/s11042-020-08620-3]
    [4] Ying YK, Chen L, Chen GC. A temporal-aware POI recommendation system using context-aware tensor decomposition and weighted HITS. Neurocomputing, 2017, 242: 195–205. [doi: 10.1016/j.neucom.2017.02.067]
    [5] Zhao Y, Xia JF, Liu GF, Su H, Lian DF, Shang S, Zheng K. Preference-aware task assignment in spatial crowdsourcing. Proceedings of the AAAI Conference on Artificial Intelligence, 2019, 33(1): 2629–2636. [doi: 10.1609/aaai.v33i01.33012629]
    [6] Zhao Y, Zheng K, Yin HZ, Liu GF, Fang JH, Zhou XF. Preference-aware task assignment in spatial crowdsourcing: From individuals to groups. IEEE Transactions on Knowledge and Data Engineering, 2022, 34(7): 3461–3477. [doi: 10.1109/TKDE.2020.3021028]
    [7] Li YC, Zhao Y, Zheng K. Preference-aware group task assignment in spatial crowdsourcing: A mutual information-based approach. In: Proc. of the 2021 IEEE Int’l Conf. on Data Mining (ICDM). Auckland: IEEE, 2021. 350–359.
    [8] Kazemi L, Shahabi C. GeoCrowd: Enabling query answering with spatial crowdsourcing. In: Proc. of the 20th Int’l Conf. on Advances in Geographic Information Systems. Redondo Beach: ACM, 2012. 189–198.
    [9] Ye GY, Zhao Y, Chen XH, Zheng K. Task allocation with geographic partition in spatial crowdsourcing. In: Proc. of the 30th ACM Int’l Conf. on Information & Knowledge Management. Queensland: ACM, 2021. 2404–2413.
    [10] Wang ZW, Zhao Y, Chen XH, Zheng K. Task assignment with worker churn prediction in spatial crowdsourcing. In: Proc. of the 30th ACM Int’l Conf. on Information & Knowledge Management. Queensland: ACM, 2021. 2070–2079.
    [11] Xia JF, Zhao Y, Liu GF, Xu JJ, Zhang M, Zheng K. Profit-driven task assignment in spatial crowdsourcing. In: Proc. of the 28th Int’l Joint Conf. on Artificial Intelligence. Macao: AAAI Press, 2019. 1914–1920.
    [12] Cheng P, Lian X, Chen Z, Fu R, Chen L, Han JS, Zhao JZ. Reliable diversity-based spatial crowdsourcing by moving workers. Proceedings of the VLDB Endowment, 2015, 8(10): 1022–1033. [doi: 10.14778/2794367.2794372]
    [13] Wang Y, Zhao CX, Xu SS. Method for spatial crowdsourcing task assignment based on integrating of genetic algorithm and ant colony optimization. IEEE Access, 2020, 8: 68311–68319. [doi: 10.1109/ACCESS.2020.2983744]
    [14] Zhao Y, Li Y, Wang Y, Su H, Zheng K. Destination-aware task assignment in spatial crowdsourcing. In: Proc. of the 2017 ACM on Conf. on Information and Knowledge Management. Singapore: ACM, 2017. 297–306.
    [15] Zhao Y, ZHENG K, Li Y, Su H, Liu JJ, Zhou XF. Destination-aware task assignment in spatial crowdsourcing: A worker decomposition approach. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(12): 2336–2350. [doi: 10.1109/TKDE.2019.2922604]
    [16] Cheng P, Chen L, Ye JP. Cooperation-aware task assignment in spatial crowdsourcing. In: Proc. of the 35th IEEE Int’l Conf. on Data Engineering (ICDE). Macao: IEEE, 2019. 1442–1453.
    [17] Zhao Y, Guo JN, Chen XH, Hao JY, Zhou XF, Zheng K. Coalition-based task assignment in spatial crowdsourcing. In: Proc. of the 37th IEEE Int’l Conf. on Data Engineering (ICDE). Chania: IEEE, 2021. 241–252.
    [18] Li X, Zhao Y, Zhou XF, Zheng K. Consensus-based group task assignment with social impact in spatial crowdsourcing. Data Science and Engineering, 2020, 5(4): 375–390. [doi: 10.1007/s41019-020-00142-0]
    [19] Zhou X, Liang ST, Li KL, Gao YJ, Li KQ. Bilateral preference-aware task assignment in spatial crowdsourcing. In: Proc. of the 38th IEEE Int’l Conf. on Data Engineering (ICDE). Kuala Lumpur: IEEE, 2022. 1687–1699.
    [20] FourSquare—NYC and Tokyo Check-ins. 2016. https://www.kaggle.com/datasets/chetanism/foursquare-nyc-and-tokyo-checkin-dataset
    [21] Ma YQ, Fu Y. Manifold Learning Theory and Applications. Boca Raton: CRC Press, 2012. 314.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

王府鑫,王宁,曾奇雄.基于工人长短期时空偏好的众包任务分配.软件学报,2024,35(10):4710-4728

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2022-11-23
  • 最后修改日期:2023-04-12
  • 在线发布日期: 2023-11-08
  • 出版日期: 2024-10-06
文章二维码
您是第19754450位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号