（应用数学专业论文）基于决策能力的属性约简模型.pdf

摘要 信息系统的属性约简是所有粗糙集理论和应用研究的焦点问题之一。常见的 属性约简算法有：p a w l a k 粗糙集模型、信息熵模型、变精度模型等。然而这几 种算法都存在一定的缺陷，不利于实际应用。 本文从现实问题角度出发，针对实际问题的需要，提出了一种基于决策能力 的属性约简模型，并在这种模型下给出了相应的属性重要性的定义。基于决策能 力的属性约简模型，是在不降低决策能力的条件下，以决策代价最小为目标，进 而求出最优的约简。同时，根据各属性集影响决策能力的高低来定义相应的属性 重要性。本文给出决策能力约简模型的满足的一些性质，并通过几个实例说明这 种模型的实用性。 关键词：粗糙集、属性约简、属性重要性、决策系统 a b s t r a c t t h ea t t r i b u t er e d u c t i o no fi n f o r m a t i o ns y s t e mi so n eo ft h ef o c u so fr o u g hs e t t h e o r ya n da p p l i e dr e s e a r c h t h ec o m m o na l g o r i t h mo fa t t r i b u t er e d u c t i o na r e p a w l a kr o u g hs e tm o d e l ，i n f o r m a t i o ne n t r o p ym o d e l ，v a r i a b l ep r e c i s i o nr o u g hs e t m o d e la n ds oo n h o w e v e r , a l lt h e s ea l g o r i t h m sh a v es o m ef a u l t w h i c hd o e s n tm a k e t h ea p p l i c a t i o ni nr e a l i t y b a s e do nt r u ei s s u e sa n da i m e da tt h en e e do fs o m ep r o b l e m si nr e a l i t y t h i s p a s s a g ep u tf o r w a r dt h ea t t r i b u t er e d u c t i o nm o d e lb a s e do nd e c i s i o n m a k i n g c a p a c i t y ，a n dd e f i n et h er e l a t i v ea t t r i b u t es i g n i f i c a n c e t h ea t t r i b u t er e d u c t i o nm o d e l b a s e do nd e c i s i o n m a k i n gc a p a c i t yi sa i m e da tc o s t i n gt h el e a s td e c i s i o n - m a k i n g ，g e t t h eb e s tr e d u c t i o n w i t h o u tl o w e r i n gt h ed e c i s i o n m a k i n gc a p a c i t y w i l ld e f i n et h e i m p o r t a n c eo fr e l a t i v er e d u c t i o na c c o r d i n gt h el e v e lo fe a c hm e a n w h i l e i tw h i c h a f f e c tt h ed e c i s i o n m a k i n gc a p a c i t y 1 1 1 ep a s s a g eg i v e ss o m eq u a l i t i e sw h i c hs a t i s f y t h em o d e l ，a n dw i l lt h r o wl i g h tu p o nt h ea p p l i c a t i o no ft h em o d e lt h r o u g hs o m e e x a m p l e s k e yw o r d s ：r o u g hs e t ，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 es i g n i f i c a n c e ，d e c i s i o n m a k i n g n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名勘q j 签字日期：。妒年6 月日 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名勘司 签字日期：。湃b 月r 日 导师签名：妄呻f 磊 签字日期：蹦年6 月j - 日 引言 不确定性可以分为随机性、模糊性和认识不确定性。随机性在自然界大量存 在，它可以由历史资料得到的统计来描述，研究性的理论通常是概率论和数理统 计。模糊性通常是指发生在概念上的模糊，模糊理论是其常用的研究工具。认识 的不确定性通常是人们认识水平的局限以及信息、知识的缺乏所造成的。因此如 果说随机性和模糊性是客观不确定性，那么认识不确定性则是主观的不确定性。 最早用于解决不确定性问题的工具是贝叶斯主观概率理论，以后又提出了粗糙 集。 粗糙集理论是一种刻划不完整性和不确定性的数学工具，能有效地分析和处 理不精确，不完整、不确定等各种不完备信息，并从中发现隐含的知识，揭示潜 在的规律。它的重要特点是不需要预先给定某些特征或属性的数量描述而直接从 给定问题的描述集合出发，在保持分类能力不变的前提下，通过知识约简，导出 概念的分类规则，因此具有很强的定性分析能力。自p a w l a k 提出以来，粗糙集 理论已经在机器学习、数据挖掘等领域中得到了较为广泛的应用，其理论体系与 f u z z y 集等理论的关系也得到了阐明。 知识约简是粗糙集理论的核心内容之一，所谓的知识约简就是研究知识库中 哪些知识是必要的，以及在保持分类能力不变的前提下，删除冗余的知识。高效 的约简算法是粗糙集理论应用于数据挖掘与知识发现领域的基础，虽然已有一些 相关研究成果，但寻求快速的约简算法仍是主要研究课题之一。 目前，信息系统的知识约简大多是在p a w l a k 粗糙集模型下进行的。然而 p a w l a k 粗糙集模型的一个局限性是它只考虑完全“包含一和“不包含 ，而没有 某种程度上“包含一与“属于一；另一个局限是它所处理的对象是已知的，且从 模型是得到的结论仅适用于这些对象。由于这些局限，很大程度上限制了p a w l a k 粗糙集模型的应用。针对p a w l a k 粗糙集模型的这些局限，一些专家、学者对 p a w l a k 粗糙集模型进行了相应的推广，提出了变精度粗糙集模型和信息熵约简 算法等几种约简算法，然而这些算法只从理论上考虑了分类能力不变下的属性约 v 简，往往不适合于实际的运用。 本文从现实问题角度出发，针对实际问题的需要，提出了一种基于决策能力 的属性约简模型，并在这种模型下给出了相应的属性重要性的定义。基于决策能 力的属性约简模型，是在不降低决策能力的条件下，以决策代价最小为目标，进 而求出最优的约简。同时，根据各属性集影响决策能力的高低来定义相应的属性 重要性。本文给出决策能力约简模型的满足的一些性质，并通过几个实例说明这 种模型的实用性。 v i 基于决策能力的属性约简模型 第1 章绪论 1 1 粗糙集理论 粗糙集( r o u g hs e t ) 由波兰数学家z p a w l a k 于1 9 8 2 年提出的【1 1 ，是作为 种处理不精确、不确定与不完全数据的新的数学理论 2 - 9 1 。由于最初关于粗糙集 理论的研究大部分是用波兰语发表的，因此当时没有引起国际计算机学界和数学 界的重视，研究地域也仅局限在东欧一些国家，一直到2 0 世纪8 0 年代末才逐渐 引起各国学者的注意。近几年来，由于它在机器学习与知识发现、数据挖掘、决 策支持与分析等方面的广泛应用【协1 9 1 ，研究逐渐趋热。1 9 9 2 年在波兰k i e k r z 召 开了第一届国际r s 研讨会。这次会议着重讨论了集合近似的基本思想及应用。 1 9 9 3 年在加拿大b a n f f 召开第二届国际r s 理论与知识发现研讨会。这次会议积 极推动了国际上对粗糙集理论与应用的研究。由于当时正值数据库知识发现 ( k d d ) 成为研究热门话题，一些著名k d d 学者参加了这次会议，并且介绍了许 多应用扩展r s 理论的知识发现方法与系统。1 9 9 5 年，a c mc o m m u n i c a t i o n 将 其列为新浮现的计算机科学的研究课题，1 9 9 6 年第四届国际研讨会( 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 e d i s c o v e r y , r s f d ，9 6 ) 在日本东京召开，推动了亚洲地区对粗糙集理论与应用的研 究。1 9 9 8 年，国际信息科学杂志为粗糙集理论的研究出了一期专辑。2 0 0 1 年5 月重庆举行了第一届中国粗糙集理论与软计算学术研讨会。 粗糙集理论反映了人们以不完全信息或知识去处理一些不可分辨现象的能 力，或依据观察、度量到某些不精确的结果而进行数据分类的能力。粗糙集的提 出为处理模糊信息系统或不确定性问题提供了一种新型数学工具，是对其它处理 不确定性问题理论如概率理论、证据理论、模糊集理论等的一种补充。粗糙集方 法的简单实用性是由其特点决定的： 1 ) 它能处理各种数据，包括不完整数据和不精确数据； 2 ) 它能求得知识的最小表达和知识的各种不同颗粒层次； 3 ) 它能从数据中提取出概念简单，易于操作的模式： 4 ) 它能产生精确而又易于检查和证实的规则。 江西师范大学硕士学位论文 近年来出现了大量的粗糙数学及粗糙函数的研究，发表了一系列关于粗糙 函数方面的论文，如粗糙函数的各种近似运算，粗糙函数的基本性质等，这些问 题的研究有助于定性推理方法的研究。这种研究实质是使连续数学离散化从而使 连续数学也能被现代计算机所接受。 目前，对粗糙集理论研究集中在其数学性质、粗糙集拓广、与其它不确定方 法的和互补及有效算法等方面。 1 ) 粗糙集理论数学性质方面的研究：主要讨论粗糙集的代数结构、拓扑结 构，以及粗糙集的收敛性问题。 2 ) 粗糙集拓广方面的研究：主要涉及广义粗糙集模型与对连续属性的离散 化。 3 ) 在粗糙集有效算法方面的研究：主要有导出规则的增量式算法以及约简 算法。 4 ) 与其它理论的相互渗透与补充：主要是与概率统计、模糊数学、证据理 论和信息论的相互渗透与补充。 知识约简是粗糙集理论的核心内容之一，所谓的知识约简就是研究知识库中 哪些知识是必要的，以及在保持分类能力不变的前提下，删除冗余的知识。高效 的约简算法是粗糙集理论应用于数据挖掘与知识发现领域的基础，虽然已有一些 相关研究成果2 m 3 5 1 ，但寻求快速的约简算法仍是主要研究课题之一。另外，粗糙 集如何处理大数据集也需要探索相应的解决方法。 本文针对完备信息系统下已有的属性约简算法存在的问题，通过分析决策者 的需要，提出了一种基于决策能力的属性约简算法，并同时在这个基础上给出了 各属性集关于决策的重要性。本文通过对几个典型实例的分析比较从理论上证明 了这种新的算法的合理性及优越性。 1 2 本文的研究内容 本文针对几种常见的属性约简算法和属性重要性的定义所存在的问题，提出 了一种基于决策能力的属性约简算法及属性重要性的定义，同时给出了一系列的 性质。并通过几个实例的对比分析，证明本文所给方法能为管理决策者提供更好 的决策支持。 2 基于决策能力的属性约简模型 本文重点研究以下几个方面的问题： 1 、完备信息系统下基于约简的属性重要性的定义。 、 2 、完备信息系统下基于决策能力的属性约简。 3 、完备信息系统下基于决策能力的属性重要性的定义。 4 、实例验证对比。 1 3 本文的结构安排 本文根据研究内容共分为五章。 第一章绪论。本章叙述了粗糙集的由来和近几年来的发展趋势、简要概述所 要讨论的问题、研究的内容、研究的意义等。 第二章粗糙集的基本概念。主要介绍了粗糙集中的一些基本概念。 第三章几种常见的属性约简算法。介绍了完备决策系统下的几种常用的属性 约简算法：p a w l a k 模型、变精度模型、信息熵模型以及这些算法的局限性。 第四章属性重要性的几种定义。介绍了几种常见的属性重要性的定义：代数 定义、信息熵定义、约简定义等；并讨论了这些定义所存在的不足。 第五章基于决策能力的属性约简及其重要性的定义。针对前面的属性约简算 法和重要性定义所存在的不足，提出了一种基于决策能力的属性约简和属性重要 性的定义并给出了新定义的所满足的一些性质。并通过几个实例进行对比，说明 这种本章算法的优越性。 3 江两师范大学硕士学位论文 第2 章粗糙集理论的基本概念 设u 是我们感兴趣对象组成的有限集合，称为论域。 任何子集x u ，称为u 中的一个概念或范畴。u 中的任何概念族称为关 于u 的抽象知识，简称知识。 定义2 1 假设u 为论域，若f = 五置，五 满足： 固x i c u 。x i 争，x j n x j = 母； 对于f 歹，i ，j = l ，2 ，n ；u 置= 【，； 则称f 为u 上的一个划分。 u 上的一族划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) ，记为 k = ( u ，r ) 。 设r 是u 上的一个等价关系，u r 表示r 的所有等价类构成的集合，【工】r 表 示包含元素工u 的r 等价类。显然，u r 是u 上的一个划分；反之若 f = 五五，以) 是u 上的一个划分，则可以定义u 上的一个等价关系。即 ( z ，y ) r 毯蚀置，y 置，也就是说，一个知识库就是一个关系。 定义2 2 假设r 是u 上的一族等价关系，若c cr ，且c 则n c 也是一个等价 关系，称为c 上的不可区分关系，记为伽d ( c ) ，且有【石】射( o = f lt x r 。 这样，u l i n d ( c ) 表示与等价关系族c 相关的知识，称为k 中关于u 的c 基本知识。为简单起见，我们用u c 代替u i n d ( c ) ，i n d ( c ) 的等价类称为知识 p 的基本概念或基本范畴。 定义2 3 令x cu ，r 为u 上等价关系。当x 能表达成某些r 基本范畴的并时， 称x 是酞可定义的；否则称x 为r 不可定义的。r 可定义集也称作r 精确集，而 4 基于决策能力的属性约简模型 r 不可定义集也称为r 粗糙集 r o u g hs e t ) 。 定义2 4 给定知识库k = ( 【厂，r ) ，对于每个子集x u 和一个等价关系r ，定义： _ r x = u 】，u i rl 】，x ) = 缸ul 【x k 互x ) 瓜= u 】，u i riy nx = 工ul 【石】rdx ) 分别称为x 的r 下近似集和r 上近似集。 “ 集合6 ( x ) = 一酗称为x 的r 边界域；p o s r = _ r x 称为x 的r 正域； n e g r ( 工) = 己，一称为x 的r 负域。显然：= p o s r ( x ) u b n r ( x ) 。 定理1( 1 ) x 为r 可定义集当且仅当麟= 些。 ( 2 ) x 为r 粗糙集当且仅当。 定义2 5 由等价关系r 定义的集合x 的近似精度为：口r ( x ) = 器，其中 x ，lxi 表示集合x 的基数。精度( x ) 用来反映我们对于了解集合x 的知 识的完全程度。 显然，对每一个r 和x u 有0 a m ( x ) l 。当口r ( x ) = 1 时，集合x 为r 可定义的；当c t r ( x ) 1 时，集合x 为r 不可定义的。 定义2 6 令g - = 五，五，以) 是u 的一个分类或划分，子集五是划分f 的类， 则定义： 酗 ( f ) 2 气百t - 为f 的近似分类质量。 近似分类的精度描述的是使用知识r 对对象分类时，可能的决策中正确决策 的百分比。近似分类的质量表示的是应用知识r 能确切地划a g 类的对象的百分 比。 定义2 7 令r 为一族等价关系，召sr 。 如果i n d ( r ) = i n d ( 1 r - b ) ，则称b 为r 中不必要的，否则称b 为r 中必要的。 如果每一个口r 都为r 中必要的，则r 为独立的。否则称为依赖的。 江西师范大学硕上学位论文 定义2 8 令b 和c 为u 中的等价关系，设曰c ，如果b 是独立的，且 i n d ( b ) = i n d ( c ) ，则称b 为c 的一个约简，记作r e d ( c ) 。 定义2 9 令c 和d 为u 中的等价关系，d 的c 正域记为p o s c ( d ) 。 即p o s c ( d ) = u 丛，d 的c 正域是u 中所有根据分类u c 的信息可以准确地 j e c ，d 划分到关系d 的等价类中去的对象集合。 定义2 1 0 令c 为u 中的等价关系，设有a c ，满足 p 黜锄( c ) ( i n d ( d ) ) = p o s i , a ( c - ) ( 朗d ( d ” 则称a 为c 中d 不必要的；否则为必要的。 如果c 中的每个属性都为d 必要的，则称c 为d 独立的。 定义2 1 1 令c 为u 中的等价关系，设b c ， b 为c 的d 约简当且仅当b 是c 的q 独立子族且p o s 丑( d ) = p o s c ( d ) ， c 的d 约简简称为相对约简。 定义2 1 2 令k = ( u ，r ) 为一知识库，且c ，d r 。当k = y c ( d ) 爿p o s c ( d ) i i 【，i 时，我们称知识d 是七度依赖于知识c 的，记c j 。d 。特别地，当k = 1 时，称 d 是依赖于知识c 的，记为c d 。 定义2 1 3 形式上，四元组s = ( u ，a ，v ，门是一个决策系统( 又称信息系统) ，其 中 u ：对象的非空有限集合，称为论域： a ：属性的非空有限集合； 厂：u a 专y 是一个信息函数，它为每个对象的每个属性赋予一个信息值， 即v a a ，x u ，f ( x ，口) r o 。 通常用s = ( u ，a ，) 来代替s = ( u ，a ，v ，厂) ，特别地，当a = c u d ，c 为条件 属性，d 为决策属性时，称s = ( u ，a ，) 为决策表。决策系统的数据以关系表的形式 表示。关系表的行对应要研究的对象，列对应对象的属性，对象的信息是通过指 定对象的各属性值来表达。当对象的信息是完全确定时，为完备决策表；当对象 6 基于决策能力的属性约简模型 的信息不完全确定时，称为不完备决策表。 定义2 1 4 决策表的分类： ( 1 ) 称决策表是一致的当且仅当d 依赖于c ，即c jd 。 ( 2 ) 称决策表是不一致的当且仅当c id ( 0 k 1 ) 。 7 江西师范大学硕上学位论文 第3 章完备信息系统下的属性约简算法 3 1 常见的属性约简算法 3 1 1p a wla k 粗糙集模型 3 1 2 变精度粗糙集模型( v p r s ) z i a r k o 于1 9 9 3 年提出了变精度粗糙集模型。在这个模型中，给定一个阈值， 当对象所在的等价类在某种程度上包含在某个集合中时，就认为这个对象属于该 是粗糙集模型的扩展。主要体现在引起p ( o 夕 o 5 ) 作为错误分类率的限制。 p a w l a k 粗糙集模型是变精度粗糙集在= 0 时的特例。 则肛 卜f 、l i 端 为集合x 关于y 的相对错误分类率。 令0s ，y = x ，圪) ) ，则 c 、d 在u 的子集组成的o r 代数上的概率分布为 p = p 蠢，p 受，：p 毒， ，【y ：p = p 戛，p 盏，：p 爱， 鼎舭) 二斜扣1 ，2 ，棚：p ( 驴爿= l ，2 ，棚。 定义3 1 5 设u c = 五，k ，以 ，则属性集c 的信息熵定义为： m o = - e p ( 五) l o g ( p ( 五) ) 定义3 1 6 设u c = 五，置，瓦 ，u d = d 。，砬，见 ， 则其相应的概率分布为： p - - i x , i i u i ，i - - l ，2 ，刀；p 0 且对v a 萑b ，有双吃( 口) = o 。 推论2 假设e ，j ，e 是c 的全部约简， 。 如果en n 色= ，则对v 口c 有义吃o ) = o ； 江西师范大学硕士学位论文 如果墨n n 只= 曰，则圈囝艺( 曰) 0 r 萍tv a 仨b ， s g f ：( a ) = o 。 显然推论1 可以由性质2 、和性质3 推出：推论2 可以由推论1 导出。 4 1 2 信息熵定义 在信息熵约简下，提出了基于信息熵的属性重要性的定义。 定义4 1 2 令s = a ，v , o 是一个决策系统，其中a = c u d ，c 是条件属性集合，u 是决策属性集合，b c c ，设u 口= 五，x 2 ，以) ，u d = d 。，0 2 ，q 。 则其相应的概率分布为： e ( x , ) = l x , i i u l ，i = 1 ，2 ，刀；p ( d ，) = i d , i i u i ，j = l ，2 ，m 对于任意属性口c - b 的重要性噼0 ) 定义为： s g f ：a a ) = h ( d ib ) - h ( d ib u 口) ) 其中，日( d i b ) = 一尸( 置) p ( 2i x j ) l o g ( p ( d ji 王) ) = 日( d u b ) 一日( 曰) i = l j - ! 日( b ) = 一np ( 置) l 。g ( p ( 鼍) ) ，p ( d jl x , ) = i z ) , n x , i i x , t s g f ：v ( a ) 的值越大，说明在已知b 的条件下，属性口对决策d 来说越重要。 显然， 当b = c 时，没有意义。 当b = 时，双瑶0 ) = 日( d ) 一h ( dia ) 表示没有已知条件下，属性口对决策d 的重要性。 4 1 3 两种定义的关系与缺陷 属性重要性的代数定义考虑的是该属性对论域中确定分类子集的影响，而信 息熵定义考虑的是该属性对于论域中不确定分类子集的影响。如果一个属性的增 加，不改变论域中本身已确定分类的实例，且所有本身不能确定分类的实例仍然 不能确定分类，只有不确定性有所变化，这样，该属性的重要性在代数定义下为 0 ，而其在信息定义下不为0 。 例如下表中 1 4 基于决策能力的属性约简模型 对c d 象 abc e l101 10 2o1oll 3oo ooo 4 o 0o1l 5o00ll 6 o0 0l1 70o 1l l 8o01o o 9 ool11 上表所示的决策信息系统，和，b ，c ，日是条件属性集， d ) 是决策属性集。 在代数定义下，属性c 的重要性为觋1 ( c ) 2 吉一吾2 0 。 在信息熵定义下，属性c 的重要性为： 跚2 地川( c ) = 日( d ) 6 ) 一日( d ) 6 ，c ) ) = 吉( 7 l 0 9 7 7 1 0 9 4 3 1 0 9 3 ) o 反过来，如果在信息熵定义下，属性重要性为0 ，那么在代数定义下一定为 0 也就是说信息熵定义是包含了代数定义的。即 s g r , l 。( c f ) = o j 舳艺( q ) = 0 。 又假设有以下决策表： c 对象d c ggg 1l11 11 2lo100 3 oo 11l 4 o11o o 按照直觉应该有 ( c d s g f c o ( q ) = ( c ：) 瓯( c 3 ) = 0 1 5 江两师范大学硕士学位论文 根据信息熵定义有 s g f 2 q 晒d ( q ) = s g f 2 c l 勺c 。( c 2 ) = s g f 2c i c 2 c d ( 乞) = 卿2 c l c 2 勺。( c 4 ) = 0 显然根据代数定义也有 s g f l c d ( q ) = s g f l ( 乞) = s g f l c o ( c o = s g f l c d ( q ) = 0 显然，前两种结论都与我们的直觉相悖。产生悖论的主要原因是代数定义和 信息熵定义在定义上存在着一定的缺陷，它们只适合用于同一约简中各个属性之 间的比较。而当信息表中存在着不必要的属性或是有多个不同约简同时存在时， 这样定义两种的属性重要性就失去了意义。 4 2 约简定义 一 针对代数定义与信息熵定义所存在的不足，本文考虑提出一种基于约简的定 义，主要考虑每个属性的缺失对最终约简个数的影响来定义相应的属性重要性。 定义4 2 1 令s = ，a ，v 0 是一个决策系统，其中a = c u d ，c 是条件属性集合，d 是决策属性集合，设c 是决策系统中所有约简的集合，口c ，c = q ，巳) 。我 们定义： b 关于d 的重要性= 含b 中元素的约简个数决策表所有约简的个数 ， 即 i c i q c c e c ) i 啤( 驴卫可丁一 特别，当曰= 辨时，属性b 关于。的重要性为：s 6 f ：o ( = 丛篁堡三产 这样定义的重要性满足下面几个性质： 性质1必要属性子集( 子集里面每一个属性都是不必要的) 的重要性为o ； 性质2 非不必要属性子集的重要性大于o ； 性质3 警哦( q ) 嘁( 踯毗乏哦( c ! f ) ) 显然这些性质可以由其定义直接推出。 定义4 2 2 当必吃( 曰) = m 。a 。丑x 双吃( q ) 时，称b 中所有属性之间完全依赖。 1 6 基于决策能力的属性约简模型 当蟛s o 吃( s g c o ( b ) r a i n 1 ，双蛇( q ) ) 时，称属性之间部分依赖。 c i e lc e 占 s c r ：o ( b ) = s g 艺( q ) 时，称b 中各属性之间完全独立。 当s g 艺( b ) = 1 时，称b 为不可省子集，也称核属性。即若缺少该子集，就会引 起决策表的不一致。 定义4 2 3 定义属性间相关系数为： 属性q 与属性勺的相关系数= c 矾( 同时含属性q 和c j 的约简) c a r d ( 含属性c f 或 c j 的所有约简) ，即 攘鲁蚓 显然0 勺1 。 性质1 当。，= 0 时，属性，q 与勺是相互独立的； 性质2 当托。，= 1 时，属性c j 与巳是完全依赖的。 性质3 对任意属性q ，有。= 1 。 性质4 若c ：f 为不必要属性，则有 ( 1 ) 册艺( q ) = 0 。 ( 2 ) 对v q 曰，s g 艺( 口) = s g 吃( 曰一q ) 。 ( 3 ) 对任意属性勺q ，有= o 。 显然这些性质可以由定义直接导出。 性质5 s g 艺( q ) = o j s 饼乞，。( q ) = o js g 艺( q ) = o 。 证明：如果s g 艺( q ) = o jq 不在任意一个约简中，即q 为不必要属性。 所以有阢墨乙，口( q ) = 0 ，双吃( q ) = o 。 4 3 约简定义的优劣分析 优点：基于约简的重要性定义主要考虑的是每个属性的缺失对最终约简个数 1 7 江西师范大学硕士学位论文 的影响来定义相应的属性重要性。这样定义的属性重要性不但可以直接反映各个 属性对决策表中约简个数的影响，而且根据属性的重要性可以很容易判断出核属 性，必要属性及冗余属性。根据这样定义的属性相关性能直接反映出属性间在约 简中的相互作用。 缺点：利用这种算法求属性的重要性时要首先求出决策系统中的所有约简， 然而求一个决策系统的所有约简是个n p 完全问题【3 6 1 ，当决策系统中的条件属性 比较多时，可能会无法求出其所有的约简。而此时，基于约简的重要性的定义就 没有任何意义了。再者，这种定义下的重要性只仅仅反映了各个属性间在约简中 出现的频率关系，而在现实中决策者可能不需要所有的约简，他可能更关心哪些 属性可以让他更简单更“便宜”地达到其所要的效果。 因此，基于约简定义的属性重要性很难运用到实际的操作中去。 4 4 实例对比 例题3 三种重要性的定义在t a b i 中的计算结果如下： t a b i 中属性重要性 q c 2c 3 1 s g f l 0 - 0 6 s g f 2 昙l 0 9 5 一。9 3 一三- 。9 2 l 0 9 2 1 1 。9 3 o s g f 3 l lo 例题4 三种重要性的定义在t a b 2 中的计算结果如下： t a b 2 中属性重要性 q c 2c 3 11 s g f _ _ o _ 82 s g f 2 吾l 0 9 3 一扣2 o 4 3 - - l 0 9 3 3 1 。9 2 s g f 3 l0l 例题5 三种重要性的定义在t a b 3 中的计算结果如下： 1 8 基于决策能力的属性约简模型 t a b 3 中属性重要性 c ： c 2g c s g f l 0oo0 s g f 2 00o0 11 1 s g f 3 - o 222 ( 详细的计算过程见附录3 、4 、5 ) 。 1 9 江两师范大学硕士学位论文 第5 章基于决策能力的属性约简模型 5 1 问题的提出 在现实操作中，决策者最希望看到的是信息表对他要做的决策能提供多大的 帮助，即最大的正确的决策率；或者在允许犯一定的错误的基础如何用最简单的 方法( 最少的属性数) 或是最“便宜”的方法( 最小的属性代价) 来进行决策。 在一致的协调的信息表中，由于不存在冲突证据，只要求出信息表的约简就 可以作出完全正确的决策。但往往很多时候所求出的约简中属性的个数相对较 多，而决策者要得到约简中的全部属性值的代价可能会很高，而且1 0 0 的正确 率有时候是不必要的。 在不一致的信息表中，由于存在一个或多个的相互冲突的证据，决策者作出 完全正确的决策是不可能的。那又如何在允许的错误率范围内用最简单或是最小 的代价作出决策? 例如在t a b 3 中： c 对象d cg c ，g l1llll 2l0loo ，o0l11 4ollo1 9 r 决策属性值只有两个( o 租1 ) ，如果只考虑决策属性而不考虑条件属性。 决策者即使随便做个决策( 0 或者1 ) 都会有5 0 的正确率。现在假设决策者只 看q 单个属性，根据g 属性值的取值情况，决策者也只有5 0 的正确率。很显 然q 这单个属性对决策者来说并不能起到什么作用，c 2 、g 单个属性也类似。 而根据c ：l 的属性取值进行决策就有1 0 0 的正确率( 当c ：i 取l 时作决策1 ，否则 作决策o ) 。同样的道理，如果决策者同时用g 和c 的属性值来判断也有1 0 0 基于决策能力的属性约简模型 的正确率。 我们再看c t r ( c a rt e s tr e s u l t s ) 数据库t a b4 ： 对 c d 象ab cef g h lc4ns mhmm ah 2c6nm mhm am 3c6nmh hn 队m 4c6nm mmm am 5s4nm mmm ah 6s4ys mh hn 队h 7c4ym mhm am 8 c6nm mh am 9c4n m mham 1 0s4ns mhmm ah 决策属性值只有两个m 和h 。假设所有的决策者都是理性的，那么如果在 没有任何的条件属性的情况下，决策者会选决策属性m 作为自己的决策，从而 有6 0 的正确率。 现在假设决策者只根据单个条件属性a 的取值情况做决策： 条件属性a 有两个属性值c 和s ，从信息表可知，当属性a 的取值为c 时， 决策属性为m 的个数为6 ，为h 的个数只有l ；当属性a 的取值为s 时，决策属 性为m 的个数0 ，为h 的个数为3 。显然，决策者根据条件属性a 的取值情况进 行决策的话，就有9 0 的正确率( a 取c 时，作决策m ：a 取s 时，作决策h ) 。 同理有： 根据条件属性b 的取值情况进行决策有8 0 正确率 根据条件属性c 的取值情况进行决策有6 0 正确率 根据条件属性e 的取值情况进行决策有9 0 正确率 根据条件属性f 的取值情况进行决策有8 0 正确率 根据条件属性g 的取值情况进行决策有8 0 0 0 正确率 根据条件属性h 的取值情况进行决策有6 0 正确率 2 1 江西师范大学硕士学位论文 决策者在实际操作过程中，可能会不关心决策的所有的约简是什么，可能不 需要1 0 0 的决策正确率，也可能只想得出一个最简单的约简而已等等，这些情 况在实际操作中都是可能出现的。然而，根据以往的几种约简算法并不能满足决 策者的这些的需要。基于这些问题，提出了一种新的属性约简算法也是势在必行。 5 2 基于决策能力的属性的约简模型 定义5 2 1设s = ，a ，v f ) 是一个决策系统，其中彳= c u d ，c 是条件属性集合， d 是决策属性集合，且bcc ， 假设u b = 五，x 2 ，以 ，u i d = d l ，0 2 ，见) 。 我们定义： 原始决舡确率( 采考虑条件属证时) = 群。 属性集b 关于。晶决策主确率：薹! 兰iv ! 兰l ! 竺! 。 当b = c 时，为决策的最大正确率砧。 一为条件属性对决策的信息增益。即属性b 的加入对决正确率的影响。 k 目丑= 一k 为条件属性信息增益，即已知条件属性b 下，属性e 的加入对 决正确率的影响。 定义5 2 2 如果对c c ，有k j = 0 ，则e 为冗余属性。 定义5 2 3 如果b c 满足 k = k ； v pb ，砟 七c 则称b 为决策系统的约简。 即约简属性和原决策系统有相同的决策正确率的。 基于决策能力的属性约简模型 定义5 2 4 属性集b 关于d 的重要性定义为： s e f ? 9 ( b ) = 乏k 忑8 - k o 显然有： 性质l 如果信息系统是一致协调的，那么k = l ，否则0 七c l 。 性质2v bcc ，0 k o k 1 。 性质3v 占cc ，s g f 4 ( e ) s g f ? , f b e ) ，当双啄( e ) = 1 时，k s l = o 。 性质4 若k e = k c 则对cc 有k s l = 0 。 性质5 若k s = k 营b 为约简。 性质6 若s e f ；, w ) = 1 营b 为约简。 以上性质可以由定义直接推出。 定理1 如果b 是p a w l a k 模型下的约简，则s g f ；, ( b ) = l 。 定理2 如果b 是信息熵模型下的约简，n s g f o ( s ) = l 。 证明：如果b 是p a w l a k 模型下的约简，则b 和c 有相同的分类能力，显然 b 和c 有相同的决策正确率。即= 砧js e f ；, ( b ) = 1 。 如果b 是信息熵模型下的约简，则b 和c 有一样的信息熵，显然b 和 c 有相同的决策正确率。即s g f 4 ( b ) = 1 0 定理3 在一致决策系统中，p a w l a k 模型、信息熵模型和决策能力模型的约 简是一样的。 证明：设s = ，c o d ，v , o 是一致决策系统，则( d ) = 1 ， 假设b 是p a w l a k 模型的约简，则 iy b ( d ) = y c ( d )fh ( d l 矽= h ( d i q 【v p c b ，y p ( d ) y c ( d )【v p c b ，h ( d i 纠 = u ic ，而d c , u ic _ b u c , u c ， 所以，信息系统的约简为 c l ，c 2 ) 2 、变精度模型： 当畸1 ，二) 1 时，约简为 c l ，乞) ； j 当【o ，去) 时，约简为娩) ) 3 、信息熵模型： 江西师范大学硕士学位论文 日( c d ) = 一2 1 。g 否1 1 1 。若= l 。9 3 + 2 1 。9 2 h ( c ) = 一圭l 。g j l 一三l 。g j l 1 1 。g i i = 3 1 0 9 2 + 三l 0 9 3 h ( d i c ) = h ( c d ) 一日( c ) = 丢l 。9 3 日( c l ，c d ) = 日( c ) ，h ( di “，c 2 ) ) = h ( dlc ) 吲u c , d2 1 ，6 ， 2 ，3 ， 4 ， 5 ；，；u c 2 d = l ，4 ， 2 ，3 ，5 ， 6 ， 胃c t q ，= 一；- 。g ；一吾t 。g 三= t 。9 3 一_ 2 3l 。9 2 h ( q d ) = 一2 _ 3l 。g j l 一三l 。g 否1 = l 。9 3 + 三l 。9 2 h ( di 以 ) = h ( q d ) 一h ( q ) = l 0 9 2 h ( dic ) 础乞) ) _ 一5 1 。g 石5 一i 1l 。g 否1 = l 0 9 6 一吾l 0 9 5 h ( c 2 d ) = 一三一。g j l 一三一。g 虿1 一丢- 。g 否1 = 三3 - 。9 2 + 三- 。9 3 h ( d i c 2 ) ) = h ( c 2 d ) 一h ( c 2 ) = 5 1 。9 5 一三l 。9 2 一三l 。9 3 h ( d ic ) 由、可知 q ，c 2 为约简。 附录2 t a b 2 条件属性决策属性 病人头痛c i肌肉痛c 2体温巳 流感 1 是是正常否 2 是是高是 3是是很高是 4 否是正常否 5 否否 高 否 6 否是 很高是 7 否否 高是 8 否是 很高 否 u c d = “1 ) ， 2 ) ，