Catálogo de publicaciones - libros

Functional dependencies, a notion originated in Relational Database Theory, are known to admit interesting characterizations in terms of Formal Concept Analysis. In database terms, two successive, natural extensions of the notion of functional dependency are the so-called degenerate multivalued dependencies, and multivalued dependencies proper. We propose here a new Galois connection, based on any given relation, which gives rise to a formal concept lattice corresponding precisely to the degenerate multivalued dependencies that hold in the relation given. The general form of the construction departs significantly from the most usual way of handling functional dependencies. Then, we extend our approach so as to extract Armstrong relations for the degenerate multivalued dependencies from the concept lattice obtained; the proof of the correctness of this construction is nontrivial.

An important topic in formal concept analysis is to cope with a possibly large number of formal concepts extracted from formal context (input data). We propose a method to reduce the number of extracted formal concepts by means of constraints expressed by particular formulas (attribute-dependency formulas, ADF). ADF represent a form of dependencies specified by a user expressing relative importance of attributes. ADF are considered as additional input accompanying the formal context 〈, , 〉. The reduction consists in considering formal concepts which are compatible with a given set of ADF and leaving out noncompatible concepts. We present basic properties related to ADF, an algorithm for generating the reduced set of formal concepts, and demonstrating examples.

Minimal generators (or ) constitute a remarkable part of the closure space landscape since they are the antipodes of the closures, i.e., minimal sets in the underlying equivalence relation over the powerset of the ground set. As such, they appear in both theoretical and practical problem settings related to closures that stem from fields as diverging as graph theory, database design and data mining. In FCA, though, they have been almost ignored, a fact that has motivated our long-term study of the underlying structures under different perspectives. This paper is a two-fold contribution to the study of mingen families associated to a context or, equivalently, a closure space. On the one hand, it sheds light on the evolution of the family upon increases in the context attribute set (e.g., for purposes of interactive data exploration). On the other hand, it proposes a novel method for computing the mingen family that, although based on incremental lattice construction, is intended to be run in a batch mode. Theoretical and empirical evidence witnessing the potential of our approach is provided.

Galois sub-hierarchies have been introduced as an interesting polynomial-size sub-order of a concept lattice, with useful applications. We present an algorithm which, given a context, efficiently computes an ordered partition which corresponds to a linear extension of this sub-hierarchy.

In this paper we propose a “divide and conquer” based generating algorithm for closed sets of a binary relation. We show that some existing algorithms are particular instances of our algorithm. This allows us to compare those algorithms and exhibit that the practical efficiency relies on the number of invalid closed sets generated. This number strongly depends on a choice function and the structure of the lattice. We exhibit a class of lattices for which no invalid closed sets are generated and thus reduce time complexity for such lattices. We made several tests which illustrate the impact of the choice function in practical efficiency.

Mannila and Räihä [5] have shown that minimum implicational bases can have an exponential number of implications. Aim of our paper is to understand how and why this combinatorial explosion arises and to propose mechanisms which reduce it.

The construction of the concept lattice of a context is a time consuming process. However, in many practical cases where FCA has proven to provide theoretical strength, e.g., in data mining, the volume of data to analyze is huge. This fact emphasizes the need for efficient lattice manipulations. The processing of large datasets has often been approached with parallel algorithms and some preliminary studies on parallel lattice construction exist in the literature. We propose here a novel divide-and-conquer (D&C) approach that operates by data slicing. In this paper, we present a new parallel algorithm, called , which borrows its main operating primitives from an existing sequential procedure and integrates them into a multi-process architecture. The algorithm has been implemented using a parallel dialect of the ++ language and its practical performances have been compared to those of a homologue sequential algorithm.

Automated layout of line diagrams for concept lattices is a hard problem as it requires not only asthetical but also semantic considerations. While many layout approaches have been proposed to produce line diagrams that are perceived as good for many applications, a general approach that suits all applications has not yet been found. Instead of proposing another specific layout approach we propose a framework that allows modelling layout constraints that are not only applied for automated layout, but also during manipulation of the diagram layout.

In formal concept analysis of data with fuzzy attributes, both the extent and the intent of a formal (fuzzy) concept may be fuzzy sets. In this paper we focus on so-called crisply generated formal concepts. A concept is crisply generated if = (and so = ) for some crisp (i.e., ordinary) set ⊆ of attributes (generator). Considering only crisply generated concepts has two practical consequences. First, the number of crisply generated formal concepts is considerably less than the number of all formal fuzzy concepts. Second, since crisply generated concepts may be identified with a (ordinary, not fuzzy) set of attributes (the largest generator), they might be considered “the important ones” among all formal fuzzy concepts. We present basic properties of the set of all crisply generated concepts, an algorithm for listing all crisply generated concepts, a version of the main theorem of concept lattices for crisply generated concepts, and show that crisply generated concepts are just the fixed points of pairs of mappings resembling Galois connections. Furthermore, we show connections to other papers on formal concept analysis of data with fuzzy attributes. Also, we present examples demonstrating the reduction of the number of formal concepts and the speed-up of our algorithm (compared to listing of all formal concepts and testing whether a concept is crisply generated).