Séminaire Francois Weber

Bonjour à tous,

Vous êtes cordialement invités à participer au 23eme séminaire du LATECE de la saison 2015/2016. Qui? Francois Weber , étudiant stagiaire au LATECE sous la direction de Petko Valtchev Quand? Mercredi 22 juin 2016 à 12:15 (11h45 pour la pizza) Où? PK-4210 Titre : Flake : Un algorithme efficace de fouille d’itemsets fermés et générateurs Résumé:

Un des problèmes classiques de la fouille de données est la recherche de règles d’association dans une base d’enregistrements de type transaction. Le Formal Concept Analysis (FCA) se prête naturellement à l’étude de ce problème dans le cadre d’une base de transactions classiques (ensembles de traits). En particulier, de nombreux travaux ont porté sur l’extraction d’itemsets fermés et/ou générateurs dans de telles bases, car leur rôle est fondamental dans la construction de familles compactes de règles d’associations (ayant la forme ‘générateur -> fermé’). Ils sont aussi le point de départ pour la construction du treillis de concepts, une structure d’abstraction conceptuelle qui s’est avérée utile dans de nombreuses applications pratiques en génie logiciel, recherche d’information, représentation de connaissances, etc.

L’algorithme Flake est destiné au calcul efficace de l’ensembles des fermés et de leurs générateurs associés. Il est motivé par un triple besoin :

* on souhaite calculer à la fois les fermés et les générateurs

* on souhaite savoir quels générateurs correspondent à quel fermé

* l’algorithme doit être, autant que possible, incrémental par rapport à l’ajout d’items, alias attributs, afin de pouvoir être utilisé dans le cadre d’un problème plus général qui est celui du calcul des fermés et générateurs d’une base de données relationnelle.

Flake étend un algorithme de la littérature, Talky-G, pour le calcul des générateurs en y incorporant des résultats structuraux avancés (sur les familles des générateurs représentatifs). Ainsi, il arrive à calculer graduellement de fermetures partielles durant la détection même desdits générateurs. Un post-traitement est néanmoins nécessaire pour achever le calcul de certains fermés. Les performances de l’algorithme sur des benchmarks du domaine sont prometteuses alors que son optimisation est encore en cours.

SLIDES

Comments are closed.