（地图学与地理信息系统专业论文）空间关联规则发掘技术研究.pdf

摘要 从人工智能的应用来看，专家系统的研究虽然取得了一定进展，但知识获取 仍然是专家系统研究的瓶颈。知识工程师从领域专家处获取知识是非常复杂的个 人到个人之间的交互，具有很强的个性，没有统的方法。因此，有必要考虑从 数据库中发现新的知识。空间知识发现是从地理信息数据库中提取隐含的、用户 感兴趣的空间的和非空间的模式和普遍特征的过程。同空间数据库管理系统检索 和查询出的信息相比，空间知识发现技术发现的知识是隐含、精练、高水平的。 这些知识一方面可以提高空间数据分析和应用的智能化水平，另一方面可用于支 持遥感图像的自动解释和分类识别，促进遥感与g i s 的智能化集成。空间知识 发现已成为理解和应用空间数据库的一项重要任务。 空间关联规则是描述一组空间谓词和非空间谓词间的某种关联关系的规则， 是空间知识发现的对象之一。强规则表现了数据库中发生频繁、具有强隐含关系 的规则模式。发掘多概念层次关联规则是空间关联规则采掘研究必须丽对的问 题。本文首先运用云理论对多值型属性数据( 或数值型数据) 进行了概念的划分， 建立属性概念层次。云理论是建立在传统模糊集理论和概率统计基础上的定性定 量不确定性转换模型，它构成定性和定量相互间的映射，解决了作为模糊集理论 基石的隶属函数概念的固有缺陷，是一种对属性空间的软划分方法。 在运用a r c s d e 几何模型计算空间关系的基础上，本研究采用一种自上丽下 的、渐进式深入的搜索技术，提取感兴趣的强空间关联规则，即首先计算空间对 象间的粗略空间关系，其次在已建立的属性概念层次的顶层，发掘具有强隐含关 系的大模式，然后对这些大模式，在低属性概念层次深入计算，直到不能发现大 的模式为止，最后过滤掉那些不能满足大模式要求的空间对象，对需要详查的候 选空间谓词，进行细化空闯计算。对中国植被数据库空间关联规则挖掘研究证实， 从大空间数据库中取得感兴趣的强关联规则是可行的。 论文也讨论了非同等概念层次关联规则的发掘，因为每种空间对象具备多层 概念层次，而且层数可能不同，或者用户感兴趣某些交叉概念层次上的关联规则， 这样就造成高层次不能出现的模式，反而会在低层次出现，影响规则的提取。本 文对这种情况做了初步的分析，提出了解决这个问题的基本方法。 关键词：空间知识发现空间关联规则云理论地理信息数据库 a b s t r a c t a l o n gw i t ht h ep r o g r e s so fa r t i f i c i a l i n t e l l i g e n c e ，a l t h o u g he x p e r ts y s t e mb a s c e r t a i ni m p r o v e m e n t , t h e k n o w l e d g eo b t a i n i n gi ss t i l lab o r l e n e c ki ne x p e ns v s t e m s ， s t u d y t h ep r o c e s so fk n o w l e d g ee n g i n e e r so b t a i n i n gk n o w l e d g ef r o mr e a l m e x p e r t s w h i c hh a sv e r ys t r o n gc h a r a c t e ra n dn ou n i t e dw a yi sa v e r yc o m p l i c a t e di n d i v i d u a l i n t e r a c t i o nw i t he a c ho t h e r t h e r e f o r e ，i ti s n e c e s s a r yt oc o n s i d e rd i s c o v e r i n gn e w k n o w l e d g ef r o mt h ed a t a b a s e s t h es p a t i a ld a t am i n i n g ，i 。e d i s c o v e r yo fi n t e r e s t i n g ， i m p l i c i tk n o w l e d g ei ns p a t i a ld a t a b a s e s ，i sa l li m p o r t a n tt a s kf o ru n d e r s t a n d i n ga n d u s i n go fs p a t i a ld a t a - a n dk n o w l e d g e - b a s e s c o m p a r i n gw i t he x p l o r i n ga n d q u e r y i n g o f s p a t i a l d a t a b a s e s m a n a g e m e n ts y s t e m s ，t h e k n o w l e d g em i n i n gb ys p a t i a l k n o w l e d g ed i s c o v e r yt e c h n i q u e i sm o r ei m p l i c i t ，h i g h e r q u a l i t y ，a n d h a sm o r e w o r t h i n e s s o n eh a n dw ec a r li n c r e a s e i n t e l l i g e n tl e v e lf o ra n a l y z i n ga n da p p l y i n g s p a t i a ld a t a o nt h eo t h e rh a n dw ec 觚u s et h ek n o w l e d g et os u p p o r tr e m o t es e n s i n g i m a g e s a u t o m a t i ci n t e r p r e t a t i o na n dc l a s s i f i c a t i o n , i nf a v o ro f a c c e l e r a t i n gi n t e l l i g e n t i n t e g r a t i o no f r s a n dg i s f i r s t l y ，n u m e r i c a lv a l u ei sp a r t i t i o n e dw i t hc l o u dm o d e l ，s i n c ec o n c e p th i e r a r c h y p l a y saf u n d a m e n t a l l yi m p o r t a n tr o l ei nd a t am i n i n g c l o u dm o d e lw h i c hc o n v e r t s c o n t i n u a ln u m e r i c a lv a l u ef r o mq u a l i t yt o q u a n t i t yb a s e do nf u z z ys e tt h e o r ya n d p r o b a b i l i t y ，a n df o r m sam a pb e t w e e nq u a l i t ya n dq u a n t i t y ，i saf l o p p yp a r t i t i o n m e t h o d s p a t i a l a s s o c i a t i o nr u l ei sar u l e i n d i c a t i n g c e r t a i na s s o c i a t i o n r e l a t i o n s h i p a m o n ga s e to fs p a t i a la n dp o s s i b l ys o m en o n s p a t i a l p r e d i c a t e s as t r o n gr u l e i n d i c a t e st h a tt h ep a t t e r n sh a v er e l a t i v e l yf r e q u e n to c c u r r e n c e si nt h ed a t a b a s ea n d s t r o n gi m p l i c a t i o nr e l a t i o n s h i p s i nt h i st h e s i s ，s p a t i a lr e l a t i o n s h i p sa r ec o m p u t e d u s i n ga r c s d eg e o m e t r ym o d e l ，a n ds t r o n gs p a t i a la s s o c i a t i o nr u l e sa r em i n e dw i t ha n e f f i c i e n tm e t h o di nv e g e t a t i o ng e o g r a p h i ci n f o r m a t i o nd a t a b a s e s w i t hat o p d o w n ， p r o g r e s s i v ed e e p e n i n gs e a r c ht e c h n i q u e ，f i r s t l ys e a r c h e sa tah i g hc o n c e p tl e v e lf o r l a r g e ( i e ，f r e q u e n t l yo c c u r r i n g ) p a t t e r n sa n ds t r o n gi m p l i c a t i o nr e l a t i o n s h i p sa m o n g t h el a r g ep a r e m sa tac o a r s er e s o l u t i o ns c a l e ，a n d s e c o n d l yd e e p e n st h es e a r c ht o l o w e rc o n c e p tl e v e l s ( i e ，t h e i rl o w e rl e v e ld e s c e n d a n t s ) o n l yf o rt h o s el a r g ep a t t e r n s s u c ha d e e p e n i n gs e a r c hp r o c e s sc o n t i n u e su n t i ln ol a r g ep a t t e r n sc a n b ef o u n d o n l y t h ec a n d i d a t e s p a t i a lp r e d i c a t e s ，w h i c h a r ew o r t h yd e t a i l e d e x a m i n a t i o n ，w i l lb e c o m p u t e db yr e f i n e ds p a t i nt e c h n i q u e s ( g i v i n gd e t a i l e dp r e d i c a t e ss u c ha si n t e r s e c t ， c o n t a i n , e t c ) a n a l y s i ss h o w st h a ti n t e r e s t i n ga s s o c i a t i o nr u l e s c a l lb ed i s c o v e r e d e f f i c i e n t l yi nl a r g es p a t i a ld a t a b a s e a l s o ，a s s o c i a t i o nr u l e s m i n i n gw h i c hi sb a s e do nn o n e q u i t a b l ec o n c e p tl e v e l s h a v eb e e nd i s c u s s e d ，s i n c ee v e r ys p a t i a lo b j e c tm a yh a si t sc o n c e p tl e v e l so fw h i c h t h en u m b e r sa r eu s u a l l yd i f f e r e n t ，o ru s e r sm a yb ei n t e r e s t e di nt h er u l e so nc r o s s e d l e v e l s t h i s m a yr e s u l t i nt h e d i s a p p e a r a n c e o fp a t t e r n sa t h i g h e rl e v e l s ，a n d a p p e a r a n c e a tl o w e rl e v e l s ，w h i c hw i l li n f l u e n c ee x t r a c t i o no fr u l e s ap r i m a r y a n a l y s i so n t h i sp h e n o m e n o ni sc o n d u c t e da n dab a s i cm e t h o dt or e s o l v et h i sp r o b l e m i sp r o p o s e di nt h i sp a p e r k e y w o r d ：s p a t i a lk n o w l e d g ed i s c o v e r y ，s p a t i a la s s o c i a t i o nr u l e ，c l o u dt h e o r y ， g e o g r a p h i ci n f o r m a t i o n d a t a b a s e 原创性声明 y - 7 3 2 0 3 9 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行研究所 取得的成果。学位论文中凡引用他人已经发表或未发表的成果、数据、观点等 均已明确注明出处。除文中已经注明引用的内容外，不包含任何其他个人或集体 已经发表或撰写过的科研成果。对本文的研究成果做出重要贡献的个人和集体 均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：型悼日期：丝垒至兰丛 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州大 学。本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保存或向 国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和借阅；本人 授权兰州大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可 以采用任何复制手段保存和汇编本学位论文。本人离校后发表、使用学位论文或 与该论文直接相关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：缉导师签名：烨日期： 玉秘劳手j 2 扩 兰州大学研究生学位论文 第1 章绪论 1 。1 论文选题意义 1 1 1 遥感与g i s 面临的困难 遥感( r s ) 、地理信息系统( g i s ) 和全球定位系统( g p s ) 技术构成了现 代对地观测技术中信息获取、存储管理、更新、分析和应用的三大支撑技术( 简 称3 s ) 。随着它们各自的发展，这三大技术逐渐向集成化发展( 李德仁，1 9 9 6 ) 。 3 s 集成来自于工程应用需求的驱动，也是3 s 技术发展的必然结果。在3 s 集成 中，g p s 主要用于实时、快速地提供目标，包括各类传感器和运载平台的空间 位置：r s 用于实时或准时地提供目标及其环境的语义和非语义信息，发现地球 表面的各种变化，及时对g i s 进行数据更新；g i s 对多种来源的时空数据进行 综合处理、集成管理、动态存取，作为新的集成系统的基础平台，并为智能化 数据采集提供地学知识( 李德仁，1 9 9 6 ) 。 遥感、g i s 及其集成不断发展的同时，也面临着许多困难与挑战。面对海量 的遥感数据和地理信息系统实时及动态分析的需要，当前的瓶颈问题仍然是遥 感数据的自动处理系统软件问题( 李德仁，1 9 9 5 ) 。 卫星遥感是数字地球获取数据的主要手段之一，高分辨率卫星影像将是构 成数字地球最基本的空间数据。1 9 9 9 年末，以美国i k o n o s 卫星为代表的1 m 分辨率商用卫星数据已开始提供给全世界的用户，随着其他商用高分辨率卫星 计划的实施，我们在享受科技进步的同时，也将面临要求快速、自动处理海量 遥感数据的更加严峻的挑战( 邸凯昌，2 0 0 0 1 。戈尔在“数字地球”的演讲中清 楚地描述了这种挑战( a lg o r e ，1 9 9 8 ) ，“充分利用这些浩瀚的数据的困难在于 把这些数据变得有意义即把原始数据变成可理解的信息。今天，我们经常 发现我们拥有很多数据，却不知如何处置。” 遥感自动处理的主要困难在于语意信息的自动提取，即遥感图像的自动解 译。遥感成像是地表的三维景物向二维景物平面的投影，这一过程造成了信息 的损失，并且不可避免地加入了许多噪音，影像解译和目标识别是从二维影像 恢复三维景物，是一个非适定问题，无法从数学上直接求得确定解，需要依赖 第l 章绪论 于人的知识来引导和约束，以求得最优解，而用于影像自动解译的知识的获取 是十分困难的( 林宗坚，1 9 9 5 刘少刨，1 9 9 7 ) 。如何自动地从海量遥感数据中 提取有用的信息、发掘隐含的知识，是数字地球要解决的关键问题之一，丽从 数据中发掘和发现有用的信息和知识，正是数据发掘和知识发现这新兴领域 的核心问题。 事实上，一个g i s 系统的核心是数据，收集数据的目的是为了使用数据产 生社会和经济效益。同样地，数字地球的核心是全球的空间数据和与之相关的 社会、经济数据( a lg o r e ，1 9 9 8 ) ，为了深入地理解和应用这些数据，我们需 要将它转换为信息和知识。目前，绝大多数g i s 系统对空间数据的利用主要是 查询、空间分析和简单统计，这仅可以满足某些低层次的需求。但人们更迫切 需要的是从大量数据中发掘出对决策具有指导意义的知识，这些知识比用简单 的查询和统计获取的信息更加概括、更加浓缩和精练，是对数据更深刻的认识， 因而更有价值( 徐铭杰，2 0 0 2 ) 。从空间数据库中发掘出的知识一方面可用于决 策支持，提高g i s 数据分析和利用的智能化水平，另一方面可以支持遥感图像 的自动解译，提高解译的自动化水平，从而促进g i s 与遥感的智能化集成( 邸 凯昌，2 0 0 0 ；罗剑承，2 0 0 0 ) 。因此，如何从大量的、含有多种不确定性的空间 数据种发掘隐含的、有价值的知识，是一项十分重要的前沿性课题，不仅在遥 感和g i s 领域有重要意义，也是地球空间信息科学和数字地球的关键支撑技术 之一。隐藏在巨量空间数据中的知识的理解和提取，是对现在可用空间数据库 技术的巨大挑战。 1 1 2 空间知识发现技术的发展 目前在地理学数据分析中对空间特性的处理主要有以下几种方法( 郭仁忠， 2 0 0 1 ) ：( 1 ) 将空间作为框架，同一区域范围内不考虑空间要素，静态研究如各 种区域统计指标计算、动态研究如系统动力学模型等。( 2 ) 利用空间统计方法， 如变异函数、空间自相关指数等，探讨空间分布的特征。( 3 ) 将空间要素转化 为一维属性要素参与分析，如距离、方向等用于主成分分析、多变量相关等。 ( 4 ) 空间要素作为属性要素的乘积因子，如交通中的等到达时线、水文中的等 流时线等。( 5 ) 将不同要素的图层进行空间配准后采用g i s 中的叠加( o v e r l a y ) 方法，形成规则网格或最小图斑单元，然后参与一般分析，不再考虑空间要素。 2 兰州大学研究生学位论文 空间数据发掘和知识发现的研究比一般关系数据痒和事务数据库的研究要 晚，但近几年引起了广泛的兴趣。加拿大s i m o nf r a s e r 大学计算机科学系的h a n j i a w e i 教授领导的小组，在m a p i n f o 平台上建立了空间数据挖掘的原型系统， 实现了空间数据特征描述、空间比较、空间关联、空间聚类和空间分类等空间 数据挖掘方法。1 9 9 6 年e s t e r 的d a s c a n 利用空问数据结构r * - t r e e 进行基于 密度的空间聚类。s t o l o r z 的q u a k e f i n d e r 采用统计、超级并行、全局优先等从 空间发现有关地震的知识( 史忠植，2 0 0 2 ) 。测绘遥感界的学者们在特征提取、 模式识别等的研究中实际已经做了许多空间数据挖掘的工作( 李勃等，2 0 0 2 ) ， 但把相关工作提到数据挖掘和知识发现的高度并系统地加以研究的还欠缺乏。 与国外相比，国内对空间知识发现技术的研究稍晚，还没有形成整体力量。 在空间数据领域，武汉大学李德仁教授提出从g i s 数据库可以发现包括几何信 息、空间关系、几倪性质与属性关系以及面向对象知识等的多种知识。中科院 地理所资源与环境信息系统国家重点实验室、中科院遥感所等单位的学者在近 几年也展开了空间数据挖掘研究，中国图像图形学学报1 9 9 9 年1 1 月首次刊出 了数据发掘专辑，主要是针对空间数据。 对于知识和推理不确定性的研究，李德毅教授在传统模糊集理论和概率统 计的基础上提出了定性定量不确定性转换模型云模型。把定性概念的模糊 性和随机性完全集成到一起，构成定性和定量相互间的映射，作为知识表达的 基础( 李德毅等，1 9 9 5 ) ，解决了模糊集理论用精确的隶属函数描述模糊性的缺 点。提出用不确定点、不确定线、不确定面、不确定方向、不确定距离等的云 模型，来表达空间概念的不确定性，以及定性概念与定量数值间的转换，为空 间对象模糊性的表达开辟了新路。 在空间数据库知识发现( 数据挖掘) 领域的众多有影响研究活动( f a y y a d e t a 1 1 9 9 5 ；p i a t e t s k y s h a p i r oe ta 1 ，1 9 9 1 ) ，导致了系列感兴趣技术的发展，为高 可信空间数据挖掘技术探索提供了一些有趣的方法。 1 1 3 空间关联规则 关联规则挖掘的研究是近几年研究较多的数据挖掘方法，在数据挖掘的各 种方法中应用得也撮为广泛。在数据挖掘的知识模式中，关联规则模式是比较 重要的一种。关联规则的概念由a g r a w a l 、i m i e l i n s k i 和s w a m i 提出( a g r a w a l e t 第1 章绪论 a 1 ，1 9 9 3 ) ，是数据中一种简单但很实用的规则。 关联规则发现的主要对象是事务数据库，其起初应用在售货数据中，也称 为货篮数据( b a s k e td a t a ) 。空间数据库关联规则的发现沿用了一般数据库的挖 掘技术，著进行了空间扩展。空间关联规则的形式是“w b ”的规则，其中 w 和b 是包含空间谓词的谓词集。在大数据库中可能存在许多的关联关系，但 是一些不经常发生或者不能由多数情况支持。为了，取得频繁发生的强模式，采 用了最小支持度和最小可信度的概念( a g r a w a le ta 1 ，1 9 9 4 ；k o p e r s k i ，e ta 1 ， 1 9 9 8 ) 。可以指定阈值强制发现的规则为强关联规则。 空间关联规则的最大特点就是利用了空间实体间的空间关系，并用空间谓 词表示。例如，描述某地区道路与河流关联的规则 “i s a ( x ，r o a a ) _ c ew ( x ，r i v e r ) ( 8 2 ) ”，可信度是8 2 ，c l o s et o 是一个空 间谓词。虽然这些规则通常不是1 0 0 正确，但它们是有关空间关联的重要知 识，是对空间数据库深入的描述，不是单从数据表面就能察觉到的，实现了空 间属性数据与空间关系信息的融合，在地理学、环境研究、生物学、工程学和 其它领域有着重要的意义( 徐铭杰，2 0 0 2 ) ，可以作为空间决策支持的依据。 在a r c l n f 0 8 中引入了面向对象的数据模型g e o d a t a b a s e 数据模型，将所 有的地理数据存储到商业关系数据库，并将主流的数据库技术集成到a r c l n f o 中，允许在要素之间定义几种类型的关联，将要素和对象关联到一起，存储在 要素集中，或直接存储。利用空间关联规则发掘技术，可以很容易找到要素类 之间丰富的关联关系。使用拓扑关系、空间表达和一般关系，不仅可以定义要 素的特征，还可以定义要素与其它要素的关联情况。当与要素相关的要素被移 动、改变或删除的时候，用户预先定义好的关联要素也会做出相应的变化 ( m i c h a e lz e i l e r ，1 9 9 9 ) 。 在对空间关联知识发掘技术的研究中，多数是一般数据库发掘技术的改进 算法、算法的优化( 程继华等，1 9 9 8 ) ，以及不确定性概念的表达( 周成虎等， 1 9 9 9 ) 和属性概念层次的建立等。空间数据与其它类型数据的最大区别就是它 的空间特性，强调空间对象间关系的表达，也就是要如何有效地处理空间谓词， 是空间关联知识发掘的不可缺少的环节，也是关联规则发掘算法与空间数据无 缝集成的关键，所以有必要建立空间关系层次，执行空间多层次关联规则的发 兰州大学研究生学位论文 掘( 陈江平，2 0 0 3 ：e l i s e oe t a l 、2 0 0 0 ) 。 1 2 文献综述 1 2 1 知识发现产生的背景 2 0 世纪计算机的问世和技术进步极大地促进了各行各业的发展，加快了世 界信息化的进程。计算机信息处理的发展过程经历了三次浪潮( p i a t e t s k y s h a p i r o 19 9 4 ；h a n ，1 9 9 5 ) ：第一次浪潮发生于6 0 7 0 年代，代表技术是数据采集和数 据库产生，这期间产生了大量的在线数据库；第二次浪潮发生于7 0 8 0 年代， 代表技术是数据组织和使用、数据库中的信息检索和事务处理，其标志是关系 数据库管理系统的成熟和广泛应用，从8 0 年代开始，数据库的大量增长远远超 过了人们通过几个查询命令对数据库进行分析的能力，数据库激增与处理和理 解能力不足的矛盾突出出来；第三次浪潮发生于8 0 9 0 年代，代表技术是数据 分布、多样性、共享和数据理解，产生了扩展关系数据库、面向对象数据库、 演绎数据库和异质数据库管理系统，产生了面向应用的数据库系统，如空间数 据库、时态数据库、多媒体数据库、主动数据库、科学数据库、知识库、办公 室信息库、全球信息库( i n t e m e t ) 等等，数据库急剧膨胀与对数据库处理和理 解能力薄弱的矛盾更加尖锐。 现今数据库的大多数应用仍然停留在查询、检索阶段，数据库中隐藏的丰 富的知识远远没有得到充分的发掘和利用，数据库急剧增长与人们对数据库处 理和理解困难之间形成了强烈的反差。“人们被数据淹没，但却饥饿于知识”正 是这一反差的生动写照。李德毅教授称这一现象为“信息灾难”，并总结为四大 问题“一是信息过量，难以消化；二是信息真假，难以辨识；三是信息安全， 难以保证；四是信息形式不一致，难以统一处理”( 邸凯昌，2 0 0 0 ) 。 面对这一困境，人们迫切需要新的技术，能够高效、自动、智能地处理数 据，从中挖掘出用于决策的规律性的东西。数据库知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e s ，k d d ) 技术，就是在数据和数据库急剧膨胀的背景下应 运而生的，也是数据库技术、人工智能技术、统计技术、可视化技术等发展融 合的结果。由于其诱人的前景和巨大的难度，使得k d d 成为计算机信启强理 领域的研究热点和前沿技术。 第1 章绪论 1 2 2 知识发现技术的研究 数据库知识发现术语于1 9 8 9 年出现，f a y y a d 定义为“k d d 是从数据集中 识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程” ( f a y y a d ，1 9 9 5 ) 。 知识发现是从数据集中抽取和精化新的模式。知识发现的范围非常广泛， 可以是经济、工业、农业、军事、社会、商业、科学的数据或卫星观测得到的 数据。数据的形态有数字、符号、图形、图像、声音等。数据组织方式也各不 相同，可以是有结构、半结构或非结构的。知识发现的结果可以表示成各种形 式，包括规则、法则、科学规律、方程或概念网等( 史忠植，2 0 0 2 ) 。 由于知识发现是一门受到来自各种不同领域的研究者关注的交叉性学科， 因此导致了很多不同的术语名称。除了k d d 外，主要还有如下若干种称法：“数 据挖掘”( d a t am i n i n g ) 、“知识抽取”( i n f o r m a t i o ne x t r a c t i o n ) 、“信息发现” ( i n f o r m m i o nd i s c o v e r y ) 、“智能数据分析”( i n t e l l i g e n td a t aa n a l y s i s ) 、“探索式 数据分析”( e x p l o r a t o r y d a t aa n a l y s i s ) 、“信息收获”( i n f o r m a t i o nh a r v e s t i n g ) 和 “数据考古”( d a t aa r c h e o l o g y ) 等等。其中，最常用的术语是“知识发现”和 “数据挖掘”。相对来讲，数据挖掘主要流行于统计界( 最早出现于统计文献中) 、 数据分析、数据库和管理信息系统界；而知识发现则主要流行于人工智能和枫 器学习界( 史忠植，2 0 0 2 ) 。现在，人们倾向于将两者一起使用，称为数据发掘 和知识发现( d a t a m i n i n g a n d k n o w l e d g e d i s c o v e r y ，d m k d ) 。 迄今为止，对关系数据库和事务数据库中数据发掘和知识发现的研究已经 取得了不少进展，代表性的工作有：用面向属性的归纳方法在关系数据库中发 现特征规则和区分规则( c a ie t a l ，1 9 9 1 ；h a r te ta j ，】9 9 2 ) ；在事务数据库中发现 关联规则( a g r a w a l e ta 1 ，1 9 9 4 ) ：基于距离的和基于密度的聚类分析的优化( n g e ta 1 ，1 9 9 4 ；e a s t e re ta 1 ，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 ) 。另外， 决策树、神经网络、遗传算法、可视化等方法也在机器学习和知识发现中得到 了研究与应用。在k d d 领域，最有影响的发现算法有加拿大s i m o nf r a s e r 大学 j h a n 教授的概念树提升算法( h a n e ta 1 ，1 9 9 2 ) 、m m 的r a g r a w a l 的关联算 法a 研o r i ( a g r a w a le 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 g e ta 1 ，1 9 9 6 ，1 9 9 7 ) 、 密西根州立大学e r i c kg o o d m a n 的遗传算法等。 由于是在强烈的应用需求背景下产生的，k d d 技术从一开始就是面向应用 的。例如加拿大b c 省电话公司要求加拿大s i m o nf r a s e r 大学k d d 研究组根据 其拥有的十多年的客户数据，总结、分析并提出新的电话收费和管理办法，制 定既有利于公司又有利于客户的优惠政策。美国著名的国家篮球队n b a 的教 练，利用i b m 公司提供的数据发掘工具临场决定替换队员。最近，还有不少 k d d 产品用来筛选因特网上的新闻，保护用户不受无聊电子邮件的干扰和商业 推销，很受欢迎( 邸凯昌，2 0 0 0 ) 。 国际上许多著名的数据库和数据仓库供应商、统计分析软件开发商以及专 门的k d d 开发商、相关大学和研究机构等纷纷投入研究和开发力量，相继开 发出一些k d d 商用系统和原型系统，这些软件被收集罗列在国际著名的k d d 网址h t t p ：、】l n v 、k d 玎u g g e t s c o m 中，g o e b e l 和g r u e n w a l d ( g o e b e l e ta 1 ，1 9 9 9 ) 对4 3 个k d d 工具软件进行了评述和对比。值得一提的是，在第四届国际k d d 大会( k d d 9 8 ，1 9 9 8 ) 上开展了k d d 工具的竞赛活动，近2 0 个软件参加了竞 赛，k d d 9 9 和k d d 2 0 0 0 大会上延续了软件竞赛活动，这一活动无疑会进步 促进k d d 软件的开发。目前，最有影响的k d d 系统有：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 em 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 s b a s e 的w a r e h o u s e s t u d i o 、s t a n f o r ds 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 、e x p l o r a 、 k n o w l e d g ed i s c o v e r y w o r k b e n c h 、d b m i n e r 、q u e s t 等。 1 2 3 关联规则挖掘算法的研究 发掘关联规则的闯题首先由a g r a w a l 等提出( a g r a w a l e t a l ，1 9 9 3 ) ，主要是 从超级市场销售事务数据库中发现顾客购买多种商品时的搭配规律，即关联规 则。最著名的关联规则发掘算法a p f i o d 也是由a g r a w a l 等提出的。a p r i o r i 算法 的思想十分简单明了，就是要统计多种商品在一次购买中共同出现( 称为项目 集) 的频数，然后将出现频数多( 称为大项目集) 的搭配转换为关联规则，算 法的核心是用前一次扫描数据库的结果产生本次扫描的候选项目集，从而提高 搜索的效率。p a r k 等提出的d h p 算法应用“h a s h ”技术进一步减少候选项目集 第1 章绪论 的数量，从而进一步提高了速度( p a r ke ta 1 ，1 9 9 5 ) 。 s r i k a n t 和a g r a w a l 引入了从既包含定量又包含范畴数据的大型关系表中发 掘定量关联规则的问题( s r i k a n te ta 1 ，1 9 9 6 ) 。而从事务数据库中发掘出的关联 规则看作是布尔关联规则，因为事务中仪包含二值属性( 项目) 。他们把关系表 中的每一个属性表达为属性值一样多个字段，从而把定量关联规则问题映射为 布尔关联规则问题。如果定量属性的定义域很大，则首先把属性值划分到不同 的区间中，然后把每一个属性区间对映射为布尔属性。经过映射，任何一 种发掘布尔关联规则的算法可用于发现定量关联规则。 c h e u n g 等首先研究了关联规则的维护问题，或称增量式关联规则发掘，提 出了f u p 算法，用于当新的事务增加到数据库中时更新关联规则。它把前一次 发掘过程得到的大项目集的计数存储下来，用于减少本次发掘过程产生候选大 项目集的数目( c h e u n g e ta 1 ，1 9 9 6 ) 。f u p 2 算法是f u p 的推广，当从数据库中 增加或删除事务时它能更新已有的关联规则( c h e u n g e ta 1 ，1 9 9 7 ) 。 上述算法都是在一个概念层次上发掘关联规则。h a r t 和f u 在1 9 9 5 年研究 了发掘多层次关联规则的问题。它对现有的单层次关联规则发掘算法进行了扩 展，并研究了多个概念层次间共享数据结构和中间结果的技巧。类似的i 作在 ( s r i k a n te ta 1 ，1 9 9 5 ) 中也有报道，a p r i o r i 算法经过扩展可以在分类层次结构 的任一层上发现关联规则。关联规则并行发掘算法( p a r ke ta 1 ，1 9 9 5 ) 、元规则 引导的多维关联规则的发掘( k a m b e r e ta 1 ，1 9 9 7 ) 等，也出现了很多报道。 空间关联规则发掘( k o p e r s k i e ta 1 ，1 9 9 5 ) 是从空间数据库中发掘知识的一 项藿要技术，国内在这一领域的研究颇多，如在多层次空间挖掘方面，陈江平 等( 2 0 0 4 ) 给出了一种基于元模式的多层次空间关联规则挖掘算法a l pm l s a m ， 通过预先确定用户感兴趣的规则模式与对象，在对象的各数据层次上进行大项 集的汁数，得到与用户给定的元模式形式一致的空间关联规则。空间关联知识 与一般关联知识最大的不同就是前者要对空闻对象间的空间关系进行描述，由 于空间几何特征数量庞大，其基本类型分为点、线、面等，空间关系的计算对 算法的效率有很大的影响，在这一方面，刘大有等( 2 0 0 4 ) 采用近似区域空间 关系模型，优化空间关系计算过程；陈江平等( 2 0 0 3 ) 直接使用空间分析方法 进行空间关系的概化，得到感兴趣的空间关联规则。在挖掘算法效率改进方面， 兰州大学研究生学位论文 毛国君等提出一种称为i s s d m 的最大频繁项目序列集生成算法，通过对事务 数据库的一次扫描丽逐步演化成最大频繁项目序列集，减少数据库的扫描次数 进而减少挖掘过程的u o 代价( 毛国君，2 0 0 2 ) ；程继华等( 1 9 9 8 ) 采用减少存 储空间占用的多层次关联规则挖掘算法m i 。a r ，计算简化频繁模式集合，然 后生成频繁模式集合，来提高挖掘速度。 本文拟以自然植被与地形、地貌、土壤、水域( 河流、运河、湖泊) 、沼泽 分布的空间关系为研究对象，挖掘强空间关联规则。在实际发掘过程中，考虑 到感兴趣的可能只是某类植被的空间分布特征( 如针叶林) ，所以挖掘算法中不 使用整个植被类，而是专门提取了针叶林对象，这样既减少了计算量，又不会 影响挖掘结果。对连续属性值，如湖泊多边形的面积、河流流域的总长度，将 讨论用云模型计算离教化语言值的方法。对土壤、水域、沼泽建立概念层次树， 以便从空间数据库中挖掘多层次关联规则。并运用一种自上而下的，渐进式深 入搜寻技术( k o p e r s k i e ta 1 ，1 9 9 8 ) ，此项技术首先计算空间对象间的粗略空间 关系，例如，一般靠近( g _ c l o s e _ t o ) ，然后在已建立的属性概念层次的顶层上， 使用关联规则发掘算法，挖掘具有强隐含关系( 也就是，频繁发生) 的大模式。 然后，对这些大模式，在低属性概念层( 也就是，属性概念子层) 上深入搜索， 直到不能发现大模式为止。这时，不能满足大模式要求的空间对象已经被过滤 掉，对需要详查的候选空间谓词，进行细化空间计算，如t o u c h 、c o n t a i n 、w i t h i n 等，可以很大程度地减少空间关系的计算量，提商算法的效率。 1 3 数据组织 1 3 1 硬件环境 i n t e l p e n t i u m e l 计算机，p r o c e s s o r 9 9 6 m h z ，1 2 8 m b 内存，1 2 0 g b 硬盘。 1 3 2 软件环境 用到的软件系统主要有： 1 ) 软件平台：m i c r o s o f tw i n d o w s s e r v e r2 0 0 3s t a n d a r de d i t i o n 2 ) 开发平台：v c + + 6 0 3 ) 专业软件：a r c g i s 9 0 ，a r c s d e 9 0f o rs q l s e r v e r ，a r c s d e 8 3c a p i 4 ) 数据库：s q l s e r v e r 2 0 0 0 9 第1 章绪论 1 3 3 数据组织 i。d。a。t。a。b。a。s；。e。：!i!j：f：!：ii!：回 i d a t a 厂l 厂- a c c e s s 卜z lkg t 器编。l 【、_ j i、。一 i i i ! j ： 卑g e 。m e t r y j 曲 堕i 由 图