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