第2期 钱文彬等：一种快速的动态属性约简矩阵算法 251· 策表S=(U,C,D,V,f)的矩阵，则Mc=rglnxn 3动态属性约简算法 和M6=r号lnxn中具有的0”元素相同. 证明：对于x∈U,∈U,若x∈U',x)∈ 根据性质2可知，由矩阵Mc和简化矩阵M% U'且r=0,则存在x∈[xc,x')∈clc且 具有相同的“0”元素，根据定理1可知基于简化 r=0.若xc/D=1且izlc/D=1时，则 矩阵的属性约简等价于基于矩阵的属性约简.且简 ∈Uos∈U6s,由定义6可知，存在ck∈C,使 化矩阵去除重复元素，有效地缩小了算法的搜索空 得f(,ck)≠f(x,ck)f(,D)≠f(,D),再由定 间，并且根据性质3，将决策表中对象的变化情况 义7可知r=r;若Ilc/D=1和xc/D=1 映射到简化矩阵中元素的动态变化，仅需扫描一遍 不同时满足时，则说明对于x,x∈'，至少有一个 简化矩阵中的元素便可求解属性约简，为此可设置 存在Uheg中，从而由定义7可知r=r,对于 标志位count记录矩阵中0”元素的个数，当count ∈U',)∈U',若x∈U,∈U且T=0,则存 越大时其对应的属性就越重要，在有效利用原属性 在ec,∈rc且r%=0,若EUpos∈ 约简的基础上，本文给出一种快速的动态属性约简 Uos时，由定义7可知，f(x,ck)卡f(x,c),再由定 矩阵算法， 义4可知r=:若，至少有一个存在Ucg 算法：快速的动态属性约简矩阵算法 中时，即假如设∈Ueg'若f(x,ck)≠f(c,ck 输入：简化决策表S=(U”,C,D,V,f),原属 则由定义4可知r)=r;如果存在f(x,ck)= 性约简Red(C),新增对象zo,Vck∈C,矩阵Me! f(xj,ck小，由于x∈Uheg且∈【rc,故一定有 中“0”元素个数count,矩阵M6中“0”元素个数 x,∈[xc使得f(x,ck)卡f(x,c),从而使得 count. f(x,c)卡f(,ck小，则由定义4可知r对=r. 输出：更新后的属性约简Red(C) 综上所述，命题成立，证毕 Step1 if((3xj∈Uheg A YCk∈CAf(xo,ck)= 定理1设R为决策表S=(U,C,D,V,f) f(xj,Ck)》 的矩阵的属性约简，设R为简化决策表S= 则Red(C)保持不变； (U,C,D,V,f)的简化矩阵的属性约简，则R和R Step2if(3zj∈Upos A VCk∈CAf(xo,ck)= 中所求结果是一致的，即有R=R成立 f(xj,ck)A f(xo,D)=f(xj,D)) 证明：在决策表S=(U,C,D,V,)的矩阵 则Red(C)保持不变； Mc中，若存在ck∈R,根据定义5可知，则存在 Step3if(3xj∈Upos A VCk∈CAf(zo,ck)= 一个r∈Mc,使得r=0,满足MR=Mc且 f(xj,ck)A f(xo,D)f(zj,D)) MR-{c}卡Mc,根据性质2可知，在简化决策表 Step3.1 if(Vzi EUpos A f(i,D)=f(rj,D)) S=(U,C,D,V,f)的简化矩阵M化中，存在一个 则根据定义7，更新对象x与x所对应的矩 对应的r∈M6,必有T=r)成立，故可知 阵元素r;并更新M化.count; rY=0,使得M=M6且MR-e}≠M6,根 if(3ck∈C-Red(C)Af(r,ck)≠f(c,ck) 据定义8可知ck∈R',则可证R二R.在决策表 S=(U,C,D,V,f)的矩阵M6中，若存在ck∈R, 则更新对象x:与x)在ck上所对应的矩阵 根据定义8可知，则存在一个r'∈M化，使得 Me}:并更新count的值： rry=0,满足M=M6且M?-fes}≠Mc,根 选择属性满足G一4 Me)count))(偌 据性质2可知，在简化决策表S=(U',C,D,V,f) 存在多个，则任选其一)： 的简化矩阵M化中，存在一个对应的r)∈Mc,必 Red(C)=Red(C)U{ci}; 有T=r成立，故可知r=0,使得Mr=Mc 根据定义8，对Red(C)中可能存在的冗余属 且MR-ck}卡Mc,根据定义5可知ck∈R,由此 性反向剔除： 可证RCR综上所述，命题成立，证毕 A 性质3在简化决策表S=(U,C,D,V,f), else 对VceC,设条件属性ck对应的矩阵为M{e}= Red(C)保持不变； rnxm,则Me}=r号nxn中0”元素个数 Step3.2iVar:∈Uheg) 越多，区分能力越大 删除对象)在矩阵S,中所对应的行，并更 证明：由定义7和性质2可知命题成立，证毕 新M6.count;