A partition-based approach towards constructing Galois (concept) lattices

Galois lattices and formal concept analysis of binary relations have proved useful in the resolution of many problems of theoretical or practical interest. Recent studies of practical applications in data mining and software engineering have put the emphasis on the need for both efficient and flexible algorithms to construct the lattice. Our paper presents a novel approach for lattice construction based on the apposition of binary relation fragments. We extend the existing theory to a complete characterization of the global Galois (concept) lattice as a substructure of the direct product of the lattices related to fragments. The structural properties underlie a procedure for extracting the global lattice from the direct product, which is the basis for a full-scale lattice construction algorithm implementing a divide-and-conquer strategy. The paper provides a complexity analysis of the algorithm together with some results about its practical performance and describes a class of binary relations for which the algorithm outperforms the most efficient lattice-constructing methods. (C) 2002 Elsevier Science B.V. All rights reserved.