一种基于改进的相关矩阵的属性约简算法.doc


一种基于改进的相关矩阵的属性约简算法
王平,王秀坤**
(大连理工大学计算机学院,大连 116024)
5
10
15
20
25
摘要:属性约简问题是粗糙集理论的核心内容之一,已经被证明为 NP-hard 问题。目前已有
研究利用相关矩阵把属性约简问题和集合覆盖问题联系起来,将粗糙集的属性约简问题转化
为求集合覆盖问题。本文提出了一种基于改进的相关矩阵的属性约简算法,经处理后的相关
矩阵比传统相关矩阵更简单,在其基础上实现了最小属性约简算法,能够快速求出决策表的
最小属性约简。理论分析和实例表明,基于改进的相关矩阵的属性约简算法可减小属性约简
的搜索空间,提高约简的效率。
关键词:计算机软件与理论;粗糙集;属性约简;集合覆盖;相关矩阵
中图分类号:
An Algorithm of Reduction of Attributes Based on
Improved Relation Matrix
WANG Ping, WANG Xiukun
(School puter Science, Dalian University of Technology, Dalian 116024)
Abstract: Reduction of attributes which is one of the most important problems in rough set theory
has been proved to be a NP-hard problem. There are studies discuss the relationship between the
reduction of attributes and set covering by constructing the relation matrix. This paper proposes an
algorithm of reduction of attributes based on improved relation matrix which is simpler than the
conventional relation matrix, and then an algorithm for minimum reduction of attributes based on
improved relation matrix was introduced. At the same time give an example to demonstrate the
algorithm and prove the effectiveness of the method with theoretical analysis.
Key words: Computer Software and Theory;Rough Set; Attributes Reduction; Relation matrix; Set
covering
0 引言
30

粗糙集理论是一种处理模糊和不确定性知识的数学工具,由波兰学者Paw lak教授
[1]

在1
982年提出,其主要思想就是保持分类能力不变的前提下,通过知识