（计算机软件与理论专业论文）空间数据挖掘中的分类方法及其应用研究.pdf

山东大学硕士学位论文 摘要 随着空间技术在各个行业的应用以及数据挖掘、空间数据采集技术、数据库 技术的迅速发展，对从空间数据库发现隐含知识的需求日益增长，出现了用于在 空间数据库中进行知识发现的崭新研究领域空间数据挖掘。空间数据挖掘是 从空间数据库中提取隐含的、用户感兴趣的空间、非空间模式和普遍特征的过程， 它是多学科和多种技术交叉综合的新领域，综合了机器学习、空间数据库系统、 专家系统、可移动计算、统计学、遥感、基于知识的系统、可视化等领域的有关 技术。尽管数据挖掘最初产生于关系数据库和事务数据库，但由于空间数据的特 殊性，从空间数据库中发掘知识很快引起了数据挖掘研究者的关注。 本文系统的介绍了空间数据挖掘的基本理论，比较传统数据挖掘与空间数据 挖掘的不同之处，进而分析了空间数据挖掘中数据分类的研究现状和目前存在的 问题。通过对已有方法的研究以及在与统计学、粗糙集理论、信息论等领域相关 技术的结合，提出针对空间数据挖掘中连续数据离散化、谓词选取以及数据分类 的解决方法，并最终以空间数据挖掘原型系统的形式加以实现。 本文所做的主要工作有以下几个方面： 利用统计学中的方差分析方法，本文根据数据总平方和可以分解为效应平 方和与误差平方和的思想，提出了基于效应平方和的连续数据离散化算法，先利 用直方图法对数据进行初始化，然后计算相应的效应平方和和误差平方和，直至 效应平方和最大。 本文利用最大熵原理对不同层次空间对象的空间关系进行分析，采用 k u l l b a c k - l e i b l e r 距离作为迭代条件，使用互信息和z 一测试方法选取最能表征空 间对象之间关系的空间谓词及与之相关联的非空间数据集。 空间数据挖掘中需要不确定性处理的一个基本方面是空间对象之间的拓 扑关系。本文提出了采用概率粗糙集模型处理空间关系的空间数据分类方法，此 方法可以处理空间数据中的不确定性关系，在保持信息分类能力不变的前提下进 行数据约简，能够处理多种类型的噪声，输出最终的空间数据分类规则。 通过对空间数据挖掘中数据预处理、空间谓词选取及数据分类的研究，最 后实现了一个空间数据挖掘的原型系统。原型系统是在w i n d o w s 操作系统下，以 山东大学硕士学位论文 v i s u a lc + + 6 0 和m a p x 5 0 作为应用平台，实现了数据预处理、空间特征提取、空 间数据分类、规则提取等功能。系统具有可视化图形界面，能完成基本的g i s 操 作、图层管理等功能，可以方便的操作空间数据。 关键词：空间数据挖掘；数据离散化；效应平方和；空间谓词；最大熵；空间数 据分类；概率粗糙集 n 山东大学硕士学位论文 a b s t r a c t w i mt h ea p p l i c a t i o no fs p a t i a lt e c h n o l o g yi ne v e r yi n d u s t r ya n dt h eq u i c k d e v e l o p m e n to f d a t am i n i n g ，s p a t i a ld a t ac o l l e c t i o nt e c h n o l o g y , d a t a b a s et e c h n o l o g y , t h e d e m a n do fd i s c o v e r i n gk n o w l e d g ef r o ms p a t i a ld a t a b a s es t r e n g t h e n si n c r e a s i n g l ya n da n e wr e s e a r c hf i e l di no r d e rt og e tk n o w l e d g ef r o ms p a t i a ld a t a b a s eh a sa p p e a r e d - s p a t i a l d a t am i n i n g s p a t i a ld a t am i n i n gi st h ep r o c e s so fd i s t i l lt h ec o n n o t a t i v es p a t i a l ， n o n - s p a t i a lp a t t e r na n dc o m m o nc h a r a c t e rt h a tt h ep e o p l ea r ei n t e r e s t e di nf r o ms p a t i a l d a t a b a s e ，i ti san e wa r e at h a ti n t e g r a t e sm u l t i - s u b j e c ta n dm a n yt e c h n o l o g i e sa n d c o m b i n e st h et e c h n o l o g i e so fm a c h i n el e a r n i n g ，s p a t i a ld a t a b a s es y s t e m , e x p e r ts y s t e m ， m o b i l ec o m p u t e ，s t a t i s t i c s , r e m o t es e n s i n g , s y s t e mb a s e do nk n o w l e d g e ，v i s u a l i z a t i o n a n ds oo i lt h o u g ha tf i r s td a t am i n i n gc o m e sf r o mr e l a t i o nd a t a b a s ea n dt r a n s a c t i o n a l d a t a b a s e ，w i t ht h es p e c i a lc h a r a c t e ro fs p a t i a ld a t a , m i n i n gk n o w l e d g ef r o ms p a t i a l d a t a b a s eb r i n g st h ea t t e n t i o no f d a t am i n i n gr e s e a r c h e r s t h i sp a p e ri n t r o d u c e st h eb a s i ct h e o r yo f s p a t i a ld a t am i n i n gs y s t e m i c a l l y , c o m p a r e st h ed i f f e r e n c e sb e t w e e nt h et r a d i t i o n a ld a t am i n i n ga n ds p a t i a ld a t am i n i n g ， a n dt h e na n a l y s e st h er e s e a r c ha c t u a l i t ya n dt h ec u r r e n tp r o b l e m so f d a t ac l a s s i f i c a t i o n i ns p a t i a ld a t am i n i n g t h r o u g ht h es t u d yo f e x i s t e dm e t h o d s a n dc o m b i n a t i o no f s t a t i s t i c s ，r o u g hs e tt h e o r y , i n f o r m a t i o nt h e o r ya n ds o no n , s o l u t i o n so f c o n t i n u o u sd a t a s d i s e r e t i z a t i o n , p r e d i c a t i o ns e l e c t i o na n dd a t ac l a s s i f i c a t i o ni ns p a t i a ld a t am i n i n g a r e s u b m i t t e da n das p a t i a ld a t am i n i n ga r c h e t y p a ls y s t e mi sa c h i e v e d t h em a i n w o r ko f t h i sp a p e ri sl i s t e da sf o l l o w s ： b a s e do nt h ea n a l y s i so fv a r i a n c ei ns t a t i s t i c sa n dt h ei d e at h a tt h et o t a ls q u a r e s u n lo fd a t ac a nb es e p a r a t e di n t oe f f i c a c ys q u a r es l i ma n de r r o rs q u a r es u m , t h i sp a p e r s u b m i t sac o n t i n u o u sd a t ad i s e r e t i z a t i o na l g o r i t h mb a s e do nt h em a x i n l u n le f f i c a c y s q u a r es u m , w ei n i t i a l i z et h ed a t ab yh i s t o g r a mm e t h o d , t h e nc o m p u t et h er e l e v a n t e f f i c a c ys q u a r es u ma n de r r o rs q u a r es u mu n t i lt h ee f f i c a c ys q u a r es u mi sm a x i m a l t h i sp a p e ra n a l y z e st h er e l a t i o n s h i po fd i f f e r e n tl e v e ls p a t i a lo b j e c t st h r o u g h 1 1 1 山东大学硕士学位论文 t h em a x i m u me n t r o p yp r i n c i p l e ；p i c ko u tt h es p a t i a lp r e d i c a t i o nt h a tc a l lf u l l yi n c a m a t e t h er e l a t i o n s h i po fs p a t i a lo b j e c t sa n dr e l e v a n tn o n - s p a t i a ld a t a s e tt h r o u g hm u t u a l i n f o r m a t i o n , z t e s ta n dk u l l b a e k - l e i b l e rd i s t a n c ea sa ni t e r a t i v ec o n d i t i o n ab a s i ca s p e c tt h a tn e e d su n c e r t a i nd i s p o s a li ns p a t i a ld a t am i n i n gi s t o p o l o g i c a lr e l a t i o no fs p a t i a lo b j e c t s t h i sp a p e rg i v e sas p a t i a ld a t ac l a s s i f i c a t i o n m e t h o dt h a td e a l sw i t i ls p a t i a lr e l a t i o n s h i pb a s e do np r o b a b i l i t yr o u g hs e tm o d e l t h i s m e t h o dc a l lh a n d l ew i t hu n c e r t a i nr e l a t i o n s h i po fs p a t i a ld a t a , r e d u c et h ed a t aw i t h k e e p i n gi n f o r m a t i o nc l a s s i f i c a t i o np u r p o s eu n c h a n g e d , m a n a g em a n yk i n d so f n o i s ya n d o u t p u tt h es p a t i a ld a t ac l a s s i f i c a t i o nr u l e sf i n a l l y a s p a t i a ld a t am i n i n ga r c h e t y p a ls y s t e mi sa c h i e v e db yt h er e s e a r c ho fd a t a p r e p r o c e s s i n g ，s p a t i a lp r e d i c t i o ns e l e c t i o na n dd a t ac l a s s i f i c a t i o ni ns p a t i a ld a t am i n i n g t h i ss y s t e mi sb u i l tu n d e rw i n d o w so s ，v i s u a lc + + 6 0a n dm a p x 5 0 ，w h i c ha c h i e v e s d a t ap r e p r o c e s s i n g , s p a t i a lf e a t u r es e l e c t i o n , s p a t i a ld a t ac l a s s i f i c a t i o n , r u l e ss e l e c t i o n f u n c t i o na n ds oo i li th a sav i s u a li n t e r f a c e ，a c c o m p l i s h e sb a s i cg i so p e r a t i o na n dl a y e r m a n a g e m e n ta n ds oo n , 8 0w c c a l lm a n i p u l a t e ss p a t i a ld a t ae a s i l y k e yw o r d s ：s p a t i a ld a t am i n i n g ；d a t ad i s e r e t i z a t i o n ；e f f i c a c ys q u a r es u m ；s p a t i a l p r e d i c a t i o n ；m a x i m u me n t r o p y ；s p a t i a ld a t ac l a s s i f i c a t i o n ；p r o b a b i l i t yr o u g hs e t i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：基! 整日期：勉。生：厂论文作者签名：丛垒日期：勉。生：j 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：查堡导师签名： 口) 口 日期：型! 竺：f 山东大学硕士学位论文 第一章绪论 1 1 数据挖掘的研究现状 由于现代数据库技术及数据库管理系统的迅速发展，社会经济各个部门生产、 收集、存储和处理数据的能力得到了空前的提高，形式各样的数据资源也日益丰 富。但是数据资源中蕴含的知识并没有得到充分的挖掘和利用，致使“数据爆炸 但是知识贫乏”目前数据库系统所能做到的只是对数据库中已有的数据进行存 取，人们通过这些数据所获得信息量仅仅是整个数据库所包含的信息量的一部分。 隐藏在这些数据之后的更重要的信息是关于这些数据的整体特征的描述及对其发 展趋势的预测，这些信息在决策生成的过程中具有重要的参考价值 1 】。 由于技术的成熟和价格的低廉，投入运行的数据库系统数量以越来越快的速 度增加，这也促使人们产生了对自动地从大量数据库中的数据寻找有用的信息和 知识的迫切需求，这样一个崭新的交叉研究领域出现了，这就是数据挖掘。 数据挖掘是一个新兴的研究领域，它被列为美国n s f 九十年代最有价值的数 据库研究项目。美国著名的工业家c a r t e r 的报告认为数据挖掘将对今后- - n 五年 的工业产生重要影响，是工业界应重点投资的关键技术 所谓数据挖掘【2 】，就是对观测到的数据集( 经常是非常庞大的) 进行分析， 目的是发现未知的关系和以数据拥有者可以理解并对其有价值的新颖方式来总结 数据【1 】。数据挖掘是综合多个学科的崭新的研究领域，在数据挖掘的研究中涉及 多个学科的技术，如数据库、数据仓库、统计学、机器学习、数据可视化、高性 能计算、信息获取，其他相关的还包括模式识别、神经网络、空间数据分析、图 像数据库、信号处理、概率图论以及归纳逻辑编程等等。数据挖掘过程需要多学 科方法的有机集成。在大量的研究基础上，运用统计学的方法已经开发出很多有 效的数据分析方法。机器学习的方法则是对分类与归纳推理进行的深入的研究。 同时神经网络方法也在分类、预测、聚类以及分析中显示出其有效性。 数据、数据挖掘任务和数据挖掘方法的多样性给数据挖掘提出了许多挑战性 的课题。数据挖掘语言的设计，高效而有用的挖掘方法和系统的开发，交互和集 山东大学硕士学位论文 成的数据挖掘环境的建立，以及应用数据挖掘技术解决大型应用问题，都是目前 数据挖掘研究人员、系统和应用开发人员面临的主要问题。 1 2空间数据挖掘概述 随着数据挖掘研究领域的不断拓展，传统的关系数据和事务数据挖掘已经发 展到对空间数据的挖掘。空间数据正在逐步成为各种信息系统的主体和基础，它 是一类重要的、特殊的数据，有着比一般关系数据库和事务数据库更加丰富和复 杂的语义信息，包含着更丰富的知识。因此，尽管数据挖掘最初产生于关系数据 库和事务数据库，但由于空间数据的特殊性，从空间数据库中发掘知识很快引起 了数据挖掘研究者的关注。 在地理信息处理领域，随着卫星和遥感技术的广泛应用，日益丰富的空间和 非空间数据被收集并存储在空间数据库中，海量的地理数据在一定程度上已经超 过了人们的处理能力，同时传统的空间分析难以胜任从这些海量的数据中提取和 发现空间知识。这给当前地理信息系统( g i s ) 技术提出了巨大的挑战，迫切需要增 强g i s 分析功能，提高g i s 解决地学实际问题的能力。数据挖掘与知识发现的出现 很好地满足了地球空间数据处理的需要，推动了空间数据挖掘的发展。根据空间 数据的特点，将数据挖掘方法引入地理信息系统，形成空间数据挖掘与知识发现 的新型数据分析理论。 目前国内外都开展了空间数据挖掘与知识发现方面的研究【3 ，4 】。加拿大s i m o n f r a s e r 大学计算机科学系的韩家炜教授领导的小组，较早对此进行系统全面的研 究，并在m a p i n f o 平台上建立了空间数据挖掘的原型系统g e o m i n e r ，实现了空间 数据特征描述、空间比较、空间关联、空间聚类和空间分类等空间数据挖掘方法。 国内武汉大学李德仁教授最早关注到从g i s 数据库中发现知识的问题，提出从g i s 数据库可以发现包括几何信息、空间关系、几何性质与属性关系以及面向对象知 识等多种知识。 1 3 本文的主要工作及其研究意义 本文分析了空间数据挖掘中数据分类的研究现状和目前存在的问题。通过对 已有方法的研究以及在与统计学、粗糙集理论、信息论等领域的相关技术的结合， 提出针对空间数据挖掘中连续数据离散化、谓词选取以及数据分类的解决方法， 苎最终以空间数据挖掘原型系统的形式加以实现。 山东大学硕士学位论文 1 3 1空间连续数据离散化的效应平方和算法 在空间数据库中包含的数据非常丰富，其属性值的类型包括离散类型和连续 类型，对于连续类型的属性，它可能取得的属性值数量非常多，甚至是无限的。 在空间数据挖掘过程当中，很多情况下要求处理的数据是离散类型，因此连续数 据必须要进行离散化。对于可以直接处理连续类型数据的算法，经过离散化后也 可以提高相应的算法执行效率，并且可能提高分类决策的精度。本文利用统计学 中的方差分析方法，根据数据总平方和可以分解为效应平方和与误差平方和的思 想，提出了基于效应平方和的连续数据离散化算法，先利用直方图法对数据进行 初始化，然后计算相应的效应平方和与误差平方和，直至效应平方和最大。本算 法是一种非监督的离散化算法，其特点是时间复杂度较低，能够根据实际的数据 得到总体感觉较好的数据离散化结果。 1 3 2空间谓词选取的最大熵方法 ； 空间数据挖掘处理的数据包括空间数据和非空间数据，我们进行空间分类的 目的是得到空间分类规则，因此在对空间数据对象的分类过程中，需要使用空间 谓词对空间对象的特征进行描述。本文利用最大熵原理对不同层次空间对象的空 间关系进行分析，采用k u l l b a c k - l e i b l e r 距离作为迭代条件，使用互信息和z 一 测试方法选取最能表征空间对象之间关系的空间谓词及与之相关联的非空间数据 集。 1 3 3空间数据分类的概率粗糙集算法 现实世界中存在大量的不确定性，任何将世界中某些方面模型化的方法都应 该包括处理不确定性的机制。在理解实体或数据的意义或性质时可能存在不确定 性。空间数据挖掘中需要不确定性处理的一个基本方面是空间对象之间的拓扑关 系空间对象之间的拓扑关系包含的是各种不同的空间实体之间的关系。空间关 系例如相交、邻近、重叠等都已经得到应用，用来发现空间数据中的关联规则和 属性泛化本文提出了采用概率粗糙集模型处理空间关系的空间数据分类方法， 此方法可以处理空间数据中的不确定性关系，在保持信息分类能力不变的前提下 进行数据约简，能够处理多种类型的噪声，输出最终的空间数据分类规则。与已 有的粗糙集分类算法相比，算法引入了概率粗糙集模型，提高了分类准确性，同 时改进了空间属性约简方法，保证能够得到完备的约简集合，降低了进行属性约 3 山东大学硕士学位论文 简的时间复杂度。 1 3 4空间数据挖掘原型系统模型实现 空间数据挖掘原型系统是在w i n d o w s 操作系统下，以v i s u a lc + + 6 o 和m a p x 5 0 作为应用平台，实现了数据预处理、空间特征提取、空间数据分类、规则提取等 功能。系统具有可视化图形界面，能完成基本的g i s 操作、图层管理等功能，可 以方便地操作空间数据。 1 4本文的组织结构 本文主要根据空间数据挖掘的特点，围绕如何行之有效的对空间数据进行分 析，获得数据中隐含的知识这一问题，提出了数据离散化、空间谓词选取和空间 规则生成的方法，提出可以处理空间数据的分类方法。本文的后续各章安排如下： 第二章主要对空间数据挖掘的理论架构、挖掘方法和目前存在的一些问题作 了简单的介绍。 第三章介绍了统计学中的方差分析理论，提出了基于效应平方和的空间数据 离散化算法，并对其实际的时间复杂度进行了分析，给出了最终的实验结果分析。 第四章介绍了最大熵原理及其相关的概念，提出了选取空间谓词的最大熵方 法，分析了算法的时间复杂度和特点。 第五章在介绍经典租糙集和扩展的概率粗糙集理论的基础上，给出了基于概 率粗糙集的空问分类算法，并对其进行理论和实验分析 第六章给出本文算法模型的原型系统实现，并对今后的工作进行展望。 4 山东大学硕士学位论文 第二章空间数据挖掘 空间数据 3 是人们藉以认识自然和改造自然的重要数据。空问数据库含有空 间数据和非空间数据，空间数据可以是地表在g i s 中的二维投影，也可以是分子 生物学中的蛋白质分子结构等：非空间数据则是除空间数据以外的一切数据。由 于雷达、红外、光电、卫星、电视摄像、电子显微成像、c t 成像等各种宏观与微 观传感器的使用，空间数据的数量、大小和复杂性都在飞快地增长。要求终端用 户详细分析这些空间数据，并提取感兴趣的知识或特征是不现实的。因此，从空 间数据库中自动地挖掘知识，寻找隐藏在空间数据库中的不明确的知识、空间关 系或其他模式，即空间数据挖掘( s p a t i a ld a t am i n i n g ) ，也变得越来越重要。 2 1空间数据库和空间数据挖掘 空间数据库是一类重要的、特殊的数据库，地理信息系统( g i s ) 是空间数据 库发展的主题，另外还有图像数据库、c a d 数据库等。g i s 中含有大量的空间和属 性数据，有着比一般关系数据库和事务数据库更加丰富和复杂的语义信息，隐藏 着丰富的知识。空间数据挖掘和知识发现技术的应用，一方面可使g i s 查询和分 析技术提高到发现知识的新阶段，另一方面从中发现的知识可构成知识库用于建 立智能化g i s 系统，因为单纯专家系统技术的引用使g i s 具有一定的自动性和智 能性，但是它远不能称为是一个真正的“智能”系统，而空间数据挖掘和知识发 现技术的引入，将使系统具有自动学习的能力，能使系统自动获取知识，使g i s 成为一种空间咨询和决策支持系统。 空间数据挖掘 3 是在空间数据库的基础上，综合利用统计学、模式识别、人 工智能、神经网络、粗糙集、模糊数学、机器学习、专家系统和相关信息技术等， 从大量的空间生产数据、管理数据或遥感数据中析取人们可信的、新颖的、感兴 趣的、隐藏的、事先未知的、潜在有用的和最终可理解的知识，从而揭示出蕴含 在数据背后的客观世界的本质规律、内在联系和发展趋势，实现知识的自动获取， 提供技术决策与经营决策的依据。 _ _ - - _ _ _ _ - _ - _ _ _ _ _ _ _ - _ _ - _ - _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ - - _ _ _ _ - _ - _ _ _ - _ _ _ _ _ 一i i i _ - - _ _ - - _ - - - 5 山东大学硕士学位论文 2 2 空间数据挖掘的特点 空间数据挖掘是数据挖掘的学科分支，但空间数据挖掘不同于普通的数据挖 掘。空间数据挖掘的对象是空间数据库或空间数据仓库，有别于常规的事务型数 据库，而且粒度不同，增加了尺度。而空间数据库有着比一般关系数据库系统和 事务数据库系统更加丰富和复杂的语义信息，隐藏着丰富的知识，也存在着众多 的冗余数据。 空间数据库与普通数据库系统之间存在着一些明显的差异： 空间数据库存储和管理的对象是点、线、面、体等空间实体，一般具有一 维或多维的空间地理坐标，不同于关系数据库中单纯的表格和记录。 空间数据结构复杂，栅格和矢量数据一般都存在着多种编码方式。 空间数据包含比关系数据更为具体、复杂而丰富的信息，数据量往往更为 庞大，一般都建立空间索引结构来组织空间数据，并提供相应的空间存取方法。 空间实体之间存在着隐含的空间邻接关系，空间数据相关度高。 缺乏标准的空间查询处理语言，对空间数据的操作还有赖于更多更好的操 作原语的实现和完善。 空间数据本身具有良好的可视性，可以为空间数据挖掘提供更好的可视化 表示。 由于挖掘对象体系结构上的不同，空间数据挖掘同其它数据挖掘存在着一些 差异。机器学习是侧重于设计新的方法从数据库中提取知识的技术行为，而空间 数据挖掘是从已经存在于空间数据库中的数据中挖掘知识的过程。与传统的地学 数据分析相比，空间数据挖掘更强调在隐含未知情形下对空间数据本身分析上的 规律挖掘。 2 3 空间数据挖掘可发现的知识 由于g i s 数据库是空间数据库的主要类型，并且从g i s 数据库中发现的知识类 型及知识发现方法可以涵盖其它类型的空间数据库。我们把g i s 数据库与空间数据 库等同起来，并认为 k g i s 数据库中发现知识与空间数据挖掘有相同的内涵。借鉴 数据挖掘和知识发现的成果，针对空间数据的特点，从空间数据库可以发现的主 要知识类型 3 有： ( 1 ) 普遍的几何知识( g e n e r a lg e o m e t r i ck n o w l e d g e ) 6 山东大学硕士学位论文 普遍的几何知识是指某类目标的数量、大小、形态特征等的普遍的几何特征。 计算和统计出空间目标几何特征量的最小值、最大值、均值、方差等，还可统计 出特征量的直方图。在足够样本的情况下，直方图数据可转换为先验概率使用。 在此基础上。可根据背景知识归纳出高水平的普遍几何知识。 ( 2 ) 空间分布规律( s p a t i a ld i s t r i b u t i o nr e g u l a r i t i e s ) 是指目标在地理空间的分布规律，分成在垂直向、水平向以及垂直向和水平 向的联合分布规律。垂直向分布即地物沿高程带的分布，如植被沿高程带分布规 律，植被沿坡度坡向分布规律等；水平向分布指地物在平面区域的分布规律，如 不同区域农作物的差异、公用设施的城乡差异等；垂直向和水平向的联合分布即 不同的区域中地物沿高程分布规律。 ( 3 ) 空间关联规则( s p a t i a la s s o c i a t i o nr u l e s ) 是指空间目标间相邻、相连、共生、包含等空间关联规则。例如村落与道路 相连，道路与河流的交叉处是桥梁等。例如目标与目标之间的相连、相邻与共生 关系的知识，从g i s 的图形和属性库中，不难发现目标间的相连( 如火车站与铁路 相连) 、相邻( 如房屋与道路相邻) 及共生关系( 如蒙古包与草场的关系) ( 4 ) 空间聚类规则( s p a t i a lc l u s t e r i n gr u l e s ) 空间聚类规则，是指特征相近的空间目标聚类成上一级类的规则，可用于g i s 的空间概括和综合。例如，将距离很近的散布的居民点聚类成居民区。 ( 5 ) 空间特征规则( s p a t i a lc h a r a c t e r i s t i cr u l e s ) 是指某类或几类空间目标的几何的和属性的普遍特征，即对共性的描述。普遍 的几何知识属于空间特征规则的一类，由于它在遥感影像解译中的作用十分重要， 所以分离出来单独作为一类知识。 ( 6 ) 空间区分规则( s p a t i a ld i s c r i m i n a t er u l e s ) 指两类或多类目标间几何的或属性的不同特征，即可以区分不同类目标的特 征。 2 4 空间数据挖掘的常用方法 3 1 空间分析方法。利用g i s 的各种空间分析模型和空间操作对空间数据库中 的数据进行深加工，从而产生新的信息和知识常用的空间分析方法有综合属性 数据分析、拓扑分析、缓冲区分析、距离分析、叠置分析、网络分析、地形分析、 山东大学硕士学位论文 - _ - _ _ - - _ _ - _ _ - _ i _ _ - - _ - _ - - - - _ - - _ - _ l _ _ _ _ _ l _ i _ i - i _ l l l _ 一il _ i l i - 一 趋势面分析、预测分析等，可发现目标在空间上的相连、相邻和共生等关联规则， 或发现目标之间的最短路径、最优路径等辅助决策的知识。 2 统计分析方法。统计方法一直是分析空间数据的常用方法，着重于空间物 体和现象的非空间特性的分析。统计方法有较强的理论基础，拥有大量成熟的算 法。统计方法难以处理字符型应用，需要有领域知识和统计知识，一般由具有统计 经验的领域专家来完成。 3 归纳学习方法。归纳学习方法是从大量的经验数据中归纳抽取一般的规则 和模式，其大部分算法来源于机器学习领域，归纳学习的算法有很多，如m i c h a s k i 等的a q l l ，a q l 5 ，洪家荣等的a e i ，a e 9 ，h u n t 的c l s ，q u i n l a n 的i d 3 ，c 5 o 等，其 中最著名的是q u i n l a n 提出的c 5 0 决策树算法。 4 聚类与分类方法。聚类和分类方法按一定的距离或相似性系数将数据分成 一系列相互区分的组。常用的经典聚类方法有k - m e a n ，k - m e r i o d ，i s o _ d a t a 等。 分类和聚类都是对耳标进行空间划分，划分的标准是类内差别最小而类间差别最 大。分类和聚类的区别在于分类事先知道类别数和各类的典型特征，而聚类则事 先不知道。 5 探测性的数据分析方法。李德仁、邸凯昌等提出了探测性的数据分析( 简 称e d a ) 。e d a 采用动态统计图形和动态链接窗口技术将数据及统计特征显示出来， 可发现数据中非直观的数据特征及异常数据。e d a 与空间分析相结合，构成探测性 空间分析( e x p l o r a t o r ys p a t i a la n a l y s i s ，简称e s a ) 。e d a 和e s a 技术在数据挖掘 中用于选取与问题领域相关的数据子集，并可初步发现隐含在数据中的某些特征 和规律。 6 粗糙集方法。粗糙集理论是波兰华沙大学z p a w l a k 教授在1 9 8 2 年提出的一 种智能数据决策分析工具，被广泛研究并应用于不精确、不确定、不完全的信息 的分类分析和知识获取。粗糙集理论为空间数据的属性分析和知识发现开辟了一 条新途径，可用于空间数据库属性表的一致性分析、属性的重要性、属性依赖、 属性表简化、最小决策和分类算法生成等。粗糙集理论与其他知识发现算法相结 合可以在空间数据库中数据不确定的情况下获取多种知识。 7 云理论。云理论是李德仁、邸凯昌等为解决模糊集在隶属度概念上的不确 定性而提出的一种新理论，包括云模型、虚云、云运算、云变换和不确定性推理 8 山东大学硕士学位论文 等主要内容。运用云理论进行空间数据挖掘，可进行概念和知识的表达、定量和 定性的转化、概念的综合与分解、从数据中生成概念和概念层次结构、不确定性 推理和预测等。 8 空间特征和趋势探测方法。这是e s t e r 等人在第4 届k d d 国际研讨会( 1 9 9 8 ) 上提出的基于邻域图( n e i g h b o r h o o dg r a p h s ) 和邻域路径( n e i g h b o r h o o dp a t h ) 概念的挖掘算法。e s t e r 等将一个空间特征定义为空间数据库中具有空间非空间 性质的目标对象集，并以非空间属性值出现的相对频率和不同空间对象出现的相 对频率( 目标对象集相对于整个数据库) 作为感兴趣的性质，从空间目标集合经过 它的相邻扩展后的集合中，发现相对频率的明显不同，以此提取空间规则：空间 趋势探测挖掘是从一个开始点出发，发现一个或多个非空间性质的变化规律。这 种算法的效率在很大程度上取决于其处理相邻关系的能力。 9 数字地图图像分析和模式识别方法。空间数据库中含有大量的图形图像数 据，一些图像分析和模式识别方法可直接用于挖掘数据和发现知识，或作为其他 挖掘方法的预处理方法。用于图像分析和模式识别的方法主要有：决策树i d 3 方法、 神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 方法、数学形态学方法、图论方法等。 为了发现某类知识，常常要综合运用这些方法。数据挖掘方法还要与常规的 数据库技术充分结合。 2 5 国内外空间数据挖掘系统发展概况 国际上最著名的有代表性的通用空间数据挖掘系统有：g e o m i n e r ，d e s c a r t e s 和a r c v i e wg i s 的s p l u s 接口 g e o m i n e r 是加拿大s i m o nf r a s e r 大学开发的著名的数据挖掘软件d bm i n e r 的 空间数据挖掘的扩展模块。空间数据挖掘原型系统g e o m i n e r 包含有三大模块：空间 数据立方体构建模块、空间联机分析处理( o l a p ) 模块和空间数据挖掘模块，能够进 行交互式的挖掘并显示挖掘结果。空间数据挖掘模块能挖掘三种类型的规则：特征 规则、判别规则和关联规则。g e o m i n e r 采用s a n d 体系结构，采用的空间数据挖掘 语言是g m q l 。其空间数据库服务器包括m a p i n f o ，e s r i o r a c l e s d e ，i n f o r m i x i l l u s t r a 以及其它空间数据库引擎。 d e s c a r t e s 支持可视化的分析空间数据，它与开发此软件的公司所开发的数据 挖掘工具k e p l e r 结合使用，k e p l e r 完成数据挖掘任务且拥有自己的表现数据挖掘 9 山东大学硕士学位论文 结果的非图形界面。k e p l e r 和d e s c a r t e 动态链接，把传统数据挖掘与自动作图可视 化和图形表现操作结合起来，实现c 4 5 决策树算法、聚类、关联规则的挖掘。 a r c v i e wg i s 的s - p l u s 接口是著名的e s r i 公司开发的，它提供工具分析空间数 据中的指定类。 2 6 空间数据挖掘面临的问题 从空间数据库发现知识的传统途径 4 是通过专家系统、数据挖掘、空间分析 等技术来实现的。但是在空间数据库隐含知识的发现方面，只单独依靠某一种技 术，往往存在着这样或那样的缺陷。对于专家系统来讲，专家系统不具备自动学 习的能力，g i s 中的专家系统也达不到真正的智能系统的要求，仅能利用已有的 知识进行推导。对于数据挖掘来讲，空间数据库与普通数据库的在数据存储机制 的不同和空间数据的相互依赖性等特点决定了在空间数据库中无法直接采用传统 的数据挖掘方法。对于空间分析来讲，虽然空间分析中常用的统计方法可以很好 地处理数字型数据，但是它存在的问题很多，例如统计方法通常假设空间分布的 数据问是统计上独立的，而现实中空间对象间一般是相互关联的；其次，统计模 型一般只有具有相当丰富领域知识和统计方面经验的统计专家才能用；另外，统 计方法对大规模数据库的计算代价非常高，所以在处理海量数据方面能力较低。 从上面的分析可以看出，由于空间数据具有诸多特点，因此在空间数据库进行知 识发现，需要克服使用单一技术的缺陷，即需要融合多种不同技术，所以研究人 员提出了空间数据挖掘技术来解决从空间数据库中发现隐含知识的难题。 空间数据挖掘是多学科和多种技术交叉综合的新领域，它综合了机器学习、 空间数据库系统、专家系统、可移动计算、统计、遥感、可视化等领域的有关技 术。空间数据挖掘利用空间数据结构、空间推理、计算几何学等技术，把传统的 数据挖掘技术扩充到空间数据库并提出很多有效的空间数据挖掘方法。与传统空 间分析方法相比，它在实现效率、与数据库系统的结合、与用户的交互、发现新 类型的知识等方面的能力大大增强。空间数据挖掘能与g i s 的结合，使g i s 系统具 有自动学 - 3 的功能，能自动获取知识，从而成为真正的智能空间信息系统。 1 0 山东大学硕士学位论文 第三章空间连续数据离散化方法 空间数据挖掘中要处理的大量数据是数值型连续数据，个属性可能取得属 性值数量是非常多的，甚至是无限的，但在传统数据挖掘和机器学习的分类方法 中很多是要求数据是离散的，因此空间连续数据的离散化是这些分类方法必需的 预处理过程。 离散化技术可以通过将属性值域划分为区间，减少给定连续属性值的个数， 区间的标号可以替代实际的数据值。对于空间连续数据离散化本身就是一个从具 体到抽象的归纳过程，可以比较容易地发现高层次的知识。如果使用基于决策树 或者规则生成的分类挖掘方法，通过离散化方法可以减少属性值的数量，这是一 个极为有效的数据预处理方法，可以提高相应的分类处理速度，并且可能提高分 类决策的精度。 3 1 数据挖掘中常用的离散化方法 3 1 1 分箱方法 分箱方法 2 通过考察。邻居”( 即周围的值) 来平滑存储数据的值。存储的 值被分布到一些“桶”或“箱”中。由于分箱方法参考相邻的值，因此它进行局 部平滑。对于排序后的数据，可以根据箱的平均值、箱的中值或者箱的边界来进 行平滑。 3 1 2 直方图方法 直方图法 2 是利用分箱方法对数据分布情况进行近似，它是一种常用的数据 离散化方法一个属性a 的直方图就是根据属性a 的数据分布将其划分为若干不 相交的子集( 箱) 。这些子集沿着水平轴显示，其高度( 或面积) 与该箱的所代表 的数值平均( 出现) 频率成正比。 构造直方图所涉及的数据集划分方法有以下几种： 等宽方法：在一个等宽的直方图中，每个箱的宽度( 范围) 是相同的。 等高方法：在一个等高的直方图中，每个箱的中的数据个数是相同的。 v - o p t i m a l 方法：若对指定箱个数的所有可能直方图进