基於使用者軌跡資料探勘個人化路徑

Abstract

現今大部分人常常駕駛在平時熟悉的路線，並且十分關心這些路線上的交通狀況。假如我們已經知道一個使用者的喜好路線，我們即可在事前提供使用者此路線的即時交通資訊，若有任何狀況，使用者可在事前改走其他道路去避免。然而，現今的一般導航系統在指定一個起點和目的地的情況下，大多著重於最短路徑或是最快路徑。在本文中，我們考慮到使用者個人化移動行為的模式，提出一個新的個人化路徑。此系統包括兩部分: personalized graph construction 以及 route planning。在第一部分，我們從使用者過去的移動軌跡資料中，探勘出familiar road segments，並且建造一個personalized graph。在第二部分，我們提出一個有效率的演算法，產生k條使用者的個人化路徑。在我們的實驗中，我們利用真實的使用者移動軌跡資料，驗證所提出個人化路徑規劃系統之效果與效能表現。此外，我們還和現存的演算法去做比較，比較的內容包括了效能和結果品質，實驗的結果證實所提出的系統架構與演算法確實能有效率地找出使用者個人化移動喜好路徑。

Most people usually drive their familiar routes to work and are concerned about the traffic on their ways to work. If a driver's preferred route is known, the traffic congestion information on his/her way to work will be early reported and the driver will avoid it in time. However, the navigation system nowadays focus on planning the shortest path or the fastest path from a given start point to a given destination point. In this paper, we introduce a novel personalized route planning system with considering user driving behaviors. The proposed system comprises two components, personalized graph construction and route planning. In the first component, we will mine familiar road segments from a driver's historical trajectory dataset, and construct a personalized graph. For the second component, we propose an efficient route planning algorithm to generate top-k familiar routes with the graph while a query, including a start point and a destination point, is on-line issued. We evaluate the performance of our algorithm by a real-world dataset and compare our algorithm with an existing approach in terms of effectiveness and efficiency.