Stages Master 2 (2009) > Stage proposé n°5
Sujet Stage :
Implémentation et étude expérimentale d’un nouvel algorithme de calcul des générateurs minimaux
Résumé du travail proposé :
Nous avons récemment mis en place au sein du laboratoire un nouvel algorithme efficace de calcul des générateurs minimaux. L’objectif de ce stage sera de l’implémenter, puis d’en mener une étude expérimentale et comparative avec d’autres algorithmes.
Mots clés :
Générateurs minimaux ; Règles d’association ; Treillis ; Algorithme
Informations complémentaires :
Encadrants: Karell Bertet
Axe thématique : Données complexes, Images et Documents
Axe stratégique : Pertinence Contenu-Interaction
Cadre de coopération :
Date de début du stage : Avril 2011
Durée du contrat : 5 mois
Contexte de l’étude:
L’extraction de règles d’association est une technique importante dans le domaine de la fouille de données et de l’extraction de connaissances [1]. Pour des données qui s’organisent sous forme d’une table binaire objets x attributs, les règles d’association entre attributs permettent d’en décrire précisément les liens, et peuvent s’utiliser aussi bien dans un objectif de description, que dans un objectif de prédiction, ou de classification supervisée, lorsqu’un attribut de classe à prédire est présent. Les premiers algorithmes d’extraction de règles d’association, et notamment l’algorithme fondateur Apriori [2], souffrent de deux problèmes majeurs, à savoir le coût d’extraction, mais aussi la grande quantité de règles extraites qui les rend difficilement exploitables.
L’exploitation des fondements mathématiques de l’opérateur de fermeture porté par la table binaire des données, a permis le développement de nouvelles approches [3] qui proposent de réduire le coût d’extraction à partir des seuls fermés, dans le but de générer un sous-ensemble de règles d’association sans perte d’information, appelée base générique. Formellement, la base générique se définit par des règles composées d’un générateur minimal en prémisse. Outre leur utilisation dans des bases de règles génériques, les générateurs minimaux peuvent permettre de mettre en place des mécanismes d’indexation efficaces.
Description du sujet :
Nous avons au sein du laboratoire L3I proposé un nouvel algorithme d’extraction des générateurs minimaux d’un fermé dont la complexité théorique améliore celle des algorithmes existants. L’objectif de ce stage sera d’implémenter cet algorithme (langage Java), puis d’en mener une étude comparative avec les algorithmes existants.
Pré requis et contraintes particulières :
Prérequis scientifiques : formation informatique.
Prérequis techniques : fouille de données, Java
Références bibliographiques :
[1] M. J. A. Berry and G. S. Linoff. Data Mining Techniques : For Marketing, Sales, and Customer Relationship Management, Second Edition. Wiley Publishing, 2004.
[2] R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In J. B. Bocca, M. Jarke, an d C. Zaniolo, editors, Proceedings of the 20th Intl. Conference on Very Large Databases, Santiago, Chile, pages 478-499, June 1994.
[3] N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Efficient mining of association rules using closed itemset lattices. Journal of Information Systems, 24(1) :25-46, 1999.
[4] A. Le Floch and C. Fisette and R. Missaoui and P. Vatchev and R. Godin. Jen: un algorithme efficace de construction de générateurs minimaux pour l’identification de règles d’association. Nouvelles Technologies de l’Information (numéro spécial), 1(1) : 135-146, 2003.
Contacts – liens :
Email : karell.bertet univ-lr.fr