A Fast Incremental Algorithm For Building Concept Lattice Based On The Partial Order Relations

Concept lattice theory has become an efficient data analysis tool and been widelyused in many engineering fields such as data mining, software engineering,information retrieval, and so on. It is based on concepts and concept lattice which isestablished by the partial order relation between concepts. However, the number ofconcepts will increase exponentially with the size of context, therefore finding a goodalgorithm is of great importance.Based on deep research in incremental algorithms, this paper proposed a kind ofconcept lattice algorithm by using the partial order set. The process of latticeconstruction can be divided into concept updating, finding the new concept andupdating lattice structure. To complete the process of concept updating, a new conceptrenovation method is used to complete the concept updating process. That is, if thesub-concept is updated, the super-concept will update too. For seeking new concept, byproving theorem, a method of object-based grouping is used to find a new concept.Then a new bottom-up lattice structure update algorithm is appeared to accomplish thelast process. Since then, by defining the concept objects synchronize the processes ofconcepts updating and creating. Finally, a algorithm named Parto is implemented.In the last part of paper, the performance of Parto has been discussed throughtheoretical analysis and experimental comparison. Theoretical analysis explains thatParto algorithm is better than Godin incremental algorithm in all kinds of formalcontexts. And the experimental data show that Parto algorithm is15percent faster thanGodin algorithm in sparse background. Furthermore, in the dense background, beforethe deterioration point of the Godin, Parto and Godin algorithm have a similarperformance curves, and they all have a better performance than the batch algorithmBodat. After the point, Parto keeps a good performance, while the Godin algorithm isincreasing exponentially and lower than Bodat algorithm.