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

Quick Algorithm of Computing Attribute Reduction of HU's Discernibility Matrix

作　　者：徐章艳[1,2] 杨炳儒[1] 宋威[1] 侯伟[1] 

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

出　　处：《小型微型计算机系统》2008年第10期1820-1827,共8页Journal of Chinese Computer Systems

基　　金：国家自然科学基金重点项目(69835001,60463003)资助;北京市自然科学基金项目(4022008)资助;广西教育厅科研项目(200626)资助

摘　　要：在已有的基于HU差别矩阵的属性约简算法中,一般是以差别矩阵中的元素作为启发信息而设计的,其时间复杂度为O(|C|2|U|2).为降低该属性约简算法的时间复杂度,首先引入简化决策表的定义,并设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).然后在简化决策表的基础上,定义了差别区域,并给出基于差别区域的属性约简定义,同时证明了基于差别区域的属性约简与基于差别矩阵的属性约简等价.在此基础上,以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性重要性的公式,并给出了它的递归计算方法,其时间复杂度为O(U/C|).最后以属性重要性为启发信息,设计了一个基于差别矩阵的快速属性约简算法,其时间复杂度降为max(O(|C||U|,O(|C|2|U/C|)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性.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 decision table is proposed. At the same time, the attribute reduction definition based on discernibility region is provided. And it is proved that the attribute reduction based on discernibility region is equivalent to that based on discernibility matrix. Based on these conditions, to reduce the search space of simplified decision table, a new reasonable formula for measuring the significance of attribute is defined. And then a recursive algorithm, whose temporal complexity is O（ ｜U/C ｜ ）, for computing the significance of attribute, is proposed. Thirdly, using proposed the significance of attribute as heuristic information, an efficient attribute reduction based on the significance of attribute is proposed, and the temporal complexity is reduced to max（O（｜C｜｜U｜,O（｜C｜^2｜U/C｜））. Finally, an example is used to illustrate the effectiveness of the proposed algorithm. Theoretical analysis and experimental results show that the new algorithm is scalable.

关 键 词：祖糙集 简化决策表 差别矩阵 差别区域 属性重要性 属性约简 算法复杂度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]