點集合資料庫中封閉性樣式之資料探勘

Abstract

隨著行動運算及定位技術的進步，位置定位服務（Location Based Services，LBS）也跟著蓬勃發展。透過定位裝置，我們可以將大量點座標資料搜集到點集合資料庫中，而點集合是由一些點座標所形成的集合。藉由資料探勘的技術，可以幫助我們在點集合資料庫中發現物體移動的經常路徑或行為。因此，這篇論文將探討如何在點集合資料庫中尋找經常出現的樣式或路徑，我們提出一個有效率的探勘演算法叫「PCP-Miner」，用來找尋點集合資料庫中的封閉性樣式。演算法主要可分為兩個階段。第一階段，我們產生出所有長度為2的頻繁樣式。第二階段，我們利用頻繁樣式樹以深先搜尋法的方式遞迴產生所有的頻繁樣式。在產生的過程中，我們會對這些樣式做檢查，檢查它們是否為封閉的。由於PCP-Miner只需掃描資料庫一次，且能避免產生不必要的候選樣式，實驗結果顯示，不管在合成資料或真實資料中，我們所提出的方法皆比改良式的Apriori演算法有效率。

With advance in mobile computing and positioning technologies, location-based services (LBS) have gained significant progress. By using these technologies, a large amount of pointsets can be collected in an LBS database where a pointset contains a set of points. Mining frequent pointset in a pointset database can help us understand the movement patterns of objects. In this thesis, we proposed a novel algorithm, PCP-Miner (Pointset Closed Pattern Miner), to mine frequent closed pointset patterns. Our proposed algorithm consists of two phases. First, we find all frequent patterns of length two in the database. Second, for each pattern found in the first phase, we recursively generate frequent patterns by a frequent pattern tree in a depth-first search manner. During the process of pattern generation, we check whether the frequent patterns are closed or not. Since the PCP-Miner only needs to scan the database once and doesn’t generate unnecessary candidates, it is more efficient than the modified Apriori algorithm. The experiment results show that the PCP-Miner outperforms the modified Apriori by one order of magnitude in both synthetic and real data.