The enumeration of pseudo-intents is a long-standing problem in which the order plays a major role. In this paper, we present newalgorithms that enumerate pseudo-intents in orders that do not necessarily respect the inclusion relation. We show that, confirming established results, this enumeration is equivalent to computing minimal transversals in hypergraphs a bounded number of times.
Keywords : Pseudo-Intents, Enumeration, Implications
Cette thèse traite du problème du calcul des implications, c’est-à-dire des régularités de la forme « quand il y a A, il y a B », dans des ensembles de données composés d’objets décrits par des attributs. Calculer toutes les implications peut être vu comme l’énumération d’ensembles d’attributs appelés pseudo-intensions. Nous savons que ces pseudo-intensions ne peuvent pas être énumérées avec un délai polynomial dans l’ordre lectique mais aucun résultat n’existe, à l’heure actuelle, pour d’autres ordres. Bien que certains algorithmes existants n’énumèrent pas forcément dans l’ordre lectique, aucun n’a un délai polynomial. Cette absence de connaissances sur les autres ordres autorise toujours l’existence d’un algorithme avec délai polynomial et le trouver serait une avancée utile et significative. Malheureusement, les algorithmes actuels ne nous autorisent pas à choisir l’ordre d’énumération, ce qui complique considérablement et inutilement l’étude de l’influence de l’ordre dans la complexité. C’est donc pour aller vers une meilleure compréhension du rôle de l’ordre dans l’énumération des pseudo-intensions que nous proposons un algorithme qui peut réaliser cette énumération dans n’importe quel ordre qui respecte la relation d’inclusion.
Dans la première partie, nous expliquons et étudions les propriétés de notre algorithme. Comme pour tout algorithme d’énumération, le principal problème est de construire tous les ensembles une seule fois. Nous proposons pour cela d’utiliser un arbre couvrant, lui-même basé sur l’ordre lectique, afin d’éviter de multiples constructions d’un même ensemble. L’utilisation de cet arbre couvrant au lieu de l’ordre lectique classique augmente la complexité spatiale mais offre plus de flexibilité dans l’ordre d’énumération. Nous montrons que, comparé à l’algorithme Next Closure bien connu, le nôtre effectue moins de fermetures logiques sur des contextes peu denses et plus de fermetures quand le nombre moyen d’attributs par objet dépasse 30% du total. La complexité spatiale de l’algorithme est aussi étudiée de façon empirique et il est montré que des ordres différents se comportent différemment, l’ordre lectique étant le plus efficace. Nous postulons que l’efficacité d’un ordre est fonction de sa distance à l’ordre utilisé dans le test de canonicité.
Dans la seconde partie, nous nous intéressons au calcul des implications dans un cadre plus complexe : les données relationnelles. Dans ces contextes, les objets sont représentés à la fois par des attributs et par des relations avec d’autres objets. Le besoin de représenter les informations sur les relations produit une augmente exponentielle du nombre d’attributs, ce qui rend les algorithmes classiques rapidement inutilisables. Nous proposons une modification de notre algorithme qui énumère les pseudo-intensions de contextes dans lesquels l’information relationnelle est représentée par des attributs. Nous fournissons une étude rapide du type d’information relationnelle qui peut être prise en compte. Nous utilisons l’exemple des logiques de description comme cadre pour l’expression des données relationnelles.
Dans la troisième partie, nous étendons notre travail au domaine plus général des règles d’association. Les règles d’association sont des régularités de la forme « quand il y a A, il y a B avec une certitude de x% ». Ainsi, les implications sont des règles d’association certaines. Notre algorithme calcule déjà une base pour les implications et nous proposons une très simple modification et montrons qu’elle lui permet de calculer la base de Luxenburger en plus de la base de Duquenne-Guigues. Cela permet à notre algorithme de calculer une base de cardinalité minimale pour les règles d’association.
This thesis deals with the problem of the computation of implications, which are regularities of the form « when there is A there is B », in datasets composed of objects described by attributes. Computing all the implications can be viewed as the enumeration of sets of attributes called pseudo-intents. It is known that pseudo-intents cannot be enumerated with a polynomial delay in the lectic order but no such result exists for other orders. While some current algorithms do not enumerate in the lectic order, none of them have a polynomial delay. The lack of knowledge on other orders leaves the possibility for a polynomial-delay algorithm to exist and finding it would be an important and useful step. Unfortunately, current algorithms do not allow us to choose the order so studying its influence on the complexity of the enumeration is harder than necessary. We thus take a first step towards a better understanding of the role of the order in the enumeration of pseudo-intents by providing an algorithm that can
enumerate pseudo-intents in any order that respects the inclusion relation.
In the first part, we explain and study the properties of our algorithm. As with all enumeration algorithms, the first problem is to construct all the sets only once. We propose to use a spanning tree, itself based on the lectic order, to avoid multiple constructions of a same set. The use of this spanning tree instead of the classic lectic order increases the space complexity but offers much more flexibility in the enumeration order. We show that, compared to the well-known Next Closure algorithm, ours performs less logical closures on sparse contexts and more once the average number of attributes per object exceeds 30%. The space complexity of the algorithm is also empirically studied and we show that different orders behave differently with the lectic order being the most efficient. We postulate that the efficiency of an order is function of its distance to the order used in the canonicity test.
In the second part, we take an interest in the computation of implications in a more complex setting : relational data. In these contexts, objects are represented by both attributes and binary relations with other objects. The need to represent relation information causes an exponential increase in the number of attributes so naive algorithms become unusable extremely fast. We propose a modification of our algorithm that enumerates the pseudo-intents of contexts in which relational information is represented by attributes. A quick study of the type of relational information that can be considered is provided. We use the example of description logics as a framework for expressing relational data.
In the third part, we extend our work to the more general domain of association rules. Association rules are regularities of the form « when there is A there is B with x% certainty » so implications are association rules with 100% certainty. Our algorithm already computes a basis for implications so we propose a very simple modification and demonstrate that it can compute the Luxenburger basis of a context along with the Duquenne-Guigues basis. This effectively allows our algorithm to compute a basis for association rules that is of minimal cardinality.
Description logic are a family of logic-based formalisms used to represent knowledge and eason on it. That knowledge, under the form of concepts and relationships between them called terminological axioms, is usually manually entered and used to describe objects in a given domain. That operation being tiresome, we would like to automatically learn those relationships from the set of instances using datamining techniques. In this paper, we study association rules mining in the description logic EL. First, we characterize the set of all possible concepts in a given EL language. Second, we use those characteristics to develop an algorithm using formal concept analysis to mine the rules more efficiently.
Keywords : Description Logics, Implications, Ontologies
The enumeration of all the pseudo-intents of a formal context is usually based on a linear order on attribute sets, the lectic order. We propose an algorithm that uses the lattice structure of the set of intents and pseudo-intents to compute the Duquenne-Guigues basis. We argue that this
method allows for efficient optimizations that reduce the required number of logical closures. We then show how it can be easily modified to also compute the Luxenburger basis.
Keywords : Pseudo-Intents, Enumeration, Implications