Rough Sets-based Theory & Approaches For Knowledge Acquisition In Incomplete Information Systems

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.