Search

International audience; Rare association rules correspond to rare, or infrequent, itemsets, as opposed to frequent ones that are targeted by conventional pattern miners. Rare rules reflect regularities of local, rather than global, scope that can nevertheless provide valuable insights to an expert, especially in areas such as genetics and medical diagnosis where some specific deviations/illnesses occur only in a small number of cases. The work presented here is motivated by the long-standing open question of efficiently mining strong rare rules, i.e., rules with high confidence and low support. We also propose an efficient solution for finding the set of minimal rare itemsets. This set serves as a basis for generating rare association rules.

The effective construction of many association rule bases require the computation of both frequent closed and frequent generator itemsets (FCIs/FGs). However, these two tasks are rarely combined. Most of the existing solutions apply levelwise breadth-first traversal, though depth-first traversal is knowingly superior. Hence, we address here the depth-first FCI/FG-mining. The proposed algorithm, Touch, deals with both tasks separately, i.e., uses a well-known vertical method, Charm, to extract FCIs and a novel one called Talky-G, to extract FGs. The respective outputs are matched in a post-processing step. Experimental results indicate that Touch is highly efficient and outperforms its levelwise competitors.

The effective construction of many association rule bases require the computation of frequent closures, generators, and precedence links between closures. However, these tasks are rarely combined, and no scalable algorithm exists at present for their joint computation. We propose here a method that solves this challenging problem in two separated steps. First, we introduce a new algorithm called Touch for finding frequent closed itemsets (FCIs) and their generators (FGs). Touch applies depth-first traversal, and experimental results indicate that this algorithm is highly efficient and outperforms its levelwise competitors. Second, we propose another algorithm called Snow for extracting efficiently the precedence from the output of Touch. To do so, we apply hypergraph theory. Snow is a generic algorithm that can be used with any FCI/FG-miner. The two algorithms, Touch and Snow, provide a complete solution for constructing iceberg lattices. Furthermore, due to their modular design, parts of the algorithms can also be used independently.

I have implemented all the algorithms presented in my thesis in a unified software platform called Coron. The software is available at http://coron.loria.fr/ .; The main topic of this thesis is knowledge discovery in databases (KDD). More precisely, we have investigated two of the most important tasks of KDD today, namely itemset extraction and association rule generation. Throughout our work we have borne in mind that our goal is to find interesting association rules from various points of view: for efficient mining purposes, for minimizing the set of extracted rules and for finding intelligible (and easily interpretable) knowledge units. We have developed and adapted specific algorithms in order to achieve this goal. The main contributions of this thesis are: (1) We have developed and adapted algorithms for finding minimal non-redundant association rules; (2) We have defined a new basis for association rules called Closed Rules; (3) We have investigated an important but relatively unexplored field of KDD namely the extraction of rare itemsets and rare association rules; (4) We have packaged our algorithms and a collection of other algorithms along with other auxiliary operations for KDD into a unified software toolkit called Coron.; Le sujet principal de cette thèse est l'extraction de connaissances dans les bases de données (ECBD). Plus précisément, nous avons étudié deux des plus importantes tâches d'ECBD actuelles, qui sont l'extraction de motifs et la génération de règles d'association. Tout au long de notre travail, notre objectif a été de trouver des règles d'associations intéressantes selon plusieurs points de vue : dans un but de fouille efficace, pour réduire au minimum l'ensemble des règles extraites et pour trouver des unités de connaissances intelligibles (et facilement interprétables). Pour atteindre ce but, nous avons développé et adapté des algorithmes spécifiques. Les contributions principales de cette thèse sont : (1) nous avons développé et adapté des algorithmes pour trouver les règles d'association minimales non-redondantes ; (2) nous avons défini une nouvelle base pour les règles d'associations appelée “règles fermées” ; (3) nous avons étudié un champ de l'ECBD important mais relativement peu étudié, à savoir l'extraction des motifs rares et des règles d'association rares ; (4) nous avons regroupé nos algorithmes et une collection d'autres algorithmes ainsi que d'autres opérations auxiliaires d'ECBD dans une boîte à outils logicielle appelée Coron.

I have implemented all the algorithms presented in my thesis in a unified software platform called Coron. The software is available at http://coron.loria.fr/ .; The main topic of this thesis is knowledge discovery in databases (KDD). More precisely, we have investigated two of the most important tasks of KDD today, namely itemset extraction and association rule generation. Throughout our work we have borne in mind that our goal is to find interesting association rules from various points of view: for efficient mining purposes, for minimizing the set of extracted rules and for finding intelligible (and easily interpretable) knowledge units. We have developed and adapted specific algorithms in order to achieve this goal. The main contributions of this thesis are: (1) We have developed and adapted algorithms for finding minimal non-redundant association rules; (2) We have defined a new basis for association rules called Closed Rules; (3) We have investigated an important but relatively unexplored field of KDD namely the extraction of rare itemsets and rare association rules; (4) We have packaged our algorithms and a collection of other algorithms along with other auxiliary operations for KDD into a unified software toolkit called Coron.; Le sujet principal de cette thèse est l'extraction de connaissances dans les bases de données (ECBD). Plus précisément, nous avons étudié deux des plus importantes tâches d'ECBD actuelles, qui sont l'extraction de motifs et la génération de règles d'association. Tout au long de notre travail, notre objectif a été de trouver des règles d'associations intéressantes selon plusieurs points de vue : dans un but de fouille efficace, pour réduire au minimum l'ensemble des règles extraites et pour trouver des unités de connaissances intelligibles (et facilement interprétables). Pour atteindre ce but, nous avons développé et adapté des algorithmes spécifiques. Les contributions principales de cette thèse sont : (1) nous avons développé et adapté des algorithmes pour trouver les règles d'association minimales non-redondantes ; (2) nous avons défini une nouvelle base pour les règles d'associations appelée “règles fermées” ; (3) nous avons étudié un champ de l'ECBD important mais relativement peu étudié, à savoir l'extraction des motifs rares et des règles d'association rares ; (4) nous avons regroupé nos algorithmes et une collection d'autres algorithmes ainsi que d'autres opérations auxiliaires d'ECBD dans une boîte à outils logicielle appelée Coron.

Site de la conférence : http://www.lirmm.fr/cla07/; International audience; In this paper, we present and detail a multifunctional itemset mining algorithm called Zart, which is based on the Pascal algorithm. Zart shows a number of additional features and performs the following, usually independent, tasks: identify frequent closed itemsets and associate generators to their closures. This makes Zart a complete algorithm for computing classes of itemsets including generators and closed itemsets. These characteristics allow one to extract minimal non-redundant association rules, a useful and lossless representation of association rules. In addition, being based on the Pascal algorithm, Zart has a rather efficient behavior on weakly and strongly correlated data. Accordingly, Zart is at the heart of the Coron platform, which is a domain independent, multi-purposed data mining platform, incorporating a rich collection of data mining algorithms.

CORON is a framework for levelwise algorithms that are designed to find frequent and/or frequent closed itemsets in binary contexts. Datasets can be very different in size, number of objects, number of attributes, density, etc. As there is no one best algorithm for arbitrary datasets, we want to give a possibility for users to try different algorithms and choose the one that best suits their needs.