D0I:10.13374/1.issnl00I53.2006.09.021 第28卷第9期 北京科技大学学报 Vol.28 No.9 2006年9月 Journal of University of Science and Technology Beijing Sep·2006 一种不完备信息表的预处理方法 鄂旭②)高学东)邵良杉) 叶柏青) 1)辽宁工学院计算机系，锦州1210012)北京科技大学管理学院，北京100083 3)辽宁工程技术大学管理学院，阜新123000 摘要针对不完备信息表预处理问题中的不完备数据的填补问题、冗余属性的约简问题和连续 属性的离散化问题进行了研究·应用粗糙集理论，由相容信息表中条件属性与决策属性间的一致 性对应关系，定义了划分区间的加法运算，解决了不完备数据填补问题：根据类别概念，定义了差 别向量，利用差别向量加法运算删除了冗余属性：根据条件属性与决策属性之间的依赖关系及相 对信息熵概念，实现了连续属性的离散化.数值示例和实验结果显示此方法是有效可行的 关键词不完备信息表：粗糙集：信息熵：属性约简：离散化 分类号TP301.6 由于市场竞争日趋激烈，各行各业在其经营 理论相结合的方法门等，但这些方法或由于没有 活动中都引入了电子、通信、计算机等先进技术， 考虑条件属性与决策属性之间的相互关系，而在 因此都沉积了大量的历史数据，这些数据千差万 信息表中产生大量冲突事件，或由于在离散过程 别，因此在分析这些数据前一般都要进行数据预 中缺乏启发搜索信息，而导致计算复杂度很高· 处理，以得到满足一定算法要求的格式化数据. 本文针对上述问题，在保持原有信息表分类 粗糙集中是进行数据预处理的有力工具，能够实 能力不变的情况下，提出了一种不完备信息表的 现不完备数据的填补、冗余属性的约简及连续属 预处理方法， 性的离散化， 目前，填补不完备数据的方法有均值法、最大 1相关定义及定理 频率法[2]等.在这些方法中，以信息表中所有断 1.1相关定义 点的平均值或各个断点出现的频率来代替不完备 粗糙集中各基本概念见文献[3]，与本算法相 的数据，这些方法虽然简单，但由于没有考虑原 关的重要概念及定义如下， 有信息表的分类信息，因此填补数据后很容易产 设信息系统为s=(U,A,V,),其中U是 生冲突事件 一个非空有限对象集合，U={x1,x2,…,xn}, 信息表中常常含有对分析主题无用的属性， 式子中的x:为对象：A是对象的属性集合，分为 需要删除掉，目前，国内外学者己经提出了许多 两个不相交的子集，即条件属性集C和决策属性 属性约简的方法，如基于分辨矩阵的属性约简方 集D,A=CUD:V是属性值的集合，V= 法]：基于信息嫡概念的属性约简算法6]等。但 U(Va),a∈A,Va是属性a的值域：f是一个函 普遍存在求解核属性过程复杂等缺点 数，即UXA→V是一个映射函数，它为每个对 由于粗糙集只能处理离散型数据，因此在应 象的每个属性赋予一个属性值，即Ha∈A,x:∈ 用粗糙集理论进行数据挖掘时，必须要先对连续 U,f(xia)∈Va 型数据进行离散化·目前离散方法有等距离划 定义1设HB三C,c∈C,U'=U- 分、等频率划分、Naive Scaler、布尔逻辑和粗糙集 POSB(D)是粗糙边界，则可以定义属性c的重要 收稿日期：2005-04-18修回日期：2005-09-13 性公式： 基金项目：国家自然科学基金资助项目(No-70271068),博士后 sig(c)=IPOSUe(D)I/IPOS (D)I (1) 科学基金资助项目(2005038319)，教有部春晖项目(Z-1一 定义2设决策种类的个数为r(d),属性a 15007),教育部博士点科研基金资助项目(20040147006)和科技 的值域V。上的一个断点记为(a,c),其中，a∈ 攻关项目(2005219005) 作者简介：鄂旭(1971一)男，教授，博士 A,c为实数值，在值域V.=[la,ra]上的任意一
一种不完备信息表的预处理方法 鄂 旭12） 高学东2） 邵良杉3） 叶柏青3） 1） 辽宁工学院计算机系锦州121001 2） 北京科技大学管理学院北京100083 3） 辽宁工程技术大学管理学院阜新123000 摘 要 针对不完备信息表预处理问题中的不完备数据的填补问题、冗余属性的约简问题和连续 属性的离散化问题进行了研究．应用粗糙集理论由相容信息表中条件属性与决策属性间的一致 性对应关系定义了划分区间的加法运算解决了不完备数据填补问题；根据类别概念定义了差 别向量利用差别向量加法运算删除了冗余属性；根据条件属性与决策属性之间的依赖关系及相 对信息熵概念实现了连续属性的离散化．数值示例和实验结果显示此方法是有效可行的． 关键词 不完备信息表；粗糙集；信息熵；属性约简；离散化 分类号 TP301∙6 收稿日期：20050418 修回日期：20050913 基金项目：国家自然科学基金资助项目（No．70271068）博士后 科学 基 金 资 助 项 目 （2005038319）教 育 部 春 晖 项 目 （Z－1－ 15007）教育部博士点科研基金资助项目（20040147006）和科技 攻关项目（2005219005） 作者简介：鄂 旭（1971－）男教授博士 由于市场竞争日趋激烈各行各业在其经营 活动中都引入了电子、通信、计算机等先进技术 因此都沉积了大量的历史数据．这些数据千差万 别因此在分析这些数据前一般都要进行数据预 处理以得到满足一定算法要求的格式化数据． 粗糙集［1］是进行数据预处理的有力工具能够实 现不完备数据的填补、冗余属性的约简及连续属 性的离散化． 目前填补不完备数据的方法有均值法、最大 频率法［24］等．在这些方法中以信息表中所有断 点的平均值或各个断点出现的频率来代替不完备 的数据．这些方法虽然简单但由于没有考虑原 有信息表的分类信息因此填补数据后很容易产 生冲突事件． 信息表中常常含有对分析主题无用的属性 需要删除掉．目前国内外学者已经提出了许多 属性约简的方法如基于分辨矩阵的属性约简方 法［5］；基于信息熵概念的属性约简算法［6］等．但 普遍存在求解核属性过程复杂等缺点． 由于粗糙集只能处理离散型数据因此在应 用粗糙集理论进行数据挖掘时必须要先对连续 型数据进行离散化．目前离散方法有等距离划 分、等频率划分、Naïve Scaler、布尔逻辑和粗糙集 理论相结合的方法［7］等．但这些方法或由于没有 考虑条件属性与决策属性之间的相互关系而在 信息表中产生大量冲突事件或由于在离散过程 中缺乏启发搜索信息而导致计算复杂度很高． 本文针对上述问题在保持原有信息表分类 能力不变的情况下提出了一种不完备信息表的 预处理方法． 1 相关定义及定理 1∙1 相关定义 粗糙集中各基本概念见文献［3］与本算法相 关的重要概念及定义如下． 设信息系统为 s＝〈UAV f〉其中 U 是 一个非空有限对象集合U ＝｛x1x2…x n｝ 式子中的 xi 为对象；A 是对象的属性集合分为 两个不相交的子集即条件属性集 C 和决策属性 集 D A ＝ C ∪ D；V 是属性值的集合V ＝ ∪（ V a）a∈ AV a 是属性 a 的值域；f 是一个函 数即 U × A → V 是一个映射函数它为每个对 象的每个属性赋予一个属性值即∀ a∈ Axi∈ Uf （ xia）∈ V a． 定义 1 设 ∀B ⊆ Cc ∈ CU′＝ U － POS U B （ D）是粗糙边界则可以定义属性 c 的重要 性公式： sig（ c）＝｜POS U′ B∪｛c｝（ D）｜／｜POS U B （ D）｜ （1） 定义2 设决策种类的个数为 r（ d）属性 a 的值域 V a 上的一个断点记为（ ac）其中a∈ Ac 为实数值．在值域 V a＝［ lara ］上的任意一 第28卷 第9期 2006年 9月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．28No．9 Sep．2006 DOI:10．13374／j．issn1001－053x．2006．09．021
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·
.904 北京科技大学学报 2006年第9期 定理3设HB三C,Hc∈C且cB,U'= 决策类进行步骤5的操作. U一P0Sg(D)为粗糙边界，则有： 步骤5在同一决策类中，设条件属性B'三 IPOSUIe(D)= B≤A,对Hx:∈MOS进行如下操作： IPOSUI(D)I-IPOS (D)I. ()若∈B,且rB(F)=rB\B(F),则由 证明对Hc∈C且cB有两种情况 推论知4(x:)可以取任一断点值. (1)若c为冗余属性，则： (2)否则，进行如下操作： IPOSEUI(D)I=IPOS (D)I=0, ①对Hx:∈MOS,在属性集B\{B'}中计算 IPOSHU(D)I=IPOS (D)I-IPOS (D)I=0. NS(xi): (2)若c为重要属性，则： ②若NS(x)=y,则令a4(xi)=a(y): U'=U-POSB(D), ③若NS(x)=y1,y2,…,ym},则令y=yi 即 (y:的等价类的势最大)，且a(xi)=a(y) U=U'十POSB(D)· (3)直至全部x:∈MOS操作完毕， 步骤6在决策表中取第二个分类，进行步 所以有 骤5的操作.直至所有决策类进行操作完毕，最 POSEUIci(D)=POS D)UPOSHUICI(D), 后得到新的信息表S只U,A,V,)· IPOSUI(D)=IPOSAUI(D)1++IPOS(D)1. 步骤7根据超立方体的概念，对每个属性 定理4在一个差别向量中，如果它的频率 进行泛化： 向量中的某一项元素取值为1，则该元素所对应 (1)按照决策属性对信息表中的实例进行归 的属性为原信息表的核属性 类 证明依据题意，令频率向量中的任意一个 (2)对同一个类别的实例进行泛化· f(a)=1.因为F=(f(a1),f(a2),…,f(an), 步骤8根据步骤7求取整体离散化断点 f(a)=DC=1,所以DC|=1.也就是差别向 集 量中的差别属性集只有一个属性，而在整个属性 初始化始断点集W=①： 集合中也只有这个属性能够区分这两个对象，因 F0R(=l;≤n:i++) 此这个属性就是原信息表的核属性 取属性：的各类泛化区间进行两两比较，如任 意选两个泛化区间[，]，[，]进行比较(j, 2不完备信息表预处理算法的描述 k为决策类标示号)： 设原始信息系统为s=(U°，A°，V,9, f<<<,则新取断点集W={,}; 计算信息表相对信息嫡E”. f<<<,则新取断点集W=马，}： 步骤1根据原始信息表建立差别向量组， others新取断点集W/i=,};W=WUWi} 进行差别向量加法运算， 输出W. 步骤2在U\MOS中计算各属性值的重 步骤9根据信息表中断点集，计算此时信 要性，并按照属性的重要性从左到右降序排列形 息表相对信息熵E,如果E>E”,则执行步骤 成序偶(a1,a2,…,an),MOS排在信息表的最后， 10;否则执行步骤12. 建立新的信息表S'只U',A',V',f)· 步骤10在差别向量组中对不同类别对象 步骤3设U\MOS中每个属性a:的断点 进行如下操作： 集P,断点为P(j=1,2,,n一1)，与之相邻的 假设不同类别对象的两个离散区间为[， 两个值x,x+1,并且xp<+1,对于每一个 ],[,],则： 属性a:进行如下操作： (1)若两个实例子集满足包含关系，则聚为 (1)令a=x,x=xj+1·若信息表无冲突， 一类. 则p=p\{P;否则，x=a,x+1=x+1 (2)若两个实例子集聚为一类后不包含异类 (2)直至全部属性操作完毕， 实例，则聚为一类 步骤4在信息表中按照决策属性对全部对 新形成的断点集为Wi=imin(,), 象分类，按各分类的势由大到小排序，并取第一个 max(u,u);
定理3 设∀B⊆ C∀c∈ C 且 c∈／BU′＝ U－POS U B （ D）为粗糙边界则有： ｜POS U′ B∪｛c｝（ D）｜＝ ｜POS U B∪｛c｝（ D）｜－｜POS U B （ D）｜． 证明 对∀c∈C 且 c∈／B 有两种情况． （1） 若 c 为冗余属性则： ｜POS U′ B∪｛c｝（ D）｜＝｜POS U′ B （ D）｜＝0 ｜POS U B∪｛c｝（D）｜＝｜POS U B （D）｜－｜POS U B （D）｜＝0． （2） 若 c 为重要属性则： U′＝ U－POS B（ D） 即 U＝ U′＋POS B（ D）． 所以有 POS U B∪｛c｝（ D）＝POS U B （ D）∪POS U′ B∪｛c｝（ D） ｜POS U B∪｛c｝（D）｜＝｜POS U′ B∪｛c｝（D）｜＋｜POS U B （D）｜． 定理4 在一个差别向量中如果它的频率 向量中的某一项元素取值为1则该元素所对应 的属性为原信息表的核属性． 证明 依据题意令频率向量中的任意一个 f （ ai）＝1．因为 F＝（ f （ a1）f （ a2）…f （ an）） f （ ai）＝ 1 ｜DC｜ ＝1所以｜DC｜＝1．也就是差别向 量中的差别属性集只有一个属性而在整个属性 集合中也只有这个属性能够区分这两个对象因 此这个属性就是原信息表的核属性． 2 不完备信息表预处理算法的描述 设原始信息系统为 S 0＝〈U 0A 0V 0f 0〉 计算信息表相对信息熵 E 0． 步骤1 根据原始信息表建立差别向量组 进行差别向量加法运算． 步骤2 在 U ＼MOS 中计算各属性值的重 要性并按照属性的重要性从左到右降序排列形 成序偶（ a1a2…an）MOS 排在信息表的最后 建立新的信息表 S′＝〈U′A′V′f′〉． 步骤3 设 U＼MOS 中每个属性 ai 的断点 集 P i断点为 P i j（ j＝12…n－1）与之相邻的 两个值 x i jx i j＋1并且 x i j＜P i j＜ x i j＋1对于每一个 属性 ai 进行如下操作： （1） 令 α＝ x i jx i j＝ x i j＋1．若信息表无冲突 则 P i＝P i＼｛P i j｝；否则x i j＝αx i j＋1＝ x i j＋1． （2） 直至全部属性操作完毕． 步骤4 在信息表中按照决策属性对全部对 象分类按各分类的势由大到小排序并取第一个 决策类进行步骤5的操作． 步骤5 在同一决策类中设条件属性 B′⊆ B≤ A对∀ xi∈MOS 进行如下操作： （1） 若 ak∈ B′且 rB （ F）＝ rB＼B′（ F）则由 推论知 ak（ xi）可以取任一断点值． （2） 否则进行如下操作： ① 对∀ xi∈MOS在属性集 B＼｛B′｝中计算 NS（ xi）； ② 若 NS（ xi）＝y则令 ak（ xi）＝ ak（ y）； ③ 若 NS（ xi）＝｛y1y2…ym｝则令 y＝yi （ yi 的等价类的势最大）且 ak（ xi）＝ ak（ y）． （3） 直至全部 xi∈MOS 操作完毕． 步骤6 在决策表中取第二个分类进行步 骤5的操作．直至所有决策类进行操作完毕最 后得到新的信息表 S＝〈UAV f〉． 步骤7 根据超立方体的概念对每个属性 进行泛化： （1） 按照决策属性对信息表中的实例进行归 类． （2） 对同一个类别的实例进行泛化． 步骤8 根据步骤7求取整体离散化断点 集． 初始化始断点集 W＝／○； FOR （ i＝1；i≤ n：i＋＋） ｛取属性 ai 的各类泛化区间进行两两比较如任 意选两个泛化区间［ l j iu j i ］［ l k iu k i ］进行比较（ j k 为决策类标示号）； If l i i＜ l k i＜ u j i＜ u k i则新取断点集 W i＝｛l k iu j i｝； If l j i＜ u j i＜ l k i ＜ u k i则新取断点集 W i＝｛l j iu k i｝； others 新取断点集 W i＝｛u k il j i｝；W＝ W∪ W i｝ 输出 W． 步骤9 根据信息表中断点集计算此时信 息表相对信息熵 E．如果 E＞ E 0则执行步骤 10；否则执行步骤12． 步骤10 在差别向量组中对不同类别对象 进行如下操作： 假设不同类别对象的两个离散区间为 ［ l j i u j i］［ l k iu k i ］则： （1） 若两个实例子集满足包含关系则聚为 一类． （2） 若两个实例子集聚为一类后不包含异类 实例则聚为一类． 新形 成 的 断 点 集 为 W i ＝｛min （ l j il k i ） max（ u j iu k i ）｝； ·904· 北 京 科 技 大 学 学 报 2006年第9期
Vol.28 No.9 鄂旭等：一种不完备信息表的预处理方法 .905. 步骤11根据W=WUW对信息表进行 P%+P9=[0,0.9]+[0.9,1.1]={[0,1),[1, 离散化并计算相对信息嫡E:如果E>E°，则执 1.1){,计算此时的相对信息熵E>E°，接着进行 行步骤10：否则执行步骤13 属性的划分区间的加法运算，直至所有划分区间 步骤12直至计算的相对信息熵E≤E”,结 操作完毕，得属性α的离散划分区间集为[0,1)， 束计算. [1,1.5),[1.15,1.25),[1.25,1.35),[1.35, 步骤13根据断点集W对信息表的属性值 1.7),[1.7,3),[3,4).同理对属性b也进行上述 进行相应的整数映射 操作，得离散划分区间集[0,1.5)，[1.5,2.5)， 3 数据实例及实验 [2.5,3). 表3完备表 设有一个原始表S=U,A,V,),如表1， Table 3 Completed tab 其中A=CUD,为条件属性和决策属性，根据 a b d a d 差别向量定义可以得到对象2和5的差别属性集 0.9 2 1.1 1 0 为{b},对象3和7的差别属性集为{a},对象2 1.4 1 3 1.3 3 0 和4的差别属性集为a,b{,对象2和7的差别 1.2 1 1.4 2 0 属性集为a,b,c},因此原始信息表的核属性集 7 1.8 3 1.3 3 0 为ia,b},属性c为冗余属性，可以去掉 3 11 2 0 由原始表1，经过本填补算法计算，得中间表 3 2和完备表3. 表1原始不完备表 最后根据这些属性的离散划分区间集对整个 Table 1 Initial uncompleted table 信息表进行整数映射，就可得到最终的离散结果. a b U a b c 为了进一步验证该算法，本文从UCI机器学 10.9 211 71.8321 习数据库中选取了著名的分类问题进行实验， 2 1.10.81 0 8 43 2 1 Iis数据库只包含有连续属性的数据，每个实体 3 1.33 2 0 9 3 2 1 包含有petal-length,petal-width,sepal length, 41.41 1 1 101.3 1 0 sepal-一width共4个连续型属性；该数据库中共有 51.42 0 150个实体，共分为Iris一setosa,Iris-versicolor, 61.21 Iris virginica共3个类别.经过本算法处理，得到 的划分区间为： 表2中间表 petallength:[1.0,3.0),[3.0,5.2),[5.2, Table 2 Middle table 6.9]petalwidth:[0.1,1.8),[1.8,2.5]sepal- U a b d U a b d length:[4.3,5.9),[5.9,7.1),[7.1,7.9];sepal-- 1 0.9 21 21.1 1 0 width:[2.0,3.4),[3.4,4.4] 1.4 1 1.3 3 0 离散后的划分区间代表了事物的属性值特征 1.2 1 1 1.4 2 且信息表并没有因此产生冲突事件. 7 1.8 3 10 1.3 0 4结论 3 1 2 1 0 3 本文根据差别向量加法运算解决了信息表属 性约简问题，根据条件属性与决策属性之间的依 根据属性重要性公式选取属性α，对其属性 赖关系，在不产生冲突事件的情况下，解决了不完 值进行排序得原始划分断点为： 备数据的填补问题，借助分治思想解决了连续属 P%=[0,0.9],P9=[0.9,1.1],P9=[1.1,1.2], 性离散化问题，并且时间复杂度由原来的O(A P=[1.2,1.3],P4=[1.3,1.4],Pg=[1.4,1.8], 1U2)降低为现在的0(A|(lY1I2+…十 P%=[1.8,2],P9=[2,4] |Y2)·数值示例和实验结果显示此方法是有 因为划分区间P8,P℉中决策属性不同，所以 效可行的
步骤11 根据 W ＝ W ∪ W i 对信息表进行 离散化并计算相对信息熵 E．如果 E＞ E 0则执 行步骤10；否则执行步骤13． 步骤12 直至计算的相对信息熵 E≤ E 0结 束计算． 步骤13 根据断点集 W 对信息表的属性值 进行相应的整数映射． 3 数据实例及实验 设有一个原始表 S＝〈UAV f〉如表1 其中 A ＝ C∪ D为条件属性和决策属性．根据 差别向量定义可以得到对象2和5的差别属性集 为｛b｝对象3和7的差别属性集为｛a｝对象2 和4的差别属性集为｛ab｝对象2和7的差别 属性集为｛abc｝因此原始信息表的核属性集 为｛ab｝属性 c 为冗余属性可以去掉． 由原始表1经过本填补算法计算得中间表 2和完备表3． 表1 原始不完备表 Table1 Initial uncompleted table U a b c d 1 0∙9 2 1 1 2 1∙1 0∙8 1 0 3 1∙3 3 2 0 4 1∙4 1 1 1 5 1∙4 2 1 1 6 1∙2 1 1 1 U a b c d 7 1∙8 3 2 1 8 4 3 2 1 9 ∗ 3 2 1 10 1∙3 ∗ 1 0 11 2 1 ∗ 0 表2 中间表 Table2 Middle table U a b d 1 0∙9 2 1 4 1∙4 1 1 6 1∙2 1 1 7 1∙8 3 1 8 4 3 1 9 ∗ 3 1 U a b d 2 1∙1 1 0 3 1∙3 3 0 5 1∙4 2 0 10 1∙3 ∗ 0 11 2 1 0 根据属性重要性公式选取属性 a对其属性 值进行排序得原始划分断点为： P a 0＝［00∙9］P a 1＝［0∙91∙1］P a 2＝［1∙11∙2］ P a 3＝［1∙21∙3］P a 4＝［1∙31∙4］P a 5＝［1∙41∙8］ P a 6＝［1∙82］P a 7＝［24］． 因为划分区间 P a 0P a 1 中决策属性不同所以 P a 0＋P a 1＝ ［00∙9］ ＋ ［0∙91∙1］ ＝｛［01）［1 1∙1）｝计算此时的相对信息熵 E＞ E 0接着进行 属性的划分区间的加法运算直至所有划分区间 操作完毕得属性 a 的离散划分区间集为［01） ［11∙5）［1∙151∙25）［1∙251∙35）［1∙35 1∙7）［1∙73）［34）．同理对属性 b 也进行上述 操作得离散划分区间集 ［01∙5）［1∙52∙5） ［2∙53）． 表3 完备表 Table3 Completed tab U a b d 1 0∙9 2 1 4 1∙4 1 1 6 1∙2 1 1 7 1∙8 3 1 8 4 3 1 9 4 3 1 U a b d 2 1∙1 1 0 3 1∙3 3 0 5 1∙4 2 0 10 1∙3 3 0 11 2 1 0 最后根据这些属性的离散划分区间集对整个 信息表进行整数映射就可得到最终的离散结果． 为了进一步验证该算法本文从 UCI 机器学 习数据库中选取了著名的分类问题进行实验． Iris 数据库只包含有连续属性的数据每个实体 包含有 petal－lengthpetal－widthsepal－length sepal－width 共4个连续型属性；该数据库中共有 150个实体共分为 Iris－setosaIris－versicolor Iris－virginica 共3个类别．经过本算法处理得到 的划分区间为： petal－length：［1∙03∙0）［3∙05∙2）［5∙2 6∙9］；petal－width：［0∙11∙8）［1∙82∙5］；sepal－ length：［4∙35∙9）［5∙97∙1）［7∙17∙9］；sepal－ width：［2∙03∙4）［3∙44∙4］． 离散后的划分区间代表了事物的属性值特征 且信息表并没有因此产生冲突事件． 4 结论 本文根据差别向量加法运算解决了信息表属 性约简问题．根据条件属性与决策属性之间的依 赖关系在不产生冲突事件的情况下解决了不完 备数据的填补问题．借助分治思想解决了连续属 性离散化问题并且时间复杂度由原来的 O（｜A｜ ｜U｜2）降低为现在的 O （｜A｜（｜Y1｜2＋…＋ ｜Y n｜2））．数值示例和实验结果显示此方法是有 效可行的． Vol．28No．9 鄂 旭等： 一种不完备信息表的预处理方法 ·905·
.906 北京科技大学学报 2006年第9期 参考文献 [5]Jelonek J.Krawiee K,Slowinski R.Rough set reduction of [1]Pawlak Z.Rough set.Int J Comput Inf Sci.1982(1)341 attributes and their domains for neural networks.Comput In- tel,1995,11(2):339 [2]Krysikiewicz M.Rough set approach to incomplete informa- tion system.Inf Sci.1998.112:39 [6]苗夺谦.Rough Set理论中连续属性的离散化方法.自动化 学报，2001,27(3)：296 [3]赵军，王国胤。基于粗集理论的数据离散化方法，小型微 型计算机系统，2004,25(1)：60 [7]Nguyen HS.Skowron A.Boolean reasoning for feature ex- [4]鄂旭，高学东，武森，等.信息表中不完备数据的填补方 traction problems/10th International Symposium on Foun 法.北京科技大学学报，2005,27(3)：364 dations of Intelligent Systems.New York.1997:116 A method for preprocessing an incomplete information table EXu),GAO Xuedong),SHAO Liangshan,YE Baiqing 1)Department of Computer Science.Liaoning Institute of Technology.Jinzhou 121001,China 2)Management School.University of Science and Technology Beijing.Beijing 100083.China 3)Management School,Liaoning Technical University.Fuxin 123000.China ABSTRACI This paper studied the problems of filling up incomplete data,reducing redundant attributes and discretizing continuous attributes in preprocessing the incomplete information table with continuous at- tributes in a rough set.According to the concept of interval value and the consistency of condition attributes and decision attributes,a plus rule for interval values was defined to filling up the incomplete data.Depend- ing on the conception of classification,the discernible vector was defined and the discernible vector addition rule was used to delete redundant attributes.By use of the super-club data and entropy of the information table,the discretization of continuous attributes was implemented.The illustration and experimental results indicate that the method is effective. KEY WORDS incomplete information table:rough set:information entropy;attributes reduction;dis- cretization
参 考 文 献 ［1］ Pawlak Z．Rough set．Int J Comput Inf Sci1982（1）：341 ［2］ Krysikiewicz M．Rough set approach to incomplete information system．Inf Sci1998112：39 ［3］ 赵军王国胤．基于粗集理论的数据离散化方法．小型微 型计算机系统200425（1）：60 ［4］ 鄂旭高学东武森等．信息表中不完备数据的填补方 法．北京科技大学学报200527（3）：364 ［5］ Jelonek JKrawiec KSlowinski R．Rough set reduction of attributes and their domains for neural networks．Comput Intell199511（2）：339 ［6］ 苗夺谦．Rough Set 理论中连续属性的离散化方法．自动化 学报200127（3）：296 ［7］ Nguyen H SSkowron A．Boolean reasoning for feature extraction problems ∥ 10th International Symposium on Foundations of Intelligent Systems．New York1997：116 A method for preprocessing an incomplete information table E Xu 12）GAO Xuedong 1）SHAO L iangshan 3）Y E Baiqing 3） 1） Department of Computer ScienceLiaoning Institute of TechnologyJinzhou121001China 2） Management SchoolUniversity of Science and Technology BeijingBeijing100083China 3） Management SchoolLiaoning Technical UniversityFuxin123000China ABSTRACT This paper studied the problems of filling up incomplete datareducing redundant attributes and discretizing continuous attributes in preprocessing the incomplete information table with continuous attributes in a rough set．According to the concept of interval value and the consistency of condition attributes and decision attributesa plus rule for interval values was defined to filling up the incomplete data．Depending on the conception of classificationthe discernible vector was defined and the discernible vector addition rule was used to delete redundant attributes．By use of the super-club data and entropy of the information tablethe discretization of continuous attributes was implemented．The illustration and experimental results indicate that the method is effective． KEY WORDS incomplete information table；rough set；information entropy；attributes reduction；discretization ·906· 北 京 科 技 大 学 学 报 2006年第9期