Mining Closed Numerical Patterns in Spatial Databases

隨著定位科技的日益普及，我們可以蒐集到大量的空間資料。因此，如何從空間資料庫中探勘出有意義的頻繁空間樣式，成為越來越熱門的研究議題。藉由資料探勘的技術，可以幫助我們在空間資料庫中發現封閉性的數值樣式，找出不同區域的之間的量化關係，進而了解或預測市場的趨勢。因此，在這篇論文中，我們提出一個有效率的探勘演算法叫「CNP-Mine」，藉以挖掘出在空間資料庫中封閉性數值樣式。CNP-Mine演算法主要可分為兩個階段。第一階段，我們產生出所有長度為1的頻繁樣式。在第二階段，我們以深度優先搜尋法的方式遞迴產生所有的頻繁樣式。在列舉的過程中，我們利用修剪策略刪除不必要的候選樣式。同時我們會對這些樣式做檢查，檢查它們是否為封閉性的樣式。由於CNP-Mine只需掃描投影資料庫，且能避免產生不必要的候選樣式，實驗結果顯示，我們所提出的方法比改良式的A-Close演算法，在執行速度與記憶體使用量上都有較佳的表現。With advance in positioning technology, a large amount of spatial data has been collected into databases. How to mine frequent spatial pattern has attracted more and more attention recently. Mining numerical patterns in spatial databases can help us identify the quantification relationships between different locations to understand or predict the trends of markets. Therefore, in this thesis, we propose a novel algorithm, CNP-Mine (Closed Numerical Pattern Mining), to mine the closed numerical patterns in a spatial database. The proposed algorithm consists of two phases. First, we find all frequent patterns of length one (1-patterns) in the database and generate their projected databases for each frequent 1-pattern found. Next, we use a frequent spatial pattern tree to recursively generate frequent patterns in a DFS manner until no more frequent closed patterns can be found. During the mining process, we employ several effective pruning strategies to prune unnecessary candidates and a closure checking scheme to remove non-closed patterns. Moreover, we localize the support counting and pattern joins in projected databases. Thus, the proposed method can efficiently mine closed numerical patterns in a spatial database. The experimental results show that the CNP-Mine algorithm outperforms the modified A-Close algorithm in several orders of magnitude