Improvement Of Chein Algorithm For Building Concept Lattice

Formal concept analysis a effective tool in data analysis, which has been widely applied to many fields such as machine learning, knowledge discovery, information retrieval and software engineering. Concept lattice is the the main data structure in formal concept analysis theory, and many application of concept lattice has to the construce the concept lattice first. The completeness of concept lattice is one of the major advantages of concept lattice.It insures the uniqueness of the final results which doesn't been influenced by the order of data or attributes and the construction algorithms.In the other hand, it will make a large lattice even from a small set of original data. Theoretically speaking, the nodes number of the lattice will increase exponentially with the growth of objects and attributes in the worst condition.So for the construction of concept lattic, there is a problem to solve, how to improve the efficiency of construction and reduce the time complexity.Chein Algorithm, which is one of the algorithms used to construce lattice, top-down constructing the lattice.If using Chein Algorithm to construce lattice,it's clarity between concepts and easy to generate Hasse diagram.But the algorithm is inefficient.In the process of generating the concepts in new level,it intersects all the concepts between each other in current level,which has to consume much time in calculation and generates many concepts of redundancy. The concepts of redundancy may cause more intersection between concepts in the next level and generate more concepts of redundancy in the next level. That's why Chein Algorithm is inefficient and has to use up a lot of storage space to store.Based on the research of concept lattice structure of the current algorithms, this paper proposed an new algorithm to improve the Chein Algorithm. By analyzing the existing problems of Chein Algorithm,this paper uses the information reflection to explain why Chein Algorithm do not delete the concepts of redundancy in it's construct process,and improve the algorithm in this respect.The main idea of the modified algorithm is to make sure whether exist concepts of redundancy in current level.We can classify concepts of redundancy and the corresponding Non-redundant concepts as a group according to the contain relations between them,if redundant concepts exist.When generating concepts in next level,we can only make intersection between Non-redundant concepts and their corresponding redundant concepts in each groups.If there's no redundant concepts exist in current level, we can only make intersection between Non-redundant concepts.By this way, modified algorithm reduce the times of intersection and retain the advantages of Chein Algorithm.By analysis and Experiments Chein Algorithm and modified algorithm, it shows that the modified algorithm is more effective than Chein Algorithm, specially with the increasing of data scale in formal context.So it's more suitable to using modified algorithm to construct lattice compared with Chein Algorithm, when the data scale of formal context is big.Major work:1) Against the original approach,this paper proposes a modified algorithm,which generates the concepts of next level by intersecting Non-redundant concepts in current level or intersecting Non-redundant concepts with it's corresponding redundant concepts in current level.These two ways are more effective than intersecting all concepts in current level,so the modified algorithm is more effective than Chein Algorithm.2) In the research of Chein Algorithm,this paper raises the concept of information reflection,and proved Chein Algorithm can't delete redundant concepts when they doesn't reflect all the information they containing.Only when the information contained in the redundant concepts is totally reflected,the redundant concepts can be deleted.