The Applications Of Directed Graphs On Attribute Reduction In Various Formal Contexts

The theory of formal concept analysis proposed by a German mathematician Wille can be used to describe concepts and find out a formal tool for a hierarchical structure.The concept is a way of knowledge expression and the process of knowledge discovery is the process of translating the information contained into useful concepts in a database.Knowledge reduction is an important aspect of knowledge discovery in which formal concept analysis puts forward the theory of attribute reduction.In concept lattice theory,an attribute reduction can make the structure of a concept lattice more convenient,which is a helpful way for the discovery of knowledge and the rule extraction of data in formal contexts.Therefore,attribute reduction is an important part of concept lattice theory.Studying on attribute reduction in formal contexts,this paper presents a method of attribute reduction with the thought of directed graph in graph theory.On the one hand,the algorithm of attribute reduction is proposed by the constructed directed graph using formal concepts.On the other hand,the fuzzy-classical concepts is used to construct a directed graph,and the method of attribute reduction is proposed with attribute characteristics in a formal fuzzy context.At the final part,a directed graph is given based on rough approximation concepts and the algorithm of attribute reduction is proposed with attribute characteristics in incomplete contexts.The main contents are as follows:1.A directed graph is given,and meanwhile the correlation matrix for this directed graph is present.And further,based on some properties of the matrix,a judgement theorem is given for determining formal concepts and meet irreducible elements in classical formal contexts.We mainly study on the method of attribute reduction based on the theory of directed graphs.After that,an example illustrates the correct of the theory.2.Based on the notion of one-side fuzzy concepts,a directed graph and the correspondent correlation matrix to this directed graph are given.Combining some relative properties of matrix,we put forward the judgement theorems of meet irreducible elements and attribute characteristics,and propose the corresponding algorithm of attribute reduction in formal fuzzy contexts.The feasibility and effectiveness of the algorithm are verified by an example.3.Combining with the definition of rough approximation concepts,a directed graph is given in incomplete contexts.By discussing about its properties,the judgement theorems of meet irreducible elements and attribute characteristics are given in incomplete context.On this basis,the corresponding algorithm of attribute reductions is proposed and an example is given to show the validity of this algorithm.