Research On Algorithms For Constructing Concept Lattice Based On Multiple Attributes Decrement

The incremental algorithm for removing attributes from concept lattice is a kind of important algorithm. We can extract the large scale of concept lattice from the large scale formal context. With the passage of time, redundant information in the lattice becomes more and more. Eliminating redundant information to get new lattice structure is a hot research topic in the present research. But there is still a lack of research work on deleting the redundant attributes from the lattice. In this thesis, we study the attributes decrement of the concept lattice and fuzzy concept lattice by using the related construction algorithm of concept lattice. The major work and contributions of this thesis are as follows:(1) The incremental construction algorithm of Zhang Lei et al. is only suitable for a single attribute reduction, and multiple attributes decrement is not further studied. In this thesis, two improved algorithms called M_BUAD and M_TDAD is proposed to solve this problem. Firstly, eliminating deleting attributes contained in the concept nodes and its parent nodes or child nodes, two algorithms can judge nodes’ type. Secondly the two algorithms do the corresponding work according to the type of nodes. M_BUAD can be used to eliminate any number of deleting attributes through one ergodic concept lattice structure. In the case that the number of objects and the number of deleting attributes is large, M_TDAD could show good time performance.(2) In view of the current research results, the problem of incremental attributes decrement of fuzzy concept lattice is seldom involved. In this paper, we propose an algorithm called FMBUAD on the basis of algorithm called M_BUAD by analyzing the relationship of membership degree between the extensions of fuzzy concept nodes and the partial order relation between the fuzzy concepts. The algorithm does not consider the accuracy of the true value set L. To a certain extent, the construction efficiency of fuzzy concept lattice is improved.(3) According to most of the current research work, parallel construction of concept lattice is mainly studied form the formal contexts. But there is no research based on the existing lattice structure on parallel construction of fuzzy lattice. On the basis of fuzzy concept lattice, this thesis proposes a parallel attributes decrement algorithm, namely PFMBUAD algorithm, based on the characteristics of multi-core computing environment. In this algorithm, firstly the original fuzzy concept lattice is divided into several sub lattices according to the hierarchy. Then the nodes in the sub lattices are processed by the different kernel of the computer. In the end, the critical nodes which cannot be processed in sub kernel of the computer will be processed in one computing node to get the correct lattice structure.(4) The proposed algorithm is proved and tested by the concept lattice construction algorithm based on multiple attributes decrement.