利用移動物體軌跡中之線索藉由分群及彙整技術探勘物體之移動模式

CACT : Clustering and Aggregating Clues of Trajectories for Trajectory Patterns

黃琬婷(Wan-Ting Huang)

指導教授 ： 彭文志

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00406

摘要

移動模式代表的是移動物體經常出現的一連串區域串列，其挑戰議題之一即是如何決定這些具代表性的區域。在真實世界中有許多原因如取樣方式、取樣頻率，機器限制，會使得軌跡資料難以描繪真實世界的移動行為。這將使得現有探勘物體之移動模式的方法難以找出準確的代表區域，同時也無法探勘出準確的移動模式。然而，即使軌跡資料只能反映出片段的移動行為，它們仍舊藏有一些關於完整之移動行為的線索。在本論文中我們提出了一個演算法ＣＡＣＴ，利用這些線索自給定的軌跡資料中探勘出移動模式。首先我們會提出對真實世界軌跡資料的觀察，由這些觀察我們設計了新的相似度來衡量兩條軌跡資料的相似程度。為了解決單一移動物體可能擁有多種移動行為的情況，我們設計了分群演算法，利用軌跡資料中的線索將代表不同移動行為的軌跡區分成不同的群組。最後我們設計了一個彙整演算法，利用軌跡資料中的線索將處在同群組中的多條片段軌跡聚合起來，重新建構成一連串具有代表性的區域串列，以描繪移動物體的移動模式。

關鍵字

軌跡 ； 移動模式 ； 資料探勘

並列摘要

Nowadays, many positioning devices and techniques are more and more popular such that there are a lot of trajectories of people or vehicles can be easily obtained. From such a huge amount of trajectories collected, discovering trajectory patterns can benefit many potential and novel applications. In general, trajectory patterns indicate sequences of frequent regions that a user usually appears. One of the challenge issues in trajectory pattern mining is how to define frequent region units in trajectory patterns. In reality, there are many factors, such as sampling method, sampling frequency and device constraints, will affect the capability of original trajectory data capturing the actual movements. Thus, if the original trajectory data only coarsely capture actual movements of a user, prior works cannot accurately identify frequent regions, let alone deriving trajectory patterns. However, even if trajectories can only reflect partial movements of a user, they reveal some clues about the moving behaviors hidden in trajectories. Consequently, in this paper, given a set of trajectories, we propose an algorithm CACT (standing for Clustering and Aggregating Clues of Trajectories) for discovering trajectory patterns by exploiting such 'clues'. Exploiting the clues of trajectories, we first propose the similarity measurement for two trajectories by tolerating certain spatiotemporal bias. Furthermore, to deal with the existence of multiple moving behaviors in trajectories, we propose a clustering algorithm to divide trajectories with similar moving behaviors into several groups. For each group, we further propose an algorithm to derive a sequence of frequent regions with their corresponding representative line segments. To the best of our knowledge, this is the first work that claims to cluster trajectories into groups first and then derive the corresponding frequent regions within each group. Through experimental studies on both synthetic and real datasets, we show that our approach is able to capture the trajectory patterns, while handling the partial information of trajectories (i.e., the clues) and avoiding the inaccuracy problem of frequent region determination.

並列關鍵字

trajectory ； data mining ； spatiotemporal

參考文獻

[2] MapMyRun Website. [available] http://www.mapmyrun.com.

[4] L. C. 0002 and R. T. Ng. On The Marriage of Lp-norms and Edit Distance. In Proc. of

[6] H. Cao, N. Mamoulis, and D. W. Cheung. Mining Frequent Spatio-Temporal Sequential

[7] L. Chen, M. T.  Ozsu, and V. Oria. Robust and Fast Similarity Search for Moving Object

[8] F. Giannotti, M. Nanni, and D. Pedreschi. E±cient Mining of Temporally Annotated