基于样例选取的属性约简算法  

An Attribute Reduction Algorithm Based on Instance Selection

作　　者：王熙照[1] 王婷婷[1] 翟俊海[1] 

机构地区：[1]河北省机器学习与计算智能重点实验室河北大学数学与计算机学院,河北保定071002

出　　处：《计算机研究与发展》2012年第11期2305-2310,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61170040);河北省自然科学基金及高校科技重点项目(F2010000323;ZD2010139)

摘　　要：计算属性约简是粗糙集框架下归纳学习的关键部分.基于差别矩阵的属性约简算法是常用的属性约简算法之一.给定一个信息系统,利用该算法可以求出信息系统的所有属性约简.但是该算法需要的存储空间大,执行时间长,特别是对于大型数据库,差别矩阵的存储成为其应用的瓶颈.针对这一问题,提出了一种基于样例选取的属性约简算法,算法分为3步:首先从样例集中挑选出重要的样例;然后用选出的样例构造差别矩阵;最后计算信息系统的所有约简.实验结果显示,当处理大型数据库时,新算法能有效地减少存储空间和执行时间.Computing reduction of attributes plays an essential role in the framework of supervised learning based on rough sets. Attribute reduction algorithm based on discernibility matrix is one of the commonly used attribute reduction algorithms. Given an information system, all reductions can be found by using this algorithm. However, this algorithm suffers from the main problems： large memory requirement and large response time needed. Especially, for a large database, it is the bottleneck to store the discernibility matrix. To tackle this problem effectively, an attribute reduction algorithm based on instance selection is proposed. The algorithm consists of three stages： firstly, the most informative instances are selected from the training set; secondly, the discernibility matrix is computed by using the selected instances; finally, all reductions can be found. The experimental results show that the proposed method can efficiently reduce the computational complexity both of time and space especially on large databases.

关 键 词：信息系统 样例选取 粗糙集 差别矩阵 属性约简 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]