探勘頻繁移動軌跡樣式

Mining Frequent Trajectory Patterns

陳怡安(Yi-An Chen)

指導教授 ： 李瑞庭

國立臺灣大學/管理學院/資訊管理學研究所/博士(2011年)

https://doi.org/10.6342/NTU.2011.00801

摘要

本論文提出三個探勘移動軌跡樣式的演算法: GBM、 FTM 及LTM。GBM 尋找由空間中連續的格點組成的樣式，而格點間的時間延遲則由時間間隔代表。FTM 探勘彈性移動軌跡樣式，其中樣式的格點不一定要連續，格點間的時間延遲則以區段代表。雖然以點序列來描述軌跡可以有效降低雜訊以及簡化整個探勘的程序；但亦可能產生過長的樣式，以致於需要耗費大量的時間進行探勘的工作。因此，LTM利用連續的線段代表物體的移動軌跡，它可以有效的降低記憶體的耗用、樣式的長度與頻繁樣式的數量，進而提升探勘的效率。
這三個方法皆採用深先演算法進行樣式探勘。GBM 利用樣式相鄰兩點鄰近的特性有效地降低搜尋空間。FTM則利用”頻繁邊”以避免不必要的樣式延伸。而LTM則使用兩個修剪策略, CU-Bound 與 FU-Bound 有效提升探勘的效率。
為了評估GBM、 FTM 和LTM 三個演算法，我們進行了大量的實驗。實驗結果顯示，GBM 的效率明顯優於Apriori-G與PrefixSpan-G。FTM 相較於Apriori-F 及PrefixSpan-F，亦在效能上亦有明顯的提升。LTM則能利用CU-Bound 及FU-Bound 兩種修剪策略明顯加速探勘的程序。

關鍵字

資料探勘 ； 移動軌跡樣式 ； 彈性移動軌跡樣式 ； 線段軌跡樣式 ； 軌跡資料庫

並列摘要

In this dissertation, we propose three algorithms, GBM, FTM and LTM, for mining trajectory patterns. GBM focuses on finding frequent trajectory patterns consisting of consecutively adjacent points, where the time spent between two consecutive points in a frequent trajectory pattern is represented by a timespan. FTM mines frequent flexible trajectory patterns, where the consecutive points in a flexible pattern are not necessarily adjacent and the time spent between two consecutive points is denoted by a time interval. Although representing a trajectory pattern by a sequence of points is ideal to reduce the effect of noises and ease the mining process, these approaches may lead to generating long patterns and requiring a tremendous amount of mining time. Therefore, LTM models trajectories and patterns as consecutive line segments rather than discrete points so that the memory consumption, the lengths and number of frequent patterns can be effectively reduced.
All these three algorithms mine frequent patterns in a depth-first search (DFS) manner. GBM utilizes the adjacency property to effectively reduce the search space, while FTM employs frequent edges to prune unnecessary patterns. LTM uses two pruning strategies, CU-Bound and FU-Bound, to speed up the mining process.
Extensive experiments are conducted to evaluate the performance of GBM, FTM and LTM. The experimental results show that GBM significantly outperforms Apriori-G and PrefixSpan-G. FTM also gains considerable improvement in efficiency in comparison to Apriori-F and PrefixSpan-F. LTM effectively speeds up the mining process by using both CU-Bound and FU-Bound pruning strategies.

並列關鍵字

Data mining ； trajectory pattern ； flexible trajectory pattern ； line-based trajectory pattern ； trajectory database

參考文獻

[2] R.C. Agarwal, C.C. Aggarwal, V. Prasad, A tree projection algorithm for generation of frequent item sets, Journal of Parallel and Distributed Computing, Vol. 61, No. 3, 2001, pp. 350-371.

[3] A.K. Akasapu, L. K. Sharma, G. Ramakrishna, Efficient trajectory pattern mining for both sparse and dense dataset, International Journal of Computer Applications, Vol. 9, No. 5, 2010, pp. 45-48.

[5] S. Brakatsoulas, D. Pfoser, N. Tryfona, Modeling, storing and mining moving object databases, Proceedings of Database Engineering and Applications Symposium, 2004, pp. 68-77.

[6] H. Cao, N. Mamoulis, D.W. Cheung, Mining frequent spatio-temporal sequential patterns, Proceedings of the 5th IEEE International Conference on Data Mining, 2005, pp. 82-89.

[7] H. Cao, N. Mamoulis, D.W. Cheung, Discovery of collocation episodes in spatiotemporal data, Proceedings of the Sixth IEEE International Conference on Data Mining, 2006, pp. 823-827.