移动情景和用户轨迹感知的众包服务推荐*
2019-09-14崔立真
姜 芸，何 伟+，崔立真，杨 倩，刘 磊
1.山东大学 软件学院，济南 250101
2.山东省软件工程重点实验室，济南 250101
1 引言
随着无线通信技术和移动智能终端的快速发展，基于位置的服务（location-based service，LBS）[1]以其移动性、实用性、便携性等独有的特点，可以随时随地获取移动网络服务和信息内容，在诸多领域得到广泛应用。所谓基于位置服务，指通过移动终端和无线或卫星通信网络的配合,确定出移动用户的实际地理位置,从而提供用户需要的与位置相关的信息服务，例如地图导航、物流跟踪、交通监测、移动众包任务推荐等。然而移动互联网服务和信息传递颇受上下文信息、移动社会化网络的影响，如何从浩瀚的移动信息海洋中发现用户感兴趣的服务，提升用户个性化服务体验，成为移动推荐系统亟待解决的难题。
与传统互联网用户相比,移动通信网中,用户的最大特征是用户位置随时间的随机性变动,正是这种位置的变动性,才使得基于移动用户不同位置的服务推荐成为可能。移动众包服务中最核心的是众包任务推荐，其旨在将时空任务推送给一个工人集合[2-4]，工人以各自独立或相互协作的方式完成同一个任务（例如，拍照/拍视频或者到指定地点签到），同时满足任务的时间、位置等约束[5-6]。在移动众包应用场景中，众包任务推荐面临着两个重要的挑战：
第一个挑战是移动用户行程轨迹及其意图的不确定性。众包模式下任务的执行者是互联网上的非特定人群，任务的接受和执行遵循自愿的原则，由用户根据自身兴趣或意图自行决定而无法强制，进行任务推荐的时候需要充分考虑每个潜在用户的轨迹变化、行为意图以及各种移动情景对他们的影响，尽可能使移动任务与用户的意愿相匹配，以提高任务推荐的成功率和他们对服务推荐的满意程度。
第二个挑战在于移动众包服务场景的动态性。例如出租车、外卖等O2O 服务，无论是任务发布者，还是潜在的执行者都在不断涌现，或者随时退出，并且其位置、轨迹也处于动态变化之中，这些对时空任务推荐算法的实时有效性、动态场景适应能力都提出了更高的要求。
目前给用户推荐任务的策略主要是基于移动用户的当前（任务分配时刻）位置，为用户推送时空任务或给他规划一个任务执行路线，而较少关注用户自身的轨迹及其位置变化趋势，有可能由于推荐给他的任务偏离其轨迹方向、行为意图等而拒绝接受这一任务，进而导致时空任务推荐的成功率低。
本文受工人历史轨迹数据可以提供很多有意义信息的启发，从中分析出某个用户的移动轨迹模式、行为习惯、对于某些地点的偏好等；然后基于该分析，对用户的移动位置区域进行预测；再将预测之后区域内的任务推送给他，这将会提高用户接受任务的概率，同时降低额外的旅行费用、时间等成本。
本文的主要贡献如下：
（1）首先将离散的位置点聚类成区域，然后对用户的区域移动轨迹进行挖掘，利用移动模式集来描述特定用户在不同移动情景下的轨迹变化。
（2）在用户移动模式集的基础上，构建移动规则，并提出预测工人位置区域的方法，将区域内的众包任务推送给他。
（3）在真实数据集上进行实验，验证了本文提出的不同移动情景下用户位置预测算法任务推荐策略的有效性和准确性。
本文的其余部分组织如下：第2章讲述其他人的相关工作；第3 章介绍相关定义；第4 章提出本文的方法，讲述具体的算法和例子；第5 章介绍任务推荐方法；第6章展示实验结果；第7章给出本文的结论。
2 相关工作
随着互联网移动通信技术的发展以及智能终端的广泛使用，很多研究人员把注意力集中到对历史轨迹数据的分析和挖掘，也因此产生了很多与空间位置有关的研究成果[7-10]。但是，绝大多数是集中在如何具体分析移动对象的历史轨迹，并从中发现有意义的信息，而对于位置预测技术的研究相对较少。Jeung和Liu等人[11]提出了一种新颖的方法，该方法结合预先定义好的运动公式来预测用户的下一个位置。预定义的运动程式通过利用复杂的数学公式和Apriori算法从用户轨迹中提取出频繁移动模式来捕捉移动对象的移动行为。他们使用的运动程式可以是线性的模型，也可以是非线性的模型。该方法时间开销巨大，计算量巨大。Morzy 利用改进版的Apriori算法来生成关联规则[12]，在他后来的研究中又利用改进后的Prefix Span 算法来发现用户频繁的移动模式，然后利用找出的频繁模式来生成预测规则[13]。尽管Morzy 的所有方法都有考虑时间信息和经纬度表示的地理位置信息，但是它们没有考虑地理位置中隐含的语义信息。
本文对文献[14]提出的位置预测方法进行改进，在预测移动模式生成中加入了上下文影响因素，例如考虑到周末/节假日和工作日的用户移动行为的区别，并根据上下文相关的移动模式分别提取移动规则从而提高预测的准确性。
3 问题定义
本文方法的基本思路是通过挖掘移动用户轨迹模式来预测用户将要到达的位置区域，然后将区域内的任务推荐给工人，以提高工人成功接受任务的概率。为了方便理解，介绍本文方法的相关定义。
定义1（区域（region,r））区域r表示地理位置范围，是对该移动用户和时空任务物理坐标的聚合，在本文中使用编号来表示。例如，万达广场商圈可以作为一个区域r。
定义2（实际路线（worker actual path，WAP））工人实际路线WAP 定义为Wap(w)=<(r1,t1),(r2,t2),…,(rn,tn)>，其中(ri,ti)表示工人w在时间为ti的时候到达了区域ri，ri是区域编号。一条路线表示工人w在一天内按时间先后依次去过的区域位置。
定义3（移动模式（worker mobile pattern，WMP））移动模式WMP也是工人的移动轨迹，在工人轨迹中出现比较频繁，即表示工人经常去的地方，能够很好地描述出工人的日常移动轨迹，表示为Wmp(w)=(<(r1,t1),(r2,t2),…,(rn,tn)>,supp),其 中 <(r1,t1),(r2,t2),…,(rn,tn)>同上述2 的路线定义，supp表示该路线基于工人w历史轨迹出现的频繁程度，叫作支持度，supp≥0。支持度的计算方式参考Apriori算法。
定义4（移动规则（worker mobile rule，WMR））一个移动规则WMR 描述了工人在各个区域之间的转移关系，表示为Wmr=
…
4 基于移动模式挖掘的工人位置预测
移动工人的位置区域预测及任务推荐过程包括四个阶段：首先对离散的位置点进行聚类，得到区域，对工人的历史区域移动轨迹进行挖掘，形成工人移动模式；根据获得的工人移动模式构建出工人移动规则；通过实时感知到的工人位置信息和移动规则预测工人下一步将要到达的位置区域；最后根据预测为工人推荐时空任务。位置预测及任务推荐过程如图1所示。
4.1 生成区域
假设本文中所有任务所在的位置能够包含在这些区域内，使用最流行的聚类算法K-means 算法将位置点聚合成区域，实现点到区域的变换。K-means算法的步骤如下：
Fig.1 Location prediction and task recommendation process for mobile workers图1 移动工人的位置预测及任务推荐过程图
（1）随机选择K个初始质心；
（2）如果没有满足聚类算法终止条件，则继续执行步骤（3），否则转步骤（5）；
（3）计算每个非质心点p到k个质心的欧几里德距离，将p指派给距离最近的质心；
（4）根据上一步的k个质心及其对应的非质心点集，重新计算新的质心点，然后转步骤（2）；
（5）输出聚类结果，算法可以执行多次，比较不同的聚类结果，选择较好的结果。
通过K-means 算法对位置点聚类后，得到区域，进一步将其形式化为有向图G。图2 是实际区域图的例子，图3 为区域网络有向图，双向箭头代表两个区域之间可以直接到达。
4.2 挖掘工人移动模式
本节详细介绍如何挖掘工人移动模式，下面是详细步骤。
Fig.2 Actual area map图2 实际区域图
Fig.3 Digraph of regional network图3 区域网络有向图
已知工人实际路线多条，首先可以得到长度为1的候选模式集C1，即长度为1的子路径，计算它们的支持度，大于本文设定的阈值1.33就加入到长度为1的移动模式集中，用L1表示；在L1中的区域，通过区域网络有向图观察从当前区域能够直接到达哪个区域，就将其区域编号加入到集合中，形成长度为2 的候选模式集C2；接着计算支持度，大于阈值的加到长度为2 的移动模式集L2中。根据这个规则，一直到找不到候选模式集为止，则移动模式集生成完毕。工人移动模式WMPMining()挖掘算法描述如算法1所示。
在移动情景方面，划分工作日、周末，将分别产生其移动模式Lw和Lp。
算法1工人移动模式WMP挖掘WMPMining()
输入：数据库中的工人实际路线（WAP）D，最小支持度suppmin，网络区域图G。
输出：工人移动模式（WMP）Lw、Lp。
为了说明CandidateGeneration()是如何工作的，假设存在一个长度为k用户轨迹，C=<(r1,t1),(r2,t2),…,(rk,tk)>作为算法的输入，考虑在区域网络有向图中，首先将从顶点rk出发所能到达的所有区域顶点加入到集合N+(rk)中去，这个集合中的区域顶点表示了工人从rk出发能够到达的地方。然后，从N+(rk)中选择某个顶点v，加入到候选序列中C′=<(r1,t1),(r2,t2),…,(rk,tk),(v,t)>，将C′加入到长度为k+1的候选序列中。表1给出了基于图3区域网络有向图的工人历史轨迹的例子。
假设支持度预先设定的阈值suppmin=1.33，根据表1中工人实际路线，通过WMPMining()算法挖掘用户的移动模式集L，如表2 所示。为了方便阅读，在表格展示中将时间省略了，但实际是将时间考虑在内的。
4.3 生成移动规则
在挖掘工人移动模式的基础上，进行移动规则提取，由第3 章移动规则定义可知，假设工人移动模式WMP，L=<(r1,t1),(r2,t2),…,(rk,tk)>,k>1,其移动规则见第3章。
Table 1 Workers'actual path表1 工人实际路线
Table 2 Worker mobile patterns set L表2 工人移动模式集合L
对于一个规则R:
利用工人移动模式挖掘算法得到的WMP，可以生成所有可能的移动规则并计算出它们的置信度。如果一个规则的置信度高于预先设定的置信度阈值(coffmin)，就将它们选择出来用于下一个区域预测阶段。
由于移动模式是基于不同情景提取的（本文只考虑了工作日/节假日相关性），每个移动规则也需要增加不同情景标签，来表明特定情景下的移动规则。
例如，根据表2 所示的移动模式集，生成移动规则并计算每个规则的置信度，假设置信度阈值(coffmin)为50%，则移动规则集合如表3 所示（WD 代表工作日，PD代表非工作日）。
4.4 工人区域预测
位置区域预测是最后一个阶段，算法的伪代码描述如下：
算法2位置区域预测MobilityPrediction()
输入：用户当前的移动轨迹P=<(r1,t1),(r2,t2),…,(ri-1,ti-1)>,移动规则集合R,预测的最大位置个数m。
输出：预测区域集合PRegions。
Table 3 Mobile rule set表3 移动规则集
上述算法的预测过程可以概括如下：假设工人当前移动轨迹为P=<(r1,t1),(r2,t2),…,(ri-1,ti-1)>,首先寻找适合当前路径的所有规则，将其归纳到匹配规则集中，匹配规则有如下特点：规则的头部包含在当前移动轨迹中，相当于是它的子路径，在匹配的时候，按照先匹配头部与轨迹一模一样的，然后逐渐降低规则头部长度的原则去寻找。把移动规则集全部扫描一遍找到所有符合匹配规则特点的规则后，将每个规则尾部的第一个区域编号以及此规则的置信度组成一个元祖（r,confidence），并按照置信度的大小降序排序。算法中还定义了另一个参数m，作为可以预测的区域的数量，从数组中选择前m个排序后的元组，意味着使用前m个匹配规则去预测工人的下一个位置。
由于生成移动规则时添加了情景标签（即是否为工作日），进行扫描时先判断当前时间与当前标签内容是否一致，如果与规则标签不符，直接跳过去扫描下一个规则，这将大大提高匹配效率。
5 移动众包任务推荐
在移动众包应用场景中，由于空间任务和工人的位置、数量都动态变化并实时更新，任务推荐的目标考虑在一段时间内，实现任务分配数量最大化的局部最优，本文基于文献[11]的贪心策略进行任务推荐。给定一组工人Wi={w1,w2,…}和区域D内的一组任务Ti={t1,t2,…},目标是在一段时间内，将Ti中的任务推荐给Wi中的工人。本文假设所有工人的质量一致。
基于文献[11]提出的策略，使用图的最大流问题解决任务推荐问题。给定一组工人Wi={w1,w2,…}和多个区域Ri的任务Ti={t1,t2,…},Gi=(V,E)表示网络图的顶点和边，其中包含|Wi|+|Ri|+|Ti|+2个顶点。每个工人wj对应一个顶点vj，每个区域rj映射到顶点，每个任务tj映射到顶点同时创建一个源点src和一个终点dest,Gi包含|Wi|+|Ri|+|Ti|+m条边，其中|Wi|条边为连接源点src和每个顶点vj，用(src,vj)表示，边的权重为每个工人可接受的最大任务数；有|Ti|条边连接任务Ti和终点dest，权重设为1，表示这个任务推荐给一个工人。
如图4 所示，是区域任务分布图，转化为图5 所示的流程网络图。图4 中工人与区域之间的箭头表示预测工人将要到达那个区域。图4 中的w1、w2、w3、w4对应于图5 的v1、v2、v3、v4,区域r1、r2、r3对应于图5的v5、v6、v7,区域内的任务对应于v8至v16，基于上一章中所述算法对工人到达位置区域的预测，可以判断出每个空间任务所推荐给的候选工人集合，接着将区域内的任务推荐给候选工人集合里的工人。通过求解图最大流问题，比如Ford-Fulkerson算法[15]，解决上述任务推荐问题。
Fig.4 Distribution map of workers,region and task图4 工人、区域、任务分布图
Fig.5 Process network diagram图5 流程网络图
6 实验
6.1 数据整理
为了在现实环境下测试所提出的方法，本文使用了基于位置的社交网络Gowalla的数据集，包括用户时间和其地点的经纬度，以及地点的ID。签到集包括了从2009 年至2010 年10 月期间收集的644 多万条数据，对其进行清洗和处理，最后提取了有100万条数据的数据集，其包含4 000 多个用户和45 000个不同地点。数据集的地点和用户分别用来代表空间的众包任务和工人的位置，只要工人到指定地点签到就看作是接受众包任务并完成。虽然数据集不是直接来自空间的众包，但它提供了不同的、现实世界的工人和任务位置的分布，由于本文研究的算法依赖于位置，使用这个数据集，能够对它们的相对性能得出一些合理的结论。
数据集本身是一些用户的签到数据，相对来说比较稀疏，本文首先对提取的数据集进行处理，将损坏的、空白的对实验没有任何帮助的数据全都清除。数据清洗完之后，使用K-means 算法对其进行聚类,将离散的数据聚成多个区域，看成众包任务的分布地点。
图6 是对数据集聚类的结果，其中类别数为2 000，每个类别分别用不同颜色标出，每种颜色代表一个类，即一个区域。
Fig.6 Clustering region graph图6 聚类区域图
按照时间先后将每一个工人的轨迹路径划分为训练集和测试集，其中训练集用来获得4.3节介绍的工人移动规则，测试集是用来测试通过移动规则预测的区域和工人真实要去的区域是否一致。如果一致，表明预测的工人即将要去的区域和众包任务的分布区域是一样的，就可以将区域内的任务推送给工人，即代表任务推荐成功，否则推荐失败。
6.2 实验评估
用success代表任务推荐的成功率，计算公式如下：
其中，match表示任务推荐成功的数量，all表示所有的任务数。
下面给出本文方法与Yavaş等研究者[14]提出的预测方法的比较，根据测试集预测区域编号的准确率进行对比，如图7、图8所示。
Fig.7 Comparison of accuracy of WMP and UMP on workdays图7 WMP、UMP在工作日的准确率比较
Fig.8 Comparison of accuracy of WMP and UMP on weekends图8 WMP、UMP在非工作日的准确率比较
图7、图8 表明，随着聚类类别数的增加，两个方法的准确率都是降低的。类别数少，实际区域的范围就大，而工人的轨迹区域变化就少，工人基本待在固定的一到两个区域内，准确率就会升高；类别数大，实际区域范围就小，越来越接近位置点，工人的轨迹变化开始增多，准确率会稍微降低。类别数为100 时，区域范围很大，工人一天基本待在一个区域内，预测的结果会很准确。由图7、图8 可知，本文方法不管在工作日还是非工作日都要比Yavaş等提出的方法性能好。本文考虑了工人历史轨迹的时序性，研究表明[16]，用户去前100 个地点的概率比后面几十万地点的概率大0.5，这就说明，区域地点之间存在某种潜在的联系，并不仅仅只考虑最后一个区域去预测。划分工作日之后，不仅成功率提高，算法的时间复杂度也会较低，因为可以直接根据规则标签来判断是否为工作日，减少算法扫描规则的时间，进而高效地去预测区域，推送任务。
7 结论
针对移动众包服务推荐，本文提出了一个移动情景和用户轨迹感知的众包服务推荐策略。本文方法在众包平台分配任务时，通过实时感知到的轨迹信息和移动规则，预测用户即将到达的位置区域，从而将区域内的时空任务推送给该用户。本文任务分配方法避免了额外增加的工人执行任务的时间、行程、费用等成本，工人更愿意接受任务，从而提高了任务完成的概率，也提高了用户体验推荐服务的满意度。
