臺灣博碩士論文加值系統

在本篇論文中，我們提出一個新的空間資料探勘演算法「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 63

[1]S. R. Arridge, “Optical tomography in medical imaging,” Inverse Problems, Vol. 15, No. 2, 1999, pp. R41-R93.
[2]R. Agrawal, T. Imielinski and A. Swami, “Mining association rules between sets of items in large databases,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 1993, pp. 207-216.
[3]R. Agrawal and R. Srikant, “Fast algorithms for mining association rules,” in Proceeding of International Conference on Very Large Data Bases, 1994, pp. 487-499.
[4]R. Agrawal and R. Srikant, “Fast algorithms for mining association rules in large databases,” Research Report RJ 9839, IBM Almaden Research Center, San Jose, California, June 1994, pp. 487-499.
[5]C. C. Chang, “Spatial match retrieval of symbolic pictures,” Journal of Information Science and Engineering, Vol. 7, No. 3, 1991, pp. 405-422.
[6]M. Ester, H. P. Kriegel, J. Sander and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” in Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining, 1996, pp. 226-231.
[7]M. Ester, H. P. Kriegel, J. Sander and X. Xu, “Clustering for mining in large spatial databases,” Special Issue on Data Mining, KI-Journal, ScienTec Publishing, Vol. 1, 1998, pp. 1-7.
[8]Y. C. Huang, “Mining frequent spatial co-relation patterns,” Master Thesis, Department of Computer Science, National Chengchi University, 2004.
[9]W. Hsu, J. Dai and M. Lee, “Mining viewpoint patterns in image databases,” in Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003, pp. 553-558.
[10]J. Han, Y. Fu, W. Wang, J. Chiang, W. Gong, K. Koperski, D. Li, Y. Lu, A. Rajan, N. Stefanovic, B. Xia and O. R. Zaiane, “DBMiner: a system for mining knowledge in large relational databases,” in Proceedings 1996 International Conference on Data Mining and Knowledge Discovery, 1996, pp. 250-255.
[11]J. Han, K. Koperski and N. Stefanovic, “GeoMiner: a system prototype for spatial data mining,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 1997, pp. 553-556.
[12]P. W. Huang and C. H. Lee, “Image database design based on 9D-SPA representation for spatial relations,” IEEE Transactions on Knowledge and Data Engineering, Vol. 16, No. 12, 2004, pp. 1486-1496.
[13]W. M. Ko, “Mining spatial association rules with 9DLT string representation,” Master Thesis, Department of Information Management, National Taiwan University, 2005.
[14]K. Koperski, J. Adhikary and J. Han, “Spatial data mining: progress and challenges survey paper,” in Proceedings of the Workshop on Research Issues on Data Mining and Knowledge Discovery, 1996, pp. 0-
[15]K. Koperski and J. Han, “Discovery of spatial association rules in geographic information databases,” in Proceedings of the 4th International Symposium on Advances in Spatial Databases, 1995, pp. 47-66.
[16]I. S. Kang, T. W. Kim and K. J. Li, “A spatial data mining method by delaunay triangulation,” in Proceedings of the 5th ACM International Workshop on Advances in Geographic Information Systems, 1997, pp. 35-39.
[17]Y. Morimoto, “Mining frequent neighboring class sets in spatial databases,” in Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001, pp. 353-358.
[18]D. J. Marceau, P. J. Howarth and D. J. Gratton, “Remote sensing and the measurement of geographical entities in a forested environment. 1. The scale and spatial aggregation problem,” Remote Sensing of Environment, Vol. 49, No. 2, 1994, pp. 93-104.
[19]R. T. Ng and J. Han, “Efficient and effective clustering methods for spatial data mining,” in Proceedings of the 20th International Conference on Very Large Data Bases, 1994, pp. 144-155.
[20]J. S. Park, M. S. Chen and P. S. Yu, “Using a hash-based method with transaction trimming for mining association rules,” IEEE Transactions on Knowledge and Data Engineering, Vol. 9, No. 5, 1997, pp. 813-825.
[21]R. Simmons and S. Koenig, “Probabilistic robot navigation in partially observable environments,” in Proceedings of the International Joint Conference on Artificial Intelligence, 1995, pp. 1080-1087.
[22]J. A. Thompson and C. A. Butler, “Digital elevation model resolution: effects on terrain attribute calculation and quantitative soil-landscape modeling,” Geoderma, Vol. 100, No. 1, 2001, pp. 67-89.
[23]X. Xu, M. Ester, H.-P. Kriegel and J. Sander, “A distribution-based clustering algorithm for mining in large spatial databases,” in Proceedings of the 14th International Conference on Data Engineering, 1998, pp. 324-331
[24]J. S. Yoo and S. Shekhar, “A partial join approach for mining co-location patterns,” in Proceedings of the 12th annual ACM International Workshop on Geographic Information Systems, 2004, pp. 241-249.
[25]J. S. Yoo, S. Shekhar and M. Celik, “A join-less approach for co-location pattern mining: A summary of results,” in Proceedings of the 5th IEEE International Conference on Data Mining, 2005, pp. 813-816.
[26]X. Zhang, N. Mamoulis, D. W. Cheung and Y. Shou, “Fast mining of spatial collocations,” in Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004, pp. 384-393.