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

一种基于改进的相关矩阵的属性约简算法.doc一种基于改进的相关矩阵的属性约简算法
王平，王秀坤
（人连理工人学计算机学院，人连116024）
摘要：属性约简问题是粗糙集理论的核心内容之一，已经被证明为NP-hard问题。目前已有 研究利用相关矩阵把属性约简问题和集合覆盖问题联系起来，将粗糙集的属性约简问题转化 为求集合覆盖问题。本文提出了一种基于改进的相关矩阵的属性约简算法，经处理后的相关 矩阵比传统相关矩阵更简单，在其基础上实现了最小属性约简算法，能够快速求出决策表的 最小属性约简。理论分析和实例表明，基于改进的相关矩阵的属性约简算法可减小属性约简 的搜索空间，提高约简的效率。
关键词：计算机软件与理论；粗糙集；属性约简；集合覆盖；相关矩阵 中图分类号：
An Algorithm of Reduction of Attributes Based on
Improved Relation Matrix
WANG Ping, WANG Xiukun
（School of Computer 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引言
粗糙集理论是一种处理模糊和不确定性知识的数学工具，由波兰学者Pawlak教授 E在1
982年提出，其主要思想就是保持分类能力不变的前提下，通过知识约简，导出问题的决策 或分类规则。目前，粗糙集理论在机器学习，数据挖掘，智能数据分析，控制算法获取等领 域取