（计算机应用技术专业论文）基于粗集的决策信息系统不确定性研究.pdf

摘要 决策信息系统是处理大量数据以获取有效决策，并应用于各个领 域的信息系统模型。决策信息系统中包含的不确定性对决策规则的产 生、有效决策的生成具有重大影响。而粗糙集理论作为一种处理不完 全、不精确及不确定数据的有效方法，在数据挖掘领域发挥了重要作 用并具有巨大的应用潜力。因此，利用粗糙集理论来研究决策信息系 统的不确定性具有重要的现实意义。 文章采用粗糙集数据分析方法，具体分析了决策信息系统的整体 不确定性，包括对决策信息系统随机性和不一致性的具体描述，产生 不确定性的原因分析，不确定性变化受决策表粒度变化的影响等。针 对决策信息系统不确定性的度量指标问题，分析了现有度量方法的适 用性与局限性，并且从粗糙集理论的代数论观点和信息论观点两种角 度加以阐述。对决策规则的不确定性度量函数也进行了研究分析。 同时，分析研究了属性约简对决策信息系统不确定性变化的影 响。属性约简过程中，决策表的粒度变化引起了决策表整体不确定性 的变化。提出了平均条件等价类粒度、整体平均粒度等概念，用来研 究分析决策表的随机性与不一致性。 此外，针对现有分辨矩阵存在的问题，文章定义了一种新的规则 分辨矩阵，并将其应用于求信息论观点下的核属性与约简簇中。此规 则矩阵具有以下优越性：相对原对象分辨矩阵存储空间减小；可用来 求不一致性决策表在信息论观点下的约简与核；启发式约简必须计算 所有属性的属性重要度，且只能得到部分约简，利用规则分辨矩阵能 得到整个约简簇。并且，此规则分辨矩阵对度量约简造成的决策信息 系统不确定性的变化，以及比较同一决策信息系统不同约简的不确定 性程度具有重要作用。 关键词粗糙集，决策信息系统，不确定性，分辨矩阵 a b s t r a c t d e c i s i o ni n f o r m a t i o ns y s t e mi s a s y s t e m ，w h i c hh a sm a n ya p p l i c a t i o n si n g r e a t d e a lo fd a t at oo b t a i ne f f e c t i v e i n f o r m a t i o ns y s t e mh a sg r e a ti n f l u e n c e k i n do fm o d e lo fi n f e l r m a t i o n v a r i o u sf i e l d si nd e a l i n gw i t ha r u l e s u n c e r t a i n t yi nd e c i s i o n u p o np r o d u c i n gd e c i s i o n r u l e s a n dm a k i n ge f f e c t i v ed e c i s i o n a n da sa ne f f e c t i v em e t h o do fs o l v i n g i n c o m p l e t e ，i m p r e c i s ea n du n c e r t a i nd a t a ，r o u g h s e tt h e o r yh a sb e e n p l a y i n gav e r ys i g n i f i c a n tr o l e i nt h ed a t am i n i n gf i e l d ，a n dh a sh u g e a p p l i c a t i o np o t e n t i a l s oi t m a k e sv e r yi m p o r t a n tp r a c t i c a ls e n s et od o r e s e a r c ho nu n c e r t a i n t yo fd e c i s i o ni n f o r m a t i o ns y s t e mb yr e f e r r i n gt o r o u g hs e tt h e o r y d e p e n d i n g o n r o u g h s e td a t a a n a l y s i s ，t h e t h e s i s a n a l y s e s t h e u n c e r t a i n t vo fd e c i s i o ni n f o r m a t i o ns y s t e mi nd e t a i l i ti n c l u d e ss p e c i f i c d e s c r i p t i o no fr a n d o m i c i t ya n d i n c o n s i s t e n c yo fd e c i s i o ni n f o r m a t i o n s y s t e m ，t h ea n a l y s i so ft h e r e a s o nf o rp r o d u c i n gu n c e r t a i n t y , a n dt h e i n f l u e n c eo ft h eg r a n u l a r i t yo fd e c i s i o nt a b l eo nt h ev a r i e t yo fu n c e r t a i n t y a n ds oo n a i m i n ga tt h ep r o b l e mo fm e a s u r e m e n tg u i d el i n e ，i ta l s o a n a l v s e st h ea p p l i c a b i l i t ya n dr e s t r i c t i o no fe x i s t i n gm e t h o d s ，i l l u s t r a t e d f r o mb o t ha s p e c t so fa l g e b r aa n di n f o r m a t i o np o i n t so fv i e wo fr o u 曲s e t t h e o r y i na d d i t i o n ，t h em e a s u r e m e n to fu n c e r t a i n t yo fd e c i s l o nr u i e s 1 s r e s e a r c h e da n da n a l y s e d a tt h es a m et i m e ，t h et h e s i sd o e sr e s e a r c ho nt h e i n f l u e n c eo t a t t r i b u t er e d u c t i o no nt h ev a r i e t yo fu n c e r t a i n t yo fd e c i s i o ni n f o r m a t i o n s y s t e m i nt h ec o u r s eo fa t t r i b u t er e d u c t i o n ，t h ev a r i e t yo fg r a n u l a r i t yo f d e c i s i o nt a b l eb r i n g st h ev a r i e t yo fh o l i s t i cu n c e r t a i n t yo f d e c i s i o nt a b l e i na d d i t i o n ，a v e r a g ec o n d i t i o ne q u i v a l e n c ec l a s sg r a n u l a r i t ya n di n t e g e r a v e r a g eg r a n u l a r i t yc o n c e p ta r ep u tf o r w a r d t h e ya r e u s e df o ra n a l y z i n g t h er a n d o m i c i t ya n di n c o n s i s t e n c yo fd e c i s i o nt a b l e f u r t h e m l o r e i no r d e rt os o l v et h ep r o b l e m so fe x i s t i n gd i s c e r n i b i l i t y m a t r i x an e wr u l ed i s c e m i b i l i t ym a t r i xi s d e f i n e da n di sa p p l i e dt o c o r e p u t ec o r ea t t r i b u t ea n dr e d u c t i o n su n d e r t h ev i e w p o i n to fi n f o r m a t i o n l l t h i sr u l ed i s c e r n i b i l i t ym a t r i x h a st h e s ea d v a n t a g e sw h e nt h es t o r a g e s p a c eo fr u l ed i s c e r n i b i l i t ym a t r i xi ss m a l l e rt h a no b j e c td i s c e r n i b i l i t y m a t r i x ；w h e nr e d u c t i o na n dc o r ea t t r i b u t ei nt h ei n f o r m a t i o nv i e w p o i n t c a n tb ef i g u r e do u ta c c o r d i n gt ot h eo b j e c td i s c e r n i b i l i t ym a t r i xa n d w h e nh e u r i s t i cr e d u c t i o nn e e d sc o m p u t ea t t r i b u t es i g n i f i c a n c e ，w h i l eo n l y p a v i a lr e d u c t i o n sc o u l db eo b t a i n e db u tr u l ed i s c e r n i b i l i t ym a t r i xc a ng e t i n t e g r a t e do n e s b e s i d e s ，i ti sh i g h l ys i g n i f i c a n tf o rm e a s u r i n gt h ev a r i e t y o fu n c e r t a i n t yo fd e c i s i o ni n f o r m a t i o ns y s t e mc a u s e db ya t t r i b u t e r e d u c t i o n ，a n dc o m p a r i n g t h e d e g r e e o f u n c e r t a i n t y o fd i f f e r e n t r e d u c t i o n sw i t ht h es a m ed e c i s i o nt a b l e k e yw o r d s r o u g hs e t ，d e c i s i o ni n f o r m a t i o ns y s t e m ，u n c e r t a i n t y , d i s c e r n i b i l i t ym a t r i x i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特另, j d i j 以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在在论文中作了明确的说明。 作者签名： 夸嘉 日期：丛年上月上日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：查盘导师签名：玉壶! 豳日期：碰年月丝日 硕士学位沦文第一章绪论 第一章绪论 粗糙集理论是在模糊集理论之后产生的又一区别于经典集合概念的新集合 理论，它的产生为处理不完整性和不确定性的问题提供了新的工具。本章主要介 绍了粗糙集理论提出的背景，自身的特点；粗糙集的理论研究方向和应用研究方 向；粗糙集模型在数据挖掘中的应用；不确定性的研究现状和发展前景。最后简 要给出了本文的研究基础和研究内容结构。 1 1 粗糙集理论的产生及发展方向 1 1 1 粗糙集理论的产生 2 0 世纪6 0 年代初，l a z a d e h 提出了模糊集理论( f u z z ys e t t h e o r i e s ) 1 , 2 1 ， 给出了模糊集隶属函数和模糊逻辑中算子的概念，以此解决全域上的一些个体既 不能在其任一个子集上被分类也不能在该子集的补集上被分类的问题。但是由于 模糊集没有给出数学公式描述，无法计算出它的边界线上的具体的含糊元素数 目。 1 9 8 2 年波兰学者z p a w l a k 提出了粗糙集理论( r o u g hs e tt h e o r i e s ) 1 3 - 5 1 ，把 那些无法确认的个体归于边界区域，在此思想下定义了上近似集和下近似集，将 边界区域定义为上下近似集之差集。上近似集和下近似集都可以通过等价关系给 出确定的数学公式描述，所以“不能确定归属到任一个集合的个体数目”可以被 计算出来，粗糙集从而成为一种处理不完整性和不确定性的软计算工具【6 。”。 1 9 9 1 年p a w l a kz 出版专著，系统全面地阐述了粗糙集理论，为粗糙集理论 研究奠定了严密的数学基础。1 9 9 2 年他又出版了粗糙集理论应用专集，总结了 这一时期粗糙集理论与实践的研究成果，促进了粗糙集理论的进一步发展。 粗糙集理论的特点是通过不可分辨关系对论域进行划分，用一对近似集合对 给定概念进行逼近，从而得出粗糙的概念表示形式。由此看来，粗糙集可以用来 处理不分明问题，并能通过分析各种不完备信息从中发现隐含的知识、揭示潜在 的规律。它具有处理不精确、不一致、不完整等不完全信息或知识的能力，或依 据观察、度量到的某些不精确的结果而进行分类数据的能力。随着粗糙集理论的 不断完善发展，产生了基于粗糙集的数据分析方法( r o u g hs e td a t aa n a l y s i s ) ， 它的基本出发点是从数据的结构上获取尽可能多的信息，也就是根据数据本身做 出推测，是一种有效的分析不确定性信息的方法。 硕十学位沦文第一章绪论 1 1 2 粗糙集理论的研究方向 粗糙集理论自产生以来，学术界一直对其十分关注，近年来粗糙集理论及其 应用快速发展。目前国际上已经成立了粗糙集学术研究会，来自波兰、美国、加 拿大、日本、挪威、俄罗斯、乌克兰和印度等国家的学者成为其会员，不断进行 合作研究。1 9 9 2 年至今，每年都召开了以粗糙集为主题的国际会议，参会人员 均系本学科领域的世界级科学家和研究人员。国际会议的召开有益于促进学术研 究的国际交流，对本领域的新思想新课题的产生发展也提供了有利条件，进一步 推动了粗糙集理论的拓展和应用。目前，粗糙集理论与诸如模糊集、粒计算、神 经网络、遗传算法等其他软计算机理论，已成为国内外计算机及相关专业的研究 热点，引起了越来越多的科研人员的关注。 目前，粗糙集的理论研究方向主要有数学性质、模型拓展、有效算法和智能 分析方法融合等。粗糙集在数学性质方面的研究主要是对其理论中知识的不确定 性问题进行理论研究，包括其代数结构、拓扑结构、粗糙逻辑和粗糙集收敛性等 问题。粗糙集在模型拓展方面的研究包括可变精度模型( v p r s ) 、相似模型和连 续属性离散化模型，主要解决数据分析时遇到数据噪声、数据不完备和连续数据 离散化等问题。粗糙集在有效性算法方面的研究主要集中在下面几个方面：约简 的启发式算法、粗糙集基本运算的并行算法、导出规则的增量式算法、大数据集 中的粗糙集计算实现。粗糙集与其他智能分析方法的融合可以取长补短以实现不 同的应用目的，如r o u g hs e t 与f u z z ys e t 理论、神经网络、遗传算法、证据理 论、专家系统、b a y e s 理论、概率统计理论等智能理论的结合。 粗糙集的应用研究可分为两大类：有决策的分析和无决策的分析。有决策的 分析主要包括监督学习和决策分析；无决策的分析主要是数据压缩、化简、聚类、 机器学习和模式发现等。粗糙集应用于有决策的分析可获取规则，对学习的训练 集作预处理，应用决策不完全时的学习，进行增量式学习。无决策分析主要是属 性约简，以此来压缩数据和进行数据的聚类分析。在大型数据库中的知识发现是 粗糙集应用的典型。 当前发表在国际重要期刊、国际重要会议刊物和国内知名刊物的粗糙集方面 的研究论文同益增多。粗糙集理论的应用也变得十分广泛，已成功应用于专家系 统、人工神经元网络、知识发现、粗糙控制、医疗诊断、冲突分析、模式识别、 人工智能等领域。这说明粗糙集无论是在理论研究还是在应用研究方面都有了突 飞猛进的发展，粗糙集作为一个研究方向已经受到学术界充分的重视。 硕士学位论文第一章绪论 1 2 不确定性问题和决策信息系统不确定性的研究现状 1 2 1 不确定性问题的研究现状 利用一般的数据挖掘方法对知识进行挖掘，要求具有相同描述信息的对象属 于同一概念i l “。但是现实世界中人们所面对的数据源本身存在各种不确定性， 这种不确定性来自人类的主观认识与客观实际之间存在的差异【1 3 1 。事物发生的 随机性、人类知识的不完全、不可靠、不精确和不一致以及自然语言中存在的模 糊性和歧义性，都反映了这种差异，都会带来不确定性。不确定性的存在造成了 具有相同描述信息的对象可能属于不同概念，怎样解决不确定性问题受到研究者 的广泛关注。 在人工智能领域，研究者们提出了许多处理不确定性问题的方法【1 4 “】。在数 据挖掘中应用最广泛的是贝叶斯网络( b n n ) 、证据理论、模糊集和粗糙集。 较早期，b n n 主要在专家系统中用来表述不确定的专家知识。九十年代以 来，b n n 的研究有了较大进展，在专家系统、决策支持系统开发中得到成功应 用【2 2 ”j 。b n n 用概率测度的权重来描述数据间的相关性，从而解决数据间的不 一致性，因此可用来处理不完整和带有噪音的数据集。利用贝叶斯网络进行数据 挖掘面临的主要问题是需要先验知识。当变量增多时，可能的网络结构成倍的增 长，不可能对所有的网络结构进行计算。因此必须在现有的知识下进行网络选择， 这在很大程度上依赖于专家知识。 证据理论( e v i d e n c et h e o r y ) f 2 4 - 2 6 1 弓i 进信任函数的概念，对经典概率加以推 广。利用信任函数，人们无需给出具体的概率值，只需要根据已有的领域知识就 能对事件的概率分布加以约束。证据理论满足比概率论更弱的公理系统，当概率 值已知时，证据理论就变成了概率理论。近年来证据理论逐步引起人们的注意， 出现了一些更深入的研究成果和实用系统。 z a d e h 提出的模糊集( f u z z ys e t s ) 理论为解决由模糊概念引起的不确定问 题提供了一种有效的方法。现实世界中存在一些模糊概念，如“温暖”、“凉快”、 “冷”，这些模糊概念所描述的对象的界限往往不是很清晰，因而无法确定一些 对象属于哪个概念，可见经典集合论已经无法解决此类问题。在模糊集理论中可 用隶属函数定量的描述模糊概念，隶属函数值反映了对象隶属于某个概念的程 度。隶属函数的值域是 0 ，1 ，如果隶属函数值只取0 或1 ，那么模糊集就特化 为经典集合。模糊集理论在专家系统、自动控制领域中应用比较广泛，模糊数据 分析技术如模糊聚类、语言概括及模糊规则发现等也能用于数据挖掘中。模糊集 理论用于数据挖掘的困难在于隶属函数的选择以及计算的复杂性。 无论是贝叶斯网络、证据理论还是模糊集理论，在应用中都离不开专家知识。 第一章绪论 贝叶斯网络的先验概率、证据理论的概率分配函数、模糊集的隶属函数都要依靠 领域专家的知识，这不仅给应用带来不便，同时个人偏好也会直接影响所发现的 规则。 粗糙集理论在过去的十几年里引起了多个领域的关注【2 “”】。粗糙集理论反映 了人们以不完全信息或知识去处理一些不可分辨现象的能力，或依据观察、度量 到的某些不精确结果进行分类数据的能力。粗糙集的提出为处理模糊信息系统或 不确定性问题提供了一种新型数学工具，是对其它处理不确定性问题理论如概率 理论、证据理论、模糊集理论等的一种补充。在粗糙集理论中，知识是主体对论 域中的客体进行分类的能力，分类能力越强，主体所具备知识的可靠度越高。与 其他处理不确定性问题的方法相比，粗糙集方法的优点之一是可以不依靠任何专 家知识挖掘数据中隐藏的模式。 1 2 2 决策信息系统不确定性的研究 决策信息系统的不确定性直观的来说就是在决策表中根据相同的条件属性 值所得到的决策属性值不唯一。决策信息系统中存在的不确定性使得通过决策信 息系统获得的决策产生冲突。目前，对决策信息系统中存在的不确定现象，研究 者们都予以了重视。基于粗糙集的决策信息系统不确定性研究主要集中于产生不 确定性的原因以及不确定性的变化情况，度量不确定性的指标这几个方面。 在知识信息收集的过程中，由于测量受噪声影响不准确或者人为纪录的偏 差，可能会造成在此基础上得到的决策信息系统出现不确定性问题。另外，为了 消除决策信息系统中存在的冗余信息，在对决策表进行约简的过程中也可能产生 新的不确定性情况。 在知识约简的过程中，知识的粒度具有增大的趋势，知识越粗糙决策信息系 统中可能存在的不确定性越大。 目前对于如何度量决策信息系统不确定性的研究，学者们提出了各种度量指 标，其中比较经典的度量指标是代数论观点下的近似度r 和信息论观点下的信息 熵。 1 3 论文的背景及研究内容 1 3 1 论文的研究基础和目的 在进行论文的撰写工作之前阅读了大量相关中外文献，深入了解了粗糙集的 研究内容，具有扎实的粗糙集理论基础。通过对中英文文献的广泛阅读及研究， 具体分析了决策信息系统不确定性产生的原因，描述了各种不确定性的体现，分 硕士学位论文第一章绪论 析比较了各种衡量指标，并在理论上分析了每利叼：确定性的度量函数的应用原理 及其优缺点。在此基础上进一步研究了决策表的不确定性度量方法和决策规则的 不确定性度量方法。决策表的整体不确定性反映了决策表的整体冲突情况。决策 规则的不确定性度量则是针对单条规则不确定性的描述。 在数据预测中使用的大多数统计学方法，比如不一致分析法、回归分析法、 相关性分析法，都需要人为地额外指定参数。应用粗糙集数据分析方法( r s d a ) 衡量决策表信息系统的不确定性，克服了这一弊端，在预测的过程中仅使用了内 部知识，即数据的粒度结构信息( 粒度在此表示为某种等价关系形成的等价类的 数目) 。由于不需要人为地指定参数或先验模型的假设，所有预测的依据的来源 于数据样本本身：这样就减少了预测中的主观因素。 本文的研究目的在于：( 1 ) 分析各种影响不确定性的因素；( 2 ) 分析比较各 种决策信息系统不确定性的度量方法，比较各种度量函数的优劣；( 3 ) 分析不确 定性对决策规则的影响，对决策规则的不确定性的研究有助于后续的数据融合技 术的研究。如多规则选择问题，单个或多个决策表的数据融合。 1 3 2 论文研究的主要内容结构 本文围绕决策信息系统的不确定性问题进行研究探讨，介绍了各种不确定性 度量方法及其各自的适用环境，以及不确定性情况下规则的获取策略。并对粗糙 集属性约简过程中决策表的不确定性变化提出了自己的看法，就规则分辨矩阵也 进行了研究。本文的内容结构如下： 第一章：绪论。主要介绍了粗糙集的研究现状及发展前景，不确定性问题的 研究背景，论文的研究基础、内容和目的。 第二章：粗糙集理论基础。介绍粗糙集的有关基本概念，包括近似空间、信 息系统以及约简。 第三章：决策信息系统的不确定性。对决策信息系统的不确定性问题进行了 具体阐述，描述了不确定性的含义并分析了产生不确定性的主要原因，并且说明 了决策系信息系统不确定性的度量方法。 第四章：属性约简中决策信息系统不确定性变化。着重围绕粗糙集属性约简 的过程进行分析，从粒度变化等方面入手研究决策信息系统在这一过程中不确定 性的变化趋势，以及各种度量指标的变化。 第五章：规则分辨矩阵研究。在目前已存在的对象分辨矩阵基础上提出了规 则分辨矩阵的定义，并对其在求约简、属性核以及决策表不确定性体现几个方面 的应用。 第六章：总结与展望。本章对全文的工作进行了总结，并给出以后的研究工 硕：l ：学位论文第一章绪论 作展望。 1 4 本章小节 本章简要阐述了z p a w l a k 提出的粗糙集理论产生的背景。粗糙集理论具有 的处理不精确、不一致、不完整等不完全信息或知识的特点。粗糙集的理论研究 方向主要有数学性质、模型拓展、有效算法和智能分析方法融合；应用研究方向 主要是监督学习、决策分析、数据压缩、化简、聚类、机器学习和模式发现。在 人工智能领域，研究者们提出了许多处理不确定性问题的方法，粗糙集方法的提 出为处理模糊信息系统或不确定性问题提供了一种新型数学工具。在对决策信息 系统的不确定性问题的研究方面，粗糙集理论也发挥了重要作用。本章最后给出 了本文的研究基础并简要介绍了六章的内容结构。 硕二 学位论文第二章粗糙集理论基础 第二章粗糙集理论基础 粗糙集理论中的很多概念在后续的行文中需要用到，本章主要就这些基本概 念进行简单介绍。近似空间是粗糙集理论的一个重要概念，也是其他概念阐述的 基础，它包括一个非空有限集合和一个等价关系。在此基础上产生了上下近似集 合的概念，是集合的粗糙描述。信息系统是基于粗糙集的数据分析方法( r s d a ) 的研究基础，它由研究的所有对象组成，对象的信息通过对象的基本特征( 属性) 和特征值( 属性值) 来描述。不可分辨关系是指信息系统中某些对象不可区分， 存在于一个等价类中。属性约简是粗糙集理论的一个重要研究方向，可以通过对 知识进行约简来去除信息系统中的冗余信息。 2 1 近似空间 2 1 1 上、下近似集合 “近似空间”是粗糙集理论中最基本的概念，在此基础上产生的上、下近似 集合是有别于经典集合的描述。 定义2 1 给定一个非空有限集合从r 是u 上的一个自反的、传递的、对称 的二元关系，即为一个等价关系，n 是一个近似空间。等价关系r 在u 上的划分表示为u r 或j d r ，它是全域为u 的非空的、两两互不相交的子集组成 的子集族。吩中包含对象a 的等价类的形式为r 。= 6 u ：a r b 。 在粗糙集理论中，对于论域u 中的对象已有的知识是根据等价关系r 划分 的等价类中包含着哪些对象。因此对于论域( ，中的一个子集兄能得知的仅局限 于等价关系r 对应的等价类以及这些等价类构成的集合。为了用已知的等价类 来描述子集z 给出下面两个精确集的定义。 定义2 2 对于x u 集合x 的r 下近似集定义为邑= u y p r ：y 玛， 上近似集定义为牙。= u y e p r ：y n ，集合的r 边界区域定义为 口v = 只一邑) ，确定区域定义为量u 一最。 墨表示u 中所有根据等价关系r 一定能归类到集合x 的对象的最大集合， j 。表示u 中所有根据等价关系月可能归类到x 的对象的最小集合。b n ( x ) 表示 u 中无法精确归类到或一x ( x 的补集) 的对象集；确定区域中的对象，要么 完全属于x ，要么定不在x 中。b n ( x ) 为空则称关于r 是清晰的，反之则称 是关于r 的粗糙集。图2 一l 为上述概念的示意图。 硕士学位论文 第二章粗糙集理论基础 图2 - 1 粗糙集概念示意图 例2 1 近似空n ，论域，- 扛l ，x 2 ，x 3 ，x 4 ，x 5 ，x 6 ，x 7 ，x 8 ) ，u r = x l ， x 2 ，x 3 ) ，x 5 ) ， x 6 ，x 7 ，x s ，集合x ，y cu ，片锄，x 3 ) ，仁 x 5 ，x 6 ，x 7 ) 。 集合在u 上的r 下近似集为蚤= 缸l ，x 2 ，均) ，上近似集为丘= 扛l ，x 2 ，x 3 ) ； 集合y 在u 上的r 下近似集品为，上近似集为露= ，x 5 ，x 6 ，x 7 ，x 8 。 2 1 2 近似度 近似空间的近似程度( 或者称为粗糙程度) 可以用近似度来衡量。 定义2 3 近似空间 的近似度为 f 。：堕昝型( 舴巩 f 一2 可丁一 ( 舴u ) 。 冈表示集合x 中包含的元素数目。fr ( 是u 中对象根据等价关系r 能否 被f 确分类到等价类x 中的量度。如果近似度为1 ，则表示集合爿在u 上是精 确定义的；如果o 月( 1 ，则表示集合x 在u 上是粗糙定义的。近似度的 数值反映了在等价关系r 下集合x 在论域u 上的粗糙程度，_ r c 确越小则x 的 粗糙程度越大。 例2 2 沿用例2 1 的近似空间 ，扎y cu ，近似度“尺= 坚掣 = 等乩蹦y ) = 等掣= 孚一s 。 l 硕士学位论文第二章粗糙集理沧基础 2 2 信息系统和不可分辨关系 2 2 1 决策信息系统和决策表 信息系统是基于粗糙集的数据分析方法( r s d a ) 的研究基础，它由研究的 所有对象组成，对象的信息通过对象的基本特征( 属性) 和特征值( 属性值) 来 描述。 定义2 4 信息系统卢( u ，q ，石) ，u 是非空有限对象论域，q 是属性 的非空有限集合，是属性q q 的值域，石：u 一是论域u 到值域的信息 函数。 其中q 是全部属性的集合，但在某些情况下对象的属性中有些是关于条件 的信息，有些是关于决策的信息，这两种属性对对象的描述是不同的两个方面。 如果所有属性进一步划分为条件属性集与决策属性集，那么这种信息系统可称为 决策信息系统。 定义25 决策信息系统肛( u ，q - = c u d ，v ，) ，论域【，_ 扛l ，x 2 ，羽明 ， l 卅表示u 中包含对象的数目，c 和d 分别为条件属性集和决策属性集，v 是属 性的值域，厂u v 是论域u 到值域v 的信息函数，表示u 中每个对象的属性 值。 在决策信息系统中，通常可以将多个决策属性根据其值的分布重新定义为单 个决策属性，即d = f 讲。 由于信息系统一般以表的方式描述，所以决策信息系统也可称为决策表。一 般情况下，决策表第一列是对象名，最后一列是决策属性，中间列是条件属性。 决策表的一行是对论域中一个对象条件属性值和决策属性值的描述，一列是对象 的某个属性( 包括条件属性和决策属性) 在值域中的取值。 决策信息系统乒( u ，q e c u d ，v ，) ，论域l ，- 扛l ，x 2 ，如) ，i m = 月， q - ：c u d 是属性集，c “l ，a 2 ，a 3 ，a k 为条件属性集，d = 田为决策属性 集，其一般形式如表2 1 所示： 表2 - 1 决策表的一般形式 cd u a 1a 2 a k d x ia 1 ia 2 1 a k l d l x 2a 1 26 1 2 2 a k 2 如 a l na 2 月a h巩 硕士学位论文第二二章粗糙集理论基础 决策表中的对象既具有条件属性值又具有决策属性值，两者间存在对应关 系。粗糙集数据分析法将这种关系符号化为规则的形式，c 表示条件属性集，d d 是一个决策属性，那么决策表规则的形式为 会，2 j x d 2 m d i x 4 m 。2 。v x d 2 m 。k 。 x 9 = 表示对象x 的条件属性q 的取值为m 。，x d 表示对象x 的决策属性d 的 取值，研：表示对象x 的决策属性d 的第k 种取值情况。例如：a l = d i l 八a 2 = d 2 2 八 a k = a k l j d = - d l 。 2 2 2 不可分辨关系 粗糙集理论认为知识是一种分类能力，表现为知识具有粒度性，知识的基础 是事物之间的不可分辨关系。不可分辨关系说明根据目前已有的知识，某些对象 是等价的，他们之间不可区分。不可分辨关系在信息系统中的定义如下。 定义2 6 信息系统卢( u ，q ，石) ，集合s cu ，属性集b c a ，对象v x ， y e s ，如果v q b ，使得0 ) = ，那么就定义为b 上的不可分辨关系， 表示为月旷 ，力：石0 ) 萌o ) ，v q e b ，也称为等价关系。集合s 定义为包含对 象x 的曰上的等价类，表示为r 口0 ) 或m 口。 在决策信息系统s = - ( u ，q t c u d ，v ，) 中，存在的由属性值划分的不可 分辨关系主要有条件等价关系，决策等价关系和规则等价关系。 定义2 7 条件属性集c 在论域u 上的划分p c = 蜀，地，) ，疋p c 为条件等价类；决策属性集d 在论域u 上的划分= y l ，y 2 ，) ，巧p a 为决策等价类；所有属性集q 在论域u 上的划分p q = z i ，z 2 ，z a , ) ，z k p q 为规则等价类。 2 3 信息系统中的约简 粗糙集理论将分类与知识联系在一起，使用等价关系来形式地表示知识分 类，知识被视作对研究对象的分类能力。然而并不是所有的知识都是必需的，可 以通过对知识进行约简来去除冗余信息。 在信息系统中存在大量的冗余知识，这些冗余知识影响了人们对于信息系统 的认识和利用。并且，随着全球信息数量飞速增长，信息系统和数据库中信息不 断膨胀。信息系统中信息增长主要有两个方向：横向增长和纵向增长。横向增长 是指对象属性数目的不断增加，纵向增长是指对象记录数目的增加。这些信息并 不都是必需的，在粗糙集理论中对于信息系统横向的约简称之为属性约简，纵向 0 硕士学位论文第二章粗糙集理论基础 的约简称之为属性值约简。信息系统中的属性并不是同等重要的，有些是冗余属 性，不能给决策表中的对象提供任何有用的附加信息。属性约简就是指在保持信 息系统分类能力不变的基础上，删除冗余或者可忽略的属性。 约简后的属性集称作属性约简集，约简集通常不唯一，找到一个决策表的所 有约简集是一个n p h a r d 问题。 从定义上来说，决策表的核属性是该决策表所有约简集的交集，即所有约简 集都包含的条件属性的集合。如果根据定义来求核，就必须先求出决策表的所有 约简集，再通过求交集求得核。这种方法计算复杂度大，并且求出的核对约简已 经失去了指导意义。因此目前常用的求核方法很少直接从定义着手，而是从其它 角度进行求核，例如：分辨矩阵求核、属性重要性求核方法。 2 4 本章小节 本章简要介绍了粗糙集理论的基础概念。近似空间和上下近似集是粗糙集理 论的基础概念，是对集合的粗糙描述。信息系统一般用表的形式描述，利用属性 与属性值来描述对象。信息系统中某些对象从属性与属性值上看是不可区分的， 存在于一个等价类中，它们之间存在不可分辨关系。信息的迅速增长导致信息系 统中对象数目的不断膨胀，属性约简就是在保持信息系统分类能力不变的基础上 删除决策表中冗余或者可忽略的属性。 硕士学位论文第三章决策信息系统的不确定性 第三章决策信息系统的不确定性 本章主要介绍决策信息系统不确定性的含义，如何用粗糙集理论来描述决策 信息系统的不确定性，分析产生不确定性的原因。度量决策信息系统的不确定性 存在哪几种方法，各个度量指标的优劣的比较。代数论观点与信息论观点中，对 于决策信息系统不确定性的定义与度量方法不同，比较这两者的差异。决策规则 的不确定性度量指标主要有支持度、置信度和覆盖度，三者之间存在一定的转换 关系。 3 1 决策信息系统不确定性描述 3 1 1 一致性和不一致性决策表 现在用粗糙集的形式来表示决策表中的规则集。根据定义2 7 ，由条件属性 等价关系心划分的等价类为五，由决策属性等价关系r a 划分的等价类为，延 续2 1 节中上下近似集的定义，e 至u 通过等价关系心定义的上近似集为 f 。= x u ：r c ( x ) n r a ) ， 下近似集为 e 。= x u ：r c ( x ) sy 。 定义3 1c d p c 乃为由c 到d 的粗糙规则集合，实际上为一组二元关 系 墨，l 户c d f 。为某条件等价类，巧为某决策等价类，p c x p d 表示条件等价类和决策等价类的笛卡尔积。由粗糙集的定义有西矿。当且仅当 ny 。o 当且仅当x ny r a 成立，因此有 c d 甘出n 巧o 。 c d 称为一条规则，可表示为西一只。 定义3 2 规则x 一巧，若 女，使得x 一致成立( 1 f n ，1 ，女m ) ， 则称石一蚱为不一致性规则，反之为一致性规则。 由于存在一致性规则和不一致性规则，于是产生了下面相对应的一致性决策 表和不一致性决策表的定义。 定义3 _ 3 决策表s - - ( u ，o = c u d ，v ，) ，如果v x ，_ y u ，都有0 ) = f a ( y ) ，v 珂 c ) j 一u r ，即当属性集月在u 上的划分是丁在u 上的划分的 细分时，信息熵1 4 ( d 1 4 ( 月) 。所以，信息熵( r ) 反映了属性集r 在u 上形成的 等价类的粒度，在细分关系成立的前提下等价类粒度越大对应的信息熵越小。 性质3 2 若划分u r = 口l ，a 2 ，a x ) 中等价类的数目一定，当p ( a 1 ) = j p 口2 ) 一 土 2 p 口曲2 p 时，信息熵为最大值觑尺) 2 一p l 0 9 2p = - - l 0 9 2 p 。 根据最大离散熵定理，“等概率分布信源的平均不确定性最大”，所以在等价 类数目一定的情况下，各等价类中对象数相等时信息熵最大。 决策信息系统的属性集q 包括条件属性集c 和决策属性集d ，选取不同的 属性集来计算，可形成条件类熵、决策类熵、条件熵、规则熵和确定性规则熵。 不同形式的信息熵可分别用来度量决策表整体随机性、决策表整体不一致性以及 决策表整体不确定性。对于一致性决策表和不一致性决策表的整体不确定性，也 分别给出了各自适合的熵度量。下面对这些不同类型的熵分别进行阐述。 定义3 1 0 决策信息系统黔( u ，q = c u d ，v ，) ，p c = 蜀，局， ， 定义条件类熵为： 三 顶c ) 2 一乞p ( x ) i 0 9 2 p ( x ) 。 i = l 条件类熵研c ) 反映了条件等价类的粒度，由性质3 1 可知，若c l c 2 c 则有川c 1 ) 域c 2 ) ，即条件等价类粒度越大条件类熵越小。根据决策信息系统中 的信息来预测某对象的决策值，即根据这个对象的条件属性值来确定其决策属性 值，首先要做的就是确定其属于哪个条件等价类，也就是确定其匹配的规则前件。 因此，条件等价类粒度越大，条件等价类的数目越少，由此判定此对象属于哪个 条件等价类的不确定性越小。所以条件类熵反映了决策信息系统中的对象匹配规 则前件的不确定性，条件类熵( c ) 越小，对象匹配规则前件的不确定性越小。 定义3 1 1 决策信息系统乒( u ，q = c u d ，v ，p ，p d = k ，y 2 ，) ， 定义决策类熵为： 旦 顶d ) 。一p ( y , ) l o g zp ( r ) 。 i = l 决策类熵坝d ) 反映了决策等价类的粒度，同样由性质3 1 若d l d 2 c 则 硕士学位论文第三章决策信息系统的不确定性 有h ( d o h ( d 2 ) ，即决策等价类粒度越大决策类熵越小。决策等价类粒度越大， 决策等价类数目越少，判定对象属于哪个决策等价类的不确定性越小。确定某对 象属于哪个决策等价类，即找到符合的规则后件。因此，决策类熵反映了决策信 息系统中的对象匹配规则后件的不确定性，决策类熵川d ) 越小，对象匹配规则 后件的不确定性越小。 定义3 1 2 决策信息系统p ( u ，q = c o d ，v ，) ，n = l u c i ，m = i u d i ，d 相 对于c 的条件熵定义为： h ( d i c ) = 一p ( x , ) y p ( ri x , ) l o g ：j p ( i ) ， 其中嘲2 爿州黔等。 顾d i c ) 的表达式中一p ( y j | 一) l o g z p ( y ji 王) 反映了等价类与所有决策 等价类的交集的粒度，所以条件熵反映了平均每一条件等价类与所有决策等价类 的交集的粒度。在条件等价类不变的情况下p ( x 3 为定值，决策等价类粒度越大 生 则交集的粒度越大，从而一p ( r i 五) l o g z p ( y j ) 越小，因此条件熵越小。 条件熵度量了在已确定二_ 个对象属于某个条件等价类的情况下，判定其属于 哪个决策等价类的不确定性。存在这种不确定性是由于决策表具有不一致性。 性质3 3 决策表s ；( u ，q = c u d ，v ，厂) ，当且仅当条件熵川d l o = 0 时， 决策表中对象都为一致性对象。 根据定义3 1 2 ，若五巧(