一种不完备决策表的差别矩阵求核算法  

Algorithm for computing core based on discernibility matrix in incomplete decision table

作　　者：廖洪建[1,2] 徐章艳[2] 

机构地区：[1]柳州师范高等专科学校数学与计算机科学系,广西柳州545004 [2]广西师范大学计算机科学与信息工程学院,广西桂林541004

出　　处：《计算机工程与应用》2011年第36期131-133,237,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(the National Natural Science Foundation of China under Grant No.60963008;No.61070101)

摘　　要：计算不完备决策表的核属性是粗糙集理论的重要内容之一。目前关于不完备决策表的求核算法的研究相对较少,而且在一般的求核算法中,其时间复杂度为O(|C||U|2)。为了有效地降低算法的时间复杂度,给出了一个不完备决策表的差别矩阵定义和基于差别矩阵的核定义,并证明了该定义与基于不完备决策表的核定义是等价的。在此基础上,利用差别矩阵方法来设计一种计算不完备决策表的求核算法,其时间复杂度降为O(|C||Upos||U|)。最后用仿真实例说明了新算法的有效性。Computing core of incomplete decision table is one of the most important researches in rough set theory.At present, the core algorithms of incomplete decision table are few.In many general algorithms of computing core,their time complexity is O（｜C｜3｜U｜2） .To cut down the time complexity of the algorithms for computing core,the definition of discernibility matrix and the corresponding definition of the core are proposed.At the same time,it proves that the core is equivalent to the core based on the incomplete decision table.On this condition,a quick algorithm for computing core is designed with the discernibility matrix, whose time complexity is O（｜C｜｜Upos｜｜U｜） .An emulate example is used to illustrate the efficiency of the new algorithm.

关 键 词：粗糙集 不完备决策表 正区域 差别矩阵 核 

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