1、第36卷第2期2023年6月Vol.36 No.2Jun.2023闽南师范大学学报（自然科学版）Journal of Minnan Normal University（Natural Science）新条件熵下协调不完备的信息系统属性约简孙亚超1,陈锦坤1,2*,金铭1（1.闽南师范大学数学与统计学院,福建 漳州 363000；2.闽南师范大学 福建省粒计算及其应用重点实验室,福建 漳州363000）摘要：针对不完备信息系统的属性约简方法较少考虑含有缺失对象集对决策类造成的影响问题,根据缺失对象集含有的对象不同,给出一种新的条件熵,用来更加精确地度量知识的不确定性.其次给出了在协调不完备信息系
2、统下关于该新条件熵的相关定理,并构造了一种基于新条件熵的属性约简算法.最后,通过实例证明了该算法的可行性.关键词：条件熵；属性约简；不完备信息系统中图分类号：TP181 文献标志码：A 文章编号：2095-7122（2023）02-0017-10Attribute reduction of consistent incomplete information systemsbased on new conditional entropySUN Yachao1,CHEN Jinkun1,2,JIN Ming1(1.School of Mathematics and Statistics,Minna
3、n Normal University,Zhangzhou 363000,China;2.Fujian Key Laboratory of Granular Computing and Applications,Minnan Normal University,Zhangzhou 363000,China)Abstract:Attribute reduction methods of incomplete information systems seldom consider the impact of missing object sets on decision classes.To so
4、lve this problem,a new conditional entropy is proposed according to the different objects in the missing object set,which is used to measure the uncertainty of knowledge more accurately.Secondly,the related theorems about the new conditional entropy in the coordination incomplete information system
5、are given,and an attribute reduction algorithm based on the new conditional entropy is constructed.Finally,an example is given to prove the feasibility of the algorithm.Key words:conditional entropy;attribute reduction;incomplete information systems粗糙集理论1-2是由Pawlak提出的,是一种能有效处理不精确、不完整和模糊信息的数学工具,已被成功应
6、用到决策支持、图像处理、数据挖掘等方面.近年来,许多专家学者以粗糙集理论为基础进行了大量的属性约简算法研究,这些研究可以分为两类:一类是基于代数的属性约简算法.首先由Hu3提出的基于正域的属性约简算法和Skowron4提出的基于辨识矩阵的属性约简算法;后来研究者对这两种约简算法进行改进,即有张玉等5以变精度粗糙集为背景,提出基于极大正域的属性约简;陈志恩等6对可辨识矩阵进行改进,得到以最大分布核属性集为起点,然后对其余属性按其在可辨识属性矩阵中出现的频数大小逐次添加到核属性集中的属性约简算法.另一类是由王国胤7提出的基于信息论的属性约简算法.唐鹏飞等8以集值决策表为背景进行改进,提出基于近似条
7、件熵的属性约简.以上专家学者是在不含有缺失值的信息系统（也称为完备的信息系统）中进行研究的.收稿日期：2022-12-26基金项目：国家自然科学基金项目(62076116);福建省自然科学基金项目(2020J01792,2021J02049).作者简介：孙亚超(1997),男,山东菏泽人,硕士生.*通信作者.E-mail:2023年闽南师范大学学报（自然科学版）上述研究都是以完备信息系统为研究对象,但在现实生活中,由于不确定性因素或者条件限制等原因会造成属性值缺失,使得以上研究在信息系统含有缺失值的情况下不能完全适用.基于此,Kryszkiewicz9在1997年通过考虑信息系统中含有缺失属性
8、值,首先提出了基于容差关系的不完备信息系统的属性约简.紧接着Stefanowski10提出了基于非对称相似关系的不完备信息系统的属性约简,随之又研究提出基于量化容差关系的不完备信息系统的属性约简.后来王国胤11把上述3种关系进行融合改进,提出了基于限制容差关系的不完备信息系统的属性约简.后续专家学者又在以上众多模型下进行研究得到新的不完备信息系统的属性约简算法.如姚晟等12提出的非平衡数据下不完备信息系统的属性约简,丁棉卫等13提出的基于二进制区分矩阵的不完备信息系统的增量式属性约简,Li等14利用属性值之间的相似度,提出基于-属性重要度的约简算法.随着三支决策思想的提出,文献15-19提出了
9、基于三支决策的不完备信息系统的属性约简算法.文献20-22中以信息量为启发信息,设计了以信息熵为启发信息的不完备信息系统的属性约简算法,滕书华等23虽然提出基于条件熵的前向添加启发式约简算法,但是没有单纯的考虑缺失对象集这一因素对决策类造成的影响.滕书华等23的属性约简算法中没有考虑缺失对象集对决策类造成的影响,当两个及以上属性的条件熵值相等的情况下如何选取属性.因此针对这一问题,在滕书华等23的基础上考虑了缺失对象集对决策类的影响,重新定义了条件熵的概念,通过实例得出了新的条件熵可以解决当两个属性的条件熵值相等的问题;其次通过新的条件熵给出了在协调的不完备信息系统上的一些主要结论;然后从条件
10、熵出发,设计出基于新条件熵的协调不完备信息系统的属性约简算法;最后通过实例证明了算法的有效性.1 基本概念定义定义124 设信息系统S=(UAVf),其中U是非空有限对象集.A=CD是非空有限属性集,C是条件属性集,D是决策属性集,CD.V=aAVa是属性值的集合,Va是属性a的值域,f:UAV表示属性到值域的一个映射,即对任意的aA,xU,都有f(xa)Va.如果信息系统中至少存在一个属性a,使得Va是一个空值,用*表示空值,即f(xa)=*,则称其信息系统是不完备信息系统.定义定义 224 在不完备信息系统S=(UAVf)中,A=CD,BC,记缺失值为“*”,*V=aAVa,对于aB,容差
11、关系定义为T(xixj)=(xixj)UU|f(xia)=*f(xja)=*f(xia)=f(xja).显然,容差关系满足自反性(xixi)T(xiU),以及对称性,即当(xixj)T时(xjxi)T(xixjU),但不满足传递性(xixj)T(xjxk)T则(xixk)T(xixjxkU).由此可以继续定义容差类为TB(xi)=xj|xjUTB(xixj).从而可以定义论域U对属性A的划分覆盖为A=U/T(A)=TA(x1)TA(x2)TA(x|U|).其中:U=x1x2x|U|,|U|表示集合U的基数.相应的上、下近似集定义为-TBX=xi|TB(xi)X，-TBX=xi|TB(xi).定
12、义定义324 在不完备信息系统S=(UAVf)中,属性集A=ak|k=1m,设xiU,对象xi的缺失属性集MASi和不完备信息系统S的缺失对象集MOS可定义为MASi=ak|ak(xi)=*k=1m，MOS(x)=i|MASii=1n.18孙亚超，等：新条件熵下协调不完备的信息系统属性约简第2期定义定义49 在不完备信息系统S=(UAVf)中,A=CD,BC,S中的广义决策函数定义为B：UVdBCB(xi)=f(dxj)|xjTB(xi).若xiU|C(xi)|=1,则称不完备信息系统是协调的,否则是不协调的.定义定义59 给定一个不完备信息系统S=(UAVf),A=CD,EBC,对于xiU,
13、都有B(xi)=C(xi),且对于任意EB,$xiU,E(xi)C(xi),则称B为约简集.定义定义625 给定一个不完备信息系统S=(UAVf),A=CD,BC,记B=U/T(B)=TB(x1)TB(x2)TB(x|U|)，D=U/T(D)=TD(x1)TD(x2)TD(x|U|)，U/RD=D1D2Dn.其中:Di=xi1xi2xisi,|Di|=si,i=1m|Di|=|U|.则有mB(xi)=maxD(Di|TC(xi)：in，xiU，其中:D(E|F)=|EF|F|是包含度.最大决策函数B为B(xi)=Di|D(Di|TC(xi)=mB(xi)，xiU.若对于任意xiU有B(xi)=
14、A(xi)成立,则称B是S的最大分布协调集.若B是最大分布协调集,且B的任何真子集都不是S的最大分布协调集,称B是S的最大分布约简集.定义定义726 给定一个不完备信息系统S=(UAVf),PQA,若xiUTP(xi)TQ(xi),则称Q是粗于P的,记作P-Q;如果P-Q,PQ,则称Q是严格粗于P的,记作PQ.因此,PQ当且仅当xiUTP(xi)TQ(xi),$xjUTP(xj)TQ(xj).所以QP当且仅当P-Q.定义定义 826 给定一个不完备信息系统S=(UAVf),A=CD,若S是协调不完备信息系统当且仅当C-D.因此,由定义5、8可得,当不完备信息系统是协调时,等价于xiU,TC(x
15、i)TD(xi);当B为约简集时,等价于xiU,有TC(xi)TD(xi),TB(xi)TD(xi),且对EB,$xiU有TE(xi)TD(xi).2 不完备信息系统的条件熵定义定义927 在不完备信息系统S=(UAVf)中,A=CD,属性集BC的信息熵定义为E(B)=1-i=1|U|TB(xi)|U|2.属性集BC的联合信息熵定义为E(DB)=1-i=1|U|TD(xi)TB(xi)|U|2.定义定义1023 在不完备信息系统S=(UAVf)中,A=CD,BC,关于决策属性D相对于条件属性集B的条件信息熵定义为E(D|B)=i=1|U|TB(xi)|-|TB(xi)TD(xi)|U|2.注注
16、1 当xiU,TD(xi)=U时,E(D|B)取最小值0;当xiU,TB(xi)=U,TD(xi)=xi时,E(D|B)取最大值1-1|U|.192023年闽南师范大学学报（自然科学版）例例1 表1给定一个不完备决策表S=(UCDVf),其中论域U=x1x2x3x4x5x6x7,条件属性C=c1c2c3c4,决策属性D=d.由表1可知根据属性c1得到的容差类为 Tc1(x1)=x1x3x4x5，Tc1(x2)=x2x3x5x6x7，Tc1(x3)=x1x2x3x4x5x6x7，Tc1(x4)=x1x3x4x5，Tc1(x5)=x1x2x3x4x5x6x7，Tc1(x6)=x2x3x5x6x7，
17、Tc1(x7)=x2x3x5x6x7.根据属性c2得到的容差类 Tc2(x1)=x1x2x3x4x5x6，Tc2(x2)=x1x2x3x4x5x6x7，Tc2(x3)=x1x2x3x4x5x6x7，Tc2(x4)=x1x2x3x4x5x6x7，Tc2(x5)=x1x2x3x4x5x6x7，Tc2(x6)=x1x2x3x4x5x6，Tc2(x7)=x2x3x4x5x7.根据属性c3得到的容差类 Tc3(x1)=x1x2x3x4x5x6x7，Tc3(x2)=x1x2x3x4x5x6x7，Tc3(x3)=x1x2x3x4x5x6x7，Tc3(x4)=x1x2x3x4x5x6x7，Tc3(x5)=x1
18、x2x3x4x5x6x7，Tc3(x6)=x1x3x4x5x6x7，Tc3(x7)=x1x2x3x4x5x6x7.根据属性c4得到的容差类 Tc4(x1)=x1x2x6x7，Tc4(x2)=x1x2x6x7，Tc4(x3)=x3x4x5x6x7，Tc4(x4)=x3x4x5x6x7，Tc4(x5)=x3x4x5x6x7，Tc4(x6)=x1x2x3x4x5x6x7，Tc4(x7)=x1x2x3x4x5x6x7.由决策属性d所得的容差类 Td(x1)=x1x4x6，Td(x2)=x2x3x7，Td(x3)=x2x3x7，Td(x4)=x1x4x6，Td(x5)=x5，Td(x6)=x1x4x6，
19、Td(x7)=x2x3x7.由定义10可得E(d|c1)=i=1|U|Tc1(xi)|-|Td(xi)Tc1(xi)|U|2=i=17|Tc1(xi)|-|Td(xi)Tc1(xi)|72=0.449.同理可得:E(d|c2)=0.531,E(d|c3)=0.571,E(d|c4)=0.449.因而可得E(d|c3)E(d|c2)E(d|c1)=E(d|c4).由例1可知:不仅属性c1和c4相对于决策属性d的条件熵值相等,而且在两个属性下含有缺失值的对象个数也相等;如果按照滕书华等23的条件熵约简算法,则从这两个属性中随机选择一个,有可能导致选择的属性约简不是最优的.然而,从表1可以看出,对于
20、属性c1和c4中含有缺失值的对象个数都为2,但属性c1中缺失值所对应的决策类为d=3或d=1,而在属性c4下的两个缺失值所对应的决策类为d=1或d=2.而d=3所对应的对象仅有x5.因此在实际问题中,对于c1和c4两个属性,更倾向于选择属性c1.表1 不完备决策表Tab.1 Incomplete decision tableUx1x2x3x4x5x6x7c121*2*11c22*21c3*1*2*c411222*d211232120孙亚超，等：新条件熵下协调不完备的信息系统属性约简第2期在实际问题中,希望尽可能选择缺失值带来影响更少的属性.因此,从缺失对象集上对条件熵的定义进行改进.定义定义1
21、1 给定一个不完备信息系统S=(UAVf),其中U=x1x2x|U|,A=CD,BC,则条件属性集B相对于决策属性集D的新条件熵定义为:H(D|B)=i=1|U|(1-|MOS(x)TD(xi)|U|)|TB(xi)|-|TD(xi)TB(xi)|U|2.注注2 由于引入缺失对象集,新条件熵H(D|B)和联合信息熵H(DB)、信息熵H(B)三者之间没有关系,即不满足H(D|B)=H(DB)-H(B).例例2 根据不完备决策表1得:H(d|c1)=i=1|U|(1-|MOS(x)Td(xi)|U|)|Tc1(xi)|-|Td(xi)Tc1(xi)|U|2=i=17(1-|MOS(x)Td(xi)
22、|7)|Tc1(xi)|-|Td(xi)Tc1(xi)|72=0.408.同 理 可 得:H(d|c2)=0.426,H(d|c3)=0.437,H(d|c4)=0.397.因 此 可 得H(d|c3)H(d|c2)H(d|c1)H(d|c4),即对于不同属性下的缺失对象集不同,所得的条件熵的值不同,对不完备信息系统的分类能力也不同.注注3 当MOS(x)TD(xi)=时,H(D|B)=i=1|U|TB(xi)|-|TD(xi)TB(xi)|U|2,则定义11可以退化成定义10.引理引理1 给定一个不完备信息系统S=(UAVf),A=CD,对xiU,BC,则有MOSB(x)MOSC(x).证明
23、证明 由定义3知,显然引理成立.定理定理1 给定一个不完备信息系统S=(UAVf),A=CD,BC,则H(D|C)H(D|B).证明证明 因为BC,则由定义 6 和引理 1 得,对xiU,有MOSB(x)MOSC(x),TC(xi)TB(xi).即有MOSB(x)TD(xi)MOSC(x)TD(xi),TD(xi)TC(xi)TD(xi)TB(xi),则有|TC(xi)|TB(xi)|，|MOSB(x)TD(xi)|MOSC(x)TD(xi)|，|TD(xi)TC(xi)|TD(xi)TB(xi)|.从而有|MOSB(x)TD(xi)|U|MOSC(x)TD(xi)|U|，|TB(xi)|-|
24、TC(xi)|-|TD(xi)TB(xi)|-|TD(xi)TC(xi)|=|TB(xi)|-|TC(xi)|-|TD(xi)TB(xi)-TC(xi)|0.则有1-|MOSC(x)TD(xi)|U|1-|MOSB(x)TD(xi)|U|，|TC(xi)|-|TD(xi)TC(xi)|U|2|TB(xi)|-|TD(xi)TB(xi)|U|2，即(1-|MOSC(x)TD(xi)|U|)|TC(xi)|-|TD(xi)TC(xi)|U|2(1-|MOSB(x)TD(xi)|U|)|TB(xi)|-|TD(xi)TB(xi)|U|2.所以有H(D|C)H(D|B),证毕.定理定理 2 给定一个不
25、完备信息系统S=(UAVf),其中U=x1x2x|U|,A=CD,PC,QC,如果xiU,TP(xi)=TQ(xi),MOSP(xi)=MOSQ(xi),则有H(D|P)=H(D|Q).证明证明 如果xiU,TP(xi)=TQ(xi),MOSP(xi)=MOSQ(xi),则有MOSP(xi)TD(xi)=MOSQ(xi)TD(xi)，TP(xi)TD(xi)=TQ(xi)TD(xi)，212023年闽南师范大学学报（自然科学版）即|TP(xi)|-|TD(xi)TP(xi)|U|2=|TQ(xi)|-|TD(xi)TQ(xi)|U|2，|MOSP(x)TD(xi)|U|=|MOSQ(x)TD(
26、xi)|U|，从而可得H(D|P)=H(D|Q),证毕.定理定理3 给定一个不完备信息系统S=(UAVf),A=CD,如果对于任意BC,则有:1)H(D|B)=0当且仅当B-D;2)H(D|B)=1-1|U|当且仅当xiUTB(xi)=U,|TD(xi)|=1MOS(x)=;3)0H(D|B)1-1|U|.证明证明 1)“”若B-D,则由定义 7 可知对xiU,有TB(xi)TD(xi),则有TB(xi)TD(xi)=TB(xi),即|TB(xi)|-|TB(xi)TD(xi)|=0,从而可得H(D|B)=0.“”如果B-D不成立,则存在xixjU,使得当xixjTB(xi)时,f(dxi)T
27、D(xi)和f(dxj)TD(xi)两式不会同时成立,即TB(xi)TD(xi),TD(xi)U,从而使得|TB(xi)|-|TB(xi)TD(xi)|0,MOSB(x)TD(xi)U,即会导致H(D|B)0,这与原始条件矛盾,故B-D.2)“”若xiUTB(xi)=U|TD(xi)|=1MOS(x)=,则有H(D|B)=i=1|U|(1-|TD(xi)|U|)(|U|-1|U|2)，即H(D|B)=i=1|U|(|U|-1|U|2),从而得H(D|B)=1-1|U|.“”若H(D|B)=1-1|U|,则对于xiU,要使得i=1|U|(1-|MOS(x)TD(xi)|U|)和i=1|U|TB(
28、xi)|-|TB(xi)TD(xi)|U|2同 时 取 最 大 值 才 能 满 足H(D|B)取 最 大 值.当i=1|U|(1-|MOS(x)TD(xi)|U|)取 最 大 值 时,则 有|MOS(x)TD(xi)|=0,即MOS(x)TD(xi)=;当i=1|U|TB(xi)|-|TB(xi)TD(xi)|U|2取最大值时,即有|TB(xi)|-|TB(xi)TD(xi)|取最大值.又由定义10,可知i=1|U|TB(xi)|-|TB(xi)TD(xi)|U|2最大值为1-1|U|,从而有|TB(xi)|-|TB(xi)TD(xi)|=|U|-1,即TB(xi)=U|TD(xi)|=1,因
29、此可得TD(xi)=xi,又需要满足MOS(x)TD(xi)=,所以MOS(x)=.综上所述当H(D|B)=1-1|U|,则有xiUTB(xi)=U,|TD(xi)|=1MOS(x)=.3)由1)和2)可得0H(D|B)1-1|U|.证毕.根据定理3 1)式可知,协调的不完备信息系统与条件熵有以下关系.推论推论 1 给定一个不完备信息系统S=(UAVf),A=CD,如果S是协调不完备信息系统当且仅当H(D|C)=0.证明证明 “”若H(D|C)=0,则对xiU,满足MOS(x)TD(xi)=U或者|TC(xi)|-|TC(xi)TD(xi)|=0.假设MOS(x)TD(xi)=U,即MOS(x
30、)=U且TD(xi)=U,所以对于任意TC(xi)都满足TC(xi)TD(xi).再假设|TC(xi)|-|TC(xi)TD(xi)|=0,即有TC(xi)TD(xi);所以xiU,无论是满足MOS(x)TD(xi)=U还是满足|TC(xi)|-|TC(xi)TD(xi)|=0,都可以得到TC(xi)TD(xi).因此,根据定义7和定义8可得S是协调不完备信息系统.“”如果S是协调不完备信息系统,根据定义 8 得C-D.再根据定义 7 可知对xiU,有22孙亚超，等：新条件熵下协调不完备的信息系统属性约简第2期TC(xi)TD(xi),即有TC(xi)TD(xi)=TC(xi),从而|TC(x
31、i)|-|TC(xi)TD(xi)|=0,即得H(D|C)=0.证毕.协调的不完备信息系统的约简集和条件熵有以下关系.定理定理 4 给定一个协调不完备信息系统S=(UAVf),A=CD,BC,若B是约简集当且仅当cmBH(D|B-cm)0,H(D|B)=0.证 明证 明 “”若B是 约 简 集,则 有xiU,TB(xi)TD(xi);cmB,$xiU,TB-cm(xi)TD(xi).假 设cmB,H(D|B-cm)=0,则 有MOS(x)TD(xi)=U或 者|TB-cm(xi)|-|TB-cm(xi)TD(xi)|=0.若MOS(x)TD(xi)=U,则满足MOS(x)=TD(xi)=U,即
32、xiU,cmB,TB-cm(xi)TD(xi)与B是约简集矛盾,则MOS(x)TD(xi)U;若|TB-cm(xi)|-|TB-cm(xi)TD(xi)|=0,即TB-cm(xi)TD(xi)与B是约简集矛盾,所以满足cmBH(D|B-cm)0.又xiU,TB(xi)TD(xi),则得|TB(xi)|-|TB(xi)TD(xi)|=0,所以H(D|B)=0.“”由H(D|B)=0可得MOS(x)TD(xi)=U或者|TB(xi)|-|TB(xi)TD(xi)|=0,则需要满足MOS(x)=TD(xi)=U或 者 满 足TB(xi)TD(xi).那 么 假 设MOS(x)=TD(xi)=U,则
33、对 于xiU,cmB,都 有TB-cm(xi)TD(xi),从而有H(D|B-cm)=0这与题意矛盾,即MOS(x)=TD(xi)=U不成立,那么就得TB(xi)TD(xi);又由cmBH(D|B-cm)0得$xiU,TB-cm(xi)TD(xi),故可得B是约简集.证毕.定理定理4 只考虑了条件熵与约简集的关系,然而对于一个不完备信息系统而言,约简方式并不唯一.因此,下面的定理给出了条件熵与其他约简集的关系.定理定理5 给定一个协调不完备信息系统S=(UAVf),A=CD,BC,则以下命题等价:1)B是约简集;2)cmBH(D|B-cm)0,H(D|B)=0;3)B是S=(UAVf)的最大分
34、布约简.证明证明 1)2)由定理4可证.2)3)由定理 4 可得,当cmBH(D|B-cm)0,H(D|B)=0可知B是C的约简集.因此xiU,有B(xi)=C(xi),从而有mB(xi)=mC(xi),即B(xi)=C(xi),于是B是S=(UAVf)的最大分布协调集.又由于cmB,$xiU有B-cm(xi)C(xi),则得mB-cm(xi)mC(xi),B-cm(xi)C(xi),从而B的任何真子集都不是S=(UAVf)的最大分布协调集,所以B是S=(UAVf)的最大分布约简.3)1)由B是S=(UAVf)的最大分布约简,可得xiU,B(xi)=C(xi),mB(xi)=mC(xi),B(
35、xi)=C(xi);cmB$xiUB-cm(xi)C(xi),mB-cm(xi)mC(xi),B-cm(xi)C(xi),又不完备信息系统S=(UAVf)是协调的,即对于xiU,有TC(xi)TD(xi),TB(xi)TD(xi);对cmB,$xiU,有TB-cm(xi)TD(xi)，所以B是C的约简集.证毕.协调的不完备信息系统的核心属性与条件熵的关系如下.定理定理 6 给定一个协调不完备信息系统S=(UAVf),A=CD,cm是核心属性当且仅当H(D|C)H(D|C).“”因为不完备信息系统S=(UAVf)是协调的,即得TC(xi)TD(xi).由推论1可得H(D|C)=0,所以当H(D|
36、C)H(D|C-cm)时,由 定 理 3 可 得0H(D|C-cm)1-1|U|,那 么 有H(D|C-cm)0,所 以232023年闽南师范大学学报（自然科学版）MOS(x)TD(xi)U和|TC-cm(xi)-(TC-cm(xi)TD(xi)|0这两个条件必须同时满足.则对xiU,有TD(xi)U,对$xiU,有TC-cm(xi)TD(xi),从 而C-cm(xi)C(xi).对 于cmBBC-cmC,则B(xi)C(xi),于是当cmB时,B不可能是C的约简集,所以cm是核心属性.证毕.3 基于新条件熵的属性约简算法在不完备信息系统S=(UAVf)中,由定理1可知,条件熵值随着条件属性集
37、的增大而减小,满足单调性.因此当条件属性c相对于决策属性D的条件熵H(D|c)越大时,说明条件属性c对决策属性D的影响就越小,该属性就越可能被删除.基于此,接下来给出基于新条件熵的属性约简算法.算法算法 基于新条件熵的不完备信息系统的属性约简.输入:不完备信息系统S=(UAVf).输出:该不完备信息系统的约简reduction.步骤步骤1 计算H(D|C),令reduction=C.步骤步骤2 计算每个ckC的条件熵值H(D|ck),根据条件熵值从大到小进行排序,按照顺序选择最大的条件熵值H(D|ck)所对应的ck,然后把ck从reduction中删除.步骤步骤3 计算H(D|reductio
38、n-ck),假如H(D|reduction-ck)0,则reduction=reduction-ck,继续转到步骤2;否则输出reduction.步骤步骤4 输出reduction.由算法可知步骤1的时间复杂度是O(|U|),步骤2的时间复杂度是O(|U|C|),步骤3的时间复杂度是O(1),步骤4的时间复杂度是O(1).当约简集为属性全集时,算法时间复杂度最高,最高是O(12|U|C|2),所以基于新条件熵的属性约简算法的时间复杂度是O(12|U|C|2).4 实例分析为更好的说明新条件熵的有效性,以下给出一个例子进行分析说明.不完备信息系统如表2所示.例例 3 表 2 给定一个不完备决策表
39、S=(UCDVf),其中论域U=x1x2x3x4x5x6,条件属性C=c1c2c3c4,决策属性D=d.1)根据表2得到:TC(x1)=x1，TC(x2)=x2x6，TC(x3)=x3x5，TC(x4)=x4，TC(x5)=x3x5，TC(x6)=x2x6，Td(x1)=x1x2x4x6，Td(x2)=x1x2x4x6，Td(x3)=x3x5，Td(x4)=x1x2x4x6，Td(x5)=x3x5，Td(x6)=x1x2x4x6.所以xiU,都有TC(xi)Td(xi),即得表2不完备信息系统是协调的.2)根据1)式可知表2是协调的不完备信息系统,所以可得H(d|C)=0.令B=reducti
40、on=C.3)H(d|c1)=0.3056,H(d|c2)=0.2917,H(d|c3)=0.1852,H(d|c4)=0.2037.表2 不完备决策表Tab.2 Incomplete decision tableUx1x2x3x4x5x6c121*221c21*12c3*1313c411222*d22121224孙亚超，等：新条件熵下协调不完备的信息系统属性约简第2期4)计算H(d|B-c1)=0=H(d|C),于是B=B-c1=c2c3c4;计算H(d|B-c2)=0=H(d|C),于是B=B-c2=c3c4;计算H(d|B-c3)=0.185 2H(d|C),所以约简B=c3c4;所以约
41、简reduction=c3c4.5)B=c3c4是不完备信息系统的一个约简.接下来验证B=c3c4是否是不完备信息系统的约简集.当B=c3c4时,有TB(x1)=x1x2,TB(x2)=x1x2,TB(x3)=x3x5,TB(x4)=x4x6,TB(x5)=x3x5,TB(x6)=x4x6,即对xiU,都有TB(xi)Td(xi);当B1=c3时,则有TB1(x1)=x1x2x3x4x5x6,使得TB1(x1)Td(x1),即B1不是约简集.当B2=c4时,则有TB2(x3)=x3x4x5x6,使得TB2(x3)Td(x3),即B2不是约简集.因此xiU,都有TB(xi)TD(xi),而对于B
42、的任意真子集B1和B2,则$xiU,使得TB1(xi)TD(xi),TB2(xi)TD(xi),所以B=c3c4是表2的不完备信息系统的约简集.5 结束语首先通过缺失对象集定义不完备信息系统中的一个新条件熵,以新的条件熵为基础,给出并证明了在协调不完备信息系统的一些相关定理,然后提出了基于条件熵的不完备信息系统的属性约简算法,并通过实例说明了本文所提出的属性约简算法具有可行性.但是新的条件熵与联合信息熵、信息熵三者之间没有联系,接下来会进一步探讨如何利用缺失对象集定义联合信息熵、信息熵的相关问题.参考文献：1 PAWLAK Z.Rough setsJ.International Journal
43、 of Computer and Information Sciences,1982(11):341-356.2 PAWLAK Z.Rough set theory and its application to data analysisJ.Cybernetics and Systems,1998,9(4):661-668.3 HU X,CERCONE N.Learning in relational databases:A rough set approachJ.Computational Intelligence,1995,11(2):323-338.4 SKOWRON A,RAUSZER
44、 C.The discernibility matrices and functions in information systemsM/SLOWI SKI R.IntelligentDecision Support:Handbook of Applications and Advances of the Rough Sets Theory.S.l.:Springer Dordrecht,1992:331-362.DOI:10.1007/978-94-015-7975-9.5 张玉,程林海,何莹莹,等.基于极大正域的变精度粗糙集属性约简J.模糊系统与数学,2020,34(5):139-149.
45、6 陈志恩,田彦山,马旭.基于可辨识矩阵的属性约简算法及应用J.大学数学,2021,37(3):20-24.7 王国胤,于洪,杨大春.基于条件信息熵的决策表约简J.计算机学报,2002(7):759-766.8 唐鹏飞.基于近似条件熵的集值决策表属性约简算法J.智能计算机与应用,2021,11(10):20-25.9 KRYSZKIEWICZ M.Rough set approach to incomplete information systemsJ.Information Sciences,1998,112(1):39-49.10 STEFANOWSKI J.Incomplete info
46、rmation tables and rough classificationJ.Computational Intelligence,2001,17(3):545-546.11 王国胤.Rough集理论在不完备信息系统中的扩充J.计算机研究与发展,2002(10):1238-1243.12 姚晟,李初宴,陈悦.基于非平衡数据下不完备混合型信息系统的属性约简J.计算机应用研究,2021,38(5):1331-1335.13 丁棉卫,张腾飞,马福民.基于二进制区分矩阵的不完备系统增量式属性约简算法J.计算机科学,2017,44(7):244-250.14 LI Z W,LIAO S M,QU L
47、 D,et al.Attribute selection approaches for incomplete interval-value dataJ.Journal of Intelligent N252023年闽南师范大学学报（自然科学版）and Fuzzy Systems,2021,40(5):8775-8792.15 ZHANG C Y,GAO R Y,QIN H,et al.Three-way clustering method for incomplete information system based on set-pair analysisJ.Granular Computi
48、ng,2019,6(2):1-10.16 YANG X P,LI T J,TAN A H.Three-way decisions in fuzzy incomplete information systemsJ.International Journal of Machine Learning and Cybernetics,2020,11(3):667-674.17 XIN X W,SUN J B,XUE Z A,et al.A novel intuitionistic fuzzy three-way decision model based on an intuitionistic fuz
49、zy incomplete information systemJ.International Journal of Machine Learning and Cybernetics,2022(13):907-927.18 MONDAL A,ROY S K,PAMUCAR D.Regret-based three-way decision making with possibility dominance and SPA theory in incomplete information systemJ.Expert Systems with Applications,2023,211:1186
50、88.19 WANG W J,ZHAN J M,ZHANG C,et al.A regret-theory-based three-way decision method with a priori probability tolerance dominance relation in fuzzy incomplete information systemsJ.Information Fusion,2023:89.20 NGUYEN N,SARTRA W.On reduction of attributes in inconsistent decision tables based on in
