JUST技术：驻留点应用及经典检测算法解析

JUST

作者：阮思捷

京东数科JUST团队原创，转载请获得授权

随着定位技术的不断普及，嵌入在手机和PDA设备内的GPS、北斗等位置传感器周期性地记录移动对象的位置，从而产生了海量的轨迹数据。用户为分享行程可能主动记录自己的轨迹，物流派送车、出租车、共享私家车等由于运营监管的需要可能被动地记录轨迹位置信息。

这些轨迹数据背后的想象空间极大。利用轨迹数据，我们可以用来估计全城的车流量、通行时间、补全现有地图等等。而为实现这些应用，我们通常会对轨迹数据进行预处理，剔除掉一些时间连续且空间上非常临近的点（下文简称驻留点），因为驻留点会影响上述应用的精确度。

然而，这些被丢掉的驻留点也隐含了丰富的信息。利用检测得到的驻留点，如图1所示，我们可以进行事件分析、地点发现、序列挖掘等等。本文，我们将带大家探索驻留点背后的故事，以及介绍一些经典的驻留点检测算法。

图1 轨迹驻留点的检测及应用

一、 驻留点应用

1.事件分析

移动对象往往会因为某些事件而停留，比如车辆会因为加油而停留、快递员因为配送而停留等等。通过分析移动对象在特定POI（兴趣点）驻留的时长和时间，我们可以分析POI的特性，助力决策。

在[1-2]中，作者将出租车轨迹中的驻留点（图2）与加油站POI进行关联，利用提出的方法，能够估计每个加油站每个时间片的平均加油等待时间，用于推荐加油地点，以及推测每个加油站每个时间片的访问车辆数，从而推测出全城实时的油耗。

图2 汽车加油事件 [1-2].

在[3]中，作者将配送员轨迹中的驻留点与客户的妥投地点做关联（图3），利用提出的方法能够自动推测出每个运单的妥投时间。该种方法不仅减轻了配送员的负担，而且结果比手工记录更为可靠。准确的妥投时间能够用于挖掘用户可收货的时间窗口，提高妥投成功率等等。

图3 配送员轨迹数据及运单收货地址 [3].

2. 地点发现

驻留点在空间上反映为一个GPS点密度较高的区域，这些区域可能是一些POI数据库中没有记录的但是又非常有意义的地点。我们可以通过DBSCAN、OPTICS等聚类算法对检测得到的驻留点进行聚类，生成一系列地点，再通过其与多源数据关联，筛选得到真正感兴趣的地点。

在[4-5]中，作者基于行人的出行轨迹数据，发现了城市内一些兴趣地点（图4），可以推荐给外地游客游玩。

图4 兴趣地点 [4-5].

在[6-7]中，作者从出租车轨迹中检测得到驻留点，将其聚类后得到一系列可以停车接客的地点。这些地点后续可被推荐给空车司机，让其前往接客，也可以推荐给用户，使其更容易打到车。

在[8]中，数据挖掘人员基于危化品运输车辆轨迹中的驻留地点以及周围路网、POI特征，寻找异常地点，工作人员到现场核查发现多起非法生产、存储等现象。

在[9]中，数据挖掘人员基于货车轨迹中的驻留点及卫星图像等信息，发现未记录在案的仓库。这些本地仓库通常由当地人搭建用于临时存储货物。知晓这些仓库的存在，对于后续物流地产的选址，具有指导意义。 

3.序列挖掘

通过分析驻留点与驻留点之间的转移关系，我们可以得到移动对象的位置访问序列。通过累计历史上的访问序列数据，我们可以得到一系列频繁序列。这些序列隐藏着人们关于出行的知识。

在[10]中，作者挖掘了个人的序列生活模式，用于做好友推荐。

在[4-5]中，作者通过挖掘行人的驻留点访问序列，得到了一个指定地理范围内多条典型的出行序列，使我们对周围环境有了更好的了解。这些访问序列还能够赋能出行推荐。

图5. 经典访问序列 [4-5]

二、 常用驻留点检测算法

通过了解上面这些应用，我们知道驻留点是轨迹中的一类重要知识，但是从轨迹中检测出驻留点其实并不困难。在对轨迹进行初步的去噪后，我们就可以进行驻留点检测了。下面我们将介绍一种简单易实现的驻留点检测算法[11]。

这种驻留点检测算法首先检查一个锚点以及它后继轨迹点的距离是否大于一个给定的距离阈值 。以图6为例，当前的锚点是 以内的后续轨迹点。然后，检测算法计算锚点 以内最后一个后继轨迹点 之间的时间跨度。如果时间跨度大于一个指定的时间阈值 ，我们即检测得到一个驻留点 ，然后锚点移动到当前驻留点后的下一个点，即 。否则，锚点向前移动一步 。这个过程不断重复，直到锚点移动到轨迹序列末尾，我们即检测得到整条轨迹中的所有驻留点。

图6 驻留点检测示意图

目前，这种简单有效的驻留点检测算法已经集成在京东时空数据引擎JUST [12]中，封装成DAL的形式，用户只需要编写简单类SQL语句，如图7所示，就可以从轨迹数据集中方便高效地检测得到驻留点。

图7. 驻留点检测类SQL语句

在一些研究[1-3][6-7]中，为了保证检测结果（加油事件、停车等客事件、妥投事件）的质量，基于监督学习的模型可以被进一步使用在检测得到的驻留点上。通过提取驻留点中的一些特征，可以过滤得到只属于某一类特定事件的驻留点，让后续分析变得更为准确。

三、 总结

以上就是本次驻留点应用及经典算法的分享。通过本文，我们了解了驻留点的一些重要应用。通过其与路网、POI、卫星图像等的关联分析，我们可以发现很多有趣的知识。未来，JUST将集成更多关联筛选的功能，快速从数据中得到洞察。

参考文献：

[1] Zhang, Fuzheng, et al. "Sensing the pulse of urban refueling behavior." Proceedings of the 2013 ACM international joint conference on Pervasive and ubiquitous computing. 2013.

[2] Zhang, Fuzheng, et al. "Sensing the pulse of urban refueling behavior: A perspective from taxi mobility." ACM Transactions on Intelligent Systems and Technology (TIST) 6.3 (2015): 1-23.

[3] Ruan, Sijie, et al. "Doing in One Go: Delivery Time Inference Based on Couriers' Trajectories." Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020.

[4] Zheng, Yu, et al. "Mining interesting locations and travel sequences from GPS trajectories." Proceedings of the 18th international conference on World wide web. 2009.

[5] Zheng, Yu, and Xing Xie. "Learning travel recommendations from user-generated GPS traces." ACM Transactions on Intelligent Systems and Technology (TIST) 2.1 (2011): 1-29.

[6] Yuan, Jing, et al. "Where to find my next passenger." Proceedings of the 13th international conference on Ubiquitous computing. 2011.

[7] Yuan, Jing, et al. "T-finder: A recommender system for finding passengers and vacant taxis." IEEE Transactions on knowledge and data engineering 25.10 (2012): 2390-2403.

[8] “京东城市”微信公众号. “一屏联动64个部门，京东城市助力南通建成全国首个市域治理现代化指挥中心”, 2020.

[9] 麻志鹏，等. “查找仓库的方法和装置” 中国专利（已授权）, 2019.

[10] Ye, Yang, et al. "Mining individual life pattern based on location history." 2009 tenth international conference on mobile data management: Systems, services and middleware. IEEE, 2009.

[11] Zheng, Yu. "Trajectory data mining: an overview." ACM Transactions on Intelligent Systems and Technology (TIST) 6.3 (2015): 1-41.

[12] https://just.urban-computing.cn/