（计算机软件与理论专业论文）基于启发式遗传算法的属性约简方法研究.pdf

堕笙鎏三堡盔堂堡主堂焦堡塞 摘要 随着空间数据获取手段的快速发展，从大量的空间数据中自动、快速、 有效地发现知识显得越来越重要。本文简要地介绍了空间数据挖掘的概念、 特点、发现的知识类型，空间数据挖掘的体系结构及基本过程，以及应用于 空间数据挖掘的理论方法等，重点对其数据预处理阶段的决策表属性约简方 法作了研究。 针对粗糙集理论、遗传算法以及决策表属性约简的特点，通过分析基于 传统遗传算法的决策表属性约简算法，吸收原算法的优点，并对其加以改进， 提出了一种基于启发式遗传算法的决策表属性约简算法( h g a a r 算法) 。该 算法对原算法的改进主要有两点：其一，对传统遗传算法中随机产生的二进 制初始种群加以改进，用决策表属性核加以限制，以增强遗传算法的局部搜 索能力，缩短算法的计算时间，并提高决策表属性约简结果的准确性；其二， 在传统遗传算法的遗传算子( 包括选择算子、交叉算子、变异算子) 的基础 上，新算法增加了修正校验算子，以信息熵定义的属性重要性作为启发式信 息，保证遗传算法的全局搜索在有效的可行解空间进行，防止丢弃能够对发 现知识产生重要影响的属性，为整个空间数据挖掘提供有效的约简属性。最 后，通过实验证明了改进后的h g a a r 算法要比基于传统遗传算法的属性约 简算法优越，可以更高效准确地进行决策表属性约简任务。 关键词：空间数据挖掘；启发式遗传算法；属性约简；属性核；属性重要性 堕堑堡三堡盔堂堡堂焦笙窒 a b s t r a c t w i t ht h ed e v e l o p m e n to f t e c h n o l o g yo fa c q u i r i n gt h es p a t i a ld a t a ，i tb e c o m e s m o r ea n dm o r ei m p o r t a n tt of i n dk n o w l e d g ef r o mal a r g en u m b e ro fs p a t i a ld a t a a u t o m a t i c a l l y , q u i c k l y , a n de f f i c i e n t l y t h ec o n c e p t ，c h a r a c t e r i s t i c so fs p a t i a ld a t a m i n i n ga n dt h ek n o w l e d g et y p e sw h i c hc a nb ef o u n db ys p a t i a ld a t am i n i n ga r e i n t r o d u c e db yt h i sp a p e r a n dt h es y s t e ms t r u c t u r ea n db a s i cc o u r s eo fs p a t i a ld a t a m i n i n ga r es h o w n t h e n ，t h em e t h o do ft h ea t t r i b u t er e d u c t i o ni nt h ed e c i s i o n t a b l ew h i c hi sap a r to ft h ed a t ap r e t r e a t m e n ti ns p a t i a ld a t am i n i n gi sd i s c u s s e da s e m p h a s i s a c c o r d i n gt ot h ec h a r a c t e r i s t i co f r o u g hs e tt h e o r y , g e n e t i ca l g o r i t h ma sw e l l a sd e c i s i o nt a b l ea t t r i b u t er e d u c t i o n ，t h r o u g ha n a l y s i so ft h ep r i m a r ya l g o r i t h mo f a t t r i b u t er e d u c t i o nw h i c hb a s e do nt h et r a d i t i o n a lg e n e t i ca l g o r i t h mi nr o u g hs e t ，a n e wa l g o r i t h mo fa t t r i b u t er e d u c t i o nw h i c hi sb a s e do nh e u r i s t i cg e n e t i ca l g o r i t h m i nr o u g hs e tf h g a a ra l g o r i t h m ) i sp u tf o r w a r di nt h i s p a p e r t h e r ea r et w o i m p o r t a n tp a r t sw h i c ha r ei m p r o v e di nt h ea l g o r i t h m t h ef i r s to n ei st h a tt h en e w a l g o r i t h mu s e sa t t r i b u t ec o r ei nd e c i s i o nt a b l ea sar e s t r i c t i o nt oi m p r o v et h e b i n a r yc o d ei n i t i a lp o p u l a t i o nw h i c hi sp r o d u c e ds t o c h a s t i c a l l yi nt h et r a d i t i o n a l g e n e t i ca l g o r i t h m t h i si m p r o v e m e n tc a ns t r e n g t h e nt h el o c a ls e a r c ha b i l i t yo f g e n e t i ca l g o r i t h m ，s h o r t e nt h ec a l c u l a t i o nt i m eo ft h ea l g o r i t h m ，a n dr a i s et h e a c c u r a c yo ft h er e s u l t so ft h ea t t r i b u t er e d u c t i o ni nd e c i s i o nt a b l e s t h eo t h e ro n e b a s e dw i t ht h eg e n e t i co p e r a t o r s ( w h i c hi n c l u d e ss e l e c t i o no p e r a t o r ，c r o s s o v e r o p e r a t o ra n dm u t a t i o no p e r a t o r ) ，t h en e wa l g o r i t h mi n c r e a s e sac o r r e c t i o no p e r a t o r i nt h i so p e r a t o r , t h ea l g o r i t h mu s e sa t t r i b u t es i g n i f i c a n c ea sh e u r i s t i ci n f o r m a t i o n w h i c hc a ng u i d et h ea l g o r i t h mc a r r y i n go u ti nt h es p a c eo ff e a s i b l er e s u l t s ，a n dt h e a t t r i b u t ew h i c hc a nm a k em o r ei m p o r t a n ti n f l u e n c ei sp r e v e n t e dt ob el o s t a n d ， m o r ee f f i c i e n ta t t r i b u t e sc a nb ep r o v i d e df o rt h es p a t i a ld a t am i n i n g f i n a l l y , a n e x p e r i m e n ti ss h o w nt op r o v et h a tt h eh g a a ra l g o r i t h mi sm o r ee x c e l l e n c et h a n 哈尔滨1 = 程大学硕士学位论文 t h ea t t r i b u t er e d u c t i o na l g o r i t h mb a s e dt r a d i t i o ng e n e t i ca l g o r i t h m ，a n di ti sm o r e a c c u r a t ea n de f f i c i e n tt os o l v et h ep r o b l e mo f a t t r i b u t er e d u c t i o ni nd e c i s i o nt a b l e k e 州o r d s ：s p a t i a ld a t am i n i n g ，h e u r i s t i cg e n e t i ca l g o r i t h m ，a t t r i b u t er e d u c t i o n ， a t t r i b u t ec o r e ，a t t r i b u t es i g n i f i c a n c e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的 指导下，由作者本人独立完成的。有关观点、方法、 数据和文献的引用己在文中指出，并与参考文献相对 应。除文中已注明引用的内容外，本论文不包含任何 其他个人或集体已经公开发表的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本人完全意识到本声明的法律结果由本人 承担。 作者( 签字) ：墨之! 纥 日期：了舢萨f _ 月功日 堕! ! 鎏王焦盔堂堡主堂焦堡塞 1 1 概述 第1 章绪论 近年来，随着数据库技术的成熟和数据应用的普及，数据库的数量、单 个数据库的容量和数据类型的复杂性都大大地增加了。例如，空间物体数据 库包括几十亿个望远镜图像，n a s a 地球观测系统每小时都会产生5 0 g b 的 数据。毫无疑问，在这些庞大的数据库中蕴藏着极其丰富的信息源，而在各 种空间数据呈指数级数增长的时候，出现了所谓的“数据丰富，知识贫乏” 的现象r n 。因此，传统数据挖掘面临着一个重要的课题就是针对复杂类型数 据的挖掘。正是基于这个原因，作为数据挖掘的一个新的分支，空间数据挖 掘应运而生。空间数据挖掘不仅在地理信息系统、地理市场、遥感、图像数 据勘测、医学图像处理、导航、交通控制、环境研究等领域有着广泛的应用， 还可以用于对空间数据的理解、空间关系和空间与非空间数据关系的发现、 空间知识库的构造、空间数据库的重组和空间查询的优化。空间数据挖掘实 质上是空间信息技术发展的必然结果，是一个极具挑战性极具前景的研究领 域【2 】。 作为空间数据挖掘的数据预处理阶段，连续属性的离散化、属性的约简 等操作都对最终的数据挖掘和知识发现产生重要的影响。正是由于空间数据 的数据量大、记录繁杂，才使得重要的有价值的“知识”隐藏其中，难以被 发现。因此，如果能通过一种方法将数据源中的大量数据进行约简，忽略其 中不重要的、重复的、不准确的冗余属性，只保留其中能够说明问题的、简 洁的、重要的属性，就可以“拨开迷雾”，使“知识”相对明晰，易于被挖 掘被发现m 。这正是人们所期待的、具有深远意义的事情。 1 2 国内外研究现状 目前国内外都开展了空间数据挖掘与知识发现方面的研究。加拿大 s i m o nf r a s t e r 大学计算机科学系的h a r tj i a w e i 教授领导的小组，较早对此进 哈尔滨工程大学硕士学位论文 行系统全面的研究，并在m a p l n f o 平台上建立了空间数据挖掘的原型系统 g e o m i n e r ，实现了空间数据特征描述、空间比较、空间关联、空间聚类和空 间分类等空间数据挖掘方法1 4 1 。美国的空间信息处理项目e o s ( e a r t ho v e r v i e w s y s t e m ) 的主要组成部分之一就是空间数据的联机分析与挖掘技术的研究，该 项目对巩固美国在全球的竞争优势具有重要的作用【5 】。此外，德国的慕尼黑 大学、芬兰的赫尔辛基大学以及美国、澳大利亚等国家的许多所大学和研究 所，都有空问数据挖掘的成果报道【q 。这些研究者大多将空间数据挖掘作为 数据挖掘的一个应用领域，把研究的重点放在提高原有数据挖掘算法在空间 数据库中的执行效率。 在国内，武汉大学李德仁教授较早关注到从g i s 数据库中发现知识的问 题，提出从g i s 数据库可以发现包括几何信息、空间关系、几何性质与属性 关系以及面向对象知识等多种知识，并对此作出了大量研究。另外，中科 院地理所资源与环境信息系统国家重点实验室、中科院遥感所、中科院软件 所、中国测绘科学研究所等也相继开展了空间数据挖掘的研究工作。中科院 已经开始创新项目“空间数据挖掘及知识发现”课题的研究，视觉与听觉信 息处理国家重点实验室的基金项目“空间数据联机分析与空间数据挖掘研究” 重点对空间数据联机分析与空间数据挖掘底层的空间数据仓库技术作基础理 论研究。 但是，空间数据挖掘毕竟是年轻的领域，它的发展还是不成熟的，也是 不完善的。对它的研究还只是处于初期，仍然有许多问题值得进一步的研究 和探讨i 。例如： ( 1 ) 算法的效率 空间数据挖掘较之传统数据挖掘具有更为海量的数据库系统，因此在空 间数据挖掘过程中出现不确定性、错误模式的可能性也就更大了。由此，提 高算法的效率成为空间挖掘算法在实际应用中不可避免的巨大挑战。 ( 2 ) 数据挖掘方法和任务的多样性 现有的空间挖掘方法与任务都是有限的。例如在对大量遥感图像进行处 理时，就需要更为多样的挖掘方法来发现不同现象间的关系，找出相似图形 等等。而除了现有的空间聚类、空间分类和空间关联规则挖掘任务等，还应 对类似于空间例外这样的任务进行挖掘【8 1 。 2 堕玺堡三塑盔堂堡主堂垡堡塞 ( 3 ) 对复杂的空间数据库的处理 数据库技术不断发展完善，像面向对象空间数据库和时空数据库这样复 杂的空间数据库也在不断地涌现和发展。所以，将空间挖掘技术应用到这些 数据库中是至关重要的 9 1 。 ( 4 ) 网络环境下的空间数据挖掘 跨入新的世纪，网络的发展更加迅速，网络的资源也日益丰富。因此， 研究适应于网络环境下的空间数据挖掘技术、工具和系统是大势所趋。 ( 5 ) 空间查询语言 数据库技术的飞速发展的原因之一就是数据库查询语言的不断完善和发 展，由此，要不断完善和发展空间数据挖掘就必须发展空间查询语言1 1 0 。这 样才能为高效快速的空间数据挖掘奠定坚实的基础。 总之，许多空间数据挖掘系统还很不成熟，难以商业化。空间数据挖掘 目前基本上处于开始阶段，需要建立和完善空间数据挖掘的基础理论和技术 框架，开发有效的算法，提高已有算法的效率，并开展典型的应用 1 q 0 2 。 目前，也有很多学者和研究人员致力于研究整个空间数据挖掘庞大的复 杂的过程中的中间环节，也是较为关键的环节数据预处理的方法，对于 其中的决策表属性约简的研究更是十分热衷1 13 1 。例如，将粗糙集理论、概率 论、模糊集理论、信息系统条件熵、神经网络、云理论、遗传算法、其它的 组合优化算法等应用到该领域，也有将其中的两种、甚至多种理论方法相结 合形成新的方法运用，都取得了一定的效果【1 4 】m 】。但是，同样存在算法的有 效性及算法的效率不令人满意的问题。 1 3 本文的主要工作 本文的主要目的是通过研究空间数据挖掘的理论和方法，空间数据挖掘 的基本理论和技术框架，针对空间数据的特点，研究空间数据挖掘过程中数 据预处理阶段的属性约简问题。重点研究将粗糙集理论以及引入启发式信息 的遗传算法应用到决策表的属性约简问题，改进传统的约简算法，结合启发 式和信息论的知识，提出基于启发式遗传算法的属性约简算法，提高对决策 表属性约简的效率。本文的主要研究内容及论文的组织如下： 第1 章概要介绍空间数据挖掘的产生背景，指出空间数据挖掘的研究具 有十分重要的研究意义，具有广阔的研究前景，介绍了空间数据挖掘的国内 外研究现状以及目前研究的热点问题。 第2 章提出空间数据挖掘的基础理论和技术框架，对其涉及的问题与方 法进行系统的阐述和研究，为全文提供理论基础与方法指导。其中介绍的空 间数据挖掘的理论基础包括：空间数据挖掘的定义、体系结构，空间数据挖 掘的基本过程，从空间数据库中所能发现的知识类型，空间数据挖掘方法、 知识的表达方法等。 第3 章将粗糙集理论及遗传算法引入空间数据挖掘领域，研究粗糙集理 论用于空间数据挖掘的基础理论和方法，包括空间数据库中知识表达系统的 分类、属性表的一致性分析、属性的依赖关系和属性的重要性的概念和理论。 重点探讨粗糙集和遗传算法在决策表属性约简中的应用。 第4 章主要介绍知识表达系统和决策表的基本概念，讨论了粗糙集理论 中提出的知识是一种分类的定义，并且提出等价类在知识表达系统的概念。 为提出算法作准备，介绍了决策表的定义，提出条件属性和决策属性的划分， 概要介绍了决策表的属性约简，属性核以及属性重要性的表示方法。 第5 章是本文的重点和核心部分。首先分析了基于传统的遗传算法的决 策表属性约简算法，并且对其进行了透彻剖析，针对其弊端，提出了本文的 基于启发式遗传算法的属性约简算法，包括算法的基本思想、算法的描述、 算法的流程、算法的具体实现技术等，并用实验证明的新的约简算法的高效 性。 堕笙堡工焦盔堂堡主堂垡丝窒 第2 章空间数据挖掘的基本理论 空间数据挖掘( s p a c i a ld a t am i n i n g ，简称s d m ) ，是数据挖掘( d a t a m i n i n g ，简称d m ) 的分支学科，但s d m 不同于一般的d m ，有别于常规的 事务型数据库的数据挖掘。 2 1 数据挖掘和知识发现 数据挖掘和知识发现( d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ，简称 d m k d ) 就是挖掘出大量数据背后隐藏的规则和模式，从而预测未来的发展 趋势。数据挖掘是数据库技术、机器学习、人工智能、统计分析、模糊逻辑、 人工神经网络和专家系统等基础上发展起来的新兴交叉学科，是继网络之后 的又一技术研究热点。如果将数据库中的大量数据比喻为矿床，则d m k d 技 术就是从矿床中挖掘知识“金块”的工具 1 1 1 。诱人的前景和巨大的难度使得 d m k d 成为计算机信息处理领域的研究热点和前沿技术】。 2 2 空间数据挖掘的概念和特点 2 2 1 空间数据挖掘的概念 空间数据挖掘是在空间数据库的基础上，综合利用统计学方法、模式识别 技术、人工智能方法、神经网络技术、粗糙集、模糊数学、机器学习、专家 系统和相关信息技术等，从大量的空间生产数据、管理数据、经营数据或遥感 数据中析取人们可信的、新颖的、感兴趣的、隐藏的、事先未知的、潜在有 用的和最终可理解的知识，从而揭示出蕴含在数据背后的客观世界的本质规 律、内在联系和发展趋势，实现知识的自动获取，提供技术决策与经营决策的依 据2 】。 可见，空间数据挖掘是利用数据挖掘方法，按照一定的度量值和临界值从 空间数据库中抽取知识以及与之相关的预处理、抽样和数据变换的一个多步 骤相互链接、反复进行的人机交互过程。 哈尔滨工程大学硕士学位论文 2 2 2 空间数据挖掘的特点 空间数据挖掘与传统数据挖掘的不同表现在以下几个方面： ( 1 ) 传统数据挖掘处理的是数字和类别，而空间数据则是一些更为复杂 的数据类型，例如：点、线、多边形等对象。 ( 2 ) 传统数据挖掘通常具有显式的输入，而空间数据挖掘的输入常常是 隐式的。 ( 3 ) 在传统数据挖掘中，有一个至关重要的前提假设：数据样品是独立 生成的。而这一假设在空间数据挖掘中是不成立的。事实上，空间数据之间 是高度关联的，例如：具有相似特征、职业、背景的人通常容易聚集在同一 个地区。这一特性被称之为空间自相关性。 2 3 空间数据挖掘发现的知识类型 空间数据挖掘发现的知识主要包括空间的关联、特征、分类和聚类等规 则，一般表现为一组概念、规则、法则、模式、方法和约束等的集合。例如， 在g i s 数据库等空间数据库中发现的主要知识类型有以下几种： ( 1 ) 空间关联规则 空间关联规则指空间对象间相邻、相连、共生、包含等关联关系m 】。例 如：村落与道路相连，道路与河流的交叉处是桥梁等。空间关系除了空间对 象间相邻、相连、包含等拓扑空间关系，还包括顺序空间关系或方位关系； 度量空间关系，如对象间的距离等0 s l 1 9 1 。 ( 2 ) 空间聚类规则 空间聚类规则是指特征相近的空间对象聚类的规则。例如，将距离很 近的居民点聚类为居民区。 ( 3 ) 空间特征规则 空间特征规则指的是一类或几类空间对象的普遍特征，是对共性的描述， 如空间对象的大小、数量和形态等【2 1 】。 ( 4 ) 空问区分规则 空间区分规则是指多类空间对象间的不同特征，即可以用来区别对象。 空间分布规则是主要的空间区分规则。空间分布规则指空间对象在空间的垂 6 哈尔滨工程大学硕士学位论文 直、水平或垂直水平分布规律。 ( 5 ) 空间演变规则 空间演变规则是指空间对象依时间的变化规则。当空间数据库是时空数 据库或存有同一地区不同时间的历史数据时，将可以挖掘具有时间约束的空 间序列规则。空间序列规则可以根据数据随时间的变化趋势预测将来的值。 2 4 空间数据挖掘的体系结构 空间数据挖掘系统大致可以分为三层结构【2 1 【z 1 1 ，如图2 1 所示。 图2 1 空间数据挖掘的体系结构 第1 层是数据源，指利用空间数据库或数据仓库管理系统提供的索引、 查询优化等功能获取和提炼与问题领域相关的数据，或直接利用存储在空间 数据立方体中的数据，这些数据可称为数据挖掘的数据源或信息库。 第2 层是挖掘器，利用空间数据挖掘系统中的各数据挖掘方法分析被提 取的数据，一般采用交互方式，由用户根据问题的类型以及数据的类型和规 模，选用合适的数据挖掘方法，但对于某些特定的专门数据挖掘系统，可采 7 堕玺堡工堡盔堂堡堂垡堡塞 用系统自动地选用挖掘方法的方式。 第3 层是用户界面，使用多种方式( 如可视化工具) 将获取的信息和发 现的知识以便于用户理解的方式反映给用户，用户对发现的知识进行分析和 评价，并将知识提供给空间决策支持使用，或将有用的知识存入领域知识库 内。 在整个空间数据挖掘过程中，用户能够控制每一步。一般说来，空间数 据挖掘的每个步骤相互连接，需要反复进行人机交互，才能得到最终满意的 结果。显然，良好的人机交互用户界面是顺利进行空间数据挖掘并取得满意 效果的基础。 2 5 空间数据挖掘的基本过程 空间数据挖掘的过程与大多数数据挖掘和知识发现的过程相同，一般可 分为：数据选取、数据预处理、数据转换、数据挖掘、模式解释和知识评估 等阶段( f a y y a d ，1 9 9 6 ) ，如图2 2 所示。 图2 2 空间数据挖掘的基本过程 数据选取：根据用户的要求从空间数据库中选择出与空间数据挖掘相关 的数据，s d m 主要从这些数据中进行知识提取。 数据预处理：主要对选取出的数据进行再加工，检查数据的完整性和一 哈尔滨工程大学硕士学位论文 致性，对其中的噪音数据进行处理，对丢失的数据用统计的方法进行填补。 最重要的是通过某些操作减少数据量。 数据挖掘：首先确定要发现的知识类型，选择合适的数据挖掘算法以及 合适的模型和参数，从数据中提取出用户需要的知识。 模式提取：对提取出的知识进行模式解释，提高其准确性和可理解性， 成为更有效的知识。 必要时还要进行知识评价，将发现的知识以用户可接受的方式呈现给用 户，同时进行对知识一致性的检验，以确信本次发现的知识不与以前发现的 知识相抵触【2 2 】。 2 6 空间数据挖掘的理论和方法 空间数据挖掘并不是一种全新的具体方法，它的许多方法在地理信息系 统、地理空间认知、地图数据处理、地学数据分析领域内早已广泛应用。因 此，可以说空间数据挖掘是多学科和多技术交叉融合的新兴边缘学科，汇集 了人工智能、专家系统、机器学习、数据库和统计学等学科的成果。目前， 应用于空间数据挖掘主要有以下的理论和方法： 1 概率论 概率论( p r o b a b i l i t yt h e o r y ) 根据随机概率挖掘含有不确定性的空间数据 库，发现的知识被表示成给定条件下某一假设为真的条件概率，常用作背景 知识。在用误差矩阵描述遥感分类结果的不确定性时，可以用这种背景知识 表示不确定性的置信度m 】。l e m a r c i k 和p i a s t a 把概率论和粗集相结合，利用条 件属性推理决策知识，开发了p r o r o u g h 系统( p r o b a b i l i s t i cr o u g hc l a s s i f i e r s g e n e r a t i o n ) 。利用基于决策树的概率图模型，f r a s c o n i 、g o r i 和s o d a 对带有 图形属性的数据库进行挖掘，得到了用于指导机器学习的知识。区域土壤属 性的空间分析常通过概率样本来实现。对于无概率样本的区域，b r u s 和 g r u i j t e r 设计了利用概率样本内插回归的方法估求其土壤属性的一般模式。 2 证据理论 证据理论( e v i d e n c et h e o r y ) 足概率论的一个扩展( 又称d e m p s t e r - s h a f e r 理论) ，是由可信度函数( 度量已有证据对假设支持的最低程度) 和可能函数 9 哈尔滨工程大学硕十学位论文 ( 衡量根据已有证据不能否定假设的最高程度) 所确定的一个区间。当证据 未支持部分为空时，证据理论等同于传统概率论。证据理论将实体分为确定 部分和不确定部分，可以用于基于不确定性的空间数据挖掘。利用证据理论 的结合规则，可以根据多个带有不确定性的属性进行决策挖掘2 ”。两两比较 法也用于属性不确定性的知识发现。证据理论发展了更一般性的概率论，却不 能解决矛盾证据或微弱假设支持等问题。 3 空间统计学 空间统计学( s p a t i a ls t a t i s t i c s ) 是依靠有序的模型描述无序事件，根据不 确定性和有限信息分析、评价和预测空间数据。它主要运用空间自协方差结 构、变异函数或与其相关的自协变量或局部变量值的相似程度实现基于不确 定性的空间数据挖掘【拍】。基于足够多的样本，在统计空间实体的几何特征量 的最小值、最大值、均值、方差、众数或直方图的基础上，可以得到空间实 体特征的先验概率，进而根据领域知识发现共性的几何知识。空间统计学拥 有较强的理论基础和大量的成熟算法，能够改善g i s 对随机过程的处理数值 型空间数据，分析空间过程，预测前景，并为分析连续域的空间相关性提供 理论依据和量化工具等。所以，空间统计学是基本的数据挖掘技术，特别是 多元统计分析( 如判别分析，主成分分析，因子分析，相关分析，多元回归 分析等) 嘲。 4 规则归纳 规则归纳( r u l e si n d u c t i o n ) 是在一定的知识背景下，对数据进行概括和 综合，在空间数据库或空间数据仓库中搜索和挖掘以往不知道的规则和规律， 得到以概念树形式( 如g i s 的属性概念树和空间关系概念树) 给出的高层次 的模式或特征。背景知识可以由s d m 的用户提供，也可以作为s d m 的任务 之一自动提取田】。在推理方法中，归纳不同于基于公理和演绎规则的演绎， 以及基于公认知识的常识推理，而是根据事例或统计的大量事实和归纳规则 进行的。决策规则是数据库中总的或部分的数据之间的相关性，是归纳方法 的扩充，其条件为归纳的前提，结果为归纳的结论，大致包括关联规则、顺 序规则、相似时间序列、i f - t h e n 规则等。 空间关联规则发现是s d m 的重要内容，目前的研究重要集中在提高算 法的效率和发现多种形式的规则两个方面，并以逻辑语言或类s q l 语言方式 1 n 哈尔滨工程大学硕士学位论文 描述规则，以使s d m 趋于规范化和工程化。一条空间关联规则可表示为x y ( c ，s ，i ) ，其中，x 和y 是空间或非空间谓词的集合，c 、s 和i 分别是规则的可信度、支持度和兴趣度。 5 聚类分析 聚类分析( c l u s t e r i n ga n a l y s i s ) 主要是根据实体的特征对其进行聚类或分 类，按一定的距离或相似测度在大型多维空间数据集中标识出聚类或稠密分 布的区域，将数据分成一系列相互区分的组，以期从中发现数据集的整个空 间分布规律和典型模式。聚类分析是统计学的一个分支，与规则归类不同的 是聚类算法无需背景知识就直接从空间数据库中发现有意义的空间聚类结 构。已有的聚类算法多为模式识别设计，用特征表示的目标为多维特征空间 的一个点，在特征空间中聚类口m 。空l 日j 数据库中的聚类是对目标的图形直接 聚类，聚类形状复杂，数据量庞大，使用经典的基于多元统计分析的聚类法 则速度慢、效率低。这对空间数据挖掘中的聚类算法提出了更高要求，如能 处理点、线、面等任意形状，计算效率高，算法需要的参数能自动确定或用 户易确定。 6 决策树 决策树根据不同的特征，以树型结构表示分类或决策集合，产生规则和 发现规律。在空间数据挖掘中，首先利用训练空间实体集生成测试函数；其 次根据不同取值建立树的分支，在每个分支子集中重复建立下层结点和分支， 最终形成决策树；然后对决策树进行剪枝处理，把决策树转化为据以对新实 体进行分类的规则l 。i d 3 ( i n t e r a c t i v ed i c h o t o m i z e r3 ) 方法根据信息论原理 建立决策树或者决策规则树，它计算数据库中各字段的信息量，寻找数据库 中具有最大信息量的字段，建立决策树的个结点，再根据字段的不同取值 建立树的分支，在每个分支子集中重复建树的下层结点和分支，叶结点为丁f 例或反例。顾及决策树邻近对象的非空间聚合值，基于分类对象的非空间属 性、描述被分类对象和邻近特征的空间关系的属性、谓词和函数。k o p e r s k i 等提出了空间数据的两步决策分类法，在查找样本对象的粗略描述后，利用 机器学习的r e l i e f 算法提取空间谓词，合并空间谓词和非空间谓词为分类决 策知识。m a r s a l a 和b i g o l i n 利用模糊决策树在面向目标的空间数据库中挖掘 区域分类规则。p o s s 系统使用决策树方法对天空图像中的星体对象进行分 1 1 哈尔滨工程大学硕士学位论文 类，并通过分辨率、背景等级或平均强度等属性参数对图像进行规范化，以 提高分类的准确性。 7 模糊集 模糊集( f u z z ys e t s ) 用隶属函数确定的隶属度描述不精确的属性数据， 重在处理不精确的概率。模糊性是客观的存在，系统的复杂性越高，对它的 精确化能力就越低，模糊性越强。在空间数据挖掘中，模糊集可用作模糊评 判、模糊决策、模糊模式识别、模糊聚类分析、合成证据和计算置信度等吲。 模糊集在g i s 中把类型、空间实体分别视为模糊集合、集合元素，空间实体 对备选类别论域的连续隶属度区间为 0 ，1 。每个空间实体与一组元素的隶 属度有关，元素隶属度用于表示实体属于某类型的程度，它越接近于1 ，实 体就越属于该类型。具有类型混合、居间或渐变不确定性的实体可用元素隶 属度描述，如一块含有土壤和植被的土地，可以由两个元素隶属度表示。传 统的集合具有精确定义的界线，为0 、1 二值逻辑。给定一个元素，要么完全 属于集合，要么完全不属于集合。因反映空间非匀质分布的地理属性不确定 性的概率是可变的，类别变量的不确定性主要源t l 定性数据所固有的主观臆 断性、易混淆性和模糊性，故没有明确定义的界线的模糊集合论，较传统集 合论更适于研究非匀质分布和模糊类别。对于遥感图象的计算机分类处理， 模糊类别域的生成可借所使用的分类器不同而输出不同的中间结果，如统计 分类器中有某像素隶属于各备选类别的似然值及神经元网络分类器中的类别 激活水平值。 8 粗糙集 粗糙集( r o u g hs e t s ) 又称粗集，由上近似集和下近似集组成，是一种处理 不精确、不确定和不完备信息的智能数据决策分析工具，较适于基于属性不确 定性的空间数据挖掘m 。粗集从集合论的观点出发，在给定论域中以知识足够 与否作为实体分类的标准，并给出划分类型的精度。上近似集中的实体具有足 够必要的信息和知识，确定属于该类别；论域全集以内且下近似集以外的实体 没有必要的信息和知识，确定不属于该类别；上近似集和下近似集的差集为类 别的不确定边界，其中的实体没有足够必要的信息和知识，无法确切地判断是 否属于该类别，为类别的边界【z 9 1 。若两个实体有完全相同的信息，则它们为等 价关系，不可区分。根据利用统计信息与否，现存的粗集模型及其延伸可以分 1 ， 哈尔滨工程大学硕士学位论文 为代数型和概率型两大类。粗糙集的基本单位为等价类，类似于栅格数据的栅 格、矢量数据的点或影像的像素。等价类划分越细，粗糙集描述实体越精确， 但存储空间和计算时间也越大。基于粗糙集的决策规则推理具有演绎、归纳 和常识等推理的原理，也有其自身的特点。决策规则是演绎推理规则和归纳方 法的扩充，不同点在于决策规则强调优化，而归纳则不必关心它的优化形式。 粗集的决策规则从条件出发作出恰当的或近似的决策，常识推理是从区域专 家共享的知识开始推导出区域中有趣的、公认的知识。粗糙集不排斥不确定 性，力求按照实体的原型来研究实体，为基于不确定性的空间数据挖掘提供了 一个新的理论基础m 】。 本文重要研究的是将粗糙集理论引入到空间数据挖掘中，进行决策表的 属性简化方法的研究。因此，粗糙集理论将在第三章中作详细介绍。 9 云理论 云理论( c l o u d t h e o r y ) 是一个分析不确定信息的新理论，由云模型、不确定 性推理和云变换三部分构成p 】。云理论把定性分析和定量计算结合起来，可以 用于处理g i s 中融随机性和模糊性为一体的属性不确定性。云在空间由系列 云滴组成，远观像云，近视无边。云具有期望值、熵和超熵三个数字特征。期 望值是概念在论域中的中心值，完全隶属于该定性概念：熵是定性概念模糊度 的度量，其值越大，概念所接受的数值范围越大，概念越模糊：超熵反映云滴的 离散程度，其值越大，隶属的随机离散度越大。云理论构成定性和定量相互间 的映射，处理g i s 中容模糊性( 定性概念的亦此亦彼性) 和随机性( 隶属度的随 机性) 为一体的属性不确定性，解决了作为模糊集理论基石的隶属函数的固有 缺陷 3 1 1 。 1 0 神经网络 神经网络( n e u r a ln e t w o r k ) 是由大量神经元通过极其丰富和完善的连接而 构成的自适应非线性动态系统，并具有分布存储、联想记忆、大规模并行处理、 自学习、自组织、自适应等功能。神经网络由输入层、中间层和输出层组成。 大量神经元集体通过训练来学习待分析数据中的模式，形成描述复杂非线性 系统的非线性函数，适于从环境信息复杂、背景知识模糊、推理规则不明确的 非线性空间系统中挖掘分类知识。神经网络对计算机科学、人工智能、认知 科学以及信息技术等都产生了重要而深远的影响，在空间数据挖掘中可用来 】3 堕垒堡! 里盔堂堡主堂垡堕塞 进行分类、聚类、特征挖掘等操作。以m p 和h e b b 学习规则为基础，存在的 神经网络可分为三类：用于预测、模式识别等的前馈式网络，如感知机 ( p e r c e p t r o n ) 、反向传播模型、函数型网络和模糊神经网络等：用于联想记忆 和优化计算的反馈式网络，如h o p f i e l d 的离散模型和连续模型等：用于聚类的 自组织网络，如a r t 模型和k o h o l e n 模型等。l e e 在空间统计学中用模糊神 经网络估计了处理空间分布异常的规则。此外，神经网络与遗传算法结合，也 能优化网络连接强度和网络参数。 1 1 遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ) 是模拟生物进化过程，利用复制( 选择) 、交 叉( 重组) 和变异( 突变) 三个基本算子优化求解的技术。在空间数据挖掘中， 把数据挖掘任务表达为一种搜索问题，利用遗传算法的空间搜索能力，经过若 干代的遗传，就能求得满足适应值的最优解规则。当实施遗传算法时，首先要 对求解的问题进行编码，产生初始群体，然后计算个体的适应度，再进行染色 体的复制、交换、突变等操作，产生新的个体。重复以上操作直至求得最佳个 体。 本文提出将启发式的遗传算法与粗糙集理论相结合，进行决策表的属性 约简的方法，遗传算法将在第四章中详细讨论。 总之，空间数据挖掘利用的技术越多，得出的结果精确性就越高，因此， 多种方法的集成也是空间数据挖掘的一个有前途的发展方向。此外，空间数 据挖掘除了发展和完善自己的理论和方法，还应当充分借鉴和汲取数据挖掘 和知识发现、数据库、机器学习、人工智能、数理统计、可视化、地理信息 系统、遥感、图形图像学、医疗、分子生物学等学科领域的成熟的理论和方 法，开拓研究和发展空间。 2 7 本章小结 本章介绍了空间数据挖掘的基本理论其中包括空间数据挖掘的概念、特 点，阐述了从空间数据库中能够发现的几种知识类型，提出了包括数据源、 挖掘器、用户界面三层结构的空闯数据挖掘体系结构，并指出空间数据挖掘 的数据选取、数据预处理、数据转换、数据挖掘、模式结实和知识评估等基 1 4 哈尔滨t 程大学硕士学位论文 本步骤，系统地研究了多种空间数据挖掘的方法，包括概率论、证据理论、 空间统计学、规则归纳、聚类分析、决策树、模糊集理论、粗糙集理论、云 理论、神经网络及遗传算法等，阐述了各种方法的特点和适用范围。 哈尔滨工程大学硕七学位论文 第3 章粗糙集及遗传算法相关理论 粗糙集理论( r o u g hs e tt h e o r y ，简称r s 理论) 是由波兰学者z d z i s l a w p a w l a k 教授在1 9 8 2 年提出的，它是一种处理含期和不确定问题的新型数学 工具，能有效的分析和处理不确定、不一致等各种不完备信息，并从中发现 隐含的知识，揭示潜在的规律 3 3 1 。利用粗糙集理论处理的问题主要包括数据 库中的数据约简、数据相关性的发现、数据意义的评估、数据中范式的发现 以及因果关系的发现。经过十几年的研究与发展，r s 已经在理论和实际应用 上取得了长足的发展。目前，它已经在医疗诊断、决策分析、信息检索、近 似推理、机器学习、图像处理等领域得到了较为成功的应用，成为数据挖掘 与知识发现的重要工具。粗糙集理论可支持空间数据挖掘与知识发现的多个 步骤，如数据预处理、数据约简、规则生成、数据依赖关系获取等1 ( 3 5 1 。 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是一种模拟生物进化的全局寻 优搜索方法，它具有鲁棒性、隐含并行性和全局搜索等特点，并且容易与其 它技术结合，适用于复杂优化问题的并行处理，已经广泛应用于组合优化等 领域1 3 6 。 本章将粗糙集理论和遗传算法相结合引入空间数据挖掘领域。系统研究 这两种理论方法在空间数据挖掘的属性约简方面的应用。 3 i 粗糙集理论的基本概念 3 。1 1 粗糙集的概念 设u 为非空的论域，x u ，是u 上的等价关系，a = ，r ) 是一个近 似空间，在a 上，如果x 是一些r 的基本类的并集，则称是尺可定义的； 否则称x 是r 是不可定义的。r 可定义集是全集u 上那样一些子集，这些子 集在个体全集u 上恰好可被定义的。r 可定义集被称为胄一致集或r 恰当集， 而r 不可定义集被称为月不一致集或称r o u g h 集。如果存在一个等价关系 r 1 n d ( u ) ，其中1 n d ( u ) 是u 上给定的所有等价关系的交集，使得j u 是r 一致的，则集合j 被称作u 中一致集；如果x u 对任意r 1 n d ( u ) 都 1 6 哈尔滨工程大学硕士学位论文 是r o u g h 的，则x 被称作【，上的不一致集或r o u g h 集。 3 1 2 上、下近似集及边界集 形式地，设x 是u 的子集，x u ，r 是己，上的等价关系，则有： 罡( x ) = u r u r 1 y 工 r 一( x ) = u r u r 】，n 辨 分别称r 一( ) 和r 一( ) 一，r 一( ) 为x 的r 下近似集和的r 上近似集， 其中】，是u 上按等价关系兄作成的等价类。下近似集被解释为所有那些被包 含在x 里面的等价类的并集：上近似集被解释为所有那些与x 有交的等价类 的并集。下近似集和上近似集的差值称为石的边界集： b n d 。( ) = r ( x ) 一r 一( 盖) 它是那些通过等价关系既不能在x 上被分类，也不能在x 的补集并上被 分类的元素的集合。显然，b n d 。( x ) 的元素越多，x 的粗糙度就越大。 3 1 3 正、负域的概念 p o s r ( x ) = r 一( x ) ，称为x 的正域，它是完全属于x 的个体元素的集合。 n e g 。( ) = u r 一( ) ，称为x 的负域，是那些不能任意模糊地用等价 关系胄确定的个体元素的集合，它们不属于墨而是属于x 的补