改进的差别矩阵及其快速求核算法  

Improved Discernibility Matrix and Its Algorithm for Quickly Computing the Core

作　　者：杨传健[1] 姚光顺[1] 马丽生[1] 

机构地区：[1]滁州学院计算机系,安徽滁州239012

出　　处：《计算机工程与科学》2010年第3期78-81,共4页Computer Engineering & Science

基　　金：安徽省高等学校省级自然科学研究资助项目(KJ2008B117;KJ2010B015);安徽省高等学校优秀青年人才基金资助项目(2009SQRZ146;2010SQRL138)

摘　　要：求核是粗糙集中一个重要的研究内容之一。本文对杨明的基于差别矩阵求核方法进行研究,实例表明其方法还存在一些不完善。为了能够进一步提高求核效率,对差别矩阵进行改进,提出一种简化差别矩阵的定义,并给出求核方法,同时证明了由该方法获得的核与正区域的核是等价的,由此设计求核算法,其时间复杂度为max{O(|C||U|),O(|C||U/C||U′1|)},空间复杂度为O(|C||U/C||U′1|)。实验表明,该算法是有效的、高效的,且能适合大数据集的处理。Computing the core is an important research issue in the rough set. The method for computing the core based on improved discernibility matrix, which was presented by Yang Ming, is studied. The example shows that the method is still imperfect in some aspects. In order to improve the efficiency of computing the core, the definition of a simplification discernibility matrix and the method of computing the core are provided. It is proved that the core acquired from the method is equivalent to the core based on the positive region. Based on this, a computing core algorithm is designed, and its time complexity is max max{O（｜C｜｜U｜）,O（｜C｜｜U/C｜｜U′1｜）} ,and its space complexity is O（｜C｜｜U/C｜｜U′1｜）. The experimental results show that the algorithm is not only effective and efficient, but also suitable for processing huge data efficiently.

关 键 词：粗糙集 等价类 差别矩阵 核属性 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]