Knowledge Reduction Of Information System Based On Improved Limited-Tolerance Relation

Rough set theory is a new theory of data analysis, it was first put forward by Poland scientist Z.Pawlak. At present it has developed to be a new math theory tool to deal with vagueness and uncertainty. It has been applied to many areas successfully including machine learning, pattern recognition, decision support, data mining, process control and predictive modeling.Pawlak rough set was established at the base of equivalent relation. But it is not suit to deal with incomplete information system. So, in the later research of rough set theory, the researchers address all kinds of models in order to expand its applying aspect. Examples are gerneralized binary-relation rough set model, variety precision rough set model, vague rough set model, probability rough set model etc. In order to describe the indistinct relationship of objects in incomplete information system, Krysckiewcz presented tolerance relation; Stefanowki etc. presented similarity relation and quantitative tolerance relation. Based on these relations, Wang G Y presents limited tolerance relation, followed by proving this model is superior to tolerance relation and similarity relation. In this paper, these relations are analyzed and improved limited-tolerance relation is presented. In this relation, thresholds are introduced and an incomplete system is divided into two parts. The aim of tolerant relation based on connection degree is to ascertain classes by which the lower approximation set and upper approximation set of a set in universe are confirmed. In the second part, this paper discusses algorithm property and presents some useful exploration about incomplete information system by introducing some important definition of complete information system.Knowledge reduction is one of the most important problems in the study of information system and knowledge discovery. There are many types of knowledge reductions in the area of rough sets. In this paper, some types of reductions of complete information are first presented to incomplete information system, followed by the relationship between these reduction methods. Also, for incomplete consistent decision tables, entropy reduction, distribution reduction, positive domain reduction, maximum distribution reduction, assignment reduction and approximate reduction are all proved to be equivalent. Based on condition information quantity, a heuristic algorithm for assignment reduction is presented, and the complexity of this algorithm is analyzed. Finally, the experimental result shows this algorithm can find this assignment reduction for incomplete information system.