基于区分函数与强等价集理论的属性约简算法

Attributes Relative Reduction Approach Based on Discernibility Function and Strong Compressible Set Theory

提出了基于区分函数与强等价集理论的属性相对约简算法。在决策表的相对约简过程中采用区分矩阵来表达知识,并在区分函数的化简过程中引进强等价集的概念,通过去除强等价集的方法,使约简效率提高。现在已经证明,寻找决策表最小相对约简是典型的NP＿hard问题,采用本文所提供的算法可降低问题复杂度,同时又可节省大量的计算存储空间。通过实例分析,证明该算法是求解全部属性相对约简的快速有效的方法。

A kind of attributes relative reduction approach based on discernibility function and strong compressible set is proposed. In the process of relative reduction of decision table, knowledge is expressed by discernibility matrix. The concept of strong compressible set is introduced when discernibility function reduced.Efficiency of the reduction is improved by means of eliminating strong compressible set. It is shown that finding the minimal reduction of a decision table is an NP_hard problem. By the approach of this paper, the complicated degree of the problem could be reduced and a great deal of memory space is saved. The practical results show that the approach is quick and effective in solving all reduction of decision table.