计算机应用 ›› 2018, Vol. 38 ›› Issue (2): 415-420.DOI: 10.11772/j.issn.1001-9081.2017071805

• 人工智能 • 上一篇    下一篇

时空众包环境下基于统计预测的自适应阈值算法

刘辉, 李盛恩   

  1. 山东建筑大学 计算机科学与技术学院, 济南 250101
  • 收稿日期:2017-07-21 修回日期:2017-09-08 出版日期:2018-02-10 发布日期:2018-02-10
  • 通讯作者: 刘辉
  • 作者简介:刘辉(1992-),男,山东济南人,硕士研究生,主要研究方向:Crowdsourcing、深度学习;李盛恩(1963-),男,山东蓬莱人,教授,博士,主要研究方向:数据仓库、联机分析、数据挖掘。
  • 基金资助:
    国家自然科学基金资助项目(61170052);济南市高校院所自主创新计划项目(201401211)。

Adaptive threshold algorithm based on statistical prediction under spatial crowdsourcing environment

LIU Hui, LI Sheng'en   

  1. School of Computer Science and Technology, Shandong Jianzhu University, Jinan Shandong 250101, China
  • Received:2017-07-21 Revised:2017-09-08 Online:2018-02-10 Published:2018-02-10
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61170052), the Jinan City University Institute of independent innovation project (201401211).

摘要: 针对时空众包环境下任务分配随机性过高且效用值不理想的问题,提出一种基于统计预测的自适应阈值算法。首先,实时统计众包平台中空闲的任务、工人及工作地点的数量以设置阈值;其次,通过历史数据分析将任务与工人的分布分为均衡的两个部分,并用Min-max normalization方法为每个任务匹配一个确定的工人;最后,计算匹配到的工人出现的概率,以验证任务分配的有效性。使用相同真实数据的实验结果证实,与随机阈值算法相比,基于统计预测的自适应阈值算法的效用值提升了7%;与贪心算法相比,其效用值提升了10%。实验结果表明,基于统计预测的自适应阈值算法能够减少任务分配过程中的随机性并提高效用值。

关键词: 时空众包, 在线任务分配, 阈值算法, 匹配策略, 统计预测

Abstract: Focusing on the problem that the randomness of task assignment is too high and the utility value is not ideal under the spatial crowdsourcing environment, an adaptive threshold algorithm based on statistical prediction was proposed. Firstly, the numbers of free tasks, free workers and free positions in the crowdsourcing platform in real-time was counted to set the threshold value. Secondly, according to the historical statistical analysis, the distributions of tasks and workers were divided into two balanced parts, then the Min-max normalization method was applied to match each task to a certain worker. Finally, the probability of the appearance of the matched workers was calculated to verify the effectiveness of the task distribution. The experimental results on real data show that, compared with random threshold algorithm and greedy algorithm, the utility value of the proposed algorithm was increased by 7% and 10%, respectively. Experimental result indicates that the proposed adaptive threshold algorithm can reduce the randomness and improve the utility value in the process of task assignment.

Key words: spatial crowdsourcing, online task assignment, threshold algorithm, matching strategy, statistial prediction

中图分类号: