正在加载图片...
,606 北京科技大学学报 2006年第6期 CD,A CD,A…A(CD,)A…ACD (T)结束运算，集合P就是原信息表的属性 由于它是一个逻辑等式，这就说明CD,被CD,约简 约简 后，并没有破坏原有信息表的属性逻辑表达式，也 3算例 就不会影响原信息表的属性约简，定理证毕， 为了说明本算法，现在举例子说明其运算过 2 算法描述 程，设原始信息表为表1. 设属性约简集为P,并初始化P=①：计算原 表1原始信息表 信息表的互信息为'. Table 1 Initial table Step1根据原始信息表建立差别向量组. Step2根据上述定理及差别向量加法规则 对向量组进行一次扫描，生成扫描向量 x2 5 定义扫描向量S=(C,FD,R),C为核属性 集，FD为差别属性集，R为频率向量， x3 初始化扫描向量S=(C,FD,R),C=O, T FD=0,R=0; x5 7 F0R(i=1;≤n;i++) {从差别向量组中读取VD,=(O,CD,F:), If fi(a)=1,then C=CU X7 2 FD=FD十CD,;R=R+F;} 最后形成扫描向量S=(C,FD,R) 把原始信息表转换成差别向量组，其中每一 Step3对扫描向量进行约简运算. 项VD,=(O,CD,F:),具体表示如表2. (1)对扫描向量S=(C,FD,R)中的核属 经计算可得原信息表中条件属性与决策属性 性集C进行扫描.若C=0,则执行步骤(3)；否 的互信息I(C,D)=0.845.然后对差别向量组 则，令P=PUC,执行步骤(2)： 中的差别向量进行扫描，并按上述定义的差别向 (2)从核属性集C中分别取各个属性，然后 量加法法则进行加法计算：因为表2中仅有差别 对扫描向量S=(C,FD,R)中的差别属性集FD 向量VD。中f(a)=1,所以，扫描向量S=(C, 进行约简：设α：∈C,则从差别属性集中删除所有 FD,R)中的核属性项C=ia},差别属性集Fn= 包含a:的项，同时从频率向量R中删除f(a) (e,f),(a,c,d),(b,c,d)f,频率向量R= 项，直至所有核属性按上述操作完毕，这样将得 (f(a),f(c),f(d),f(e),f(g):f(c)=1/5+ 到一个新的扫描向量. 1/4+1/5+1/5+1/3+1/4+1/3+1/3+1/2= (3)计算信息表的互信息1，如果≤°，则 156/60,同理可得：f(d)=171/60,f(e)= 执行步骤(7)；否则，执行步骤(4) 176/60,f(g)-191/60.令P=PUa,计算信 (4)根据上述定理对新的扫描向量中的差别 息表的互信息得：I(P,D)≤I(C,D)=0.845. 属性集FD中的元素项进行逻辑运算：如果HA 删除差别属性集合中的(a,c,d)项，删除频率向 CFD,VBC FD,并且A三B,则令FD=FD\B; 量R中的元素f(a)·因为属性a为仅有的核属 形成新的扫描向量 性，所以下一步将从差别属性集中选择重要属性， (5)在新的扫描向量中，对频率向量R中的 在频率向量中，由于f(g)=191/60最大，所以， 元素进行大小比较，若f(a)最大，则选取属性a: 取属性9作为重要属性，令属性约简P= 作为重要属性，并令P=PU1a}.计算此时信息 PUig{,计算此时的互信息得：I(P,D)≤I(C, 表的互信息1，如果≤P,则执行步骤(7)：否则， D)=0.845,则在差别属性集合中删除(e,g)项， 执行步骤(6) 在频率向量中删除f(g)项.然后接着重复上面 (6)在扫描向量的差别属性集中，删除包含 的操作，选取属性d作为重要属性，令P= 属性a的项，在频率向量R中删除f(a:)项，得 PUid},计算信息表的互信息I(P,D)=I(C, 到新的扫描向量，然后执行步骤(4)· D)=0.845,所以，P={a,d,g}就是原信息表的CD1∧CD2∧…∧（CDi ）∧…∧CDn 由于它是一个逻辑等式这就说明 CDj被 CDi约简 后并没有破坏原有信息表的属性逻辑表达式也 就不会影响原信息表的属性约简．定理证毕． 2 算法描述 设属性约简集为 P并初始化 P＝∅；计算原 信息表的互信息为 I 0． Step1 根据原始信息表建立差别向量组． Step2 根据上述定理及差别向量加法规则 对向量组进行一次扫描生成扫描向量． 定义扫描向量 S＝（ CFDR）C 为核属性 集FD 为差别属性集R 为频率向量． 初始化扫描向量 S＝（ CFDR）C＝ ∅ FD＝∅R＝0； FOR（ i＝1；i≤ n；i＋＋） ｛从差别向量组中读取 VDi＝（ OiCDiFi） If f i（ ak）＝1then C＝C∪｛ak｝； FD＝FD＋CDi；R＝ R＋Fi；｝ 最后形成扫描向量 S＝（CFDR）． Step3 对扫描向量进行约简运算． （1） 对扫描向量 S＝（ CFDR）中的核属 性集 C 进行扫描．若 C＝∅则执行步骤（3）；否 则令 P＝P∪C执行步骤（2）； （2） 从核属性集 C 中分别取各个属性然后 对扫描向量 S＝（ CFDR）中的差别属性集 FD 进行约简：设 ai∈C则从差别属性集中删除所有 包含 ai 的项同时从频率向量 R 中删除 f （ ai） 项．直至所有核属性按上述操作完毕这样将得 到一个新的扫描向量． （3） 计算信息表的互信息 I如果 I≤ I 0则 执行步骤（7）；否则执行步骤（4）． （4） 根据上述定理对新的扫描向量中的差别 属性集 FD 中的元素项进行逻辑运算：如果∀ A ⊂FD∀B⊂FD并且 A ⊆B则令 FD＝FD＼B； 形成新的扫描向量． （5） 在新的扫描向量中对频率向量 R 中的 元素进行大小比较若 f （ ai）最大则选取属性 ai 作为重要属性并令 P＝P∪｛ai｝．计算此时信息 表的互信息 I如果 I≤I 0则执行步骤（7）；否则 执行步骤（6）． （6） 在扫描向量的差别属性集中删除包含 属性 ai 的项在频率向量 R 中删除 f （ ai）项得 到新的扫描向量然后执行步骤（4）． （7） 结束运算集合 P 就是原信息表的属性 约简． 3 算例 为了说明本算法现在举例子说明其运算过 程设原始信息表为表1． 表1 原始信息表 Table1 Initial table U a b c d e g h x1 3 1 3 1 1 2 3 x2 3 2 3 1 2 3 5 x3 3 3 2 2 3 1 1 x4 3 1 1 3 3 1 6 x5 1 1 3 1 3 1 7 x6 2 1 3 1 3 1 4 x7 3 1 3 1 3 1 2 把原始信息表转换成差别向量组其中每一 项 VDi＝（ OiCDiFi）具体表示如表2． 经计算可得原信息表中条件属性与决策属性 的互信息 I（ CD）＝0∙845．然后对差别向量组 中的差别向量进行扫描并按上述定义的差别向 量加法法则进行加法计算：因为表2中仅有差别 向量 VD19中 f （ a）＝1所以扫描向量 S＝（ C FDR）中的核属性项 C＝｛a｝差别属性集 FD＝ ｛（ef ）（ acd）（ bcd）｝频率向量 R ＝ （ f （ a）f （ c）f （ d）f （ e）f （ g））．f （ c）＝1／5＋ 1／4＋1／5＋1／5＋1／3＋1／4＋1／3＋1／3＋1／2＝ 156／60同 理 可 得：f （ d ） ＝171／60f （e）＝ 176／60f （ g）＝191／60．令 P＝ P∪｛a｝计算信 息表的互信息得：I （ PD）≤ I （ CD）＝0∙845． 删除差别属性集合中的（ acd）项删除频率向 量 R 中的元素 f （ a）．因为属性 a 为仅有的核属 性所以下一步将从差别属性集中选择重要属性． 在频率向量中由于 f （ g）＝191／60最大所以 取属 性 g 作 为 重 要 属 性令 属 性 约 简 P ＝ P∪｛g｝计算此时的互信息得：I（ PD）≤ I（ C D）＝0∙845则在差别属性集合中删除（ eg）项 在频率向量中删除 f （ g）项．然后接着重复上面 的操作选取属性 d 作 为 重 要 属 性令 P ＝ P∪｛d｝计算信息表的互信息 I（ PD）＝ I（ C D）＝0∙845所以P＝｛adg｝就是原信息表的 ·606· 北 京 科 技 大 学 学 报 2006年第6期