正在加载图片...
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