時空資料庫中封閉性數值樣式之資料探勘

Abstract

時空資料庫中樣式的資料探勘，可以幫助我們了解地理位置上分布不同的目標物或是事件的連續變化趨勢。因此，在這篇論文中，我們提出一個有效率的探勘演算法叫「STP-Mine」，用來找尋時空資料庫中的封閉性數值樣式。演算法主要可分為三個階段。第一階段，我們產生出所有長度為1的頻繁樣式及其映射資料庫。第二階段，我們利用頻繁樣式樹在空間維度上以深先搜尋法的方式遞迴產生所有的頻繁樣式。第三階段，我們利用頻繁樣式樹在時間維度上以深先搜尋法的方式遞迴產生所有的頻繁樣式。第二、第三階段的步驟將不斷地遞迴進行，直到沒有頻繁時空樣式被產生為止。在探勘的過程中，我們利用一些有效的修剪策略，以避免產生不必要的候選樣式，並檢查所產生的樣式是否為封閉的樣式。實驗結果顯示，不論在合成資料或真實資料中，我們所提出的方法皆優於改良式的A-Close演算法。

Mining spatial-temporal patterns can help us retrieve valuable and implicit information from an abundance of spatial-temporal data in a database. In this thesis, we propose a novel algorithm, STP-Mine (Spatial- Temporal Patterns-Mine), to mine closed stpatterns in a spatial-temporal database. The proposed algorithm consists of three phases. First, we find all frequent length-1 patterns (1-patterns) and construct a projected database for each frequent 1-pattern found. Second, we recursively generate frequent super-patterns in the spatial dimension in a depth-first search manner. Third, once a pattern cannot grow further in the spatial dimension, we extend it in the temporal dimension in a depth-first search manner. The steps in the second and third phases are repeated 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 stpatterns. The experimental results show the STP-Mine algorithm is efficient and scalable, and outperforms the modified A-Close algorithm in one order of magnitude.