Algorithms For Constructing Three-way Concept Lattices

Formal concept analysis was proposed by professor Wille in 1982,whose core structure is formal concepts and formal concept lattices.It is widely used in the fields of knowledge discovery,software engineering and Web services.However,formal concept analysis adopts the classical decision,which can only express refusal and acceptance.In order to express refusal,acceptance and no commitment in three-way decision,Qi et al.developed three-way concept analysis on the basis of formal concept analysis in 2014,whose core structure is three-way concepts and three-way concept lattices.At present,three-way concept analysis theory is still in the initial stage.How to construct three-way concepts and three-way concept lattices is the key content of the theory.This paper mainly studies and designs the construction algorithms of three-way concepts and three-way concept lattices to provide support for three-way concept analysis.First of all,this paper analyzes the performance of the algorithms Bordat,CbO,In Close,FCb O and In Close3 for constructing formal concepts,and then proposes a three-way concepts construction algorithm named Cb O3 C by adopting the idea of these serial construction algorithms.In order to improve the efficiency and lower the memory overhead,Cb O3 C employs partial closure canonicity test and inherited failure test to reduce the repeated computations of three-way concepts,and implements set operations on the basis of bits.By using the compiler switch,it automatically generates three-way concepts or core three-way concepts.The experiments on several UCI and random data sets show that Cb O3 C can efficiently calculate all three-way concepts of a formal context.Secondly,in order to make the best of CPU resources and improve the construction speed of three-way concepts,the parallel construction algorithm PCbO3C is designed on the basis of analyzing the existing formal concepts parallel construction algorithm.On the basis of Cb O3 C,PCbO3C applies the idea of the algorithm PCb O to employ the multi-threaded technology to compute all three-way concepts in parallel.The basic idea is that PCbO3C computes all three-way concepts of the Lth layer in series,and creates P threads to process all sub-concepts of each L-layer concept in parallel by calling Cb O3 C respectively.In order to validate the efficiency of PCbO3C,experiments on some data sets are conducted in the situation of 24 CPU cores.The results show that the speed of PCbO3C can be increased by 67.05% in average with the number of threads doubled if the number of threads is no more than 24.Finally,in order to generate the Hasse diagram of three-way concept lattices,it is necessary to obtain the parent-child relationship between three-way concepts.This paper gives two methods.One is to use the algorithm described above to generate all three-way concepts,and calculate parent-child relationship between three-way concepts.Then the algorithm PCbO3CL is proposed.The other is to label the parent-child relationship when computing three-way concepts.Then the algorithm Bordat3 CL is designed.After calculating all three-way concepts and their parent-child relationship,we can use the existing tools to draw out the Hasse diagram of three-way concept lattices.In this paper,the performance of the algorithm PCbO3CL and Bordat3 CL is analyzed through experiments on several random data sets,which show PCbO3CL is faster.