A Parallel Construction Model Of Concept Lattice Based On Depth First

Formal Concept Analysis is a tool which can analyze data.The Concept lattice is a core data structure of it.In recent years,Concept lattice has been widely applied to many fields such as machine learning, knowledge discovery, information retrieval and software engineering.In the application of concept lattice, the lattice construction algorithm plays a very important role. The completeness of concept lattice on the one hand insures the uniqueness of the final results which isn't influenced by the order of data or attributes and the construction algorithms, and on the other hand, it will make a large lattice even from a small set of original data. Because of completeness of concept lattice,the scale of lattice will make an exponential increase as the growth of objects and attributes of formal context.So,it is impossible to find an construction algorithm which is better than existing in the time complexity. Thus, how to construct a lattice efficiently from a large context is still a focus of the research on FCA.With the maturing of parallel computing technology and the reducing cost of high-performance parrallel computer, it offers a new thinking to solve this problem.That is using computeint and storing ability of parallel computer to build concept lattice.So, Based on the known existence currently of construction alogrithms and models, we emphasizes the research work of parallel construction of lattice. By analyzing the construction process of lattice,We find that, the intent of new object makes intermingle with all nodes of originally lattice bottom-up when inserting object. Establishment mark according to the result of intermingle and then doing corresponding operation,which can reduction number of comparing which is between the intent of the new object and the nodes of the originally lattice.Then the time complexity is reducted,too.On this basis,we design and implement a incremental construction algorithms of concept lattice based on depth first(AICACLBDF).Finally,we applicate this construction algorithms in the paralleling.Then we can get a model of paralleling construction of concept lattice based on depth first.The experiments proved that the AICACLBDF and the parallel building are effective.They perform better than Godin which is a traditional incremental construction algorithms on time and space complexity,and it improves efficiency of construction lattices.Especially, superiority of the algorithms is more obvious when the intersection between the intent of new object and attribute region of originally lattice is smaller.Contributions as follows:1)We design and implement a incremental construction algorithms of concept lattice based on depth first(AICACLBDF).Analysis performance of the algorithm. In experiment's foundation,we compare the algorithms with Godin which is a traditional incremental construction algorithms.2)We design a model of paralleling construction of concept lattice based on depth first and analysis the experimental results of this model.Then we compare the algorithms with Godin.