作者：JUST团队-李瑞远
如何快速得知从你的位置开始出发，在当前的交通状况下，5分钟之内能够抵达的空间区域范围？当你掏出手机打车时，出租车调度平台应该通知哪些范围的车主进行接单？本期技术前沿，京东城市将带来被国际著名数据库和数据挖掘会议DASFAA 2020 (CCF B类)成功接收的、JUST团队与武汉大学、西安电子科技大学、西南交通大学合作的论文：《Discovering Real-Time Reachable Area using Trajectory Connections》[2]，作者为：Ruiyuan Li，Jie Bao，Huajun He，Sijie Ruan，Tianfu He，Liang Hong，Zhongyuan Jiang，Yu Zheng。相关的技术也已经获得了专利局授权[3]。
1. 问题背景
什么叫做实时可达区域？我们先给出一个系统展示例子(该系统读者可以通过链接http://r-area.urban-computing.com/访问)。如图1所示，当用户选择一个时间预算t，在地图上选择一个点q，该系统会返回从q点出发，t时间范围内，考虑到当前交通状况下，能够到达的路段。这些路段构成的区域称为实时可达区域。我们将这个过程称为实时可达区域分析。
图1 实时可达区域分析的系统展示
实时可达区域分析在很多城市应用中都非常有用：1)基于地点的推荐。如图2(a)所示，用户想要找到从他/她当前位置(红色五角星处)5分钟之内抵达的餐馆；2)车辆调度。如图2(b)所示，用户需要找到10分钟之内能够打上的出租车。出租车公司需要使用实时可达区域分析算法找到所有那些满足条件的出租车司机。此外，在一些紧急调度系统中实时可达区域分析也非常重要，例如，当一个地方发生车祸时，应该尽快通知那些20分钟内能够抵达事故现场的警车或者救护车。
图2 实时可达区域分析的应用场景
最基本的方法是利用基于欧式距离或者路网距离的静态空间范围查询找到可达区域范围，例如方圆1公里的区域范围。然而这种方法忽略了在不同时间段下交通状况的不同。一种较好的方法是，首先评估出每条路段的通行时间，然后利用路网扩张的方法找到实时可达区域范围。但是这种方法忽略了交叉路口的延迟，给出的空间范围也不准确。ICDE 2017年的一篇文章[1]提出了一种更好的找到可达区域范围查询的方法。它将历史同一时段经过查询点q的轨迹在t时间内经过的路段作为可达区域范围。但是它却忽略了实时的交通状况，例如影响交通的天气、车祸或者封路等信息。
于是我们想到，能否只用最近一段时间(例如最近半小时)产生的轨迹，采用文献[1]的技术来分析实时可达区域范围？因为最近一段时间的轨迹能够反映出交通状况信息。但是，由于在段时间内经过查询点q的轨迹数目很少，我们可能遇到低覆盖率的问题。如图3(a)所示，红色的区域明显可以抵达，但是由于最近一段之间内没有刚好经过出发点到达红色区域的轨迹，因此红色区域没有返回。为了解决这个问题，我们提出了一种轨迹拼接的技术，如图3(b)所示。如果两条轨迹同时经过了同一个地点，它们就能够相互拼接，例如轨迹tr3和tr4。
图3 实时轨迹的低覆盖率问题，以及解决思路
我们发现，通过轨迹拼接返回的可达区域与轨迹拼接的次数非常相关。令轨迹拼接的次数为k。如图4所示，当轨迹拼接次数越大时，返回的可达区域也越大，但是返回的区域就越不靠谱(我们称之为可靠性)。我们评估了利用轨迹评估道路通行时间误差与轨迹拼接的次数的关系，如图5所示。由图可知，当轨迹拼接的次数小于5时，通行时间的预估误差小于5%，这就保证了可达区域分析的高可靠性。
图4 轨迹拼接次数与可达区域大小之间的关系
图5 道路时间预估误差与轨迹拼接次数之间的关系
但是，我们仍然会遇到两个问题。1)如何确定具体的k值呢？2)轨迹拼接的引入，可能会带来组合爆炸的问题，因为轨迹可能在任何地方进行拼接。对于第一个问题，我们可以利用机器学习的技术来决定在不同时间、不同地点的最佳k值；对于第二个问题，我们可以构建有效的索引机制对搜索空间进行剪枝，提高查询分析效率。
2. 基本框架
图6是我们提出的解决方案的基本框架，其包含2个部分：离线学习阶段和在线处理阶段。在离线学习阶段，我们首先利用历史的轨迹信息产生学习的标签，然后从不同的数据源中抽取一些时空特征，最后训练k值预测模型。在线处理阶段，我们接受实时的轨迹数据，并用京东城市时空数据引擎JUST(http://just.urban-computing.cn)提供的能力对轨迹数据进行去噪和地图匹配。地图匹配后的轨迹一方面用于构建索引，另一方面，与其他的数据一起，抽取出一些实时时空特征，用于k值的预测。当用户的实时可达区域分析请求到来时，查询处理模块利用构建好的索引以及离线训练好的模型，快速分析用户查询点的实时可达区域。接下来，我们将分别详细介绍索引构建机制和k值预测技术。
图6 算法基本框架
3. 跳图索引(Skip Graph Index，SG Index)
为了高效支持任意轨迹拼接的实时可达区域分析，我们提出了一种新的索引，称之为跳图索引(SG Index)。SG Index的基本思想是，我们发现一些轨迹被另外的轨迹支配。例如图7(a)所示，轨迹tr4在路段C->B中比轨迹tr3更慢，我们称轨迹tr4在路段C->B上被tr3支配。保留轨迹tr4只会给我们带来计算复杂度的提升。基于此，我们仅仅利用那些任意两点之间最快的轨迹来构建SG Index。如图7(b)是轨迹数据集图7(a)所有的最快轨迹。本质上，SG Index是一个有向图，该图的每个节点对应与一条路段，每条边表示存在至少一条轨迹从起始路段到达终止路段，边上的权重表示两条路段的最少时间开支。给定一个轨迹数据库如图7(c)所示，我们可以构建出图7(d)的SG Index。
图7 跳图索引示例
利用SG Index，我们便可以将可达区域分析问题转化成图上k阶邻居的搜索问题。图8显示的是基于图7(d)从查询点q出发的查询搜索树，共有两种类型的节点：跳图扩展节点和路网连接节点。跳图扩展节点是基于SG Index往外不断扩展产生的，共有四个属性：路段id、从根节点到该节点的时间总开销tc、轨迹拼接次数kc(论文中有证明，kc可以不作存储，只是方便逻辑上的剪枝过滤)、搜索层级l。路网连接节点是基于跳图扩展节点和路段的邻接关系产生的，共有3个属性：路段的id、从根节点到该节点的时间总开销tc、层级l。注意到BFS的遍历顺序非常重要，因为基于此遍历顺序，我们更进一步地提出了一个剪枝策略来加速查询处理过程。对于每个扩展节点，我们有两个状态：搜索层级l和时间开销tc。如果其中一个扩展节点n的这两个状态都比另一个扩展节点n’的这两个状态小，那么我们称n支配节点n’，n’能够被安全地剪枝。在图8的例子当中，n9能够被剪枝，因为它被n5支配。
图8 SG Index 搜索树
4. k值预测
对k值预测的最大挑战是，在我们的数据集中，我们并没有轨迹拼接次数的标签。实际情况中，我们几乎也不可能获得这类标签。这就给我们采用有监督机器模型训练带来了挑战。基于此，我们提出了一种标签产生算法。如图9(a)所示，假设用户在t时刻q点触发一次实时可达区域查询，我们用一个时间窗口获得在这个时间窗口内经过q点的历史轨迹，这些轨迹进一步划分成两个轨迹子集T1和T2(这边δ是我们在实时分析中需要考虑的最近轨迹时间跨度，tb是用户指定的时间预算，对于1~20分钟的每个时间预算，我们分别会单独训练一个模型)。假设时间点t是用户触发的查询时间点，集合T1用来找到k次(k<=5)轨迹拼接的可达区域范围Ek(利用前述跳图索引技术)，集合T2用来找到不经过任何轨迹拼接找到的可达区域范围Egt，Egt可以看成真值的部分。对于所有满足不等式的Ek和Egt，我们选择最小的k作为标签。
图9 k标签产生过程
有了标签之后，我们从多种外部的数据中抽取q点周围时空特征。抽取的特征包括五类：1)交通特征，这些特征可以从历史轨迹中抽取出来，包括：交通流量，平均速度；2)时间特征，包括一天中的时刻、星期几、是否为节假日等；3)天气特征，例如降雨量、气温、天气状况(即阴、晴、雨等)；4)POI特征，即查询点周围1公里范围内不同种类(餐馆、公司、小区等)的POI的数目；5)路网特征，即查询点周围交叉路口的数目、不同道路等级的道路总长度等。图10展示了不同的特征条件下，k值的分布情况。例如，从图10(a)可知，交通流量较少的情况下，轨迹拼接的次数应该更少一些。
图10 k值随不同的特征分布情况
最后，我们将抽取到的时空特征输入到模型当中。我们采用了ST-ResNet模型[4]，因为这个模型既能够捕捉到时间的临近性、周期性和趋势性，也能够捕捉到空间的临近性和关联性。
5. 实验
我们采用了4个真实数据集验证本文提出的算法的有效性和效率。数据的统计如下图所示：
图11 实验中用到的数据统计
我们首先做了一个案例调研。图12(a)和(b)分别展示了用我们提出的方法在不同时间点找到的可达区域范围。虽然这两天都是周五，但是图(a)的可达区域范围比图(b)的要大的多。究其原因，是因为在2016年12月30日，著名女歌手王菲在上海梅赛德斯-奔驰文化中心举办了跨年演唱会，这段时间有大量的粉丝聚集在此，造成了严重的拥堵。说明我们提出的方法能够较好地捕捉实时交通状况的信息。而基于历史轨迹的方法[1]和基于通行时间预估的方法无法做到这一点，如图12(c)和图12(d)所示。
图12 王菲跨年演唱会的案例
我们还做了效率实验。其中SGE+是我们最终提出的方法，对比方法中有些是其他的索引方法，有些没有用到剪枝策略。由图可知，相对于其他方法来说，SGE+在效率方面有数量级的提升，能够在毫秒级别返回查询结果。
图13 效率性能对比
论文下载链接：
http://bucket.kangry.net/paper%2FDASFAA2020_ReachableArea.pdf
PPT下载链接：
http://bucket.kangry.net/0slides%2FR-Area-DASFAA2020.pptx
系统Demo链接：
http://r-area.urban-computing.com/
参考文献：
[1] Guojun Wu, Yichen Ding, Yanhua Li, Jie Bao, Yu Zheng, Jun Luo, Mining Spatio-Temporal Reachable Regions over Massive Trajectory Data. ICDE 2017.
[2] Ruiyuan Li, Jie Bao, Huajun He, Sijie Ruan, Tianfu He, Liang Hong, Zhongyuan Jiang, Yu Zheng. Discovering Real-time Reachable Area using Trajectory Connections. in 25th International Conference on Database Systems for Advanced Applications. (DASFAA 2020)
[3] 李瑞远，鲍捷，阮思捷，郑宇。一种用于确定可达区域的方法和装置，已授权，专利号：ZL 2018 1 0565693.7
[4] Junbo Zhang, Yu Zheng, Dekang Qi, Ruiyuan Li, Xiuwen Yi, Tianrui Li. Predicting citywide crowd flows using deep spatio-temporal residual networks[J]. Artificial Intelligence, 2018, 259: 147 – 166.