Theory and Algorithms of Attribute Decrement for Concept Lattice

Incremental algorithms for the construction of concept lattices are of key importance. But most of them focus on the case of the addition of objects or attributes in formal context. When the attributes in formal context are deleted, reconstructing concept lattice by these algorithms is needed. It is very time consuming. The theory and algorithms of incrementally obtaining new concept lattice by updating the old one after attributes being deleted are investigated in this paper. At first, the mapping relation between concepts of the old and new concept-lattice is explained and the changes of edges from the old concept lattice to the new one are analyzed. Based on this, two decremental algorithms called top-down and bottom-up algorithms are proposed, by which the original concept lattice can be directly modified to obtain the new one, and reconstructing the whole structure from scratch is avoided. Relying on the structure of concept lattice, the algorithms only explore limited parts of the lattice for modifying. Thus, its time complexity is reduced to O(‖L‖·‖G‖·‖M‖). Experimental results show that the algorithms presented can save considerable time compared with the traditional algorithms.