Applications Of Graph Theory In Concept Lattice

Formal concept analysis,proposed by German mathematician Wille in 1982,first introduced philosophical ideas into the study of mathematics,studied the binary relationship between objects and attributes in formal context,and reflected its hierarchical relationship through lattice structure.As a carrier of knowledge expression in formal concept analysis,the process of discovering and extracting concepts from formal context is the process of knowledge discovery.Knowledge reduction is one of the important research directions in knowledge discovery,and attribute reduction theory is proposed for formal concept analysis.Attribute reduction in formal context cannot only make the lattice structure simpler but also reduce the difficulty of rule extraction.Therefore,attribute reduction is an important part of concept lattice theory.In addition,in the study of three-way concept,the construction method of three-way concepts is still relatively few,so the construction of three-way concepts is also an important research content.Using the properties of directed graphs in graph theory and combining with association matrix,this paper presents the methods of attribute reduction of formal context and the construction of three-way concepts.In view of the above problems,the following research work has been done:1.In the given classical formal context,we use the properties of the directed graph to find out the directional edge formed by the coverage relationship between the two attributes in the given formal context,find the relation between the directional edge and the attribute,and express it through the association matrix.Finally,the correctness and feasibility of the algorithm are verified by examples.2.In fuzzy formal context,attribute reduction is discussed based on crisp-fuzzy concept.Firstly,it is transformed into the corresponding reachable matrix according to the given fuzzy formal context.Then,according to the transformation matrix,the core attributes,relative non-attributes and absolute unnecessary attributes are discussed,and the corresponding algorithms are proposed.Finally,the correctness and validity of the algorithm are illustrated by examples.3.In classical formal context,combining with the idea of weights in graph theory,the construction of three-way concept is studied.First,the definition of three-way attribute weighted graphs are given,and the formal context is transformed into the corresponding three-way attribute weighted graphs according to the definition.Then,according to the three-way attribute weighted graphs design algorithm to get all three-way concepts.Finally,the feasibility and effectiveness of the algorithm are verified by examples.