D0I:10.13374/1.issnl00I53.2006.06.021 第28卷第6期 北京科技大学学报 Vol.28 No.6 2006年6月 Journal of University of Science and Technology Beijing Jun.2006 基于扫描向量的属性约简方法 鄂旭2) 高学东)喻斌) 1)辽宁工学院计算机系，锦州1210012)北京科技大学管理学院，北京100083 摘要针对粗糙集理论中属性约简问题，提出了一种基于扫描向量的属性约简方法，根据粗糙 集理论知识，定义了一个新概念一差别向量，利用差别向量将信息表转换成差别向量组：根据差 别向量的结构特征，定义了差别向量加法法则：运用这个加法法则仅需对差别向量组扫描一次，就 可以形成结构简洁却能代表原信息表属性特征的扫描向量·以扫描向量中的属性频率项作为属性 约简搜索的启发信息，提高了属性约简效率·数值实例及数据库测试的结果表明该属性约简算法 是有效可行的· 关键词粗糙集：信息表：属性约简；差别属性集：扫描向量 分类号TP311 粗糙集理论山是20世纪80年代初由波兰华 设决策表为S=(U,A,V,f),其中论域 沙理工大学Pawlak教授提出的，近几年来，粗糙 U=x1,x2,…,xm}是一个非空有限对象集合； 集已经成为数据挖掘2研究中的一种有效分析 A是对象的属性集合，分别由条件属性集C= 方法，被应用在分类分析、聚类分析等算法5-可] {a|i=1,…,m}和决策属性集D={d}两个不 中。属性约简是粗糙集理论中的核心内容之一， 相交的子集组成，即A=CUD;a:(x)是样本： 目前国内外学者已经提出了许多属性约简的方 在属性a:上的取值.定义一个三元组作为差别向 法，如Hu等人[可、Jelonek等人[8]提出的基于分 量，VD=(O,CD,F),其中O为可区分对象对； 辨矩阵的属性约简方法：苗夺谦等人提出了基于 CD为差别属性集， 信息论中信息熵概念910的属性约简算法等，人 CD 们试图能够找到最佳属性约简，然而Wog和 {a4a4∈CAa4(xi)≠()l,d(xi)≠d(xj) Ziarko已经证明求解最简属性约简问题是NP一 0, d(xi)=d(x） hard问题山).目前，还没有一种公认、有效的约 F为一个频率向量，F=（f(a1)f(a2),…, 简方法，主要问题是计算属性重要性过程重复繁 f(a),它的每一项表示该属性出现的频率， 琐、求解核属性的过程复杂、候选属性数目过多极 1/lCnl,a:∈Cn 易造成属性组合爆炸1012] f(a)= 0, a;CD 本文在定义了差别向量、差别向量组、差别向 由定义可以看出，f(a)越大，属性a:的重要 量的加法运算法则及扫描向量的基础上，提出了 性越强，可以借助上面的定义，把一个给定的信 一种新的属性约简方法，实验结果表明该算法是 息表转化成与其等价的差别向量组，即VD,T= 有效可行的 (Vn,V,…,VD.,其中，它的任一项元素VD,= (O,CD,F:),n为可区分对象对的个数.利用 1 相关概念及定理 差别向量的结构特征，定义差别向量加法法则：现 1.1算法相关概念 有两个差别向量VD,=(O,CD,F),Vp,= 粗糙集理论中包含很多概念5)，这里只介 （0,CDF),令VD+VD=(Og CDF),其 绍与本算法有关的几个新概念 中，0g=0:U0,Fy=F:十E=(f(a)+ fji(a)fi(a2)十fi(a2),…,f(am)十fj(an)), 收稿日期：2005-03-29修回日期：2005-09-12 Co CDCCD 基金项目：国家自然科学基金(No.70572070),博士后基金(N。- 2005038319):教育部春晖项目(No-Z一1-15007)和教育部博士 CD CD' CDCD, 点科研基金(Na.20040147006) 作者简介：鄂旭(1971一)，男，副教授，博士 CD,UCD,(CD,CCD)n(CD,CD,)
基于扫描向量的属性约简方法 鄂 旭12） 高学东1） 喻 斌1） 1） 辽宁工学院计算机系锦州121001 2） 北京科技大学管理学院北京100083 摘 要 针对粗糙集理论中属性约简问题提出了一种基于扫描向量的属性约简方法．根据粗糙 集理论知识定义了一个新概念———差别向量利用差别向量将信息表转换成差别向量组；根据差 别向量的结构特征定义了差别向量加法法则；运用这个加法法则仅需对差别向量组扫描一次就 可以形成结构简洁却能代表原信息表属性特征的扫描向量．以扫描向量中的属性频率项作为属性 约简搜索的启发信息提高了属性约简效率．数值实例及数据库测试的结果表明该属性约简算法 是有效可行的． 关键词 粗糙集；信息表；属性约简；差别属性集；扫描向量 分类号 TP311 收稿日期：20050329 修回日期：20050912 基金项目：国家自然科学基金（No．70572070）博士后基金（No． 2005038319）；教育部春晖项目（No．Z—1—15007）和教育部博士 点科研基金（No．20040147006） 作者简介：鄂旭（1971—）男副教授博士 粗糙集理论［1］是20世纪80年代初由波兰华 沙理工大学 Pawlak 教授提出的．近几年来粗糙 集已经成为数据挖掘［24］研究中的一种有效分析 方法被应用在分类分析、聚类分析等算法［56］ 中．属性约简是粗糙集理论中的核心内容之一 目前国内外学者已经提出了许多属性约简的方 法如 Hu 等人［7］、Jelonek 等人［8］ 提出的基于分 辨矩阵的属性约简方法；苗夺谦等人提出了基于 信息论中信息熵概念［910］的属性约简算法等．人 们试图能够找到最佳属性约简然而 Wong 和 Ziarko 已经证明求解最简属性约简问题是 NP— hard 问题［11］．目前还没有一种公认、有效的约 简方法主要问题是计算属性重要性过程重复繁 琐、求解核属性的过程复杂、候选属性数目过多极 易造成属性组合爆炸［1012］． 本文在定义了差别向量、差别向量组、差别向 量的加法运算法则及扫描向量的基础上提出了 一种新的属性约简方法实验结果表明该算法是 有效可行的． 1 相关概念及定理 1∙1 算法相关概念 粗糙集理论中包含很多概念［56］这里只介 绍与本算法有关的几个新概念． 设决策表为 S ＝（ UAV f ）其中论域 U＝｛x1x2…x n｝是一个非空有限对象集合； A 是对象的属性集合分别由条件属性集 C＝ ｛ai｜i＝1…m｝和决策属性集 D＝｛d｝两个不 相交的子集组成即 A＝C∪ D；ai（ xj）是样本 xj 在属性 ai 上的取值．定义一个三元组作为差别向 量VD＝（ OCDF）其中 O 为可区分对象对； CD 为差别属性集 CD＝ ｛ak｜ak∈ C∧ ak（ xi）≠ ak（ xj）｝ d（ xi）≠ d（ xj） 0 d（ xi）＝ d（ xj） F 为一个频率向量F ＝ （ f （ a1）f （ a2）… f （ an））它的每一项表示该属性出现的频率 f （ ai）＝ 1／｜CD｜ ai∈CD 0 ai∈／CD 由定义可以看出f （ ai）越大属性 ai 的重要 性越强．可以借助上面的定义把一个给定的信 息表转化成与其等价的差别向量组即 VDT ＝ （VD1VD2…VDn其中它的任一项元素 VDi＝ （ OiCDiFi）n 为可区分对象对的个数．利用 差别向量的结构特征定义差别向量加法法则：现 有两个差别向量 VDi ＝（ OiCDiFi）VDj ＝ （ OjCDjFj）令 VDi＋ VDj ＝（ OijCDijFij）其 中Oij ＝ Oi ∪ OjFij ＝ Fi ＋ Fj ＝ （ f i （ a1） ＋ f j（ a1）f i（ a2）＋ f j（ a2）…f i（ an）＋ f j（ an）） CDij＝ CDi CDi⊆CDj CDj CDj ⊆CDi CDi∪CDj （CDi⊄CDj ）∩（CDj ⊄CDi ） 第28卷 第6期 2006年 6月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．28No．6 Jun．2006 DOI:10．13374／j．issn1001－053x．2006．06．021
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·
,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期
Vol.28 No.6 鄂旭等：基于扫描向量的属性约简方法 607. 最小属性约简 表2差别向量组 Table 2 Discernible vector array 0 CD F 0 CD F (x1,x2) (b.e.g) (0,1/3.0,0,1/3,1/3) (x3,x4) (b.c,d) (0,1/3,1/3,1/3,0,0) (x1,x3) (b,c.d,e,g) (0,1/5,1/5,1/5,1/5,1/5) (x3,x5) (a,b,c,d) (1/4,1/4,1/4,1/4,0,0) (x1,x4) (c.d,e,g) (0,0,1/4,1/4,1/4,1/④ (x3,x6) (a,b,c,d) (1/4,1/4,1/4,1/4,0,0) (x1,x5) (a e,g) (1/3,0,0,0,1/3,1/3) （x3,3x7) (b,c,d) (0,1/3,1/3,1/3,0,0) (x1,x6) (a,e,g) (1/3,0,0,0,1/3,1/3) (x4,x5) (a.c,d) (1/3,0,1/3,1/3.0,0) (x1,x7) (e,g) (0,0,0,0,1/2,1/2) (x4,x6) (a.c,d) (1/3,0,1/3,1/3.0,0) (x2,x3) (b,c.d,e,q) (0,1/5,1/5,1/5,1/5,1/5) (x4,x7) (c,d) (0,0.1/2.1/2,0,0) (x2x4） (b,c,d,e,g） (0,1/5,1/5,1/5,1/5,1/5) (x5,x6) (a) (1,0,0,0,0,0,0) (x2,x5) (a:b,e,g) (1/4,1/4,0,0,1/4,1/4 (x5,x7) (a) (1,0,0,0,0,0,0) (x2:x6) (a.b,e,q) (1/4,1/4,0,0,1/4,1/4) (x6,x7) (a) (1,0,0,0,0,0,0) (x2,x7) (b,e,g） (0,1/3,0,0,1/3,1/3) 为了进一步验证本算法的有效性，从世界著 低寻找属性约简集的搜索范围，从数值实例和数 名的测试数据库UCI中挑选了3个典型的数据 据库运算结果可以看出本文的算法是有效可 库，利用本文提出的算法做测试，测试结果如图1 行的 所示 参考文献 60 [1]Pawlak Z.Rough set.Int J Comput Inf Sci.1982 (1):341 [2]鄂旭，高学东，武森，等。信息表中不完备数据的填补方法 42 Mushroon Lung Cancer Balloon 北京科技大学学报，2005,27(3)：364 (adult-stretch) [3]鄂旭，高学东，谭文东，等.基于超立方体与信息熵的离散 划试数据库 化方法.北京科技大学学报，2005,27(6)：760 图1属性约简对比图 [4]武森，高学东，Bastian M.数据仓库与数据挖掘.北京：冶 Fig.1 Results of attributes reduction 金工业出版社，2003 [5]王国胤.Rough集理论与知识获取.西安：西安交通大学出 版社，2003 4 结论 [6]张文修，吴伟志，梁吉业，等.粗糙集理论与方法.北京： 科学出版社，2001 根据原始信息表，应用粗糙集中的不可分辨 [7]Hu X H.Cercone N.Learning in relational databases:a rough 关系将原始信息表转换成差别向量组，由于在差 set approach.Comput Intell.1995,11(2):323 别向量中定义了频率向量，同时又根据相应的定 [8]Jelonek J,Krawiec K,Slowinski R.Rough set reduction of 理证明定义了差别向量的加法运算，因此本算法 attributes and their domains for neural networks.Comput In" tel,1995,11(2):339 大大降低了算法的时间复杂，经典的基于分辨矩 [9]苗夺谦.Rough Set理论中连续属性的离散化方法.自动化 阵的属性约简算法，如Hu的差别矩阵方法[8]求 学报，2001,27(3)：296 核属性的时间复杂度为O(nm),n=card(u), [10]孟庆生：信息论.西安：西安交通大学出版社，1986 m=card(c):而本算法只是通过对差别向量进行 [11]Wong S K M,Ziarko W.On optional decision rules in deci- 一次扫描就能将核属性识别出来，算法的时间复 sion tables.Bull Pol Acad Sci.1985.33,693 [12]Ohrn A.Discernibility and Rough Sets in Medicine:Tools 杂度最大仅为O(nm)·同时在识别核属性的过 and Applications [Dissertation].Trondheim:Department of 程中通过差别向量的加法运算，形成了数目少却 Computer and Information Science.Norwegian University 具有典型代表意义的差别属性集，这样将大大降 and Science and Technology,1999:53
最小属性约简． 表2 差别向量组 Table2 Discernible vector array O CD F O CD F （ x1x2） （ beg） （01／3001／31／3） （ x1x3） （ bcdeg） （01／51／51／51／51／5） （ x1x4） （ cdeg） （001／41／41／41／4） （ x1x5） （ aeg） （1／30001／31／3） （ x1x6） （ aeg） （1／30001／31／3） （ x1x7） （ eg） （00001／21／2） （ x2x3） （ bcdeg） （01／51／51／51／51／5） （ x2x4） （ bcdeg） （01／51／51／51／51／5） （ x2x5） （ abeg） （1／41／4001／41／4） （ x2x6） （ abeg） （1／41／4001／41／4） （ x2x7） （ beg） （01／3001／31／3） （ x3x4） （ bcd） （01／31／31／300） （ x3x5） （ abcd） （1／41／41／41／400） （ x3x6） （ abcd） （1／41／41／41／400） （ x3x7） （ bcd） （01／31／31／300） （ x4x5） （ acd） （1／301／31／300） （ x4x6） （ acd） （1／301／31／300） （ x4x7） （ cd） （001／21／200） （ x5x6） （ a） （1000000） （ x5x7） （ a） （1000000） （ x6x7） （ a） （1000000） 为了进一步验证本算法的有效性从世界著 名的测试数据库 UCI 中挑选了3个典型的数据 库利用本文提出的算法做测试测试结果如图1 所示． 图1 属性约简对比图 Fig．1 Results of attributes reduction 4 结论 根据原始信息表应用粗糙集中的不可分辨 关系将原始信息表转换成差别向量组．由于在差 别向量中定义了频率向量同时又根据相应的定 理证明定义了差别向量的加法运算因此本算法 大大降低了算法的时间复杂．经典的基于分辨矩 阵的属性约简算法如 Hu 的差别矩阵方法［8］ 求 核属性的时间复杂度为 O（ n 2m）n＝card（ u） m＝card（ c）；而本算法只是通过对差别向量进行 一次扫描就能将核属性识别出来算法的时间复 杂度最大仅为 O（ nm）．同时在识别核属性的过 程中通过差别向量的加法运算形成了数目少却 具有典型代表意义的差别属性集这样将大大降 低寻找属性约简集的搜索范围．从数值实例和数 据库运算结果可以看出本文的算法是有效可 行的． 参 考 文 献 ［1］ Pawlak Z．Rough set．Int J Comput Inf Sci1982（1）：341 ［2］ 鄂旭高学东武森等．信息表中不完备数据的填补方法． 北京科技大学学报200527（3）：364 ［3］ 鄂旭高学东谭文东等．基于超立方体与信息熵的离散 化方法．北京科技大学学报200527（6）：760 ［4］ 武森高学东Bastian M．数据仓库与数据挖掘．北京：冶 金工业出版社2003 ［5］ 王国胤．Rough 集理论与知识获取．西安：西安交通大学出 版社2003 ［6］ 张文修吴伟志梁吉业等．粗糙集理论与方法．北京： 科学出版社2001 ［7］ Hu X HCercone N．Learning in relational databases：a rough set approach．Comput Intell199511（2）：323 ［8］ Jelonek JKrawiec KSlowinski R．Rough set reduction of attributes and their domains for neural networks．Comput Intell199511（2）：339 ［9］ 苗夺谦．Rough Set 理论中连续属性的离散化方法．自动化 学报200127（3）：296 ［10］ 孟庆生．信息论．西安：西安交通大学出版社1986 ［11］ Wong S K MZiarko W．On optional decision rules in decision tables．Bull Pol Acad Sci198533：693 ［12］ Ohrn A．Discernibility and Rough Sets in Medicine：Tools and Applications ［Dissertation ］．Trondheim：Department of Computer and Information ScienceNorwegian University and Science and Technology1999：53 Vol．28No．6 鄂旭等： 基于扫描向量的属性约简方法 ·607·
,608 北京科技大学学报 2006年第6期 A method for attributes reduction based on scan vector EXu2),GAO Xuedong,YU Bin) 1)Department of Computer Science.Liaoning Institute of Technology.Jinzhou 121001,China 2)Management School.University of Science and Technology Beijing.Beijing 100083.China ABSTRACI In order to deal with attributes reduction,one of the major problems in rough set theory,an attributes reduction algorithm was proposed based on scan vector,and a new conception of discernible vec- tor was defined by which the information table can be transformed into discernible vector sets.Depending on the structural feature of the discernible vector,a plus rule for the discernible vector sets was defined,and a scan vector with concise structure but representing the information table can be obtained through scanning the discernible vector just one time.The item of attribute frequency in the scan vector was taken as heuris- tic information to improve the efficiency of attributes reduction.An illustration and experimental results in- dicate that the method proposed is much more effective. KEY WORDS rough set;information table;attributes reduction:discernible attributes set;scan vector (上接第586页) Numerical simulation on heat transfer of impinging slot jet LIU Guoyong,LI Mouwei,WANG Bangwen,ZHANG Shaojun,LI Shengyong,HUANG Yan Mechanical Engineering School.University of Science and Technology Beijing,Beijing 100083.China ABSTRACI Numerical simulation with the standard ke model was performed to study single phase con- vective heat transfer at the impinging zone of non-immersed slot jet.The factors considered were jet veloci- ty,spacing of nozzle to impinging plate (height),slot width,angle between jet direction and plate,tem- peratures of impinged plate and water (liquid)from the slot nozzle.The results show that jet velocity is the most remarkable factor influencing heat transfer at the impinging zone,and other factors such as water temperature and slot width are also non-negligible.The angle between jet direction and impinging plate on- ly influences the distribution of local convective heat transfer coefficient. KEY WORDS slot;impinging jet;convective heat transfer:k model;numerical simulation
A method for attributes reduction based on scan vector E Xu 12）GAO Xuedong 1）Y U Bin 1） 1） Department of Computer ScienceLiaoning Institute of TechnologyJinzhou121001China 2） Management SchoolUniversity of Science and Technology BeijingBeijing100083China ABSTRACT In order to deal with attributes reductionone of the major problems in rough set theoryan attributes reduction algorithm was proposed based on scan vectorand a new conception of discernible vector was defined by which the information table can be transformed into discernible vector sets．Depending on the structural feature of the discernible vectora plus rule for the discernible vector sets was definedand a scan vector with concise structure but representing the information table can be obtained through scanning the discernible vector just one time．The item of attribute frequency in the scan vector was taken as heuristic information to improve the efficiency of attributes reduction．An illustration and experimental results indicate that the method proposed is much more effective． KEY WORDS rough set；information table；attributes reduction；discernible attributes set；scan vector （上接第586页） Numerical simulation on heat transfer of impinging slot jet LIU GuoyongLI MouweiWA NG BangwenZHA NG ShaojunLI ShengyongHUA NG Y an Mechanical Engineering SchoolUniversity of Science and Technology BeijingBeijing100083China ABSTRACT Numerical simulation with the standard k—εmodel was performed to study single-phase convective heat transfer at the impinging zone of non-immersed slot jet．The factors considered were jet velocityspacing of nozzle-to-impinging plate （height）slot widthangle between jet direction and platetemperatures of impinged plate and water （liquid） from the slot nozzle．The results show that jet velocity is the most remarkable factor influencing heat transfer at the impinging zoneand other factors such as water temperature and slot width are also non-negligible．The angle between jet direction and impinging plate only influences the distribution of local convective heat transfer coefficient． KEY WORDS slot；impinging jet；convective heat transfer；k—εmodel；numerical simulation ·608· 北 京 科 技 大 学 学 报 2006年第6期