空间关联规则挖掘研究进展

doi:10.11820/dlkxjz.2007.06.013

摘要/Abstract

摘要：

随着空间数据获取技术的进步, 空间数据量日益增大, 已超出人们的分析能力。传统的空间数据分析方法只能进行简单的数据分析, 无法满足人们获取知识的需要。空间关联规则是空间数据挖掘一个基本的任务, 是从具有海量、多维、多尺度、不确定性边界等特性的空间数据中进行知识发现的重要方法。本文从基本概念、分类、挖掘过程、挖掘方法、目前研究成果等方面对其进行综述, 重点阐述了空间关联规则挖掘效率的改进策略、基于不确定空间信息的挖掘方法、挖掘过程及结果的可视化、弱空间关联规则的挖掘方法等。通过对现有空间关联规则研究成果和存在问题的深入剖析, 指出了其未来主要的发展方向。

关键词: 地理信息系统(GIS), 空间关联规则, 空间数据, 数据挖掘

Abstract:

With the progress of spatial data technologies, the volumes of the spatial data enhance gradually, far exceeding people’s ability to analyze it. Traditional spatial data analysis methods can only carry out simple data analysis, having no way to satisfy people’s need of gaining knowledge. Spatial association rule mining approach, which is used to acquire underlying spatial knowledge from spatial database managing complex, multiple- dimension, large, and flexibility border space spatial data, is a fundamental mission of the spatial data mining. The authors make an annotated review of basic concepts, classification, mining process, current research achievements and so on, especially paying attention to approaches improving mining efficient, mining method based on the uncertain space information and attribute information, visualization of mining results and processes, and negative spatial association rule mining. After deeply analyzing research achievements and existing problems, the authors bring forward the future main development directions of spatial association rule mining.

Key words: association rule mining, data mining, geographic information system, spatial data

张雪伍, 苏奋振, 石忆邵, 张丹丹. 空间关联规则挖掘研究进展[J]. 地理科学进展, 2007, 26(6): 123-132.

ZHANG Xuewu, SU FenZhen, SHI Yishao, ZHANG Dandan. Resear ch on Progr ess of Spatial Association Rule Mining[J]. PROGRESS IN GEOGRAPHY, 2007, 26(6): 123-132.

参考文献

[1] M Ester, H P Kriegel, J Sander. Spatial data mining: A database approach, in Advances in Spatial Databases, 1997, 1262: 47~66.

[2] Salvatore Rinzivillo, Franco Turini. Knowledge discovery from spatial transactions. Journal of Intelligent Information Systems, 2007, 28(1): 1~2.

[3] Lu W, Han J, et a1. Discovery of general knowledge in large spatial databases. In: Proc. Far East Workshop on Geographie Information Systems. Singapore, 1993, 275~ 289.

[4] Eliseo Clementini, Paolino Di Felice, Krzysztof Koperski. Mining multiple- level spatial association rules for objects with a broad boundary. Data & Knowledge Engineering, 2000, 34(3): 251~270.

[5] 吕曹芳, 庞宇, 罗永龙. 基于GIS 空间关联规则的挖掘综述. 资源开发与市场, 2007, 23(4): 323~325.

[6] K Koperski, J Han. Discovery of spatial association rules in geographic information databases. Lecture Notes In Computer Science, 1995, 951: 47~66.

[7] 王海起, 王劲峰等. 空间数据挖掘技术研究进展. 地理与地理信息科学, 2005, 21(4): 6~10.

[8] Wang S L, Guoqing Chen, Deyi Li, et al. A try to handing uncertainties in spatial data mining. Lecture Notes in Artificial Intelligence, 2004, 3215:513~520.

[9] 李德仁, 王书良, 李德毅. 空间数据挖掘理论与应用. 北京: 科学出版社, 2006, 10: 7~16.

[10] 赵文武, 傅伯杰, 吕一河等. 多尺度土地利用与土壤侵蚀. 地理科学进展, 2006, 25(1): 24~33.

[11] R Agrawal, T Imielinskin, A Swami. Mining Association Rules between Sets of Items in Large Databases, Proc, ACM SIGMOD, 1993, 207~216.

[12] R Agrawal, R Srikant. Fast Algorithms for Mining Association Rules in Large Databases. In Proc. 1994 Int. Conf. VLDB, 1994, 487~499.

[12] K Koperski, J Han. Discovery of spatial association rules in geographic information databases. Lecture Notes In Computer Science, 1995, 951:47~66.

[13] Robert Bembenik, Henryk Rybi"ski. Mining Spatial Association Rules with No Distance Parameter. In Proc. Intelligent Information Processing and Web Mining. Springer Berlin/Heidelberg, 2006, 35: 499~508.

[14] 苏奋振, 杜云艳, 杨晓梅等. 地学关联规则与时空推理的渔业分析应用. 地球信息科学, 2004, 6(4): 68~69.

[15] 刘独玉, 杨晋浩, 钟守铭. 关联规则挖掘研究综述. 成都大学学报(自然科学版), 2006, 25(1): 54~57.

[16] 马荣华, 蒲英霞, 马小冬. GIS 空间关联模式发现. 北京:科学出版社, 2007.

[17] Estivill Castro V, Murray A T. Discovering associations in spatial data~ an efficient medoid based approach. In:Proc. Of PAKDD’98, 1998, 110~121.

[18] Estivill Castro V, Lee I. Data mining techniques for autonomous exploration of large volumes of geo~referenced cirme data. In: Proc. Of the 6th international conference of geocomputation, 2001.

[19] Ceci M, Appice A, Malerba D. Spatial associative classification at different levels of granularity: A probabilistic approach. Knowledge Discovery in Databases: Pkdd 2004, Proceedings. Springer Berlin/Heidelberg, 2004, 3202:99~111.

[20] Shekhar S, HuangY. Discovering spatial co- location patters: a summary of results. In: Processdings o f7th International Symposium o n Spatial and Temporal Databases, 2001, 236~256.

[21] 倪凯, 祝晓东, 张超. 基于关联规则的空间数据知识发现及实现. 计算机应用与软件, 2005, 22(12): 34~35.

[22] 陈江平. 空间关联规则挖掘算法研究. 计算机工程, 2004, 30(23): 53~55.

[23] 袁红春, 熊范纶. 元规则指导下的逐步求精多层空间关联规则挖掘算法. 计算机工程, 2004, 30(8): 34~39.

[24] Annalisa Appice, Margherita Berardi, Michelangelo Ceci, et al. Mining and Filtering Multi- level Spatial Association Rules with ARES. Foundations of Intelligent Systems. Springer Berlin/Heidelberg, 2005, 3488:342~353.

[25] 陆勤, 刘胜军, 蔡庆生. 空间关联规则发掘的一种渐进求精算法. 计算机应用研究, 2006, (6): 10~11.

[26] Ansaf Salleb, Christel Vrain. An Application of Association Rules Discovery to Geographic Information Systems. In Proc. Principles of Data Mining and Knowledge Discovery. Springer Berlin/Heidelberg, 2000, 1910 : 613~618.

[27] CHEN Jiangping, FU Zhongliang, BIAN Fuling, etal. Mining Spatial Association Rules with Spatial Analysis. Computer Engineering, 2003, 29(11):29~31.

[28] 刘君强, 潘云鹤. 挖掘空间关联规则的前缀树算法设计与实现.中国图象图形学报, 2003, 8(4): 476~480.

[29] Francesca A. Lisi, Donato Malerba. Inducing Multi- Level Association Rules from Multiple Relations. Machine Learning, 2004, 55 (2): 175~208.

[30] 李宏, 蔡之华. 应用于空间关联规则挖掘的ILP 方法. 计算机工程与应用, 2003, 16: 188~197.

[31] 马荣华, 马小冬, 蒲英霞. 从GIS 数据库中挖掘空间关联规则研究. 遥感学报, 2005, 9(6): 733~741.

[32] Qin Ding, Qiang Ding, William Perrizo. Association Rule Mining on Remotely Sensed Images Using P- trees. In Proc. Advances in Knowledge Discovery and Data Mining. Springer Berlin/Heidelberg, 2002, 2336: 66~79.

[33] Anthony J T Lee, Ruey-Wen Hong, Wei-Min Ko, et al. Mining spatial association rules in image databases. Information Sciences, 2006, 177(7): 1593~1608.

[34] Robert Bembenik, Henryk Rybi#ski. Mining Spatial Association Rules with No Distance Parameter. Intelligent Information Processing and Web Mining. Springer Berlin/Heidelberg, 2006, 35:499~508.

[35] 刘大有, 王生生, 虞强源等. 基于定性空间推理的多层空间关联规则挖掘算法. 计算机研究与发展, 2004, 41(4): 565~ 570.

[36] LAN Rongqing, LIU Zengliang, YANG Xiaomei. Methods of Mining Fuzzy Spatial Association Rules. Journal of Institute of Surveying and Mapping, 2005, 22(1): 36~39.

[37] Beaubouef Theresa, Petry Frederick E. A rough set foundation for spatial data mining involving vague regions. IEEE International Conference on Plasma Science, 2002, 1: 767~772.

[38] Beaubouef Theresa, Ladner Roy, Petry Frederick . Rough Set Spatial Data Modeling for Data Mining. International Journal of Intelligent Systems, Granular Computing and Data Mining , 2004, 19(7): 567~584.

[39] Seo Eun~Kyoung, Biggerstaff, Michael I. Impact of cloud model microphysics on passive microwave retrievals of cloud properties. Part II: Uncertainty in rain, hydrometeor structure, and latent heating retrievals. Journal of Applied Meteorology and Climatology, 2006, 45(7): 955~972.

[40] Yang Bin, Zhu, Zhong~Ying. Mining multilevel spatial association rules with cloud models. Journal of Harbin Institute of Technology (New Series), 2005, 12(3):314~318.

[41] Wang Xiao Hui, Xie Jiancang, Li Jianxun, et al. Implementation of GIS spatial data mining based on cloud theory. Proceedings ~ 2006 International Conference on Hybrid Information Technology, ICHIT 2006, 2006, 1: 530~534.

[42] D. Bruzzese, C. Davino. Visual post analysis of association rules. Journal of Visual Languages and Computing, 2003, 14(6): 621~635.

[43] Annalisa Appice, Paolo Buono. Analyzing Multi- level Spatial Association Rules Through a Graph- Based Visualization. In Proc. Innovations in Applied Artificial Intelligence. Springer Berlin/Heidelberg, 2005, 3533: 448~457.

[44] 涂建东, 陈崇成, 樊明辉等. 基于Java3D 的空间关联规则可视化原理与实现. 高技术通讯, 2004(6): 98~99.

[45] L K Sharma, O P Vyas, U S Tiwary, et al. A Novel Approach of Multilevel Positive and Negative Association Rule Mining for Spatial Databases. Machine Learning and Data Mining in Pattern Recognition. Springer Berlin/Heidelberg, 2005, 3587: 620~629.

[46] Wu X, Zhang C, Zhang S. Efficient Mining of Both Positive and Negative Association rule. ACM Tran. On Information System, 2004, 22(3), 381~405.

[47] William Perrizo, Qin Ding, Qiang Ding, et al. Deriving High Confidence Rules from Spatial Data Using Peano Count Trees. In Proc. Advances in Web~Age Information Management. Springer Berlin/Heidelberg, 2001, 2118:91~102.

[48] 蒋艳, 周成虎, 程维明. 新疆阿克苏河流域年径流时序特征分析. 地理科学进展, 2005, 24(1): 87~96.