正在加载图片...
Vol.28 No.9 鄂旭等：一种不完备信息表的预处理方法 .903. 个断点集合{(a,cf),(a,c),…,(a,c%)定义了 1.2定理及其证明 V。上的一个分类划分 定理1设决策表S=(U,A,V,),其中 P。=l[6,ci),[ci,c),[c,c,+1]}, U=UUU',U°是所有属性值都已知的样例集 l.=c8<c1<c4<<c呢<c星.+1=ra 合，U'是部分属性值未知的样例集合，A=CU C'UD,C”是重要条件属性集，C是冗余条件属 v.=[6,ci)U[ci,c)U.U[,c.+1] 性集，D为决策属性集.如果对Ha∈U,Hb∈ 定义3根据定义2，由相容信息表中条件属 v°，Hc∈C',令c(a)=c(b),则信息表的确定 性与决策属性间的一致性对应关系，可以定义划 性不变 分区间的加法运算法则.设两个划分区间为[©， 证明设分类E:∈UIND(C),(i=1,2, c+1),[c+1,c+2),则： …,m),m是由条件属性集C决定的分类数， {X1,X2,…,Xn}是U上由决策属性决定的概念 [c,c+1)十[c+1,c+z)= 簇，则对任意分类E∈UIND(C),其对于决策 [,c+2) 两区间决策值相同 属性分类的确定性程度为： 2 出+ Pmax(E)= 2 两区间策值不同 max({|E∩X:l/八El:X:∈UlIND(D))- (2) 由此可以得出决策表S的确定性程度为： 定义4在信息系统S=(U,A,V,)中， E 如果A={a:=1,…,m}是属性集，设X:∈U, a(s)-(E) 则对象X:的遗失属性集MAS:、对象X:的无差 (1)若C中有且仅有一个元素c,则有条件 别对象集NS:和信息系统S的遗失对象集MOS 属性集C=CU1c决定的分类为： 分别定义为： EE UlIND(coU(e)),i=1,2...m'. MASi=al a(xi)=*,k=1,....ml, 因为c为冗余属性，所以U I IND(C)= MOS={iMAS:≠0，i=1,…,nf, UIND(CU{c),也就是增加冗余属性值并不 NS:=jl M(i j)=j.j=1...n. 影响决策表中分类情况，即E=E'·对任意分类 定义5设决策表为S=(U,A,V,),则 E∈UlIND(c)都有，E∈UIND(CU1cf), 可定义一个三元组作为差别向量D=(O,DC, ma(E)=max(E),决策表的nmax(S)无变化， F),其中O为可区分对象对；DC为差别属性集， (2)同理可证，若冗余属性C={C1,C2,…, 其定义为： Cm},决策表的“m(S)仍然不发生变化 14l4∈CN4(x)≠既()i,d(x)≠d(x) 推论1若一个决策表存在冗余属性且冗余 d(xi)=d(xj） 属性存在遗失值，则遗失值填补为该属性的任意 F为一个频率向量，F=(f(a),f(a2),…, 一个断点，决策表的确定性不变 f(an),它的每一项表示该属性出现的频率，其 定理2设决策表为S=(U,A,V,),其 中， 中论域U是一个非空有限对象集合，A是对象 1/八Dcl,a∈DC 的属性集合，分为条件属性集C和决策属性集D f(a)= 0, 两个不相交的子集，即A=CUD,HB三C,令 a;DC U'=U一P0SB(D)为粗糙边界，如果 定义6现有两个差别向量D:=(O,DC U'lIND(BUc=mi,m2,.mp, F),DV;=(O,DCj,E),则差别向量加法法则 U'lIND(D)=1,n2,…,g{,则在粗糙边界 为：D:十D=(0时，DC可，F),其中，0时=O:U 中，Hc∈C,POse(D)=POs1c(D)% 0, Fij=FiF=(fi(a)fj(a1), 证明POs1et(D)=9BUHd(X)= fi(a2)fj(a2),..,fi(an)fj(an)), giy,∈U'IBUIc:Y∈xf=91Y:∈iY DCi, DC DCi Uiy2UU1y.:y:∈x=91y,∈1y:: DCi, DCDCi DC:UDC;,(DC:CDCi)n(DC EDC:) Y∈X=当POS1e(D)4个断点集合｛（ ac a 1）（ ac a 2）…（ ac a k a ）｝定义了 V a 上的一个分类划分 Pa＝｛［ c a 0c a 1）［ c a 1c a 2）…［ c a k ac a k a＋1］｝ la＝c a 0＜c a 1＜c a 2＜…＜c a k a＜c a k a＋1＝ ra V a＝［ c a 0c a 1）∪［ c a 1c a 2）∪…∪［ c a k ac a k a＋1］． 定义3 根据定义2由相容信息表中条件属 性与决策属性间的一致性对应关系可以定义划 分区间的加法运算法则．设两个划分区间为［ c a i c a i＋1）［ c a i＋1c a i＋2）则： ［ c a i c a i＋1）＋［ c a i＋1c a i＋2）＝ ［ c a i c a i＋2） 两区间决策值相同 c a i c a i＋1＋c a i＋2 2 ∪ c a i＋1＋c a i＋2 2 c a i＋2 两区间决策值不同 （2） 定义4 在信息系统 S ＝〈UAV f〉中 如果 A＝｛ai｜i＝1…m｝是属性集设 Xi∈ U 则对象 Xi 的遗失属性集 MAS i、对象 Xi 的无差 别对象集 NS i 和信息系统 S 的遗失对象集 MOS 分别定义为： MAS i＝｛ak｜ak（ xi）＝∗k＝1…m｝ MOS＝｛i｜MAS i≠／○i＝1…n｝ NS i＝｛j｜M（ ij）＝／○i≠ jj＝1…n｝． 定义5 设决策表为 S ＝〈UAV f〉则 可定义一个三元组作为差别向量 D＝（ ODC F）其中 O 为可区分对象对；DC 为差别属性集 其定义为： DC＝ ｛ak｜ak∈ C∧ ak（ xi）≠ ak（ xj）｝ d（ xi）≠ d（ xj） ／○ d（ xi）＝ d（ xj） F 为一个频率向量F ＝ （ f （ a1）f （ a2）… f （ an））它的每一项表示该属性出现的频率其 中 f （ ai）＝ 1／｜DC｜ ai∈ DC 0 ai∈／DC 定义6 现有两个差别向量 Di＝（ OiDC i Fi）DV j ＝（ OjDC jFj）则差别向量加法法则 为：Di ＋ Dj ＝（ OijDC ijFij ）其中Oij ＝ Oi ∪ Oj Fij＝Fi＋Fj＝（ f i（ a1）＋ f j（ a1） f i（ a2）＋ f j（ a2）…f i（ an）＋ f j（ an）） DC ij＝ DC i DC i⊆DC j DC j DC j⊆DC i DC i∪DC j （DC i⊄DC j）∩（DC j⊆DC i） 1∙2 定理及其证明 定理1 设决策表 S ＝〈UAV f〉其中 U＝ U 0∪ U′U 0 是所有属性值都已知的样例集 合U′是部分属性值未知的样例集合．A ＝ C 0∪ C′∪ DC 0 是重要条件属性集C′是冗余条件属 性集D 为决策属性集．如果对∀ a∈ U′∀b∈ U 0∀c∈C′令 c（ a）＝ c（ b）则信息表的确定 性不变． 证明 设分类 Ei∈ U｜IND（ C）（ i＝12 …m）m 是由条件属性集 C 决定的分类数 ｛X1X2…Xn｝是 U 上由决策属性决定的概念 簇则对任意分类 E∈ U｜IND（ C）其对于决策 属性分类的确定性程度为： μmax（ E）＝ max（｛｜E∩Xi｜／｜E｜∶Xi∈ U｜IND（ D）｝）． 由此可以得出决策表 S 的确定性程度为： μmax（ S）＝ ∑ m i＝1 ｜Ei｜ ｜U｜ μmax（ Ei）． （1） 若 C′中有且仅有一个元素 c则有条件 属性集 C＝C 0∪｛c｝决定的分类为： E′i∈ U｜IND（C 0∪（ c））i＝12…m′． 因为 c 为 冗 余 属 性所 以 U｜IND （ C 0） ＝ U｜IND（C 0∪｛c｝）也就是增加冗余属性值并不 影响决策表中分类情况即 E＝ E′．对任意分类 E∈ U｜IND（C 0）都有E∈ U｜IND（ C 0∪｛c｝） μmax（ E）＝μmax（ E′）决策表的 μmax（ S）无变化． （2） 同理可证若冗余属性 C′＝｛C′1C′2… C′m｝决策表的 μmax（ S）仍然不发生变化． 推论1 若一个决策表存在冗余属性且冗余 属性存在遗失值则遗失值填补为该属性的任意 一个断点决策表的确定性不变． 定理2 设决策表为 S ＝〈UAV f〉其 中论域 U 是一个非空有限对象集合A 是对象 的属性集合分为条件属性集 C 和决策属性集 D 两个不相交的子集即 A ＝ C∪ D∀B⊆ C令 U′＝ U － POS U B （ D ） 为 粗 糙 边 界如 果 U′｜IND（B ∪ ｛c｝ ＝ ｛ m1 m2… mp｝ U′｜IND（ D）＝｛n1n2…nq｝则在粗糙边界 中∀c∈CPOS U′ B∪｛c｝（ D）＝POS U′ B∪｛c｝（ D） n i． 证明 POS U′ B∪｛c｝（ D）＝ ∪ m j＝1 B∪｛c｝（ Xj ）＝ ∪ m j＝1 ｛Y i∈ U′｜B∪｛c｝∶Y i⊆ Xj｝＝ ∪ m j＝1 ｛Y i∈｛Y1｝ ∪｛Y2｝∪…∪｛Y n｝∶Y i⊆ Xj｝＝ ∪ m j＝1 ｛Y i∈｛Y i｝∶ Y i⊆Xj｝＝ ∪ m j＝1 POS U′ B∪｛c｝（ D） n i． Vol．28No．9 鄂 旭等： 一种不完备信息表的预处理方法 ·903·