基于简化的二进制差别矩阵的快速属性约简算法

被引：16

作者：

徐章艳 ^{[1
]}

杨炳儒 ^{[2
]}

宋威 ^{[2
]}

机构：

[1] 广西师范大学计算机系

[2] 北京科技大学信息工程学院

来源：

计算机科学 | 2006年 / 04期

关键词：

粗糙集; 二进制差别矩阵; 简化的二进制差别矩阵; 核; 复杂度;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

目前,基于二进制差别矩阵的属性约简算法有如下不足:算法的时间和空间复杂度不理想;所得到的属性约简与由基于正区域的属性约简的定义得到的属性约简不一致。本文给出一个简化的二进制差别矩阵和相应的属性约简的定义,证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化的二进制的差别矩阵中,要先求出IND（C）,故设计了一个较好的求 IND（C）的算法,其复杂度被降低为 O（|C‖U|）。在此基础上设计了一个快速属性约简算法,其时间复杂度和空间复杂度分别被降为 max{O|C|2(|U?‖U/C|)),O（|C‖U|）}和 max{O（|U|）,O(|C|(|U?‖U/C|))}。

引用

页码：155 / 158

页数：4

共 6 条

[1] 一个新的二进制可辨识矩阵及其核的计算 [J].