Two Kinds Of New Methods For Concept Lattice Constructions

Concept lattice theory,also known as Formal Concept Analysis(simply as FCA),was proposed by R.Wille,a German mathematician,in 1982.It is mainly used to describe the relationship between objects and attributes in the formal context.For a given formal context,a concept is consisted by two parts: extent and intent.Concept lattice is a hierarchical structure owned with all of concepts in a given formal context.Therefore,for a given context,how to construct the correspondent concept lattice in a quick way is an important research issue for concept lattice theory.After studying on the already existed constructive algorithms of concept lattices,we propose a new constructive algorithm to build up a concept lattice with the assistance of the idea of graph theory.In addition,combined with the users' demand,some attributes and objects in the raw formal context need to be omitted.That is to say,they should be deleted from the raw formal context.For the new formal context which is born from the raw formal context by deleting both of some attributes and objects at the same time,this paper,with a convenient and an efficient way,presents an algorithm to construct the concept lattice assisted by the raw concept lattice.The main contents are as follows:1.On the basis of attributes topology graph of concept lattices,a kind of weakened attribute topology graph is defined.Afterwards,an algorithm for constructing concept lattice is proposed.The process of the algorithm is the following.At first,a weakened attributes topology graph for a formal context is built up.After that,based on the above weakened attributes topology graph,we search out any of the cycles which owns the maximum weight value so as to provide a concept,followed by producing all of the concepts in the formal context.The third step is to set up the concept lattice.Analyzing with the complexity of this algorithm provided here,we find that the complexity of our algorithm is lower than that before.In addition,using an example verifies the validity of this new algorithm.2.For the formal context based on the user's demands,an algorithm of constructing the correspondent concept lattice is proposed.And also,we prove the correct of this algorithm.The process of the algorithm is the following.At first,according to the construction of Hasse diagram among concepts in the original formal context,we find the hierarchical order among all of the concepts based on the cardinality of the intent in any of concepts.Secondly,in accordance with the bottom-up rule,for the concepts in the same layer,we decide their types in order to search out all of concepts in this layer.The third,we can obtain all the concepts in the new context.In addition,an example is given to illustrate the effective of the algorithm.