Algebraic And Topological Study On Formal Concept Analysis And Rough Set Theory

Formal concept analysis (FCA) and rough set theory (RST) provide two important methods for data analysis and knowledge processing. They are two active relevant research fields in artificial intelligence and information science. On the one hand, there are differences in the research manners and research topics of them. The basic idea of RST is to construct concepts and rules by classifying data in relational databases and the key notions of it are approximation spaces and approximation operators. The central notions of FCA are formal contexts and concept lattices, which reflect the concept hierarchies briefly through certain relevance between objects and attributes and therefore deal with the data pithily. On the other hand, there are tight connections between FCA and RST since they are both based on relations (or orders) and have common research backgrounds and aims. Moreover, they are both closely related to topology, algebra and logic, and interact each other.With the rapid development of computer science and information science, more and more attention is paid to their mathematical foundation which has been the common field of mathematicians, computer scientists and information scientists. FCA and RST are just such two important research fields. In this dissertation, we study FCA and RST deeply from the aspects of algebra and topology. The main results are listed as follows.1. Topological properties such as separations Ti(i= 0,1,2), regularity, normality, compactness and connectedness for generalized approximation spaces are introduced from a topological point of view in Chapter 2. A generalized ap-proximation space (GA-space for short) is a pair (U, R), where U is a nonempty set and R is a binary relation on U. If R is a preorder, then (U, R) is in fact a topological space and thus called a topological GA-space. We first characterize the classical separations Ti (i= 0,1,2), regularity, normality and compactness for such kind of topological spaces (i.e., topological GA-spaces) in terms of given relations and then extend these characterizations to give concepts of separations Ti (i= 0,1,2), regularity, normality, compactness in general GA-spaces. By in-troducing R-open sets,R-closed sets and R-clopen sets we define and characterize connectedness of GA-spaces. Relationships among separations of GA-spaces are explored. Relationships between topological properties of topological spaces and those of the induced GA-spaces are also investigated. Hereditariness with respect to sub-GA-spaces of above mentioned topological properties is discussed.2. Lattice-theoretical properties of GA-spaces are studied in Chapter 3. The concept of regular sets of a GA-space (U, R) is introduced and algebraic structures of various families of subsets of (U, R) under the set-inclusion order are investigated. Main results are:(1) The family of all R-open sets (resp.,R-closed sets, R-clopen sets) is both a completely distributive lattice and an algebraic lattice, and in addition a complete Boolean algebra if relation R is symmetric. (2) The family of definable sets is both an algebraic completely distributive lattice and a complete Boolean algebra if relation R is serial. (3) The collection of upper (resp., lower) approximation sets is a completely distributive lattice if and only if relation R is regular. (4) The family of regular sets is a complete Boolean algebra if relation R is serial and transitive, which is a generalization of the corresponding result in domain theory.3. Approximation operators and rough approximations are introduced into quantales in terms of quantale congruences in Chapter 4. We discuss properties of the approximations of quantales and study rough (prime, semi-prime, primary) ideals and subquantales of quantales. We generalize the prime radical theorem of rings to rough prime ideals of quantales. Some results about homomorphism images of rough ideals and rough prime ideals of semigroups and rings are gen-eralized and improved in quantales.4. Formal concept analysis is studied by means of topological methods in Chapter 5. We introduce topological properties of formal contexts such as sepa-rations Ti (i= 0,1,2) and compactness. Properties and relationships of separa-tions Ti(i= 0,1,2) are discussed. It is proved that separations Ti(i= 0,1,2) are hereditary with respect to compatible subcontexts and embedding subcon-texts and that compactness is hereditary with respect to closed subcontexts. It is also proved that separations Ti (i= 0,1,2) and compactness of formal contexts are preserved by so-called infomorphisms satisfying certain conditions. More-over, we show that the finitely direct products of compact formal contexts (resp., T0, T1, T2 formal contexts without full rows) are also compact (resp., T0, T1, T2) formal contexts. 5. Algebraic properties of rough concept lattices are studied in Chapter 6. Given a context K, one can get the concept lattice L(K) in Wille's sense and the rough concept lattice RO-L(K). We discuss relationships between these two kinds of concept lattices. The notion of definable sets of contexts is introduced. It is proved that the family Def (K) of the definable sets under the set-inclusion order is a complete sublattice of RO-L(K) and a complete field of sets under some reasonable conditions. A necessary and sufficient condition for Def (K) to be equal to RO-L(K) is given. It is proved that RO-L(K) is a completely distributive lattice if and only if the involved relation is a regular relation. Several sufficient conditions for RO-L(K) to be algebraic are also given.