Direct Product Decompositions of Concept Lattices

Formal Concept Analysis is a powerful tool to visualize hierarchical data structures by computing concept lattices from formal contexts. However, the interpretability is often limited by the complexity and sheer size of the resulting concept lattice. To counteract this problem, a variety of ways to decompose a concept lattice into smaller constituent lattices have been developed, which can aid with the interpretation of the results. This work will examine decomposition methods based on the direct product of lattices. These have already been explored as a method to decompose concept lattices in a previous study, however, this investigation was limited to reducing the size of a lattice using this decomposition. This work will expand the research and attempt to form a comprehensive interpretation of the direct product decomposition in terms of the properties of the concept lattices’ objects and attributes, and how they must relate to each other, for such a decomposition to exist. Since in the previous study, concept lattices could only be reconstructed from their factors up to isomorphism, an attempt will be made to develop a variant of the direct product operation that respects the concepts of the factors and itself produces a concept lattice. The decomposition method will then be evaluated using a variety of criteria. Multiple variants of computing a direct product decomposition will be considered, and their properties will be examined. This work will also examine the case of a concept lattice either having multiple distinct direct product decompositions, or its factors being themselves further decomposable. To visualize how these different decompositions of a lattice relate to each other, the Direct Decomposition Lattice, which represents the factors of a concept lattice in a hierarchical structure, will be introduced. An already known limitation of the direct product decomposition for concept lattices is its limited applicability to real-world examples. Most concept lattices do not fulfill the structural requirements to permit such a decomposition. Therefore this work will also explore ways to apply direct product decomposition to sublattices of concept lattices, to take advantage of the easy-to-interpret meaning of the decomposition method. Ways to expand an indecomposable concept lattice so that it permits a direct product decomposition will also be briefly considered.