李瑞庭臺灣大學：資訊管理學研究所蔡欣穆Tsai, Hsin-MuHsin-MuTsai2007-11-262018-06-292007-11-262018-06-292007http://ntur.lib.ntu.edu.tw//handle/246246/54246在本篇論文中，我們提出一個新的空間資料探勘演算法「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.Table of Contents i List of Figures iii List of Tables v Chapter 1 Introduction 1 Chapter 2 Problem Definition and Preliminary Concept 5 2.1 9D-SPA Representation 5 2.2 Problem Definition 8 Chapter 3 The Method for Rectangular Objects 10 3.1 A Two-level Index Structure 10 3.2 Candidate Generation 12 3.3 The Pruning Strategies 14 3.3.1 Reasoning Dij 15 3.3.2 Reasoning Dji 23 3.3.3 Reasoning Tij 24 3.4 The Mining Algorithm 25 Chapter 4 The Method for Difform Objects 32 4.1 Reasoning Dij 32 4.1.1 Reasoning Region[0] 34 4.1.2 Reasoning Region[1] 34 4.1.3 Reasoning the state of the other regions 37 4.1.4 Deciding candidates of Dij 44 4.2 Reasoning Dji 45 4.3 Reasoning Tij 45 4.4 The Mining Algorithm 45 Chapter 5 Performance Evaluation 47 5.1 Synthetic Data and Parameters 47 5.2 Experiments on Rectangular Synthetic Data 48 5.3 Experiments on Difform Synthetic Data 52 5.4 Experiments on Real Data 57 Chapter 6 Conclusions and Future Work 62 References 63642983 bytesapplication/pdfen-US空間資料探勘空間關聯規則9D-SPA表示法spatial data miningspatial association rules9D-SPA representationotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54246/1/ntu-96-R93725013-1.pdf