一种基于属性互补性的粗糙集属性约简方法
王学恩，韩德强，韩崇昭
（电子与信息工程学院，西安交通大学，陕西，西安，710049）
摘要：属性约简是粗糙集理论中的一个关键问题，其中寻找最小约简是一个NP-hard问题。许多启发式约简算法多使用属性的分类能力来衡量属性的重要性。本文利用条件属性之间互补性来度量属性的重要性，增加约简属性间的互补性，提高约简属性的分类能力。经过在UCI数据集上的测试，实验结果表明本文给出的约简方法可行有效。
关键词： 粗糙集；属性约简；条件信息熵；决策表
中图分类号： TP18 文献标识码：
Rough Set Attribution Reduction based on Complementarity of Condition Attributes
Wang Xue-en, Han De-qiang, Han Chong-zhao
(School of Electronic and Information Engineering, Xi’an Jiaotong University, 710049, Xi’an, China)
ABSTRACT：The reduction of attributes is a critical problem in the rough set theory. Finding the minimal reduct is turned out to be a NP-hard problem. Many heuristic algorithms, which use the significance of the condition attribute with reference to the decision attributes as the indication for attribute selection, have been proposed in this area. In this paper the pair-wise complementarity of condition attributes is defined based on conditional information entropy and employed as a heuristic in the attribute reduction process. Finally, a heuristic algorithm of reduction is proposed and tested on the UCI machine learning repository. It can be verified by the experimental results that the proposed algorithm is feasible and effective.
KEYWORDS：rough set, attribute reduction, conditional information entropy, decision table.
1. 引言
对于信息系统中不完备信息、模糊信息，粗糙集是一个有效的数学工具。随着粗糙集理论的不断发展，它被广发的应用于人工智能、认知科学中[1]。
基金项目：国家自然科学基金创新研究群体科学基金（60921003），国家“973”重点基础研究发展规划项目(2007CB311006)
粗糙集理论建立在不可分辨关系基础之上。属性约简是粗糙集的重要内容，其工作是寻找一个能保持不可分辨关系的最小属性子集，即在保持信息系统分类能力的情况下删除系统内的冗余（属性）信息。然而，寻找这个最小约简是一个NP难问题[2]。目前已经有很多启发式方法，大多数启发算法都是以属性重要性作为一个指引来对属性进行选择。按照属性重要性的度量方法不同，目前已有的算法主要可以分为三类。第一类是基于不可分辨矩阵的方法，该方法中属性重要度以分辨矩阵中属性出现的频率来衡量[3]。第二类是基于Pawlak的属性重要度概念，该方法从代数的观点对属性重要度进行了定义[4]。第三种方法是基于信息熵的，该方法使用信息熵对属性重要度进行描述[5-7]。
在大多数系统中，属性重要度对应于属性的分类能力，当一个属性加入一个属性集合后，该集合的分类能力增加越多，该属性对于这个属性集合重要性越大，或者当一个属性从一个属性集合中删除的时候，分类能力下降越多说明该属性越重要。一般来说这个重要性是直接计算得到的，没有考虑相关属性之间的相互信息。本文试图从属性之间的相互补性来给出一个属性重要性的计算方法。
2. 基本概念
一个决策信息表可以描述为：
(1)
其中
是论域，
是条件属性集，
是决策属性集且
。
是属性的值域，其中
是属性
的值域。
是信息决策函数[1]。
不可分辨关系：对于任意属性子集
，
(2)
使用不可分辨关系可以对论域形成一个划分
（或者
）。其中划分的每个小区域均是一个等价类，记为
。
对于任意论域中的任意子集
，其相对于P的上近似与下近似可以分别记为：
(3)
上近似是指在基于
的划分区域中可以确定的被划分到
类中对象集合。下近似是指基于
的划分区域中有可能被划分到
类中对象集合。
对于一个属性集合
，其相对于决策集合
的正区域可记为：
(4)
该正区域表示的是基于
的划分区域中可以确定的被划分到某一个基于
的划分区域中的所有区域集合，反应的是集合
相对于
的分类能力。
对于条件属性的任一子集
，如果
(5)
是
的一个相对约简。属性核是所有约简的交集。根据文献[8]的方法，判断一个属性a 是否是核属性可以通过
是否与
相等判断，如果不等则属性a是核属性，对每个属性均作此判断，就可以获得属性的相对约简核。
本文档为【一种基于属性互补性的粗糙集属性约简方法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483