（管理科学与工程专业论文）基于粗糙集理论的不确定决策问题的研究与应用.pdf

摘要 ( 决策需要知识，目前的决策系统因知识获取瓶颈而发展缓慢。粗糙集作为一种 处理不确定、不精确数据的数学工具，从新的角度认识知识，特别值得注意的是它 与其它软计算方法有很强的集成能力。此种背景下，基于粗糙集理论分析的决策就 成为决策学科的一个前沿问题。同时必须看到，粗糙集还是一个发展中的新生事物， 在许多方面的研究仍是开放问题。这些问题的解决，是扩大粗糙集实用化的基石o 弋 本文妊是以此为契机芦就粗糙集理论分析为中心的几个关键问题进行了深入的研 究。全文重点论述的内容如下： ( 1 )连续属性的离散化，是制约粗糙集发展的主要障碍之一。从粗糙集的角度， 就相容连续条件属性决策表的离散化，提出了一种简单的离散化方法。最优离 散化是n p - h a r d 问题，这里引用文献2 将之转化为0 - i 数学规划问题。鉴于数 学规划对大型决策表离散的计算收敛性问题，提出了一种新的基于第一类分类 分离矩阵和第二类分类分离矩阵的遗传算法的连续属性离散算法。 ( 2 )选择合理有效的简明属性集，是粗糙集研究的重要内容。最优属性选择也是 n p h a r d 问题。在分析属性选择方法不足的基础上，利用特征矩阵概念，提出了 最优属性选择的启发式算法。算法能在决策表有效约简的情况下全面得到最优 解。此外，基于扩张矩阵理论，提出了一种求解最优属性的改进优化模型。并 用遗传算法研究最优属性的选择方法。 ( 3 )粗糙集理论分析的精华是约简决策表，挖掘其中的有用模式辅助决策。针对 相容无噪决策表，引鉴了两种从决策表获取知识的算法一i t i l 算法和启发式规 则获取算法。并就复杂决策表，研究了一种决策表的分解方法，简化了大型决 策表的分析难度。 j 关键词：粗糙集，专家知识。( 粗糙集理论分析厂决策表，离散化，属性选择， 知识获取 a b s t r a c t d e c i s i o n d e p e n d so nk n o w l e d g e r o u g h s e ti sat o o lf o r p r o c e s s i n g i n d e f i n i t e ，i m p r e c i s ed a t a ，w h i c h d e a l sw i t h k n o w l e d g e i nt e r m so f c l a s s i f i c a t i o n e s p e c i a l l y ，i ti sv e r ye a s yt oi n t e g r a t et h et h e o r yw i t h a l m o s ta l1o t h e rs o f t c o m p u t i n gm e t h o d ss u c ha sn e u r a ln e t w o r k s i n t e g r a t e d s y s t e m sh a v et h ea d v a n t a g eo v e ru s i n gas o f tc o m p u t i n gs i m p l y u n d e rt h i s b a c k g r o u n d ，i n t e l l i g e n td e c i s i o nb a s e d o nr o u g h a n a l y s i sf o r m st h ef o r e f r o n t p a r to fd e c i s i o ns c i e n c e a tt h es a m et i m e r o u g hs e ti sa tu si n i t i a ls t a g e a n dm a n yp r o b l e m st h a tc o n c e r na r es t i l lo p e n o n l yt h ep r o b l e m sa r es o l v e d c a nr o u g hs e ta p p l yt od i f f e r e n td o m a i n ss u c c e s s f u l l yi nt h et h e s i s ，w es t u d y af e w i m p o r t a n tp r o b l e m s i n d e p t h t h e t h e s i sm a i n l yc o n s i s t so ft h e f o ll o w i n g ： ( i ) t h ed i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e si sa ni m p o r t a n tm e t h o d f o rc o m p r e s s i n gd a t aa n ds i m d l i f y i n ga n a l y s i s t h eo p t i m a ld i s c r e t i z a t i o n h a sb e e np r o v e dt ob en p - h a r d s o m eh e u r i s t i cd i s e r e t i z a t i o na l g o r i t h m sh a v e b e e nu s e db u tt h e r ee x i s td i s a d v a n t a g e si nt h e m f o re x a m p l e ，t h ec h o i c e o fi n i t i a ls e to fc u t si sh a r dt ob ed e t e r m i n e d b a s e do l lt h e r o u g h s e tt h e o r y ， w et r a n s f o r mt h ed i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e si n t o0 1i n t e g e r p r o g r a r 肿i n g ，w h i c h c a nb es o l v e d s u c c e s s f u l l yb y e x i s t e n ts o f t w a r e ， f u r t h e r m o r e ， a g e n e t i ca l g o r i t h mu s i n g f i r s ta n ds e c o n dc l a s so f d is c r e t i z a t i o nm a t r i xi sp r o p o s e dt oc o m p u t et h eo p t i m a ld i s c r e t i z a t i o n ( 2 ) t h eo p t i m a lf e a t u r es u b s e ts e l e c t i o ni sa l s oan p h a r do n ea n d t h e r ea r em a n y1 i m i t si np r e v i o u sa l g o r i t h m s an e wh e u r i s t i ca l g o r i t h mi s p r e s e n t e d t os o l v et h ed i f f i c u l t y t od e c i s i o nt a b l e sw h o s en u m b e r o f f e a t u r e si sr e d u c e dg r e a t l ya f t e rr e d u c t i o n ，t h ea l g o r i t h mi si l l u s t r a t e d t ob ee f f e c t i v e e s p e c i a l l y ，i tc a ng i v ea l m o s ta l lt h eo p t i m a ls o l u t i o n s f u r t h e r m o r e ，t h ef e a t u r es e l e c t i o ni sc h a n g e di n t oa no p t i m i z a t i o np r o b l e m a n dt h ec o r r e s p o n d i n gm o d e l sa r ep r o p o s e db a s e do ne x t e n s i o nt h e o r y ，w h i c h u s e dt ob eu t i l i z e df o rh e u r i s t i ca l g o r i t h m s t h em o d e l sa r eb o t hs o l v e d b ye x i s t i n gs o f t w a r eo rg e n e t i ca l g o r i t h m s ( g a s ) a n dm o r eu n d e r s t a n d a b l e ( 3 ) r o u g ha n a l y s i si sa c c o m p l i s h e di na n a l y z i n gt h ep a t t e r ne x i s t i n g i nd e c i s i o nt a b l e sb yr e d u c t i o n t w or u l ep r o d u c e r s - - i t i l ( i n f o r m a t i o nt h e o r y b a s e di n d u c t i o nl e a r n i n g ) a n d h e u r i s t i c k n o w l e d g e e l i c i t a t i o n ，a r e d e s i g n e d a sf a ra sc o m p l e xd e c i s i o nt a b l e sa r ec o n c e r n e d ，ad e c o m p o s i t i o n i j a l g o r i t h mi sg i v e nt ol o w e rt h ea n a l y s i sd i f f i c u l t yt o o k e y w o r d s ： r o u g hs e t ，e x p e r tk n o w l e d g e ，r o u g ha n a l y s i s ，d e c i s i o nt a b l e d i s c r e t i z a t i o n ，a t t r i b u t e ss e l e c t i o n ，k n o w l e d g ea c q u i s i t i o n l 一 南京航空航天大学硕士学位论文 绪论 信息是决策的依据，是决策者的重要财富。信息技术，特别是管理信息系统和计算 机网络的发展，为信息的传播、存储和管理提供了广泛的基础。面对大量的数据，人 们已经意识到新型数据管理和信息浓缩技术在决策支持中的重要性，而传统的管理信 息系统所提供的功能已经不能满足决策者的需要。从大量的数据中开采其中隐含的、 有用的知识，是辅助决策的重要手段，这个问题已经成为决策科学的一个研究热点。 通常，数据库中的具有数量大、动态和噪声等特点。数据开采的质量与数据开采的方 法有密切的联系。目前，已经有多种开发方法，每一种都有其实用的范围，多种方法 的继承是一个有前途的发展方向。在此背景下，数据库知识发现技术( k d d ) 和数据开 采( d 加应运而生，并成为研究热点。整体上讲数据库为数据开采提供了物质基础， 数据开采是为了发掘蕴藏在数据重的有用信息。从大量的含有噪声、不完整、动态稀 疏性的数据中提取知识，是统计理论、数据库技术、机器学习等学科方向交叉的结合 点。 决策离不开知识。数据库存储的数据只是原始的信息。这些原始信息能够描述事 物的基本信息，告诉人们事情是怎样发生的，但不能直接用于决策，因为它们并不能 提供判断、解释和行动的依据。与数据的数量相比，决策所需的知识却相对较少。因 为决策所需的知识是隐含在数据背后的数据之间的关联或因果关系。从数据信息中浓 缩的可理解模式，才为知识。由于知识的含义随着计算机技术的高速发展被赋予了新 的意义，知识将于大量观察和实验数据的处理、处理、分析相联系。因此我们需要对 数据库中的原始数据进行分析、推理，发现数据的联系，提取有用特征，简化信息处 理，研究不确定、不精确知识的表达、学习、归纳方法等已成为这一领域的重要的研 究课题。 在数据采集中，在实际采集到的数据可能包含各种噪声，存在许多不确定因素和 不完全信息有待处理。传统的信息处理方法，如模糊集理论、证据理论和概率统计理 论等因需要数据的附加信息或先验知识，有时在处理大量数据的数据库方面能力欠 佳。 近年来，波兰华沙理工大学z p a w l a k 教授等一批科学家提出了粗糙集j 里论( r o u g h s e t st h e o r y ) ，粗糙集理论作为一种软计算方法，从新的角度认识知识把知识和分类密 切的联系起来，为处理不确定、不完全数据的分类问题提供了符合人类认识的数学工 具。下面简要的介绍粗糙集理论与其他相关的处理不确定问题理论的主要区别：粗糙 集理论与统计方法处理不确定问题完全不同，不是采用概率方法来处理描述数据的不 确定性，与这一领域中传统的模糊集理论处理不精确数据的方法也不同，虽然两者都 是研究信息系统中知识不完善、不准确问题，但它们的着眼点不同，粗糙集理论着眼 于集合的粗糙程度，模糊理论着眼于集合的模糊性；粗糙集理论基于集合中对象闻的 1 基于粗糙集理论的不确定决策问题的研究与应用 不可分辨性思想。模糊集理论基于集合子集边缘的病态定义模型；粗糙集理论的计算 方法是知识的表达与简化，模糊集理论的计算方法主要是连续特征函数的产生。 由于粗糙集理论所具有的独特的分析视角，因此，可以克服传统的不确定处理方 法的不足，并且和其他分析方法有机结合，可望进一步增强对不确定问题的处理能力。 可以说目前还没有其他的软计算方法能象粗糙集理论那样有非常强的亲和力。粗糙集 理论不但为信息科学和认知科学提供了新的科学逻辑和研究方法，还为智能决策提供 了有效的处理技术。作为一种数据开采方法，粗糙集的应用范围也是日新月异的。该 理论目前主要用于知识的约简和知识依赖性的分析，在医疗诊断、模式识别、专家系 统、机器学习、图象处理、数据挖掘等领域获得了广泛的应用。与此同时，我们也应 该看到：粗糙集是发展中的新生事物，其作用也不可能是万能的，无论从理论还是从 应用上讲，仍有许多方面需要进一步的研究。这一点将在本章的第二节加以介绍。 1 采用粗糙集理论进行分析的基本步骤 1 1 决策表的约简 粗糙集理论中，知识被定义为对事物的分类能力。这种能力由上近似集、下近 似集、等价关系等概念体现。因为粗糙集处理的对象是类似二维关系表的信息表( 决 策表) ，目前成熟的关系数据库管理系统和新发展起来的数据仓库管理系统，为粗糙 集的数据开采奠定了坚实的基础。 粗糙集从决策表开采规则，辅助决策，其关键步骤是求值约简或数据浓缩，包括 属性约简和值约简两个过程。决策表中的属性或取值并不是同等重要的，有些属性或 某些取值删除后对决策并没有多大影响，但它们占用存储空间和处理时间。决策表约 简经常涉及到核和可辨识矩阵【lj 两个重要的概念。设决策系统s t ( u c u 回，u 为非空 有限论域，c 为条件属性，d 为决策属性。可辨识矩阵定义为： 、| 口c ：口( _ ) a ( x m ，当d ( 一) d ( x a t ，工j u d 坫。气。砂一。一。f 2 1中，当d ( x ) ：d o ) l o 可分辨函数兵s ) = v ( c f ) ：l f 疗，。f 中) ，式中八和v 分别表示逻辑与和 逻辑或。通过逻辑运算将鸺化简，得到主蕴涵子( p r i m ei m p l i c a n t ) ，即为信息系统的 约简。其中所含元素数( 基数) 最小属性集合是最小约简。一般来讲，决策表的相对约 简有许多，最小约简( 含有最少属性) 是人们期望的。另一方面决策表的核是唯一的， 它定义为所有约简的交集。所以核可以作为求解最小约简的起点。但对大型决策表， 核的计算量较大，从而影响整个算法的效率。可辨识矩阵突出属性的分辨能力，从中 可以求出决策表的核以及约简。最小约简的求解需要借助启发式搜索解决。属性予集 的重要性可用条件属性子集b c _ c 与决策属性d 的依赖度： 2 簿察靛空较天天学疆士学锼论文 扣r 妒警 袭承，l i 簌零集螽豹基，删性8 表添b 豹di e 域。女越大，b 鞫d 躺依赖关暴越强 ( 统诗规律) ，褥秘的窥鲻譬信度莲大。蓠夺谦簿天获傣惑话魏穗魔辩耩往静蘩簧毪箨 了定义：设霞c ，￥a c - r 豹堇袋姓： s g f ( a , 鼠d ) = 【r ( 置回- r ( ( r 一 口) ) ，vy ( 置 并在踅基璐上提趣了一嵇蓥子互僚惠熬熟识约麓嬲算法m i b a r t l o l 。该嬲发式方 法尽管复杂性减小，健对最小麴筒的求解都憝不完备瀚。诧外，这些弊法还哭楚局限 子完全决策袋。决繁袭浓缩鹣效果可用下面三个参数度量： ( 1 ) 属幢蒸发率e , , = ( i - n n a ) * 1 0 0 ，其串忿帮磁分爱蔻终楚蠢帮鳕簿蔚鹣矮髅 个数； g 实镶蒸发率蓊1 颈蕊l ，箕孛蝣秀终篱蘑嚣慕瓣囊裂散，怒秀凌策表 实例冉白个数； 绉) 数摇蒸发率e - - ( 1 嘉赫擎l 衡，箕串掰器分裂受瓣蕊君簌嚣获繁袭戆数 据量。 瓣耀容决蘩表，癸怒获褥魄较蹇熟蒸发攀，萄戮馊臻不一致鼗摆浓续方法，其哉 价是弓i 入噪声，可将其视为例外。 没毒臻声戆决繁液。若糍获褥最，j 、约麓，郑么载粥以去除踅余，姻蚋笺溃骞效妁 决策知识，灾际数据般是被污染的，难受存在这样都样酶不足。对运祥静决策表， 瑟搜能够缮剿最小约稳，由此德到豹耀则也鑫嚣过拟食往往包禽数据中的噪声这样 豹蕊赠泛纯簸力差( 辩决策表井豹藜情嚣不黥歪确颈灏) 。露爨在绩惠不竞垒趣绪醺 下，阻于信息的缺菱。上述规则难以被激活，但近似约简会缀解这个问题。 1 2 连续属性的离散纯 糖琏集翡数学纂壤g 是豢裔论；赡戳壹犊处理连续憋鬓性。嚣现实决蓑表巾连续属 性是蒋遍存程的。因此连续糯性的离散纯是黼约程糙集理论蜜壤纯熟潦点之。这个 翊簇一壹是入王蟹熊舞关注舱焦点。连续羼性的离数他的根本出发点是在尽懿减少决 策衰信惠损必的靛弱下，瑟豫挎决策袭不两类怼糸豹阿劳辨关系，褥搿簿佬麓窝藏缭 的决綮表，戥便题糨糙集理论分析，锬得决饿所需要的知识。最优离敝化间趟一离散 的秘点数最少，蘑一麓痿发式葬法可漤褥爨满意懿臻莱。慈髂上鬟，蕊毫褰教纯轰滚 主要分为非般督离散化和监餐离散化。前者瓴括等宽度( 将迤续值属性的值域姆份) 和 等额攀离教纯( 每令蒜觳话嚣瓣溪含鹣慰蒙藕麓) 。嚣懿餐寓教恁方法饕单，但存在繁 划分域的方法过于死板等问题，因而也就滩以获得较好的离敝化效聚。只能斌用于属 毪：蒸蠢特爨分零麓媾涎。铮蹲主透溜题，夔餐蹇数纯方法考感了分类信息，太大改棼 了离散化效滟。目前比较有代表性的监督离散化方法有 三f 下凡种： 3 。 萋于挺糙集理论酶举确定决策薅麓豹磺究岛瘫期 ( 1 ) 文献1 2 提出了一种方法，通过不断调整分割点，蠢至在离散厝的每个区间里 包含尽量多的同类对象，并满足区间对象数达到菜一阙值； ( 2 ) 信息缡方法f l 朝，分割点c 对连续属毪a 值域翊分弓l 起的信怠熵定义为： 融岛：l ! 丛易 ) + 堕j 西域醍) 打开 式中c 和u 2 为决策表对象集认基为h ) 被分割点c 划分霜两个区间包含的对象数。互 值最小的分割点的离散效莱较好。对分割后的两个子隧间递归调用上述方法，直至满 慰要求( 如分类误差) 。从而完成整个麟往域酌离散化； ( 3 ) 穗糙集和布尔稚瑗“，给定决策表s - - - ( 酲c u 园，对任意连续属性a e , 4 ，其僮 域p ( 口，曲，将决策表中元素在属往a 的取值按照从小翔大的顺序排列 1 ，；，；， v ： ，姆艇会 t 华，华，。，华， 作为候选分割点集，每个候选分割点c ? 对应个b o o l 变量p ? ，若v ? 和v 在 决策表串对应的袄策藩校敬穰不潜，粼p ? = t r u e ；否裂芦? = f a l s e 。 此外还有贝叶斯决策法“8 和越平面等。这楚方法备有特点，值存在一个不足： 每个属性的离散化过程是相甄独驻的，即所谓的简部离散纯忽略7 簇往在嚣分对象 方面的关联佼和嚣 性，扶丽离散的结果串含有咒余鬣不合璎靛分裁点。锌对这令翊 髓，本文将在第弱章给密种新的连续嚣性离散纯方法，该方法兼鬏各个属性分割点 的分纯优势。； l | 蠲遗传算法进行分割点鹣优选，舆毒良好约分割效累。 连续震媸离数纯尽裁还存在豹迥题是缺乏递增豹离教化方法，即当掰的对象加入 决策表时，溅有的分割点可能不是最优或满意的。 l 。3 粗糙集与其它软计算方法的集成 粗糙集璐论和其它软计算方法的结合，能够提高簸据舞果髓力，这是出琨实毽界 的复杂性和簸理方法有黻能力静矛盾决定靛。其串耀糙集与神经掰终豹结会蹩研究豹 热点。獠糙集对噪声壤臻盈泛纯裁力弱( 弹缀难在穗有知识豹基础上再产生叛灼知 识) ，哥_ | 2 圭用辩经鼹络豹传点自组织、容错褪推广能力) 寒髂卦：亭孛经网络不能确定 蹩要的属性缎合、结构构造缺乏遵用的方法熙推理过程对用户等不足，可以用粗糙集 理论分掇辕助。粳糙集理论觏神经网络的结台实质上是人类两种思维方式一逻辑思维 和形象思维的结合。粗糙集翔神经网络的结合一般有5 种o ”： ( 1 ) 用粗糙集简化样本集( 实例集) ，然后辫用简化后的样本集训练网络，这样埘大 d 南京航空航天大学硕士学位论文 大简化网络的结构和训练效果； ( 2 ) 也先用粗糙集理论简化决策表，得到初始规则集利用( 模糊) 神经网络与( 模糊) 规则集的对应关系，构造网络结构( 确定网络的层数、各层节点数、权值及其它参数) ， 最后用遗传算法或梯度下降法精化网络有关参数； ( 3 ) 结合粗糙集和神经网络的优点，先用粗糙集分析( 简称粗分析) 得到初始规则， 然后用神经网络精化； ( 4 ) 粗糙集理论分析也可用于神经网络的后处理。对于训练过的神经网络用粗糙 集理论分析其权值，可以使神经网络的推理过程清晰化； ( 5 ) 神经元的出现可以弥补传统的神经网络缺乏语义的不足，在交通流量的预测 方面已取得较好的结果。 2 粗糙集理论应用的展望 粗糙集是发现知识、辅助决策的有效工具，具有坚实的理论基础。粗糙集理论自 1 9 8 2 年由p a w l a k 教授提出以来，已在许多领域得到了应用。仅就数据开采而言，每 年都有许多高质量的论文出现，新的功能不断完普，新的软件也不断推出。目前，随 着对粗糙集理论研究的不断深入，粗糙集的应用领域也正在不断的扩展。粗糙集理论 的优势在于： ( 1 ) 能够搜索数据的最小集合； ( 2 ) 评价数据的重要性： ( 3 ) 同时允许使用定性和定量的数据； ( 4 ) 从数据中产生决策规则。 目前粗糙集理论的应用领域涉及决策分析系统、数据挖掘、模糊粗糙集控制、粗 糙神经网，以及医疗诊断、专家系统等诸多方面。粗糙集理论的应用范围很广，不但 可以构造新的系统，而且关键在于它能够优化许多现有的算法。但对于数据逼近过程 中的数据丢失以及对属性判别的方法等方面还需要更进一步的研究。 但作为一种新事物，粗糙集在实用中也遇到了许多困难，目前的有效途径有两条： 一是粗糙集理论的拓展；其次是粗糙集与其它方法的深入和新型结合。这个问题虽然 已引起了人们的重视，但仍有许多问题需要深化。目前基于粗糙集的决策支持在下述 方面有待深化： ( 1 ) 粗糙集和其它软计算方法的进一步结合问题这是粗糙集的生长点，也是其 发展的动力： ( 2 ) 知识获取中，建立专家和知识工程师之间新型的合作关系：先由知识工程师( 通 过观察、出声”思考”和专家会谈) 或专家( 通过编辑软件) 收集大量的事例( 收集事例比 收集规则容易得多) ，然后采用粗糙集等机器学 - 3 7 - 具获得初始规则集。由于机器学 习的局限性，难以获得无噪声的知识库，所以还有必要对知识库进行优化( 如采用遗 5 一 基于粗糙集理论的不确定决策闯题的研究与应用 传算法、神经网络等) 和校验，以得到高质量的知识库，增加系统的实用性。上述过 程，实质上是面向专家的，知识工程师的主要任务是引导和协助专家对知识获取的一 些问题进行技术处理，从而在他们之间形成了新的合作关系，有利于构造高质量的知 识库。上述过程中，专家的作用是主动的、不可低估的。离开了专家的知识库校验和 验证，结果同样可能会有局限性。因为事物的糖确表示在其本身； ( 3 ) 粗糙集的基本理论，如连续属性的离散化、决策表属性的约简等问题都是n p h a r d 难题，目前还缺乏普遍适用的算法。这是制约粗糙集实用化的重要方面： ( 4 ) 粗糙集基本运算的并行算法及硬件实现，将大幅度改善数据开采的效率。已 有的粗糙集软件适用范围还很有限； ( 5 ) 现代信息系统具有分布异构的特点，解决的办法之一是分解：即将用户提出 的全局开采要求分解为不同节点的子数据库开采要求。然后在各个点上单独开采，最 后集成，这可借助a g e n t 技术。粗糙集与多智能体的结合也是一个崭新的课题。 一6 南京航空航天大学硕士学位论文 第一章粗糙集理论基础 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主要思想是从专 家求解过的大量实例中进行分析，保持分类能力不变的基础上，通过知识的约简，导 出问题的决策或分类规则。除了数据本身外，应用粗糙集理论不需要其他的先验背景 知识。更重要的是，它对不确定、不完整和模糊信息也能给出满意的结果。 如今，要解决比较复杂的问题需要大量的知识，以及处理这些知识的机构，以便 针对知识产生答案，然而知识也有难于处理的特性，如知识量很大，很难精确的描述， 知识处于动态变化之中。知识理论各个方面的研究得到了逻辑学、信息工程、系统工 程和人工智能等研究人员的广泛关注。 1 1 粗糙集理论基本概念 1 1 1 论域、知识与等价类n 现已有许多理解、表述和处理知识的方法，由于当涉及到不同领域时知识具有不 同的定义，所以我们只从认知科学的一些观点来理解知识。我们认为知识源于人类以 及其他物种的分类能力这样，在我们的方法中，假设知识是基于对对象的分类能力， 知识直接与真实或抽象世界有关的分类模式联系在一起，称之为论域u 。 假定给定一个我们感兴趣的的对象论域阢对于任何子集x u 可称之为一个u 中的概念或范畴，并且u 的任何概念族称为u 的抽象知识，简称知识。 关于u 的一个划分叮定义为： _ 1 7 = 石，石，疋 h 其中石呈u ，石，z n z = 驴，对于f ，i ，- ，= 1 , 2 ，1 7 ；u z = 以 i 1 【，上的一族划分称为关于u 的一个知识库( k n o w l e d g e b a s e ) 。 设月是u 上的一个等价关系，u r 表示胄的所有等价类，( 或u 上的划分) 构成 的集合；m 。表示包含元素x u 的r 等价类。一个知识库就是一个关系系统j p ( 【，皿) ， 其中【，为非空有限集，是论域，r 是u 上的一族等价关系。 若p g r 且尸吐则n 尸( j p 中所有等价关系的交集) 也是一个等价关系，称为户 上不可区分关系( i n d i s c e r n i b i l i t y ) ，记为i n d ( p ) ，且有 冈= nm 一 。1 r e 声 u i n d ( p ) ( 即等价关系i n d ( p ) 的所有等价类) 表示等价关系族p 相关的知识， 称为k 中关于u 的p 基本知识( 尸基本集) 。为简单起见，我们用u p 代替u i n d ( p ) ， 1 n d ( p ) 的等价类称为知识，的基本概念或基本范畴。特别地，如果g r ，则称q 为 一7 基于粗糙集理论的不确定决策问题的研究与应用 k 中关于u 的q 初等知识，q 的等价类为知识r 的q 初等概念或q 的初等范畴。 定义1 1 ：称s - - - ( u , c u 西为一决策表，其中u 为论域，c 是条件属性集合，d 是决策 属性。 定义1 2 ：称，是信息函数：是u x c u 田v 的映射，y 是各属性的值域， p 圪儿。 粗糙集理论从不可分辨关系和不可分辨类的概念出发，可以从大量的原始数据发 现精简的、概括化的规则，可以得到令人满意地解决问题的方法，本文的分析和计算 就验证了这一点。 1 1 2 粗糙集合逼近 给定一个非空有限的论域u 和u 上的一族等价关系r 将u 划分成互不相交的基 本等价类，给定的知识库k 气u , r ) 构成一个近似空间。对于每一个属于u 的子集z 来研究它们的不可分辨关系为此引入两个精确集合，分别称为上逼近和下逼近，分别 定义如下。 定义1 3 ：集合x 关于胄的下逼近“1 g c 的= 缸卅嘲t 椰 ( 1 1 ) 即当且仅当i x 一x 时，有x r 一。也就是说月代表那些根据现有知识能够 判断肯定属于x 的元素所组成的最大集合。 定义1 4 ：集合x 关于r 的上逼近“1 r 一的= 缸硼扛】- n z 毋 ( 1 2 ) 即当且仅当i x 。f i x ：中时，有工r 一的。尺一代表与z 相交非空的所有等价组 的并集，是可能属于x 的对象所组成的最小集合。显然r 一( 田r 一( 。 由此可见r 一( 的所表示的是精确部分，而r 一( 均所表示的则包含不确定部分，这 就引出了边界区域的概念： b n ( x ) = r c 的一r 一 ( 1 3 ) 边晃区域所包含的是那些不能确定是否属于z 的元素。边界区域是判断精确与不 精确、清晰与不清晰的根据。当b n ( x ) = 中时，则称z 关于r 是清晰的：当 蝴驴时，则称z 关于r 是不清晰的，即z 是关于r 的粗糙集。 1 1 3 评价粗糙集的相关函数 由粗糙集基础理论，可以定义如下四个粗糙集的基础类别“3 r 一中且r 一( 的( ，则z 为粗糙地r 可定义； r 南京航空航天大学硕士学位论文 r c 的= 中且r 一( 的u ，则x 为狭义地r 不可定义： r 一中且r c 的= 阢则z 为广义地r 可定义； r 一= 中且r 一= u ，则x 为全局地r 不可定义。 定义1 5 ：租糙集还可以用逼近精度来度量，逼近精度a 。定义如下：“3 a t ( ) ( ) = 啤一f ，i r 一i ( 1 4 ) 其中闪表示并的基数( e a r d u n a k u t y ) ，对有限集合而言即集合中元素的个数。显然 0 a - ( x ) l ，当d = l 时，z 对盖而言是清晰的，口 o 。 定理1 1 。1 ：设船( ua ，力是一个信息系统，p c = a 。若，妒) = ，“) 且对任意a e p 有 s i g p 们( 口) 0 则p 为a 的一个约简。 1 2 决策表分析基础 如前所述。知识在粗糙集理论中表现为等价关系。设p c a ，a 为属性集，则有： u p = n v a ， ( 1 9 ) “e 尸 对于单属性a 求解等价类，其步骤如下： c l a s s c o u n t = 1 ；1 c l a s s c o u n t 表示分类数的当前值 c l a s s 1 1 = u1 ； c l a s s 为c h a r 型的n * n 二维矩阵 加厂( f - 2 ；f = h ；f 十+ ) 力，( - 1 扩，- c l a s s c o u n t i ，h ) 扳“f ( 口) = = d e s ( c l a s s 阴 1 】) ) 加( 妇2 ；j | _ ”；抖+ ) 飒c l a s s 们 明2 = n u l l ) c l a s s d l 【七】= u i ； b r e a k , ) ) ) e l s e 巩- = c l a s s c o u n o c l a s s c o u n t - h - ； c l a s s c l a s s c o u n t 1 = ug i d e s ( c l a s s j 1 ) 为等价f 类中第_ ，类的取值 构造出一个新类 一 ) 对于多属性求出等价类，可以根据式( 1 9 ) 。并结合单属性求解等价类的程序，从 单属性等价类的并集中得到。 例1 1 ：【，_ a i ，a 2 ，a3 ，a 4 ，a5 , a 6 ，a7 ，a s ，为九个对象的集合c o l o r ，s h a p e ，s i z e 是 属性集c 的属性，等价类的分化如下： u c o l o r = a l ，a3 ) ， a2 ，a 4 ， a 5 ，a 6 ，a7 ，口8 ) u s h a p e = 口l ，a5 ) 口2 ，口6 a 3 ，a 4 ，a7 ，a8 ) ) u s i z e = a l ，a3 ，a4 ，a5 ，a6 ) a 2 ，口7 ，a8 ) 一l o 南京航空航天大学硕士学位论文 u e o l o r , s h a p e , s i z e ) = a d ， a 2 ， a3 ， 口4 ) ， a5 ， 口6 ) ， a7 ，口8 ) ) u c o l o r , s h a p e , s i z e ，的意义是：通过这三种属性，可以辨识前六个对象，而无法 辨识口7 8 。 设u p = 蜀z 2 ，m ，并假设u 的对象随机的分布在尸的等价类中，令 p ( x 3 = i 蜀i | 硼，i = l 2 声， 则p 的熵为： 料- p ( x , ) l 0 9 2 p ( 置)( 1 1 0 ) 熵可以看成为分类粒度的测度：粒度越小，熵值越大，当该属性可以完全辨识所 有的对象时，粒度达到最小，熵值达到最大值l 0 9 2 ( s ) ；相反的，粒度越大，熵值越小， 当该属性完全不能辨识任意的对象时，粒度达到最大，熵值达到最小值0 。例1 1 满足h ( s i z e ) 吠) = 吠v ) ，式中坝“) 嘲v ) 表 示对于va e x , 都满足“) = 烈v ) ，即“和v 在属性4 中的取值相等，_ 表示蕴涵关 系。则称决策属性d 依赖于条件属性子集z 记为x _ d 。可以看出若能找出这样的 属性子集z 使得条件属性相同的对象具有相同的决策属性取值，则由决策表可以获 得完全确定的规则。 z j d 营u x c _ v d ) ，u x 和u 田分别表示由x 和d 导出的等价类。 然而，事实上决策表因存在不一致、噪声、空值( 有些属性值暂时无法获取) 和 测量误差等原因，难以满足上述条件，因而决策属性和条件属性之间存在着一定程度 的不一致性，获得的规则可信度往往小于l 。 对于vx c c ，x 和决策属性d 之间的依赖度嘲：k - 坚笔尝型 i ul 从依赖度的定义可以看出，k 越大，z 对d 的依赖性就越强，从而可以说得到的 规则确定性也就越大。但k 只能反映出z 对d 的确定性的依赖程度。然而，决策属性 和条件属性之间却存在着一些不确定的依赖关系。 基于粗糙集理论的不确定决策问题的研究与应用 对于v e m 田，尸c ，可信度昕( 驴留，。晦l ，表示对于每一个决 策类能被p 识别的程度，l l p 规则的不确定程度。 若可以获得完全规则，即u x c _ u , o ，其中x c _ c ，则诉( 功= l 。 同样的，若将决策属性作为规则的前件，将条件属性作为规则的后件，即结论， 则： 若d j x 其可信度为：蛎。哥 1 4 本章小结 基于粗糙集理论，从决策表中挖掘知识，是克服知识获取瓶颈的有效途径，其实 质是一种从实例中获取规则的归纳学习方法。归纳学习是从有限的、不完全的的例子 中获取概念和规则。 本章对粗糙集理论的几个基本问题进行了讨论，为后续章节的深入研究提供了基 础。 1 2 南京航空航天大学硕士学位论文 第二章粗糙集理论在决策树优化中的应用 2 1 粗糙集和决策树 通过对决策表的约简和提取，我们可以获取规则或决策树，与规则相比，决策树 更加直观、更容易理解。决策树的建树方法通常是采用自顶向下的方式，其基本思想 是：根据某种度量准则选择最优的属性或属性组合，然后用它来区分样本，得到相应 的分支。并将上述归纳步骤应用于各个分支节点上，直至将所有的样本都区分开来。 在各种决策树的建树方法中，比较有影响的是q u i n l a n 提出的1 1 ) 3 “1 。它用信息增 益作为在各级非叶节点上选择节点的标准，获得样本集最大的类别信息。这种方法虽 然简单实用，但是不能使所建立的决策树达到最优，即所建决策树的节点数不一定最 少。在这个问题上，jr h o n g 已经证明它是一个n p 一 i a r d 问题。1 。 粗糙集理论从新的视角认识知识，把知识和分类密切的连系在一起，为处理不确 定、不完全的数据分类提供了更加符合入类思维方式的数学工具。该理论目前主要是 应用于知识的约简和知识依赖性的分析。下面将采用粗糙集理论来建立决策树的方 法。这种方法不但属性之间的依赖关系，还兼顾了决策树的节点数量，系分类的种数。 对于决策表s - - ( t z , c ud ) ，p o s c ( c o 是u 中所有的通过知识c 肯定被归为u d 类的元 素所组成的集合。若c 和d 分别为条件属性和决策属性，则表示c 和d 之间的依赖 关系。l p o s c ( c o i 越大，说明依赖程度就越强，即决策属性d 从条件属性c 说得到的信 息量就越大，这就说明属性之间的互信息量与i p o s c ( a r ) l 有关，成正比关系。 定义2 1 ：设有离散属性a 、b ，a 从曰中所获得的互信息量为： ，口j 回= h c m ) - h ( a b ) ( 2 1 ) 一方面，若b p g c ，且p _ d 时，由式( 1 1 0 ) 可得： 设p = 墨义2 ，芦。)u d = - y 1 ，y 2 ，】，。) 因为尸d ，可知野或蜀n 】产，其中i - - i ，2 ，产1 ，2 ，用因此有： 烈弓胁单掣：l 或烈巧鼢：o i i 从而 觑磷p ) = p ( x ，) p ( 巧i z ) l o g ：p ( 一ix ) 2 0 ， ， 再由式( 2 1 ) ，可知埘d 钡西c ) 叫敢力，此m t m s c ( c o = u ，决策属性d 从条件属性 c 中所获得的互信息量达到最大值。 另一方面，若p o s d , o c _ 以且i p o s c ( d ) l o ，曩才力咄才c ) 0 ，且p o