不完备知识系统非对称相似关系的最小简式

在实际决策时，人们所面临的往往是大量的数据，因此知识约简很重要，已经证明：在知识系统中求解最小简式是NP完全问题。对于完备知识系统，已有很多方法来求解最小简式，而对于不完备知识系统，这方面的研究较少，处理也更困难。对于不完备的知识系统，可以采用一些补齐算法先进行完备化处理，然后再对所得到的完备知识系统采用一些常用的约简算法如分辨矩阵法等进行处理。但是，补齐处理只是以主观估计值，将未知值补齐，不一定完全符合客观事实。因此，需要保持知识系统的原始信息不发生变化的前提下进行约简。设计了二进制矩阵，和不完备知识系统的非对称相似关系结合，证明了一个定理，并提出了一种基于非对称相似关系的遗传算法，求解不完备知识系统中的最小简式。算法的适应度函数较为简单，可以有效求出最小简式子。实验结果显示了算法的有效性。

Finding minimal reducts from incomplete information systems

In real decision-making system, people often face huge amounts of data. So knowledge reduction is important. There are a lot of methods to computing the minimal reducts in complete information systems. But for incomplete information systems, the research of this aspect is few and difficult. Incomplete data sets may be transformed into complete data sets by similarity measures or by removing objects with unknown values before handling with them. But it is only by what to be supposed, and may not accord with the fact. So it is necessary to find reducts directly from incomplete data sets without guessing unknown attribute values. A theorem is proved on the basis of defined binary matrix and asymmetry relation, and a genetic algorithm based on this theorem is proposed for finding the minimal reducts from incomplete information systems. The experimental studies indicate that the genetic algorithm have good performance.