一种快速计算HU差别矩阵的属性约简算法

被引：13

作者：

徐章艳 ^{[1
,2
]}

杨炳儒 ^{[1
]}

宋威 ^{[1
]}

侯伟 ^{[1
]}

机构：

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

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

来源：

小型微型计算机系统 | 2008年 / 10期

基金：

北京市自然科学基金; 国家自然科学基金重点项目;

关键词：

粗糙集; 简化决策表; 差别矩阵; 差别区域; 属性重要性; 属性约简; 算法复杂度;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

在已有的基于HU差别矩阵的属性约简算法中,一般是以差别矩阵中的元素作为启发信息而设计的,其时间复杂度为O(|C|2|U|2).为降低该属性约简算法的时间复杂度,首先引入简化决策表的定义,并设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).然后在简化决策表的基础上,定义了差别区域,并给出基于差别区域的属性约简定义,同时证明了基于差别区域的属性约简与基于差别矩阵的属性约简等价.在此基础上,以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性重要性的公式,并给出了它的递归计算方法,其时间复杂度为O(U/C|).最后以属性重要性为启发信息,设计了一个基于差别矩阵的快速属性约简算法,其时间复杂度降为max(O(|C||U|,O(|C|2|U/C|)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性.

引用

页码：1820 / 1827

页数：8

共 11 条

[1] 一个复杂度为max(O(|C||U|),O(|C||U/C|))的快速属性约简算法
徐章艳
刘作鹏
杨炳儒
宋威
[J]. 计算机学报, 2006, (03) : 391 - 399
[2] 一种新的快速计算正区域的方法
刘少辉
盛秋戬
史忠植
[J]. 计算机研究与发展, 2003, (05) : 637 - 642
[3] 决策表核属性的计算方法
王国胤
[J]. 计算机学报, 2003, (05) : 611 - 615
[4] Rough集高效算法的研究
刘少辉
盛秋戬
吴斌
史忠植
胡斐
[J]. 计算机学报, 2003, (05) : 524 - 529
[5] 一个新的差别矩阵及其求核方法
叶东毅
陈昭炯
[J]. 电子学报, 2002, (07) : 1086 - 1088
[6] 基于条件信息熵的决策表约简
王国胤
于洪
杨大春
[J]. 计算机学报, 2002, (07) : 759 - 766
[7] Reduction algorithms based on discernibility matrix: The ordered attributes method[J] . Jue Wang,Ju Wang.Journal of Computer Science and Technology . 2001 (6)
[8] Rough set theory and its applications to data analysis
Pawlak, Z
[J]. CYBERNETICS AND SYSTEMS, 1998, 29 (07) : 661 - 688
[9] Rough computational methods for information systems[J] . J.W. Guan,D.A. Bell.Artificial Intelligence . 1998 (1)
[10] Analysis on attribute reduction strategies of rough set[J] . Jue Wang,Duoqian Miao.Journal of Computer Science and Technology . 1998 (2)

← 1 2 →