利用9D-SPA表示法探勘空間關聯規則

Abstract

在本篇論文中，我們提出一個新的空間資料探勘演算法「9DSPA-Miner」。從一個所有影像都是用9D-SPA表示法呈現的影像資料庫中去探勘出空間關聯規則。我們提出的方法包含了三個階段。第一階段，掃瞄資料庫一次並且建立一個索引結構。第二階段，掃瞄索引結構以找出所有長度為二的頻繁樣式。第三階段，利用長度為k的頻繁樣式（k≧2）去產生長度為k+1的候選樣式，並且藉著索引結構確認每個候選樣式的出現頻率是否不小於使用者定義的最小出現頻率門檻值。然後持續重複第三階段的步驟直到不能再找得到頻繁樣式為止。因為9DSPA-Miner利用9D-SPA表示法的特性刪除許多不可能的候選樣式，並利用索引結構加速探勘的程序，實驗結果顯示9DSPA-Miner比改良式的Apriori方法更有效率且更具擴充性。

In this thesis, we propose a novel spatial data mining algorithm, called 9DSPA-Miner, to mine the spatial association rules from an image database, where every image is represented by the 9D-SPA representation. Our proposed method consists of three phases. In the first phase, we scan the database once and create an index structure. In the second phase, we scan the index structure to find all frequent patterns of length two. In the third phase, we use the frequent k-patterns (k≧2) to generate candidate (k+1)-patterns and check each generated candidate if its support is not less than the user-specified minimum support threshold by using the index structure. Then, the steps in phase 3 are repeated until no more frequent patterns can be found. Since 9DSPA-Miner uses the characteristics of the 9D-SPA representation to prune most of impossible candidates and the index structure to speed up the mining process, the experiment results demonstrate that it is more efficient and scalable than the modified Apriori method.