Search

National audience; Coron is a domain and platform independent, multi-purposed data mining toolkit, which incorporates not only a rich collection of data mining algorithms, but also allows a number of auxiliary operations. To the best of our knowledge, a data mining toolkit designed specifically for itemset extraction and association rule generation like Coron does not exist elsewhere. Coron also provides support for preparing and filtering data, and for interpreting the extracted units of knowledge.; Conçu à l'origine pour une étude de cohorte, Coron est devenu une plate-forme de fouille de données à part entière, qui incorpore une riche collection d'algorithmes pour l'extraction de motifs (fréquents, fermés, générateurs, etc.) et la génération de règles d'association à partir de données binaires, ainsi que divers outils de pré- et post- traitements.

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.

National audience; Un certain nombre de travaux en fouille de données se sont intéressés à l'extraction de motifs et à la génération de règles d'association à partir de ces motifs. Cependant, ces travaux se sont jusqu'à présent, centrés sur la notion de motifs fréquents. Le premier algorithme à avoir permis l'extraction de tous les motifs fréquents est Apriori mais d'autres ont été mis au point par la suite, certains n'extrayant que des sous-ensembles de ces motifs (motifs fermés fréquents, motifs fréquents maximaux, générateurs minimaux). Dans cet article, nous nous intéressons aux motifs rares qui peuvent également véhiculer des informations importantes. Les motifs rares correspondent au complémentaire des motifs fréquents. A notre connaissance, ces motifs n'ont pas encore été étudiés, malgré l'intérêt que certains domaines pourraient tirer de ce genre de modèle. C'est en particulier le cas de la médecine, où par exemple, il est important pour un praticien de repérer les symptômes non usuels ou les effets indésirables exceptionnels qui peuvent se déclarer chez un patient pour une pathologie ou un traitement donné.

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.

National audience; Les études en fouille de données se sont surtout intéressées jusqu'à présent à l'extraction de motifs fréquents et à la génération de règles d'association à partir des motifs fréquents. L'algorithme le plus célèbre ayant permis d'atteindre ces objectifs est Apriori, qui a été suivi par toute une famille d'algorithmes mis au point par la suite et possédant tous la caractéristique d'extraire l'ensemble des motifs fréquents ou un sous-ensemble de ces motifs (motifs fermés fréquents, motifs fréquents maximaux, générateurs minimaux). Dans cet article, nous posons le problème de la recherche des motifs rares ou non fréquents, qui se trouvent dans le complémentaire de l'ensemble des motifs fréquents. Ce type de motif n'a jamais vraiment fait l'objet d'une étude systématique, malgré l'intérêt et la demande existant dans certains domaines d'application. Ainsi, en biologie ou en médecine, il peut se révéler très important pour un praticien de repérer des symptômes non habituels ou des effets indésirables exceptionnels se déclarant chez un patient pour une pathologie ou un traitement donnés.

In this paper, we address the problem of generating relevant rare association rules. In the literature, this problem has not yet been studied in detail, although rare association rules can also contain important information just as frequent association rules do. Our work is motivated by the long-standing open question of devising an efficient algorithm for finding rules with low support and very high confidence. In order to find such rules using conventional frequent itemset mining algorithms like Apriori, the minimum support must be set very low, which drastically increases the runtime of the algorithm. Moreover, when minimum support is set very low, Apriori produces a huge number of frequent itemsets. This is also known as the "rare item problem". For this long-existing problem we propose a solution. A particularly relevant field for rare itemsets and rare association rules is medical diagnosis. For example it may be that in a large group of patients diagnosed with the same sickness, a few patients exhibit unusual symptoms. It is important for the doctor to take this fact into consideration.

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.

Colloque avec actes et comité de lecture. internationale.; International audience; In this paper we investigate the application of Galois (or concept) lattices on different data sources (e.g. web documents or bibliographical items) in order to organise knowledge that can be extracted from the data. This knowledge organisation can then be used for a number of purposes (e.g. knowledge management in an organisation, document retrieval on the Web, etc.). Galois lattices can be considered as classification tools for knowledge units in concept hierarchies that can be used within a knowledge-based system. Moreover, Galois lattices can be used in parallel with domain ontologies for building more precise and more concise concept ontologies, and for guiding the knowledge discovery process.

Colloque avec actes et comité de lecture. nationale.; National audience; Dans cet article, nous étudions la construction de treillis de Galois à partir de différentes sources d'information (par exemple des documents du Web ou des notices bibliographiques) afin d'organiser les connaissances qui peuvent en être extraites. L'organisation en treillis qui en résulte peut alors être utilisée pour satisfaire un certain nombre de buts, comme par exemple la gestion de la connaissance dans une organisation, la recherche documentaire sur le Web, etc. En outre, la classification par treillis peut également tirer parti d'une ontologie des propriétés du domaine considéré. Notre objectif global est de mettre en place un processus de classification par treillis pour enrichir une ontologie qui à son tour permet de guider le processus de découverte de connaissances dans les données.

Colloque avec actes sans comité de lecture. internationale.; International audience; This paper presents an ongoing research work on knowledge management. The problem is to be able to design a "multidimensional portfolio", in order to organize and to index the different aspects of knowledge in an enterprise. We have chosen an object-oriented view for such a representation. Every piece of knowledge is represented within classes in an object-based representation system. The multidimensional organization is supported by a number of tangled hierarchies of classes, one hierarchy giving a particular point of view on the enterprise knowledge.