（管理科学与工程专业论文）基于粗糙集的证据理论方法研究.pdf

基于粗糙集的证据理论方法研究 摘要 证据理论是处理由认识的局限性所带来的不确定性问题的有力工具，它处理 的证据来源于专家。但专家的知识经验往往是有限的，获取也较困难，且可能存 在一定的主观性，粗糙集理论反映了人们以不完全信息或知识去处理一些不可分 辨现象的能力，或依据观察、度量得到某些不精确的结果而进行数据分类的能力。 粗糙集的提出为处理模糊信息系统或不确定性问题提供了一种新型数学工具，是 对其它处理不确定性问题理论如概率理论、证据理论、模糊集理论等的一种补充。 针对上述所提证据理论的局限性，本文提出了一种基于粗糙集理论的证据获取的 新方法，并对证据合成和应用进行了研究。 首先对粗糙集理论作了进一步的研究，细化了其划分的粒度，在此基础上。 对决策表的决策属性作了进一步的转换，结合粗糙集和证据理论之问的关系，再 利用粗糙集的分类思想和隶属度概念，计算证据的基本可信度分配，从而实现了 证据信息的提取。 其次对证据合成的现状做了研究，针对目前方法在证据相关性、冲突性、重 要性等方面无法很好解决的问题，从以解决证据独立性问题为目的出发，给出了 采用属性聚类的方法分解决策表来解决问题的方案，并对属性约简的现状和问题 作了进一步的研究，设计了一种更有效的属性约筒算法。 再次，讨论了证据重要度和支持度的概念，研究了基于本文所提理论的证据 的合成方法以及决策支持。 最后，在上述研究内容的基础上，本文研究了基于粗糙集证据理论的股票分 析预测系统的体系结构、设计与实现等，并通过试验验证了本文所提方法的正确 - l 生， 关键字：证据理论，粗糙集，依赖度，基本可信度分配，信度函数 m e t h o dr e s e a r c ho n r o u g h s e t s - b a s e de v i d e n c e t h e o r y a b s t r a c t a sap o w e r f u lt o o li nd e a l i n gw i t hu n c e r t a i n t yq u e s t i o n s ，t h ee v i d e n c eu s i n gi n t h ee v i d e n c et h e o r yi s g i v e nb ye x p e r t s b u tt h ee x p e r t sk n o w l e d g ei s l i m i t e d ， s u b j e c t i v ea n dd i f f i c u l tt og a i ns o m e t i m e s q t ht h er o u g hs e t st h e o r y , p e o p l ec a n p r o c e s st h eu n d i s t i n g u i s h e dp r o b l e mu s i n gu n c o m p l e t e di n f o r m a t i o no rk n o w l e d g e a n da l s oe n h a n c et h ec a p a b i l i t y t o d a s s i f y t h e i m p r e c i s e d a t a c o m i n g f r o m o b s e r v a t i o no rm e a s l l r e m e n t s ot h ep r e s e n t a t i o no ft h er o u g hs e t st h e o r yg i v e su sa n e wm a t h e m a t i ct o o l p r o c e s s i n g t h e f u z z y i n f o r m a t i o ns y s t e ma n du n c e r t a i n t y p r o b l e m ，a n di sav a l u a b l ec o m p l e m e n t o f t h e o r ys u c h a sp r o b a b i l i t yt h e o r y ，e v i d e n c e t h e o r y , f u z z y s e t st h e o r ye t ca sw e l l t ot h el i m i t a t i o no fe v i d e n c et h e o r ym e n t i o n e d a b o v e ，t h i sp a p e rp r o p o s e san e ww a y o f k n o w l e d g ea c q u i r e m e n ta n da l s op r e s e n t sa v a l u a b l em e t h o do f t h ee v i d e n c ec o m b i n a t i o na n da p p l i c a t i o n f i r s t l y ，t h r o u g hf u r t h e rr e s e a r c ho f t h er o u g hs e t st h e o r y , w er e f i n et h eg r a n u l e o ft h ec l a s s i f i c a t i o n ，a n dt h e nc h a n g et h ed e c i s i o na t t r i b u t eo f t h ed e c i s i o nt a b l e b a s e o nt h e s ea n dt h er e l a t i o n s h i pb e t w e e nr o u g hs e t st h e o r ya n de v i d e n c et h e o r y , w e c o m p u t et h ee v i d e n c e sb a s i cb e l i e fa s s i g n m e n tt h r o u g hc l a s s i f i c a t i o n ，a n dt h u sw e r e a l i z et h ea c q u i s i t i o no f e v i d e n c e ， s e c o n d l y , w ed i s c u s st h ec u r r e n tr e s e a r c ho f t h ee v i d e n c ec o m b i n a t i o n t ot h e l i m i t a t i o nt h a tt h ec u r r e n tm e t h o d so ft h ee v i d e n c ec o m b i n a t i o nc a n tw e l ls o l v e ds u c h a s i n t e r r e l a t i o n ，c o n f l i c t a n d i m p o r t a n c e ，a n d f o rt h e g o a l o ft h e s o l v i n g t h e i n d e p e n d e n c e o ft h ee v i d e n c e ，an e ws o l u t i o nt h a t u s i n gt h e a t t r i b u t ec l u s t e rt o p a r t i t i o nt h ed e c i s i o n t a b l ei s p r o p o s e d i nt h i sp a p e rw ea l s od i s c u s st h ec u r r e n t r e s e a r c ho fa t t r i b u t er e d u c t i o na n dg i v ean e w m e t h o da sw e l l t h i r d l y , w ep r e s e n tt w on e l , vc o n c e p t i o n s ：e v i d e n c ei m p o r t a n c ea n de v i d e n c e s u p p o r t a n dt h e np r o p o s e t h ee v i d e n c ec o m b i n a t i o na n dd e c i s i o ns u p p o r tu n d e rt h e t h e o r yt h i sp a p e rp r e s e n t f i n a l l y , o nt h eb a s i so f t h ee f f o r t sa b o v e ，t h ed e s i g n ，a r c h i t e c t u r ea n dr e a l i z a t i o n o ft h es t o c km a r k e ta n a l y s i sa n df o r e c a s ts y s t e mb a s eo nr o u g hs e t s b a s e de v i d e n c e t h e o r yi sp r o p o s e d a n dt h r o u g ht h ee x p e r i m e n tw ev a l i d a t et h ea v a i l a b i l i t yo f t h e t h e o r y k e yw o r d s ：e v i d e n c e t h e o r y ,r o u g bs e t s ，d e 黟e e o fd e p e n d e n c y ,b a s i c p r o b a b i l i t ya s s i g n m e n t ，b e l i e f f u n c t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得盒目b 工些厶堂或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签专李啦签字日期f 枷怔年1 瑚1 日 学位论文版权使用授权书 本学位论文作者完全了解佥g b 王、业厶堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权盒 世互些厶堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名7 誉坠刁。 导师签名： 签字日期：伽p 仁年，月砷日 学位论文作者毕业后去向： - 1 ：作单位： 通讯地址： a 以够跌 签字日期叶年广月书 致谢 本文从论文的选题、资料的收集、论文的撰写到论文的成稿，自始至终都得 到了我的导师刘业政教授的悉心指导和细心帮助，不仅如此，三年来，刘老师在 学业上一直对我严格要求，生活上也给予我无微不至的关怀，我所取的每一点进 步、每一点成绩都离不开刘老师的谆谆教诲，值此论文完成之际，我谨向导师刘 业政教授表示诚挚的感谢，并致以深深的谢意。刘老师对待学生高标准、严要求 却又平易近人，他那渊博的知识、严谨的治学态度、敏锐的学术洞察力、积极开 拓和忘我的工作精神，对我产生了很大的影响，将使我受益终生。 感谢管理学院杨善林、马溪骏、朱卫东、李兴国、钟金宏、张结魁、左春荣、 何建民、刘心报等领导和老师对我的关心和指导。 在这读研的三年时间里，我也得到了刘振广、蔡勇、胡剑、李杰、于海峰、 张福安、徐春、汪振安、王长勇、查道鹏等同学的关心和帮助，在此对他们表示 感谢。同时，也感谢实验室的王毅、林文龙、杨攀、聂海兵、张婷以及王华娴等 师弟师妹们对我的关心和帮助，尤其感谢王华娴同学，她在论文试验数据的收集 上提供了很大的帮助。 感谢我的父母和家人，正是他们多年来默默的支持和无私的关怀，使我完成 了学业。 感谢对论文进行评审和提出宝贵意见的各位老师。 最后，感谢所有关心和帮助过我的人们。 i i l 作者：李亚飞 2 0 0 4 年5 月 第一章绪论 不确定性可以分为随机性、模糊性和认识不确定性。随机性在自然界大量存 在，它可由历史资料得到的统计数字来描述，研究随机性的理论通常是概率论和 数理统计。模糊性通常是指发生在概念上的模糊，模糊理论是其常用研究工具。 认识的不确定性通常是人们认谚 水平的局限以及信息、知识的缺乏所造成的。因 此如果说随机性和模糊性是客观不确定性，那么认识不确定性则是主观的不确定 性。最早用于解决认识不确定性问题的工具是贝叶斯主观概率理论，以后又提出 确定性理论和证据理论等。 1 1 证据理论 “证据理论”也称“信度函数论”，它是用来处理由认识的局限性所带来的不确 定性问题的有力工具。证据理论是由s h a r e r 在1 9 7 6 年正式创立的，但为证据理 论作出重大贡献的则是d e m p s t e r 。他在1 9 6 7 年时给出了上、下概率的概念，第 一次明确提出了不满足可加性的概率；1 9 6 8 年，他又对统计问题给出了两批证 掘( 即两个独立的信息源) 的合成法则，即d e m p s t e r 合成法则。因此证据理论 又称为“d e m p s t e r s h a f e rt h e o r y ”( d s t ) 。近年来，证据理论越来越引起人们的重 视，在理论上取得了一些更加深入的研究成果，并在决策、人工智能、专家系统 等领域得到了初步应用。 经典的归纳概率逻辑预设了两个条件：( 1 ) 逻辑全知，即艟穷尽一试验的所 有可能结果。( 2 ) 概率全知，即能确定事件域中任一成员的概率值。正是这后一 条使得在经典归纳概率逻辑中具有突出地位的贝叶斯理论难以合适的表达无知， 专家间意见的不一致等。保留( 1 ) 舍去( 2 ) 导致了上下概率函数理论的诞生。 它力图描述人们在确定概率f 于的无知和证据的不充分这就是最初的d e m p s t e r 理论。s h a f e r 进一步发展了d e m p s t e r 理论，他对该理论作了重新解释，放弃信 念度即为下概率的观点，引入了证据权重的一些新概念等，同时保留“d e m p s t e r 规则”，从而构建了证据的数学理论，这就是我们所说的证据理论。 证据理论通过引入信度函数的概念，利用信度函数，人们无需给出具体的概 率值，而只要根据已有的领域知识就能对事件的概率分布加以约束，在此基础上 就可以正确的决策。换句话说就是它将对命题概率推断的基础建立在结论的幂集 土丽不是结论本身，把对命题约推断转化为对集合的运算，基于从客观阅题获玻 的知识( 证据) 用分布于【0 ，1 1 之间的数值构造出命题为真的信任程度，从而支持 决策。 证据理论在理论和应用方面都得到了很大的发展。在应用上如前面所讲， 它在决策、预测、人工智能、专家系统等领域得到了初步应用。具体如基于证据 理论数据融合技术的多传感器目标辨识【1 、2 3 】。目前在理论上它的发展状况就是： 它缺乏一个大家所认同的解释。对它的解释目前主要有三种【4 】：上下概率解释、 随机译码器范例、可迁移信念模型。目前的研究热点主要是进一步拓展证据理论， 包括：如何使用证据理论处理不确定性的证据；如何使用证据理论表示规则强度： 如何推广证据理论等。由于为证据理论的主要合成规则的d e m p s t e r 规则存在着 明显的局限性，如它要求被合成的证据之间是独立的；它对不同信息源提供的证 据平等对待，合成时不考虑各证据的重要程度和可靠性优劣等，因此证据理论的 合成也是目前研究的热点之。对于相关证据合成，目前主要有两大类方法：一 类是将相关证据分解成独立证据，再使用d e m p s t e r 合成法则；另类是调整相 关证据的基本可信度分配，力图将相关证据转化为相当的独立证据，再应用 d e m p s t e r 合成法则。这些证据合成方法不同程度地克服了d e m p s t e r 合成法则的 缺陷，并且在一些领域取得了较好的应用，但也存在着一些缺陷限制了上述方法 的应用。 在证据获取方面，s h a f e r 认为，证据理论中的证据并不是实证据，而是指我 们的经验、知识以及对问题的观察和研究的结果。因此对某个实际问题，领域专 家的经验、知识以及他对该问题的观察、研究都是我们进行推理的证据。目前证 据理论中的证据获取主要是向专家咨询，根据专家的知识、经验在辨别框架上产 生一个基本可信度分配。由于它是由专家提供的，这必然面临下列一些问题：( 1 ) 专家的知识、经验是有限的；( 2 ) 专家的知识、经验往往有一定的主观性，特别 在面向决策领域时个人倾向会更明显；( 3 ) 专家的知识、经验获取有时是很困难 的。从上述分析可以看出，尽管证据理论在近年来得到了迅速发展。但在证据获 取、基本可信度分配等方面仍存在大量的问题需要进一步研究。 1 2 粗糙集理论 粗糙集( r o u g hs e t s ，简称r s 理论) 作为一种处理不精确、不确定与不完 全数据的新的数学理论，最初是由波兰数学家z p a w l a k 于1 9 8 2 年提出的。由于 最初关于粗糙集理论的研究大部分是用波兰语发表的，因此当时没有引起国际计 算机学界和数学界的重视，研究地域也仅局限在东欧一些国家，直到2 0 世纪8 0 年代末才逐渐引起各国学者的注意。近几年来，由于它在机器学习与知识发现、 数据挖掘、决策支持与分析等方面的广泛应用，研究逐渐趋热。1 9 9 2 年在波兰 k i e k r z 召开了第一届国际r s 研讨会。这次会议着重讨论了集合近似定义的基本 思想及应用，其中r s 环境下机器学习的基础研究是这次会议的4 个专题之一。 1 9 9 3 年在加拿大b a n f f 召开第二届国际r s 理论与知识发现研讨会。这次会议积 极推动了国际上对r s 理论与应用的研究。由于当时正值数据库知识发现( k d d ) 成为研究的热门话题，一些著名k d d 学者参加了这次会议，并且介绍了许多应 用扩展r s 理论的知识发现方法与系统。1 9 9 5 年，a c mc o m m u r f i c a t i o n 将其列 为新浮现的计算机科学的研究课题，1 9 9 6 年第四届国际研讨会f t h ef o u r t h i n t e r n a t i o n a l w o r k s h o p o n r o u g hs e t s ，f u z z ys e t s ，a n dm a c h i n ed i s c o v e r y ， r s f d 9 6 ) 在日本东京召开，推动了亚洲地区对r s 理论与应用的研究。1 9 9 8 年， 国际信息科学杂志为r s 理论的研究出了一期专辑。2 0 0 1 年5 月在重庆举行第一 届中国r s 理论与软计算学术研讨会。 粗糙集理论反映了人们以不完全信息或知识去处理一些不可分辨现象的能 力，或依据观察、度量到某些不精确的结果而进行数据分类的能力。粗糙集的提 出为处理模糊信息系统或不确定性问题提供了一种新型数学工具，是对其它处理 不确定性问题理论如概率理论、证据理论、模糊集理论等的一种补充。粗糙集方 法的简单实用性是令人惊奇的，它能在创立后的不长时间内得到迅速应用完全是 由其特点决定的【5 】； ( i ) 它能处理各种数据，包括不完整( i n c o m p l e t e ) 的数据以及拥有众多变量的 数据； ( 3 ) 它能处理数据的不精确和模棱两可( a m b i g u i t y ) ，包括确定性和非确定性 的情况； ( 4 ) 它能求得知识的最小表达( r e d u c t ) 芹n 知识的各种不同颗粒( g r a n u l a r i t y ) 层 次： ( 5 ) 它能从数据中揭示出概念简单，易于操作的模式( p a t t e r n ) ； ( 6 ) 它能产生精确而又易于检查和证实的规则，特别适于智能控制中规则的自 动生成。 近些年来出现了大量的r o u g h 数学及r o u g h 函数的研究，发表了一系列关 于r o u g h 函数方面的论文，如r o u g h 函数的各种近似运算，r o u g h 函数的基本 性质，关于它的r o u g h 连续、r o u g h 极限、r o u g h 可导、r o u g h 积分和r o u g h 稳定性、r o u g h 函数控制及建立由r o u g h 实函数控制的离散动态系统都是典型的 问题，这些问题都要求在r o u g h 函数理论的模型下给予公式化。这些问题的研 究将有助于定性推理方法的研究。这种研究实质上是使连续数学离散化从而使连 续数学也能被现代计算机所接受。 目前，对r s 理论研究集中在其数学性质、r s 拓广、与其它不确定方法的关 系和互补及有效算法等方面。 1 ) r s 理论数学性质方面的研究，主要讨论r s 的代数结构、拓扑结构，以 及r s 的收敛性问题。 2 ) r s 拓广方面的研究主要涉及广义r s 模型( 或称变精确性r s 模型) 与 对连续属性的离散化。 3 ) 在r s 有效算法方面的研究，主要集中于：a 导出规则的增量式算法。原 有的算法是在固定的数据集上进行的，当有新的数据增加到数据集时，若用原有 算法导出规则是相当麻烦的，增量式算法是对原有规则进行修正，从而得出关于 新数据集的规则的方法；b 约简的启发式算法。对于一个信息系统来说找出其 所有约简是n p h a r d 问题，很自然的想法是采用启发式方法找出最优或次优约 简，这些算法的共同特点是利用属性的重要性作为启发信息； 4 ) 基于r s 的逻辑是关于r s 的不确定推理的基础，发展这类逻辑的理论基 础也是目前r s 理论研究的重要课题。 5 ) 在粗糙集理论与其他处理模糊性或不确定性方法的理论研究中，主要集 中在它与概率统计、模糊数学、d s 证据理论和信息论的相互渗透与补充。 1 3 基于粗糙集的证据理论 p a w l a k 认为，决定人类行为的一个基本特征是对对象的分类能力，而分类 既是r o u g h 集理论的核一i i , ，也是证据理论的核心。最早注意到证据理论和r o u g h 集理论关系的是g r z y m a l a b u s s e 和s k o w r o n 【6 j ，他们解释了在r o u g h 集框架下证 据理论的基本概念。r o u g h 集理论与证据理论的关系可以给我们带来如下的启 发：( 1 ) r o u g h 集理论可以依据决策表分析各属性之间的相关性、属性的重要性和 可靠性，因而可以将其推广到对证据的分析，包括分析证据的重要性、可靠性和 相关性，从而改进d e m p s t e r 合成法则及合成结果：( 2 ) r o u g h 集理论可以依据决 策表分析对象的隶属度，因而可以将其推广到对辨别框的分析，以获取证据在辨 别框架上的基本可信度分配，从而解决传统证据理论中有关此类信息获取的困难 和由于专家的经验判断所带来的主观不确定问题。r o u g h 集理论与应用研究近年 来也取得了较大的发展，但在将其与证据理论集成应用时，为了提高证据分析的 准确性、可靠性以及能合理获取证据在辨别框架上的基本可信度分配，改善证据 合成的效果，还有一些问题有待进一步研究。但不管怎么说，集成证据理论和 r o u g h 集理论处理不确定性问题，即利用r o u g h 集理论从大量的历史数据中寻找 证据，获取证据在辨别框架上的基本可信度分配并对证据进行有效合成，是一种 行之有效的方法。这种首次将r o u g h 集方法集成于证据理论对推动不确定性理 论的发展有较大的理论意义和实际应用价值。 1 4 文章的主要研究内容及结构安排 1 4 1 研究内容 本文针对证据理论中有关证据信息获取时所遇到的困难，研究基于粗糙集的 证据信息获取及决策支持。通过对历史数据的分析，利用粗粗糙集技术从中挖掘 出隐含的知识，从而解决证据理论中专家意见获取困难的问题，在此基础上，研 究基于历史信息的证据理论决策方法，为管理决策者提供决策支持。针对此研究 目的，本文重点研究以下几个方面的问题： 1 、基于r o u g h 集的证据理论研究 根据r o u g h 集理论中的上近似、下近似、边界域等概念描述证据理论中的辨 别框架、置信度、似然函数等，建立r o u g h 集与证据理论的相互联系，从而将 r o u g h 集中的属性分析转化为证据理论中的证据分析。 2 、研究影响决策目标的证据、证据作用在辨别框架下的基本可信度分配， 分析证据的相关性、证据的重要度。 3 、综合考虑证据相关性、重要性、可靠性与证据高度冲突对证据合成的影 响，研究具有一般规律的证据合成法则。 4 、实例验证：基于 h 糙集证据理论的数据分析原型系统开发及应用。 1 4 2 结构安排 本文根据研究内容共分为六章。 第一章，绪论。本章分析了目前证据理论存在的局限性，粗糙集在不确定性 问题上的优点等。简要概述所要讨论的问题，研究的内容，意义等。 第二章，粗糙集与证据理论。主要介绍粗糙集和证据理论的基本概念和基本 算法。包括等价关系，上下近似集，知识约简及其算法以及证据理论中的基本概 率分配，信度函数，似真函数，证据合成等。 第三章，基于粗集理论的证据信息获取方法研究。主要研究了如何把粗糙集 同证据理论结合在一起。内容包括对象的进一步划分，决策属性转换和证据信息 的提取。 第四章，决策表分解及属性约简。讨论了证据理论中有关证据合成的研究现 状和问题，以及决策分解的目的、方法。对每张决策表的属性约简问题，本章也 作了探讨，包括研究现状和问题，并提出了自己的约简算法。 第五章，证据合成及决策支持。研究了基于本文所提方法所获证据的可靠性 和对问题的支持度问题，从而可以使决策更趋合理。在本章的最后，分析了证据 的合成和具体的决策方法。 第六章，实证研究。试验对本文所提方法作一实际验证，并对结果进行分析。 第二章粗糙集与证据理论 粗糙集理论是建立在分类机制的基础上的，它将分类理解为在特定空间上的 等价关系，而等价关系构成了对该空间的划分。粗糙集理论将知识理解为对数据 的划分，因此其主要思想是利用已知的知识库，将不精确或不确定的知识用已知 知识库中的知识来( 近似该0 画。该理论与其他处理不确定和不精确问题理论的最 显著的区别是它无需提供问题所需处理的数据集合之外的任何先验信息【7 j ，所以 对问题的不确定性的描述或处理可以说是比较客观的，由于该理论未能包含处理 不精确或不确定原始数据的机制，所以它与概率论、模糊数学和证据理论等其他 处理不确定或不精确问题的理论有很强的互补性。本章首先介绍粗糙集基本理论 并给出基本算法，然后介绍证据理论的有关概念、定理等基本理论。 21 经典粗糙集模型及计算方法 经典粗糙集理论是建立在基于等价关系的对象分类上的，由相同信息所标识 的对象是不可分辨的，它们之间的这种不可分辨关系就是一种等价关系，这种不 可分辨关系其实就构成了粗糙集理论的数学基础。 2 1 1 信息系统与决策表 定义2 1 若论域u 表示非空有限集合，4 表示关于u 的属性集，v = u 圪， d e p ：表示属性a 的值域，映射厂：u a 一矿表示对v x u ，口彳，有- 厂( x ，口) 矿， 那么信息系统可用四元组i = 表示。 定义2 2 对于每个属性子集b a ，可以定义一个不可分辨二元关系( 不分 明关系) i n d ( b ) 即： i n d ( b ) = b ，y ) jk y ) u2 ，v b b ( 6 b ) = 6 ) ) ；。 显然1 n d ( b ) 是一个等价关系，i n d ( b ) = n i n d ( b ) 。它的所有等价类的集合记 6 e 口 为u 占，含有x 的等价类记为b ( x ) 或m 。同一等价类中的元素是不可分辨的， 称i n d ( b ) 等价类为初等集，它是知识库的基本结构单元即概念。若 u b = x l ，x 汀一，x 。) ，则x ，( f = 1 , 2 ，月) 均为u 上的b 初等集，且有 n ( ，n x7 = o ) u x ，= u ( f ，；f ，j = 1 , 2 ，n ) 。 i = 1 u b 也被称为知识，它是论域u 的一种划分。 定义2 3 ，若属性集可以表示为：a = c u d ，其中c 和d 分别成为条件属性 和决策属性，d a ，那么信息系统i = 就是一个决策表。条件属性 c 和决策属性d 的等价关系i n d ( c ) 和i n d ( d ) 的等价类分别称为条件类和决策 类。决策表简记为i = ( u ，c u 留 ) 。 若决策表的决策属性集只含有一个属性，则此决策表是单一决策的，否则是 多决策的。对于多决策的任务，可通过下列两神方法将其转换成单决策任务。 方法一：若决策表，= ( u ，c u d ，v 。， ，d = d ，d ：，d 。) ，则可将此决策 表分解成m 个不同的单一决策表i = ( f = 1 , 2 ，打) 。 方法二：若决策表，= ，d = p 。，d ：，d 。) ，则可以构造一 个新的决策表t = ，a = c u d ，其中忙 为新的决箫属性集，其 取值满足如下要求； 对于任意x ，y u ，有d ( x ) = d ( y ) 矽a ( d ( 工) = d ，( _ y ) ) 。 定义2 4 设u a = x ，x ：，x 。) 和u ，b = _ ，夏，k ) 是论域u 上的两个 划分。则u a 与u b 的交、并运算及包含关系为二 u a 五u b = x n ：x ，u a a 一u b ) u a o u b = x ，u 一：x ，u a a y ，u b ) u a 兰u ，廖= ( v x ) z e u a ( j 一) y j u b a x ， 定义2 5 对于任意z ，y sa 产生两个划分u x u y ，有日，a 万u r 也 是u 的一个划分，且u 一五( ，b = u ( x u y 、。 定义2 6 决策表可以简记为：i = ( u ，cl y p ) ，其s t ? a 列的项记为a ( s ) ，又 称盯( = 伽en ，u ：口d ) = k ) 为a 的阶，记为，( 则。的值域为 屹= 1 , 2 ，( d ) ) 。 由此，我们可以根据决策属性d 把决策表i 划分为： 睨，( d ) = x ，彳2 ，x 州) j ，其中： = d 。 i ，= 扛? s u d ( 了) = 七ii s 露，p ) a 另外，我们分别称决策表j = ( u ，c u 臼j ) 的由d 决定的两个一一对应集合： o ，= 1 , 2 ，( d ) ) 和c ( d ) = x ，爿：，x w 】) 为d 辨识框和d 分类。 算法2 1u 关于属性a 的分类 输入：论域u 及属性a a 输出：u 关于g 的分类p a r t i t i o n a ( 1 ) p a r t i t i o n 一口 a ，r ( d ) = 0 ，屹卜o ； ( 2 ) f o r ( i = 1 ；i l u l ；f + + ) i f ( a ( i ) e ) 圪_ a ( 1 ) ； r ( a ) + + ； ( 3 ) i f ( r ( a ) 一0 ) 转( 5 k ( 4 ) f o r ( i = 1 ；i l u l ；i + + ) 口( f ) = k ； s w i t c h ( k ) c a s e ( 1 ) ：p a r t i t i o n a o 】- i ； c a s e ( 2 ) ：p a r t i t i o n a 1 4 - - - i ； c a s e ( r ( a ) ) ：p a r t i t i o n 一讲r ( d ) 一1 卜i ； ) ( 5 ) 输出p a r t i t i o n a 。 算法时间复杂度：t c o ( n 2 ) 算法2 2 己知u a ，u b ，求u ( a u b ) 输入：u ，a = p a r t i t i o n a = a l ，a 2 ，彳。) ，u b = p a r t i t i o n b = b 【，b 2 ，e 输出：u 关于u b ) 的分类p a r t i t i o n 一4 曰 ( 1 ) p a r t i t i o n a b 卜o ； ( 2 ) f o r ( i = 0 ；i m ；i + + ) f o r ( j = 0 ；j n ；j + + ) w h i l e ( a * ! = 0 ) w h i l e ( b n ! = o ) 矿( 厶一b y t ) l e t u p 卜a m ； b r e a k ； t + + ： ) k + + ： ) i f ( t e m p ! = 彩1 p a r t i t i o n a b 卜t e m p ； ) 算法时间复杂度：t c o ( n 4 ) 。 结合算法2 1 和2 2 ，可以求出u 关于任意属性的分类。 2 1 2 粗糙集与近似 设x u ，4 是u 上的等价关系，在= ( u ，a ) 上，如果是一些a 初等集 的并，则称x 是爿一可定义的，否则称盖是一不可定义的。么可定义集被称为a 一 一致集或a 一恰当集，而爿一不可定义集被称为a 一不可定义集或a r o u g h 集，简 称不一致集或r o u g h 集。借用上近似集和下近似集可以定义r o u g h 集。 定义2 7 8 1 设x u 是任一子集，a 是u 上的等价关系，则有 d ( x ) = u i r u a ：y e x ； 爿( x ) = u r u a ：y n x o ) 分别称它们为x 的a 下近似和a 上近似，其中a 是空集，j ，是 ，上按等价 关系4 划分所形成的等价类( 初等集) 。下近似和上近似也可以写成下面的等价 形式： 4 ( ) = x u ：【x 】x ) ； a ( x ) = x u ：【z 】 n x a 另外，称b n 。( ) = 4 ( j ) 一4 ( x ) 为x 的一边界域，p o s 。( x ) = 丛为爿的 爿正域，称n e g ( x ) = u 一以( 五) 为x 的a 负域。 显然，正域内的对象一定属于，负域内的对象定不属于z ，边界域内 的对象可能属于x ，也可能不属于x 。因此可以看出，下近似集中的对象反映 了对象属于概念x 的充分条件，因而形成分类规则；上近似中的对象反映了对 象属于概念z 的必要条件，因而形成了特征规则【9 】o 算法2 3 已知，u a ，求型x ) 输入：x ，u a = a 1 ，a 2 ，a 。) 输出：( x ) ( 1 ) s u m = 0 ，4 ( x ) 卜a ； ( 2 ) f o r ( i = o ；f ”；f + + ) s g m = o ： f o r ( j = o ；j a ，c o u n t ( ) ；j + + ) f o ，( k = o ；k n ；k + + ) i f ( a ，= = x 。) s u m 十+ ： b r e a k ； ) i f ( s u m = = a c o u n t ( ) ) ( x ) 扣a 。； ( 3 ) 输出i ( x ) 。 算法时间复杂度t c o ( n3 ) 算法2 4 己知x ，u a ，求a ( x ) 输入：x ，u a = a ，a 2 ，a 。) 输出：4 ( x ) ( 1 ) a ( x 1 卜o ； ( 2 ) f o r ( i = o ；i n ；i + + ) f l a g = o ： f o r ( j = o ；， a 。c o u n t o ；j + + ) f o r ( k = o ：k x c o u n t ( ) ；k + + ) i f ( a 。一x 女) f l a g = 1 ； 4 ( ) + - 4 。 b r e a k ； i f ( f l a g 一1 、 b r e a k ； ) ) ( 3 ) 输出爿( x ) 。 时间复杂度t c o ( n 3 ) 。 定义2 8 对于，= ( u ，4 ) ，x u 是a r o u g h 集，则称 州耻矧c n a ， 为的a 的精度，p a ( x ) = i - 口。( x ) 称为x 的爿粗糙度，粗糙度反应了知识4 的 不完全程度。 2 1 3 知识依赖 定义2 9 ( 隶属度) 根据等价关系a ，论域中的对象x 隶属与工的粗糙隶属 度定义为： 袱加科 显然，一。a 【0 ，1 】。可以看出，隶属度其实是一种条件概率，是x x 的确定 度。 定义2 1 0 ( 近似精度与近似质量) 对于，= ( u ，爿) ，x = ( j ，x ：，x 。) 是u 上的个划分，则称 j 战ji 掣 卜蒜和h 卜讦 i 砝i m 为x 的a 近似精度和近似质量。 分类的近似精度相当于规则的信度，表明根据现有的知识对对象进行分类时 可能正确的百分数；近似质量则相当于规则的支持度，反映了知识4 相对于x 的 分类能力。 定义2 1 1 对于= ( u ，c u d ) ，如果a c ，则d 的a 正域定义为 p o s _ ( d ) = u 簦。 定义2 1 2 ( 属性依赖) 如果属性集d 中所有的值唯一的由属性集c 中的属 性值确定，则称d 完全依赖于属性集c ，记为c jd 。如果有： 七= y ( c ，。) = i p o s c ( d ) i 则称d 以度( o k 1 ) 依赖于c ，记为c j 。d 。若k = 1 ，d 完全依赖于c ， 若0 k 【0 ，l 】满足； q ( 臼) = 川( 妒) ( p c ) 3 口 则称9 为众信度函数( c o m m o n a l i t y f u n c t i o n ) 。可以看出，对于一个集合0 0 ， 它的众信度0 ( o ) 反映了包含0 的集合的所有基本概率分配之和。 定义2 2 0 ( 似真度函数) 设辨识框0 上的函数p i ：2 。辛 0 ，1 满足： p l ( o ) = 埘( 妒) 或p i ( o ) = l b e t ( o ) ( 口o ) 口i 品。 称尸f 为似真度函数( p l a u s i b i l i t yf u n c t i o n ) 。若0 n 妒a ，称0 ，妒相容，则似真 度函数p l ( o ) 说明了它是所有与0 相容的那些集合的基本可信度分配之和。可以 发现在单点集上，似真度函数与众信度函数是相同的，表示公式为： p f ( ) ) = q ( ) ) ，( a o ) 。 定理2 1 基本概率分配与信度函数可以有如下关系： r e ( o ) = ( 一1 ) l o - a l b e l ( a ) ( 口o ) c 目 定理2 2 设b e l 是 上的信度函数，| p ，和q 分别是b e l 所对应的似真度函数 和众信度函数那么： p i ( o ) = ( 一1 ) q ( 妒) 2 5口 q ( 臼) = ( 一“p t ( e ) 口c d 定理2 3 设。是一个辨识框，集函数b e l ：2 。_ 0 ，1 是信度函数当且仅当 它满足： ( 1 ) 、b p ? ( o ) = 0 ( 2 ) 、b e l ( 0 1 = 1 ( 3 ) 、v 0 1 ，0 2 ，0 。匕。有： b e l ( u o i ) b e l ( o , ) 一b e l ( o i n q ) + + ( 一1 ) “1 肋，( n 臼，) j=】t=lj ( ji = 1 从上面第三条可以看出，信度函数不定满足, - i 自d 性【2 1 】，而是满足所谓的半 可加性( b e l ( o ) + b e l ( o 一0 ) s 1 ) 。因此可以认为满足可加性的信度函数是特例。 定义2 2 1 ( 贝叶斯信度函数) 如果0 是一个辨识框，b e l ：2 。_ 【0 ，1 满足： b e l ( 护u ) ：f 功+ 8 e 段)( 口，e ，护n = o ) 则称b e l 是贝叶斯信度函数。可以看出贝叶斯信度函数有如下性质： ( 1 ) b e l ( o ) = p i ( o 、； ( 2 ) e m ( ) ) = l ；b e l ( o ) = m ( ( ) ，其中0 o ， a e3 , c o 显然b e l ( o ) + b e l ( o ) = 1 ； ( 3 ) 所有的焦元都只含有一个元素，即是单点。 可见贝叶斯信度函数实质上是一个点函数而不是集函数，正因为如此，