基于Skowron分明矩阵的有效属性约简算法  

Efficient algorithm of attribute reduction based on Skowron's discernibility matrix

作　　者：秦奕青[1,2] 杨炳儒[2] 徐章艳[2,3] 

机构地区：[1]北京信息科技大学计算机学院,北京100192 [2]北京科技大学信息工程学院,北京100083 [3]广西师范大学计算机系,桂林541004

出　　处：《北京科技大学学报》2009年第3期398-404,共7页Journal of University of Science and Technology Beijing

基　　金：国家自然科学基金资助项目(No.60675030);北京市教委科技发展计划面上项目(No.KM200910772013)

摘　　要：为降低基于Skowron分明矩阵属性约简算法的复杂度,提出了简化分明矩阵及其相应属性约简的定义,并证明了基于简化分明矩阵的属性约简与基于原分明矩阵的属性约简等价.在简化决策表的基础上,定义了一个函数,该函数能度量条件属性在简化分明矩阵中出现的频率,并给出了计算该函数的快速算法,其时间和空间复杂度均为O(|U/C|).用该函数设计了一个有效的基于原分明矩阵属性约简算法,算法的时间复杂度降为O(|C||U|)+O(|C|2|U/C|),空间复杂度降为O(|U|);并用实例证明了算法的有效性.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 provid- ed. 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 simplified discernibility matrix was defined. An algorithm for the above function was designed. Its time and space complexity are O （｜U/C｜）. Then an efficient algorithm of attribute reduction based on Skowron＇ s discernibility matrix was designed with the new function. Its time complexity is cut down to O（｜C｜｜U｜） ＋ O（｜C｜^2｜U/C｜）, and space complexity to O（｜U｜）. Finally, an example was used to illustrate the effectiveness of the new algorithm.

关 键 词：粗糙集 分明矩阵 属性约简 复杂度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]