第6期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1081· 考虑区分对<，x>。 U,根据定义4有Dis(BUa,U)≥Dis(B,U)。从 定义3对于给定信息系统IS=<U,A,V,f>, 而可证Dis(BUa,U2)+Disw(BUa,U)≥Dis(B,UP)+ 令A=CUD,其中子集C是条件属性集合，D是 DisM(B,UP),即Dis(BUa,U≥Dis(B,U)。 决策属性集合，又称四元组为决策系统，用DS=<U, 定义6给定弱标记不完备决策系统WTDS= CUD,Vf>表示。 <U,CUD,Vf>,设U=LUM,其中L表示有标记 对于给定决策系统DS=<U,CUD,Vf>,如果 实例的集合，M表示无标记实例的集合，RSC是 至少有一个属性c∈C使得V。含有缺失值，其中 一个属性约简，当且仅当R满足： 缺失值用”*”表示。此时，该系统称为不完备决 1)Dis(R,U2)=Dis(C,U2); 策系统，用DS=<U,CUD,Vf>表示。 2)VceR,Dis(R-c,U2)≠Dis(C,UP)。 定义4给定不完备决策系统DS=<U, 定义7给定弱标记不完备系统WDS= CUD,Vf>,有Ca,C,SB,其中C4表示离散型属 <U,CUD,V,f>,设U=LUM,其中L表示有标记 性，C,表示连续型属性，设<，x>EU,对Yp∈ 实例的集合，M表示无标记实例的集合，并且 B、B≤C,D关于B的区分对定义为Dis(B,UP)= B≤C.对Hc∈C-B,则 <x,x>(其中L表示有标记)，对V<,x>有 1)属性c相对于属性集合B的区分度 (3peC,lfxp)-fx,p川>) RSig(c,B,U2)= Dis(BUc,U2)-Dis(c.U2).B+O V]p∈Cdfx,p)+fxp) Dis(c,U儿，B=O f(x,p)≠*Afx,p)≠* 2)当RSig(c,B,U)=0时，则称属性c相对于 f(x,D)≠f(xiD) B是不必要的（相对冗余的）。 给定的不完备决策系统DS=<U,CUD,Vf>, 如图1所示，利用Dis(BUc,U-Dis(c,U)|= 对YBcC,Dis(B,UP引表示属性集B的重要度，其 RSig(c,B,UP)计算属性c相对于属性集B的重要 物理含义为属性集B的区分度。属性集能区分 度时，仅需要在属性集B无法区分的区分对中， 的实例对的数量越多，则表明该属性集越重要。 搜索属性c能够区分的实例对。由于相对重要度 由于在现实应用中，在大量不完备数据中只 的引人，在算法的迭代过程中，可不断地剔除当 有少部分实例存在标记，若仅利用带标记的实例 前属性约简集已能够区分的实例对和相对冗余的 获取属性约简结果，由于无标记的实例未得到有 属性，使得算法的搜索空间不断缩减，避免了大 效的利用，使得属性约简结果较难反映数据的整 量的重复计算，从而有效地减少算法的计算时间。 体信息，分类算法难以学习有效的知识规则，导 致分类模型的分类性能较弱。为此，针对弱标记 Dis (B,U2) 不完备决策系统，设计有效的属性重性度量方法 显得尤为重要。本文在文献[8,13]的基础上，构 Dis(c,U) -RSig (C.B.U-) 造了面向弱标记不完备数据的属性重要性度量方法。 给定的不完备决策系统DS=<U,CUD,V,f>, 若决策属性d存在缺失值。此时该系统称为弱标 图1属性C相对于属性集B的重要度 记不完备决策系统，用WIDS=<U,CUD,V,f>表示。 Fig.1 Significance of attribute c with respect to B 定义5给定弱标记不完备决策系统WIDS= 性质2给定弱标记不完备决策系统WDS= <U,CUD,Vf>,设U=LUM,其中L表示有标记 <U,CUD,Vf>,设U=LUM,其中L表示有标记 实例的集合，M表示无标记实例的集合，属性集 实例的集合，M表示无标记实例的集合，并且 B二C的重要度定义为 R≤C是C的一个属性约简集有 Dis(B,L2+DisM(B,UL2),L≠O,M≠O Dis(B,U2)= Dis(B,L2),L≠O,M=0 1)RSig(c,R,U2)=0,VcEC-R; Dis(B.UL2),L=0,M 2)RSig(c,R-c,UP)≠0，Yc∈R。 性质1给定弱标记不完备决策系统WDS= 证明因为R二C是C的一个属性约简集， <U,CUD,Vf>,设U=LUM,其中L表示有标记 根据定义6有Dis(R,U)=Dis(C,U),对Yc∈C-R 实例的集合，M表示无标记实例的集合，对 RSig(c,R,U2)=Dis(c,U2)-Dis(c.U2)nDis(R,U2)= Va∈C-B满足： Dis(c,U2)-Dis(c,U2)nDis(c,U2)=0 Dis(BUa,U≥Dis(B,U) 证明了1)的充分性。 证明根据定义2可得DisM(BUa,UP)≥DisM(B, 若RSC是C的一个属性约简集，对Yc∈< xj 考虑区分对 , xi >。 IS =< U,A,V, f > A = C ∪ D C D DS =< U, C ∪ D,V, f > 定义 3 对于给定信息系统 ， 令 ，其中子集 是条件属性集合， 是 决策属性集合，又称四元组为决策系统，用 表示。 DS =< U,C ∪ D,V, f > c ∈ C Vc ” ∗ ” IDS =< U,C ∪ D,V, f > 对于给定决策系统 ，如果 至少有一个属性 使得 含有缺失值，其中 缺失值用 表示。此时，该系统称为不完备决 策系统，用 表示。 IDS =< U, C ∪ D,V, f > Cd,Cr ⊆ B Cd Cr < xi , xj >∈ U 2 ∀p ∈ B B ⊆ C D B DisL(B,U 2 ) = < xi , xj > L ∀ < xi , xj > 定 义 4 给定不完备决策系统 ，有 ，其中 表示离散型属 性 ， 表示连续型属性，设 ，对 、 ， 关于 的区分对定义为 (其中 表示有标记)，对 有       (∃p ∈ Cr ,| f(xi , p)− f(xj , p)| > δ) ∨∃p ∈ Cd, f(xi , p) , f(xj , p) f(xi , p) , ∗ ∧ f(xj , p) , ∗    ∧ f(xi ,D) , f(xj ,D) IDS =< U,C ∪ D,V, f > ∀B ⊆ C |DisL(B,U 2 )| B B 给定的不完备决策系统 ， 对 ， 表示属性集 的重要度，其 物理含义为属性集 的区分度。属性集能区分 的实例对的数量越多，则表明该属性集越重要。 由于在现实应用中，在大量不完备数据中只 有少部分实例存在标记，若仅利用带标记的实例 获取属性约简结果，由于无标记的实例未得到有 效的利用，使得属性约简结果较难反映数据的整 体信息，分类算法难以学习有效的知识规则，导 致分类模型的分类性能较弱。为此，针对弱标记 不完备决策系统，设计有效的属性重性度量方法 显得尤为重要。本文在文献 [8,13] 的基础上，构 造了面向弱标记不完备数据的属性重要性度量方法。 IDS =< U,C ∪ D,V, f > d WIDS =< U,C ∪ D,V, f > 给定的不完备决策系统 ， 若决策属性 存在缺失值。此时该系统称为弱标 记不完备决策系统，用 表示。 WIDS = < U,C ∪ D,V, f > U = L∪ M L M B ⊆ C 定义 5 给定弱标记不完备决策系统 ，设 ，其中 表示有标记 实例的集合， 表示无标记实例的集合，属性集 的重要度定义为 Dis(B,U 2 )=    DisL(B,L 2 )+DisM(B,UL2 ), L , Ø, M , Ø DisL(B,L 2 ), L , Ø, M = Ø DisM(B,UL2 ), L = Ø, M , Ø WIDS = < U,C ∪ D,V, f > U = L∪ M L M ∀a ∈ C − B 性质 1 给定弱标记不完备决策系统 ，设 ，其中 表示有标记 实例的集合， 表示无标记实例的集合，对 满足： Dis(B∪a,U 2 ) ⩾ Dis(B,U 2 ) DisM(B∪a,U 2 证明 根据定义 2 可得 ) ⩾ DisM(B, U 2 ) DisL(B∪a,U 2 ) ⩾ DisL(B,U 2 ) DisL(B∪a,U 2 )+DisM(B∪a,U 2 ) ⩾ DisL(B,U 2 )+ DisM(B,U 2 ) Dis(B∪a,U 2 ) ⩾ Dis(B,U 2 ) ，根据定义 4 有 。从 而可证 ，即 。 WIDS = < U,C ∪ D,V, f > U = L∪ M L M R ⊆ C R 定义 6 给定弱标记不完备决策系统 ，设 ，其中 表示有标记 实例的集合， 表示无标记实例的集合， 是 一个属性约简，当且仅当 满足： Dis(R,U 2 )= Dis(C,U 2 1) ) ； ∀c ∈ R Dis(R−c,U 2 ) , Dis(C,U 2 2) ， )。 WIDS = < U,C ∪ D,V, f > U = L∪ M L M B ⊆ C ∀c ∈ C − B 定 义 7 给定弱标记不完备系统 ，设 ，其中 表示有标记 实例的集合， 表示无标记实例的集合，并且 ，对 ，则 1) 属性 c 相对于属性集合 B 的区分度: RSig(c,B,U 2 ) = { |Dis(B∪c,U 2 )|−|Dis(c,U 2 ) |, B , Ø |Dis(c,U 2 )|, B = Ø RSig(c,B,U 2 ) = 0 c B 2) 当 时，则称属性 相对于 是不必要的 (相对冗余的)。 |Dis(B∪c,U 2 )|−|Dis(c,U 2 ) | = RSig(c,B,U 2 ) c B B c 如图 1 所示，利用 计算属性 相对于属性集 的重要 度时，仅需要在属性集 无法区分的区分对中， 搜索属性 能够区分的实例对。由于相对重要度 的引入，在算法的迭代过程中，可不断地剔除当 前属性约简集已能够区分的实例对和相对冗余的 属性，使得算法的搜索空间不断缩减，避免了大 量的重复计算，从而有效地减少算法的计算时间。 Dis (c,U2 ) Dis (B,U2 ) RSig (c,B,U2 ) 图 1 属性 c 相对于属性集 B 的重要度 Fig. 1 Significance of attribute c with respect to B WIDS = < U,C ∪ D,V, f > U = L∪ M L M R ⊆ C C 性质 2 给定弱标记不完备决策系统 ，设 ，其中 表示有标记 实例的集合， 表示无标记实例的集合，并且 是 的一个属性约简集有 RSig(c,R,U 2 1) ) = 0， ∀c ∈ C −R ； RSig(c,R−c,U 2 2) ) , 0， ∀c ∈ R。 R ⊆ C C Dis(R,U 2 )= Dis(C,U 2 ) ∀c ∈ C −R RSig(c,R,U 2 ) =   Dis(c,U 2 )−Dis(c,U 2 )∩Dis(R,U 2 )    =   Dis(c,U 2 )−Dis(c,U 2 )∩Dis(c,U 2 )    = 0 证明 因为 是 的一个属性约简集， 根据定义 6 有 ，对 有： 证明了 1) 的充分性。 若 R ⊆ C 是 C 的一个属性约简集，对 ∀c ∈ 第 6 期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1081·