不确定系统的信息熵与知识化简

第35卷 第3期 昆明理工大学学报(理工版) http：I／www．kustjourna1．corn／ Vo1．35 No．3 2010年6月 Journal of Kunming University of Science and Technology(Science and Technology) Jun．2010 doi：10．3969／j．issn．1007—855x．2010．03．016 不确定系统的信息熵与知识化简 曾黄麟 ，许立志 ，梁 宁 (1．四川理工学院 自动化与电子信息学院，四川 自贡643000；2．四川理工学院机械工程学院，四川 自贡643000) 摘要：根据一个不确定系统的条件属性对决策结果产生的依赖关系，建立了基于信息熵和知识重要陛 对不确定系统的知识冗余 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 的联系，得到了基于信息熵和基于Rough集理论对不确定系统的知识 冗余分析概念的统一和 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 的一致性重要结论，从信息熵的角度以统计概率的方法提出了不确定系 统的知识冗余分析新的知识简化方法，应用实例验证了本文理论和方法的可行J生和有效性． 关键词：不确定系统；Rough集；信息熵；知识约简 中图分类号：TP18 文献标识码：A 文章编号：1007—855x(2010)03—0083—06 Analysis on Information Entropy and Knowledge Simplification of an Uncertain System ZENG Huang—lin ，XV Li—zhi ，LIANG Ning (1．Institute of Automation and Electronic Information，Sichuan University of Science and Engineering，Zigong，Sichuan 643000，China； 2．Institute of Machinery Engineering，Sichuan University of Science and Engineering，Zigong，Sichuan 643000，China) Abstract：The association of information entropy and knowledge significance with knowledge redundancy in all an— certain system is set up in this paper due to the decision dependence on condition attributes．It is concluded that the analyses based on information entropy and on rough sets ale consistent in the concepts an d methods．An 印一 proach to analyzing knowledge redundancy and knowledge simplification of an uncertain system is presented on in— formation entropy．Th e theoretical analysis and the proposed method ale validated by some examples． Key words：uncertain system；rough sets；inform ation entropy；knowledge simplification O引 言 不确定系统是一种随机事件系统，不确定系统的信息处理常常从信息熵的角度以统计概率的方法分析， 但对于不确定系统中的知识冗余和知识简化往往很少从信息熵的角度讨论，大多数研究者都是从 Rough集 理论的角度进行研究，通过知识冗余分析进行知识简化 J．对于信息的不确定性，信息熵和Rough集理论 概念之间是否存在某些联系?对于不确定系统中的知识冗余和知识简化，能否建立两种方法之间的关系与 一 致性?这些问题是智能信息处理研究领域十分感兴趣的问题，但目前尚未得到明确的 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 ． 本文将从信息论中信息熵的角度出发，对于信息的不确定性，通过讨论不确定系统的条件属性对决策 结果产生的依赖关系，建立信息熵和 Rough集理论中知识的重要性之间的联系，研究基于信息熵和基于 Rough集理论对不确定系统的知识冗余分析方法的一致性，讨论基于信息熵和基于Rough集理论对于不 确定系统的知识冗余和知识简化方法的统一，从信息熵的角度以统计概率的分析方法，提出对于不确定系 统知识冗余分析新的知识简化方法． 1基本理论 一 个不确定系统常 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达为一个采集的数据信息系统S=( ，A， ，其中：U是非空有限论域，任意的 收稿日期：2009—02—23．基金项目：四川省生物技术白酒重点实验室课题(NJ2008—5)；四川省教育厅重大培育项目 (09ZXO02)． 作者简介：曾黄麟(1955一)，博士，教授，电子科技大学博士生导师．主要研究方向：人工神经网络，粗集理论，模糊逻 辑，智能信息处理，模式识别等．E—mail：zhl@suse．edu．ca 昆明理工大学学报(理工版) http：／／www．kustjourna1．corn／ 第35卷 对象 ∈U，A=C u D是属性集，c和 分别是条件属性集和决策属性．若一个不确定系统采集的数据中 条件属性为R ，i=1，2，⋯， ，V= u ． ( )是属性值的集合，对于任意属性Rj∈A，存在 ：U×A— 是 一 个信息函数． 定义1 当不可分辨关系是物种由属性集c表达时，属性集R c c，任意的对象 ，Y∈U，当且仅当 厂( ，R )= Y，R )时，Ri E R， ，Y是不可分辨的．可表达为： ind(R)= {( ， )c ：所有的 R ∈R ，R )= Y，R )} (1) 且有 [ ]础 1=n[ ]c，R c C (2) 定义2[6 设子集 ，y c ，若根据决策属性D， 和 y不可分辨时，称其为 ind(D)，表示为 u I ind(D)．根据条件属性c划分的等价类置， 中可能归入基于决策属性D划分的等价类l，的元素的集合， 表示为D的上近似集，定义为 P一(D)=u { U I ind(C)： n Y≠0} (3) 根据条件属性c划分的等价类置， 中一定能归入基于决策属性D划分的等价类y的元素的集合，表 示为 D的下近似集 ，定义为 P 一 (D)=u{ ∈UI ind(c)： Y} (4) 对于S：( ，A， 是一个决策信息系统，定义D的c正域，表示为POS。(D)，即： POSc(D)= 1．3 P_(D) (5) 系统的知识可以用决策属性D表达，也可以由条件属性c描述，根据数据库中的函数之间的依赖性关 系，知识的重要性定义为： l I—l 一( )一 -( )l ，一 R ———— 丌——一 Lo O／ 表达了一种知识的重要性，例如它可以表达利用系统参数 描述 中对象的隶属度情况，它可以代 表该特征(或特征集)对于分类的有效程度． 定义3 设S=(U，A， 是一个不确定系统，若属性 存在n种取值状态，假定一个可能事件集 合，其事件出现的概率则为p(x )，P( )，⋯，p( )．利用Shannon提出的熵的概念作为不确定信息的统 计测度，则定义属性 R 的熵为： 日(R )=一∑p(Xi)log(p(X )) (7) 定义4 设S=( ，A， 是一个不确定系统，系统决策结果被划分为m(m>1)个状态(类别)，若 属性R 在它的第i个状态时的概率为p( i)，把第 类样品点落到第i段的频率记作P(Y／Xi))，基于属性 的系统熵的期望值，则条件属性 对决策系统产生的不确定信息的统计测度，则条件熵定义为： H(D／R )=一∑p(置)∑p(Y／Xi)log(p(Y／Xi)) (8) 2不确定信息熵和知识的重要性 信息熵从统计测度的角度研究了不确定信息中条件属性对决策结果产生的依赖关系，Rough集理论 从不可分辨的角度研究了不确定信息中条件属性对决策结果产生的依赖关系，对于信息的不确定性，迄今 尚未建立信息熵和Rough集理论中知识的重要性之间的联系，尚未见讨论对于不确定系统的信息熵与 Rough集理论分析方法两种方法之间的一致性问题．因此，我们将从条件属性对决策结果产生I 依赖关系 去研究信息的不确定性和两种分析方法之间的关系与一致性． 命题1 对于一个不可分辨关系的决策信息系统S=( ，A， ，设 是一个论域，P，Q是 上的两 个属性集合，且P Q，存在下列结论： 若 ind(Q)=ind(P)，则 (Q)=日(P) (9) 证明 设P，Q在 上导出划分的等价类分别为X，Y(X={ 。， ，⋯， }，Y={】，1，y2，⋯， })，则 P，Q在 的子集组成的代数上的概率分布为： 第3期 曾黄麟，许立志，梁 宁：不确定系统的信息熵与知识化简 85 小 ) 其 ( = 1'2，⋯，Ⅳ． )= I vl 根据式(7)有： P(X2) p( ) 1 p( )J’ 1 p( )J’ ，J：1，2，⋯， ． 日(P)=一∑p(置)log(p(置))， (Q)=一∑p(Y／)log(p(Y／))，若有ind(Q)=ind(P)，则对于任意的 ( ∈{ 。， ，⋯， })存在唯一的 ( E{ ，y2，⋯， })与之对应 其中k∈[1，Ⅳ]，z∈[1， ]． 即： (Xk∈{ 。，X2，⋯， })与 ( ∈{yl， ，⋯， })存在一一对应关系． 因而有．p( = -p(yj)= ； 所以 一∑p(x )log(p(置))=一∑p(Y／)log(p( ))； 即 日(P)=日(Q)． 命题 2 对于一个以等概率分类出现的决策信息系统 S=(U，A，vJ)，在属于边界 研( )一 R 一 ( )的特征Ri的每一等价类中的对象相等地分布在m个分类中时，对于任意分类 ，特征R 减小系 统的信息熵的不确定性贡献为： ：H—H(R )： l， — 三 二 ：a Ri (1o) 证明 一个以等概率分类出现的决策信息系统，p( )=一1，k=1，2，⋯，m．则这时系统的初始熵 为： 日 =一 ㈦ ~L p(Wk)I。gmp(Wk)=一 -1ogm( )=1 令 F代表特征的等价类族，我们把 ，划分成两个不相联的子集，即： F={R1，R2，⋯，R }u {s1，s2，⋯，s } 这里每一个R 仅含有相同分类的对象．根据特征 对系统产生的不确定信息的统计测度的定义 H(R )=一∑∑p( )p( I )log胍p( I )，可得R 对系统产生的不确定信息的统计测度H(R )= 0，1≤ ≤ L． 由条件假定第i个分类出现在s 中的概率为 = ，i=1，2，⋯，m，根据特征对系统产生的不确定信息 的统计测度的定义，有 s 对系统产生的不确定信息的统计测度H(si)=1，1≤．『≤|i}．则 n + 1 圭 =1 = 砉 ⋯， 根据粗集分类的概念，因此集合 u 。s，与 ( )=一研 ( )一R ( )相同，则 ∑ I=∑ I尺 ( )一 一( )I，1≤k≤m (12) 故 卢 ：H—H(R )： 二l_ 二(_ 二 ：口 结论(9)，(1O)和(11)揭示了对于不确定系统的信息熵与Rough集理论分析方法的统一，建立了两 种方法之间的关系与一致性． 推论1 S=(U，A，va3是一个决策信息系统，条件属性R 减小系统的信息熵的不确定性的日(R )越 大，对影响系统决策的确定信息越小，则条件属性R 分类能力越弱；反之亦然． 昆明理工大学学报(理工版) http：／／www．kustjourna1．corn／ 第35卷 推论的结论是显然的，证明略． 3基于信息熵和Rough集理论新的冗余知识简化方法 设S=(U，A， 是一个不确定系统，A R ∈C，根据粗集理论 卜 ，如果存在 POSc(D)=POS~-Ri(D) =C u D是属性集，C和D分别是条件属性集和决策属性集， (13) 杯 Ri力 甲 珂 于 日J钨’峪 朗 ，台 则 Ri力 甲布H对 十 D小 口J铂’田备的． 命题1 设 U是一个论域，C，D是U上的两个属性集合，D是决策属性集．存在 H(D I C)=H(D u C)一日(C) (14) 证明 设C，D在U上导出划分的等价类分别为 ，Y( ={ 。，X2，⋯， }，Y={Yl，y2'．．”， })， 则 C，D在 U的子集组成的代数上的概率分布为： p X N y：p =【p p ：：：p ： 】， 其 (置)= l'2，⋯，Ⅳ． )= I U I小1，2，⋯ p(蒡)= ． 根据式(7)和式(8)有： 日(c)：一∑N p( )1。g(p( )) ， i=I 肼 H(D)=一 p( g(p( ))， ( )=一薹p(置)薹P(薯)l。g(P( )) 令A=C u D，则A在 U上导出的划分的等价类为Z，即对X(或对 y)的细分． z ：f 置， n置≠咖， ：1，2，⋯，t； 、忽略 ， n X = 则 ． 根据式(7)有 日(A)=H(C U D)=一塞p(z )l。g(p(z ))=一窆i=1 j兰=l l。g( ) 因为 塞 f)l0g( 一兰i=1丽I Xi l log( ) = 一 耋j塞=l ·。g( )一耋p( )log(p( )) = 一 耋 耋 c 一毫 c = 一 耋 {[耋 l0g( log( )} 其 og( )=~OS(T --ff—i-)· H(A)一H(C)=H(D u C)一H(C) n Xi ∑ 第3期 曾黄麟，许立志，梁 宁：不确定系统的信息熵与知识化简 87 = 一 耋删Xi j塞=l c c ·y塞=l = 一 耋pc置 耋 c = 一 ∑p(置)∑p( )log(p( ) i=l f-l i i ( ) 证明完毕． 命题2 设S=(U，A，v,o0是一个不确定系统，A=C u D是属性集，c和D分别是条件属性集和决 策属性集，R ∈C，如果存在 (D I C)=日(D I C一足) (15) 称 为 C中相对于D可省略的，否则 为 C中相对于 D不可省略的． 证明 首先令 U l ind(C)={ 。， ，⋯， }， I ind(D)={y1，y2，⋯，ym}． 因为论域 是在 c上相对于D一致的，即POSc(D)= 所以 I ind(C)是 U I ind(D)的细分，有 I ind(C+D)=U I ind(C)={Xl，X2，⋯， }， 日( )=一∑p(xi)∑p( I置)log(p( I X ))=0 必要性：假设属性 是 C中相对决策属性 D不必要的，则 POS 墙(D)=POSc(D)=U，所以 l ind(C—R )是 Ul ind(D)的细分． 令 I ind(C—R +D)=U I ind(C—Rf)={z1，z2，⋯，zK}，则 H(D I c一 )=一∑p(Z )∑p( l Z )log(p( I zi))=0， 故 日(D l C)=日(D l c一尺 )． 充分性 ：假设 POSc墙(D)≠U=POSc(D) 令 U I ind(C—R )={z ，z2，⋯， }，则至少存在 ，Z ∈U I ind(C— )，且 。， ∈UI ind(D) 和 ， ∈U l ind(D)， 。≠ ，使得互n 。≠0，且 n ≠0， 因此日( 一Ri)=一∑p(Z )∑p( I Zi)log(p( l ))>0 这与H( )=H(D I C—R )=0相矛盾，假设 POS (D)≠U不成立． 故有 POSc (D)=POSc(D)=U 根据式(14)，故 为 C中相对于 D可省略的． 证明完毕． 根据命题2，若属性 ，弓∈c，X-， ，⋯， 是基于薏等价类， ，y2，⋯，ym是基于薏的等价类，则相 应的信息熵满足： 日( 一 )：Ⅳ( 一 ) (16) 并且对于任何一个 都有与之相对应的 ，使得 POSc _ R~( )=POS ( ) (17) 其中：Xk∈Xl，X2，⋯，X ， ∈Yl，y2，⋯，ym． 则：属性足和属性R，粗等价，即知识 ，尺，对于系统来说至少有一个为冗余属性． 这里从信息熵的角度以统计概率的方法解决了对于不确定系统中的知识冗余和知识简化问题． 下面我们从Rough集理论和信息熵的角度出发，考察一个知识系统(数据见表1) 的知识冗余和知 昆明理工大学学报(理工版) http：／／www．kustjourna1．corn／ 第35卷 识约简，来验证本文的理论和方法的可行性和有效性． 这里，条件属性集 C = { ， ，R，}，决策属性为 D = D． 因为 l C={{ }，{ ：}，{ ，}，{ }，{ }，{ }}， I D={{ }，{ }，{ ，}，{ }，{ }，{ }}， J C={{ 。}，{ }，{ ，}，{ }，{ }，{ }}， 有 I(c —R ) = {{ 。}，{ }，{ 。}，{ }， { }，{ }l， U I(C—R，)={{ }，{ ：}，{ }，{ }，{ }，{ }}． 条件属性 ：或R 对于系统来说，至少有一个为冗余 的，可省略其中的一个属性来简化系统． 表 1 一个知识系统的数据表 Tab．1 A data table of a knowledge system 根据H(D I c—R2)=一∑p(xi)∑p( I )log(p( l Xi))=0 l 1 J 1 6 6 H(D l c～R，)=一∑p(x )∑p( I Xi)log(p( I Xi))=0 ￡=1 J 1 且有 POSc ( )=POSc喝(y=f)． 条件属性R：或 ，对于系统来说，至少有一个为冗余的，可省略其中的一个属性来简化系统． 上述分析表明，我们提出的基于信息熵和基于Rough集理论方法来分析知识冗余和知识简化两种方 法得到的结果是一致的． 4 结 论 对于一个不确定系统，可以从统计测度的角度研究系统的不确定信息，也可以基于 Rough集理论研究 系统的不确定信息．根据一个不确定系统的条件属性对决策结果产生的依赖关系，我们对知识冗余和知识 简化进行深入分析，研究了基于信息熵和基手Rough集理论知识冗余和知识简化两种方法之间的关系与 一 致性，得出： 1)首次建立了不确定系统知识冗余分析和知识简化方法的统一； 2)从信息熵的角度，以统计概率的分析方法提出了不确定系统的知识冗余分析新的知识简化方法． 参考文献： 、 [1]Pawlak Z．Some issues on rough sets[C]／／Swiniarski B，Szczuka R W，eds．Transactions Oil Rough Sets．Springer—Verlag， Berlin。2004：1—58． [2]曾黄麟．智能计算——关于粗集、模糊、人工神经网络理论及其应用[M]．重庆：重庆大学出版社，2004：1—60． [3]Qing Shen．Attribute Reduction of Multi—v~ued Information System Based on Conditional Information Entropy[C]／／Proceed— ings of IEEE International Conference on Granular Computing，China，Aug．2008：562—566． [4]Huanglin Zeng，Xiaohui Zeng．Redundant Data Processing Based O11 Rough—Fuzzy Approach[J]．Rough Sets and Knowledge Technology，Springer—Verlag Berlin Heidelberg，Germ any，2006：156—161． [5]Huanglin Zeng，Xiaohui Zeng．Studies on consistence of the knowledge simplification of an uncertain system[C]／／Proceeding of 8Il1 International Conference on Cognitive Informaties，HongKong，2009：162—166． [6]Huanglin Zeng，Xiaohui Zeng．Reasoning Decision Rules of an Uncertain System[C 3／／The Fourth International Conference Oil Rough Sets and Knowledge Technology，Proceeding of RSKT 2OO9，Aus~alia，Springer—Verlag Berlin Heidelberg，2009：634—642． [7]Huanglin Zeng，Yan Huang，Xiaohui Zeng．A New Approach of Attribute Reduction Based on Ant Colony Optimization[C]／／ Proceeding of Fifth International Conference On Natural Computation 2009(3)：3—7． [8]叶全明，胡学钢．一种基于属性重要性的属性约简启发式算法[J]．计算机科学，2008，35(8A)：28-29． [9]张海云，梁吉业．一种基于划分的决策表属性约简算法[J]．计算机科学 ，2008，35(8A)：18—21． [10]靳孝方，祝峰，等．改进的基于属性重要度的决策表属性约简算法[J]．计算机科学，2009，36(8A)：4—7． [11]李磊军，米据生．信息系统属性约简的比较研究[J]．计算机科学，2009，36(8A)：42—44． [12]刘静，米据生．概率信息系统的属性约简[J]．计算机科学，2009，36(8A)：45—48．