Search

As a whole, this thesis focuses on the quantitative and qualitative aspects of the search for association rules and proposes generalizations of classical approaches as well as innovative evaluation and extraction solutions both in the supervised case and in the unsupervised case., Le modèle des règles d’association bénéficie, de par ses nombreuses applications, d’une grande popularité en fouille de données pour la découverte de connaissances à partir de données toujours plus volumineuses. Deux défis principaux se posent, l’un algorithmique pour la génération, et l’autre qualitatif pour l’évaluation et la validation des règles d’association. Par ailleurs, le problème de décision sous-jacent est NP-complet. Les techniques classiques d’extraction procèdent généralement en deux phases. La première extrait des motifs sous une contrainte de fréquence, notamment grâce à une propriété d’antimonotonie, tandis que la seconde évalue et génère exhaustivement les règles à partir des motifs fréquents. Un grand nombre de mesure d’intérêt existent pour l’évaluation : ce travail s’appuie sur 42 d’entre elles. Dans ce contexte, nous définissons un cadre formel d’étude des règles d’association et des mesures, sur lequel nous nous appuyons pour étudier différentes propriétés qualitatives et algorithmiques des règles d’association. Dans un premier temps, nous étudions la notion de robustesse, très peu étudiée à ce jour dans le contexte des règles d’association. Nous proposons une mesure de robustesse permettant de quantifier la validité d’une règle étant donnée une mesure d’intérêt. Cette mesure exprime pour une règle donnée, de façon opérationnelle, une zone de sécurité garantissant l’intérêt de la règle. Dans un second temps, nous étudions l’extraction des règles, et plus précisément l’insertion de la phase d’évaluation au coeur des algorithmes. Nous étudions 3 propriétés algorithmiques de la littérature : bien qu’intéressantes, celles-ci sont limitées à un nombre restreint de mesures. Nous les généralisons et montrons des conditions nécessaires et/ou suffisantes d’existence pour les mesures. Finalement, dans le cadre des règles de classe, nous généralisons la notion d’antimonotonie. Nous proposons alors des propriétés algorithmiques pour un ensemble de mesures qui permettent d’inclure celles-ci dans la phase de recherche. Nous montrons que cette approche est particulièrement efficace, et énonçons une condition permettant de déterminer les mesures possédant une telle propriété. Dans son ensemble, ce travail de thèse étudie les aspects quantitatifs et qualitatifs de la recherche des règles d’association et propose des généralisations d’approches classiques ainsi que des solutions innovantes d’évaluation et d’extraction tant dans le cas supervisé que dans le cas non supervisé.

International audience; Many studies have shown the limits of the support/confidence framework used in APRIORI -like algorithms to mine association rules. There are a lot of efficient implementations based on the antimonotony property of the support, but candidate set generation (e.g., frequent item set mining) is still costly. In addition, many rules are uninteresting or redundant and one can miss interesting rules like nuggets. We are thus facing a complexity issue and a quality issue. One solution is to not use frequent itemset mining and to focus as soon as possible on interesting rules using additional interestingness measures. We present here a formal framework that allows us to make a link between analytic and algorithmic properties of interestingness measures. We introduce the notion of optimonotony in relation with the optimal rule discovery framework. We then demonstrate a necessary and sufficient condition for the existence of optimonotony. This result can thus be applied to classify the measures. We study the case of 39 classical measures and show that 31 of them are optimonotone. These optimonotone measures can thus be used with an underlying pruning strategy. Empirical evaluations show that the pruning strategy is efficient and leads tothe discovery of nuggets using an optimonotone measure and without the support constraint.

International audience; Association Rules Discovery is an increasing subdomain of Datamining. Many works have focused on the extraction and the evaluation of the association rules, leading to many technical improvments on the algorithms, and many different measures. But few number of them have tried to merge the both. We introduce here a formal framework for the study of association rules and interestingness measures that allows an analytic study of these objects. This framework is based on the contingency table of a rule and let us make a link between analytic properties of the measures and algorithmic properties. We give as example the case of three algorithmic properties for the extraction of association rules that were generalized and applied with the help of this framework. These properties allow a pruning of the search space based on a large number of measures and without any support constraint.

As a whole, this thesis focuses on the quantitative and qualitative aspects of the search for association rules and proposes generalizations of classical approaches as well as innovative evaluation and extraction solutions both in the supervised case and in the unsupervised case.; Le modèle des règles d’association bénéficie, de par ses nombreuses applications, d’une grande popularité en fouille de données pour la découverte de connaissances à partir de données toujours plus volumineuses. Deux défis principaux se posent, l’un algorithmique pour la génération, et l’autre qualitatif pour l’évaluation et la validation des règles d’association. Par ailleurs, le problème de décision sous-jacent est NP-complet. Les techniques classiques d’extraction procèdent généralement en deux phases. La première extrait des motifs sous une contrainte de fréquence, notamment grâce à une propriété d’antimonotonie, tandis que la seconde évalue et génère exhaustivement les règles à partir des motifs fréquents. Un grand nombre de mesure d’intérêt existent pour l’évaluation : ce travail s’appuie sur 42 d’entre elles. Dans ce contexte, nous définissons un cadre formel d’étude des règles d’association et des mesures, sur lequel nous nous appuyons pour étudier différentes propriétés qualitatives et algorithmiques des règles d’association. Dans un premier temps, nous étudions la notion de robustesse, très peu étudiée à ce jour dans le contexte des règles d’association. Nous proposons une mesure de robustesse permettant de quantifier la validité d’une règle étant donnée une mesure d’intérêt. Cette mesure exprime pour une règle donnée, de façon opérationnelle, une zone de sécurité garantissant l’intérêt de la règle. Dans un second temps, nous étudions l’extraction des règles, et plus précisément l’insertion de la phase d’évaluation au coeur des algorithmes. Nous étudions 3 propriétés algorithmiques de la littérature : bien qu’intéressantes, celles-ci sont limitées à un nombre restreint de mesures. Nous les généralisons et montrons des conditions nécessaires et/ou suffisantes d’existence pour les mesures. Finalement, dans le cadre des règles de classe, nous généralisons la notion d’antimonotonie. Nous proposons alors des propriétés algorithmiques pour un ensemble de mesures qui permettent d’inclure celles-ci dans la phase de recherche. Nous montrons que cette approche est particulièrement efficace, et énonçons une condition permettant de déterminer les mesures possédant une telle propriété. Dans son ensemble, ce travail de thèse étudie les aspects quantitatifs et qualitatifs de la recherche des règles d’association et propose des généralisations d’approches classiques ainsi que des solutions innovantes d’évaluation et d’extraction tant dans le cas supervisé que dans le cas non supervisé.

International audience; Many studies have shown the limits of support/confidence framework used in Apriori-like algorithms to mine association rules. There are a lot of efficient implementations based on the antimonotony property of the support but candidate set generation is still costly. In addition many rules are uninteresting or redundant and one can miss interesting rules like nuggets. One solution is to get rid of frequent itemset mining and to focus as soon as possible on interesting rules. For that purpose algorithmic properties were first studied, especially for the confidence. They allow all confidence rules to be found without a preliminary support pruning. More recently, in the case of class association rules, the concept of optimal rules gave a pruning strategy compatible with more measures. However, all these properties have been demonstrated for a limited number of interestingness measures. We present a new formal framework which allows us to make the link between analytic and algorithmic properties of the measures. We apply this framework to optimal rules, and we demonstrate a necessary and sufficient condition of existence for this pruning strategy, which can be applied to any measure.