Catálogo de publicaciones - libros

Galois connections can be defined for lattices and for ordered sets. We discuss a rather wide generalisation, which was introduced by Weiqun Xia and has been reinvented under different names: Relational Galois connections between relations. It turns out that the generalised notion is of importance for the original one and can be utilised, e.g., for computing Galois connections.

The present paper may be understood as an attempt to bring together ideas of Wille [15], Xia [16], Domenach and Leclerc [3], and others and to suggest a unifying language.

has been introduced as the theory of semantic structures and their connections which, in particular, covers the methodology of activating semantic structures for . It is the main aim of this paper to explain and demonstrate that semantic structures are in fact basic for which comprises activities such as representing, infering, acquiring, and communicating conceptual knowledge.

Different rule semantics have been successively defined in many contexts such as implications in artificial intelligence, functional dependencies in databases or association rules in data mining. We are interested in defining on tabular datasets a class of rule semantics for which Armstrong’s axioms are sound and complete, so-called . The main contribution of this paper is to show that an does exist between some syntactic restrictions on the natural definition of a given semantics and the fact that this semantics is well-formed. From a practical point of view, this equivalence allows to prove easily whether or not a new semantics is well-formed. We also point out the relationship between our generic definition of rule satisfaction and the underlying data mining problem, i.e. given a well-formed semantics and a tabular dataset, discover a cover of rules satisfied in this dataset. This work takes its roots from a bioinformatics application, the discovery of gene regulatory networks from gene expression data.

Recent advances in data and knowledge engineering have emphasized the need for formal concept analysis () tools taking into account structured data. There are a few adaptations of the classical methodology for handling contexts holding on complex data formats, e.g. graph-based or relational data. In this paper, relational concept analysis () is proposed, as an adaptation of for analyzing objects described both by binary and relational attributes. The process takes as input a collection of contexts and of inter-context relations, and yields a set of lattices, one per context, whose concepts are linked by relations. Moreover, a way of representing the concepts and relations extracted with is proposed in the framework of a description logic. The process has been implemented within the platform, offering new and efficient tools for knowledge and software engineering.

We model a Digital Library as a formal context in which objects are documents and attributes are terms describing documents contents. A formal concept is very close to the notion of a collection: the concept extent is the extension of the collection; the concept intent consists of a set of terms, the collection intension. The collection intension can be viewed as a simple conjunctive query which evaluates precisely to the extension. However, for certain collections no concept may exist, in which case the concept that best approximates the extension must be used. In so doing, we may end up with a too imprecise concept, in case too many documents denoted by the intension are outside the extension. We then look for a more precise intension by exploring 3 different query languages: conjunctive queries with negation; disjunctions of negation-free conjunctive queries; and disjunctions of conjunctive queries with negation. We show that a precise description can always be found in one of these languages for any set of documents. However, when disjunction is introduced, uniqueness of the solution is lost. In order to deal with this problem, we define a preferential criterion on queries, based on the conciseness of their expression. We then show that minimal queries are hard to find in the last 2 of the three languages above.

This paper investigates the scalability of applying Formal Concept Analysis to large data sets. In particular we present enhancements based on an existing spatial data structure, the RD-Tree, to better support both specific use with Formal Concept Analysis as well as generic multidimensional applications. Our experiments are motivated by the application of Formal Concept Analysis to a virtual filesystem [11,20,16]. In particular the libferris [1] Semantic File System.

Strings are an important part of most real application multi-valued contexts. Their conceptual treatment requires the definition of , i.e., sets of relevant substrings, so as to form informative concepts. However these scales are either defined by hand, or derived in a context-unaware manner (e.g., all words occuring in string values). We present an efficient algorithm based on suffix trees that produces complete and concise substring scales. Completeness ensures that every possible concept is formed, like when considering the scale of all substrings. Conciseness ensures the number of scale attributes (substrings) is less than the cumulated size of all string values. This algorithm is integrated in Camelis, and illustrated on the set of all ICCS paper titles.

Formal Concept Analysis (FCA) is a natural framework for learning from positive and negative examples. Indeed, learning from examples results in sets of frequent concepts whose extent contains only these examples. In terms of association rules, the above learning strategy can be seen as searching the premises of exact rules where the consequence is fixed. In its most classical setting, FCA considers attributes as a non-ordered set. When attributes of the context are ordered, Conceptual Scaling allows the related taxonomy to be taken into account by producing a context completed with all attributes deduced from the taxonomy. The drawback, however, is that concept intents contain redundant information. In this article, we propose a parameterized generalization of a previously proposed algorithm, in order to learn rules in the presence of a taxonomy. The taxonomy is taken into account during the computation so as to remove all redundancies from intents. Simply changing one component, this parameterized algorithm can compute various kinds of concept-based rules. We present instantiations of the parameterized algorithm for learning positive and negative rules.

Minimal generators (s), minimal keys, play an important role in many theoretical and practical problem settings involving closure systems that originate in graph theory, relational database design, data mining, etc. As minima of the equivalence classes associated to closures, s underlie many compressed representations: For instance, they form premises in implication/association rules – with closures as conclusions – that losslessly represent the entire rule family of a closure system. However, s often show an intra-class combinatorial redundancy that makes an exhaustive storage and use impractical. In this respect, the () recently introduced by Dong is a first step towards a lossless reduction of this redundancy. However, as shown elsewhere, some of the claims about , , its invariant size and lossless nature, do not hold. As a remedy, we propose here a new succinct family which restores the losslessness by adding few further elements to the core, while theoretically grounding the whole. Computing means for the new family are presented together with the empirical evidences about its relative size the entire family and similar structures from the literature.

Pseudo-intents (also called pseudo-closed sets) of formal contexts have gained interest in recent years, since this notion is helpful for finding minimal representations of implicational theories. In particular, there are some open problems regarding complexity. In our paper, we compile some results about pseudo-intents which contribute to the understanding of this notion and help in designing optimized algorithms. We provide a characterization of pseudo-intents based on the notion of a formal context’s incrementors. The latter are essentially non-closed sets which – when added to a closure system – do not enforce the presence of other new attribute sets. In particular, the provided definition is non recursive. Moreover we show that this notion coincides with the notion of a quasi-closed set that is not closed, which enables to reuse existing results and to formulate an algorithm that checks for pseudo-closedness. Later on, we provide an approach for further optimizing those algorithms based on a result which correlates the set of pseudo-intents of a formal context with the pseudo-intents of this context’s reduced version.