From Implicational Systems to Direct-Optimal Bases: A Logic-Based Paradigm Shift

Abstract

Due to its solid mathematical foundations, Formal Concept Analysis (FCA) has become an emergent topic in the area of data analysis and knowledge discovering. Information is represented in a binary table defining a relation between a set of objects and a set of attributes—the formal context. The knowledge extracted from the formal context allows to identify useful patterns in data in different forms. One very useful knowledge representation in FCA are implications among attributes which are validated over the objects. The most outstanding feature of implications is that they can be managed by means of inference systems. Equivalent sets of implications can be obtained using different logic-based transformations. The aim of these transformations is to turn the original set of implications into an equivalent one fulfilling some desired properties. Among them, the directness and optimality are very popular targets because getting a direct-optimal basis ensures that the closure of a set of attributes may be computed with lower cost (time and resources). In this work, we introduce a new method to compute the direct-optimal basis which improves the existing ones. The new method reduces the input in a first stage and is guided by the idea of limiting the growth of the intermediate sets of implications as a way to improve the performance. We illustrate the good features of the new method with both a detailed example and by experimental evaluation