| 一种快速计算HU差别矩阵的属性约简算法 |
| |
| 引用本文： | 徐章艳,杨炳儒,宋威,侯伟.一种快速计算HU差别矩阵的属性约简算法[J].小型微型计算机系统,2008,29(10). |
| |
| 作者姓名： | 徐章艳 杨炳儒 宋威 侯伟 |
| |
| 作者单位： | 1. 北京科技大学,信息工程学院,北京,100083;广西师范大学,计算机系,广西,桂林,541004
2. 北京科技大学,信息工程学院,北京,100083 |
| |
| 基金项目： | 国家自然科学基金，北京市自然科学基金，广西教育厅科研项目 |
| |
| 摘 要： | 在已有的基于HU差别矩阵的属性约简算法中,一般是以差别矩阵中的元素作为启发信息而设计的,其时间复杂度为O(|C|2|U|2).为降低该属性约简算法的时间复杂度, 首先引入简化决策表的定义,并设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).然后在简化决策表的基础上,定义了差别区域,并给出基于差别区域的属性约简定义,同时证明了基于差别区域的属性约简与基于差别矩阵的属性约简等价.在此基础上,以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性重要性的公式,并给出了它的递归计算方法,其时间复杂度为O(U/C|).最后以属性重要性为启发信息,设计了一个基于差别矩阵的快速属性约简算法,其时间复杂度降为max(O(|C||U|,O(|C|2|U/C|)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性.
|
| 关 键 词： | 粗糙集 简化决策表 差别矩阵 差别区域 属性重要性 属性约简 算法复杂度 |
Quick Algorithm of Computing Attribute Reduction of HU's Discernibility Matrix |
| |
| XU Zhang-yan,YANG Bing-ru,SONG Wei HOU Wei.Quick Algorithm of Computing Attribute Reduction of HU's Discernibility Matrix[J].Mini-micro Systems,2008,29(10). |
| |
| Authors: | XU Zhang-yan YANG Bing-ru SONG Wei HOU Wei |
| |
| Affiliation: | XU Zhang-yan1,2,YANG Bing-ru1,SONG Wei1 HOU Wei1 1(School of Information Engineering,University of Science , Technology Beijing,Beijing 100083,China)2(Department of Computer,Guangxi Normal University,Guilin 541004,China) |
| |
| Abstract: | The elements of discernibility matrix are used as the heuristic information by all the existing attribute reduction algorithms based on HU's discernibility matrix.The temporal complexity of this kind of algorithm is O(|C|2|U|2).To lower the temporal complexity,firstly,the simplified decision table is introduced,and an algorithm with temporal complexity O(|C||U|)for calculating the simplified decision table is designed accordingly.Secondly,the definition of discernibility region based on the simplicity decis... |
| |
| Keywords: | rough set simplified decision table discernibility matrix discernibility region the significance of attribute attribute reduction algorithm complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
