定性空间推理与空间数据挖掘技术.pdf

《定性空间推理与空间数据挖掘技术.pdf》由会员分享，可在线阅读，更多相关《定性空间推理与空间数据挖掘技术.pdf（113页珍藏版）》请在三一文库上搜索。

1、重庆大学 硕士学位论文 定性空间推理与空间数据挖掘技术 姓名：刘然 申请学位级别：硕士 专业：计算机应用技术 指导教师：郭平 20031108 中文摘要 摘要 曰益丰富的地学数据在一定程度上已超过了地球科学家能够处理的能力。从 这些海量数据中发现地学知识的需要使得空间数据挖掘( 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

2、 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

3、 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 ) ) 己成为空间数据挖掘的重要的有效的方法，也是近几年研究的热点。研究、分析 和探讨空间数据挖掘和定性空间推理技术，对于提

4、高我国城市规划、建设、管理 与服务的数字化水平，促进地理信息系统的发展，都有着极为重要的学术和实用 意义。 本论文所做的研究工作属于国家“十五”科技攻关项目：城市规划、建设、 管理与服务的数字化工程( 项目编号：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 法相结合

5、的空间数据挖掘方法。 其次，介绍了空问推理和定性推理。 第三，研究了空间数据挖掘的一个重要的方法定性空间推理。论文分别 讨论了拓扑关系( 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

6、( 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

7、 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

8、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 n

9、o 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

10、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

11、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

12、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

13、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

14、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 n

15、t 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

16、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

17、 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

18、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

19、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

20、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

21、 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

22、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

23、 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

24、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 ) 是数据挖掘的一个分支领域，是指对空间

25、数 据库中非显式存在的知识、空间关系或其他有意义的模式等的提取【1 。作为数据挖 掘的一个分支领域的空间数据挖掘的研究，比一般关系数据库和事务数据库中的 数据挖掘的研究要晚，但近几年已引起学术界的广泛兴趣。加拿大西蒙弗雷泽大 学、德国慕尼黑大学、芬兰赫尔辛基大学以及美国、澳大利皿等国家的许多大学 和研究所，都有空间数据挖掘研究成果的报道 4 】，其研究者大多具有计算机科学背 景。他们的研究重点是提高一般的数据挖掘算法在对G I S 中属性数据进行挖掘时 的执行效率。测绘遥感界的学者在特征提取、模式识别等的研究中实际已经做了 许多空间数据挖掘的工作，但把相关工作提到数据挖掘的高度加以系统研究的还

26、 不多见。 与国外相比，国内对数据挖掘、空间数据挖掘的研究都要稍晚，还没有形成 整体力量。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 ) 和国家自然科学 基金优秀国家重点实验室研究项目( 项目

27、编号：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 等等，由此而产生了各种

28、各样的空间数据挖掘和知识发现方法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

29、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

30、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 ) 技术对空间 对象进行建模、描述和表示，并据此对空间对象间的空间关系( 方向关系

31、、拓扑 关系、度量关系) 进行定性或定量分析和处理的过程【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

32、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 ，所以研究空间推理的重点就是研究定性空间推理。定性空问 推理是空间推理的重要组成部分。当描述一个空间配置或对这样的配置进行推理 的时候，要获得精确、定量的数据通常是不可能的或不必要的。在

33、这种情况下， 可能要用到关于空间配置的定性推理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 则具体阐述了一种定性空间推理分层逼近

34、方法。方向关系和度量关系的定性推理 的研究也取得了一定的进展【3 4 ，3 5 。目前，定性空间推理正在被逐步应用到空间数 据挖掘中去，成为一个研究的热点。 数据挖掘和地理信息系统近十多年的发展，积累了丰富的理论，也使得相应 技术逐步走向成熟，为空间数据挖掘和定性空间推理技术的诞生、发展及实际应 用提供了一个良好的发展平台。目前，有关空间数据挖掘和定性空间推理的文献 资料比较多，国内外都有不少这一研究领域的网站，这些为空间数据挖掘和定性 空间推理的研究工作的开展提供了大部分的理论基础和技术资料支持。 近几年兴起的定性空间推理，极大地扩展了空间数据挖掘的研究领域，成为 了空间数据挖掘技术的新生长

35、点，人们已开始将其应用到地理信息系统中。这些 富有创新的实践，为本论文的研究工作的开展提供了良好的帮助和支持。 从2 0 0 0 年开始，我们课题组就在郭平副教授的指导下，系统地开始了本课题 的研究，几年中已取得了初步的成果。以上这些研究背景为本论文研究工作的开 展打下了良好的基础。 1 2 研究意义与目的 数据挖掘是解决“人们被数据淹没，但却饥饿于知识”的矛盾的最为有效的 手段，目前在地理学、生物医学、金融分析、零售业、电信业等许多领域都有广 泛的应用【”。空间数据挖掘是数据挖掘的一个分支领域，它可用于对空问数据的理 解、空间关系和空间与非空间数据间关系的发现、空间知识库的构造、空间数据 库

36、的重组和空间查询的优化等。空间数据挖掘主要针对海量的地学数据，在遥藤 特别是地理信息系统( 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 在资源调查、评价、管 理和监测，在城市的管理、规划和

37、市政工程、行政管理与空间决策、灾害的评估 与预测、地籍管理及土地利用、交通、农业、公安等诸多领域发挥重要作用。而 空间推理技术( 特别是定性空间推理技术) 则是空间数据挖掘的重要的有效的方 法，已成为近几年研究的热点。 近年来，空间数据挖掘的研究有了很大进展 ”。然而多数研究工作的成果都只 适用于属性数据【3 ”，对空间数据【3 习的分析能力依然很弱。解决这一矛盾的有效方 3 重庆人学硕士学位论文 法就是在G I S 中增加空间推理的功能。 技术。由于空间知识本质上是定性的， 间推理。 当前，空间推理已成为G I S 的发展的关键 所以研究空问推理的重点就是研究定性空 由上可知，研究、分析、探

38、讨空间数据挖掘和定性空间推理技术，对于提高 我国各行业、特别是城市规划、建设、管理与服务的数字化水平，促进地理信息 系统的发展，都有着极为重要的学术和实用意义。 本论文的研究目的，就是希望在对空间数据挖掘进行全面、系统研究的基础 上，重点探讨定性空间推理中一些关键问题，在此基础上给出了我们课题组的一 些研究结论，并据此开发出原型系统，实现空间推理等功能模块。这项研究工作 属于国家“十五”科技攻关项目：城市规划、建设、管理与服务的数字化工程( 项 目编号：2 0 0 2 B A l 0 7 B ) 的一部分。 1 - 3 研究内容 本文研究的内容主要包括以下几部分： 基于遗传算法( G e n

39、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 集方法相结合的空间

40、数据挖掘以及其他方法。 空间推理与定性推理 主要空间推理的形式框架、研究步骤、表示体系、推理框架【2 5 】；定性系统的 构成、定性推理的基本要素、任务和基本方法等等。 定性空间推理 首先讨论空间推理中的定性与定量关系，在此基础上详细讨论拓扑关系和方 向关系的定性表示与推理，包括： 基于点集拓扑学的三维拓扑空间的形式化表示与推理 4 l 绪论 基于R C C 的定性空间表示和推理 基于井字空间的方向关系的定性表示与推理 S R 表示模型 原型系统的开发：在理论研究的基础上，利用相关的G I S 平台开发出原型 系统，实现空间推理等功能模块，并用它验证论文中有关定性空问推理与空间数 据挖掘应用的

41、若干问题。 总结：对空间数据挖掘技术和定性空间推理做一个总结，对原型系统开发 过程中存在的问题做一个分析，确定下一步研究的方向和工作。 本论文涉及的概念之间的关系如图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

42、 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 年代，代表技术是数据分

43、布、多样性、共享 和数据理解，产生了面向对象数据库、空间数据库等等。这三次浪潮冲击的结果， 就是使得数据库急剧膨胀与对数据库处理和理解能力薄弱的矛盾逐步尖锐起来。 特别是到了现在，随着数据采集技术的迅速发展，许多领域能够实时地直接获取 数字化的数据，如超级市场的条码阅读器每天都会获得大量的产品销售数据，遥 感卫星每天也在获取巨量的对地观测数据，等等。但是，现今数据库的大多数应 用仍然停留在查询、检索阶段，数据库中隐藏的丰富的知识远远没有得到充分的 挖掘和利用，数据库急剧增长与人们对数据库处理和理解困难之间形成了强烈的 反差。“人们被数据淹没，但却饥饿于知识”正是这一反差的生动写照。面对这一 困

44、境，人们迫切需要新的技术，能够高效、自动、智能地处理数据，从中挖掘出 可用于决策的规律性的东西，数据挖掘就是在这种背景下应运而生的。 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 月举行的第十一届国际联合人工智能学术会议 上【

45、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 集和 模糊集理论得到了广泛的

46、研究与应用( 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

47、 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

48、 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 等。数

49、据挖掘是解决“人们被数据淹没， 但却饥饿于知识”的矛盾的最为有效的手段之，目前在地理学、生物医学、金 融分析、零售业、电信业等许多领域都有广泛的应用【“。 2 1 3 数据挖掘的主要研究内容 数据挖掘是一个由数据库、人工智能、数理统计、可视化等多种学科和技术 交叉、渗透和融合形成的交叉学科，其研究内容十分广泛。在理论与方法方面， 其主要研究内容包括数据挖掘的理论基础、新的高效的算法、递增式数据挖掘、 不确定性情况下的数据挖掘、背景知识概念层次结构的自动形成、数据仓库、可 视化技术、定性定量互换模型、知识表示方法、发现知识的再利用、半结构化和 非结构化数据中的知识发现、I n t e m e t 上的数据挖掘和知识发现等等；在系统的实 现方面，研究内容包括多种算法的集成、数据挖掘系统与其它系统的集成、数据 挖掘系统中的人机交互技术和可视化技术。 从可发现的知识类型来看，数据挖掘一般主要发现下面几类知识： 广义型知识( G e n e m l i z a t i o n ) _ 一根据数据的微观特性发现其表征的、带有普遍 性的、较高