信息系统的最大可能约简算法

Maximum Possible Reduction Algorithm of Information System

计算信息系统的所有约简是一个典型的NP完全问题.不计算所有约简,而寻找所有约简中发生的可能性最大的约简,可以为属性约简提供了一种新的方法.首先,基于区分矩阵计算每个属性出现在约简中的概率;其次,将此概率作为属性的重要度,构建了最大可能约简算法,并进行了算法分析;最后,通过两个具体实例对该算法进行了说明.理论分析结果表明,本文的算法是有效可行的.

Calculating all reductions of information system is a typical NP complete problem.The concept of maximum possible reduction of information system,rather than all reductions of information,is proposed as a new method for attribute reduction.Firstly,the probability of each attribute appearing in the reduction is calculated based on discernibility matrix.Secondly,this probability is used as importance degree of the attribute to construct maximum possible reduction algorithm,and the algorithm analysis is carried out.Finally,two examples are given to illustrate the algorithm.The theoretical analysis results show that this algorithm is effective and feasible.