Vol.27 No.6 鄂旭等：基于超立方体与信息熵的离散化方法 ·761· ND(C)={X,,,X},则对于任意子集X∈X, POSauta(D)>POSau((D),所以有： xy是子集X,中含有类Y,的样本数，则信息熵 sig(a)-sig(b)-POSD)-POS(D) x,x,,X-lgp,其中，P, U-POSD POSUAb (D)-POS(D) U-POSD)>0 定义5在信息系统S中，样本集X相对于 定理证毕. UNDD)的信息熵： Shannon熵是用来衡量一个系统不确定性程 E0X0-2+IK,X,,X) 度的指标.根据其最大值定理和最小值定理及 叫作相对信息熵. 信息表的特性，可以给出如下定理. 由粗糙集的基本概念，设决策表为S-(U,A, 定理4设决策表为S(U,A,',F),D,为某一决 ”,),其中论域U是一个非空有限对象集合，是对 策属性值集，[4，]n为按条件属性划分的某一等价 象的属性集合，分为条件属性集C和决策属性集 类，令0 c2在倍 D两个不相交的子集，即A=CUD. 息表分别按照条件属性和决策属性进行等价 定义6在信息表S中BsC,c∈C,U=U- 划分的结果中，若VD,3[u,]o,PD4,]nwo上l,则 POS(D)是粗糙边界，可以定义属性c的重要性公 E(U)>E(U)>>E(U),n为等价划分的类别数. 式： 证明：设决策表的论域为U,按照某一个等价 sgoP品 关系在U上的划分为： 根据条件属性与决策属性间的关系及定义 A1={X,X2,,X-1,X,X1,…,X-1,X,Xn,,X}, 的属性重要性公式，可以给出如下定理， A={X,X2,…,X-1,X1,…,X-,X41,,X,XUX} 定理1设决策表为S-(U,A,”,力，其中论域U 则有： 是一个非空有限对象集合，A是对象的属性集合， E(A)-E(A))- 分为条件属性集C和决策属性集D两个不相 交的子集，即A=CUD,HBSC,令U'=U-POS(D) Xutxtx[0u+怀KatXs,…xtx+ 为粗糙边界，如果UND(BU{c})={m,m,…,m,}, x"…x- UND(D小{n,n,,n,},则在粗糙边界中， ttt0 kutXuXatXx…xtx） VcEC,POSKte(D)=UPOSL)(D).. 因为 x+tt+xmn…xn） X 证明： t2t+比0 Cu+XuXar+xa…xm+x20 POS(D)=UBU{cX)=U{Y,∈U1BU{c:Y,二x}= 又因为y+w,x》 U(Y∈{U{UU{Y.Y,eX= Kytxatitxxu)0 U(YE(Y.):Y,X)=UPOSK(D). 所以，E(A)之A).由此可以导出： 定理2设HBsC,Hc∈C且c年B,U=U- E,(U>E,(亿U>>E(U0. POSD)为粗糙边界，则有： 定理5如果一个信息表中的两个实例子集 IPOSL(D)=POS(D)-POS%(D) X,XCU中含有且只含有相同比例数目的决策 证明：对廿c∈C且ctB有两种情况： 类，则两个实例子集的并集XUX具有与X,X相 若c为冗余属性，则 同的相对信息熵. POS(D)=POS(D)=0, 证明：设实例子集X中含有的决策类为 POSKRe (D)=POS(D-POS(D)=0 D,D,…,D,实例子集X中含有的决策类为 若c为重要属性，因为U'=:U-POS(D),所以U= D列_D DD. U+POS(D),POSte(D)=POS(D)UPOSKte,(D), D,D,…D,并且有-7P“xP, 所以lPOS8e(D=POSe(D+POS(D儿. 可得DpKl,D=p,XUX中含有实例总数 定理3设B∈C,Va,b∈C且a,bB,如果属 为X+X,含有的决策类D的数目为D+D 性a比属性b重要，则有siga)-sig(b)>0. pK+pX,由此可以得出决策类D占XUX的比 D(px tpixD 证明：如果属性a比属性b重要，由定理2可 例为X议p,与原实例子集x,名 知属性a比属性b在粗糙边界的分类能力强，即 中的相同.同理可以证明其余的决策类M 〕 1 . 2 7 N 0 . 6 鄂 旭 等 : 基 于 超 立方体 与 信息嫡 的离散 化方 法 川 IN D (C) = {戈 ,戈 , … , 瓜 } , 则 对 于任 意 子集戈任 X, x , 是 子 集 不 , 中含 有 类 X 的样 本 数 , 则信 息 嫡 (IH 几 一 “ 一纳如, , 其 中 ,P愉 · 定 义 5 在 信息 系 统 S 中 , 样 本 集 X 相对 于 训NI D (D ) 的信 息嫡 : p O S , u { 口 } (D ) > PO S , u {。 , (D ) , 所 以有 : 5 19 ( a ) 一 5 19( b ) = (EP 琪 互竺窗生五` 帆 , Xjz , 一 瓜’ 叫作 相对 信 息墒 . 由粗 糙集 的 基本 概念 〔:i] , 设决 策表 为个( U, ,A V, 力 , 其 中论域 u 是 一个 非 空有 限对 象集 合 , 是对 象 的属性 集 合 , 分 为条 件属 性 集 C 和 决策 属性 集 D 两 个 不 相交 的 子集 , 即才 二 C u D . 定义 6 在 信 息表 豹扣V B g C , c 任 C , U =, U一 PO S戮D )是粗 糙边 界 , 可 以定义 属性 c 的重要 性 公 式 : “ ` · 卜!淄韶旱 定理 证 毕 . S h an o n 墒 是用 来衡 量 一个 系 统不 确 定性 程 度 的指 标 . 根 据其 最 大值 定 理 和最 小 值定 理 〔7] 及 信 息 表 的特 性 , 可 以给 出 如下 定 理 . 定理 4 设 决策 表 为赓(口月尤月 , jD 为某 一 决 策属 性值 集 , 〔ut] NDI 为按条 件 属性 划分 的某 一等 价 举 . 今尸 (D 打u,1 _ 卜舆契奥醉 二 丝照犯奥醉霖 信 玖 L封 x J加 ) C盯 Q LL封`」彻 ) 一 ’ ~ 息 表 分 别 按 照 条 件 属 性 和 决 策 属 性 进 行 等 价 划分 的结 果 中 , 若 V 几 〕 「u,] NDI , 尸(p 尹 }【ut] NDI )月 , 则 E , (功> 石2 (功>. 二 > 瓦 (功 , n 为等 价 划 分 的类 别数 . 证 明 : 设 决策表 的论域 为 U , 按照 某 一个 等价 关系 在 U 上 的划 分 为 : 根据 条 件 属 性 与 决 策 属 性 间 的 关 系及 定义 的 属性 重 要性 公 式 , 可 以给 出如 下 定理 . 定理 1 设 决策 表 为=S ( U, A , V, 力 , 其 中论 域 U 是 一个非 空有 限对象 集 合 , A 是对 象 的属性集 合 , 分 为 条 件 属 性 集 C 和 决 策 属 性 集 D 两 个 不 相 交 的子 集 , 即A 二 C u D , V B 互 C , 令 U 任 U 一 PO S戮D ) 为粗糙 边 界 , 如 果 U llN D (B U { c }) = { m l , m Z , … , 札 } , 川NI D (D ) 一 { n , ,从 , … , 久} , 则在 粗 糙边 界 中 , 川= {戈 ,龙 A Z= {戈 ,龙 则 有 : , … ,戈 一 , ,尤 , 恙 1 , … , 不 一 , , 戈 , , … ,戈 一 1 ,戈 十1 , … ,戈 一 , ,戈 + , , 养 1 , … , Xn } , ,龙 ,戈 U戈 } , V e 任 C , P O S能、 。 , (D ) = u P O S乳{ 。 }归 ) , . J= 1 证 明 : P O S筑、 : } (D ) = u 刀 u { e }氏 ) = u { X 任 U ( B 口 { e } : X 二戈 } 二 u {X 任 {叭 } u {乙 } u … u {式} : X 二 戈卜 u {艺e { X } : 艺二不 } = u P O S乳{ 。 } (D ) , (EA 1 , 一 (EA 2 )里翁鱼堆 苦1声 Z j, … 声 , ` , - 业裔热称 . 、 砂 2j , … 、 周 + 互号均 以内 , … 、 - 业裔丛取 1 +,x1j 丙+vx , … 声, 、 因为 业裔场心 1丙 , …励 - 世翁 兰鱼心+l,x1j 砂 2j , … 声两 ) 二 0 又 因为 星翁均 以 ljN 二 司 - 业裔卿取、 、 2j , … 声两 ) 二 0 定 理 2 设 V B 互 C , V c 任 C 且 c 子B , 甘 = 口一 P O S欲刀) 为粗糙 边 界 , 则 有 : ! p O S筑{ 。 } (D )卜} p O S跳{ 。 } (I ) )卜} p O S班D )! 证 明 : 对 V c 任 C 且 c 磋B 有 两种 情 况 : 若 。 为 冗余 属性 , 则 ! P O S能{ 。 } (D ){ = } p O S了(D )} = 0 , } p O S乳、 。 、 (D )} = { p O S别刀: .卜{ p O S欲刀)} = 0 若 c 为重 要属 性 , 因为 理= U 一 P O S B沪) , 所 以 =U “ +, P O S 。 (D ) , 则 P O S箭{ 。 } (D ) = PO S言(D ) 曰 p O S能( 。 } (D ) , 所 以 } p O S乳、 。 } (D )卜} p O S跳。 。 }心, )卜} p O S会飞D )} . 定理 3 设 V B 生 C, V a才 ,任 C 且 a , b 磋B , 如 果 属 性 a 比属 性 b重 要 , 则 有 5 19 ( · ; ) 一 5 19 ( b ) > 0 . 证 明 : 如 果属 性 a 比属 性 b 重要 , 由定 理 2 可 知 属 性 a 比 属 性 b 在 粗 糙边 界 的分 类 能 力强 , 即 所 以 , E (A 1 ) 七 E (A 2 ) . 由此 可 以导 出 : E , ( 叻> 百 2 (功> … > 石 月 (叻 . 定 理 5 如 果一 个 信 息 表 中 的两 个 实 例 子集 戈 式 c U 中 含 有 且 只 含 有 相 同 比 例 数 目 的决 策 类 , 则 两个 实 例 子集 的 并集戈 U不 具 有 与戈 式 相 同 的相对 信 息 墒 . 证 明 : 设 实 例 子 集尤 中 含 有 的 决 策 类 为 酬 刀’,. · 几 , 实 例 子 集 戈 中 含 有 的 决 策 类 为 酬“ ,一“ , 并 且有 捌 一鲁 一 lP , … , 鲁斜 二 , , 可 得 }D ;}, 1比 } , }侧 }=P ,比} , 戈 日不 中含 有 实例 总数 为 比卜因 } , 含有 的决策 类 D , 的数 目为 }侧卜}侧卜 p l比}+P ;比 } , 由此可 以得 出决策类 D , 占戈 u 不 的比 例 “ 哉 一 嚼剖 , 1 , 与 原 实例 子集、 , ; 中 的 相 同 . 同 理 可 以 证 明 其 余 的 决 策 类