基於歷史軌跡資料探勘相關停留區域

Abstract

隨著具有GPS定位功能的設備越來越廣泛的被使用，如：GPS定位器、智慧型手機及導航機，大量的軌跡資料可以被收集，並且使用者可以藉由上傳他們的軌跡資料以獲得基於地點的服務。預測使用者下一個可能停留的位置對使用者是很有幫助的，當這些相關停留區域被探勘出來，一些交通狀況、商家廣告、旅遊景點推薦等關於下一個停留位置的地點服務將可以被提供。先前關於位置預測的研究都是從整群的軌跡資料中發掘停留區域並找出區域與區域間的關係來描述使用者的移動模式。然而，我們認為軌跡資料即使經過相同的區域並不代表擁有相似的移動行為。 此論文中，我們提出一個系統架構來探勘關於特定移動行為的停留區域並且用於位置預測，包含兩個部分：Region Modeling以及Mobility Prediction。對於Region Modeling，我們提出軌跡分群法將相似形狀的軌跡分群，並且從分群的結果中發掘停留區域；對於Mobility Prediction，我們提出挑選軌跡群的演算法及預測策略來找出最佳k個相關停留區域。 我們利用了實際資料進行相關實驗，結果顯示我們的方法可以有效地預測停留位置，且準確度達到接近60%，而nDCG評估也可以達到80%。

With increasingly prevalent mobile positioning devices, such as GPS loggers, smart phones, and GPS navigation devices, a huge amount of trajectories data is collected. Users are able to obtain the various location-based services by uploading their trajectories. Predicting the next region the user may possibly stay is very useful. Once a set of stay regions discovered, traffic status, targeted advertises, sightseeing recommendations, and other location-based information of the next stay can be provided in advance. Prior works have elaborated on discovering stay region from the whole crowd trajectories and then exploring the relations between the regions to describe the movement patterns for location prediction. However, the trajectories pass the same region may not have the similar movement behavior. In this paper, we propose a framework to discover stay regions relevant to the specific movement behavior and then applied in location prediction, called Region Modeling and Mobility Prediction. The proposed framework includes two modules: region modeling and mobility prediction. In the region modeling module, we develop shape-clustering method to group the similar trajectories from historical data and then explore the stay region model from trajectory clusters. Based on the discovered region model, the mobility prediction module provide a cluster selection algorithm and several prediction strategies to generate the top-k relevant stay regions. In an experimental evaluation, We evaluated the prediction method by using labeled ground truth. The experimental results show that the prediction accuracy of our method can reach 60% and nDCG is more than 80% .