《知识获取中的rough sets理论及其应用研究》由会员分享，可在线阅读，更多相关《知识获取中的rough sets理论及其应用研究（141页珍藏版）》请在金锄头文库上搜索。
1、博博 士士 学学 位位 论论 文文 论文题目论文题目 知识获取中的知识获取中的 Rough Sets 理论及其应用研究理论及其应用研究 作者姓名作者姓名 马马 玉玉 良良 指导教师指导教师 赵光宙赵光宙 教授教授 学科学科(专业专业) 控制理论与控制工程控制理论与控制工程 所在学院所在学院 电气工程学院电气工程学院 提交日期提交日期 2005 年年 2 月月 博博 士士 学学 位位 论论 文文 知识获取中的知识获取中的 Rough Sets 理论及其应用研究理论及其应用研究 姓姓 名：名： 马马 玉玉 良良 导导 师：师： 赵光宙赵光宙 教授教授 学科学科(专业专业)：控制理论与控制工程：控制
2、理论与控制工程 浙江大学浙江大学 电气工程学院电气工程学院 2005 年年 2 月月 Research on Rough Sets Theory and Its Applications in Knowledge Acquisition A Dissertation Submitted to the Academic Committee Applying for the Degree of Doctor of Philosophy Candidate： Ma Yuliang Supervisor： Prof. Zhao Guangzhou Speciality： Control Theory
3、(DPI(|)H Q P0=，则。 PQ 证明：与定理2.3类似，故省略。 本定理说明，在两种知识相依的条件下，由它们对同一决策的互信息大小也 可以判断知识的粗糙程度。 25 信息熵对知识不确定性的测量信息熵对知识不确定性的测量 251 不确定性测量方法不确定性测量方法 信息熵对粗糙集理论中知识不确定性的测量分为基本测量、模糊测量和扩展 模型的测量三种。 1）基本测量。粗糙集理论中对知识不确定性的测量是P和Q的近似质量， 简称准则。准则及粗糙集理论的统计学基础是无差别准则（Principle of indifference） ，即认为对正域之外的元素没有任何了解。它的缺点是忽略了正域之 外对象
4、隐含的属性间不确定性关系和对数据噪声比较敏感。 针对标准的缺点，Duntsch I. 等基于信息熵最大化准则和在无差别准则上 作最小程度的模型外假设，提出三种测量信息系统和决策系统不确定性的模型， 分别为、和【Duntsch I. et al 1998】 。 ()HQd locdet( ) l HQd *( HQd) Theresa Beaubouef等利用信息熵分析粗糙集理论，尤其是粗糙关系数据模型 的不确定性【Theresa Beaubouef et al 1998】 。 2）模糊测量。Kankana C. 等讨论粗糙集理论中模糊性的测量以及该测量的 有关性质【Kankana C. et
5、al 2000】 。 3）扩展模型的测量。在粗糙集扩展模型的不确定性测量中，针对变精度粗 糙集（VPRS）模型的不确定性测量，陈湘晖等采用基于信息熵的方法构造了两 个粗糙决策规则不确定度量函数，可以兼顾由划分粒度引起的不一致性和随机性 两种不确定性，还考虑了数据中的噪声对规则一致性的影响【陈湘晖等 2001b】 。 陈湘晖等还构造了一种新的扩展粗糙集模型，给出适于数据对象具有不同重要性 31 第二章 知识粗糙性与信息的关联 情况的粗糙决策规则集合的不确定性度量【陈湘晖等 2002】 。 针对粗糙集的另外一种扩展模型相似模型，梁吉业等【Liang Jiye et al 2000】利用粗糙熵（Ro
6、ugh Entropy）测量了该模型的不确定性。 252 信息熵在粗糙集理论中的应用信息熵在粗糙集理论中的应用 信息熵在粗糙集理论中的应用包括：约简与核的计算、连续属性离散化计算 两部分。 1）约简与核的计算：对信息系统和决策系统，苗夺谦分别给出带策略的知 识约简算法，并指出其计算复杂性是多项式的。他还利用信息熵对已有的几种知 识约简算法进行分析，指出现有算法对最小简约都是不完备的【苗夺谦 1997】 。 韩斌在粗糙集约简中引入信息熵准则，克服准则对数据噪声的敏感性和不能表 达属性间概率因果关系的缺点，提出了一种粗糙集动态约简算法【韩斌 2002】 。 李玉榕等定义四种条件熵，并在此基础上提出
7、四种基于熵的粗糙集属性简约算法 【李玉榕等 2002】 。 2）连续属性离散化计算：Dougherty J. 等论述有监督和无监督的连续属性离 散化计算，提出最大熵（Maximum Entropy）离散法，定义了香农（Shannon）熵 函数， 通过迭代寻求最优的分割方案， 确保离散化过程损失最少的信息 【Dougherty J. et al 1995】 。 陈湘晖等利用基于信息熵的规则不确定性量度函数构造一个决策规 则挖掘的遗传算法，将规则挖掘与特征选取和连续属性的离散化集成在一起【陈 湘晖等 2001a】 。 基于信息熵的粗糙集算法已经被应用于许多领域，例如：模糊神经网络【杭 小树等 20
8、01】 、电力系统【张琦等 2001】 【马玉良等 2003】 、投资组合【郝善勇 等 2000】和区域产品绿色度评价等【谭光兴等 2002】 。 26 无决策时无决策时 RS 的信息表示的信息表示 粗糙集理论的最重要的功能之一是知识的约简。要进行知识约简，就必须给 出判断知识是否冗余的标准。在粗糙集理论中，判断知识冗余的思想是极其简单 的，即从知识库中将该知识去掉后，考察该知识库的分类能力是否降低。若降低 了，说明该知识是有用的；否则，该知识是冗余的。Pawlak利用代数表达式对其 32 浙江大学博士学位论文 进行了定义【Pawlak Z. 1991】 。为了后面证明两种表示等价性的需要，现
9、将代数 表示罗列如下： 定义 2.2 设U为一个论域，P为定义在U上的一个等价关系族，pP。 如果( )( )IND PpIND P=， 则称关系p在P中是不必要的 （dispensable） ； 否则， 称p在P中是必要的（indispensable） 。 不必要的关系（知识）在知识库中是冗余的。如果将它从知识库中去掉，不 会改变该知识库的分类能力。相反，若从知识库中去掉一个必要的知识，则一定 降低该知识库的分类能力。 定义 2.3 设U为一个论域，P为定义在U上的一个等价关系族。如果每个 关系pP在P中都是必要的，则称关系族P是独立的（independent） ；否则，称 P是相依的（de
10、pendent） 。 对于相依的知识库来说，其中包含有冗余知识，可以对其约简；而对于独立 的知识库，去掉其中任何一种知识都将破坏知识库的分类能力。 定义 2.4 设U为一个论域，P为定义在U上的一个等价关系族。P中所有 必要关系组成的集合，称为关系族P的核（core） ，记作CORE（P） 。 知识的核是知识库中最重要的部分。 定义 2.5 设U为一个论域，P、Q为U上的两个等价关系族，且Q。 P 如果 ( )( )IND QIND P=； Q是独立的。 则称Q是P的一个约简。 如果知识Q是知识P的约简， 那么U中通过知识P可区分的对象， 用知识Q 同样可以区分。知识的任何约简与原知识库拥有同
11、样多的知识。一般情况下，一 个知识库可能有多个约简，即知识的约简是不唯一的。知识的核与约简之间存在 如下关系： ( )( )CORE PRED P= 其中，( )RED P表示P的所有约简。 33 第二章 知识粗糙性与信息的关联 261 主要概念的信息表示主要概念的信息表示 在本小节中，我们从信息的角度对知识约简的有关概念进行定义，并对其直 观含义给以说明。 定义 2.6 设U是一个论域，P是U上的一个等价关系族，pP。如果 ， 则 称 关 系(| )0H p Pp=pP在P中 是 不 必 要 的 ； 否 则 ， 如 果 ，则称(| )0H p PppP在P中是必要的。 条件熵为零说明， 在已
12、知一种知识的条件下， 另一种知识没有提供任何信息。 因此，该知识（后者）在已知知识（前者）中是冗余的。 定义 2.7 设U是一个论域，P是U上的一个等价关系族。 如果对任意pP， 都有，则称P是独立的；否则，称P是相依的。 (| )0H p Pp 独立知识库中的每一种知识都提供一定的信息，若从中删除任一知识都将导 致总信息量的降低。对于相依的知识库来说，其中必存在着冗余信息。 定义 2.8 设U是一个论域，P是U上的一个等价关系族，且Q。如果 下列两个条件满足： P ( )( )H QH P=； 对任意的，有qQ( | )0H q Qq。 则称Q是P的一个约简。 定义中的第一个条件保证在知识约
13、简的过程中没有信息损失；第二个条件说 明，在约简中不存在冗余的信息。 262 信息表示与代数表示的等价性信息表示与代数表示的等价性 为了说明信息表示的合理性，下面我们证明信息表示和代数表示的等价性。 为此，首先证明两个引理。 引理 2.1 设U是一个论域，P、Q是U上的两个等价关系族。若 34 浙江大学博士学位论文 ( )( )IND PIND Q=，则。 ( )( )H PH Q= 证明：因为( )( )IND PIND Q=，所以，下面两式同时成立： ( )( )IND PIND Q （27） ( )( )IND PIND Q （28） 由定理2.1及公式（27）得，。 ( )( )H P
14、H Q 同理，由公式（28）得，( )( )H PH Q。 故有 ( )( )H PH Q=。 证毕 引理2.2 设U是一个论域，P、Q是U上的两个等价关系族。 若， 且（或） 。则 ( )( )H PH Q= PQPQ( )( )IND PIND Q=。 证明：因为，所以PQ( )( )IND PIND Q。 下面证明 ( )( )IND PIND Q （29） 令 12 , ( ) n A AA IND P =? U 12 , ( ) m U B BB IND Q =? 反证法，假设（29）式不成立。 则至少存在一个 0 ( ) i U A IND P ，对任何 ( ) j U B IND
15、 Q 都有 0 ij AB，。 1,2,jm=? 从而存在正整数K（） ，使得2Km 0 ij AB ， 且 0 0 0 0(|) ij ji i AB p BA A = 1 这与（210）式矛盾！故假设不成立，结论得证。 证毕 下面我们证明，无决策时的信息表示与代数表示的等价性。 定理 2.5 设U是一个论域，P是U上的一个等价关系族。 一个关系pP在 P中是不必要的充分必要条件为(| )0H p Pp=。 证明： （必要性）设pP在P中是不必要的，由定义知下式成立： ( )( )IND PpIND P= 由引理2.1可知，。 ( )(H PpH P=) P 因为 ( )( ) H PH Ppp=+ ( )(| )H PpH p Pp=+ 所以 。 (| )0H p Pp= （充分性）设 ， (| )0H p Pp= 因为
