（计算机应用技术专业论文）基于粗糙集的空间数据挖掘研究.pdf

摘要 现代科技和数据获取设备的迅速发展，空间数据的数量和大小日益丰富， 使得空间数据挖掘和知识发现变得越来越重要。同样为了对林业资源进行信息 自动采集、动态监测管理和辅助决策，用信息化技术改变传统的林业生产管理 模式，这必将产生大量的原始数据。如何充分利用这些数据，进一步为林业管 理辅助决策服务是一个很有意义的问题。 本文首次将粗糙集理论应用于林业信息管理之中。通过对立地因子库和小 班属性数据的属性约简，在不损失原有信息分类的情况下，减少参加处理的数 据量，从而获得较高的数据分析运算速度。另外，将数据预处理技术向空间数 据挖掘进行了扩展，并提出了对空问数据进行预处理的具体方法。通过空间数 据预处理，使得原始空间数据更加准确，更能反映问题的本质，从而使得后续 的数据挖掘算法得到的各种规则更具有价值，更能体现出数据挖掘的力量。 本文通过m a p l n f o 来管理空间数据，利用m a p x 接h ，实现了空间对象间 空间关系，包括拓扑关系和方位关系的自动判别。对空间数据进行特定的处理 后可将空间信息包含在一般的属性数据之中，从而可以利用经典数据挖掘技术 作进一步的分析和处理。这样可以充分借鉴经典数据挖掘的方法和思想来实施 对空间数据进行挖掘，获得较高的效率和满意的结果。 关键词：数据挖掘，空间数据挖掘，粗糙集，地理信息系统，关联规则 a b s t r a c t t ml a r g en u m b e ro fs p a t i a ld a t a ，o w i n gt or a p i dd e v e l o p m e n to fm o d e m s c i e n c ea n dt e c h n o l o g y , a n dd a t ar e t r i e v a ld e v i c e s ，e n a b l es p a t i a ld a t am i n i n ga n d k n o w l e d g ed i s c o v e rb e c o m em o r ei m p o r t a n t i nt h es a m ew a y , f o ri n f o r m a t i o n a u t o c o l l e c t i o n ，d y n a m i cs u p e r v i s em a n a g ea n da s s i s t i n td e c i s i o n m a k i n gt of o r e s t r y r e s o u r c e ，i n f o r m a t i o nt e c h n o l o g yw i l lc h a n g et h et r a d i t i o n a lf o r e s t r ym a n a g em o d e t h i sw i l lc e r t a i n l yp r o d u c ee n o r m o u so r i g i n a ld a t a h o wt ou s es u c hi m p o r t a n td a t a t os e r v ef o r e s t r ya s s i s t a n td e c i s i o n m a k i n gi sas i g n i f i c a n tp r o b l e m t h i sp a p e rf i r s ta p p l yt h er o u g hs e tt h e o r yt of o r e s t r yi n f o r m a t i o nm a n a g e s i t e f a c t o r sd a t ab a s ea n ds u b - c o m p a r t m e n ta t t r i b u t ed a t aa r ep r e t r e a t e dt or e d u c et h e d i m e n s i o n a l i t y , t h i si m p r o v et h ee f f i c i e n c yo fd a t aa n a l y s i so b s e r v a b l yb ys u c h a t t r i b u t er e d u c t i o nw i t h o u tl o s i n go r i g i n a lc l a s s i f i c a t i o ni n f o r m a t i o n s p a t i a ld a t a m i n i n ga l s oi n t r o d u c e dd a t ap r e t r e a t m e n t ，a n dd e t a i lm e t h o da r ep r o v i d e d b ys p a t i a l d a t ap r e t r e a t m e n t ，o r i g i n a ls p a t i a ld a t aw i l lb ep r e c i s et or e f l e c te s s e n c eo fp r o b l e m ， t h a ta r eu s e f u lt or e t r i e v a lm o r ew o r t h yr u l e si nt h ed a t am i n i n ga l g o r i t h m s t h i sp a p e ru s em a p l n f om a n a g i n gt h es p a t i a ld a t a ，s os p a t i a lr e l a t i o n sb e t w e e n s p a t i a lo b j e c t sa r ei m p l e m e n t e dw i t hm a p x ，i n c l u d et o p o l o g yr e l a t i o na n dd i r e c t i o n r e l a t i o na u t o d i f f e r e n t i a t i o n a f t e rp r o c e s s i n go fs p a t i a ld a t a ，i tc a ns t o r ei na t t r i b u t e d a t ab a s e t h a ta r ec o n v e n i e n tt oc l a s s i c a ld a t am i n i n gt e c h n o l o g yf o rf u r t h e r a n a l y s i s i nt h i sw a y , w ec a nm a k eu s eo fg o o dm e t h o d sa n di d e a si nc l a s s i c a ld a t a m i n i n gt od i s c o v e rs p a t i a lk n o w l e d g eu n d e rw e l l p l e a s i n gr e s u l t k e y w o r d ：d a t am i n i n g ，s p a t i a ld a t am i n i n g ，r o u g hs e t ，g i s ，a s s o c i a t i o nr u l e 1 引言 1 引言 1 1 数据挖掘的产生 数据挖掘是信息技术自然演化的结果，其主要依据在于数据管理和数据库的 发展及数据库系统功能的逐步强化( 如图1 1 ，h a n2 0 0 0 ) ：数据采集和数据库 创建、数据管理、数据分析和理解技术的发展。它是人工智能、数据库、统计理 论相结合的技术，具有广泛的应用前景。 关系数据库逐渐戚熟并被卢泛使用；第三旅发建委8 0 9 0 年代，先进的熟撼模型 被采用，产生了分布式数据库、扩展关系数据库、面向对象数据库、演绎数据库 和异质数据库管理系统等，并结合特定行业繇蜡需球j 又产生了许多面向应用的数 据库系统，如空间数据库、时态数据库、多媒体数据库、科学数据库、知识库、 全球信息库等等。j ”“。一一“，j? o 在过去的几十年中，计算机硬件的进步导致弱能强大的计算机、数据收集设 备和存储介质的出现，大大推动了数据库技术的发展，使数据库技术成为计算机 信息处理中最重要、应用最广泛的技术之一。同时数据采集技术也在迅速发展， 许多领域实时地直接获取数字化数据，如超市的条码阅读器每天可以获得大量产 品销售数据，遥感卫星每天可获取巨量的对地观测数据等，使得数据量和数据库 1=，|，op 贵州大学硕士学位论文 的数目增加的速度不断加快。图1 2 显示了数据激增的现实和趋势。 1 9 7 01 9 8 01 9 9 02 0 0 0 图卜2 数据增长示意图 数据的丰富和数据库的增加，使得原来的数据查询、检索方式无法满足人们 的需求。不能充分发掘和利用数据库中隐藏的丰富知识，数据库的急剧增长与人 们对数据库处理能力的相对落后形成了强烈的对比。这种无法充分利用和处理数 据的状态被描述为“数据丰富，但知识贫乏”( h a n ，2 0 0 0 ) ，“人们被数据淹 没，但却饥饿于知识”( 邸凯昌，2 0 0 1 ) ，“信息灾难”( 李德毅，1 9 9 9 ) 。因 此，我们将面l 临四大问题：信息过量，难以消化；信息真假，难以辨识；信息安 全，难以保证：信息形式不一致，难以处理( 李德毅，1 9 9 9 ) 。 我们可以收集大量的数据，然而却难于对数据进行有效分析和利用。这种形 势下，人们迫切需要有有效的数据分析和处理工具来帮助人们从海量的数据中提 取有价值的知识，挖掘隐含在数据库中的、可用于决策的规律和规则。数据挖掘 和知识发现( d a t am m 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 起源于从数据库中发现知识( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ， k d d ) ，首次出现于1 9 8 9 年8 月在美国底特律召开的第十一届国际人工智能联合 会议上。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年举行了k d d 的专题讨论会，汇集了来 自各个领域的研究人员和应用开发者。由美国人工智能协会主办的k d d 国际会 议从1 9 9 5 年开始，成为一年一度的大型国际学术会议，人数规模不断扩大，研究 重点也逐渐从发现方法转向系统应用。此外，数据库、人工智能、信息处理、知 识工程等领域的国际学术刊物也纷纷开辟了k d d 专题或专刊。 d m k d 是目前国际上数据库和信息决策领域的最前沿研究方向之一，引起 了学术界和工业界的广泛关注。一些著名的研究实验室，如i b ma l m a d e n 和g t e ， 以及众多的学术单位，如美国的u cb e r k e l e y 和加拿大的s i m o nf r a s e r 大学，都在 这个领域开展了各种各样的研究计划，并取得了丰硕的成果。国际上许多数据库 和数据仓库供应商、统计分析软件开发商以及专门的d m k d 开发商、研究所等， 相继研制开发出了数据挖掘软件产品。例如，i b m 公司的q u e s t 和i n t e l l i g e n t m i n e r ：加拿大s i m o nf r a s e r 大学的d b m i n n e r ；s g i 公司的m i l l es e t 等。此外，一 些关系数据库产品也加入了相关的数据挖掘功能和支持数据挖掘的接口，用户可 以通过构造数据仓库来实现数据挖掘功能，或者进行二次开发，来建立专门的数 据挖掘系统，女i m i c r o s o f l s q l s e r v e r 2 0 0 0 、o r a c l e 9 i 、i n f o r m i x 等数据库产品。 d m k d 技术也开始应用到市场营销、金融和银行业、生产销售和零售业、保险 业、医药、电信、交通、公司经营管理等领域。 - - 2 - - l 引言 1 。2 空间数据挖掘研究现状 随着地球空间数据获取技术的快速发展，传统的对空间数据的处理能力已显 得落后，远远无法满足海量数据处理的需求。将数据挖掘与知识发现技术引入到 空间数据管理系统中，结合地理信息系统等空间数据管理技术，能很好地满足空 间数据分析和处理的需要。地理信息系统( g i s ) 作为地球空间数据管理的重要手 段已得到地学研究领域广泛的认可和重视，但面对快速增长的空间数据如遥感影 像、g p s 测量、地图数字化、航空摄影测量等获取的数据，g i s 的分析功能已无 法满足数据自动处理的需要，这就制约了g i s 应用。在g i s 平台和它的基本空间 分析功能的基础上，根据地学空间数据的特点，将机器学习算法引入g i s ，形成 自动、智能化的地学空间数据挖掘与知识发现模型，增强地学数据的分析处理能 力，促成了空间数据挖掘和知识发现( s p a t i a ld a t am i n i n ga n dk n o w l e d g e d i s c o v e r y ，s d m k d ) 。 s d m k d 指的是从空间数据库中抽取隐含的知识、空间关系或非显式地存储在 空间数据库中的其他模式，用于理解空间数据库、发现空间和非空间数据间的关 系、构建空间知识库、查询优化、空间数据库数据重组、以简单精确的方式描述 通用特征等( 石云，1 9 9 9 ) 。空间数据库中的数据挖掘研究比关系数据库和事务 数据库中的挖掘研究起步要晚，但近几年引起需学术界的广泛兴趣。加拿大s i m o n f r a s e r 大学、德国慕尼黑大学、芬兰赫尔辛基大学以及美国、澳大利亚等国家的 许多大学和研究所都有空间数据挖掘的成果报道：他们研究的重点是提高原有数 据挖掘算法在空间数据上的执行效率尊匀口拿大s i 。m o n ”f t a s e r p h a nj i a w e i 教授领导的小组，较早对此进行系统全面的砩究，并在m a p i n f o 平台上建立了空 间数据挖掘的原型系统g e o m i n e r ，实现了空间数据特征描述、空间比较、空间关 联、空间聚类和空间分类等空间数据挖掘方法i , l u ，h a n 和o o i 提出了面向属性归 纳的基于概化的空间数据挖掘方法。n g 和h a r t 提出一种基于聚类结果的描述性空 间数据分析方法。h a n ，s t e f a n o v i c 和k o p e r s k i 研究了有兼空间数据立方体的设 计和构造问题。k o p e r s k i 和h a n 提出了一种逐步求精韵空间关联规则挖掘方法。 k n o r r 和x u ，以及e s t e r ，f r o m m e l t 给出了空间分类和趋势分析的方法。k o p e r s k i ， h a n 和s t e f a n o v i c 提出了一种空间数据分类的两蓼绣皓。e s t e r ，k r i e g e l ，s a n d e r 和x u 提出了一种基于密度的空间聚类方法。n g 和h a n 把基于k 一中心点的聚类方法 c l a r a 扩展到空间数据挖掘上，并提出了2 种基于随机搜索的新的空间聚类方法。 此外，一些著名的数据库系统公司和数据统带卜分析公司，如r b m 、s g i 、s p s s 、a s 、 s y b a s e 等都加入到数据挖掘领域，纷纷推出通用的数据挖掘系统。还有g i s 软件 产品，如e s 工i 公司的a r c i n f o 、a r c v i e 碟争i ；错觥加与实现空间数据挖掘和知 识发现相应的功能。一”。 在我国，空间数据挖掘和知识发现的研究 延在进行1 9 9 4 年，武汉大学季 德仁院士提出了从g i s 。数据库申发现知识静建黼并与李德毅院士合作，- 开始了 空间数据挖掘和知识发现的理论、方法与应用研究。此外，中科院地理所的周成 虎教授也带领自己的科研人员，进行空间数据挖掘和知识发现的理论和应用研 究。中国图形图像学报在1 9 9 9 年1 1 月也出版了针对空间数据挖掘的专辑。随着g i s 的推广和空间数据库建设的进一步深化，空间激据挖掘和知识发现的重要性越来 越受到大家的重视，国内从事该领域研究的专家学者也逐渐增多。 3 - - ijlo，q省趸l书!镯o。l 贵州大学硕士学位论文 1 3 主要研究内容 本文针对县级林业信息管理系统的研究与应用项目，研究基于粗糙集的 g i s 空间数据挖掘的方法上，即如何从g i s 的空间数据中发现更多感兴趣的以及新 类型的知识。该项目考虑到林业信息化建设的系统性、整体性的需要，多年来县 级林业部门所建的各种单、散、小系统需要整合的需要，基于c s 结构开发了林 业基础地理信息平台及其森林资源地理信息系统、森林防火指挥与灾后评估系统 和生态公益林管理系统等3 个系统，这些系统的使用产生了大量的空间数据。另 外，空间数据挖掘如何与g i s 、数据库系统相结合，如何借助g i s 实现空间数据挖 掘的可视化等也是我们研究的内容。 从数字化的空间实体信息中，通过一系列的空间关系的判断和特征分析，识 别出其中包含的空间特征和空间分布规律，用种描述性的语言进行表达，可以 让用户总体形象地理解其中的信息，有利于非专业人员对空间数据的理解和应 用。本文针对某区域，选择林业小班作为研究对象，按照空间数据的组织方式， 在保证地理目标意义完整的前提下，对数据进行组织。同时通过空间数据挖掘算 法，获得空间关联规则，确立小班树种在空间分布的空间规律。论文的组织结构 如下： 第一部分，简要讨论了论文的起因、数据挖掘和空间数据挖掘的含义、发展 现状； 第二部分，粗糙集基本理论的探讨，作为空间数据挖掘数据预处理部分，粗 糙集的属性约简技术可以为大数据集进行数据归约，从而得到等价的、简化的数 据集，提高挖掘算法的效率： 第三部分，讨论了空间数据挖掘基本理论，提出了基于g i s 的空间关系的判 别方法，为进一步的实验打下基础： 第四部分，讨论了基于粗糙集的空间挖掘技术在林业中的应用。选择一个县 级市的区域，通过m a p l n f o 平台进行空间数据的数字化，然后通过不同对象间的 空间关系的计算获得它们之间的临近关系。在临近关系的基础上，通过经典的数 据挖掘算法可以得到空间关联规则，得出空间对象间的一般规律，以利于决策。 该方法在实验数据的处理中取得了一定的效果。但由于讨论的数据的正确性和数 据量的问题，以及空间数据表达的多样性，该方法还难以对大范围的数据进行处 理，需要进一步的探讨和完善； 第五部分，结束语，讨论了本文方法的适用性以及发展方向。 一d 一 2 粗糙集及算法设计 2 粗糙集及算法设计 2 1 粗糙集研究状况 现实生活中有许多含糊现象并不能简单地用真、假值来表示，如何表示和处 理这些现象就成为一个研究领域。早在1 9 0 4 年谓词逻辑的创始人g f r e g e 就提出 了含糊( v a g u e ) 一词，他把它归结到边界线上，也就是说在全域上存在一些个体， 它们既不能在某个子集上分类，也不能在该子集的补集上分类。 1 9 6 5 年，z a d e h 提出了模糊集，不少理论计算机科学家和逻辑学家试图通过 这一理论解决g f r e g e 的含糊概念。但模糊集理论采用隶属度函数来处理模糊性， 而基本的隶属度是凭经验或者由领域专家给出，所以具有相当的主观性。 2 0 世纪8 0 年代初，波兰科学家p a w l a k 针对g f r e g e 的边界线区域思想提出了 粗糙集( r o u g hs e t ) ，他把那些无法确认的个体都归属于边界线区域，而这种 边界线区域被定义为上近似集和下近似集之差集。由于它有确定的数学公式描 述，完全由数据决定，所以更具有客观性。粗糙集理论作为一种智能决策分析数 学工具，被广泛研究并应用于不精确、不确定、不完全的信息的分类分析和知识 获取中。它的主要思想就是在保持分类能力不变的前提下，通过知识约简，导出 问题的决策或分类规则。 粗糙集理论的主要优势之_ 是它不需要任何预备的或额外的数据信息。自提 出以来，许多计算机科学家和数学家对粗糙集理论及其应用进行了坚持不懈的研 究，使之在理论上日趋完善，特别是由于2 0 世纪8 0 年代末和9 0 年代初它在知识发 现等领域得到了成功的应用而越来越受到国际上的广泛关注。 1 9 9 1 年p a w l a k 教授的第一本关于粗糙集的专著r o u g hs e t s ：t h e o r e t i c a l a s p e c t so fr e a s o n i n ga b o u td a t a 和1 9 9 2 年r s l o w i n s k f 主编的关于粗糙集应 甩吸其与相关方法比较研究的论文集的出版，推动了国际上对粗糙集理论与应用 。盼深入研究：1 9 9 2 年在波兰k 连k 讫召开了第1 届国际粗糙集讨论会。“从此每年召 开2 次与粗糙集理论为主题的国5 际研讨会。 、 粗糙集理论在医疗诊断、“诀策分析、机器学习、信息检索、近似推理等领 域都获得了成功的应用，：或秀知识发现的重要工具。在数据挖掘与知识发现中， 无需提供问题所需处理的数据集合之外的任何先验信息。粗糙集理论强调的是 信息系统中知识的不完全性、不可分辨性，其处理方法是确定性的，要求属性 值都是定性值，而实际应用中大量存在的是定量数据，必须设法转换成定性数 据才能运用粗糙集方法。因此与其它处理不确定性问题的理论，如模糊数学、 云理论等，具有很强的互补性，可以互相促进，增强其知识发现的能力： 根据利用统计信息与否，现存的粗糙集模型及其延伸可以分为代数型和概 率型两大类。粗糙集由上近似集和下近似集组成，是一种处理不精确、不确定 和不完备信息的智能数据决策分析工具，较适于基于属性不确定性的i 空间数据 挖掘。粗糙集从集合论的观点出发，在给定论域中以知识足够与否作为实体分 类的标准，并给出划分类型的精度。上近似集中的实体具有足够必要的信息和 jjji，、，dwdo，dl铷l、，119，习诩潮埘啊111爿1词孤姐11潮 贵州大学硕士学位论文 知识，确定属于该类别：论域全集以内且下近似集以外的实体没有必要的信息 和知识，确定不属于该类别；上近似集和下近似集的差集为类别的不确定边界， 其中的实体没有足够必要的信息和知识，无法确切地判断是否属于该类别，为 类别的边界。若两个实体有完全相同的信息，则它们为等价关系，不可区分。 基于粗糙集的数据挖掘系统有g r o b i a n 、r s 2 d m 、le r s 、t r a n c e 、p r o b r o u g h 、 r o s e t t a 、r s l 、r o u g h f a m i l y 、t a s 、r o u g h f u z z y l a b 、p r i m e r o s e 、k d d r 等。 此外，还可以在粗糙集的基础上，发展专门针对空间信息学的地学粗空间理论： 利用粗糙集理论、模糊数学和插值函数等技术，基于属性不确定性，在空间数 据库或空间数据仓库中，可以挖掘和发现用于影像分类和分析、地价评估和空 间表达、城乡结合部用地分析和规划的知识。 本文将讨论粗糙集理论的核心内容之一属性约简。属性约简指在保持知识 库分类能力不变的条件下，删除其中不相关或不重要的属性，从而简化原有的 系统。一般来说，描述对象特征的属性集是较大的，但是对于信息系统分类的 知识发现来说，不同属性的重要程度是不同的。有些是绝对不必要的，去掉这 种属性并不影响分类的知识发现；还有一些属性是相对必要的，去掉这种属性 必然会影响分类的知识发现。属性约简就是要在属性集中寻找一个最小的属性 集，它能完全确定知识发现，也即由这个最小的属性集确定分类知识与用全体 属性集确定的分类知识是相同的。本文将属性约简应用于林业信息管理数据， 结合具体实例讨论了粗糙集在林业信息管理中的应用，说明了这些方法的有效 性。 2 2 粗糙集基本理论 设是非空有限论域，r 是一个不可辨别关系( i n d i s c e m i b i l i t yr e l a t i o n ) ，或 称等价关系( e q u i v a l e n c er e l a t i o n ) ，即斤是自反、对称和传递的。如果在，中的 两个元素五y 有x r y ，那么称x 、j ，为不可辨识的。序对a p r r = ( “而称为近似空 间( a p p r o x i m a t i o ns p a c e ) 或知识库。斤是上由生成斤的等价类的全体，它 构成了的一个划分，可记为i n d ( r ) ；记等价类 朗。= ( yi m 吲。r 中的等价类 称为基本集( e l e m e n t a r ys e t s ) ；基本集的有限并集称为可定义集( d e f i n a b l e s e t ) ，或称合成集( c o m p o s e d s e t ) ，基本集的元素也被称为源知识，意思是其 他知识可以由源知识来组合。 为了能够在近似空间a p l r 中通过基本集来表示的子集月，定义一对近似算 子下近似( 1 0 w e ra p p r o x i m a t i o n ) 和上近似( u p p e ra p p r o x i m a t i o n ) 如下： 鲋= x e u l i x 。铘 面= x e u l i x 。n a ，升 ( 1 ) ( 2 ) 我们称序对( 区爿，r 爿) 为集合爿的粗糙集。通过图2 - 1 可以形象地说明粗糙 集的基本概念。在图中，曲线所包含部分为集合a ，由矩形单元构成二维近似 空间，其中每个单元表示一个等价类，a 的下近似和上近似如图所示。 2 粗糙集及算法设计 ， i j i 丫 i陟 ， 、 量 r a a r a 图2 1 粗糙集基本概念关系图 定义b n d ( a ) = 瓦4 一苎口，称为彳的边界( b o u n d a r y ) ，或边界区( b o r d e r l i n e r e g i o n ) ：称p o s 研) = l 3 a 为x 的正区域( p o s i t i v er e g i o n ) ；称 n e g ( a ) = u 一融为x 的反区域( n e g a t i v er e g i o n ) 。 若把r 看成分类的知识，a 的正区域中的目标可以确定地分类为a 的成员； 反区域中的目标可以确定地判断不属于月，即属于a 的补集一彳；边界区中的目 标无法确定地判断属于a 或一九卅是r 一可定义的，简称可定义，当且仅当 r a = 鲋。a 对于r 是粗略的( r o u g h ) ，当且仅当l 4 _ h a 。 若u = x 。，x2 一，x 。) ，u 中的每个x 。( i n ) 称为一个对象；a = a 。，a ：，、， 巩) 为属性集，a 中的每个a 。( j m ) 称为一个属性：f = f ，：j m ) ，其中f j ：u v ，( j m ) ，v ，为属性a 。的值域。则我们称( u ，a ，f ) 为一个信息系统，或数据库 、系统。 f f 有属性集b a ，若满足= ，兄并且对任意b b 有m ；r a ，则称b ，： 为信息系统( u ，a ，f ) 的属性约简。j d ， 设信息系统，a ，f ) 中，曲嘭确定的划分为4 = 尺。= c f ：f s f ) ，t 为划 分数。用五( g ) 表示属性n 。关于c _ _ 肆“的獬参嗨值? 。、我们称 d ( e ，c ) ； 喀彳：蔫弼) 石( c ，) ) ( 3 ) 为g 与c 的可辨识属性集。称 ，。t 刀= d ( e ，c f ) ：f ，s t ) ( 4 ) 为信息系统的可辨识属性矩阵。它所对应的辩识公式： ，。“学 - ” m = 。鼻( 。d ( g ；c * 。_ ( 5 ) 1 ；，_1蠼码凋调a1 i_1_i诅1，；jill 贵州大学硕士学位论文 设僻，s ) 是偏序集，若对v x ，y e x 都有数d ( y x ) 与之对应，且满足： ( 1 ) 0 sd ( y x ) s 1 ， ( 2 ) xs y = d ( y x ) = 1 ( 3 ) xs ys z j d 0 z ) s d y ) 则称d 为x 上的包含度。 对于b c _ a ，d 以，记u = x k ：工u ，u r o = d 1 ，d 2 ，d ，) ，其中 r l = y e u ：0 ，y ) e ，。记 。( d i i x 加槲吣r ) ( 6 ) 则d 为尹( u ) 上的包含度，其中夕) 表示u 上的全体子集。根据对象集 上的包含度，我们可以确定规则的置信度。 2 3 模糊集与粗糙集的集成 设是由一些确定的可识别的对象构成的集合( 称为论域) ，在，上的一 个模糊集f 通过其隶属函数p ，：u + 【o ，1 】表示。经典集合可以看作为模糊集当 将其隶属函数的值域从 o ，1 限制到 0 ，1 时的一个特例。给定一个数口e o ，1 ， 一个模糊集f 的n 截集凡定义如下：e = 缸u iu ，0 ) 口) 。通过a 截集可以 实现模糊集合与经典集合之间按照一定的法则进行转化。通过n 截集，一个模 糊集决定了上的一簇子集；相反，一个模糊集尸也能通过其a 截集按照如下 方式复原：，x ) 一s u p 恤i x 只) 。因此，通过a 截集也可以表示一个模糊集。 基于集合的表示方法的最大优点在于它显式地给出了模糊集与经典集合之间的 关系，而这对于深刻理解模糊集，处理模糊集具有非常重要的作用。 若r 是在u u 上的一个模糊集，则称r 是u 上的一个模糊关系。记r 的 隶属函数为u 。( x ，y ) ，它表示元素x ，y 的相关程度。若模糊关系r 还满足自反( 对 所有x u ，有ur ( x ，x ) = 1 ) 、对称( 对所有x ，y u ，有1 1r ( x ，y ) = pr ( y ，x ) ) 和传递( 对所有x ，y ，z u ，有u 。( x ，z ) m i n ur ( x ，y ) ，ur ( y ，z ) ) ，则称r 是 u 上的模糊等价关系。 在粗糙集的经典模型中，通过近似算子可以用厅来描述一个经典集合。 但是在实际的应用中，往往涉及到的知识或概念是模糊的不确定的，这时就要 考虑，上的一个模糊集合如何使用已知的确定知识，即斤来表示。这导致了 对粗糙集和模糊集集成的研究，并产生了粗糙模糊集和模糊粗糙集的概念。 近似空间8 口r 产( “励，f 是上的一个模糊集，则f 关于a p 2 r 的一对下近 2 粗糙集及算法设计 c a a p _ 竺足( f ) 和上近似缈r ( f ) 定义为斤上的一对模糊集合，其隶属函数分别 定义为： z a p ! ( 吲r ) =f ( ) ，)r ) (7)s(f) i n f z iy e x 肛玩( n ( m 一) ；s u p h ，( y ) i y e x 一 ( 8 ) 我们称序对( 印，。( f ) ，a p t 。( f ) ) 为论域上的粗糙模糊集。在经典粗糙模型 的近似空间a p r r = ( “励中，属于同一等价类中的两个对象是不可辨别的。从式 ( 7 ) ( 8 ) 我们也可以看出，近似空间中的同一等价类的隶属函数都是常数。 i g a p r 。( f ) o ) 可理解为对象j 肯定属于模糊集尸的隶属程度，p 石。( d o ) 可理解为 对象肖可能属于模糊集f 的隶属程度。 给定论域和模糊等价关系尼序对a p r , = ( “励称为模糊近似空间。元素 肖对应的模糊等价类 捌一定义为口m o ) = 卢m 0 ，y ) 。序对( ! 坐m ( f ) ，印r m ( f ) ) 为 论域u 上的模糊粗糙集，其中近似算子印r 。和a p r m 的隶属函数按如下方式定 ! 义： 肛，。( ，) ( b k ) = i n f m a x t u ，( y ) ，1 一【，h ( y ) ) i ) ，p 月) ( 9 ) 肛石。( ，) ( m 一) = s u p m i n p e ( y ) p i ，】，( y ) i y e z 一) ( 1 0 ) 根据我们上面所定义的粗糙模糊集和模糊粗糙集，通过比较公式( 7 ) ( 9 ) 和 公式( 8 ) ( 1 0 ) 可必发现，粗糙模糊集其实是模糊粗糙集中将模糊等价关系的取值 范围从 o ，1 限制到 0 ，1 ) 时的一个特例。0 蠢 。 现在通过一个具体的实例来说明模糊集和赧糙集集成的应用。某学校根据 课程a l 、a 2 、a 3 评估学生的表现，给出6 个学生酌爹葶铡，= x 。，x 。，x ，柏，x 5 x 6 k 评估信息表见表2 1 。每门课程的取值范围为 o ，05 ，d 给出了学生最终表现，取 值范围为 0 ，i 。 扭 、蠢，a 2a f。d x 1 。 2 1 ，。3 ， 白5 ， 32 。气坶羹戈 x 2 x 趾 21 易0 曩 x d尊22誊2 萄：7 x j ll4o 4 x 6 32 l0 5 翟； 表2 - i 学生评估信息表 评估结果d是 u上的 模糊集，即 、 + 0 。 o 一 爨旗| ，| ? 一： 贵州大学硕士学位论文 d = 0 5 x 。+ 0 6 x ：+ o 6 x 。+ o 7 x 。+ o 4 x ；+ o 5 x 。按照属性集爿= a 。a 2 ，a 。) 将u 分为4 类：g = x 。，x 。 ：岛二 x ：，x 。 ：g = x 。) ：g = x 。) 。根据公式( 7 ) ( 8 ) 可得到d 关 于爿的下近似：a p r 爿( d ) 2 0 5 c , + 0 5 厶+ o 7 厶+ o 4 g ， 和d 关于彳的上近似：缈4 ( d ) 2 0 6 c + 0 6 g + 0 7 g + 0 4 c 4 。 取值，可以从表1 中计算出模糊关系露： ，其中五( 韵表示对象毋在属性a 。上的 显然露是自反和对称的。进一步，通过模糊关系的闭包运算可可到模糊等 价关系r ： 在模糊近似空间( “露) 中，根据公式( 9 ) ( i 0 ) 可计算出模糊粗糙集的下近 似和上近似为： a p r 册，( d ) 2 0 5 c - + 0 5 岛+ 0 7 g + 0 4 g ， 印7 m ，( d ) 2 0 6 c , + 0 6 厶+ 0 7 g + 0 4 岛。 从这个结果可以看到，只要选取适当的模糊等价矩阵，相应计算出的模糊 粗糙集与从原关系表中计算出的粗糙模糊集是一致的。 根据上面我们得到的在近似空间中的近似算子给出了不同类上的评估的 下限和上限，为客观地综合评价学生起到重要作用。如果给出评价的阂值，经 、lllllj卯卵 n l n n n l 3 o 3 7 0 0 暑5 o 穹一m 5 0 o o 0 1 0 2 7 2 0 7 7 9 7 9 o 7 7 o o o l o 0卵蛇昭酊 l n l n n n卯酊 如 o l 0 o o 1 o 7 0 2 3 7 m 石m 9 名石 1 0 1 o o o ，l = 昂 、lljij 7 o 7 7 7 0 7 0 7 7 7 0 o 1 o 0 0 1 3 7 3 3 0 7 8 7 8 8 0 7 o 0 o 0 1 o蛇 蛇船 o o o 1 0 0 0 7 0 2 3 7 0 7 0 9 8 7 1 o 1 o o 0 7 o 7 7 7 o 7 0 7 7 7 0 0 1 o 0 o 1 0 7 0 2 3 7 o 7 0 9 8 7 1 o 1 0 0 o ，。l = 拧 2 粗糙集及算法设计 过进一步的数据处理，可获得关于原系统的关联规则和其它的决策信息。这可 作为归纳学习的方法用于对各种应用的决策之中。 模糊集与粗糙集的集成是模糊集理论与粗糙集理论研究的必然结果。粗糙 模糊集是经典近似空间中模糊集合的近似，而模糊粗糙集是模糊近似空间中模 糊集合的近似。通过以上具体的实例讨论了分析问题的方法。在决策过程中， 如果决策属性不是一个确定的值，而是根据相应的条件属性变化时，模糊集和 粗糙集的集成往往可以利用各自理论的优点到达比较好的解。因此，它们许多 领域中具有很大的应用价值。 2 4 算法实现分析 根据上面讨论的粗糙集基本理论，我们通过一个具体的实例给出核心属性 约简的算法。若有一个信息系统表2 2 。 系 u a l口2码 x l 2 13 x 2321 x 3213 x 4114 x 5112 x 6114 x 7123 x 8 12 3 表2 - 2 信息系统表 如果凡= “，x ，) ：五 ) = f t ( x j ) ( 1 = 1 ，2 ，3 ) ，则上面的信息系统通过等价关 a 口1口2 口3 c l = “，x d 213 c ：= 忆) 321 c 3 = 仁7 ，x s 1 、2 ，3 c 4 = 协。，) 114 c 5 = 玩) 112 表2 - 3 简化后的信息系统 贵卅i 大学硕士学位论文 根据辨识矩阵公式( 4 ) ，表2 - 3 转换成表2 4 所示的可辨识属性矩阵。 c ic 2gag c l 庐a a i , a 2 “，a 3 口l ，a ， c 2 4庐 a i , 口3 ) 爿爿 c 3 口1 ，a 2 n 1 ，a 3 妒扣：，码 口l ，口，) c 口1 ，a 3 爿 口2 ，巳 妒 呜 g“，a 3 爿 口2 ，a 3 口，妒 表2 - 4 辨识属性矩阵 可得辨识公式： m = a 3a 0 lv 口2 ) a 0 lv a 3 ) a ( 口2v a 3 ) a 0 1v a 2v a 3 ) 由于a 3s a lv 口3 ，0 3s a 2v a 3s ( a lv a 2v a 3 ) 所以m = a 3a ( 口1v a 2 ) = ( 口la a 3 ) v 0 2a a 3 ) 。 最后得到约简 a ia a 3 ) 和 口2a 码) 。 根据以上示例，给出核心属性约简的算法： s t e p l ：在二维数据表中，消去重复的行得到相同的对象分类 s t e p 2 ：将两个记录集r s i 和r s 2 指向简化后的表中的记录集 s t e p 3 ： r s i 移动到第一条记录第一条记录游标为0 ，r s i 指向竖直方向的记录集 r s 2 移动到第一条记录 i n d e x = l标志，用来使r s 2 移动到r s i 的当前游标的下一条记录 只处理上三角矩阵数据( 矩阵是对称的) 。 w h i l e ( r s i 非空) r s 2 移动到第i n d e x 条记录： i n d e x + + ： w h i l e ( r s 2 非空) 比较r s 2 当前记录和r s i 当前记录，得到相应可辨识矩阵中项的值 r s 2 移动到下一条记录； ) r s i 移动到下一条记录； ) s t e p 4 ：分配上一步得到的最简可辩识矩阵，得到最终属性约简结果。 下面结合表2 3 和表2 - 3 的辨识属性矩阵来说明这个算法。 算法开始时，r s i 和r s 2 都包含c 1 ，c 2 ，c 3 ，c 4 ，c 5 一使r s i 移到第0 条当前值为c 1 ， 2 相糙集及算法设计 1 r s 2 则移到第1 条( 0 + 1 ) 当前值为c 2 进行各个属性值的比较c l 在属性a l ，a 2 ，a 3 上的值分别为2 ，1 ，3 而c 2 在属性a l ，a 2 ，a 3 上的值分别为3 ，2 ，1 所以当前格里的值为 a = ( a 1 ，a 2 ，a 3 2 r s 2 移到第2 条前值为c 3 ，与r s i 的当前值c 1 进行比较得 a 1 ，a 2 ) 3 r s 2 移到第3 条前值为c 4 ，与r s l 的当前值c 1 进行比较得 a 1 ，a 3 ) 4 r s 2 移到第4 条前值为c 5 ，与r s l 的当前值c l 进行比较得 a l ，a 3 ) 二r s i 移到第1 条当前值为c 2 r s 2 移到第2 条前值为c 3 ，与r s l 的当前值c 2 进行比较得 a 1 ，a 3 ) r s 2 移到第3 条前值为c 4 ，与r s l 的当前值c 2 进行比较得a = a 1 ，a 2 ，a 3 ) r s 2 移到第4 条前值为c 5 ，与r s l 的当前值c 2 进行比较得a = a 1 ，a 2 ，a 3 三r s l 移到第2 条当前值为c 3 1 r s 2 移到第3 条前值为c 4 ，与r s l 的当前值c 3 进行比较得a = ( a 2 ，a 3 2 r s 2 移到第4 条前值为c 5 ，与r s i 的当前值c 3 进行比较得a = a l ，a 3 ) 四r s i 移到第2 条当前值为c 4 1 r s 2 移到第4 条前值为c 5 ，与r s l 的当