Reducing the Size of Concept Lattices: The JBOS Approach.
Sérgio Mariano Dias, Newton José Vieira · 2010
Abstract. Formal concept analysis (FCA) is used nowadays in a large number of applications in several different areas. Nevertheless, in some applications the size of a concept lattice may be prohibitively large, thus creating a need for new approaches and algorithms to reduce concept lattices to a manageable size. This paper presents a new method for reducing a concept lattice’s complexity and introduces a new methodology for evaluating reduction methods. The main idea of the proposed approach, junction based on objects similarity (JBOS), is the substitution of groups of “similar ” objects by prototypical ones. As a consequence, the resulting lattice is simplified in its size and structure. The user has control of the degree of simplification by means of parameters specification. Two measures are proposed for the evaluation of the final lattice with respect to the original one, the first related to the consistency of the reduced lattice and the other to the descriptive losses incurred by the reduction. The JBOS approach was applied to two data sets from the UCI machine learning repository. The results show that it is possible to reduce the size of a concept lattice in a controlled way. In particular, it makes possible the use of FCA in a data set (formal context) for which that use was previously impossible.