正在加载图片...
Vol.28 No.6 鄂旭等：基于扫描向量的属性约简方法 .605. 1.2算法相关定理证明 0:中的对象x:与，那么根据粗糙集等价类的 根据上述定义及差别向量加法法则，可以得 概念，对象x:与x为同一类，这与题设中V,= 到如下定理： (O:,CD,F:)是一个差别向量相矛盾，因此，在差 定理1在一个差别向量中，如果它的频率 别向量组中，每个差别向量的差别属性集合必不 向量中的某一项元素取值为1，则该元素所对应 能取空值 的属性为原信息表的核属性 定理3在差别向量组中，每个差别向量的 证明：令频率向量中的任意一个f(a:)=1, 差别属性集合取值为全属性，则任一个属性都是 因为F=(f(a1),f(a2),,f(an),f(a)= 原信息表的属性约简， C命=1，所以C0=1,也就是差别向量中的差 证明：设原信息表中任意两个可分辨对象转 化的差别向量为VD,=(O:,CD,F:),则整个信 别属性集只有一个属性，而在整个属性集合中也 息表转化的差别向量组为VD.r=(Or,CD.T, 只有这个属性能够区分这两个对象，因此这个属 性就是原信息表的核属性，证明完毕 F),即D二Vo如果信息表中的全部属性 定理2在差别向量组中，每个差别向量的 为a,a2,…,an},由题意知，≤n,都有Cp 差别属性集合必不能取空值 ={a1,2,…,an,由于每一个差别集合在数理 证明：因为差别向量组描述的是整个信息表 逻辑中是析取关系，即Cn,=aiV azV…Vaa,又 的可分辨情况，所以每一个差别属性集包含的都 根据差别向量组和信息表的对应关系可知，整个 是能够区分某一对象对的属性，设某一个差别向 差别向量组中各个差别向量是一种逻辑合取关 量VD,=(O,CD,F),0:=(xi,x),如果CD,= 系，即逻辑表达式为： O,则说明在原信息表中，所有的属性都不能区分 ACD,=(aiV azV.Va)(aiV azV..Va)A..(aiv azV.Va)=(aiV azV.Va). m个(aVaV…Vg) 因此，ia,a2,,an}中的任意一个元素都将是 是析取关系，即Cp,=(aVa2V…Vam),Cp,= 原信息表的一个属性约简，证明完毕， (aVa2V.Vanv am+1V.…Van-1Van),而 推论1在差别向量组中，每个差别向量的 根据差别向量组和信息表的对应关系可知，这两 差别属性集合如果含有部分相同的属性集，则这 个差别属性集合在求解属性约简过程中是一种逻 些相同属性集中任一个属性集都是原信息表的属 辑合取关系，即逻辑表达式为： 性约简 CD,A CD=(ai V az V...Vam)A 推论2在差别向量组中，每个差别向量的 (aiV azV…V an V am+iV…Va-iVan)= 差别属性集合如果含有部分相同的属性，则在属 (aVa2V…Vam)A(aVaV.…Van)V 性全集中，这些相同属性集中的补集即为原信息 (am+iV.…Van-1Van)= 表的冗余属性集 ((aiv azv...vam)A(aiV azv...Va))V 推论3在差别向量组中，每个差别向量的 ((aiva2v...Va)A(am+iV...Va-iV a))= 差别属性集合如果仅含有1个相同的属性集，则 这个相同属性集就是原信息表的属性约简 (aiV a2V...Vm)=CD 定理4在差别向量组中任取两个差别向量 也可以从粗糙集的等价关系角度考虑，因为 VD,VD,做加法运算，如果它们的差别属性集合 IND(CD,)=IND(CD,),它们具有相同的分类能 力，而现在又是在求属性约简，因此可以说C如，就 为CD,CD,且存在C,三CD,则用CD,作为它们 是CD,的属性约简，同时，根据差别向量组和信息 相加后的差别属性集合不会改变原信息表的属性 约简 表的对应关系可知，整个差别向量组中各个差别 属性集合是一种逻辑合取关系： 证明：设Cn,={a1,a2,,an{,CD,={a1, CD,ACD,A…ACD,A…ACD,A…ACD= a2,…,am,am+1,…,an-1,an},由差别向量构造 Cp,ACD,A…(CD,A CD,)A…ACp= 的方法可知，每一个差别属性集合在数理逻辑中1∙2 算法相关定理证明 根据上述定义及差别向量加法法则可以得 到如下定理： 定理1 在一个差别向量中如果它的频率 向量中的某一项元素取值为1则该元素所对应 的属性为原信息表的核属性． 证明：令频率向量中的任意一个 f （ ai）＝1 因为 F＝（ f （ a1）f （ a2）…f （ an ））f （ ai）＝ 1 ｜CD｜ ＝1所以｜CD｜＝1也就是差别向量中的差 别属性集只有一个属性而在整个属性集合中也 只有这个属性能够区分这两个对象因此这个属 性就是原信息表的核属性．证明完毕． 定理2 在差别向量组中每个差别向量的 差别属性集合必不能取空值． 证明：因为差别向量组描述的是整个信息表 的可分辨情况所以每一个差别属性集包含的都 是能够区分某一对象对的属性．设某一个差别向 量 VDi＝（ OiCDiFi）Oi＝（ xixj）如果 CDi＝ ∅则说明在原信息表中所有的属性都不能区分 Oi 中的对象 xi 与 xj那么根据粗糙集等价类的 概念对象 xi 与 xj 为同一类这与题设中 VDi＝ （ OiCDiFi）是一个差别向量相矛盾．因此在差 别向量组中每个差别向量的差别属性集合必不 能取空值． 定理3 在差别向量组中每个差别向量的 差别属性集合取值为全属性则任一个属性都是 原信息表的属性约简． 证明：设原信息表中任意两个可分辨对象转 化的差别向量为 VDi ＝（ OiCDiFi）则整个信 息表转化的差别向量组为 VDT ＝（ OTCDT FT ）即 VDT＝ ∪ n i＝ i VDi．如果信息表中的全部属性 为｛a1a2…an｝由题意知∀ i≤ n都有 CDi ＝｛a1a2…an｝由于每一个差别集合在数理 逻辑中是析取关系即 CDi＝ a1∨ a2∨…∨ an又 根据差别向量组和信息表的对应关系可知整个 差别向量组中各个差别向量是一种逻辑合取关 系即逻辑表达式为： ∧ n i＝1 CDi＝（ a1∨ a2∨…∨ an）∧（ a1∨ a2∨…∨ an）∧…∧（ a1∨ a2∨…∨ an） n个（ a1∨ a2∨…∨ a n ） ＝（ a1∨ a2∨…∨ an）． 因此｛a1a2…an｝中的任意一个元素都将是 原信息表的一个属性约简．证明完毕． 推论1 在差别向量组中每个差别向量的 差别属性集合如果含有部分相同的属性集则这 些相同属性集中任一个属性集都是原信息表的属 性约简． 推论2 在差别向量组中每个差别向量的 差别属性集合如果含有部分相同的属性则在属 性全集中这些相同属性集中的补集即为原信息 表的冗余属性集． 推论3 在差别向量组中每个差别向量的 差别属性集合如果仅含有1个相同的属性集则 这个相同属性集就是原信息表的属性约简． 定理4 在差别向量组中任取两个差别向量 VDiVDj做加法运算如果它们的差别属性集合 为 CDiCDj且存在 CDi⊆CDj则用 CDi作为它们 相加后的差别属性集合不会改变原信息表的属性 约简． 证明：设 CDi＝｛a1a2…am｝CDj ＝｛a1 a2…amam＋1…an—1an｝由差别向量构造 的方法可知每一个差别属性集合在数理逻辑中 是析取关系即 CDi＝（ a1∨ a2∨…∨ am ）CDj＝ （ a1∨ a2∨…∨ am∨ am＋1∨…∨ an—1∨ an）而 根据差别向量组和信息表的对应关系可知这两 个差别属性集合在求解属性约简过程中是一种逻 辑合取关系即逻辑表达式为： CDi∧CDj＝（ a1∨ a2∨…∨ am）∧ （ a1∨ a2∨…∨ am∨ am＋1∨…∨ an—1∨ an）＝ （ a1∨ a2∨…∨ am）∧（（ a1∨ a2∨…∨ am）∨ （ am＋1∨…∨ an—1∨ an））＝ （（ a1∨ a2∨…∨ am）∧（ a1∨ a2∨…∨ am））∨ （（ a1∨a2∨…∨am）∧（ am＋1∨…∨an—1∨an））＝ （ a1∨ a2∨…∨m）＝CDi． 也可以从粗糙集的等价关系角度考虑因为 IND（CDi ）＝IND（ CDj ）它们具有相同的分类能 力而现在又是在求属性约简因此可以说 CDi就 是 CDj的属性约简．同时根据差别向量组和信息 表的对应关系可知整个差别向量组中各个差别 属性集合是一种逻辑合取关系： CD1∧CD2∧…∧CDi∧…∧CDj ∧…∧CDn＝ CD1∧CD2∧…∧（CDi∧CDj ）∧…∧CDn＝ Vol．28No．6 鄂旭等： 基于扫描向量的属性约简方法 ·605·