Knowledge Reprensentation And Reduction Of Information Systems With Uncertainty

Concepts are regarded as the most fundamental units of human cognition and play a major role in cognitive tasks such as learning, memorizing and reasoning. Among different concept formation approaches available in the literature, Formal Concept Analysis (FCA) has recently received more attention. In this theory, concept lattice is the core notion, which reflects the hierarchal relationships among concepts. It has been applied to many disciplines, such as soft engineering, knowledge discovery and information retrieval. Classical FCA is based on definite formal context. However, real-world datasets are usually uncertain, and how to acquire useful knowledge from incomplete, imprecise and inconsistent data sets concerns many researchers. Knowledge reduction is another important issue in FCA. Through knowledge reduction, the complexity of the concept lattice can be reduced, the structure of the concept lattice can be simplified, and important aspects of the data can be revealed.This dissertation studies the issues of knowledge representation and knowledge reduction in uncertain information systems. Main contributions can be summarized as follows:1. In incomplete contexts, three-way approximate concept lattices are constructed based on the theory of three-way decisions, and two attribute reduction approaches are proposed. First, three-way approximate concepts are constructed to describe the uncertain knowledge with both inclusion method and exclusion method, which result in a comprehensive understanding of the uncertain knowledge. Then the relationship between the three-way approximate concept lattices and the classical concept lattices is revealed. Finally, two attribute reduction approaches are proposed to simplify the representation of the three-way approximate concepts, one is based on the discernibility matrix and the discernibility function, and the other is based on ∧-irreducible elements.2. In multi concept lattice models whose concept extents are crisp sets, a new framework for the construction of discernibility matrix, named the Object-Concept discernibility matrix (or OC discernibility matrix for short) is given. In the traditional method, when constructing a discernibility matrix, the comparisons of each two concepts are required, which result in a high complexity (O(nl2), where n is the number of attributes,l is the number of the concepts). In the OC-discernibility matrix, only comparisons between the objects and the concepts whose extent does not include the objects are required, which result in a considerable small complexity (O(mnl), where m is the number of objects, and generally speaking, m<<l). By full use of the partial order of the concept lattices, the OC-discernibility matrix is further simplified. Theoretical analysis and experiment results validate the efficiency of the proposed method.3. In formal fuzzy contexts, an approach to attribute reduction in crisply generated fuzzy concept lattice is proposed based on discernibility matrix and discernibility function. A crisply generated fuzzy concept (C-concept, for short) is a fuzzy concept that can be induced by a crisp attribute subset. It has three practical consequences when considering only the C-concepts. First, the number of the C-concepts is considerable smaller than the number of all fuzzy concepts. Second, the C-concepts can be considered as the most important ones. And third, the C-concept lattice is almost independent on the logical connectives. The attribute reduction theory and approaches in C-concept lattice are studied in this dissertation. First, the theoretical foundation for attribute reduction is given. Based on this, the discernibility matrix and the discernibility function are constructed to obtain the attribute reducts. After that, all attributes are classified into three types, i.e., the absolutely necessary attributes, the relatively necessary attributes and the absolutely unnecessary attributes, according to their different significances in the construction of the C-concept lattice, and the characteristics of each type are analyzed. Finally, the proposed method is used to conduct knowledge reduction in variable threshold concept lattices, which is a complementary to the existing knowledge reduction methods in variable threshold concept lattices.4. In inconsistent decision systems, a FCA based value reduction algorithm, named FCAVR, is proposed. Value reduction is an important kind of knowledge reduction in rough set theory. Two main problems are encountered when computing value reducts. First, value reducts are searched from attribute reducts in traditional methods, and the best value reducts may be missed. And second, in probabilistic rough set model, the introduction of the threshold values makes the decision region non-monotonic with respect to the granularity of partition, which results in a high complexity due to the examination of each subsets of the attribute set when searching for a value reduct, however this problem is not encountered in the classical RST. To solve these problems, a heuristic method, named FCAVR, is proposed in in classical rough set model to avoid the conduction of attribute reduction. Then the inconsistent information systems are converted to consistent ones, and the issue of value reduction in decision theoretic rough set model, a special probabilistic rough set model, is then converted to the issue of value reduction in a consistent information system. Based on the method mentioned above, the value reduction in decision theoretic rough set model can be computed. Finally, experiments on the UCI datasets validate the efficiency of the proposed method.