Recommender Systems and Information Fusion in Spatial Crowdsourcing 公开

Garcia Ulloa Daniel Alejandro (Fall 2017)

Permanent URL: https://etd.library.emory.edu/concern/etds/q524jn78d?locale=zh
Published

Abstract

 

Spatial Crowdsourcing (SC) refers to a series of data collection mechanisms where a set of users with a sensing or computing device are asked to perform a set of tasks at different locations and times. In this work, we explore some of the challenges that arise with SC and propose some solutions. These challenges concern a proper recommendation of tasks to users in such a way that they maximize their expected utility while at the same time maximizing the probability that all the tasks are performed. The utility for the users can be based on the tasks the expected reward they are planning to obtain, and the distance to the assignments. These aspects can be predicted through tensor-factorization techniques. A high-paying assignment might be far from a user, while a low paying assignment is nearby. Depending on the users’ preference, we seek to recommend a set of tasks that maximize the user’s utility. On the other hand, we also want to maximize the sum of probabilities that the tasks are performed, considering the interdependencies between users. We define the system utility as a convex linear combination of the user and the task utility and suggest approximation methods to recommend the tasks that yield the highest system utility.

We also deal with the problem of truth inference, which focuses on integrating the responses from a mobile crowdsourcing scenario and determining the true value. Many times, the answers from a mobile crowdsourcing scenario are noisy, contradicting, or have missing values. We developed a recursive Bayesian system that updates the reputation model of the users, the probability that the users were in the correct time and location, and the probability that the events are true. We further enhanced this algorithm using a Kalman filter that predicts the true state of the event at each time-stamp using a hidden event model and which is updated with the reports from the users. Our method was compared against the naive majority voting method as well as other state-of-the-art truth inference algorithms and our method shows a considerable improvement. 

Table of Contents

Contents

1 Introduction                                                                                           1

1.1  Motivation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  1

1.2  Recommender Systems in Spatial Crowdsourcing . . . . . . . .  4

1.2.1  CurrentChallenges . . . . . . . . . . . . . . . . . . . . .  4

1.2.2  ExistingSolutionsandLimitations . . . . . . . . . . . . . . .  5

1.2.3  Frameworkofproposedsolution . . . . . . . . . . . . . . . . .  6

1.3  TruthInferenceinSpatialCrowdsourcing. . . . . . . . . . . . . . . . . . 7

1.3.1  CurrentChallenges . . . . . . . . . . . . . . . . . . . . .   8

1.3.2  ExistingSolutionsandLimitations . . . . . . . . . . . . . . .   8

1.3.3  Frameworkofproposedsolution . . . . . . . . . . . . . . . . .   8

1.4  Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  9

2 Related Work                                                                                         13

2.1  SpatialCrowdsourcing . . . . . . . . . . . . . . . . . . . . . . . . 13

     2.1.1 Classification of Tasks . . . . . . . . . . . . . . . . . . . . . 13

     2.1.2 Classification of Distribution Models . . . . . . . . . . . . . . . 16

2.2  Recommender Systems in Spatial Crowdsourcing . . . . . . . .  19

     2.2.1 Taskrecommendations . . . . . . . . . . . . . . . . . . . . .  20

     2.2.2 Taskprediction . . . . . . . . . . . . . . . . . . . . . . . . . .  21

2.3  TruthInferenceAlgorithms . . . . . . . . . . . . . . . . . . . . . . 22

               2.3.1 General Classification of Truth Inference Algorithms . .  22

               2.3.2 Truth Inference in Spatio-temporal Scenarios . . . . . . . . . 22

3  Recommender Systems in Spatial Crowdsourcing                                 25

     3.1  Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . .  25

          3.1.1  Users’pointofview . . . . . . . . . . . . . . . . . . . . . . . . . . 25

          3.1.2  Tasks’pointofview . . . . . . . . . . . . . . . . . . . . . . . . . . 26

          3.1.3  System’spointofview . . . . . . . . . . . . . . . . . . . . . . . .  27

     3.2  Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

          3.2.1  IndividualUtilityFunction . . . . . . . . . . . . . . . . . . . . . . 29

          3.2.2  Independent probability of performing a task . . . . . . . . . . . 30

          3.2.3  Dependent probability of performing a task . . . . . . . . . . . . . 31

          3.2.4  Probability that a task is performed. . . . . . . . . . . . . . . . . . . . . 32

     3.3  Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32

          3.3.1 Depth First Search Algorithm . . . . . . . . . . . . . . . . . . . . .32

          3.3.2 GreedyAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33

          3.3.3 ProgressiveAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 34

          3.3.4 HybridApproaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

     3.4  Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

          3.4.1 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

          3.4.2 Simulation experiments . . . . . . . . . . . . . . . . . . . . . . .  42

          3.4.3 Case study. . .  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43

     3.5  Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  52

          3.5.1 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . .  52

          3.5.2 Case Study Results . . . . . . . . . . . . . . . . . . . . . . . . . . . .  53

4  Location and Time-aware Truth-Inference with Bayesian Filtering             63

     4.1  Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

          4.1.1 Proposed Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

     4.2  Truth-Inference Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . .  70

          4.2.1 Bayesian Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

          4.2.2 Kalman Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

     4.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  80

          4.3.1 Compared Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

          4.3.2 Real-World Case Study. . . . . . . . . . . . . . . . . . . . . . . . . . . 82

          4.3.3 Evaluation metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  84

          4.3.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

          4.3.5 Simulation Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . .  85

5 Conclusion 93

     5.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  93

     5.2 Recommender Systems in Spatial Crowdsourcing . . . . . . . . . . . . . . . . 94

     5.3 Truth Inference in Spatial Crowdsourcing. . . . . . . . . . . . . . . . . . . . . . . . . 96

     5.4 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  97

Appendix                                                                                                                100

     6.1 Tighter Bounds for User and TaskUtilities . . . . . . . . . . . . . . . . . . .  100

Bibliography                                                                                                          102 

About this Dissertation

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School
Department
Degree
Submission
Language
  • English
Research field
关键词
Committee Chair / Thesis Advisor
Committee Members
最新修改 Default

Primary PDF

Supplemental Files