一个有效的基于信息熵的启发式属性约简算法  

Efficient Heuristic Attribute Reduction Algorithm Based on Information Entropy

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

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

出　　处：《小型微型计算机系统》2009年第9期1805-1810,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金重点项目(69835001)资助;教育部科技重点项目([2000]175)资助;北京市自然科学基金项目(4022008)资助;广西教育厅基金项目(200807MS015)资助

摘　　要：基于信息熵的属性约简算法都是以信息熵为启发信息设计的,其时间复杂度并不理想.为降低算法的时间复杂度,引入简化决策表的定义,设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性的信息量,并给出了它的递归计算方法,其时间复杂度为O(|U/C|).同时证明了简化决策表上基于信息量的属性约简与原决策表上基于信息熵的属性约简是等价的.然后以属性的信息量为启发信息,设计了一个基于信息熵的快速属性约简算法,其时间复杂度降为max(O(|C||U|),O(|C|2|U/C|)),并用一个实例说明算法的有效性.实验结果表明新算法不仅具有高效性,且能处理大型决策表.Information entropy is usually used as the heuristic information by all the existing attribute reduction algorithms based on information entropy. The temporal complexity of this kind of algorithm is not good enough. Firstly, to lower the temporal complexity, the simplified decision table is introduced, and an algorithm with temporal complexity O（｜C｜｜U｜） is designed accordingly. Second- ly, to reduce the search space of simplified decision table, a new reasonable information measurement of attribute is defined. And then a recursive algorithm, whose temporal complexity is O（ ｜ U/C｜ ）, for computing the new measurement of attribute is proposed. Thirdly, it is proved that the attribute reduction algorithm based on information measurement and simplified decision table is equivalent to that based on the old decision table. Fourthly, using proposed information measurement of attribute as heuristic information, an efficient attribute reduction based on information entropy is proposed, 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. The experimental results show our algorithm is not only efficient, but also suitable for dealing with large decision table.

关 键 词：粗糙集 简化决策表 信息熵 属性的信息量 属性约简 算法复杂度 

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