| 一种快速的不完备决策表属性约简算法 |
| |
| 引用本文： | 舒文豪,徐章艳,钱文彬,杨炳儒.一种快速的不完备决策表属性约简算法[J].小型微型计算机系统,2011,32(9). |
| |
| 作者姓名： | 舒文豪 徐章艳 钱文彬 杨炳儒 |
| |
| 作者单位： | 1. 广西师范大学计算机科学与信息工程学院,广西桂林,541004
2. 北京科技大学信息工程学院,北京,100083 |
| |
| 基金项目： | 国家自然科学基金项目(60963008)资助; 广西省教育厅科研基金项目(200807MS015)资助; 广西研究生教育科研创新基金项目(200910602M61)资助 |
| |
| 摘 要： | 目前,关于不完备决策表的属性约简算法已有不少,其中在很多算法中,其时间复杂度为O( |C|3|U|2).为有效地降低算法的时间复杂度,给出一个差别矩阵的定义和基于差别矩阵属性约简的定义,并证明了该属性约简与基于正区域的属性约简是等价的.生成的差别矩阵无需比较Umeg之间的对象,使差别矩阵得到有效地简化,进一步降低算法的存储空间.在此基础上,利用简化的差别矩阵设计一个快速计算不完备决策表的属性约简的算法,其时间复杂度降为maX{O( |C|2|Upos,||U|),O(K|C||U|)}.(其中K=max{ |Tc(xi)|,xi∈U}).最后用实例仿真说明了新算法的有效性.
|
| 关 键 词： | 粗糙集 不完备决策表 正区域 差别矩阵 属性约简 算法复杂度 |
Quick Attribution Reduction Algorithm Based on Incomplete Decision Table |
| |
| SHU Wen-hao
,
XU Zhang-yan
,
QIAN Wen-bin
,
YANG Bing-ru.Quick Attribution Reduction Algorithm Based on Incomplete Decision Table[J].Mini-micro Systems,2011,32(9). |
| |
| Authors: | SHU Wen-hao XU Zhang-yan QIAN Wen-bin YANG Bing-ru |
| |
| Affiliation: | SHU Wen-hao1,XU Zhang-yan1,QIAN Wen-bin2,YANG Bing-ru21(School of Computer Science and Information Engineering,Guangxi Normal University,Guilin 541004,China)2(School of Information Engineering,University of Science and Technology Beijing,Beijing 100083,China) |
| |
| Abstract: | At present,some scholars provided the attribution reduction algorithms of incomplete decision table.The time complexity of many algorithms are O(|C|3|U|2).To cut down the time complexity of the algorithms for computing attribution reduction,the definition of discernibility matrix based on positive region and the corresponding definition of the attribution reduction are provided.At the same time,it is proved that the attribution reduction is equivalent to the attribution reduction based on the positive regio... |
| |
| Keywords: | rough set incomplete decision table positive region discernibility matrix attribution reduction algorithm complexity |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
