Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (1): 135-137.

• 数据库、信号与信息处理 • Previous Articles     Next Articles

Algorithm for computing core based on incomplete decision table

ZENG Yanyan1, XU Zhangyan1, SHU Wenhao1, YANG Bingru2   

  1. 1.School of Computer Science and Information Engineering, Guangxi Normal University, Guilin, Guangxi 541004, China
    2.School of Information Engineering, University of Science and Technology Beijing, Beijing 100083, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2012-01-01 Published:2012-01-01

一种基于不完备决策表的求核方法

曾艳燕1,徐章艳1,舒文豪1,杨炳儒2   

  1. 1.广西师范大学 计算机科学与信息工程学院,广西 桂林 541004
    2.北京科技大学 信息工程学院,北京 100083

Abstract: The computing core algorithm is one of the important researches in rough set theory. At present, most of the computing core algorithms are based on complete decision table. The research of computing core based on incomplete decision table is few. A way to compute binary discernibility matrix based on incomplete decision table is provided. On this condition, an algorithm for computing core is designed with the binary dicernibility matrix. It also proves theoretically that the core computed based on binary discernibility matrix is equal to the core based on positive region. The time complexity of the new algorithm is [O(|C||U|2)]. An example is used to illustrate the correctness of the new algorithm.

Key words: rough set, incomplete decision table, binary discernibility matrix, compute core

摘要: 求核是粗糙集理论的重要研究内容之一,现有的求核算法大部分都是基于完备决策表的,对基于不完备决策表的求核研究很少。提出了不完备决策表二进制差别矩阵的构造方法,在此基础上,利用二进制差别矩阵设计了一种不完备决策表的求核算法。从理论上证明了基于二进制差别矩阵的求核与基于正区域的求核是相等的。新算法的时间复杂度是[O(|C||U|2)],用实例分析说明了新算法的正确性。

关键词: 粗糙集, 不完备决策表, 二进制差别矩阵, 求核