Information System Reduction And Granular Analysis And Its Application In Data Mining

On the basis of Rough set theory and Fuzzy set theory, this dissertation analyzes the reduction of complete information system. It includes two parts, in the theoretical part, the reduction of complete information system and the granularity in the reduction are discussed; in the application part, the universe reduction algorithm and attribute reduction algorithm proposed in the first part are applied to census dataset and achieve satisfactory result. The fruits of this dissertation can be used in the research of Data Mining. The contribution of this dissertation can be summarized as follows:1) The algebra properties and the changing law of conditional entropy are analyzed and an efficient attribute reduction algorithm is designed. It is found that possible reduct is not equivalent to approximate reduct, and possible reduct can neither keep positive region nor conditional entropy unchanged, while approximate reduct and -decision reduct can keep positive region and conditional entropy unchanged. Information granulation changes in information system are demonstrated, and an algorithm based on parallel symbiotic evolution is designed to find the minimal discernibility attribute reduct successfully. Finally, the fusion of reducts in parallel computing is discussed.2) Discretization lattice is proposed and analyzed. All discretization schemes of an information table are organized into a lattice named discretization lattice. It is proved that this lattice is a Boolean algebra, and the representation theory of discretization lattice is given. A mapping from discretization lattice to partition lattice is constructed on the basis of indiscernibility relation on attribute set. The information granulation and the changes of positive region and conditional information entropy in this lattice are illustrated. At last, the analysis of several discretization algorithms shows that these algorithms find the discretization schemes actually by searching the discretization lattice of the information system.3) The principle and algorithms of universe reduction are discussed. Universe reduction refers to the compression of object set in decision table. Continuity is assumed in a consistent decision table and two methods are proposed to evaluate the decision ability of decision tables. The representation of information granules is studied and three reduction algorithms are realized on the base of neighborhoodsystem, fuzzy equivalence relation between objects and fuzzy equivalence relation between rules. And then, an approach for knowledge reduction is given in the construction of history knowledge base to store interesting rules in incremental data mining.4) Census dataset is reduced successfully. The universe reduction algorithm based on neighborhood system and the parallel symbiotic evolution algorithm for attribute reduction are applied to a census dataset, and some valuable attributes highly correlated to total income are found by universe reduction, attribute reduction and fusion of attribute reducts.