属性序下的快速约简算法

被引：49

作者：

胡峰 ^{[1
]}

王国胤 ^{[2
]}

机构：

[1] 重庆邮电大学计算机科学与技术研究所

[2] 西南交通大学信息科学与技术学院

来源：

计算机学报 | 2007年 / 08期

关键词：

粗集; 分治; 属性约简; 属性序;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

将分治法的思想溶入Rough集算法中,在给定属性序下,提出了基于分治策略的属性约简算法.利用该算法可以计算给定属性序下的唯一约简,并能快速得到海量数据的属性约简.在一次性将决策表的所有数据调入计算机内存的情况下,算法的平均时间复杂度为O(|U|×|C|×(|C|+log|U|)),空间复杂度为O(|U|+|C|).仿真实验结果说明了算法的高效性.

引用

页码：1429 / 1435

页数：7

共 12 条

[1] 二维表快速排序的复杂度分析
胡峰
王国胤
[J]. 计算机学报, 2007, (06) : 963 - 968
[2] 一个复杂度为max(O（|C||U|）,O（|C|2|U/C|）)的快速属性约简算法
徐章艳
刘作鹏
杨炳儒
宋威
[J]. 计算机学报, 2006, (03) : 391 - 399
[3] 基于U/{a}划分的最小约简构造
李订芳
李贵斌
章文
[J]. 武汉大学学报(理学版), 2005, (03) : 269 - 272
[4] 决策表核属性的计算方法
王国胤
[J]. 计算机学报, 2003, (05) : 611 - 615
[5] Rough集高效算法的研究
刘少辉
盛秋戬
吴斌
史忠植
胡斐
[J]. 计算机学报, 2003, (05) : 524 - 529
[6] 一个新的差别矩阵及其求核方法
叶东毅
陈昭炯
[J]. 电子学报, 2002, (07) : 1086 - 1088
[7] 基于条件信息熵的决策表约简
王国胤
于洪
杨大春
[J]. 计算机学报, 2002, (07) : 759 - 766
[8] 粗糙集理论及其应用进展
胡可云
陆玉昌
石纯一
[J]. 清华大学学报(自然科学版), 2001, (01) : 64 - 68
[9] Reduct and attribute order
Han, SQ
Wang, J
[J]. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY, 2004, 19 (04) : 429 - 449
[10] Jue Wang,Ju Wang.Reduction algorithms based on discernibility matrix: The ordered attributes method[J].Journal of Computer Science and Technology,2001(6)

← 1 2 →