Resumen de Formal methods for mining structured objects
Gemma Casas Garriga
In the field of knowledge discovery, graphs of concepts are an expressive and versatile modeling technique that provides ways to reason about information implicit in a set of data, Interesting examples of this can be found under the classical ma\-the\-ma\-ti\-cal theory of Formal Concept Analysis, dedicated to construct a lattice of concepts by defining a Galois connection on a binary relationship. Here, we will consider the more complex case where data comes in a set of structured objects; e.g. a set of sequences, trees or even of graphs. As a natural step towards the general characterization, we first focus on the mining of sequential data and, for this case, we contribute with the formalization of a lattice of closed sets of sequences.
This lattice turns out to be an interesting combinatorial object from where to derive justified methods for current sequential mining problems.
The first set of results from the lattice focuses on the characterization of logical implications with order. We propose a notion of association rules and prove that they can be formally justified by a purely logical characterization, namely, a natural notion of empirical Horn approximation for ordered data, which involves background Horn conditions; these ensure the consistency of the propositional theory obtained with the ordered context.
We also discuss a general method to calculate these rules that can be easily incorporated into any algorithm of discovering closed sequential patterns.
The second set of results corresponds to the identification of partial order structures from the input sequences. The combinatorial nature of this problem makes the classical algorithmic solutions incur in a substantial overhead, thus, remaining it to be still a challenging task. Here we contribute by proving that the maximal paths of the closure of such partial orders can be derived from the closed sets of sequences of our lattice. This theoretical result allows for the con
