计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (36): 131-133.

• 数据库、信号与信息处理 • 上一篇    下一篇

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

廖洪建1,2,徐章艳2   

  1. 1.柳州师范高等专科学校 数学与计算机科学系,广西 柳州 545004
    2.广西师范大学 计算机科学与信息工程学院,广西 桂林 541004
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-12-21 发布日期:2011-12-21

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

LIAO Hongjian1,2,XU Zhangyan2   

  1. 1.Department of Mathematics and Computer Science,Liuzhou Teachers College,Liuzhou,Guangxi 545004,China
    2.School of Computer Science and Information Engineering,Guangxi Normal University,Guilin,Guangxi 541004,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-12-21 Published:2011-12-21

摘要: 计算不完备决策表的核属性是粗糙集理论的重要内容之一。目前关于不完备决策表的求核算法的研究相对较少,而且在一般的求核算法中,其时间复杂度为[O(|C||U|2)]。为了有效地降低算法的时间复杂度,给出了一个不完备决策表的差别矩阵定义和基于差别矩阵的核定义,并证明了该定义与基于不完备决策表的核定义是等价的。在此基础上,利用差别矩阵方法来设计一种计算不完备决策表的求核算法,其时间复杂度降为[O(|C||Upos||U|)]。最后用仿真实例说明了新算法的有效性。

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

Abstract: 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.

Key words: rough set, incomplete decision table, positive region, discernibility matrix, core