属性序下的快速约简算法

被引：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 [J].

Han, SQ ;

Wang, 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 →