|
Sur la fusion de treillis de concepts/Galois et de bases canoniques facteurs| old_uid | 3777 |
|---|
| title | Sur la fusion de treillis de concepts/Galois et de bases canoniques facteurs |
|---|
| start_date | 2008/01/10 |
|---|
| schedule | 10h |
|---|
| online | no |
|---|
| location_info | salle 549 |
|---|
| summary | L’analyse formelle de concepts (AFC) est une approche aux fondements algébriques pour l’analyse de données et pour la fouille de données. L’AFC structure les connaissances qui sont implicites dans des tableaux de données de type (objets x attributs), appelés contextes, de deux façons mutuellement complémentaires. D’une part, sont extraits les ensembles maximaux d’attributs partagés par des objets, alias les intents, organisés en un demi-treillis par l’inclusion. D’autre part, on construit la famille d’implications valides dans le contexte, c’est-à-dire, les pairs d’ensembles d’attributs explicitant les co-occurrences entre ces ensembles dans les objets du contexte. Plutôt que dans son intégralité, la famille des implications est manipulée à travers une base, dite canonique ou de Duquenne-Guigues, jouant un rôle identique aux couvertures minimales d’une famille de dépendances fonctionnelles en théorie des bases de données. Les tâches d’extraction des intents et de la base canonique à partir du contexte, toutes deux réputées comme problèmes difficiles, sont centraux pour l’algorithmique de l’AFC et de là pour la fouille de données basée sur l’AFC.
Dans cet exposé, nous les abordons à l’aide d’une approche diviser-pour-régner consistant à scinder les tableaux en fragments, d’analyser ceux-ci séparément, puis de fusionner les résultats. Le défi principal de cette entreprise réside dans la nature intrinsèquement séquentielle du calcul de la base canonique. Celle-ci force une approche en deux temps pour la fusion, fondée sur une étude préalable des structures intermédiaires d’implications, dites relatives, complétant les bases canoniques des fragments. Reflétant les “interactions” entre deux groupes complémentaires d’attributs du contexte, ces structures ont leur propre rôle dans une analyse de données ‘’par morceaux". Des algorithmes concrets pour le calcul en mode diviser-pour-régner seront présentés ainsi que des indications à propos de leur efficacité.
*) Ce travail est une collaboration avec V. Duquenne du CNRS |
|---|
| oncancel | salle inhabituelle |
|---|
| responsibles | Bouchon-Meunier, Diaz, Gallinari |
|---|
| |
|