? ? ? ?隨著定位技術的不斷普及，嵌入在手機和PDA設備內的GPS、北斗等位置傳感器周期性地記錄移動對象的位置，從而產生了海量的軌跡數(shù)據(jù)。用戶為分享行程可能主動記錄自己的軌跡，物流派送車、出租車、共享私家車等由于運營監(jiān)管的需要可能被動地記錄軌跡位置信息。
這些軌跡數(shù)據(jù)背后的想象空間極大。利用軌跡數(shù)據(jù)，我們可以用來估計全城的車流量、通行時間、補全現(xiàn)有地圖等等。而為實現(xiàn)這些應用，我們通常會對軌跡數(shù)據(jù)進行預處理，剔除掉一些時間連續(xù)且空間上非常臨近的點（下文簡稱駐留點），因為駐留點會影響上述應用的精確度。
然而，這些被丟掉的駐留點也隱含了豐富的信息。利用檢測得到的駐留點，如圖1所示，我們可以進行事件分析、地點發(fā)現(xiàn)、序列挖掘等等。本文，我們將帶大家探索駐留點背后的故事，以及介紹一些經典的駐留點檢測算法。
一、?駐留點應用
1.事件分析
移動對象往往會因為某些事件而停留，比如車輛會因為加油而停留、快遞員因為配送而停留等等。通過分析移動對象在特定POI（興趣點）駐留的時長和時間，我們可以分析POI的特性，助力決策。
在[1-2]中，作者將出租車軌跡中的駐留點（圖2）與加油站POI進行關聯(lián)，利用提出的方法，能夠估計每個加油站每個時間片的平均加油等待時間，用于推薦加油地點，以及推測每個加油站每個時間片的訪問車輛數(shù)，從而推測出全城實時的油耗。
在[3]中，作者將配送員軌跡中的駐留點與客戶的妥投地點做關聯(lián)（圖3），利用提出的方法能夠自動推測出每個運單的妥投時間。該種方法不僅減輕了配送員的負擔，而且結果比手工記錄更為可靠。準確的妥投時間能夠用于挖掘用戶可收貨的時間窗口，提高妥投成功率等等。
2.?地點發(fā)現(xiàn)
駐留點在空間上反映為一個GPS點密度較高的區(qū)域，這些區(qū)域可能是一些POI數(shù)據(jù)庫中沒有記錄的但是又非常有意義的地點。我們可以通過DBSCAN、OPTICS等聚類算法對檢測得到的駐留點進行聚類，生成一系列地點，再通過其與多源數(shù)據(jù)關聯(lián)，篩選得到真正感興趣的地點。
在[4-5]中，作者基于行人的出行軌跡數(shù)據(jù)，發(fā)現(xiàn)了城市內一些興趣地點（圖4），可以推薦給外地游客游玩。
在[6-7]中，作者從出租車軌跡中檢測得到駐留點，將其聚類后得到一系列可以停車接客的地點。這些地點后續(xù)可被推薦給空車司機，讓其前往接客，也可以推薦給用戶，使其更容易打到車。
在[8]中，數(shù)據(jù)挖掘人員基于?；愤\輸車輛軌跡中的駐留地點以及周圍路網、POI特征，尋找異常地點，工作人員到現(xiàn)場核查發(fā)現(xiàn)多起非法生產、存儲等現(xiàn)象。
在[9]中，數(shù)據(jù)挖掘人員基于貨車軌跡中的駐留點及衛(wèi)星圖像等信息，發(fā)現(xiàn)未記錄在案的倉庫。這些本地倉庫通常由當?shù)厝舜罱ㄓ糜谂R時存儲貨物。知曉這些倉庫的存在，對于后續(xù)物流地產的選址，具有指導意義。?
3.序列挖掘
通過分析駐留點與駐留點之間的轉移關系，我們可以得到移動對象的位置訪問序列。通過累計歷史上的訪問序列數(shù)據(jù)，我們可以得到一系列頻繁序列。這些序列隱藏著人們關于出行的知識。
在[10]中，作者挖掘了個人的序列生活模式，用于做好友推薦。
在[4-5]中，作者通過挖掘行人的駐留點訪問序列，得到了一個指定地理范圍內多條典型的出行序列，使我們對周圍環(huán)境有了更好的了解。這些訪問序列還能夠賦能出行推薦。
二、?常用駐留點檢測算法
通過了解上面這些應用，我們知道駐留點是軌跡中的一類重要知識，但是從軌跡中檢測出駐留點其實并不困難。在對軌跡進行初步的去噪后，我們就可以進行駐留點檢測了。下面我們將介紹一種簡單易實現(xiàn)的駐留點檢測算法[11]。這種駐留點檢測算法首先檢查一個錨點以及它后繼軌跡點的距離是否大于一個給定的距離閾值以圖6為例，當前的錨點是p3,p4到p6是在Dmax以內的后續(xù)軌跡點。然后，檢測算法計算錨點p2到Dmax以內最后一個后繼軌跡點p6之間的時間跨度。如果時間跨度大于一個指定的時間閾值Tmin，我們即檢測得到一個駐留點（p3到p6），然后錨點移動到當前駐留點后的下一個點，即p7。否則，錨點向前移動一步p4。這個過程不斷重復，直到錨點移動到軌跡序列末尾，我們即檢測得到整條軌跡中的所有駐留點。
目前，這種簡單有效的駐留點檢測算法已經集成在京東時空數(shù)據(jù)引擎JUST [12]中，封裝成DAL的形式，用戶只需要編寫簡單類SQL語句，如圖7所示，就可以從軌跡數(shù)據(jù)集中方便高效地檢測得到駐留點。
????在一些研究[1-3][6-7]中，為了保證檢測結果（加油事件、停車等客事件、妥投事件）的質量，基于監(jiān)督學習的模型可以被進一步使用在檢測得到的駐留點上。通過提取駐留點中的一些特征，可以過濾得到只屬于某一類特定事件的駐留點，讓后續(xù)分析變得更為準確。
三、?總結
以上就是本次駐留點應用及經典算法的分享。通過本文，我們了解了駐留點的一些重要應用。通過其與路網、POI、衛(wèi)星圖像等的關聯(lián)分析，我們可以發(fā)現(xiàn)很多有趣的知識。未來，JUST將集成更多關聯(lián)篩選的功能，快速從數(shù)據(jù)中得到洞察。
參考文獻：
[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] “京東城市”微信公眾號. “一屏聯(lián)動64個部門，京東城市助力南通建成全國首個市域治理現(xiàn)代化指揮中心”, 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/
相關文章：
