從地點紀錄探勘時空語意軌跡模式

Abstract

隨著GPS裝置以及智慧型手機的普及，人們能很輕易的記錄自己每天的活動路徑，也使得從行動記錄來挖掘移動路徑模式的研究蓬勃發展。移動路徑模式的資訊包含熱門地點以及移動的順序。然而，這類研究所專注的移動模式並不包含時間或語意的資訊，為了賦予移動模式更多的資訊，在這篇研究中，我們提出了 STS-TP，一種包含時間、空間、語意資訊的軌跡模式。給定一定數量的地點記錄，我們試圖從中找出包含時間、空間、語意資訊的移動軌跡模式。對於蒐集頻率高的的軌跡資料，我們使用了著名的 PrefixSpan 方法來找出其中的STS-TP，對於蒐集頻率低的地點資料(例如：打卡資料等)，我們提出了D-TPMiner 演算法來找出其中的移動軌跡模式；又因為 PrefixSpan 演算法的輸入型態必須是經過標記的串列資料，於是我們提出了SS以及進階的ASS演算法來對資料進行標記。更進一步，我們也定出了查詢的機制使得我們可以利用 STS-TP 來預測人們移動的行為以及其中所包含的資訊。最後，我們使用了在 Google 以及 Foursquare 的真實資料進行了實驗來驗證我們的方法，藉由可用性以及效率兩方面的實驗，證明了我們提出的方法確實能有效的達到上述的目的。

With the development of GPS and the popularity of smart phones and wearable devices, users can easily log their daily trajectories. Prior works have elaborated on mining trajectory patterns from raw trajectories. Trajectory patterns consist of hot regions and the sequential relationships among them, where hot regions refer to the spatial regions with a higher density of data points. However, trajectory patterns do not have explicit time information or semantic information. To enrich trajectory patterns, we propose STS-TPs (standing for Spatial-Temporal Semantic Trajectory Patterns) which refer to the moving patterns with spatial, temporal, and semantic attributes. Given a set of location log sets, we aim at mining STS-TPs, where each STS-TP should fulfill the three criteria: (1) temporal dependency, (2) spatial proximity, and (3) semantic consistency. Explicitly, we extract the three attributes from location log, and convert these logs into semantic trajectory sequences. Given a set of such semantic trajectory sequences, STS-TPs could be viewed as sequential patterns with multiple attributes. For high sampling rate location data, which can be viewed as raw trajectory, to fully explore the efficiency of PrefixSpan on sequential pattern mining, we propose a PrefixSpan-based algorithm (abbreviated as PS), and, also, we propose Distinct Temporal-Pattern Miner (D-TPMiner) algorithm for low sampling rate location log such as check-in data to discover STS-TPs. Note that the input for PrefixSpan is a set of sequences consisting of items. However, each item of semantic trajectory sequences contains three attributes, and we need to further transform these sequences into symbolized sequences before using PrefixSpan. Therefore, we propose two algorithms of Sequence Symbolization (SS) and Advanced Sequence Symbolization (ASS) to achieve this purpose. In light of STS-TPs, we further propose query tasks to predict users’ behaviors. To evaluate our proposed algorithms, we conducted experiments on the real datasets of Google Location History and Foursquare check-in data. Experimental results show the effectiveness and efficiency of our proposed algorithms.