信息表中不完备数据的填补方法

D0I:10.13374/i.issm1001053x.2005.03.027 第27卷第3期 北京科技大学学报 Vol.27 No.3 2005年6月 Journal of University of Science and Technology Beijing Jun.2005 信息表中不完备数据的填补方法 鄂旭12高学东”武森” 张秋月) 1)北京科技大学管理学院，北京1000832)辽宁工学院计算机系，锦州1210013)北京科技大学管庄校区，北京100083 摘要提出了~种基于粗糙集的不完备数据填补方法，本算法以突出信息表的决策规则 为主要目的，选取重要断点为主要手段，以分类质量作为迭代约束条件，实验和数值实例表 明，本算法不但不会产生冲突规则，而且能够进一步突出决策规则， 关键词租糙集：相关性；等价类；断点 分类号TP18 粗糙集理论"在20世纪90年代初首先被引 性值，即Va∈A,x,∈U,fx,a)∈V. 入到机器学习、人工智能等研究领域，近几年来 定义3不可分辨：Va∈A对于(A中包含一个 已经成为数据挖掘回研究中的一种有效分析方 或多个属性)，e,e∈U,若f八e,a)=fe,a)成立，则 法，被应用在分类分析、聚类分析等算法中. 称对象e,e关于属性A不可分辨. 在粗糙集中，数据是以信息表的形式来表示 定义4等价关系：P是U上的一个等价关系 的.在进行数据挖掘分析时，常常发现信息表中 簇，如？=P且2+0，则∩2(Q的所有等价关系的 存在不完备数据的现象，这就需要把这些数据填交)记作ND(Q),它也是一个等价关系 补回来，再进行深层次的分析.目前，填补不完备 定义5划分：在U中关于属性集A的所有等 数据的方法有均值法、最大频率法等，但利用这 价集称为U中属性集A的划分R,即R={EE,为关 些方法填补的数据大都不能与信息表隐藏的信 于A的等价集，i=1,2,…,n}. 息很好地结合，因此填补数据的质量较差，本文 定义6上、下近似集：假设U中关于A的划分 提出能够较好地提高填补数据的质量的方法， 是E,U中关于A的划分是Y.等价集Y(Y是A'的 1粗糙集相关定义 划分Y中的一个等价集)为关于属性A的下近似集 合为AY=U{E,E,∈E且E,≤Y}.4y是E中被Y包 算法主要涉及到属性相关性以及不可分辨 含的等价集的并集，即Vx∈AY,x,一定属于y.等 关系等一些粗糙集知识，其相关定义如下. 价集Y(Y是A'的划分Y中的一个等价集)的关于 定义1属性相关系数：设属性c,与C2相关系 属性A的上近似集合为： 数记为Pe且 AY=U{ElE,∈E且E,nY,+O} Covci,C2) Var(e,)Var(c) AY,是E中与Y交集非空的等价集的并集，即 其中，Cov(c,c)表示c与c2的协方差，Var(c,), x∈卫，，x可能属于Y,, Varc)分别表示与c的cz方差 定义7设集合簇F={X,X,,Xn}(U=UX) 定义2信息系统S的定义为=(U,A,V,月.其 是论域U上的知识，B是一个属性子集，定义B对 中U是一个非空有限对象集合，U={x,,,x}, F的近似分类的质量： 式中的x,为对象：A是对象的属性集合，分为两个 ΣIB.(X 不相交的子集，即条件属性集C和决策属性集D, rF)- A=CUD;V是属性值的集合，V=U(V,a∈A,。 其中，B(X引为X关于属性B的下近似集的势，U 是属性a的值域；f是一个函数，即UxA→V是一个 为U的势. 映射函数，它为每个对象的每个属性赋予一个属 定义8若F是由决策属性集D导出的分类， 收稿日期：200406-25修回日期：20041103 属性子集B'在属性集B中的重要性定义为r(F)- 基金项目：内蒙古白治区高等学校科学研究项目No.NJ02112) r(F).若r(F)=rs(F),则B'为冗余属性：否则，若 作者简介：鄂旭(1971一，男，讲师，博上研究生 r(F)丰r(F,则B为重要属性

第 2 7卷 第 3 期 2 0 0 5年 6 月 北 京 科 技 大 学 学 报 J o u r n a l o f U n iv e sr i yt o f S c le n e e a n d eT e b n o l o gy B e ij i o g V b l . 2 7 N o . 3 J U n . 2 0 0 5 信息表中不 完备数据 的填补方法 鄂 旭 l,2) l )北 京科技 大学管理 学院 , 北京 10 0 08 3 高学 东” 武 森 ” 张秋 月 ” 2) 辽 宁工 学 院计算机 系 , 锦州 12 10 01 3) 北 京科技 大学管 庄 校 区 , 北京 10 00 83 摘 要 提 出 了 1 种 基于 粗糙集 的不完 备数 据填补 方法 . 本 算法 以突 出信 息表 的决策 规则 为 主要 目的 , 选 取重 要断点 为主 要 手段 , 以分类 质量作 为迭代 约束 条件 . 实验和 数值 实例表 明 , 本算法 不但 不会产 生 冲突 规则 , 而且 能够进 一 步突 出决策规 则 . 关 键词 粗糙集 ; 相 关性 ; 等价类 ; 断 点 分 类号 T P 18 粗 糙集 理 论 川 在 20 世纪 90 年代 初 首先被 引 入 到机 器学 习 、 人 工 智能等 研 究领域 , 近 几 年来 己 经 成 为数 据挖 掘 1[ 研 究 中的一 种 有 效分 析方 法 , 被 应用 在 分类 分析`习、 聚类 分析`4] 等算 法 中 . 在粗糙 集 中 , 数据 是 以信 息表 的形 式来表 示 的 . 在 进行 数据 挖 掘分 析 时 , 常常发 现信 息表 中 存在 不 完备数据 的现 象 , 这就 需要把 这些数 据填 补 回来 , 再进行 深层 次的 分析 . 目前 , 填补 不完备 数据 的方法 有均 值法 、 最大 频率法 5I] 等 , 但 利用这 些 方 法填 补 的数 据 大 都不 能 与信 息 表 隐藏 的信 息 很好 地 结合 , 因此填 补数 据 的质 量较 差 . 本文 提 出 能够较 好地 提 高填 补数 据 的质量 的方 法 . 1 粗 糙集相 关 定 义 算 法 主要 涉 及 到 属性 相 关性 以及 不 可 分辨 关系 等一 些 粗糙 集 知识 , 其 相 关定 义如 下 , 一盯 . 定义 1 属性 相 关系数 : 设 属性 c , 与 c Z相关 系 数记 为cP ’l 且 C o v ( c , , c Z ) 其 中 , C o v ( e l , e Z ) 表 示 e , 与 e Z 的 协 方 差 , V斌 e , ) , V ar (伪) 分别表 示 与 c , 的 c Z 方 差 . 定 义 2 信息 系统 S 的定义 为 S 二 (以月 , 飞户 . 其 中 u 是 一个 非 空 有 限对象 集 合 , U = x{ 1 , 瓜 , … , 从 } , 式 中的x 为对 象 ; A 是对 象 的属性 集 合 , 分 为两 个 不相 交 的子集 , 即条件 属性 集 C 和 决策属 性集 D, A 二 C u D ; V是属性 值 的集 合 , V 二 目 ( Va ) , a 任 A , Va 是属性 a 的值 域 ; . 提 一 个 函数 , 即 沙A 一 V 是 一 个 映射 函 数 , 它为每 个 对象 的每个属 性赋 予一 个 属 收稿 日期 : 2 0 04 es 习` 2 5 修 回 日期 : 2 0 0今1 1一3 基金项 目 : 内蒙古 自治 区 高等学校 科学研 究项 目 (N 。 NJ 02 112 ) 作者简 介 : 鄂旭 ( 19 71 一) , 男 , 讲师 , 博 上 研究 生 性值 , 即 V a 任 A , 姜 任 U, j’( x 毖, a) 任 Va . 定 义 3 不可 分辨 : V a 任 A 对 于 (A 中包 含 一个 或 多个属 性 ) , 已 , ej 任 U , 若f( e, a) 二 f( ’e, a) 成 立 , 则 称对 象 已 , ej 关 于属 性A 不可 分辨 . 定 义 4 等价 关 系 : 尸 是 U上 的一 个等 价 关系 簇 , 如 Q 二 尸 且 Q 羊 0 , 则 n Q (Q 的所有 等价 关 系的 交 ) 记 作 NI D (Q) , 它也 是 一 个等 价 关系 . 定义 5 划 分 : 在 U 中关 于属 性集 A 的所有 等 价 集称 为 U 中属 性 集A 的划 分R , 即 R 二 {式阵为关 于 A 的等价 集 , i = l , 2 , … , n} . 定义 6 上 、 下近似 集 : 假设 U 中关于 A 的划分 是 E , U 中关于 A ’ 的划分 是 .Y 等价集 茸 ( X 是A `的 划 分 Y中的一个等 价集 ) 为关于 属性A 的下 近似集 合 为丝耳二 u {瓦阵任 E 且 云二 茸} . 通琴 是 E 中 被 X 包 含的等价 集 的并集 , 即 V 兀 任丝X , x 一 定属 于艺 . 等 价 集 X (耳是 A ’的 划分 Y中的一 个等 价 集 ) 的关于 属 性A 的上近似 集 合 为 : 万万= u {川云 任 E 且 云n X 羊 0 } . A 万是 E 中 与 艺 交 集 非 空 的等 价 集 的 并 集 , 即 V 戈 任又 , 为可 能属 于艺 、 定 义 7 设 集合 簇 F 二 {戈 ,龙 , … , 龙 } ( U = u 义 ) 是论域 U 上 的知 识 , B 是一个 属性 子 集 , 定义 B 对 F 的近似 分类 的质 量 : 艺}召 一 忱 ){ 。 旧 一” ’ }训 其 中 , ! B 一 忱 )}为尤 关 于属性 B 的下近似 集 的势 , !训 为 U 的势 . 定 义 8 若 F 是 由决策 属 性集 D 导 出的分 类 , 属性 子集 B 尸 在 属性 集B 中的 重要 性 定义 为` (月一 场城月 . 若` 囚 = 鲡《月 , 则B 尸为冗 余属性 ; 否 则 , 若 er 旧 羊 俪 <月 , 则B ` 为重 要属 性 . DOI: 10. 13374 /j . issn1001 -053x. 2005. 03. 027

Vol.27 No.3 邪旭等：信息表中遗失数据的填补方法 ·365 2 PMMDVCP算法描述 件属性间的相关系数，构造相关系数矩阵， 步骤2根据相关系数矩阵对条件属性进行 2.1 PMMDVCP算法相关定义、定理 聚类，然后从每类属性中选出代表属性形成新的 PMMDVCP(Packing Method for Missing Data 条件属性集. Value Based on Attribute Correlation and Breaking 步骤3在MOS中按照定义6和定义7计 Poin)算法主要是基于信息表中属性相关性及断 算各属性值的重要性，并按照属性的重要性从左 点提出的，因此填补的数据能较好地体现信息表 到右降序排列，MOS排在信息表的最后，建立新 中的隐含知识 的信息表S=(U,A,”,f?. 定义9信息系统S(UA,'f,A={al=l,…,m} 步骤4设UMOS中每个属性A'的断点集P', 是属性集，设X∈U,则对象X的遗失属性集MAS, 断点为P0=1,2,",n-1)，与之相邻的两个值 对象X的无差别对象集NS,和信息系统S的遗失 ,,并且x<P<,对于每一个属性A'进行如 对象集MOS分别定义为： 下操作：(1)令a=,=,若信息表无冲突，则 MAS,={a4a(x)=*,k=1,",m} P=P叭{P》}:否则=a,=.(2)直至全部属性 MOS={MAS,≠O,i=1,,n} 操作完毕 NS,=(lM(i,)=,i#j,j=1,,n} 步骤5在信息表中按照决策属性对全部对 定理决策表S=(U,R,',F),其中U=UUU, 象分类，并按各分类的势由大到小排序，并取第 °是所有属性值都已知的样例集合，U是部分属 一个决策类进行步骤6的操作. 性值未知的样例集合，R=CUCUD,C是重要条 步骤6在同一决策类中，设条件属性 件属性集，C是冗余条件属性集，D为决策属性 B'SBSA,对x,∈MOS进行如下操作：(I)若auEB', 集.如果对a∈U,廿b∈U°，Hc∈C;,令c(a)=c(b), 且r(F=ra(F,则由椎论知a(x)可以取任一断点 则信息表的确定性不变 值.(2)否则进行如下操作.①对Hx,EMOS,在属性 证明：设分类E,∈UND(C②，i=1,2,,m,而m 集B\{B中计算NS(x):②若NS(x)=y,则令a(x)= 是由条件属性集C决定的分类数，K,X,,X} ay:③若NSx)=y,,,y},则令y=yy,的等 是U上由决策属性决定的概念簇，则对任意分类 价类的势最大)，并且a(x)=ay).(3)直至全部 EEUIND(C),其对于决策属性分类的确定性程 x,∈MOS操作完毕， 度为w(B=max∈UND(D.由此可 步骤7在决策表中取第二个分类，进行步骤 以得出决策表S的确定性程度为： 6的操作， A=月 同“au(E). 步骤8直至所有决策类进行步骤4操作，最 (1)若C'中有且仅有一个元素c,则有条件属 后得到新表输出新的信息表， 性集C=CU{c}决定的分类为E,'∈UND(CU{c), 3数值实例 i=1,2,,m'因为c为冗余属性，所以UND(C UND(CU{c),也就是增加冗余属性值并不影 设有一个原始表S以U,A,')如表1，其中 响决策表中分类情况，即E=E.所以对任意分类 A=AUD为条件属性和决策属性.在MOS中 E∈UND(C),有E∈UjND(CU{c}),4mm(E=um(E), UND(a,b,c,)={{1},{2},…,{8}}, 决策表的4(S无变化. UND(a)=({1},{2,{3},{4,5,{7,{8}), (2)同理可证，若冗余属性C{C,C,,C}, UNDb)={1,5),{2),3,7,8,{4,6}, 决策表的um(S)仍然不发生变化. UU1NDc)={{1,2,4,5,6},{3,7,8}}. 推论若一个决策表存在冗余属性且冗余属 由分类质量公式得： 性存在遗失值，则遗失值填补为该属性的任意一 0)-巡9P》-g-1. card(U) 个断点，决策表的确定性不变， 同理， ro(D)=card(POS(D)3 2.2算法描述 card(U) -8 算法具体步骤描述如下，设原始信息系统为 (D)=card(POSD)5 card(U) S=U,A,,% D=POD》-g. 步骤】在MOS中按照定义1计算各个条 card(U)

、勺 1 . 2 7 N o . 3 鄂 旭等 : 信息 表 中遗 失数 据 的填 补方 法 一 3 6 5 - 2 P M M D V C P 算 法描述 2 . 1 PM M Dv C P 算法 相 关定 义 、 定理 PM M D V C P ( P a ick n g M het o d ofr Mi s s ign D at Va lue B as e d o n A itr b u t e C o er l a ti o n an d B er ak ign P o int )算 法主 要是 基 于信 息表 中属 性相 关 性及 断 点提 出的 , 因此 填补 的数据 能较 好地 体现信 息 表 中的 隐含 知识 . 定义 , 信 息系 统赓 ( U洲 , K乃 , A = {alt 户l , 一 , m } 是属 性集 , 设不 任 U , 则对象戈 的遗 失属性集 M A st, 对 象不 的无 差 别对 象集 N S `和 信 息 系 统 S的遗 失 对象 集 M O S分别 定义 为 : M A S ` = { a * } ak X( , ) 二 ’ , k 二 l , … , m } M O S = { i !M A S 。李 O , i 二 l , … , n } N s , = 仃!斌i , j) = O , i对’,j = l , … , n } 定 理 决 策表 S = (U, R , V, 玛 , 其 中 U 二 护 u U 飞 护是所 有 属性 值都 己知 的样 例集 合 , 酬是 部分 属 性 值未 知 的样 例集 合 . R = oC u c 勺D , 0C 是 重要 条 件 属性 集 , C 是冗 余条 件 属性 集 , D 为 决策 属 性 集 . 如 果对 V a 任 U几V b 任 护 , V c 任 C 几令 c a( ) “ c( b) , 则信 息 表 的确 定性 不变 . 证 明 : 设 分类瓦任 训NI (D 0 , i 二 1 , 2 , 一 , m , 而 m 是 由条 件属 性集 C 决定 的分 类数 , 忧 ,龙 , … , 龙 } 是 U上 由决策 属性 决定 的 概念 簇 , 则对 任 意 分类 E 任酬NI D ( )C , 其 对 于 决 策 属 性 分类 的 确 定 性 程 度 为 U一()E 一ax{ 罕 : 、 。 。 NID ()D } · 由此 可 以得 出决 策表 S 的确 定 性程度 为 : 。一 (必一 鸯县 · 产一 (E, ) · ( l) 若 ’C 中有 且仅 有 一个 元素 。 , 则 有 条件属 性 集小C o u { e } 决 定的 分类 为云性 切NI D (C o u { e }) , i 二 1 , 2 , … , 。 ` . 因 为 c 为 冗余 属 性 , 所 以切NI D ( 0C 卜 酬州D (oC u ( c} ) , 也 就 是增 加 冗 余属 性 值 并不 影 响 决策 表 中分类情 况 , 即E 二 ’E . 所 以对任 意 分类 E 任 训NI D ( e 。 ) , 有 E 任 训p叮D (C O u { c }) , u ~ ()E = u m。 (E ,) , 决策 表 的u ~ (匀无变 化 , (2 ) 同理 可证 , 若冗 余属 性 C 任 {侧 , 侧 , … , C 幼 , 决 策 表 的u ~ ()S 仍 然 不发 生 变 化 . 推论 若 一个 决策 表存 在 冗余 属 性且 冗余 属 性 存在 遗 失值 , 则遗 失值 填补 为该属 性 的任意 一 个 断 点 , 决策 表 的确 定性 不变 . .2 2 算法 描述 算 法 具体 步骤 描述 如 下 . 设原 始信 息系 统 为 0S =( 0U , 0A , 尸 ,尸) . 步 骤 1 在 动M O S 中按 照 定义 1 计算 各 个条 件 属 性间 的相 关 系数 , 构造 相关 系 数矩 阵 . 步 骤 2 根 据相 关系 数 矩 阵对 条件 属性 进行 聚类 , 然后 从每类 属 性 中选 出代 表属 性形成 新 的 条件 属 性集 . 步骤 3 在 助M O S 中按照 定 义 6 和定 义 7 计 算各 属性 值 的重要 性 , 并按照 属 性的重 要性 从左 到右 降序排 列 , M O S 排 在信 息表 的最后 , 建立 新 的信息 表了= <’U, A,’V, f 今 . 步 骤 4 设 以 M O S中每 个属 性 A `的断 点集’P , 断 点 为拜沪 1 , 2 , · 、 n 一 l) , 与 之 相 邻 的 两 个 值 对 , 林 . , 并且写K 拜K芬 , , 对 于 每 一个 属 性A ’进 行 如 下 操作 : ( l) 令 a “ 对冈 二林 , , 若 信 息表 无冲 突 , 则 尸” 扒 (君} ; 否 则另= a ,林 , 二林 、 . (2 ) 直 至 全 部属性 操作 完 毕 . 步骤 5 在信 息 表 中按 照决 策属 性对 全 部对 象分 类 , 并按 各 分类 的势 由大 到 小排 序 , 并取 第 一个 决策 类 进行 步 骤 6 的操 作 . 步 骤 6 在 同 一 决 策 类 中 , 设 条 件 属 性 B 竺 B ` A ,对 V 戈 任 M O S 进 行如 下操 作 : ( 1) 若仇任 B ` , 且rB旧 = 场<月 , 则 由推 论知负x(, ) 可 以取 任一 断点 值 . (2 )否则 进行 如下操 作 . ① 对 V戈任 M O S , 在属 性 集 \B {B ` } 中计 算 N S (xt ) ; ②若 N S (x, ) 二 y , 则 令ak x(, ) 二 ak切 ; ③若 N S x(,) = 伽 ; ,必 , … ,凡} , 则 令y 二 y ` 伽 ,的等 价类 的势 最大 ) , 并 且山 (幼 = 山妙) , ( 3) 直 至 全部 龙任 M O S 操 作 完 毕 . 步骤 7 在决策 表 中取第 二 个 分类 , 进行 步骤 6 的操 作 . 步 骤 8 直 至所 有决 策类 进行 步骤 4 操 作 , 最 后得 到新 表 输 出新 的信 息表 . 3 数值 实 例 设 有 一 个 原 始 表 二垦丈以月尤力 如表 1 , 其 中 A喇 u D 为条件 属 性和 决 策属 性 . 在 小M O S 中 酬IN D 伍 , b , e , ) “ { { l } , { 2 } , … , { 8 } } , 酬NI D ( a ) “ {{ 1 } , { 2 } , { 3 } , { 4 , 5 } , { 7 } , { 8 } } , 训NI D (b ) = {{ l , 5 } , { 2 } , { 3 , 7 , 8 } , { 4 , 6 } } , 酬NI D ( e ) = { { l , 2 , 4 , 5 , 6 } , {3 , 7 , 8 }} . 由分 类 质量 公 式得 : 同理 , r)KD 一 嘿黯碧 ) 一 普 一 ` · 、 a{} ()D 一 丝弩黯鱼卫一 令 or ` , , (D ) _ e adr ( p O S 。 、, , (D )) _ 5 e a r d (功 、 c(} ()D 一 嘿黯迎 一 令

366· 北京科技大学学报 2005年第3期 所以，属性a的重要性为r(D)-rc(DFl-0.375= 试验.s数据库只包含有连续属性的数据，每个 0.625,属性b的重要性为r(D)-rc(D=1-0.625= 实体包含有petal--length,petal--width,sepal--length,se 0.375属性c的重要性为r(D)-rce(D)=1-1=0,c pal-width共4个连续型属性：该数据库中共有150 为冗余属性， 个实体，分为Iris-setosa,Iris-versicolor,Iris-virginica 由表1原始表经过本算法，得到中间表和最 共3个类别.实验中随意选取遗失数据的个数为 终表.为了进一步验证该算法，本文从UC1机器10,15,30,40时，经本算法填补后的数据归属其原 学习数据库中选取了著名的is分类数据库进行 类别的正确填补个数分别为8,12,23,32 表1原始表，中间表及最终表 Table 1 Initial table,middle table and final table 原始表 中间表 最终表 U a b d C a d b 0.9 2 0.9 3 1 0.9 3 2 11 0.8 0 1.4 1.4 1 1.3 3 2 0 6 1.2 6 1.2 1 1 1.4 1.8 3 3 1 7 1.8 3 3 1.4 2 1 4 3 1 8 4 3 6 1.2 1 9 3 2 9 4 3 2 1.8 3 1.1 1 0 2 1.1 0 4 3 1.3 3 0 1.3 3 3 0 9 3 1.4 3 0 1.4 3 0 10 1.3 10 L.3 0 10 1.3 0 11 2 0 11 2 0 11 2 0 4结论 北京科技大学学报，2004,262：206 [4]武森，高学东.一种高位稀疏数据聚类的类特征表示法.北 一般的求均值法填补数据时容易引起信息 京科技大学学报，2003,25(2)：131 表内容的冲突，本算法是基于求信息表断点基础 [5]Krysikiewicz M.Rough set approach to incomplete information system.Inf Sei,1998,112:399 上进行不完备数据填补的，即避免了信息表的冲 [6]Kohavi R,Frasca B.Useful feature subsets and rough set reducts. 突，又能很好地反映信息表所蕴含的决策规则. In:3th International Workshop on Rough Sets and Soft Comput- ing.New York,1994 参考文献 [刀王国胤.Rough集理论与知识获取西安：西安交通大学出 [I]Pawlak Z.Rough set.Int J Comput Inf Sei,1982 (1):341 版社，2003 2]武森，高学东，Bastian M.数据仓库与数据挖掘.北京：治 8]张文修，吴伟志，梁吉业.等.粗糙集理论」方法北京：科 金工业出版社，2003 学出版社，2001 [3引尹阿东，宫雨，吴胜利，等，增量决策树算法及复杂度分析 A New method of packing the missing data E Xu2,GAO Xuedong",WU Sen.ZHANG Qiuyue 1)Management School,University of Science and Technology Beijing,Beijing 100083,China 2)Department of Computer Science,Liaoning Institute of Technology.Jinzhou 121001.China 3)Guanzhuang Campus,University of Science and Technology Beijing.Beijing 100024,China ABSTRACT A new algorithm for filling up in complete data was presented according to rough sets.In this meth- od,the main purpose was emphasizing the decision rules,the main means was selecting the important breaking poin- ts,and the iterative constraint was the quality of classification.Numerical illustration and database experiments show that the algorithm did not generate conflict rules,but highlighted them. KEY WORDS rough sets;correlation;equivalent class;breaking point

一 3 6 6 - 北 京 科 技 大 学 学 报 2 0 0 5 年 第 3 期 所 以 , 属性 a 的重要 性 为r c (D ) 一 。 。 { 。 、 (D ) = 一 0 . 37 5 二 住 62 5 , 属性 b 的重要 性 为r 仄D ) 一 肠枷(D )月 一 0 . 62 5 = .0 3 75 属 性 c 的重 要 性 为cr (D ) 一份 c{} (D )封 一 1 二 O , c 为冗 余属 性 . 由表 1 原 始表 经过 本算 法 , 得 到 中间表 和 最 终表 . 为 了进一 步验 证 该算法 , 本文 从 U CI 机器 学 习 数据 库 中选 取 了著名 的 Iir s 分类 数据 库进 行 试 验 . ilr s 数 据库 只 包 含有 连续 属性 的数 据 , 每 个 实体包 含有 p et a l 一 len gt h , p et a l 一 iw dht , s e p a l 一 l e 雌ht , s e - p al 一 w i dt h 共 4 个连 续型 属性 ; 该数 据库 中共有 150 个 实体 , 分 为 Iir s 一 s e ot s a , Iir s 一 v e r s i e o l o r , nI s 一v i飞i n i e a 共 3 个类 别 . 实验 中随意选 取遗 失 数据 的个 数 为 10 , 15 , 3 0 , 4 0 时 , 经 本算 法填补 后 的数 据 归属其 原 类 别 的 正 确填 补个 数分 别 为 8 , 1 2 , 23 , 犯 . 表 1 原始 表 。 中间表 及 最终表 aT b l e 1 I n iU a l t a b l e , m id d l e t a b l e a . d if n a l 加 b l e 原始 表 中间表 最终表 U a b e d U a b e d 142比州413曰13 0名 1 . 4 1 . 8 , 尹nQ l 4 名3421 * 3 l 0 l 0 l 0 1 1 2 1 * 0 11 2 1 * 0 1 1 2 1 1 0 4 结 论 一 般 的求 均值 法填 补 数 据 时容 易 引 起信 息 表 内容 的冲突 , 本 算法 是基 于求信 息表 断点基础 上进 行不 完备 数据填 补 的 , 即 避 免 了信 息表 的冲 突 , 又 能很 好地 反 映信 息 表所 蕴含 的决 策规 则 . 参 考 文 献 【l ] P aw lak Z , R o u gh s e t . I n t J C o m P u t I n f s e i , 19 8 2 ( l ) : 3 4 1 肆] 武森 , 高学东 , B ast ian M . 数据仓 库与 数据 挖掘 . 北京 : 冶 金 工 业 出版 社 , 2 0 0 3 【31 尹 阿 东 , 宫雨 , 吴胜 利 , 等 , 增量 决 策树算 法及复 杂度 分析 . 北 京科技 大学学报 , 2 0 0 4 , 2 6 (2 ) 2 0 6 砰l 武 森 , 高学 东一 种高 位稀疏数据 聚类 的类 特征表 示法 . 北 京科技大 学学报 , 2 00 3 , 2 5 (2 ) : 一3 1 15 】 K 巧 s ik i e w i e z M . R o u g h s e t a P p or ac h t o in e o m p l e t e i n of rm at i o n s y s t e m . I n f s e i , 19 9 8 , 1 12 : 3 9 9 16 】 K o h a 、 l i R , F r as e a B . U s e fu l fe at ure s u b s e t s an d r o u hg s e t r e d u e ts . I n 二3 t h I n t e m at i o n a l 节(/ 〕 rks h o P o n R o u hg S e t s a n d S o ft C o m P u -t in g . N 洲 OY r k , 1 99 4 〔7] 王 国J敞 . R o u hg 集理 论与 知识获取 西 安 西 安 交通大 学出 版社 , 20 0 3 〔8] 张文 修 , 吴伟 志 , 梁 吉业 , 等 . 粗糙 集理 论 ` J 方法 . 北京 科 学 出版 社 , 2 0 0 1 A N e w m e t h o d o f P a e k i n g ht e m i s s i n g d a t a E xu , , , , GA o Xu e do 馆 , ’ , 环 尸 U S e 刀 l , , 乙队J N G Qi妙 u e , , l ) M an ag e m e n t S e h o o l , nU i v e r s ity o f s e i e n c e an d eT e hn o l o gy B e ij in ` B e ij in g l0 0 0 8 3 , C hi n a 2 ) D e P a rt l n e nt o f C o m P u t e r s e i e ne e , 1 1的n i鸣 I n st i t u t e o f eT e hn o l o gy, Ji n hz o u 12 10 0 l , C h i n a 3 ) G u an hz u an g C a m P u s , U n 里v e r s ity o f s e i e n e e an d eT e hn o l o g y B e ij i n g , B e ij i n g l 0 0 0 24 , C h i n a A B S T R A C T A n e w a lgo ir t hm of r if l li n g uP i n e o m P l et d at a w a s rP e s e nt e d a o e or d in g t o r o u g h s e t s . I n ht i s m e th - o d , ht e m a i n P u pr o s e w a s e m P h a s i z i n g th e d e e i s i o n ur l e s , t h e m a i n m e ans w a s s e l e c t in g het im P o rt ant b r e iak n g P o i n - t s , an d ht e it e r at i v e e o n s t r a iin w a s ht e q u a liyt o f e l a s s iif e at i o n . N u l刀 e ir e a l ill u s tr at i o n an d d a t a b as e e x P e ir m e nt s s ho w ht at het a l g ior t h m id d n o t g en er at e c o n fl i e t ur l e s , b ut h igh ligh t e d ht e m . K E Y W O R D S r o u gh s et s : e o er l iat on : e qiu v a l ent e l as s ; br e ak i n g P o i n t