利用個人移動軌跡探勘潛藏之使用者社群

Abstract

隨著定位技術發展與行動裝置普及，使用者能輕易地收集所走過的路徑，並能透過所收集的路徑，更清楚地表達其生活經驗，許多與路徑相關的社群網站紛紛因此而建立，促使我們希望利用能表達使用者生活經驗的路徑，來找尋具有相似移動模式的使用者社群。我們提出一個完整的架構來尋找使用者社群。首先，我們利用所收集路徑來找出經常經過的區域，再將原有的路徑轉換為常經過區域的序列。接著，利用轉換過的序列，替每一個使用者建立能捕捉其行為模式的sequential pattern tree (簡稱為SP-tree)。然後，制定出兩個SP-tree間的相似程度，以得知兩個使用者間相似關係。最後，根據前一步驟所找出的使用者間相似關係，提出找尋使用者社群的COST演算法，將具有相似移動模式的使用者分成一個社群。為了要驗證我們的方法，我們提出完整的實驗來證明，實驗結果顯示我們提出來的方法可以反應使用者的行為模式外，也能正確的找出使用者社群。

With the rapid development of positioning techniques (e.g., GPS), users can easily collect their trajectories. Furthermore, with the growth of Web 2.0, many community web sites allow users to share their own trajectories and search trajectories that they are interested in. To provide more insights into these raw trajectories, in this paper, we target the problem of discovering user communities where users in the same community have similar moving behaviors. First, we transform raw trajectories into sequences of frequent regions. Then, we adopt a sequential pattern tree (abbreviated as SP-tree) as a trajectory profile to find and organize user trajectory patterns. We further formulate a similarity function to measure similarities among trajectory profiles of users. Based on the similarity measurements, we construct a cost function to discover user communities. To evaluate our proposed methods, we conduct comprehensive experiments. The experimental results show that the trajectory profile can effectively reflect user moving behavior, and our proposed methods can accurately identify communities among users.