時空資料庫中頻繁路徑之資料探勘

Abstract

隨著追蹤和定位技術的進步以及定址服務的大規模普及化，使得時空資料庫中的資料量大幅成長。隱藏在時空資料庫中的知識可被應用在各種不同的領域中，利用資料探勘方法在時空資料庫中找出頻繁路徑，可以讓我們了解資料庫中物件的移動特性。因此，在本論文中，我們提出一個二階段式的演算法來探勘時空資料庫中的所有頻繁路徑。在第一階段，我們建立一個對應圖和一系列的路徑資訊串列。在第二階段，我們利用對應圖和路徑資訊串列來找出資料庫中所有頻繁路徑。我們所提出的演算法不會產生不必要的候選樣式，且可以減少資料庫的掃描次數，並利用所有路徑必須是連續的特性以減小搜尋空間。因此，我們的方法比改良式PrefixSpan的方法更有效率。實驗結果顯示，不管在人造資料或真實資料上，我們的方法比改良式PrefixSpan的方法快上約二至九倍。

With advances in tracking technologies and great diffusion of location-based services, a large amount of data has been collected in a spatial-temporal database. The implicit knowledge in a spatial-temporal database can be used in many application areas and mining frequent trajectories in the spatial-temporal database can help us understand the movements of objects. Therefore, in this thesis, we propose a novel algorithm to mine the frequent trajectory patterns in a spatial-temporal database. Our proposed method consists of two phases. First, we transform all trajectories in the database into a mapping graph. For each vertex in the mapping graph, we record the information of the trajectories passing through the vertex in a data structure, called Trajectories Information lists (TI-lists). Second, we mine all frequent patterns from the mapping graph and TI-lists in a depth-first search manner. Our proposed method doesn’t generate unnecessary candidates, needs fewer database scans, and utilizes the consecutive property of trajectories to reduce the search space. Therefore, our proposed method is more efficient than the PrefixSpan-based method. The experiment results show that our proposed method outperforms PrefixSpan-based method by one order of magnitude in synthetic data and real data.