|
|||||
|
|
| 基于Skowron分明矩阵的有效属性约简算法 | |
| 引用本文： | 秦奕青,杨炳儒,徐章艳.基于Skowron分明矩阵的有效属性约简算法[J].北京科技大学学报,2009,31(3). |
| 作者姓名： | 秦奕青 杨炳儒 徐章艳 |
| 作者单位： | 1. 北京信息科技大学计算机学院,北京,100192;北京科技大学信息工程学院,北京,100083 2. 北京科技大学信息工程学院,北京,100083 3. 北京科技大学信息工程学院,北京,100083;广西师范大学计算机系,桂林,541004 |
| 基金项目： | 国家自然科学基金资助项目(No.60675030);;北京市教委科技发展计划面上项目(No.KM200910772013) |
| 摘 要： | 为降低基于Skowron分明矩阵属性约简算法的复杂度,提出了简化分明矩阵及其相应属性约简的定义,并证明了基于简化分明矩阵的属性约简与基于原分明矩阵的属性约简等价.在简化决策表的基础上,定义了一个函数,该函数能度量条件属性在简化分明矩阵中出现的频率,并给出了计算该函数的快速算法,其时间和空间复杂度均为O(|U/C|).用该函数设计了一个有效的基于原分明矩阵属性约简算法,算法的时间复杂度降为O(|C||U|)+O(|C|2|U/C|),空间复杂度降为O(|U|);并用实例证明了算法的有效性. |
| 关 键 词： | 粗糙集 分明矩阵 属性约简 复杂度 |
Efficient algorithm of attribute reduction based on Skowron's discernibility matrix |
|
| QIN Yi-qing,YANG Bing-ru,XU Zhang-yan.Efficient algorithm of attribute reduction based on Skowron's discernibility matrix[J].Journal of University of Science and Technology Beijing,2009,31(3). | |
| Authors: | QIN Yi-qing YANG Bing-ru XU Zhang-yan |
| Abstract: | To cut down the time and space complexity and improve the efficiency of the attribute reduction algorithm based on Skowron's discernibility matrix,the definitions of a simplified discernibility matrix and corresponding attribute reduction were provided.It is proved that attribute reduction based on the simplified discernibility matrix is equivalent to that based on the old one.By the foundation of a simplified decision table,a function which can measure the frequency of a condition attribute in the simplifi... |
| Keywords: | rough set discernibility matrix attribute reduction complexity |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |