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