1. Contribution to the study of interestingness measures for association rules and their algorithmic properties
- Author
-
Le Bras, Yannick, Le Bras, Yannick, Télécom Bretagne - Brest, Télécom Bretagne, Télécom Bretagne, Université de Bretagne-Sud, Philippe Lenca, and Stéphane Lallich
- Subjects
Data mining DM ,[INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB] ,[INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG] ,Association rules ,robustesse ,fouille de données ,[INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG] ,[INFO.INFO-IR]Computer Science [cs]/Information Retrieval [cs.IR] ,[INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB] ,règles d’association ,intérêt ,[INFO.INFO-IR] Computer Science [cs]/Information Retrieval [cs.IR] ,Robustness ,élagage ,algorithmes - Abstract
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é.
- Published
- 2011