一种基于空间众包社交影响偏好的组任务分配方法

摘要

本发明公开了一种基于空间众包社交影响偏好的组任务分配方法，该方法包括(S1)利用二分图嵌入模型BGEM和注意力机制分析每个工人对不同任务种类的社交影响偏好值，即每个工人和任务类别直接的权值；(S2)引入树分解的任务分配算法根据每个工人对不同任务种类的社交影响偏好值将一个任务分配给多个工人，即工人组。通过上述方案，本发明通过使用二分图嵌入模型(BGEM)和注意力机制学习工人组对任务种类的基于社交影响的偏好值，在此偏好值的基础上，对空间任务进行分配，从而达到最大任务分配的目的，具有很高的实用价值和推广价值。

权利要求

1.一种基于空间众包社交影响偏好的组任务分配方法，其特征在于，包括工人组的基于社交影响的偏好模型SIPM和基于工人组偏好值的基于偏好的组任务分配PGTA；所述SIPM部分中，同时使用工人‑任务交互数据和工人组‑任务交互数据，采用二分图嵌入模型BGEM和注意力机制获得每个工人组对不同任务种类的偏好值；采用BGEM对工人‑任务交互数据和工人组‑任务交互数据进行建模，从而分别学习低维空间中工人和任务种类的向量表示；

引入工人的社交影响力，所述社交影响力表示在作出任务选择决策时团队中工人的权重，具体为：将工人‑任务交互数据和工人组‑任务交互数据融合以构建一个社交网络，基于该社交网络提取社交网络信息；将工人组‑任务交互数据和工人‑任务交互数据相结合，获得工人和任务种类的表示向量以及工人的权重，即工人社交影响；同时，使用注意力机制计算工人组向量，该注意力机制为不同的工人分配不同的权重，最终，将工人组的表示向量和任务种类向量做点积，以获得工人组对任务种类的偏好值；

所述PGTA中，给定要分配的工人和任务，首先通过考虑行程限制以获得可用工人集合，然后使用基于树分解的最优任务分配算法将任务分配给合适的工人组以最大化总任务分配，并且给对任务有着更高偏好值的工人组更高的优先级；

个人交互模型：

给定工人和任务之间的交互，即工人‑任务交互数据，首先构建一个二分图，其中， 表示工人集合，表示任务种类， 表示 中的节点集合， 表示工人和任务种类间的边集合；当工人 执行过种类为 的任务时，则两者之间存在一条边 边 的权值 设为 其中， 表示工人 执行过的种类为 的任务数量， 表示工人 执行过的任务总数；

使用BGEM建模个人工人‑任务交互，对于给定的工人 和种类为 的任务进行交互的概率可以计算如式(1)所示：其中， 表示工人 的表示向量，这代表该工人的偏好， 表示任务种类 的表示向量；

定义BGEM的目标函数，BGEM的目标旨在对于每个工人 最小化经验分布和估计的邻居概率分布 之间的KL散度；使用 表示工人节点 的出度，该出度使用 计算得出，其中， 表示边 的权值；将经验分布定义为因此，目标函数可定义为式(2)：工人组交互模型：

构建一个 二分图表示 工人组 和任务种类之间 的交互 ，该二分图 用表示，其中，表示工人组集合， 表示 和的节点集合，表示工人组和任务种类间的边集合；当工人组 执行过种类为 的任务时，则两者之间存在一条边 同时，边 的权值 可简单设为 其中， 表示工人组 执行过的种类为 的任务数量， 表示工人组 执行过的任务总数；使用 表示工人组 的表示向量， 表示任务种类 的表示向量；目标是为每个工人组获取表示向量以估计对所有任务种类的偏好值；

工人组‑任务交互数据的目标函数可以通过式(3)计算：引入一个系数 表示工人组 中工人 的权重，该权重表示组 在选择任务时工人 的组意识的个人社交影响力；具体为：给定工人组 如式(4)定义工人组的表示向量

为每个工人 引入一个额外的正值 该值表示不依赖于任何特定组的全局个人社交影响力；使用 表示一个工人对组内选择任务的相对影响力；因此，按照注意力机制，该系数 可由如式(5)计算：根据社交网络结构信息计算每个工人 的社交网络特征向量 使用特征选择向量为不同的结构特征分配不同的权重；将所有的特征值归一化为[0，1]范围内；接下来，将社交网络特征向量 和特征选择向量 做点积，作为工人的全局个人社交影响的高斯先验，即 其中 是一个偏差项；由于全局个人社交影响可能会受到其他未知因素的影响，为了学习更加健壮的全局个人社交影响力，设 服从正态分布，均值为在目标函数方面，由于为个人社交影响参数 引入了高斯先验，因此在目标函数中添加相应的正则化项 即 其中超参数 可以控制正则项的权重；因此，新的目标函数如式(6)所示：将 和 相结合形成联合目标函数，定义如式(7)所示：采用标准的随机梯度下降策略最小化式(7)中的目标函数 在此过程中，学习到工人表示向量 任务种类表示向量 和模型参数、 根据式(5)计算出表示组意识的个人社交影响力的系数 然后根据式(4)相应的计算出每个组的表示向量 最终，将每个组的表示向量和每个任务种类的表示向量做点积，以获得每个组对每个任务种类的偏好值；

可用工人组集合的产生：

获得每个任务的可用工人；由于工人可达范围、工人可用时间和任务失效时间的约束，在某个时刻每个任务只能由一小部分工人完成；因此，首先在不违反约束的情况下获得能够完成该任务的工人集合；任务 的可达工人子集，可用 表示，且 应该满足以下条件：

(1)工人在任务s失效前，到达任务s的地点，即(2)任务s在工人的可达范围内，即(3)工人在自己的有效时间内，到达任务s的地点，即其中， 表示当前时间， 表示从工人位置 和位置 之间的行驶时间，而 是给定的位置 和位置 之间的行驶距离；上述三个条件保证工人可以在任务 失效之前且在工人 的可用时间内直接从其位置 行驶到任务 的位置；

并且 是Reachable Worker sets，表示可达工人集合，即由于时空约束，每个任务只能由一些工人来完成， 是一个整体式；前面提到的 不指定某个任务，即对于空间众包中的所有工人；

获得每个任务的可用工人组集合；给定每个任务s的可达工人，在组内工人可用时间和允许分配的执行任务 的工人数量的约束下，接下来查找可用工人组集合，用 表示， 中的可用工人组应满足以下条件：(1)

(2)

其中， 表示 中工人数量；上述两个条件保证一个组内的工人到达任务 的位置而不会影响互相的可用时间。

说明书

一种基于空间众包社交影响偏好的组任务分配方法

技术领域

[0001] 本发明属于计算机技术领域，具体地讲，是涉及一种基于空间众包社交影响偏好的组任务分配方法。

背景技术

[0002] 随着无线网络和移动设备(例如智能电话)的广泛部署，空间众包(Spatial Crowdsourcing，SC)是一种利用分布式移动设备监测人类活动各种现象的新兴范例，它已
经引起了学术界和行业界的广泛关注。空间众包的主要思想是招募一组可用的工人，通过
实际移动到这些位置来执行特定位置的任务，这被称为任务分配(task assignment)。

[0003] 现有的大多数SC研究集中于单个任务分配，这种任务分配假设任务很简单并且每个任务只能分配给单个工人。例如，Tong Yongxin等人设计一些有效的贪心算法来解决空
间众包中提出的全局在线微任务分配问题(Global Online Micro‑task Allocation,
GOMA)。Deng Dingxiong等人同时考虑任务分配和调度，其发明了一种近似算法，迭代的改
进分配和调度以实现更多复杂的任务。但是在现实情况中，单个工人可能无法独立执行一
个复杂的任务(例如，监测某个区域的交通流量或搬运重物)，因为单独完成这个任务超过
了该工人的能力。在这种情况下，应该将每个任务分配给一组工人，这被称为组任务分配
(Group Task Assignment,GTA)。

[0004] 组任务分配需要一组工人通过在特定时间内实际前往该任务的位置从而执行该任务。先前的一些研究已经探索过空间众包中的组任务分配问题。例如，Gao Dawei等人提
出面向团队的任务计划(Team‑Oriented Task Planning,TOTP)问题，该问题为工人执行了
可行的计划并且满足了不同任务对工人的技能要求。Gao Dawei等人在空间众包中还提出
一个Top‑k的团队推荐框架，该框架中，团队领导人是在每个推荐的工人团队中任命，以方
便的协调不同的工人。Cheng Peng等人考虑了任务分配中的协作性，其中要求工人们共同
合作且完成任务，从而获得较高的总协作质量分数。然而，他们无法有效的集成小组偏好，
这是在空间众包中提高组任务分配质量的重要因素，这是因为当组成员对任务不感兴趣时
他们可能不愿意执行分配给他们的任务。

发明内容

[0005] 为了克服现有技术中的上述不足，本发明提供一种基于空间众包社交影响偏好的组任务分配方法，使用二分图嵌入模型(BGEM)和注意力机制学习工人组对任务种类的基于
社交影响的偏好值，在此偏好值的基础上，对空间任务进行分配，从而达到最大任务分配。

[0006] 为了实现上述目的，本发明采用的技术方案如下：

[0007] 一种基于空间众包社交影响偏好的组任务分配方法，包括如下步骤：

[0008] (S1)利用二分图嵌入模型BGEM和注意力机制分析每个工人对不同任务种类的社交影响偏好值，即每个工人和任务类别直接的权值；

[0009] (S2)引入树分解的任务分配算法根据每个工人对不同任务种类的社交影响偏好值将一个任务分配给多个工人，即工人组。

[0010] 进一步地，所述步骤(S1)中社交影响偏好值的判断类型包括个人交互模型和工人组交互模型。

[0011] 进一步地，所述个人交互模型为给定工人和任务之间的交互，即工人‑任务交互数据，使用BGEM建模个人工人‑任务交互得：

[0012]

[0013] 其中，W表示工人集合，C表示任务种类，W∪C表示 中的节点集合，EWC表示工人和任务种类间的边集合。

[0014] 进一步地，所述工人组交互模型为给定工人组和任务种类之间的交互，使用BGEM建模工人组‑任务交互得：

[0015]

[0016] 其中，G表示工人组集合，G∪C表示 中的节点集合，EGC表示工人组和任务种类间的边集合。

[0017] 进一步地，所述步骤(S2)中根据每个工人对不同任务种类的社交影响偏好值对组任务进行分配可获得每个任务的可用工人或者获得每个任务的可用工人组集合。

[0018] 进一步地，所述获得每个任务的可用工人为在不违反约束的情况下获得能够完成任务的工人集合，其中，任务s的可达工人集用RWs表示，即 同时满足以下条件：

[0019] (1)工人在任务s失效前，到达任务s的地点，即tnow+t(w.l,s.l)≤s.e；

[0020] (2)任务s在工人的可达范围内，即d(w.l,s.l)≤w.r；

[0021] (3)工人在自己的有效时间内，到达任务s的地点，即tnow+t(w.l,s.l)≤w.off；

[0022] 其中，tnow表示当前时间，t(w.l,s.l)表示从工人位置w.l和位置s.l之间的行驶时间，d(w.l,s.l)表示给定的位置w.l和位置s.l之间的行驶距离；上述三个条件保证工人w可
以在任务s失效之前且在工人w的可用时间内直接从其位置w.l行驶到任务s的位置。

[0023] 具体地，所述获得每个任务的可用工人组集合在给定每个任务s的可达工人，在组内工人可用时间和允许分配的执行任务s的工人数量的约束下查找可用工人组集合，并用
AWG(s)表示可用工人组，同时AWG(s)满足以下条件：

[0024] (1)|AWG(s)|＝s.numW；

[0025] (2)

[0026] 其中，|AWG(s)|表示AWG(s)中工人数量，并且上述两个条件保证了一个组内的工人可以到达任务s的位置而不会影响互相的可用时间。

[0027] 实验设置：

[0028] 本发明使用Twitter中的check‑in数据集进行实验，该数据集提供了从2010年9月到2011年1月除夏威夷和阿里斯加以外的美国范围内的check‑in数据，其中包括62462个场
所和61412个用户的位置。该数据集被广泛应用于众包平台的评估。由于数据集中缺少场所
的种类信息，因此本发明借助Foursquare的API信息生成每个场所的种类信息(即任务种类
信息)。在实验研究中使用该数据集时，由于在不同地点签到的用户可能是在这些地点附近
执行空间任务的好人选，所以假设数据集中的用户是众包平台中的工人，工人位置是最新
的签到点。假设这些点是众包平台的任务，使用其位置表示任务的位置，一天中最早的签到
时间表示任务的发布时间。本发明抽取20种签到种类模拟任务种类(即签到的种类)。在一
个地点签到等效于接受此任务。因为Twitter不包含显式的组信息，所以按照以下方法抽取
隐式的组任务完成活动：假设一个小时内一组用户访问同一个地点或同一种类的彼此接近
的不同地点(例如，在实验中任何两个地点之间距离小于10km)被视为一个组内的成员。

[0029] 比较并评估以下方法的性能：

[0030] 1)OGTA：基于树分解算法的最优组任务分配(Optimal Group Task Assignment)，没有考虑工人组的偏好值。

[0031] 2)AVG‑OGTA：具有平均工人组偏好的最优组任务分配(Optimal Group Task Assignment with average worker group’s preference)，其中组g的平均偏好值设置为
其中 表示组g已经执行过的类别为c任务数量，Ng表示组g执行过的总任务数量。

[0032] 3)SIP‑GGTA：工人组的基于社交影响的偏好值的贪心组任务分配(Greedy Group Task Assignment with Social Impact‑based Preference of worker groups)。为了提
高效率，引入基本的贪心任务分配算法以将每个任务贪婪地分配给具有最大偏好值的工人
组，直到所有的任务被分配完或所有的工人组都用尽。

[0033] 4)SIP‑OGTA：工人组的基于社交影响的偏好值的最优组任务分配(Optimal Group Task Assignment with Social Impact‑based Preference of worker groups)。即我们
提出的算法。

[0034] 上述算法中我们比较了三个指标：

[0035] 1)CPU成本：在某个时刻查找任务分配的CPU时间成本。

[0036] 2)ASR：分配成功率(Assignment Success Rate)是一个时刻内所有工人的成功分配数和总分配数的比值。注意，一旦一个小时内所有组内成员实际上执行(签到)彼此接近
的相同类别的任务(地点)(例如，在实验中任务之间的距离小于10km)，认为此任务分配为
一个成功分配。

[0037] 3)任务分配数量。

[0038] 其中实验参数如表1所示：

[0039] 表1.实验参数

[0040] 参数 默认值任务的有效时间e‑p 1.5h
每组工人数量numW 2
工人的可达半径r 2km
工人的可用时间off‑on 3h
任务数量|S| 3000

[0041] 实验结果：

[0042] e‑p的影响：首先研究任务有效时间e‑p的影响。正如图2(a)所示，由于随着失效时间边长我们需要搜索更多的可用工人组，因此对于所有算法而言这会导致更多的CPU成本。
不出所料，随着任务有效时间的增加，除OGTA之外其他所有算法的准确率都提高，这是因为
随着任务有效时间增加，工人组有更多的机会被分配其感兴趣的任务(如图2(b)所示)。在
ASR方面，SIP‑OGTA和SIP‑GGTA的性能均优于AVG‑OGTA，这表明了将社交影响考虑到工人组
偏好中的优势。由于OGTA算法没有考虑工人组的偏好所以该方法几乎保持不变。虽然SIP‑
GGTA在所有方法中是最快的并且和SIP‑OGTA有着相似的ASR，但是SIP‑GGTA算法和其他方
法(即OGTA、AVG‑OGTA、SIP‑OGTA)相比分配任务数量更低(如图2(c)所示)。

[0043] off‑on的影响：在这部分实验中，评价工人可用时间的影响。从图3(a)可以看出，所有算法的CPU成本随着off‑on增加呈增长趋势，这是因为每个任务的可用工人组增加。如
图3(b)所示，SIP‑OGTA和SIP‑GGTA的ASR始终优于其他算法，SIP‑GGTA略低于SIP‑OGTA。当
off‑on增加时，所有方法的分配成功率都和e‑p方面有着相似的趋势，其原因也是类似的，
当off‑on增加时，工人组有更多的机会获得他们感兴趣的任务。而任务分配数量随着off‑
on的增加而迅速增长，几乎呈线性增长(如图3(c))。其内在原因在于随着工人可用时间边
长每个任务的可用工人组越来越多。

[0044] r的影响：即工人可达半径的范围。显然，随着r的增大，所有方法的CPU成本都逐渐增加(参考图4(a))。对于考虑了工人组偏好的所有方法，分配成功准确率随着r的增加而增
加，这是因为工人可达区域越大，工人组被分配其感兴趣的任务的几率更大(图4(b))。如图
4(c)所示，可以看到SIP‑GGTA算法的性能比其他算法都差，这也表明了最优任务分配策略
的优越性。

[0045] numW的影响：图5(a)说明了当每组的工人数量(即numW)变大时，CPU成本逐渐降低。背后的原因是随着numW变大，每个任务的可用工人组越来越少，从而减少了搜索空间。
就分配成功率而言，如图5(b)所示，所有的算法均呈下降趋势。由于可用工人组减少，、无法
将任务分配给合适的组。但是，SIP‑OGTA方法仍然比其他算法具有更高的优越性。另外，图5
(c)证明了SIP‑GGTA算法的任务分配数量与其他方法相比没有优势。

[0046] |S|的影响：在实验的最后部分，通过改变任务的数量|S|从1k到5k，评价所提出的算法的可扩展性。正如预期那样，虽然CPU成本随着|S|的增加而增加，但是由图6(b)和图6
(c)所示，SIP‑OGTA在提升分配准确率和任务分配数量方面表现良好。由图6(a)所示，SIP‑
GGTA是最省时的算法，而其他的基于OGTA的算法运行速度要慢得多，这主要是因为在构建
要搜索的树和对树进行搜索时需要额外的时间成本。在分配成功率方面，由图6(b)可知，随
着|S|数量的增多，SIP‑OGTA的准确率仍比SIP‑GGTA稍高些，AVG‑OGTA缓慢增长。由图6(c)
可得，和之前的结果类似，在任务分配数量方面，对于|S|的所有值，OGTA相关算法的性能均
优于SIP‑GGTA的方法。

[0047] 与现有技术相比，本发明具有以下有益效果：

[0048] (1)本发明使用二分图嵌入模型BGEM和注意力机制学习工人组对任务种类的基于社交影响的偏好值，在此偏好值的基础上，对空间任务进行分配，从而达到最大任务分配。

[0049] (2)本发明提出一种基于工人组偏好的组任务分配框架。该框架由两个主要部分组成：基于社交影响的偏好模型SIPM和基于偏好的组任务分配PGTA。首先在SIPM部分中，利
用二分图嵌入模型和注意力机制从工人组‑任务交互数据中学习任务种类和工人组在低维
空间中的表示，为了克服数据稀疏问题的局限性，在偏好建模过程中同时集成了工人‑任务
交互数据和社交网络结构信息。然后在PGTA部分中，使用基于树分解策略的最优任务分配
算法，通过将更高的优先级给予对任务更感兴趣的工人组，将任务分配给相应的工人组从
而实现最大化的任务分配。

附图说明

[0050] 图1为本发明的系统结构示意图。

[0051] 图2为本发明组任务分配性能关于e‑p的影响图。

[0052] 图3为本发明组任务分配性能关于off‑on的影响图。

[0053] 图4为本发明组任务分配性能关于r的影响图。

[0054] 图5为本发明组任务分配性能关于numW的影响图。

[0055] 图6为本发明组任务分配性能关于|S|的影响图。

[0056] 图7为本发明的模型框架图。

[0057] 图8为本发明具体运行示例图。

具体实施方式

[0058] 下面结合附图和实施例对本发明作进一步说明，本发明的实施方式包括但不限于下列实施例。

[0059] 实施例

[0060] 如图1所示，一种基于空间众包社交影响偏好的组任务分配方法，包括如下步骤：

[0061] (S1)利用二分图嵌入模型BGEM和注意力机制分析每个工人对不同任务种类的社交影响偏好值，即每个工人和任务类别直接的权值；其中，社交影响偏好值的判断类型包括
个人交互模型和工人组交互模型。

[0062] (S2)引入树分解的任务分配算法根据每个工人对不同任务种类的社交影响偏好值将一个任务分配给多个工人，即工人组；其中，根据每个工人对不同任务种类的社交影响
偏好值对组任务进行分配可获得每个任务的可用工人或者获得每个任务的可用工人组集
合。

[0063] 如图7所示，本发明包含两个主要部分，其一是工人组的基于社交影响的偏好模型SIPM(Social‑Impact‑based Preference Modeling)，其二是基于工人组偏好值的基于偏
好的组任务分配PGTA(Preference‑based Group Task Assignment)。

[0064] 在SIPM部分中，本发明同时使用工人‑任务交互数据和工人组‑任务交互数据，利用二分图嵌入模型(BGEM)和注意力机制获得每个工人组对不同任务种类的偏好值。值得注
意的是，本发明如果一个工人执行过一项任务则表示该工人和该任务是有交互的。更具体
来说，我们利用BGEM对个人交互(即工人‑任务交互)和工人组交互(即工人组‑任务交互)进
行建模，从而分别学习低维空间中工人和任务种类的向量表示。由于空间众包中的工人组
通常是临时组建的(称为偶然组)，这些组和任务没有任何的交互，这意味着组交互数据很
稀疏，因此本发明无法直接有效的学习组的向量表示。为了解决该问题，本发明引入工人的
社交影响力，该影响力表示在作出任务选择决策时团队中工人的权重。具体来说，将工人‑
任务交互数据和工人组‑任务交互数据融合以构建一个社交网络，基于该社交网络提取社
交网络信息。为了减轻工人组‑任务交互数据的稀疏度，使用联合优化的方法将工人组‑任
务交互数据和工人‑任务交互数据相结合，可以获得工人和任务种类的表示向量以及工人
的权重(即工人社交影响)。同时，使用注意力机制计算工人组向量，该机制为不同的工人分
配不同的权重。最终，本发明将组向量和任务种类向量做点积，以获得工人组对任务种类的
偏好值。

[0065] 在PGTA部分中，给定要分配的工人和任务，本发明首先通过考虑行程限制(即工人可达半径、工人可用时间和任务失效时间)以获得可用工人集合(Available Worker 
Groups,AWGs)，然后使用基于树分解的最优任务分配(Optimal Task Assignment,OTA)算
法将任务分配给合适的工人组以最大化总任务分配，并且给对任务有着更高偏好值的工人
组更高的优先级。

[0066] 个人交互模型：

[0067] 给定工人和任务之间的交互，即工人‑任务交互数据，首先构建一个二分图，其中，W表示工人集合，C表示任务种类，W∪C表示 中的节点集
合，EWC表示工人和任务种类间的边集合。当工人wi∈W执行过种类为cj∈C的任务时，则两者
之间存在一条边eij∈EWC。边eij的权值hij设为 其中， 表示工人wi执行过的种
类为cj的任务数量， 表示工人wi执行过的任务总数。

[0068] 由于BGEM在学习异构交互实体嵌入表示方面的成功，本发明使用BGEM建模个人工人‑任务交互，对于给定的工人wi，wi和种类为cj的任务进行交互的概率可以计算如式(1)所
示：

[0069]

[0070] 其中，wi表示工人wi的表示向量，这代表该工人的偏好，cj表示任务种类cj的表示向量。

[0071] 接下来，定义BGEM的目标函数，BGEM的目标旨在对于每个工人wi∈W，最小化经验分布 和估计的邻居概率分布p(·|wi)之间的KL散度。使用di表示工人节点wi的出
度，该出度可以使用 计算得出，其中，hij表示边eij的权值。将经验分布定义
为 因此，目标函数可定义为式(2)：

[0072]

[0073] 工人组交互模型：

[0074] 同样的，构建一个二分图表示工人组和任务种类之间的交互，该二分图可用表示，其中，G表示工人组集合，G∪C表示 中的节点集合，EGC表示
工人组和任务种类间的边集合。当工人组gi∈G执行过种类为cj∈C的任务时，则两者之间存
在一条边eij∈EGC。同时，边eij的权值hij可简单设为 其中， 表示工人组gi执行
过的种类为cj的任务数量， 表示工人组gi执行过的任务总数。本发明使用gi表示工人组
gi的表示向量，cj表示任务种类cj的表示向量。本发明的目标是为每个工人组获取表示向量
以估计对所有任务种类的偏好。

[0075] 因此，和工人‑任务交互数据相似，工人组‑任务交互数据的目标函数可以通过式(3)计算：

[0076]

[0077] 然而，实际上在空间众包中，几乎没有持久性团体(persistent groups)，而有着大量临时形成的偶然团体(occasional groups)，去执行任务。因此，由于偶然组的冷启动
特性(即没有或只有很少的工人组‑任务交互)，工人组‑任务交互数据非常稀疏，这导致难
以直接学习偶然组的表示向量。为了解决数据稀疏和冷启动问题，从工人组‑任务交互数据
中集成组内所有成员的向量表示。可以注意到，在诸如任务选择之类的决策中，某些组内成
员可能在表达其偏好时胜过其他成员(由于声望、权威或其他个人因素)，因此这些人在小
组选择任务时的影响力更大。因此，本发明引入一个系数α(k，i)表示组gi中工人wk的权重，
该权重表示组gi在选择任务时工人wk的组意识的个人社交影响力(group‑aware personal 
social impact)。具体来说，给定偶然组gi，如式(4)定义组表示向量gi：

[0078]

[0079] 但是，偶然小组在某个时刻暂时聚集在一起执行任务。由于极端的数据稀疏问题，难以直接从工人组‑任务交互数据中直接学习系数α(k，i)。因此本发明为每个工人wk引入
一个额外的正值λk，该值表示不依赖于任何特定组的全局个人社交影响力(global 
personal social impact)。使用exp(λk)表示一个工人对组内选择任务的相对影响力。因
此，按照注意力机制，该系数α(k，i)可由如式(5)计算：

[0080]

[0081] 显然，一旦获得了表示每个工人wk的全局个人社交影响的λk，就可以很容易的获得表示一个工人组中具有群体组意识的个人社交影响力α(k，i)。但是如果一个工人参加的组
活动很少，则可能遇到过拟合问题。而且，如果一个工人从未参加过任何的组活动，则无法
学习到全局个人社交影响。因此，本发明无法仅从工人组‑任务交互数据中学习到令人满意
的社交影响力。

[0082] 为了提升全局个人社交影响估计的准确性，本发明基于工人‑任务和工人组‑任务交互数据构造工人的社交网络，在此社交网络的基础上抽取社交网络信息，这会有利于工
人全局社交影响的估计。在社交网络中，每个工人映射到一个节点，如果同一组内的两个工
人互相合作过则两者之间存在一条边。边的权值设为工人之间的合作次数。每个工人(节
点)和他完成的任务数量相关联。然后使用不同的措施(例如，度中心性(degree 
centrality)和中介中心性(betweenness centrality))抽取社交网络结构信息，并且将社
交网络结构信息集成到工人全局社交影响的学习过程中，这有效减轻了工人组‑任务交互
数据的冷启动问题。

[0083] 具体来说，根据社交网络结构信息计算每个工人wk的社交网络特征向量βk，使用特征选择向量h为不同的结构特征分配不同的权重。将所有的特征值归一化为[0，1]范围内。
接下来，将社交网络特征向量βk和特征选择向量h做点积，作为工人的全局个人社交影响的
高斯先验，即 其中b是一个偏差项。由于全局个人社交影响可能会受
到其他未知因素的影响，为了学习更加健壮的全局个人社交影响力，假设λk服从正态分布，
均值为βk·h+b。

[0084] 在目标函数方面，由于为个人社交影响参数λk引入了高斯先验，因此应该在目标函数中添加相应的正则化项RV，即 其中超参数 (即方
差)可以控制正则项的权重。因此，新的目标函数如式(6)所示：

[0085] OVGC＝OGC+RV   (6)

[0086] 考虑到工人组‑任务交互数据的冷启动问题，在优化过程中将工人‑任务交互数据和工人组‑任务交互数据结合在一起。更具体来说，即设计了一个联合优化方法，该方法可
以同时从工人‑任务交互数据和工人组‑任务交互数据中学习工人和任务种类的表示向量。
除此以外，在优化过程中，工人的全局社交影响也可以学习到。因此，将OVGC和OWC相结合形成
联合目标函数，可以简单定义如式(7)所示：

[0087] OGWC＝OVGC+OWC   (7)

[0088] 采用标准的随机梯度下降(Stochastic Gradient Descent，SGD)策略最小化式(7)中的目标函数OGWC，在此过程中，可以学习到工人表示向量w、任务种类表示向量c和模型
参数(即λk、h)。根据式(5)可以计算出表示组意识的个人社交影响力的系数α(k，i)。然后根
据式(4)可以相应的计算出每个组的表示向量g。最终，将每个组的表示向量和每个任务种
类的表示向量做点积，以获得每个组对每个任务种类的偏好。

[0089] 可用工人组集合的产生：

[0090] 获得每个任务的可用工人。由于工人可达范围、工人可用时间和任务失效时间的约束，在某个时刻每个任务只能由一小部分工人完成。因此，首先在不违反约束的情况下获
得能够完成该任务的工人集合。任务s的可达工人子集，可用RWs表示，且 应该
满足以下条件：

[0091] (1)工人在任务s失效前，到达任务s的地点，即tnow+t(w.l，s.l)≤s.e；

[0092] (2)任务s在工人的可达范围内，即d(w.l，s.l)≤w.r；

[0093] (3)工人在自己的有效时间内，到达任务s的地点，即tnow+t(w.l，s.l)≤w.off；

[0094] 其中，tnow表示当前时间，t(w.l，s.l)表示从工人位置w.l和位置s.l之间的行驶时间，而d(w.l，s.l)是给定的位置w.l和位置s.l之间的行驶距离(例如，欧几里德距离)。上述
三个条件保证工人w可以在任务s失效之前且在工人w的可用时间内直接从其位置w.l行驶
到任务s的位置(该任务位于工人的可达范围内)。

[0095] 并且RWs是Reachable Worker sets，表示可达工人集合，即由于时空约束(如工人的可达范围、有效时间，以及任务的失效时间)，每个任务只能由一些工人来完成，RWs是一
个整体式。前面提到的W不指定某个任务，即对于空间众包中的所有工人。例如，一共有5个
苹果(相当于W)，小孩A只能吃其中一个苹果(该苹果相当于孩子A的RWs)。

[0096] 获得每个任务的可用工人组集合。给定每个任务s的可达工人，在组内工人可用时间和允许分配的执行任务s的工人数量的约束下，接下来查找可用工人组集合，用AWG(s)表
示，AWG(s)中的可用工人组，应该满足以下条件：

[0097] (1)|AWG(s)|＝s.numW；

[0098] (2)

[0099] 其中，|AWG(s)|表示AWG(s)中工人数量。上述两个条件保证了一个组内的工人可以到达任务s的位置而不会影响互相的可用时间。

[0100] 本发明引入了基于树分解的策略，以获得具有最大偏好值的最优任务分配。更具体来说，首先根据任务之间的依赖关系(即，如果两个任务之间共享可用的工人则彼此是相
互依赖的，否则他们是彼此独立的)构建一个任务依赖图。随后，利用树分解策略将所有的
任务划分到独立的簇中(即不同簇中的任务不共享相同可用工人)，并且将它们组织到平衡
树结构中，以使得树的兄弟节点中的任务不共享相同的可用工人。通过这样的树结构，本发
明可以独立的解决每个兄弟节点上的最优分配子问题，然后对树进行深度优先搜索查找最
优分配。

[0101] 具体示例：

[0102] 图8显示了组任务分配问题的示例，其中每个任务都需要分配给两个工人，一共存在五个工人(w1，...，w5)和两个任务(s1，s2)。每个工人和他当前位置及其可达距离范围相
关联。每个任务标记有被执行的位置。除此以外，图8还显示了不同的可达任务组队每个任
务的偏好。则该问题即将任务分配给合适的工人组以最大化总任务分配。在空间众包中，在
不违反时空约束(即，所分配的任务应位于相应工人的可达范围内，工人应当在任务截止时
间之前到达所分配任务的位置)的情况下，将附近的任务分配给工人是一种直观的行为。因
此，我们可以获得一个任务分配{，}，其总组偏好为0.33。但是，当
我们将任务s2分配给工人组{w4，w5}时，由于该工人组对s2几乎没有兴趣(即，对s2的组偏好
值为0.04)，因此该工人组可能不会执行任务s2，这会使得s2不能被完成。如果在分配任务
时，对于对任务更感兴趣的工人组，我们给其更高的优先级，我们可能获得任务分配结果{<
s1，{w2，w3}>，}，其总组偏好是0.78。

[0103] 上述实施例仅为本发明的优选实施例，并非对本发明保护范围的限制，但凡采用本发明的设计原理，以及在此基础上进行非创造性劳动而做出的变化，均应属于本发明的
保护范围之内。