一种新的信息系统启发式属性约简算法

A New Heuristic Attribution Reduction Algorithm Based on Information System

为降低信息系统属性约简算法的时间复杂度，首先引入简化信息系统的概念，然后定义了简化信息系统中属性集的区分对象数，证明了基于简化信息系统区分对象数的属性约简与原属性约简是等价的．进而定义了简化信息系统的属性重要性，并设计了一个快速求属性重要性的算法．同时，以属性重要性为启发式信息，设计了一个新的属性约简算法．新算法的时间复杂度降为max{O（｜C｜｜U｜），O（｜C｜^2｜U｜C｜）}．最后用一个实例说明了新算法的有效性．

To reduce the time complexity of attribute reduction algorithm based on information system, the definition of the simplified information system is introduced at first. Then the number of discernibility object of attribute set is defined in the simplified information system. And it is proved that attribute reduction based on the number of discernibility object in the simplified system is equivalent to that in the old information system. Then the definition of attribute importance in the simplified information system is proposed. And an algorithm for computing attribute importance is designed. At the same time, a new attribute reduction algorithm is designed with attribute importance as heuristic. Its time complexity is cut down to. At last, an example is used to illustrated the efficiency of the new algorithm.