写点什么

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

2020 年 12 月 19 日

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/


本文转载自:京东数科技术说(ID:JDDTechTalk)

原文链接:JUST技术:驻留点应用及经典检测算法解析

2020 年 12 月 19 日 08:00669

评论

发布
暂无评论
发现更多内容

第五周作业

小兵

Java核心基础——动态代理、静态代理

老农小江

java基础 代理模式

架构师3期3班-week1-总结

zbest

总结 week1

第九周课后练习

高兵

架構師訓練營 week9 作業

ilake

Python进阶——如何实现一个装饰器?

Kaito

Python

一致性HASH算法和相关测试

DL

week09作业

追风

架构师一期

架构师训练营第五周作业1

韩儿

Week5 - 技术选型 - 缓存,队列,负载均衡

evildracula

学习 架构

第五周作业一

lithium

架构师3期3班-week1-作业

zbest

作业 week1

架構師訓練營第 1 期 - 第 09 周總結

Panda

架構師訓練營第 1 期

深入理解r2dbc-mysql

程序那些事

响应式编程 R2DBC 程序那些事 响应式数据库 r2dbc-myql

架构师训练营第九周总结

_

极客大学架构师训练营 第九周总结

架构作业--第九周

Nick~毓

第五周-作业一

Geek_0b0f83

架构师训练营第 1 期第九周作业

Leo乐

极客大学架构师训练营

native关键字作用到底是什么?

秦怀杂货店

Java 源码 源码刨析 native

架构一期第九周作业

Airs

架构师训练营 1 期 -- 第九周总结

曾彪彪

极客大学架构师训练营

架構師訓練營第 1 期 - 第 09 周作業

Panda

架構師訓練營第 1 期

架构师训练营第五周学习笔记

李日盛

笔记

架构师训练营第五周作业

李日盛

架构师入门学习感悟五

莫问

架构师训练营第 1 期 - 第 9 周课后练习

Anyou Liu

极客大学架构师训练营

架构师训练营第五周作业2

韩儿

架構師訓練營 week9 總結

ilake

微服务手册:分库分表从分析到实践,不再停留只会说分库分表

互联网应用架构

分库分表

关于开发排期

张明森

架构师训练营第 1 期 - 第 9 周学习总结

Anyou Liu

极客大学架构师训练营

微服务架构下如何保证事务的一致性

微服务架构下如何保证事务的一致性

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