基于简化差别矩阵的完备属性约简算法

被引：9

作者：

徐章艳 ^{[1
]}

杨炳儒 ^{[2
]}

宋威 ^{[2
]}

机构：

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

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

来源：

计算机工程与应用 | 2006年 / 26期

关键词：

粗糙集; 差别矩阵; 简化差别矩阵; 属性约简; 完备算法; 复杂度;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

由于基于老差别矩阵的属性约简的定义与基于正区域的属性约简的定义是不一致的,给出一个简化差别矩阵和相应的属性约简的定义,并证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化差别矩阵中,要先求出IND(C),故设计了一个较好的求IND(C)的算法,其复杂度被降为O(｜C‖U｜)。在此基础上设计了一个完备属性约简算法,其时间复杂度和空间复杂度分别被降为max｛O(｜C｜2(｜U′pos‖U/C｜)),O(｜C‖U｜)｝和max｛O(｜U｜),O(｜C｜(｜U′pos‖U/C｜))｝。

引用

页码：167 / 169+197 +197

页数：4

共 8 条

[1] 一种基于差别矩阵的属性约简完备算法 [J].

王兵 ;

陈善本 ;

不详 .

上海交通大学学报 , 2004, (01) :43-46

[2] 基于属性重要性的逐步约简算法 [J].

杜金莲 ;

迟忠先 ;

翟巍 .

小型微型计算机系统, 2003, (06) :976-978

[3] Rough集高效算法的研究 [J].

刘少辉 ;

盛秋戬 ;

吴斌 ;

史忠植 ;

胡斐 .

计算机学报, 2003, (05) :524-529

[4] Jelonek属性约简算法的一个改进 [J].

叶东毅 .

电子学报, 2000, (12) :81-82

[5] 知识约简的一种启发式算法 [J].

苗夺谦 ;

胡桂荣 .

计算机研究与发展, 1999, (06) :42-45

[6] 基于Rough Set理论的“数据浓缩” [J].

王珏 ;

王任 ;

苗夺谦 ;

郭萌 ;

阮永韶 ;

袁小红 ;

赵凯 .

计算机学报, 1998, (05) :393-400

[7]

Jue Wang,Ju Wang.Reduction algorithms based on discernibility matrix: The ordered attributes method[J].Journal of Computer Science and Technology,2001(6)

[8]

Zdzisław Pawlak.Rough sets[J].International Journal of Parallel Programming,1982

← 1 →