Study On Construction Algorithms Of Concept Lattice Based On Context Decomposition On CUDA

Formal concept analysis is a powerful tool for data analysis and rule extraction,who is widely used in knowledge representation,data mining and analysis.Concept lattice is the core data structure of formal concept analysis.In the application process of formal concept analysis,the concept lattice must be constructed first.In general,the nodes in the concept lattice grow exponentially.In this way,the efficiency of the concept lattice construction algorithm becomes the key to the successful application of formal concept analysis.Parallel computing is an effective means to improve algorithm efficiency.This paper mainly designs and implements the parallel construction algorithm of concept lattice based on CUDA parallel computing architecture,so as to improve the efficiency of concept lattice construction algorithm and make formal concept analysis get more effective application in various fields.First of all,this paper analyzes the basic ideas of classic concept lattice construction algorithms,and designs the C-In-Close algorithm based on the CUDA parallel computing architecture.Because the depth of support for recursion on the CUDA platform is not enough,the C-In-Close algorithm adopts an iterative method,starting from the known concepts at the top level,and iteratively calculating each level of concepts.The algorithm uses the uncorrelation between concepts at the same level to distribute the sub-concepts generated by the previous level of concepts to the various computing units of the GPU,calculates the subconcepts of this level of concept in a task-parallel manner,and transmits the generated concepts back to the CPU to complete an iteration process.This iteration is repeated until no new concept is generated,that is,the construction of concept lattice is completed.This paper conducts experiments on this algorithm on different data sets.The experimental results show that the C-In-Close algorithm can effectively calculate all formal concepts corresponding to the formal context.Secondly,in order to improve the parallelism of the algorithm,this paper designs the CCDFCbO algorithm based on the context decomposition of the concept lattice parallel construction algorithm on the CUDA parallel computing architecture platform.This algorithm decomposes the formal context into multiple sub-contexts through the cut points in the bipartite graph,and distributes the multiple sub-contexts to each thread of the GPU through the CPU side calling the kernel function in a data-parallel manner.Each thread then calls the GPU kernel function to apply for other threads to perform parallel calculations on the concepts of each sub-context,and then reconstruct the formal concepts corresponding to each sub-context to obtain the formal concepts of the original context.The algorithm merges the data parallel method on the basis of the original task parallel,and the parallelism of the algorithm is improved to a certain extent.In this paper,the experimental results on different data sets show that: in the case of uniform context decomposition,the CCD-FCbO algorithm can calculate all the formal concepts of the formal context faster than the C-FCbO algorithm;In the case of uneven decomposition,the CCD-FCbO algorithm is not as efficient as the CFCbO algorithm,which directly calculates the formal context,but is faster than the FCbO algorithm which is in the classic concept lattice construction algorithm.Finally,this paper designs the CCD-In-Close algorithm based on the context decomposition of the concept lattice parallel construction algorithm on the CUDA parallel computing architecture platform.The algorithm first decomposes the formal context,performs parallel calculations on the concepts of the decomposed sub-context,and reconstructs the concepts generated by the sub-context to obtain the formal concepts of the original context.This paper conducts experiments on this algorithm on different data sets.The experimental results show that: in the case of uniform context decomposition,the CCD-In-Close algorithm has a certain improvement in efficiency compared with the C-In-Close algorithm;In the case of uneven context distribution,the efficiency of the CCD-In-Close algorithm is slower than the C-InClose algorithm,which directly calculates the formal context,but faster than the In-Close algorithm which is in the classic concept lattice construction algorithm.Through the horizontal comparison of the running time of the C-FCbO algorithm and the C-In-Close algorithm under the same data conditions,it is found that the efficiency of the two algorithms is similar.Through the horizontal comparison of the running time of the CCD-FCbO algorithm and the CCD-In-Close algorithm under the same data conditions,it is found that the efficiency of the two algorithms is also similar.The four algorithms compared have a certain improvement in efficiency compared with the classic concept lattice construction algorithm,so the FCbO algorithm and In-Close algorithm are all suitable for the design of parallel concept lattice construction algorithm on the CUDA platform.