（计算机应用技术专业论文）定性空间推理与空间数据挖掘技术.pdf

中文摘要 摘要 曰益丰富的地学数据在一定程度上已超过了地球科学家能够处理的能力。从 这些海量数据中发现地学知识的需要使得空间数据挖掘( s p a t i a ld a t am i n i n g ) 的产 生成为必然。空间数据挖掘是数据挖掘( d a t am i n i n g ) 的一个分支领域，它在遥感 ( r e m o t es e n s e ) * 口地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，g i s ) 中有着广泛的 应用。从g i s 中进行空间数据挖掘所发现的知识，可用于对空间数据( s p a t i a ld a t a ) 的理解、空间关系( s p a t i a lr d a t i o n s ) 知识的发现、空间数据与属性数据( p r o p e r t y d a t a ) 之问关系知识的发现、空间知识库( s p a t i a lr e p o s i t o r y ) 的构造、空间数据库 f s p a t i a ld a t a b a s e ) 的重组和空间查询( s p a t i a lq u e r y ) 的优化等。这样就可使g i s 在 资源调查、评价、管理和监测，城市的管理、规划和市政工程、行政管理与空间 决策，灾害的评估与预测、地籍管理及土地利用、交通、农业、公安等诸多领域 发挥重要作用。空间数据挖掘有许多种方法。由于空间知识本质上是定性的，所 以空间推理( s p a t i a lr e a s o n i n g ) ( 特别是定性空间推理( q u a l i t a t i v es p a t i a lr e a s o n i n g ) ) 己成为空间数据挖掘的重要的有效的方法，也是近几年研究的热点。研究、分析 和探讨空间数据挖掘和定性空间推理技术，对于提高我国城市规划、建设、管理 与服务的数字化水平，促进地理信息系统的发展，都有着极为重要的学术和实用 意义。 本论文所做的研究工作属于国家“十五”科技攻关项目：城市规划、建设、 管理与服务的数字化工程( 项目编号：2 0 0 2 b a l 0 7 b ) 的一部分。论文所论述的内容 主要有以下几方面； 首先，介绍了空间数据挖掘的特点、可发现的知识类型、知识的表示方法、 挖掘系统的结构和开发策略等等，并结合一个具体实例，给出了一个基于遗传算 法( g e n e t i c a l g o r i t h m s ) $ 口r o u g h 集( r o u g hs e 0 j j 法相结合的空间数据挖掘方法。 其次，介绍了空问推理和定性推理。 第三，研究了空间数据挖掘的一个重要的方法定性空间推理。论文分别 讨论了拓扑关系( t o p o l o g f i c a lr e l a t i o n s ) 定性表示与推理，以及方向关系( d i r e c t i o n a l r e l a t i o n s l 定性表示与推理，特别是基于井字空间的方向关系定性表示与推理方法， 给出了这种推理方法满足的定理。在此基础上，将拓扑关系和方向关系相结合， 提出了空间关系的艘表示模型r e p r e s e n t a t i o nm o d e l ) ，给出了井字空n ( s p a c e w i t hn e u t r a lz o n e l 中方向关系与拓扑关系r c c 8 之间的约束规则( c o n s t r a i n t r u l e s ) 。 重庆大学硕士学位论文 最后，本论文在上述研究工作的基础上，开发出原型系统，实现了方向关系 定性推理等功能模块，为空间数据挖掘过程提供了空间查询功能。 关键词：空间数据挖掘，定性空间推理，方向关系，拓扑关系，组合运算表 i i 蒌苎垫墨 a b s t r a c t i t sn o we x c e e dt h eg e o s c i e n t i s t s a b i l i t yt op r o c e s st h ei n c r e a s i n g l yg e o g r a p h i cd a t at o s o m ee x t e n d t h ed e m a n d o f d i s c o v e r yg e o g r a p h i ck n o w l e d g ef r o mt h eh u g ea m o u n to f d a t a m a k e st h ec e r t a i na p p e a r a n c e o f s p a t i a ld a t am i n i n g s p a t i a ld a t am i n i n gi sab r a n c ho f d a t a m i n i n g , a n d i sw i d e l yu s e di nr e m o t es e n s ea n d g e o g r a p h i ci n f o r m a t i o ns y s t e m k n o w l e d g e d i s c o v e r e db ys p a t i a ld a t am i n i n gi ng i sc a r lb eu s e df o rc o m p r e h e n s i o no f s p a t i a ld a t a ， d i s c o v e r yo fk n o w l e d g ea b o u ts p a t i a lr e l a t i o n s ，d i s c o v e r yo fk n o w l e d g ea b o u tr e l a t i o n s b e t w e e ns p a t i a ld a t aa n dp r o p e r t yd a t a ，c o n s t r u c t i o no f s p a t i a lr e p o s i t o r y ，r e o r g a n i z a t i o n o fs p a t i a ld a t a b a s e ，o p t i m i z a t i o no fs p a t i a lq u e r ya n ds oo n t h u sm a k eg i sp l a ya l l i m p o r t a n tr o l e i ni n v e s t i g a t i n g ，e v a l u a t i o n , a n dm o n i t o r i n g o f r e s o u r c e s ，c i t ym a n a g e m e n ta n d p l a n n i n g , a d m i n i s t r a t i o n ，s p a t i a ld e c i s i o n ，e v a l u a t i o na n dp r e d i c a t i o no fd i s a s t e r , c a d a s t r e m a n a g e m e n t a n dl a n de x p l o i t a t i o n ，t r a f f i c ，a g r i c u l t u r e ，p o l i c ea n de t c m a n ym e t h o d sa r eu s e d t o s p a t i a ld a t am i n i n g a ss p a t i a lk n o w l e d g ei se s s e n t i a l l yq u a l i t a t i v e ，s p a t i a lr e a s o n i n g ， e s p e c i a l l yq u a l i t a t i v e 印a t i a lr e a s o n i n g , b e c o m e s a ni m p o r t a n ta n de f f i c i e n tm e t h o do f s p a t i a ld a t am i n i n g ，a n da l s ob e c o m e s a h o t s p o t o f r e s e a r c hi nr e c e n ty e a r s i t sv e r yu s e f u lt o r e s e a r c h ，a n a l y z ea n dd i s c u s ss p a t i a ld a t am i n i n g a n d q u a l i t a t i v es p a t i a lr e a s o n i n g i t i sg r e a t l y s i g n i f i c a t i v eb o t hi ns c h o l a r s h i pa n dp r a c t i c a l i t y t o d i g i t a l i z ec i t yp l a n n i n g , c o n s t r u c t i o n ， m a n a g e m e n ta n ds e r v i c e s ，a n d t oa c c e l e r a t et h ed e v e l o p m e n to f g i s t h er e s e a r c hw o r ki nt h i sd i s s e r t a t i o ni sp a r tw o r ko ft h et e n t hn a t i o n a lf i v e y e a rp l a n o fm i n i s t r ys c i e n c ea n dt e c h n o l o g y ( n o 2 0 0 2 b a l0 7 b ) t h em a i nc o n t e n t s o ft h i s d i s s e r t a t i o na r ea sf o l l o w s ： f i r s t , w ei n t r o d u c e dt h ec h a r a c t e r i s t i c so fs p a t i a ld a t am i n i n g ，t y p e so fk n o w l e d g et h a t c a nb ed i s c o v e r e d ，k n o w l e d g er e p r e s e n t a t i o nm e t h o d s ，t h es t r u c t u r eo fm i n i n gs y s t e ma n d s y s t e md e v e l o p m e n ts t r a t e g y a l s ob ys h o w i n ga ni n s t a n c e ，w eg a v eas p a t i a ld a t am i n i n g m e t h o d ，w h i c h c o m b i n e sg e n e t i ca l g o r i t h m sa n dr o u g hs e tt o g e t h e r s e c o n d ，s p a t i a lr e a s o n i n g a n d q u a l i t a t i v es p a t i a lr e a s o n i n g a r e p r e s e n t e d f o l l o w i n gt h i s ，w eg i v e a t t e n t i o nt oa ni m p o r t a n tm e t h o do fs p a t i a ld a t am i n i n g q u a l i t a t i v es p a t i a lr e a s o n i n g q u a l i t a t i v er e p r e s e n t a t i o na n dr e a s o n i n g o f t o p o l o g i c a l r e l a t i o n s a n dd i r e c t i o n a lr e l a t i o n sa r eg i v e ni n d e t a i lr e s p e c t i v e l y a n dq u a l i t a t i v er e a s o n i n g o f d i r e c t i o n a lr e l a t i o nb a s e do ns p a c ew i t hn e u t r a lz o n e ，w i t ht h et h e o r e mt h a ti ss a t i s f i e d ，i s a l s op r e s e n t e d b a s e do nt h i s ，aq u a l i t a t i v er e p r e s e n t a t i o nm o d e lo fs p a t i a lr e l a t i o n s ，s r r e p r e s e n t a t i o nm o d e l ，w h i c hc o m b i n e sq u a l i t a t i v er e p r e s e n t a t i o no f t o p o l o g i c a lr e l a t i o n sa n d d i r e c t i o n a lr e l a t i o n s ，i sg i v e n t h ec o n s t r a i n tr u l e sb e t w e e nr c c 8 a n dd i r e c t i o n a lr e l a t i o n s i i i 重庆大学硕士学位论文 j ns p a c ew i t hn e u t r a lz o n ea r ea l s og i v e n f i n a l l y , b a s e do nt h er e s e a r c hw o r ka b o v e , w ed e v e l o p e dap r o t o t y p es y s t e m ，w h i c h r e a l i z e dt h em o d u l e ss u c ha sq u a l i t a t i v er e a s o n i n go fd i r e c t i o n a lr e l a t i o n s a n dt h es y s t e m a l s op r o v i d e ss p a t i a lq u e r yf u n c t i o nf o rs p a t i a ld a t am i n i n g k e y w o r d ：s p a t i a l d a t am i n i n g ，q u a l i t a t i v es p a t i a lr e a s o n i n g ，d i r e c t i o n a lr e l a t i o n s ， t o p o l o g i c a lr e l a t i o n s ，c o m p o s i t i o no p e r a t i o n t a b l e 1 v 1 绪论 1 绪论 1 1 研究背景 数据挖掘( d a t am i n i n g , o m ) ，也称为数据库中的知识发现( k n o w l e d g e d i s c o v e r ) , i nd a t a b a s e ，k d d ) ，简单地说，就是从大量数据中提取或“挖掘”知识 。它处理的对象一般是规模庞大的数据，目的是从中发现有用的信息1 2 】。数据挖 掘首次出现在1 9 8 9 年8 月举行的第十一届国际联合人工智能学术会议上 ”。至u 现 在为止，对在关系数据库或事务数据库中进行数据挖掘的研究已经取得了长足的 进步，并且国际上一些著名软件公司的商用的数据挖掘系统己投放市场。 空间数据挖掘( s p m i m d a t am i n i n g ) 是数据挖掘的一个分支领域，是指对空间数 据库中非显式存在的知识、空间关系或其他有意义的模式等的提取【1 。作为数据挖 掘的一个分支领域的空间数据挖掘的研究，比一般关系数据库和事务数据库中的 数据挖掘的研究要晚，但近几年已引起学术界的广泛兴趣。加拿大西蒙弗雷泽大 学、德国慕尼黑大学、芬兰赫尔辛基大学以及美国、澳大利皿等国家的许多大学 和研究所，都有空间数据挖掘研究成果的报道 4 】，其研究者大多具有计算机科学背 景。他们的研究重点是提高一般的数据挖掘算法在对g i s 中属性数据进行挖掘时 的执行效率。测绘遥感界的学者在特征提取、模式识别等的研究中实际已经做了 许多空间数据挖掘的工作，但把相关工作提到数据挖掘的高度加以系统研究的还 不多见。 与国外相比，国内对数据挖掘、空间数据挖掘的研究都要稍晚，还没有形成 整体力量。1 9 9 3 年，国家自然科学基金首次支持数据挖掘领域的研究项目。目前， 国内许多科研单位和高等院校竟相开展空间数据挖掘的研究。其中，武汉大学李 德仁院士在1 9 9 4 年就提出了从g i s 数据库发现知识的建议( l i d e r e ne ta 1 ，1 9 9 4 ) 。 他们的研究集中在空间数据挖掘和知识发现的理论、方法与应用，并得到了测绘 遥感信息工程国家重点实验室基金项目( 项目编号：w k l ( 9 7 ) 0 3 0 2 ) 和国家自然科学 基金优秀国家重点实验室研究项目( 项目编号：4 0 0 2 3 0 0 4 ) 的资助，其研究水平居国 内领先。此外，中科院地理所资源与环境信息系统国家重点实验室、中科院遥感 所等单位的学者也开展了空间数据挖掘的研究。但总的说来，空间数据挖掘的研 究还处于起步阶段。 针对空间数据挖掘，国内外学者提出了不同的理论框架，如证据理论( e v i d e n c e t h e o r y ) 、r o u g h 集理论( r o u g h s e tt h e o r y ) 和发现状态空间理论( d i s c o v e r y s t a t e s p a c e t h e o r y ) 6 1 等等，由此而产生了各种各样的空间数据挖掘和知识发现方法h 重庆大学硕士学位论文 驯：统计方法( s t a t i s t i c a l a p p r o a c h ) 、归纳方法( i n d u c t i o n ) 、聚类方法( c l u s t e r i n g ) 、 关联规则方法( a s s o c i a t i o n r u l e m i n i n g ) 、空间分析方法( s p a t i a l a n a l y s i s ) 、探测 性的数据分析( e x p l o r a t o r yd a t aa n a l y s i s ) 、云理论( c l o u dt h e o r y ) 、图像分析和模 式识别( 1 m a g e a n a l y s i s a n dp a t t e r nr e c o g n i t i o n ) 、神经网络( n e u r a ln e t w o r k ) 、证 据理论( e v i d e n c e t h e o r y ) 、可视化( v i s u a l i z a t i o n ) 、模糊集理论( f u z z y s e t t h e o r y ) 、 r o u g h 集方法( r o u g hs e t s ) 、遗传算法( g e n e t i ca 1 9 0 d t h m s ) 。本文把空间推理 ( s p a t i a lr e a s o n i n g ) 也列为其中的一种方法。因为经过近几年的研究，学者们发 现，空间数据库中含有大量的空间数据，有着比般关系数据库和事务数据库更 加丰富和复杂的语义信息，而上述传统的方法在处理空间数据时总是表现得力不 从心。克服这一缺陷的有效方法就是在空间数据挖掘中采用空间推理的方法。 空间推理是指利用空间理论和人工智能a i ( a r t i f i c i a li n t e l l i g e n c e ) 技术对空间 对象进行建模、描述和表示，并据此对空间对象间的空间关系( 方向关系、拓扑 关系、度量关系) 进行定性或定量分析和处理的过程【9 】。空间推理的研究起源于 7 0 年代初，最初是以量空间为研究对象，多维的并且不能通过单一的纯量充分表 示的空间，只是在近年成为了知识表示中的一个重要研究领域 9 】。由于空间推理的 研究对象的转变，极大地扩展了空间推理的应用领域，使空间推理的理论和应用 研究近年来有了长足的进展。在国外，近年来成立了许多专门从事空间推理方面 研究的协会和联盟，如n c g i a ( n a t i o n a lc e n t e rf o rg e o g r a p h i c a n d a n a l y s i s ) 、 u s g s ( u s g e o l o g i e a ls u r v e y ) 、欧洲定性空间推理网s p a c e n e t 以及匹兹堡大学 的空间信息课题组和慕尼黑大学空间推理课题组等等。 当前空间推理主要有以下几个比较热的研究方向： 空间推理与地理信息系统 空间决策支持系统 时空推理 定性空间推理 定性空间推理是处理常识性空间知识的一种人工智能方法p ”。由于空间知识 本质上是定性的f 2 7 1 ，所以研究空间推理的重点就是研究定性空间推理。定性空问 推理是空间推理的重要组成部分。当描述一个空间配置或对这样的配置进行推理 的时候，要获得精确、定量的数据通常是不可能的或不必要的。在这种情况下， 可能要用到关于空间配置的定性推理1 2 ，1 3 o c l a r k e 等人在拓扑关系的定性推理方 面作了先驱性的工作m 。他用c 似d 表示两个区域x 和j ，是相互连接的。在区域 连接计算r c c ( r c c ，即r e g i o n c o n n e c t i o nc a l c u l u s ，是用于定性空间表示和推 理的拓扑结构方法) 系统中，c y ) 则被稍加改动为：共享一点的区域的闭包一“。 2 1 绪论 另外，还有一种拓扑关系表示和推理的方法是“n 一交集”表示法1 4 ，1 5 1 。文献 2 8 1 则具体阐述了一种定性空间推理分层逼近方法。方向关系和度量关系的定性推理 的研究也取得了一定的进展【3 4 ，3 5 。目前，定性空间推理正在被逐步应用到空间数 据挖掘中去，成为一个研究的热点。 数据挖掘和地理信息系统近十多年的发展，积累了丰富的理论，也使得相应 技术逐步走向成熟，为空间数据挖掘和定性空间推理技术的诞生、发展及实际应 用提供了一个良好的发展平台。目前，有关空间数据挖掘和定性空间推理的文献 资料比较多，国内外都有不少这一研究领域的网站，这些为空间数据挖掘和定性 空间推理的研究工作的开展提供了大部分的理论基础和技术资料支持。 近几年兴起的定性空间推理，极大地扩展了空间数据挖掘的研究领域，成为 了空间数据挖掘技术的新生长点，人们已开始将其应用到地理信息系统中。这些 富有创新的实践，为本论文的研究工作的开展提供了良好的帮助和支持。 从2 0 0 0 年开始，我们课题组就在郭平副教授的指导下，系统地开始了本课题 的研究，几年中已取得了初步的成果。以上这些研究背景为本论文研究工作的开 展打下了良好的基础。 1 2 研究意义与目的 数据挖掘是解决“人们被数据淹没，但却饥饿于知识”的矛盾的最为有效的 手段，目前在地理学、生物医学、金融分析、零售业、电信业等许多领域都有广 泛的应用【”。空间数据挖掘是数据挖掘的一个分支领域，它可用于对空问数据的理 解、空间关系和空间与非空间数据间关系的发现、空间知识库的构造、空间数据 库的重组和空间查询的优化等。空间数据挖掘主要针对海量的地学数据，在遥藤 特别是地理信息系统( g e o g r a p h i c i n f o r m a t i o ns y s t e m ，g i s ) 中有着广泛的应用【4 j ， 已成为这一研究领域的前沿和热点。从g i s 数据库中进行空间数据挖掘所发现的 知识，可构成知识库，用于建立智能化的g i s 系统，支持知识驱动的遥感图像解 释，促进3 s 的智能化集成。同时，通过专家系统的应用，可以构建空间决策支持 系统，支持以知识为驱动的决策过程 i “。这样就可使g i s 在资源调查、评价、管 理和监测，在城市的管理、规划和市政工程、行政管理与空间决策、灾害的评估 与预测、地籍管理及土地利用、交通、农业、公安等诸多领域发挥重要作用。而 空间推理技术( 特别是定性空间推理技术) 则是空间数据挖掘的重要的有效的方 法，已成为近几年研究的热点。 近年来，空间数据挖掘的研究有了很大进展 ”。然而多数研究工作的成果都只 适用于属性数据【3 ”，对空间数据【3 习的分析能力依然很弱。解决这一矛盾的有效方 3 重庆人学硕士学位论文 法就是在g i s 中增加空间推理的功能。 技术。由于空间知识本质上是定性的， 间推理。 当前，空间推理已成为g i s 的发展的关键 所以研究空问推理的重点就是研究定性空 由上可知，研究、分析、探讨空间数据挖掘和定性空间推理技术，对于提高 我国各行业、特别是城市规划、建设、管理与服务的数字化水平，促进地理信息 系统的发展，都有着极为重要的学术和实用意义。 本论文的研究目的，就是希望在对空间数据挖掘进行全面、系统研究的基础 上，重点探讨定性空间推理中一些关键问题，在此基础上给出了我们课题组的一 些研究结论，并据此开发出原型系统，实现空间推理等功能模块。这项研究工作 属于国家“十五”科技攻关项目：城市规划、建设、管理与服务的数字化工程( 项 目编号：2 0 0 2 b a l 0 7 b ) 的一部分。 1 - 3 研究内容 本文研究的内容主要包括以下几部分： 基于遗传算法( g e n e t i c a l g o r i t h m s ) 和r o u g h 集方法相结合的空间数据挖掘 定性空间推理 基于点集拓扑学的三维拓扑空间的形式化表示( “n 交集”表示法) 与推 理 基于r c c 的定性空间表示与推理 基于井字空间的方向关系的定性表示与推理 空问数据挖掘和空间推理在g i s 中的应用 基于研究的内容和目的，论文的结构和内容如下： 空间数据挖掘的理论和技术框架 主要介绍空间数据挖掘的特点、可发现的知识类型、知识的表示方法、挖掘 系统的结构和开发策略等等，并重点介绍我们研究工作中所使用的方法和研究成 果，包括基于遗传算法和r o u g h 集方法相结合的空间数据挖掘以及其他方法。 空间推理与定性推理 主要空间推理的形式框架、研究步骤、表示体系、推理框架【2 5 】；定性系统的 构成、定性推理的基本要素、任务和基本方法等等。 定性空间推理 首先讨论空间推理中的定性与定量关系，在此基础上详细讨论拓扑关系和方 向关系的定性表示与推理，包括： 基于点集拓扑学的三维拓扑空间的形式化表示与推理 4 l 绪论 基于r c c 的定性空间表示和推理 基于井字空间的方向关系的定性表示与推理 s r 表示模型 原型系统的开发：在理论研究的基础上，利用相关的g i s 平台开发出原型 系统，实现空间推理等功能模块，并用它验证论文中有关定性空问推理与空间数 据挖掘应用的若干问题。 总结：对空间数据挖掘技术和定性空间推理做一个总结，对原型系统开发 过程中存在的问题做一个分析，确定下一步研究的方向和工作。 本论文涉及的概念之间的关系如图1 1 所示。 产生 窖蚵最据挖掘幂l 知识发现方 挂面每蕊【 。一j f 壁阃摧鞋；弭二_ 二= ， 一上= 二童立二一 + 际幕面习 图1 1 本论文涉及的概念之间的关系 f i 9 1 1r e l a t i o n s b e t w e e nt h ec o n c e p t si nt h i sd i s s e r t a t i o n 5 鐾攀一 禽 哆 一 2 空间数据挖掘研究 2 空间数据挖掘研究 2 1 数据挖掘概述 2 2 1 数据挖掘产生的背景 2 0 世纪计算机的问世和技术进步极大地促进了各行各业的发展，加快了世界 信息化的进程。从数据库角度来看，计算机信息处理的发展过程经历了三次浪潮 ( p i a t e t s k y s h a p i r o ，1 9 9 3 ；h a r t ，1 9 9 5 ) ：第一次浪潮发生于6 0 7 0 年代，代表技术是数 据采集和数据库的产生；第二次浪潮发生于7 0 8 0 年代，代表技术是数据组织和 使用、数据库中的信息检索和事务处理，其标志是关系数据库管理系统的成熟和 广泛使用；第三次浪潮发生于8 0 - 9 0 年代，代表技术是数据分布、多样性、共享 和数据理解，产生了面向对象数据库、空间数据库等等。这三次浪潮冲击的结果， 就是使得数据库急剧膨胀与对数据库处理和理解能力薄弱的矛盾逐步尖锐起来。 特别是到了现在，随着数据采集技术的迅速发展，许多领域能够实时地直接获取 数字化的数据，如超级市场的条码阅读器每天都会获得大量的产品销售数据，遥 感卫星每天也在获取巨量的对地观测数据，等等。但是，现今数据库的大多数应 用仍然停留在查询、检索阶段，数据库中隐藏的丰富的知识远远没有得到充分的 挖掘和利用，数据库急剧增长与人们对数据库处理和理解困难之间形成了强烈的 反差。“人们被数据淹没，但却饥饿于知识”正是这一反差的生动写照。面对这一 困境，人们迫切需要新的技术，能够高效、自动、智能地处理数据，从中挖掘出 可用于决策的规律性的东西，数据挖掘就是在这种背景下应运而生的。 2 1 2 数据挖掘的定义和发展历程 数据挖掘( d a t am i n i n g ，d m ) ，也称为数据库中的知识发现( k n o w l e d g e d i s c o v e r y i nd a t a b a s e ，k d d ) ，简单地说，就是从大量数据中提取或“挖掘”知识 【n 。它处理的对象一般是规模庞大的数据，目的是从中发现有用的信息吲。 数据挖掘首次出现在1 9 8 9 年8 月举行的第十一届国际联合人工智能学术会议 上【4 1 。经过十几年的发展，对在关系数据库或事务数据库中进行数据挖掘的研究已 经取得了长足的进步。这期间代表性的工作有：用面向属性的归纳方法在关系数 据库中发现特征规则和区分规则( c a i e ta 1 ，1 9 9 1 ；h a ne ta 1 ，1 9 9 2 ) ；在事务数据库中 发现关联规则( a g r a w a l e ta 1 ，1 9 9 4 ) ；基于距离的和基于密度的聚类分析的优化( n g e t a l 1 9 9 4 ：e a s t e re t a l ，1 9 9 6 ) 等。为了处理数据库中的不确定性问题，r o u g h 集和 模糊集理论得到了广泛的研究与应用( p a w l a k ，1 9 9 1 ；z i a r k o ，1 9 9 4 ) 。另外，决策树、 神经网络、遗传算法、可视化等方法也在机器学习与知识发现中得到了研究与应 用。在数据挖掘领域，最有影响的挖掘算法有加拿大s i m o n f r a s e r 大学j h a n 教授 7 重庆大学硕士学位论文 的概念树提升算法( h a n e ta 1 ，1 9 9 2 ) 、i b m 的r a g r a w a l 的a p r i o r i 关联算法( a g r a w a l e ta 1 ，1 9 9 4 ) 、澳大利亚的j r q u i n l a n 教授的分类算法c 4 5 c 5 0 ( q u i n l a n ，1 9 9 3 ) 、 z h a n g 等的b i r c h 聚类算法( z h a n ge ta 1 ，1 9 9 6 ，1 9 9 7 ) 、密歇根州立大学e r i c k g o o d m a n 的遗传算法等。 由于是在强烈的应用需求背景下产生的，数据挖掘技术从一开始就是面向应 用的。目前，国际上一些著名软件公司的商用的数据挖掘系统已投放市场。最有 影响的数据挖掘系统有：i b m 公司的i n t e l l i g e n t m i n e r 、s a s 公司的e n t e r p r i s e m i n e r 、 s g i 的m i n e s e t 、s p s s 公司的c l e m e n t i n e 、s y b b s e 的w a r e h o u s es t u d i o 、s t a n f o r d s y s t e m s 的c a r t 、t h i n k i n gm a c h i n e s 公司的d a r w i n 、r u l e q u e s tr e s e a r c h 公司的 s e e 5 、还有c o v e r s t o r y 、q u e s t 、d b m i n e r 等。数据挖掘是解决“人们被数据淹没， 但却饥饿于知识”的矛盾的最为有效的手段之，目前在地理学、生物医学、金 融分析、零售业、电信业等许多领域都有广泛的应用【“。 2 1 3 数据挖掘的主要研究内容 数据挖掘是一个由数据库、人工智能、数理统计、可视化等多种学科和技术 交叉、渗透和融合形成的交叉学科，其研究内容十分广泛。在理论与方法方面， 其主要研究内容包括数据挖掘的理论基础、新的高效的算法、递增式数据挖掘、 不确定性情况下的数据挖掘、背景知识概念层次结构的自动形成、数据仓库、可 视化技术、定性定量互换模型、知识表示方法、发现知识的再利用、半结构化和 非结构化数据中的知识发现、i n t e m e t 上的数据挖掘和知识发现等等；在系统的实 现方面，研究内容包括多种算法的集成、数据挖掘系统与其它系统的集成、数据 挖掘系统中的人机交互技术和可视化技术。 从可发现的知识类型来看，数据挖掘一般主要发现下面几类知识： 广义型知识( g e n e m l i z a t i o n ) _ 一根据数据的微观特性发现其表征的、带有普遍 性的、较高层次概念的、中观和宏观的知识。用于对数据的概括、精炼和抽象。 分类型知识( c l a s s i f i c a t i o n c l u s t e r i n g 卜反映同类事物共同性质的特征型 知识和不同事物之间差异型特征知识。用于反映数据的汇聚模式或用根据对象的 属性区分其所属类别。 关联型知识( a s s o c i a t i o n ) 反映一个事件和其它事件之间依赖或关联的知 识，又称依赖关系( d e p e n d e n c y ) 。这类知识可用于数据库中的归一化，查询的优 化等。 预测型知识( p r e d i c t i o n ) 通过时间序列型数据，由历史的和当前的数据 去预测未来的情况。它实际上是一种以时间为关键属性的关联知识。 偏差型知识( d e v i a t i o n ) 偏差型知识对差异和极端特例的描述，如标准 类以外的特例，数据聚类以外的离群值，实际观测值和系统预测值之间的显著差 8 一一! 窒堕塾塑丝塑堡窒 别。 2 1 4 数据挖掘的研究方法与策略 从数据挖掘的定义和对其进行的分析可以看出，数据挖掘有以下特点：( 1 ) 数据源是真实的、大量的、含噪声的；( 2 ) 数据源支持相应的发现，但发现的知 识是隐含的，事先不知道的；( 3 ) 发现的是人们感兴趣的知识；( 4 ) 发现的知识 可接收、可理解、可运用：( 5 ) 不要求发现放之四海皆准的知识，仅解决特定的 问题。 由于数据挖掘自身的这些特点，其研究方法和技术策略也有其鲜明的特色： 首先，在研究方法上，数据挖掘采用以归纳为主、归纳与演绎相结合的方法 从数据中发现模式和规则采用归纳逻辑，而模式评价和规则推理采用演绎逻 辑。 其次，由于数据挖掘要处理的数据一般是大型的数据库，而数据不完整、不 精确、有噪声、模糊的情况经常存在。这样，一方面，数据挖掘研究中重视各种 不确定性的研究，统计方法、模糊集理论、r o u g h 集理论等得到了广泛应用；另一 方面，数据挖掘也注重算法的效率，比如：对关联规则挖掘算法的大量研究都是 在努力减少扫描数据库的次数，提高算法速度。 第三，在数据挖掘过程中，定性分析和定量分析同样重要，需要相互结合。 特别是在空间数据挖掘的过程中，定性分析也能够深刻地反映问题的本质，并且 用较少的代价就能传递足够的信息，对复杂问题做出高效率的判断和推理。所以 在数据挖掘中既采用定量的计算来分析和处理数据，也充分重视定性思维和描述 的作用。 最后，数据挖掘系统的实现强调集成和交互。集成意指数据挖掘系统与数据 库管理系统、数据分析系统、专家系统、决策支持系统等的集成，数据挖掘系统 并不能解决实际应用中的所有问题，必须与相关系统相结合和集成才能发挥更大 的作用。在我们的国家“十五”科技攻关项目( 项目编号：2 0 0 2 b a l 0 7 b ) 的实旋过 程中，我们特别强调的是g i s 与数据挖掘系统的集成。交互即要求数据挖掘系统 有较强的人机交互能力。完全让系统自发地去发现会得到大量没有价值的模式， 而且效率很低，除非是非常专用的系统。用户的作用一般是选择数据子集、选择 感兴趣的知识类、提供背景知识、结果的选择和解释等。系统根据用户的启发和 限制自动地从数据库中提取高质量的特征模式。并且，这种人机交互需要不断循 环，使得用户对数据的理解不断深入，才能使最终得到的知识更有价值。在我们 的项目实施过程中，我们也非常注重人机交互，用户对整个挖掘过程都有控制能 力，结果也尽量以可视化的形式呈现给用户。 9 重庆火学硕士学位论文 2 2 空间数据挖掘概述 由于空间数据挖掘是数据挖掘的一个分支领域，所以这里不再重复与数据挖 掘相同的概念，而是重点介绍以下几个问题。 2 2 1 从数据挖掘到空间数据挖掘 空间数据挖掘( s p a t i a ld a t am i n i n g ) 是从数据挖掘发展而来的，是数据挖掘的一 个分支领域。它的挖掘平台从一般的事务数据库转移到了空间数据库。空间数据 挖掘是指对空间数据库中非显式存在的知识、空间关系或其他有意义的模式等的 提取【l 】。它可用于对空间数据的理解、空间关系和空间与非空间数据间关系的发现、 空间知识库的构造、空间数据库的重组和空间查询的优化等。空间数据挖掘主要 针对海量的地学数据，在遥感特别是地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ， g i s ) 中有着广泛的应用1 4 1 ，己成为这一研究领域的前沿和热点。 由以上定义可知，由于空间数据挖掘是指对空间数据库中非显式存在的知识、 空间关系或其他有意义的模式等的提取，因此，较数据挖掘而言，空间数据挖掘 的特点在很大程度上决定于空间数据库的特点。 空间数据库是一类重要的、特殊的数据库，除最具代表的g i s 外，它还包括 图像数据库、c a d 数据库等f 3 ”。空间数据库存有大量空间对象，它们以空间数据 类型( 如点、线、区域等) 和空间关系( 如相离、相交和包含等) 表示。空间数 据具有许多独有的特性，它带有拓扑、方位和( 或) 距离信息，通常以复杂的多 维空间索引结构组织，通过空间数据存取方法存取，常常需要空问推理、几何计 算和空间知识表示等技术。因而针对空间数据库的数据挖掘就有以下特点： 在空间数据库中实施数据挖掘，首先需要确定把什么作为处理的元组，我 们称之为空间数据挖掘的粒度问题i4 1 。针对空间数据结构的特点，我们把空间数据 挖掘的粒度分为两种：一种是在空间对象粒度上挖掘，另种是直接在像元粒度 上挖掘。空间对象可以是图形数据库中的面、线和点对象，也可以是遥感图像中 经过处理和分析得到的面特征( 如均质取多边形) 和线特征( 如边缘线) 。像元主 要指遥感图像的像元，也就是栅格图形的单元。空间数据挖掘粒度的确定取决于 数据挖掘的目的，即发现的知识做什么用，也取决于空间数据库的结构。本论文 采用的粒度是空间对象。以空问对象作为数据挖掘的粒度，可以充分利用空间对 象的位置、形态特征、空阅关联等特征，得到空问分布规律、广义特征规则、分 类规则等多种知识，可用于定性空间推理，也可用于遥感图像分类。 确定了空间数据挖掘的粒度后，需要确定元组的属性。在一般的关系数据 库中，学习的属性直接取自字段或经过简单的数学或逻辑运算派生出学习用的属 性。空间数据库中图形的几何特征和空间关系等一般并不直接存储于数据库中， 而是隐含在多个图层的图形数据中，需要经过专有的空间运算和空间分析才能得 1 0 ! 窒塑鳖塑垄塑婴窒 到归纳学习用的属性。这也是空间数据挖掘区别于一般关系数据库中的数据挖掘 的主要特征。 需要修改现有的数据挖掘算法使其适合在空间数据库中进行挖掘。现有的 数据挖掘算法大多是针对关系数据库设计的。关系数据库是结构化的，数据库的 记录作为元组，字段作为属性，便于数据挖掘算法的实施。而空问数据库比一般 的关系数据库要复杂得多，既有空间数据又有属性数据。其中空间数据是一种非 结构化的数据。它既有矢量数据又有栅格数据，所以在空间数据库中实施数据挖 掘比在一般的关系数据库中实施要复杂。由于空间数据的复杂性及其应用的专业