一种启发式知识约简算法  

A Heuristic Algorithm of Knowledge Reduction

作　　者：刘启和[1] 闵帆[1] 蔡洪斌[1] 杨国纬[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都610054

出　　处：《计算机科学》2005年第10期135-138,共4页Computer Science

摘　　要：属性约简是Rough集理论中的核心问题之一,找出所有的约简或最小约简是一个NP难题。本文证明了正区域和边界域的一些性质,指出在考虑工区域作为启发信息的同时,还应该考虑在不一致决策表中边界域对约简的影响,综合这两种信息,提出了不一致决策表约简的启发信息。并在此基础上,设计了不一致决策表的启发式约简算法。实验证明,在多数情况下,该算法能够得到决策表的最小或次优约简。In rough sets theory, reduction of attributes is an important issue. It has been proved that computing all reductions or the minimal reduction of decision table is a NP-hard problem. Now, many algorithms for reduction of attributes are still heuristic algorithms. In this paper, new heuristic information is proposed. We consider boundary region （complement of positive region） can affect reducing attributes in inconsistent decision table, so we use not only positive region but also boundary region to calculate this heuristic informatiorL Based on this new heuristic information. We develop heuristic algorithm for reduction of attributes in inconsistent decision table. In order to test efficiency of the algorithm, an example is analyzed and some experiments are made. The analysis and experimental results show that the algorithm is efficient and capable of finding the minimal or suboptimal reduction in most of cases.

关 键 词：Rough集 属性约简 边界域 正区域 知识约简算法 启发式 决策表约简 Rough集理论 启发信息 最小约简 实验证明 属性约简 NP难题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP393.092[自动化与计算机技术—计算机科学与技术]