【作者】 黄兵；

【导师】 周献中；

【作者基本信息】 南京理工大学 ， 控制科学与工程， 2004， 博士

【摘要】 本文以粗糙集理论为工具，不完备信息系统为对象，知识获取为目的，研究基于粗糙集理论的不完备信息系统知识获取理论与方法。主要内容如下： 1．研究了基于一般二元关系信息系统的不确定性度量和知识约简。针对一般二元关系的信息系统，给出了知识和粗糙集的不确定性量度，证明了新的粗糙熵是等价关系下粗糙熵的推广；针对广义粗糙集覆盖约简，给出了知识和粗糙集的不确定性量度。证明了随着知识确定性的增加，以上两种粗糙熵都是单调下降的。在一般二元关系下定义了六种知识约简，讨论了它们之间的关系。提出了属性约简保留性定义。证明了上下近似约简具有属性保留性，通过反例说明了分布约简、最大分布约简、分配序约简都不具有属性保留性。给出了最大分布约简、分配约简、分配序约简的一般算法。分析了这些算法的时间复杂度，并通过实例说明了它们的有效性。 2．研究了相容关系的粗计算及知识约简。定义了相容矩阵，建立了相容关系与相容矩阵之间的一一对应关系，通过相容矩阵的计算来刻画基于相容关系的粗计算。定义了基于相容关系的上下近似约简，提出了上下近似一致集的判定定理，进一步给出求所有上下近似约简的分辨矩阵法。为克服分辨矩阵方法时间复杂度是指数级的，提出了一种知识约简的启发式算法，并通过实例分析说明了算法的有效性。 3．研究了相似关系的粗计算及知识约简。定义了相似矩阵，建立了相似关系与相似矩阵之间的一一对应关系，通过相似矩阵的计算来刻画基于相似关系的粗计算。定义了基于相似关系的上下近似约简，提出了上下近似一致集的判定定理，给出求所有上下近似约简的分辨矩阵法。提出了一种上下近似约简的启发式算法，并通过实例分析说明了算法的有效性。 4．研究了规则提取的矩阵算法。通过定义适当的矩阵，提出了基于一般二元关系的最大分布规则、分配规则、基于相容关系的上下近似规则和基于相似关系的上下近似规则的矩阵算法。该方法在提取信息系统的所有相应规则的同时获得相应的所有约简。 5．设计了一个基于本文提出的知识约简和规则提取方法的不完备信息系统知识获取系统原型。更多还原

【Abstract】 Rough sets-based theory & approaches for knowledge acquisition in incomplete information systems are studied in this dissertation. The main contributions include:1. The roughness and reduction of incomplete information systems based on binary relation are studied. Firstly, the rough entropy is defined to measure the roughness of knowledge and rough sets based on general binary relation. It is proved that the new entropy generalizes that of equivalence relation in complete information systems. Secondly, under generalized rough set covering reduction, the entropy of knowledge and rough sets is proposed and this entropy is proved to decrease monotonously as the generalized rough set covering reduction becomes finer. Thirdly, six knowledge reductions are defined under general binary relation -based incomplete information systems, and the relations between them are discussed. The consistency of reduction is presented. The consistency of upper and lower approximation reduction is proved to hold, however, that of maximum distribution, distribution, and ordered assignment reduction does not through counterexamples. The general algorithms for maximum distribution reduction, assignment reduction and ordered assignment reduction are examined and their time complexities are analyzed. Finally, example analysis illustrates the validity of these algorithms.2. Rough computation and reduction based on tolerance relation are examined. Tolerance matrix is defined and the one-to-one relation between tolerance relation and tolerance matrix is constructed. Rough computation based on tolerance relation is executed through tolerance matrix computation. The upper/lower approximation reduction based on tolerance relation is presented, the judgement theorems of the consistent sets of upper/lower approximation are proved, and generalized discernibility matrices are proposed. A heuristic algorithm for minimal upper/lower approximation reducts is devised.3. Rough computation and reduction based on similarity relation are researched. Similarity matrix is defined and the one-to-one relation betweensimilarity relation and similarity matrix is constructed. Rough computation based on similarity relation is executed through similarity matrix computation. The upper/lower approximation reduction based on similarity is presented; the judgement theorems of the consistent sets of upper/lower approximation are proved, and generalized discernibility matrices are proposed. A heuristic algorithm for minimal upper/lower approximation reducts is devised.4. Matrix computations for rules extraction are presented. By defining appropriate matrices, rules extraction approaches for maximum distribution and assignment rules based on general binary relation, the upper/lower approximation rule extraction based on tolerance and similarity relation are studied. This algorithm can extract all rules and acquire all reducts.5. On the basis of the above algorithms, a prototype system for knowledge acquisition of incomplete information systems is developed.更多还原