101
Revue des Nouvelles Technologies de l’Information Sous la direction de Djamel A. Zighed et Gilles Venturini RNTI-E-5 Extraction des connaissances : Etat et perspectives Rédacteurs invités : Florence Cloppet (Laboratoire CRIP5-SIP, Université René Descartes, Paris) Jean-Marc Petit (Laboratoire LIMOS, Université Blaise Pascal, Clermont-Fd) Nicole Vincent (Laboratoire CRIP5-SIP, Université René Descartes, Paris) CÉPADUÈS-ÉDITIONS 111, rue Vauquelin 31100 TOULOUSE – France Tél. : 05 61 40 57 36 – Fax : 05 61 41 79 89 (de l’étranger ) + 33 5 61 40 57 36 – Fax : + 33 5 61 41 79 89 www.cepadues.com courriel : [email protected]

Egc05 atelier rnti-e-5_(extraits)

  • Upload
    sinfst

  • View
    1.083

  • Download
    1

Embed Size (px)

DESCRIPTION

 

Citation preview

Page 1: Egc05 atelier rnti-e-5_(extraits)

Revue des Nouvelles Technologies de l’InformationSous la direction de Djamel A. Zighed et Gilles Venturini

RNTI-E-5

Extraction des connaissances :Etat et perspectives

Rédacteurs invités :Florence Cloppet

(Laboratoire CRIP5-SIP, Université René Descartes, Paris)Jean-Marc Petit

(Laboratoire LIMOS, Université Blaise Pascal, Clermont-Fd)Nicole Vincent

(Laboratoire CRIP5-SIP, Université René Descartes, Paris)

CÉPADUÈS-ÉDITIONS111, rue Vauquelin

31100 TOULOUSE – FranceTél. : 05 61 40 57 36 – Fax : 05 61 41 79 89

(de l’étranger ) + 33 5 61 40 57 36 – Fax : + 33 5 61 41 79 89www.cepadues.com

courriel : [email protected]

Page 2: Egc05 atelier rnti-e-5_(extraits)

© CEPAD 2005

Dépôt légal : novembre 2005

ISBN : 2.85428.707.X

Le code de la propriété intellectuelle du 1er juillet 1992 interdit expressément la photocopie à usage collectif sans autorisation des ayants droit. Or, cette pratique en se généralisant provoquerait une baisse brutale des achats de livres, au point que la possibilité même pour les auteurs de créer des œuvres nouvelles et de les faire éditer correctement serait alors menacée.

Nous rappelons donc que toute reproduction, partielle ou totale, du présent ouvrage est interdite sans autorisation de l'éditeur ou du Centre français d'exploitation du droit de copie (CFC – 3, rue d'Hautefeuille – 75006 Paris).

N° éditeur : 707

Chez le même éditeur

RNTI-Revue des Nouvelles Technologies de l'InformationSous la direction de Djamel A. Zighed et Gilles Venturini

n°1 : Entreposage fouille de donnéesE1 : Mesures de qualité pour la fouille de données

E2 : Extraction et gestion des connaissances EGC 2004C1 : Classification et fouille de données

E3 : Extraction et gestion des connaissances EGC 2005B1 : 1re Journée Francophone sur les Entrepôts de Données

et l’Analyse en ligne EDA 2005E4 : Fouille de données complexes

Page 3: Egc05 atelier rnti-e-5_(extraits)

iii

LE MOT DES DIRECTEURS DE LA COLLECTION RNTI

Nous avons le plaisir de vous présenter ce nouveau numéro de la Revue des Nouvelles Technologies de l'Information qui va vous faire connaître le fruit des ateliers de la conférence EGC’2005. De nombreux travaux de grande qualité présentés lors de ces ateliers méritaient d’avoir leur place dans RNTI, et c’est maintenant chose faite grâce au travail des rédacteurs invités et au soutien de l’association EGC. A l'image de ce numéro, nous vous rappelons que les thématiques générales couvertes par RNTI concernent tous les domaines liés à l'Extraction de connaissances à partir des Données (ECD), la Fouille de données (FD), la Gestion des connaissances (GC). Afin de mieux distinguer les différentes thématiques de RNTI, nous avons défini les appellations spécifiques suivantes :

§ RNTI - A : Apprentissage § RNTI - B : Bases de données § RNTI - C : Classification § RNTI - E : Extraction et Gestion des Connaissances § RNTI - S : Statistiques § RNTI - W : Web

RNTI a pour objectif d'être un outil de communication de très grande qualité et ouvert à tous. Nous vous rappelons également que deux types de numéros sont publiés dans RNTI :

§ des actes de conférences sélectives garantissant une haute qualité des articles (par exemple, nous demandons à ce que trois relecteurs émettent un avis sur les articles soumis),

§ des numéros à thème faisant l'objet d'un appel à communication. Chaque numéro à thème est édité par un ou plusieurs rédacteurs en chef invités. Un comité de programme spécifique d'une quinzaine de personnes est formé à cette occasion.

Nous sommes à votre écoute pour toute proposition de numéros spéciaux. Les thématiques abordées sont susceptibles également à moyen terme d'être élargies à d'autres domaines connexes. Nous espérons vivement que ce numéro vous donnera à tous une entière satisfaction. Pour tout renseignement, nous vous invitons à consulter notre site Web et à nous contacter. Djamel A. Zighed et Gilles Venturini. http://www.antsearch.univ-tours.fr/rnti

Page 4: Egc05 atelier rnti-e-5_(extraits)
Page 5: Egc05 atelier rnti-e-5_(extraits)

v

PREFACE

Les journées francophones EGC’2005 se sont tenues à Paris du 18 au 21 janvier et ont remporté un grand succès. La journée du 18 janvier était consacrée aux ateliers et aux cours. Une partie importante du succès de la conférence EGC a résidé dans la grande attractivité des ateliers qui ont réuni plus de 200 personnes sur des sujets très variés dont le point commun était l’extraction et la gestion des connaissances. En outre, ces rencontres ont permis des échanges fructueux, voire ont favorisé l’émergence de nouvelles problématiques.

Dans ce contexte, il a donc semblé tout à fait opportun à l’association EGC de valoriser le travail des organisateurs des douze ateliers et les articles des participants qui ont contribué au succès de ces ateliers. Le présent ouvrage est le fruit de ces réflexions. Il a été constitué à partir des actes informels qui ont été distribués le jour des ateliers. L’intérêt de l’ouvrage réside en partie dans la réactivité que nous avons eue pour assurer sa publication. Chaque atelier est représenté par un chapitre dans l’ouvrage, les responsables d’ateliers rédigeant une introduction à chaque chapitre. De manière à assurer la meilleure qualité possible de l’ouvrage, un processus de relecture a été entrepris et une évaluation globale des différents papiers a été proposée par chaque responsable d’ateliers aux éditeurs de l’ouvrage. Il va de soi qu’il ne s’agissait pas d’accepter de nouveaux papiers, plutôt d’amener les auteurs à consolider leur article à la lumière des discussions qui ont pu intervenir pendant l’atelier. Que soient ici remerciés chaleureusement pour leur travail et leur coopération les organisateurs des ateliers ainsi que les membres des comités de lecture impliqués dans l’ouvrage. Enfin, la réalisation de cet ouvrage n’aurait pas été possible sans le très fort soutien de l’association EGC. A titre d’exemple, cet ouvrage a été distribué gratuitement aux participants des ateliers, aux frais de l’association EGC.

Florence Cloppet (Université René Descartes, Paris) Jean-Marc Petit (Université Blaise Pascal, Clermont-Fd) Nicole Vincent (Université René Descartes, Paris)

Page 6: Egc05 atelier rnti-e-5_(extraits)
Page 7: Egc05 atelier rnti-e-5_(extraits)

vii

TABLE DES MATIÈRES

Table des matières

Partie I : Modélisation ...................................................................................................1 Chapitre 1 : Modélisation des connaissances...............................................................3 Une nouvelle méthode graphique pour interroger et vérifier des diagrammes de classes UML Thomas Raimbault............................................................................................................7 Transformation des concepts du diagramme de classe UML en OWL full Macaire Ahlonsou, Emmanuel Blanchard, Henri Briand, Fabrice Guillet....................13 Modéliser des connaissances ontologiques dans le cadre du modèle des Graphes Conceptuels Frédéric Fürst................................................................................................................19 Cartes cognitives de graphes conceptuels David Genest, Stéphane Loiseau....................................................................................25 Modélisation des connaissances émotionnelles par les cartes cognitives floues Nathalie Ronarc’h, Gaële Rozec, Fabrice Guillet, Alexis Nédélec, Serge Baquedano, Vincent Philippé.........................................................................................31 Logique Floue appliquée à l’inférence du « Risque Inhérent » en audit financier Souhir Fendri-Kharrat, Hassouna Fedhila, Pierre-Yves Glorennec..............................37 Méthode sémantique pour la classification et l’interrogation de sources de données biologiques Nizar Messai, Marie-Dominique Devignes, Amedeo Napoli, Malika Smaïl-Tabbone..........................................................................................................................43 Chapitre 2 : Modèles graphiques probabilistes pour la modélisation des connaissances : inférence, apprentissage et applications ..........................................49 Modèles de Markov cachés pour l’estimation de plusieurs fréquences fondamentales Francis Bach, Michael I. Jordan....................................................................................53 Inférence dans les HMM hiérarchiques et factorisés : changement de représentation vers le formalisme des Réseaux Bayésiens. Sylvain Gelly, Nicolas Bredeche, Michèle Sebag...........................................................57

Page 8: Egc05 atelier rnti-e-5_(extraits)

viii

Représentation et reconnaissance de caractères manuscrits par Réseaux Bayésiens Dynamiques Laurence Likforman-Sulem, Marc Sigelle......................................................................61 Les Réseaux Bayésiens versus d’autres modèles probabilistes pour le diagnostic multiple de gros systèmes Véronique Delcroix, Mohamed-Amine Maalej, Sylvain Piechowiak..............................65 Réseaux bayésiens pour le filtrage d’alarmes dans les systèmes de détection d’intrusions Ahmad Faour, Philippe Leray, Cédric Foll....................................................................69 Causal Inference in Multi-Agent Causal Models Sam Maes, Stijn Meganck, Bernard Manderick.............................................................73 Réseaux Bayésiens de Niveau Deux et D-Séparation Linda Smail, Jean-Pierre Raoult....................................................................................77 Chapitre 3 : Modélisation d’utilisateurs et Personnalisation de l’Interaction Homme-Machine..........................................................................................................81 Représentation contextualisée des pratiques des utilisateurs Patrick Brézillon, Charles Tijus.....................................................................................83 Modélisation Sémantique de l’Utilisateur Charles Tijus, Sébastien Poitrenaud, Jean-François Richard.......................................89 Une plate-forme de personnalisation basée sur une architecture multi-agents Abdouroihamane Anli, Emmanuelle Grislin-Le Strugeon, Mourad Abed......................95 Réflexions sur l'apport de l'exploration des traces d'usage pour améliorer le tri des résultats des moteurs de recherche sur le Web Rushed Kanawati..........................................................................................................101 Services contextualisés pour utilisateurs et la modélisation des utilisateurs à base d’ontologies : défis et perspectives Liana Razmerita...........................................................................................................107 De l’importance du pré-traitement des données pour l’utilisation de l’inférence grammaticale en Web Usage Mining Thierry Murge..............................................................................................................113 Mesure d’audience sur Internet par populations de fourmis artificielles Nicolas Labroche..........................................................................................................119

Page 9: Egc05 atelier rnti-e-5_(extraits)

ix

Apprentissage d’une hiérarchie de concepts pou la conception de modèles de domaine d’hypermédias Hermine Njike Fotzo, Thierry Artières, Patrick Gallinari, Julien Blanchard, Guillaume Letellier.......................................................................................................125 Partie II : Extraction de connaissance et Web ........................................................131 Chapitre 4 : Métadonnées et Adaptabilité pour les Systèmes d’Information sur le Web....................................................................................................................133 Interface adaptable de requêtes pour un service de Métadonnées Julien Barde, Jacques Divol, Thérèse Libourel, Pierre Maurel...................................135 Gestion de connaissances et de données dans l'aide à la conception de Tissue Microarrays Julie Bourbeillon, Catherine Garbay, Françoise Giroud.............................................141 Un modèle d'adaptation pour les œuvres médiatiques Anis Ouali, Brigitte Kerhervé, Odile Marcotte, Paul Landon......................................147 Adaptabilité à l’utilisateur dans le contexte des services Web Céline Lopez-Velasco, Marlène Villanova-Oliver, Jérôme Gensel, Hervé Martin.......153 Génération de descripteurs : interrogation d’images satellitaires par les métadonnées Florence Sèdes..............................................................................................................159 Chapitre 5 : Extraction et Gestion de Connaissance dans les Environnements Informatiques pour l’Apprentissage Humain ..........................................................165 Extraction d'Information Pédagogique à l'aide de Fouilles de Données : une étude de cas Agathe Merceron..........................................................................................................167 Un Web sémantique de formation par questionnement Sylvain Dehors, Catherine Faron-Zucker, Alain Giboin, Jean-Paul Stromboni..........173 Extraction de pépites de connaissances dans des réponses d’élèves en langage naturel Sylvie Normand-Assadi, Lalina Coulange, Elisabeth Delozanne, Brigitte Grugeon....179 Un cadre pour l’étude des comportements sur une plate-forme pédagogique : du parcours individuel à la conscience du groupe Pierre Camps, Marie-Françoise Canut, André Péninou, Florence Sèdes....................185

Page 10: Egc05 atelier rnti-e-5_(extraits)

x

Chapitre 6 : De la construction d’entrepôts de données à l’extraction de connaissances sur grilles............................................................................................191 Entrepôts de données sur grilles de calcul Pascal Wehrle, Maryvonne Miquel, Anne Tchounikine................................................195 Service de Cache pour les Grilles de Calcul Yonny Cardenas, Jean-Marc Pierson, Lionel Brunie...................................................199 Sélection d’attributs en fouille de données sur grilles Sébastien Cahon, Nouredine Melab et El-Ghazali Talbi..............................................203 Chapitre 7 : Extraction de motifs temporels pour la détection en ligne de situations critiques......................................................................................................209 Apprentissage relationnel de motifs temporels Marie-Odile Cordier, René Quiniou.............................................................................211 Extraction non supervisée de motifs temporels, multidimensionnels et hétérogènes Application à la télésurveillance médicale à domicile Florence Duchêne, Catherine Garbay, Vincent Rialle.................................................217 Améliorer la découverte de chroniques par une découpe intelligente d'un log d'alarmes Françoise Fessant, Christophe Dousson, Fabrice Clérot ............................................223 Extraction de motifs temporels pour la détection dynamique de conflits ethno-politiques Laure Mouillet, Bernadette Bouchon-Meunier, Emmanuel Collain.............................229 Vers une analyse de la dynamique des paramètres physiologiques en Unité de Soins Intensifs Samir Sharshar, Marie-Christine Chambrin................................................................235 Partie III : Données complexes .................................................................................243 Chapitre 8 : Fouille de données complexes...............................................................245 Extraction d’indices spatiaux et temporels dans des séquences vidéo couleur Sébastien Lefèvre, Nicole Vincent................................................................................249 Fusion de classifieurs pour la classification d’images sonar Arnaud Martin..............................................................................................................259 Fouille de collections de documents en vue d’une caractérisation thématique de connaissances textuelles Abdenour Mokrane, Gérard Dray, Pascal Poncelet....................................................269

Page 11: Egc05 atelier rnti-e-5_(extraits)

xi

Recherche d’information multimédia : Apport de la fouille de données et des ontologies Marie-Aude Aufaure , Marinette Bouet........................................................................279 Complexité de l’extraction des connaissances de données : une vision systémique Walid Ben Ahmed, Mounib Mekhilef, Michel Bigand, Yves Page................................289 Une représentation des arborescences pour la recherche de sous-structures fréquentes Federico Del Razo Lopez, Anne Laurent, Maguelonne Teisseire.................................299 Classement d'objets incomplets dans un arbre de décision probabiliste Lamis Hawarah, Ana Simonet , Michel Simonet..........................................................309 Fouille de données du génome à l'aide de modèles de Markov cachés Sébastien Hergalant, Bertrand Aigle, Pierre Leblond, Jean-François Mari................319 Exploration visuelle d'images IRMf basée sur des Gaz Neuronaux Croissants Jerzy Korczak, Jean Hommet, Nicolas Lachiche, Christian Scheiber..........................329 Mise en évidence d'invariants dans une population de cas chirurgicaux Mélanie Raimbault, Ricco Rakotomalala, Xavier Morandi, Pierre Jannin..................339 Chapitre 9 : Extraction de Connaissance à partir d’images...................................349 Apprentissage Automatique de Catégories d'Objets Cartographiques par signature structurelle Güray Erus, Nicolas Loménie.......................................................................................351 Application des courbes de Peano en recherche d'image par le contenu Adel Hafiane, Bertrand Zavidovique............................................................................355 Recherche d’image par le contenu : requête partielle ou globale, apprentissage en ligne Sylvie Philipp-Foliguet.................................................................................................359 Extraction de connaissances pour la description d’images satellitaires à très haute résolution spatiale Erick Lopez-Ornelas, Florence Sèdes..........................................................................365 Chapitre 10 : Qualité des Données et des Connaissances........................................371 Data Freshness Evaluation in Different Application Scenarios Veronika Peralta, Mokrane Bouzeghoub......................................................................373 Nettoyage des données XML : combien ça coûte ? Laure Berti-Equille.......................................................................................................379

Page 12: Egc05 atelier rnti-e-5_(extraits)

xii

Extraction de Règles en Incertain par la Méthode Implicative Régis Gras, Raphaël Couturier, Fabrice Guillet, Filippo Spagnolo............................385 IPEE : Indice Probabiliste d'Ecart à l'Equilibre pour l'évaluation de la qualité des règles Julien Blanchard, Fabrice Guillet, Henri Briand, Régis Gras.....................................391 Le rôle de l'utilisateur dans un processus d'extraction de règles d'association Cyril Nortet, Ansaf Salleb, Teddy Turmeaux, Christel Vrain .......................................397 Arbre BIC optimal et taux d’erreur Gilbert Ritschard..........................................................................................................403 Validation d’une expertise textuelle par une méthode de classification basée sur l’intensité d’implication Jérôme David, Fabrice Guillet, Vincent Philippé, Henri Briand, Régis Gras.............409 ARQAT : plateforme exploratoire pour la qualité des règles d'association Xuan-Hiep Huynh, Fabrice Guillet, Henri Briand.......................................................415 Mesurer l’intérêt des règles d’association Benoît Vaillant, Patrick Meyer, Elie Prudhomme, Stéphane Lallich, Philippe Lenca, Sébastien Bigaret..............................................................................................421

Page 13: Egc05 atelier rnti-e-5_(extraits)

Partie I

_

Modélisation

- 1 - RNTI-E-5

Page 14: Egc05 atelier rnti-e-5_(extraits)

Chapitre 1

Modélisation des connaissances �

La conférence EGC rassemble depuis plusieurs années des chercheurs et industriels autour de la double thématique de l'extraction et de la gestion des connaissances. Tous les acteurs de cette communauté sont confrontés au problème de la modélisation des connaissances. Différentes méthodes, formalismes et outils ont été proposés et mis en oeuvre pour modéliser, stocker et utiliser les informations au sein des bases de données ou des bases de connaissances. L'atelier modélisation des connaissances qui a eu lieu en parallèle avec les journées EGC 2005 a réuni une quarantaine de personnes autour d'exposés sélectionnés avec édition d'actes. Les papiers ont été retravaillés pour l'édition que nous vous proposons dans cet ouvrage.

Actuellement, les recherches qui intéressent la communauté extraction et gestion des connaissances visent à exploiter les nombreuses données disponibles au sein des organisations, à en extraire des connaissances intéressantes et exploitables, à intégrer ces connaissances aux systèmes décisionnels, ou à les diffuser aux différents agents de l'organisation. La modélisation des connaissances est un sujet majeur pour ces différentes problématiques. Les articles présentés peuvent être regroupés en trois thèmes: transformation de modèles, apports fondamentaux, applications.

Tout d'abord un rapprochement s'effectue entre les travaux d'intelligence artificielle et les

travaux des communautés de modélisation des données. Les problématiques de transformation de modèles sont ainsi de plus en plus prégnantes dans les diverses communautés. L'article de T. Raimbault présente ainsi comment les diagrammes UML peuvent être utilisés comme support à de la représentation visuelle de connaissances dans le cadre du modèle des graphes conceptuels ; des vérifications inédites de construction de ces modèles sont proposées. L'article de M.

Responsables du chapitre : B. Duval, S. Loiseau, H. Briand

- 3 - RNTI-E-5

Page 15: Egc05 atelier rnti-e-5_(extraits)

Ahlonsou et al. présente lui les transcriptions possibles entre un diagramme de classe UML et le langage OWL qui est utilisé dans les travaux de WEB sémantique.

Ensuite, les travaux fondamentaux qui proposent de nouveaux langages ou modèles de représentation sont illustrés par deux contributions. Le travail de F. Fürst propose un cadre formel et complet pour contraindre les ontologies ; celles-ci sont à la base de nombreux travaux de modélisation en fournissant de manière organisée le vocabulaire de base d'un domaine étudié. L'article de D. Genest et al. propose quant à lui un modèle de connaissance qui fusionne les modèles d'influence traditionnels avec le modèle des graphes conceptuels qui contient lui-même une couche ontologique.

Enfin, les travaux de recherche appliqués à un domaine particulier sont évidemment présents. Les applications ne sont pas simplement des illustrations ou validations des recherches menées en modélisation des connaissances, elles sont un point d'entrée pour comprendre et modéliser les connaissances mises en jeu dans les processus intelligents. Le travail de N. Ronarc'h et al. est issu des besoins applicatifs de modélisation du comportement psychologique. Il propose d'utiliser les modèles de cartes cognitives pour capturer et formaliser les connaissances émotionnelles des personnes. Les recherches de S. Fendri et al. sont consacrées à une tâche de modélisation et de capitalisation des connaissances humaines dans le domaine de l'audit financier. Afin de dépasser les limites des modèles couramment proposés, le processus d'estimation du risque d'audit est modélisé à l'aide d'arbres de décision flous permettant d'expliciter les facteurs pertinents mis en jeu. L'article de N. Messai s'intéresse à l'intégration de plusieurs sources de données biologiques lors d'une recherche. Le travail utilise des méta-données associées aux sources et le concept de treillis de Galois pour classer ces sources en fonction de leur intérêt pour les requêtes. Des ontologies sont associées aux treillis de Galois afin de permettre l'enrichissement de requêtes.

Plusieurs tendances peuvent être dégagées des travaux actuels. La modélisation des

connaissances, en tant que processus intermédiaire entre l'analyse et l'exploitation, fait de plus en plus appel à des langages visuels de représentation. Les modèles de cartes cognitives, de graphes conceptuels, de diagrammes de classes sont ainsi à la base de nombreux travaux. La complexité des connaissances à modéliser nécessite des approches issues des travaux formalisant les informations "imparfaites" comme le fait la logique floue. Une des difficultés croissante, due en particulier au développement de l'internet, est l'hétérogénéité des sources de connaissances ; les problèmes de fusion et d'incohérence nécessitent des travaux nouveaux. Un point important que nous pouvons noter dans les différents articles proposés est que les travaux de recherche menés sont de plus en plus pluridisciplinaires : les travaux de génie logiciel (UML), de logique (logique floue), d'aide à la décision (cartes cognitives), de modèles de données (XML) côtoient les travaux de modélisation traditionnels (graphes conceptuels).

Comité de programme et d'organisation : Béatrice Duval (LERIA, Université d'Angers ) Stéphane Loiseau (LERIA, Université d'Angers ) Henri Briand (LINA, Ecole Polytechnique de l'université de Nantes )

- 4 -RNTI-E-5

Page 16: Egc05 atelier rnti-e-5_(extraits)

Salem Benferhat (CRIL, Université d'Artois) Giuseppe Berio (Université de Turin, Italie) Corine Cauvet (LSIS, Université de Marseille ) Nadine Cullot (LE2I, Université de Bourgogne) Jérôme Euzenat (INRIA Rhône Alpes) David Genest (LERIA, Université d'Angers) Fabrice Guillet (LINA, , Ecole Polytechnique de l'université de Nantes) Mohan Said Hacid (LIRID, Université Lyon1) Rémi Lehn (LINA, Université de Nantes) Chantal Reynaud (LRI, Université de Paris Sud)

- 5 - RNTI-E-5

Page 17: Egc05 atelier rnti-e-5_(extraits)

Une nouvelle methode graphique pour interrogeret verifier des diagrammes de classes UML

Thomas Raimbault

LERIA, Universite d’Angers, 2 boulevard Lavoisier 49045 ANGERS Cedex [email protected]

Resume. UML est le langage graphique de reference dans l’industriepour la modelisation objet. Cependant UML reste un langage, et ne four-nit aucun moyen de verification ou d’interrogation de ses schemas. Il existeaujourd’hui des outils de verification, mais ils se comportent comme desboıtes noires ou l’utilisateur ne peut acceder. Nous proposons une methodegraphique de verification et d’interrogation de diagrammes de classesUML. L’aspect intuitif et dessinable de notre methode offre a l’utilisa-teur la possibilite d’interroger le contenu de diagrammes de classes, ainsique de definir et d’adapter ses propres criteres de verification. Le modelecalculatoire de notre approche est celui des graphes conceptuels.

1 Introduction

UML, Unified Modeling Language (Booch et al. 1998), est le langage graphique dereference dans l’industrie pour la modelisation objet. Cependant UML reste un langage,et ne fournit aucun moyen de verification ou d’interrogation de ses schemas. Il existedes outils commerciaux de verification, tels que Rational Software Rose (IBM 2004)ou Borland Together (Borland 2004). Mais les verifications proposees sont uniquementstandards, verifiant la coherence des diagrammes par rapport aux specifications objet.De plus, la methode de verification est dans une boıte noire : les traitements sont debas niveau et non accessibles a l’utilisateur. Enfin, l’interrogation de diagrammes n’estpas totalement libre mais limite a un cadre pre-formate de questions.

Pour repondre aux exigences de qualite et d’interaction en modelisation, nous propo-sons une methode graphique d’interrogation et de verification de diagrammes de classesUML. L’aspect intuitif et dessinable de cette methode offre a l’utilisateur la possibilitede definir et d’adapter ses propres criteres de verification, ainsi que d’interroger libre-ment le contenu de diagrammes de classes UML. Le travail presente dans cet articleest issu de (Raimbault 2004), et est traite pour l’atelier EGC 2005 “Modelisation des

connaissances” de facon intuitive au travers un exemple. Concretement, notre methodeutilise pour les calculs le modele des graphes conceptuels (Sowa 1984).

Cet article est structure comme suit : la section 2 traite de notre methode gra-phique d’interrogation et de verification de diagrammes de classes UML. En section 3,nous abordons l’aspect calculatoire de notre methode qui utilise la modele des graphesconceptuels. La section 4 discute des resultats et des perspectives de notre methode.

2 Interroger et Verifier un diagramme de classes

Nous indiquons d’une part comment formuler une requete pour interroger le contenud’un diagramme de classes UML, d’autre part, comment definir les criteres de validite

- 7 - RNTI-E-5

Page 18: Egc05 atelier rnti-e-5_(extraits)

Transformation des concepts du diagramme de classe UML en OWL full

Macaire Ahlonsou, Emmanuel Blanchard

Henri Briand, Fabrice Guillet 2bis boulevard Léon Bureau BP96228 de l’Université de Nantes

http://www.sciences.univ-nantes.fr/lina/fr/ LINA – Université de Nantes

Ecole polytechnique de l’université de Nantes La Chantrerie, rue Christian Pauc 44306 Nantes CEDEX 3

{Prenom.Nom}@polytech.univ-nantes.fr

Résumé. Le web peut être considéré comme une grande base de connaissances. La recherche des informations pertinentes sur la toile est rendue de plus en plus difficile, voire impossible avec l’accroissement de la volumétrie des pages disponibles. Le problème réside dans le fait que les outils existants ne peuvent pas s’appuyer actuellement sur une description du contenu des documents. Le web sémantique utilise différents langages pour mieux exploiter et traiter les contenus des ressources web. Dans le but de passer de UML vers OWL, il est intéressant d’étudier la possibilité de transformer chacun des concepts du diagramme de classe UML en OWL.

1 Introduction UML (Unified Modeling Language) (Gaertner et al. 2002) est un langage de modélisation

orienté objet clairement adopté dans le monde industriel. Le web sémantique est une vision du futur web dans lequel l'information serait explicitée de manière à permettre son traitement automatique par des machines. Nombreuses sont les applications qui sont déjà modélisées en UML. Il n’existe pas de langage de modélisation spécifique pour modéliser une base de connaissance. On peut étendre l’utilisation de UML, notamment les diagrammes de classe à cette fin (Walter 1998).

L’objectif de cet article est d’étudier la possibilité de transformer les concepts du diagramme de classe UML (langage semi formel) en OWL (langage formel). Cette transformation est effectuée dans un seul sens (UML vers OWL) et reste dans un monde clos. Nous proposons de transformer trois concepts du diagramme de classe après avoir situé les divers langages du web sémantique les uns par rapport aux autres, en mettant en avant leurs limites.

2 Langages et définitions

2.1 UML

UML est un langage de modélisation plébiscité dans le domaine de la conception. Il permet de représenter les composants statiques et dynamiques des systèmes dépendant des logiciels à travers des modèles représentés par des vues. Ces vues sont manipulées à travers des diagrammes. Cet article ne traitera que le cas des diagrammes de classe.

- 13 - RNTI-E-5

Page 19: Egc05 atelier rnti-e-5_(extraits)

Modeliser des connaissances ontologiques dans lecadre du modele des Graphes Conceptuels

Frederic Furst

LINA - FRE 272922 rue de la Houssiniere, BP 92208, 44322 Nantes

[email protected]

Resume. Cet article presente OCGL (Ontology Conceptual Graph Lan-guage), un langage de representation d’ontologie base sur le modele desGraphes Conceptuels. Il decrit en detail la facon dont une ontologie estmodelisee en OCGL, et presente l’implementation de ce langage dans l’ate-lier d’ingenierie ontologique TooCoM.

1 Introduction

L’ingenierie des ontologies est nee de la volonte de diversifier les applications desSystemes a Base de Connaissances (SBC), et de permettre des representations deconnaissances independantes de ces diverses applications (Gomez-Perez et al., 2003).L’integration d’un tel composant dans un Systeme a Base de Connaissances supposealors d’adapter les representations qu’il integre a l’objectif operationnel du systeme,adaptation qui est l’objet du processus d’operationalisation des ontologies (Furst et al.,2004). D’autre part, les ontologies ont vocation a integrer toute la semantique desdifferents domaines de connaissances, c’est-a-dire des proprietes de base comme la sub-somption entre concepts, mais egalement toute propriete permettant d’exprimer lasemantique du domaine considere. Les ontologies evoluent ainsi des ontologies legeres(lightweight ontologies), n’integrant qu’un nombre restreint de proprietes, vers des onto-logies lourdes (heavyweight ontologies), visant la modelisation de toutes les proprietesnecessaires a la representation de toute la semantique d’un domaine (Gomez-Perezet al., 2003).

Dans cet article, nous presentons OCGL (Ontology Conceptual Graph Language),un langage de representation d’ontologies lourdes, base sur le modele des GraphesConceptuels (GCs) (Sowa, 1984). OCGL est implemente dans l’outil TooCoM (a Tool toOperationalize an Ontology in the Conceptual Graph Model), dedie a la modelisation etl’operationalisation d’ontologies lourdes dans le cadre du modele des Graphes Concep-tuels 1. Nous detaillons ici le modele de representation utilise dans TooCoM, mais nepresentons pas le processus d’operationalisation qu’il implemente, renvoyant pour celale lecteur a (Furst et al., 2004).

1. Cet outil est disponible sous licence GPL sur le site http://sourceforge.net/projects/toocom/

- 19 - RNTI-E-5

Page 20: Egc05 atelier rnti-e-5_(extraits)

Cartes cognitives de graphes conceptuels

David Genest, Stéphane Loiseau

LERIA – Université d’Angers, 2, Boulevard Lavoisier – 49045 Angers cedex 1 {genest,loiseau}@info.univ-angers.fr

Résumé. Le modèle des cartes cognitives offre une représentation graphique d’un réseau d’influences entre différentes notions. Nous proposons un nouveau modèle de cartes cognitives qui intègre la partie représentation des connaissances et l'opération de projection du modèle des graphes conceptuels.

1 Introduction Une carte cognitive (Tolman 1948) contient deux types d'informations : des nœuds

appelés états représentant des concepts et des arcs entre ces nœuds représentant des liens d'influence positifs ou négatifs. Un mécanisme d’inférence propage les influences.

Une première faiblesse des cartes cognitives est sa trop grande souplesse car un état peut être représenté par n'importe quelle étiquette linguistique. Une seconde faiblesse du modèle est l’absence de structuration des états, qui fait que des liens entre états, autres que ceux d’influence, ne peuvent pas être exprimés.

Le modèle des graphes conceptuels (Sowa 1984) est un modèle de représentation graphique de connaissances. Un graphe conceptuel est défini sur une structure appelée support permettant de spécifier en hiérarchie le vocabulaire. Une opération d'inférence, appelée projection, permet de rechercher des graphes qui sont sémantiquement liés entre eux.

L’idée du modèle des cartes cognitives de graphes conceptuels que nous proposons consiste à décrire chaque état par un graphe. D’abord, l’utilisation d'un graphe conceptuel, associé à chaque état, permet de définir chaque état en référence à une ontologie qui est le support. Ensuite, on peut calculer ou regrouper des classes d’états qui sont liés entre eux dans une collection. Enfin, cette classification peut se combiner avec le calcul d'influence.

Dans la partie 2, nous décrivons le modèle des cartes cognitives de graphes conceptuels. La partie 3 décrit la notion de collection. Dans la partie 4, nous définissons les opérations permettant le raisonnement dans le modèle et décrivons les apports de ces opérations.

2 Modèle des cartes cognitives de graphes conceptuels

Le modèle des graphes conceptuels utilisé est celui défini dans (Chein et Mugnier 1992).

Tout graphe conceptuel est défini sur un support qui organise, à l’aide de relations « sorte de », un vocabulaire composé de types de concepts et de types de relations (figure 1). Un graphe conceptuel G est formé d’un ensemble de sommets concepts (CG), un ensemble de sommets relations (RG), un ensemble d’arêtes (EG) et une application qui associe à tout sommet et à toute arête une étiquette (étiqG). Le graphe conceptuel de la figure 2 représente un accident mortel (accident dans lequel une personne est morte)

Une carte cognitive de graphes conceptuels permet de représenter des relations d’influence entre différentes notions, appelées états, chacun de ces états étant défini par un graphe conceptuel.

- 25 - RNTI-E-5

Page 21: Egc05 atelier rnti-e-5_(extraits)

Modélisation des connaissances émotionnelles par

les cartes cognitives floues

Nathalie Ronarc’h 2, Gaële Rozec

1,

Fabrice Guillet 2, Alexis Nédélec

3, Serge Baquedano

1 , Vincent Philippé

1

1 Performanse SA Atlanpôle La Fleuriaye 44470 CARQUEFOU

http://www.performanse.fr2 LINA - Polytech' Nantes rue Christian Pauc BP50609 44306 Nantes CEDEX 3

{Prenom.Nom}@polytech.univ-nantes.fr3 CERV/ ENIB de Brest Technopôle Brest Iroise ; CP 15 ; 29608 Brest Cedex

{nom}@enib.fr

Résumé: Les recherches en psychologie ont permis d'établir une relation entre

émotions et prise de décision. La prise en compte de caractéristiques humaines

telles que les émotions et la personnalité dans les processus d’interaction entre

agents est au centre de ce travail. Il s'inscrit dans le cadre du projet GRACE

(Groupes Relationnels d'Agents Collaborateurs Emotionnels)/ RIAM (Réseau

des Industries, de l’Audiovisuel et du Multimédia) .

1 Introduction

Aujourd’hui peu d'outils permettent de décrire facilement les comportements d’individus.

Les sciences humaines apportent leur expertise en proposant des modèles émotionnels

décrivant le processus de décision et les comportements des humains dans un contexte

donné. Les cartes cognitives émotionnelles basées sur le modèle Performanse SA nous

servent d'outil de recueil d'informations sur l'évolution des émotions, suite à un événement

donné. Douze émotions, influencées par les traits de personnalité de l'individu, sont ainsi

représentées. La problématique est de traduire ces modèles en langage informatique. La

combinaison de la socio-psychologie et du domaine multi-agent (Ferber 95) nous apporte les

éléments nécessaires à la modélisation pertinente des comportements et des interactions

d'agents humains pouvant évoluer dans un milieu virtuel.

Dans ce contexte les travaux du CERV/ LI2, associé au projet GRACE / RIAM , sur les

SMA et la réalité virtuelle ont donné lieu à l'élaboration d'une simulation sur la plateforme

AréVi (Harrouet) dans laquelle les entités considérées, c'est à dire des agents autonomes,

sont capables de percevoir tout ou partie de leur environnement, de réagir aux évènements en

fonction de leur état interne et de leurs connaissances. Nos agents possèdent des capacités de

raisonnement, ils sont munis d'états mentaux, ce sont des agents cognitifs. De plus les agents

ont une personnalité qui nous permet de les distinguer.

2 Représentation du processus de décision de l'agent

Le processus de prise de décision de l'agent repose sur la boucle Perception – Décision –

Action du fonctionnement des agents cognitifs. Ainsi les cartes cognitives émotionnelles

(CEF) sont intégrées à un dispositif plus complexe de prise de décision de l’agent, tenant

compte de ses connaissances, de l’évaluation de l’événement perçu et de son estimation de

l’environnement. Le processus de prise de décision des agents, représenté Figure 1 et

- 31 - RNTI-E-5

Page 22: Egc05 atelier rnti-e-5_(extraits)

Logique Floue appliquée à l’inférence du « Risque Inhérent » en audit financier

Souhir Fendri-Kharrat*

Hassouna Fedhila** Pierre-Yves Glorennec***

* Ecole Supérieure de Commerce, Rte de l’Aéroport-Km 4, BP 1081, Sfax 3018-Tunisie

[[email protected]] ** Institut Supérieur de Comptabilité et d’Administration des Entreprises, Campus, Manouba

2001-Tunisie [[email protected]]

*** Institut National des Sciences Appliquées de Rennes, 20, Av. des buttes de Coësmes-CS 14315-35043 RENNES Cedex-France

[[email protected]]

Résumé : Le Risque d’Audit est un indice d’existence d’erreurs dans les états financiers d’une entreprise. Trois modèles mathématiques sont associés à ce concept du RA : un modèle « Bayesien », un modèle « évidentialiste », et un modèle « flou ». Ces trois modèles accusent des incohérences mathématiques et des difficultés d’application pratique, surtout au niveau de la composante « Risque Inhérent » du risque d’audit. Ils considèrent le processus cognitif d’estimation du RI en tant que « boîte noire ». Nous proposons un simple algorithme d’inférence flou interprétable pour capter le processus cognitif d’estimation du RI, algorithme basé sur l’induction d’arbre de décision flou. Notre objectif est d’identifier les éléments de cette structure et de démontrer que l’utilisation d’une telle structure d’inférence floue est proche de la décision réelle d’estimation du RI. Il s’agit d’une recherche exploratoire et expérimentale.

1 Introduction Aussi bien les normes internationales [ISA1] que les normes américaines [SAS1] d’audit

s’accordent sur le fait que l’audit financier est un audit de conformité entre les réglementations en vigueur et les états financiers d’une entreprise. Les SAS n° 39, 47 & 55 et les ISA n° 400 à 408, stipulent que la non-conformité de la comptabilité d’une firme à des réglementations en vigueur, est l’essence même de l’erreur comptable (AICPA 2003 et IFAC 2003). Le concept de « Risque d’Audit » [RA] est un indice de l’occurrence d’erreurs dans les rapports financiers : ces normes conceptualisent le « Risque d’Audit » [RA] en tant qu’une intersection entre trois ensembles, à savoir : « Risque Inhérent » [RI], « Risque de Non Contrôle » [RNC] et « Risque de Non Détection » [RND]. La première composante RI, indique l’ensemble des erreurs pouvant s’infiltrer dans les états financiers et provenant de

1 SAS : .......Statements on Auditing Standards (normes d’audit de l’AICPA) ISA : ........International Standards of Auditing (normes d’audit de l’IFAC) AICPA :...American Institute of Certified Public Accountants (Ordre des experts comptables-USA). IFAC : .....International Federation of Accountants (Fédération internationale des experts comptables).

- 37 - RNTI-E-5

Page 23: Egc05 atelier rnti-e-5_(extraits)

������������ ��������������� � ��� �������� ��������� ���

�������������������� ���� �����

������������������ ��������������������� ���� �������������������� ����

����� !"�#$�%��&'�(")�*� + !,�-��� ������#.����/0�*���12�3�������������� ������45� ���67��899�:;;<<<6� ���67�;������; ����������

������� � ����=��9 �������=98 ������/���7�/�9� ���9������/8��/8����� ��/���� � �����6�2����/ ��9��>�/ �9���������9����������?�� ��>����9����@���������������=9��� ��=��� /�=����A� ��/���9�/ ����9�������� ���=9=�� �=����6����/ �/��9�/ �9���9�>����9����@��������B9���9����9�����9�����9����=�=��������9���������C/��>������� ��98������/ �9��/9� ����/�=���9���6�#��/��/�������=��9�9������.���>��A9�������@����������� ��/��7������9���������A9��� �� ��� ������9� ��� / �/��9� ����B9�� ���� ��� 9������� ��� ?�� ���=��9��96� #@ �����������9����/����� ��/���9��=���9� >� ���9�������@ �������������9� �����/ �/��9�/ ���� ����9��������9������6�������=�� ��9� ���������=98 ���/ ��9��>�����/8����������B9��>����9����@ �9 � �������� ����������9���� �@��=���� ���� ��� 9������6� ���A� � ��� �@����/8�����9� �9� � ����:��@����/8�����9������=�=�����9� ���9��@����/8�����9������=/�����9� �6���

�� ��������� �������9����A��� ��.��// �������������� ��/9� ���9��@����0������ ��=���� � ���������

������� ��������� ��=���9��������//�������������D��6�1��� ��=�� �9��=���9 ��=��������� ��/���� � ������ 77���9������9��7�/���@��9��� ��9� ���7������7�/���9����@�//.�>������ / �9���6� #�� ������9=� ��� /�� ��/�� �9� ��� / ���=���9���9=� ��� � ��=�� ��@�����/ �9������9������99��9���A��9����9�����@�� ��������7 ���9� ������/ ���.9�6�1�������9��@����/���@���/8=�����������@��/ ���9�����9=����7 ���9����� ��=���9��@����/��E �����7������7�=����/�F��������>�G ������/ �9������� ��/��������9���9��H���������/ 8=���/����������������=� �����A�����B9��� =�6�*�/��>����9����� ��.���������9����=�=�����9���������� ����@����/���7�/�9� ����� ��/���� �������7 ���9� ������=���9����������99��9����G�����������9����/����� ��/�����>�����������B9�6�1�99��/���7�/�9� �����9�B9���7��9�������������@��������������/��9.���� /����9��9����/ �9�����9���������9=���� ��/���9������=� �=9��� ��=�6� I� ���9��� ��� ��� 8�=���/8��� ��� ��/�� �9����� � �� ��� �� B9���/��������@�A9��������� ��/���/��9���������=� ������������A�>��������9� ��� ��=�6�#���=98 ��� �@��9��� ��9� �� ��� ��/�� � �9� ��� �9��� �������� ��� / ��9�� ��� =���9������������B9�� ��@����� 9���9�� � ��� ��=�� ���� ��� �=��9�9� ��� ��� ��/8��/8�6� ����� ��� �� ��.��� �����.����@�������9� >��@�A�� �9�9� �����/ ������/��E�=9��� ��=�F��=/�����9���� ��/����� ������������D������������9��@����9�7������� ��/�����9����9��� ����������9� ��� =���9��@��9������9�>��@����0��=���9���������������B9��������=7=���9�>���� �9 � �������� ���������������9������77�����/�99������B9���9��@��=�� ��������=� ��6���

- 43 - RNTI-E-5

Page 24: Egc05 atelier rnti-e-5_(extraits)

Chapitre 2

Modèles graphiques probabilistes pour la modélisation

des connaissances : inférence, apprentissage et applications

Les modèles graphiques probabilistes sont classiquement définis comme étant le mariage entre la théorie des probabilités et la théorie des graphes. Les probabilités permettent à ces modèles de prendre en compte l’aspect incertain présent dans les applications réelles. La partie graphique offre un outil intuitif inégalable et attractif dans de nombreux domaines d’applications où les utilisateurs ont besoin de "comprendre" ce que raconte le modèle qu’ils utilisent. Réciproquement, cela permet aussi à un expert des modèles graphiques de construire plus facilement un modèle pour une application précise en s’appuyant sur les avis des spécialistes de ce domaine.

L’utilisation conjointe des probabilités et des graphes nous offre une famille de modèles de connaissance très riche, avec par exemple les réseaux bayésiens, les modèles de Markov cachés et leurs dérivés ou les filtres de Kalman.

L’apparition d’un formalisme commun pour représenter et manipuler ces modèles donne maintenant lieu à de fructueux échanges où un travail original sur l’un de ces modèles peut être adapté ou généralisé aux autres, et ouvrir de nouvelles pistes de recherche. Citons par exemple le cas des réseaux bayésiens dynamiques, qui utilisent à la fois des algorithmes développés originalement soit pour les réseaux bayésiens statiques, soit pour les modèles de Markov cachés, soit pour les filtres de Kalman, le tout en apportant un pouvoir expressif supplémentaire par rapport à ces premiers modèles.

Responsable du chapitre : P. Leray

- 49 - RNTI-E-5

Page 25: Egc05 atelier rnti-e-5_(extraits)

Nous proposions dans cet atelier de dresser un panorama des activités de recherche dans le domaine des modèles graphiques probabilistes, tant au niveau théorique que pour les aspects applicatifs. Le but était donc de rassembler, dans le cadre de la conférence EGC 2005, et sous le parrainage de CAFE, Collège Apprentissage, Fouille et Extraction de l’AFIA, les chercheurs intéressés par le sujet et de fournir un lieu de discussion sur ses derniers développements.

Les présentations devaient aborder un des thèmes suivants : • inférence : nouveaux algorithmes d’inférence exacte ou approchée • stratégies et algorithmes d’apprentissage : élicitation de données, prise en compte de

données incomplètes / variables manquantes, modélisation biomimétique • modèles graphiques probabilistes : réseaux bayésiens temporels, réseaux bayésiens

orientés objets, diagrammes d’influence, réseaux de neurones • relations avec d’autres formalismes de représentation de l’incertain • applications réelles • outils logiciels

Afin de couvrir les nombreuses facettes du sujet tout en gardant du temps pour discuter, cet

atelier s’est déroulé sur une journée entière, avec sept présentations couvrant un spectre assez large, de part les types de modèles graphiques utilisés (réseaux bayésiens « classiques », modèles causaux, modèles dynamiques, réseaux bayésiens de niveau deux), les algorithmes mis en oeuvre (inférence, apprentissage) et les domaines d’application concernés (diagnostic multiple de systèmes complexes, reconnaissance de caractères manuscrits, détection d’intrusion, systèmes multi-agents, traitement de la parole).

La première série d’articles traite des modèles graphiques dynamiques. F. Bach et M.I. Jordan

utilisent des modèles de Markov cachés pour une application de traitement de signal, l’estimation de plusieurs fréquences fondamentales. Ce travail utilise de nombreuses avancées récentes des modèles graphiques probabilistes temporels.

Le second article de cette série est consacré à l’inférence dans les Modèles de Markov cachés hiérarchiques et factorisés. Ce travail, présenté par S. Gelly, N. Bredeche et M. Sebag, propose un changement de formalisme permettant de "simplifier" ces modèles pour être capable de leur appliquer des algorithmes d’inférence exacts.

L. Likforman-Sulem et M. Sigelle nous décrivent ensuite une application des réseaux bayésiens dynamiques pour la représentation et la reconnaissance de caractères manuscrits.

La dernière série d’articles est consacrée à d’autres modèles graphiques probabilistes. Les

travaux de V. Delcroix, M.A. Maalej et S. Piechowiak passent en revue l’utilisation des réseaux bayésiens pour le diagnostic multiple de systèmes complexes.

A. Faour, Ph. Leray et C. Foll décrivent ensuite l’utilisation de réseaux bayésiens au sein d’une architecture de data-mining destinée à filtrer les alarmes dans les systèmes de détection d’intrusion informatique.

- 50 -RNTI-E-5

Page 26: Egc05 atelier rnti-e-5_(extraits)

Nous passons ensuite des réseaux bayésiens "classiques" aux réseaux bayésiens causaux, et plus précisèment les modèles causaux multi-agents avec le travail de S. Maes, S. Meganck et B. Manderick, qui décrit un algorithme d’inférence pour ces modèles spécifiques.

L’article de L. Smail et J.P. Raoult conclut cette série d’articles en développant un nouveau formalisme, les réseaux bayésiens de niveau deux et en illustrant le principe fondamental de d-séparation dans ces modèles.

Comité de programme et d'organisation :

P. Leray (Laboratoire PSI - FRE CNRS 2645, INSA Rouen - [email protected] M.R. Amini (LIP6, Université Paris 6), T. Artières (LIP6, Université Paris 6), M. Bouissou (EDF / LAMA, Université de Marne la Vallée), F. Druaux (GREAH, Université du Havre), A. Faure (GREAH, Université du Havre), O. François (PSI, INSA Rouen), P. Gallinari (LIP6, Université Paris 6), Y. Kodratoff (LRI, Université Paris Sud), P. Naïm (Elseware), O. Pourret (EDF), J.P. Raoult (LAMA, Université de Marne la Vallée), L. Smail (LAMA, Université de Marne la Vallée), P.H. Wuillemin (LIP6, Université Paris 6).

Remerciements

Nous aimerions remercier F. Cloppet et les responsables de la conférence EGC 2005 pour avoir accueilli cet atelier, et M. Sebag pour son aide concernant la diffusion de l’appel d’offre.

- 51 - RNTI-E-5

Page 27: Egc05 atelier rnti-e-5_(extraits)

Modeles de Markov caches pour l’estimation

de plusieurs frequences fondamentales

Francis Bach∗, Michael I. Jordan∗∗

∗ Centre de Morphologie MathematiqueEcole des Mines de Paris

35, rue Saint Honore77305 Fontainebleau, [email protected]

∗∗ Computer Science Divisionand Department of Statistics

University of CaliforniaBerkeley, CA 94720, [email protected]

1 Introduction

Le suivi de la frequence fondamentale est un probleme important du traitementde la parole et de la musique, et le developpement d’algorithmes robustes pour ladetermination d’une ou plusieurs frequences fondamentales est un sujet actif de re-cherches en traitement du signal acoustique (Gold et Morgan, 1999). La plupart desalgorithmes d’extraction de la frequence fondamentale commencent par construire unensemble de caracteristiques non lineaires (comme le correlogramme ou le “cepstrum”)qui ont un comportement special lorsqu’une voyelle est prononcee. Ensuite, ces al-gorithmes modelisent ce comportement afin d’extraire la frequence fondamentale. Enpresence de plusieurs signaux mixes additivement, il est naturel de vouloir modeliserdirectement le signal ou une representation lineaire de ce signal (comme le spectro-gramme), afin de preserver l’additivite et de rendre possible l’utilisation de modelesdestines a une seule frequence fondamentale pour en extraire plusieurs.

L’utilisation directe du spectrogramme necessite cependant un modele probabili-tiste detaille afin de caracteriser la frequence fondamentale. Dans cet article, nousconsiderons une variante de modele de Markov cache et utilisons le cadre des modelesgraphiques afin de construire le modele, apprendre les parametres a partir de donneeset developper des algorithmes efficaces d’inference. En particulier, nous utilisons desdeveloppments recents en apprentissage automatique (machine learning) pour caracte-riser les proprietes adequates des signaux de parole et de musique ; nous utilisons desprobabilites a priori non-parametriques afin de caracteriser la regularite de l’enveloppespectrale et nous ameliorons la procedure d’apprentissage grace a l’apprentissage dis-criminatif du modele.

- 53 - RNTI-E-5

Page 28: Egc05 atelier rnti-e-5_(extraits)

Inférence dans les HMM hiérarchiques et factorisés :changement de représentation vers le formalisme des

Réseaux Bayésiens.

Sylvain Gelly∗, Nicolas Bredeche∗, Michèle Sebag∗

∗Equipe Inference&Apprentissage - Projet TAO (INRIA futurs),LRI, Université Paris-Sud, 91504 Orsay Cedex

(gelly,bredeche,sebag)@lri.fr

1 Présentation du problème

Une limite essentielle des HMM, et plus généralement des modèles de Markov,concerne le passage à l’échelle, l’impossibilité de la prise en compte efficace de l’influencede phénomènes indépendants et la difficulté de généralisation.

Pour répondre à ces problèmes, plusieurs extensions existent. En particulier, nousnous intéresserons dans ce qui suit à la hiérarchisation (Theocharous et al. 2001, 2004)et à la factorisation (Ghahramani 1996).

La hiérarchisation permet de réduire le nombre de liens entre états nécessaires dansun HMM et par là même de réduire la complexité algorithmique de l’apprentissage ainsique l’imprécision. Quant à la factorisation, le principe est d’expliquer les observationspar plusieurs causes plutôt qu’une seule. C’est à dire qu’on remplace le P (Y |X) desHMM par P (Y |X1, X2, ..., Xn). Les X i sont des variables cachées pouvant être géréesindépendamment. Les P (X i

t+1|X i

t) sont alors différents pour chaque i.

– L’existence de dépendances multiples dans les FHHMM entraîne à priori uneexplosion combinatoire du nombre de paramètres à apprendre, ce qui est d’autantplus problématique lorsque peu d’exemples sont à notre disposition (ceci est unepropriété inhérente à la robotique) ;

– La présence de circuits dans les dépendances conditionnelles entre les variablesd’un FHHMM empêchent la modélisation directe par un réseau bayesien. Il està noter que ces dépendances ne concernent les variables qu’à un même pas detemps (synchrones).

Dans la suite de cet article, nous ne ferons pas de différence entre les dépendancessynchrones et les transitions temporelles, les deux types étant des dépendances condi-

tionnelles entre deux variables.

On ne peut ainsi pas adapter directement les algorithmes existants dans le cas desHMM factorisés, ou hiérarchiques.

Un aspect important du problème est que notre système apprend à partir de don-nées éparses car nous faisons l’hypothèse que nous ne disposons que d’un petit nombred’exemples pour apprendre. Ceci se justifie par le domaine d’application (la robotiquesituée), où le processus d’échantillonnage des données est contrôlé par un compor-tement dépendant entre autres de l’environnement et des capacités du robot qui nepermet pas d’obtenir beaucoup d’exemples. Par conséquent, nous souhaitons exprimerun compromis entre précision et vitesse de l’apprentissage.

- 57 - RNTI-E-5

Page 29: Egc05 atelier rnti-e-5_(extraits)

Représentation et reconnaissance de caractères manuscritspar Réseaux Bayésiens Dynamiques

Laurence Likforman-Sulem, Marc Sigelle

GET-ENST/ Traitement du Signal et des Images et CNRS-LTCI (UMR 5141)46, rue Barrault, 75013 Paris

{likforman|sigelle}@tsi.enst.fr

1 IntroductionLes approches stochastiques, tels que les modèles de Markov cachés (HMM), sont

largement utilisées pour la reconnaissance de la parole et de l’écrit (Elms et al. 1998 ;Hallouli et al. 2002) pour leur capacité à s’adapter aux distorsions élastiques temporelles etspatiales. Cependant ces modèles sont mono-dimensionnels. Une adaptation doit donc êtreréalisée pour les images, par nature bi-dimensionnelles : celles ci sont converties enséquences 1D d’observations le long d’une direction. Une séquence admissibled’observations est par exemple la suite des colonnes de pixels en balayant l’image de gaucheà droite. D’autres séquences sont possibles : vecteurs de caractéristiques sur des fenêtresglissantes, lignes de texte...

Les HMM font l’hypothèse que les observations sont indépendantes conditionnellementaux états cachés, ce qui n’est pas toujours réaliste pour les images. Des extensions des HMMpermettant de mieux prendre en compte l’aspect bi-dimensionnel des images ont ainsi étéproposées avec les modèles pseudo-2D (ou planar HMM) (Gilloux 1994). Plus récemment,des modèles 2D à base de champs de Markov ont été développés (Park et Lee 1998 ; Saon etBelaid 1999 ; Chevalier et al. 2003). En faisant apparaître les dépendances entre variablesd’états ou observations, une modélisation plus fine de phénomènes peut être obtenue. Danscette optique, des modèles probabilistes s’appuyant sur les réseaux bayésiens statiques sontapparus dans le domaine de la reconnaissance de l’écriture en-ligne (Cho et Kim 2003),l’analyse de documents (Souafi 2002) et l’authentification de signatures (Xiao et Leedham,2002). Les réseaux bayésiens dynamiques sont une extension des réseaux statiques quiprennent en compte des séquences variables d’observations. On note ξt, l’ensemble desvariables d’états et d’observations au temps t. Un réseau bayésien dynamique à deux pas detemps (2TBN) est défini par – un réseau initial B1 qui spécifie la distribution initiale des états et les distributions

conditionnelles des états et des observations à t=1– un réseau de transition Btr qui spécifie les distributions P(ξt+1 | ξt ). Ces distributions sont

supposées stationnaires, i.e. indépendantes de t.

Cette étude expérimente des modèles simples mono-flux de type HMM et des modèlescouplés. Les structures couplées sont toutes construites par la mise en correspondance dedeux réseaux simples mono-flux (ajouts de liens dans la structure graphique). Dans notreapplication, les états cachés sont des variables discrètes et les observations sont continues.Les observations sont soit les lignes, soit les colonnes normalisées de pixels d’un caractère,obtenues par balayage séquentiel, soit les deux à la fois. L’évaluation de ces modèles a étéréalisée sur la base de chiffres MNIST (LeCun 1998).

- 61 - RNTI-E-5

Page 30: Egc05 atelier rnti-e-5_(extraits)

Les Reseaux Bayesiens versus d’autres modelesprobabilistes pour le diagnostic multiple de gros

systemes

Veronique Delcroix∗, Mohamed-Amine Maalej∗

Sylvain Piechowiak∗

∗LAMIH, Universite de Valenciennes et du Hainaut-Cambresis, Le Mont Houy, 59313 Valenciennes cedex 9

Veronique.Delcroix,Mohamed-Amine.Maalej,[email protected] ://www.univ-valenciennes.fr/LAMIH/

1 Introduction

Notre travail se situe dans le contexte du diagnostic multiple de systemes fiableset de grande taille. Les systemes que nous considerons sont constitues de composants,relies entre eux par leurs entrees ou sorties. Un composant C est soit en bon etatok(C) soit defaillant ab(C). L’objectif du diagnostic est de trouver le ou les compo-sants defaillants qui expliquent le mieux des observations de panne. Plusieurs aspectsrendent cette tache difficile : la grande taille des systemes consideres implique qu’ungrand nombre de composants peuvent etre defaillants et que la liste des diagnostics cor-respondant a des observations de panne peut etre longue ; de plus, pour les systemesfiables, peu de scenarios de pannes sont connus et ils ne peuvent pas etre utilisespour la recherche des diagnostics. En revanche, la probabilite de defaillance de chaquecomposant est connue. En fonction de ces contraintes pour la recherche des meilleursdiagnostics, les reseaux bayesiens apparaissent comme un modele tres bien adapte.Apres avoir decrit les reseaux bayesiens que nous utilisons, nous presentons notre al-gorithme de diagnostic. Nous comparons ensuite notre approche avec d’autres modelesprobabilistes utilises pour le diagnostic et expliquons en quoi ils ne sont en general pasadaptes au diagnostic multiple de systemes fiables et de grande taille.

2 Definitions et presentation du modele utilise

Un reseau bayesien est un graphe oriente sans circuit dont les nœuds represententles variables du systeme (Becker et Naım, 1999). Dans notre modele, les variables dusysteme incluent les variables d’entrees/sorties des composants et les variables d’etat(ok ou ab) des composants. A chaque nœud est associee une distribution de probabilitesconditionnelles. On appelle observations de pannes un ensemble de variables dont lavaleur est connue et incompatible avec l’etat normal du dispositif : au moins un compo-sant est defaillant. Un etat du systeme represente une affectation d’un etat (ok ou ab)a tous les composants du systeme. Un diagnostic est un etat du systeme coherent avecles observations de panne. Pour simplifier, nous designons parfois un diagnostic commel’ensemble des composants defaillants. Un diagnostic est simple ou multiple selon lenombre de composants defaillants. L’objectif est de calculer les “meilleurs” diagnostics

- 65 - RNTI-E-5

Page 31: Egc05 atelier rnti-e-5_(extraits)

Réseaux bayésiens pour le filtrage d’alarmes dans lessystèmes de détection d’intrusions

Ahmad Faour1,2 Philippe Leray1 Cédric Foll1,3

[email protected] [email protected] [email protected]

1 Laboratoire PSI - FRE CNRS 2645, INSA Rouen, France2 Laboratoire LPM, Université Libanaise, Beyrouth, Liban

3 Rectorat de Rouen, France

1 Introduction

La détection des tentatives d’attaques sur un réseau est une problématique trèsimportante dans le domaine de la sécurité informatique. Les NIDS (Network Intrusion

Detection Systems), systèmes de détection d’intrusions, génèrent tellement d’alertes surun réseau qu’il en devient très difficile de déterminer celles générées par une attaqueréelle. L’utilisation d’outils de raisonnement probabiliste comme les réseaux bayésiens(RB) peut être efficace pour détecter les problèmes réels. Nous allons donc tout d’abordprésenter les systèmes de détection d’intrusions et leurs limites puis passer brièvementen revue l’application de méthodes d’apprentissage à cette problématique. Nous décri-rons enfin notre architecture de filtrage d’alarmes issues de NIDS.

2 Systèmes de détection d’intrusions

Les firewalls utilisés sur les réseaux TCP/IP fonctionnent sur l’analyse des couchesIP et TCP/UDP/ICMP, pour déterminer quelles sont les machines impliquées dansla connexion et à quel service la connexion s’adresse. Ce genre d’approche, bien quenécessaire, se révèle insuffisant dans bien des cas (Chambet, 2002). Il faut donc pousserplus loin l’analyse en examinant aussi les couches réseaux supérieures. Cette tâche, plusdifficile, est dévolue aux NIDS. Ces logiciels fonctionnent le plus souvent par signatures,sur le même principe que les anti-virus (Zimmermann et al., 2002), en répertoriant lesattaques connues. Une alarme est donc générée à chaque fois qu’une trame réseau res-semble à une des attaques répertoriées. Lorsqu’un nouvel exploit (tentative d’intrusionréussie) est répertorié, une signature adaptée sera ajoutée à la base de signatures. Cetteapproche est souvent utilisée conjointement avec une approche statistique dans laquellele NIDS détermine d’abord un profil type du réseau (nombre de paquets échangés, vo-lume des flux, nombre de connections, etc.) et alarme ensuite l’administrateur lorsquele trafic courant dévie de ce profil. Malheureusement, les NIDS émettent généralementune quantité importante d’alarmes que l’administrateur n’est pas capable d’interpréterrapidement.

Depuis (Denning, 1987), les approches à base d’apprentissage statistique proposéespour la détection d’intrusion peuvent être classées en deux types : les méthodes essayantd’opérer avec les mêmes informations que les NIDS classiques (analyse de donnéesréseaux), et celles opérant à partir de données comportementales de plus haut niveau(fichiers de logs de certaines applications ou du système).

- 69 - RNTI-E-5

Page 32: Egc05 atelier rnti-e-5_(extraits)

Causal Inference in Multi-Agent Causal Models

Sam Maes, Stijn Meganck, Bernard Manderick

Computational Modeling Lab,Vrije Universiteit Brussel,Pleinlaan 2 - 1050 Brussel,

sammaes, smeganck, [email protected],http ://como.vub.ac.be

1 Introduction

This paper treats the calculation of the effect of an intervention (also called causaleffect) on a variable from a combination of observational data and some theoreticalassumptions. Observational data implies that the modeler has no way to do experimentsto assess the effect of one variable on some others, instead he possesses data collectedby observing variables in the domain he is investigating.

The theoretical assumptions are represented by a semi-Markovian causal model(SMCM), containing both arrows and bi-directed arcs. An arrow indicates a directcausal relationship between the corresponding variables from cause to effect, meaningthat in the underlying domain there is a stochastic process P(effect |cause) specifyinghow the effect is determined by its cause. Furthermore this stochastic process mustbe autonomous, i.e., changes or interventions in P(effect |cause) may not influence theassignment of other stochastic processes in the domain. A bi-directed arc represents aspurious dependency between two variables due to an unmeasured common cause (Tianand Pearl, 2002), this is also called a confounding factor between the correspondingvariables.

Deciding if a causal effect is identifiable (i.e. can be computed) in a SMCM amountsto assessing whether the assumptions of a diagram are sufficient to calculate the effect ofthe desired intervention from observational data. When all variables of a domain can beobserved, all causal effects are identifiable. In the presence of unmeasured confounders,identifiability becomes an issue (e.g. the causal effect of X on Y is not identifiable inthe causal diagram of Figure 1, since we can not distinguish causal influence from Xto Y form the influence via the unobserved confounder (Pearl, 2000).

X Y

Fig. 1 – The causal effect of X on Y is not identifiable in this SMCM.

In this paper we introduce an algorithm for the identification of causal effects in acontext where no agent has complete access to the overall domain. Instead we consider amulti-agent approach where several agents each observe only a subset of the variables.The main advantages of the multi-agent solution is that the identification of causal

- 73 - RNTI-E-5

Page 33: Egc05 atelier rnti-e-5_(extraits)

Reseaux Bayesiens de Niveau Deux et D-Separation

Linda Smail, Jean-Pierre Raoult

Laboratoire d’Analyse et de Mathematiques Appliquees (CNRS UMR 8050)Universite de Marne-la-Vallee

5 boulevard Descartes, Champs sur Marne 77454 Marne-la-Vallee Cedex [email protected], [email protected]

Resume. Etant donne une famille de variables aleatoires (Xi)i∈I , mu-nie de la structure de reseau bayesien et un sous-ensemble S de I, nousconsiderons le probleme de calcul de la loi de la sous-famille (Xa)a∈S

(resp. la loi de (Xb)b∈S , ou S = I − S, conditionnellement a (Xa)a∈S).Nous mettons en evidence la possibilite de decomposer cette tache en plu-sieurs calculs paralleles dont chacun est associe a une partie de S (resp.de S) ; ces resultats partiels sont ensuite regroupes dans un produit. Dansle cas du calcul de (Xa)a∈S , ceci revient a la mise en place sur S d’unestructure de reseau bayesien de niveau deux.

1 Introduction

Etant donne un reseau bayesien (Xi)i∈I , nous nous interessons, etant donne unepartie non vide S de I, a la loi PS de la sous-famille XS = (Xi)i∈S et a la loi PS/S , dela sous-famille XS = (Xj)j∈S conditionnellement a XS .

Dans les reseaux bayesiens possedant de nombreaux nœuds et fortement connectes,le calcul de lois ou de lois conditionnelles peut faire intervenir des sommations relatives ade tres gros sous-ensembles de l’ensemble des indices I. Il y a donc interet a s’efforcer,au prealable, de decomposer, s’il est possible, ces calculs en plusieurs calculs moinslourds et pouvant etre menes en parallele. Cette decomposition est liee a des proprietesdu graphe definissant le reseau.

Les formules donnant PS et PS/S apparaissent alors comme des produits de facteursdependant isolement des atomes pour des partitions appropriees.

La construction de ces partitions fait intervenir deux relations d’equivalence dansS, toutes deux du type : x et y sont equivalents si et seulement s’ils sont relies, dans ungraphe non oriente (GNO) convenablement deduit du graphe oriente (GO) definissantle reseau bayesien, par une chaıne ne passant pas par S. Deux tels GNO sont consideres ;l’un, classique, est le graphe moral, pour lequel les aretes relient les nœuds joints parun arc ou ceux ayant un enfant en commun ; l’autre, a notre connaissance original, estle graphe hyper-moral, pour lequel les aretes relient les nœuds joints par un arc ou ceuxdont les descendances proches (voir definition dans (Smail 2004) et en 2 ci-dessous) ontune intersection non vide .

La formule de calcul de PS est liee a une structure de reseau bayesien dont les nœudsne sont pas les elements de I mais les atomes d’une partition de I (notion introduiteen (Smail 2003) sous le nom de reseau bayesien de niveau 2).

- 77 - RNTI-E-5

Page 34: Egc05 atelier rnti-e-5_(extraits)

Chapitre 3

Modélisation d’Utilisateurs et Personnalisation de

l’Interaction Homme-Machine �

L’acquisition, la modélisation et le traitement des préférences et besoins d’un utilisateur jouent un rôle central dans le développement de services et de produits web (interaction et dialogue avec l'utilisateur, connaissance client et ciblage de clientèle, etc.). Durant les vingt dernières années, le domaine de la modélisation utilisateur a produit des résultats en terme de méthodes et de théories pour l’analyse et la modélisation de l’interaction à court ou long terme de l’utilisateur avec l’ordinateur et les systèmes informatiques en général. Des techniques de personnalisation de l’interaction homme machine ont été développées, appliquées et évaluées dans des domaines tels que le filtrage d’information, le commerce électronique ou les systèmes éducatifs adaptatifs. Ces résultats sont le fruit de la coopération entre chercheurs de différents domaines, l’intelligence artificielle, l’apprentissage automatique, l’interaction homme machine, la psychologie cognitive, la linguistique, etc. Aujourd’hui, avec le développement d’Internet, la conception de systèmes adaptatifs s’appuyant sur le web ainsi que l’adaptation et la personnalisation d’interfaces sont devenus des aspects cruciaux du développement de bon nombre d’applications. Parmi celles-ci, on peut citer l’accès aux hypermédias culturels, le e-commerce, les guides touristiques, la TV interactive, etc.

Responsables du chapitre : T. Artières, B. Bouchon-Meunier, P. Gallinari, C. Tijus

- 81 - RNTI-E-5

Page 35: Egc05 atelier rnti-e-5_(extraits)

Ce chapitre rassemble des contributions de chercheurs intéressés par la problématique de la modélisation utilisateur au sens large et fait le point sur quelques uns des problèmes génériques du domaine, des applications phares et des méthodes employées.

L’interaction de l’utilisateur avec un dispositif technique est très complexe. Deux articles

s’attachent à une modélisation fine des utilisateurs et de leurs pratiques. (Brézillon et Tijus) s’intéressent à la modélisation d’un utilisateur accomplissant une tâche particulière, ici la recherche d’information tandis que (Tijus et al.) se focalisent sur la problématique de la représentation des connaissances pour modéliser les procédures utilisateurs sur un dispositif technique.

Actuellement, la modélisation d’utilisateurs est utilisée dans la production de services

personnalisés, ces services sont principalement des services distribués. Trois contributions discutent d’architectures de services de ce type. (Anli et al.) présente une architecture multi-agents pour la personnalisation, appliquée à la personnalisation d’itinéraires. (Kanawati) décrit une application de la modélisation utilisateur à la recherche d’information. Enfin, (Razmerita) s’intéresse notamment aux perspectives d’utilisation des nouvelles technologies dans l’apprentissage assisté par ordinateur et reposant sur l’emploi d’ontologies.

Dans ce type d’applications, les modèles d’utilisateurs sont assez frustres et les données

recueillies sur l’utilisateur sont basiques et bruitées, ce sont le plus souvent des traces de navigation.

Deux contributions discutent du traitement des traces de navigation sur un site web ou sur Internet en général. (Murgue) traite du problème du prétraitement des données de log, bruitées par les techniques de cache et les proxys notamment. (Labroche) présente une technique permettant de classifier les sessions de navigation d’utilisateurs sur un site et de les regrouper par similarité. Enfin, (Njike et al) proposent une technique pour automatiser la construction et la définition de modèles d’utilisateurs dans le cadre des hypermédias adaptatifs. Comité de programme et d'organisation :

T. Artières (LIP6, Université Paris 6 - [email protected]) B. Bouchon-Meunier (LIP6, Université Paris 6 - [email protected]) P. Gallinari (LIP6, Université Paris 6 - [email protected]) C. Tijus (Université Paris 8 - [email protected]) N. Carbonell (LORIA, Université Henri Poincare, Nancy) H. Assadi (FT RD) B. Trousse (Inria Sophia) C. de la Higuera (Eurise, Univ. Jean Monnet - Saint Etienne)

- 82 -RNTI-E-5

Page 36: Egc05 atelier rnti-e-5_(extraits)

Représentation contextualisée des pratiques des utilisateurs

Patrick Brézillon *, Charles Tijus *** LIP6, Case 169, Université Paris 6, 8 rue du Capitaine Scott, 75015 Paris

E-mail: [email protected] - http://www-poleia.lip6.fr/~brezil/** Laboratoire Cognition & Usages, Université Paris 8, 2, rue de la Liberté,

93526 Saint-Denis Cedex 02, E-mail: [email protected]

Résumé. Le contexte intervient dans toue étude du comportement humain.Nous présentons les graphes contextuels qui sont utilisés dans de nombreuxdomaines comme l’intelligence artificielle, la psychologie, la sécuritéinformatique, la gestion d’incidents, le diagnostic médical, ... L'idée centralede ce formalisme est la représentation au même niveau des éléments decompréhension d’un utilisateur et des éléments contextuels dans lesquels leséléments de compréhension prennent un sens et ont une validité. Nousdonnons un exemple dans le domaine de la recherche d’information. Cettemodélisation de l’utilisateur au travers de ses actions offre un intérêt pourredéfinir les tâches prescrites dans le cadre du travail collaboratif.

1 Introduction

Le traitement des données contextuelles joue un rôle dans tous les domaines où leraisonnement intervient, comme pour la compréhension, l'interprétation, le diagnostic, ... Cetraitement repose sur une expérience qui n’est généralement pas explicitée, et sur une notion,ce qu’on appelle contexte, qui n’a pas toujours pas une définition consensuelle suffisammentprécise pour être opérationnel (Bazire et al., 2005). Toutefois, une composante consensuellede cette définition est que le contexte est toujours relatif à quelque chose : le contexte d’unraisonnement, le contexte d'une action, le contexte d'un objet, ... Nous nommons focus ceréférent du contexte (Brézillon, 2005) et nous proposons un modèle du raisonnement del’utilisateur, prise comme personne qui comprend, interprète, et diagnostique pour agir sur undispositif, qui est basé sur le traitement contextuel des données.

Dans la réalisation d’une interface, il est bien connu que toute procédure aussi détailléesoit-elle laisse implicite un certain nombre de choses qui font que la procédure n’est jamaisuniverselle : l’interface ne fonctionne pas sur tel ou tel navigateur, les couleurs sont malcalibrées sur un ordinateur, un utilisateur rejette systématiquement les cookies, etc.Clairement, il est nécessaire de prévoir des variations autour de la procédure. Les procéduresthéoriques (et parfaites) sont généralement adaptées par les utilisateurs pour prendre encompte le contexte de leur focus. Le raisonnement pratique de l’utilisateur n'est pas unraisonnement logique et théorique pour lequel l'opération conduit à la conclusion. Aucontraire, le raisonnement pratique a plus le statut d'un raisonnement inductif et probabiliste :la conclusion ne peut être inféré à partir des seules prémisses. Il s’agit d’une situationgénérale. Un exemple montre qu’à partir d’une suite de caractères « A p s E k U O h f P sE », la consigne « parmi les voyelles, barrer la consonne » fait barrer le caractère « P », alorsmême qu’une consonne ne peut être une voyelle (Tijus, 2001) : toutes les voyelles, dans cecontexte étant des majuscules, la conclusion conduit à choisir la consonne en majuscule.

- 83 - RNTI-E-5

Page 37: Egc05 atelier rnti-e-5_(extraits)

Modélisation Sémantique de l’Utilisateur

Charles Tijus, Sébastien Poitrenaud Jean-François Richard

Laboratoire Cognition & Usages

Université Paris 8, 2 rue de la Liberté, F-93526 St Denis cedex 02 [email protected]

Résumé. Notre approche « sémantique de l’utilisabilité », basée sur la catégorisation, correspond à un mode de représentation des connaissances, sous la forme d’un treillis de Galois qui permet de modéliser et simuler les procédures utilisateurs sur un dispositif technique. Cette approche, qui diffère de celles qu’on trouve avec SOAR ou ACT, associe les actions et les procédures aux catégories d’objets, comme propriétés de ces catégories (Poitrenaud, Richard & Tijus, sous presse). L’accès aux actions et procédures a lieu à partir des catégories d’objets. Dans le cadre de cette approche, les erreurs relèvent de méprises catégorielles et l’analogie relève des processus de reconnaissance qui ont lieu lors de la catégorisation. La modélisation et la simulation dans le cadre de cette approche se réalisent avec les formalismes développés par Poitrenaud (1995): ProcOpe et STONE.

1 La sémantique de l’utilisabilité On peut avoir deux points de vue sur l’utilisateur. Un premier point de vue est celui de la

conception de dispositifs qui désire connaître et modéliser ses utilisateurs cible, pour savoir comment personnaliser l’interface, quels liens recommander selon le profil utilisateur, etc. Un deuxième point de vue est celui de l’utilisateur lui-même qui peut se demander pourquoi l’interface ne lui convient pas et pourquoi il n’a pas perçu la signification du lien qui correspondait à sa recherche. Ces deux points de vue sont complémentaires et leur intégration devrait donner lieu à une modélisation plus complète de l’utilisateur. L’approche de la sémantique de l’utilisabilité correspond au second point de vue. Elle découle des recherches menées dans notre laboratoire sur la résolution de problème (Richard, Poitrenaud, & Tijus,1993 ; Richard, Clément & Tijus, 2002). Ces recherches montrent que ce n’est pas l’organisation des actions qui freine une planification réussie, mais la conceptualisation des objets de l’action. D’où la grande différence de difficulté trouvée entre des problèmes isomorphes, de la Tour de Hanoi par exemple, qui ont des habillages différents. Ainsi, le problème de la Tour de Hanoi qui consiste à changer la place de 3 disques de taille différente se résoud en moyenne au 11.4 coups alors que l’isomorphe qui consiste à changer la taille de 3 disques de place différente se résoud en moyenne au bout de 35.5 coups, alors que 7 coups suffisent dans les deux cas. On mesure toute l’importance de la sémantique, c’est-à-dire de la signification accordée aux objets qu’on manipule. Ainsi, le paradigme de la Tour de Hanoi, problème apparemment trivial pour l’informaticien, doit être considéré sérieusement, lorsqu’on découvre les grandes différences de comportement lorsque change l’habillage du problème, c’est-à-dire sa sémantique. C’est aussi un paradigme qui sert de base à la modélisation de l’utilisateur et sert à valider les propositions de modèles.

- 89 - RNTI-E-5

Page 38: Egc05 atelier rnti-e-5_(extraits)

����������� ����������������������

��������������������������� �����������

����������� ��������� ������� ���������� ��������

� �� ����� ����

������ ��� ���� !"#

�� ���� ���$

%�!&"'" (���)������ ����* &

+��������� ���,-���.�.���)������/0�

���1233444/���.�.���)������/0�3�����

����)����

5&� 6����.�� �� ���������

%�!&#57 ����� ����*

���- �)����/0�

���1233444/�)����/0�

���� �� 8�� �� )����*�� �911��)����� ��������:�� �� �9��.����������

�����1���0����� � 1������������� ��)��� �� )���* �� � 1����0���

�9�����)���� ;<�� <8�� =>� �� ��� �9�����)���� ;��*����� .�)�� =>� �

)��0�������� ����)������ ��� ����:�� 0�������� ��)/ <�������� :������� ��:��

�:�:������ ��� �� 1��0�� �� �9����������� 1�������� �� 1������ �� )�1�� )��

��00:����� �1�)��/ ���� 1��1����� ��� 1����0���� ? ��� �9����� ����)�����

1��.�� ���.�� �� ��11��� 1��� � )��)�1���� �� �$��@� �� <�������������

;�<>/ �� �< 0)����� � ������� �� � ���������� ��� �:������ �� ���

��)�������� ��� �� �$��@� ��������: �� :.�����0/ �� �< ��� 11��A�:

1��� � 1������������� �� �9��0������ ����1���/ �� �9��� �)� �9���� ���

������ ��� ����1���� )����)��0� ��� ���� )���* �9����:������ �� ��� ��0����

��� 1����������� :.��������� �� �� ��� ������ ���� � ���� �� ���� �:1�)����/

�� �������������

��� ���.����� ��)��������� �� �9��0������ �� �� � )����)���� �00���� � 1���������:

�9)):��� ? ��� ���� �9��0������ �� 1��� �� 1��� ������ ��� ��� ��11���� �� 1��� ��

1��� .��:� �� ��11����� ��� ���� �9�����)���� �� 1��� �� 1��� ��00:�����/ �� ����������

1��� ��)���)��� ��3�� ��)�.��� �� �9��0������ ��� ��� ��������� �� ������ ��� <8�� ���

�:�:1���� 1������� ��)/ � 1��1�� �� )�� 1����0���� �9))���� 1�������� ��� �����)����

��������� )������ �� ���� �9��� �� �� ��*��/

<��� �:1����� � )���@�� �9�����������: �� 1������� ? �9���������� �� ������.�� 0)������

�9��0������ A�� �9���:������ � 1������������� �� 1�:����� )�� ��� �������� 11��1��:�/

B���� � 1������������� ��� ��0������� �:��.�:��� �9����� �1�)�� �� �9�����)����

1��.��� 0��� �9��C�� �� 1������������� ��� )� )���� ���� A�� � 1���� �� )�1�� ���

��00:����� ���� �9�����)���� ;.�)�� ��*����� =>� � 1���� �� )�1�� ��� ��00:������ 1�����

0���� �9�����)���� ;<�� <8�� �:�:1���� 1������� =>� �� �9������)� ? �9����������/ �����

��C�)��0 ��� �� 0������ �� ��11��� ? � )��)�1���� �� �$��@�� �� 1������������� ;�<> A��

)��.�� )�� ��00:����� �1�)��/

� 1���� �� )�1�� ��� ���� �9�����)���� �� ��� 1�����0���� ������:�� �����0��� 1���

����� A�� �� �$��@� �� 1������������� ���� ��� ���:���� ��� ��� ����������� 1� �11���

- 95 - RNTI-E-5

Page 39: Egc05 atelier rnti-e-5_(extraits)

Réflexions sur l'apport de l'exploration des traces d'usagepour améliorer le tri des résultats des moteurs de recherche

sur le WebRushed Kanawati

LIPN – CNRS UMR 703099 Av. J.B. Clément 93430 Villetaneuse

[email protected]://www-lipn.univ-paris13.fr/~kanawati

Résumé. Nous présentons dans ce papier un système de fouille coopérative dedonnées d'usage de moteurs de recherche sur le Web dont l'objectif estd'améliorer le tri des résultats rendus par un moteur de recherche. Le systèmeest construit selon une architecture multi-agents où chaque utilisateur estassisté par un agent personnel. Les agents coopèrent entre-eux et utilisent laméthodologie du raisonnement à partir de cas pour re-trier les résultats renduspar un moteur de recherche. Nous nous servons de ce système pour 1)présenter notre analyse des choix de conception d’un système d’explorationcoopérative de données d’usage du Web et 2) montrer les problèmes quirestent à résoudre et l’apport attendu des techniques de fouille de donnéesd’usage pour les résoudre.

1 IntroductionLa présentation et le tri des résultats des moteurs de recherche est un problème important

dans le domaine de la recherche d’information sur le Web. En soumettant une requête à unmoteur de recherche l'utilisateur attend en retour un ensemble de documents triés en fonctionde leur pertinence par rapport à ses besoins informationnels. La contre performance desmoteurs existant est le meilleur témoin de la nécessité de nouvelles approches de tri derésultats. Différents travaux se sont intéressés récemment au problème du tri de résultats derecherche. Nous les classifions selon les trois axes suivants :

1. Approches fondées sur l’exploration de la structure du Web (Brin & Page, 1998)(Ding, 2002).

2. Approches fondées sur l’exploration des données d’usage (Chen & Meng, 2000)(Arezki et al., 2004).

3. Approches coopératives ou approches orientées communauté d’utilisateurs(Chidloveski et. al., 2000).

Nous nous intéressons à une approche hybride qu’on qualifie de fouille coopérative dedonnées d’usage. L’idée de base est de permettre à un groupe d’utilisateurs de partagerimplicitement leurs expériences en recherche d’information (Trousse et. al., 1999),(Kanawati, 2003), (Freyne, et. al, 2004). Un premier prototype d’un système d’agentsassistants d’aide au tri des résultat est proposé. Ce système est construit selon unearchitecture égal-à-égal (Peer to Peer). Les agents assistants utilisent la méthodologie du

- 101 - RNTI-E-5

Page 40: Egc05 atelier rnti-e-5_(extraits)

Services contextualisés pour utilisateurs et la modélisation des utilisateurs à base d’ontologies :

défis et perspectives

Liana Razmerita

INRIA, Projet Acacia, 2004 route des Lucioles

06902 Sophia-Antipolis Cedex

[email protected]

http://www-sop.inria.fr/acacia/personnel/Liana.Razmerita/

Résumé. Il existe un besoin d’outils avancés d’apprentissage sur le Web. Le

développement des nouvelles technologies comme le Web sémantique, le

calcul sur grille et les services web ouvrent de nouvelles perspectives et défis

pour la conception d’une nouvelle génération de systèmes d’apprentissage.

Cette nouvelle génération peut être conçue comme des services distribués,

autonomes, contextualisés, services web ou grille. Le papier présente le rôle et

les perspectives des nouvelles technologies pour le développement d’une

nouvelle génération de services d’apprentissage en s’appuyant sur le modèle

utilisateur et sur la modélisation des utilisateurs à base d’ontologies.

1 Introduction

Il existe un besoin d’outils avancés d’apprentissage sur le Web. Malgré des années de

recherche dans le domaine de l’apprentissage assisté par ordinateur, le défi des chercheurs

dans ce domaine est encore de concevoir et fournir de nouveaux outils ou services

d’apprentissage sur le Web. Ces services avancés devraient tenir compte des nombreuses

ressources existantes sur le Web, en intégrant aussi de nouveaux paradigmes pédagogiques.

Traditionnellement ; les systèmes d’apprentissage sont orientés sur le contenu et

l’apprenant est souvent vu comme un simple « absorbeur » d’information. On pense qu’une

nouvelle génération de systèmes avancés d’apprentissage doit intégrer de nouvelles

approches pédagogiques donnant à l’apprenant un rôle actif pour apprendre et construire ses

connaissances. Ces systèmes doivent être plus interactifs, plus collaboratifs dans le sens

qu’ils vont permettre et encourager la collaboration entre les apprenants ; mais ils doivent

aussi intégrer une vision plus centrée sur l’utilisateur, permettant de prendre en compte ses

besoins, ses caractéristiques, ses préférences, etc.

Le développement de nouvelles technologies comme le Web sémantique, le calcul sur

grille, les services Web ouvrent de nouvelles perspectives et défis pour une nouvelle

génération de systèmes d’apprentissage. Cette nouvelle génération de systèmes

d’apprentissage peut être conçue comme des services distribués, ubiquitaires, contextualisés,

services Web ou grille. Le Web contient une multitude de sources d’information et de

connaissance qui peuvent être utilisées comme objets d’apprentissage. Les méta-données

associées avec ces objets d’apprentissages et les caractéristiques de l’utilisateur vont

- 107 - RNTI-E-5

Page 41: Egc05 atelier rnti-e-5_(extraits)

De l’importance du pre-traitement des donnees pourl’utilisation de l’inference grammaticale en

Web Usage Mining

Thierry Murgue

Eurise – Universite Jean Monnet23 rue du docteur Paul Michelon

42023 Saint-Etienne Cedex [email protected]

Resume. Le Web Usage Mining est un processus d’extraction de connais-sance qui permet la detection d’un type de comportement usager sur unsite internet. Cette tache releve de l’extraction de connaissances a par-tir de donnees : plusieurs etapes sont necessaires a la realisation du pro-cessus complet. Les donnees brutes, utilisees et souvent incompletes cor-respondent aux requetes enregistrees par un serveur. Le pre-traitementnecessaire de ses donnees brutes pour les rendre exploitables se situe enamont du processus et est donc tres important. Nous voulons travailler surdes modeles structures, issus de l’inference grammaticale. Nous detaillonsun ensemble de techniques de traitement des donnees brutes et l’evaluonssur des donnees artificielles. Nous proposons, enfin, des experimentationsmettant en evidence l’affectation des algorithmes classiques d’inferencegrammaticale par la mauvaise qualite des logs bruts.

1 Introduction

Le Web Usage Mining a ete introduit pour la premiere fois en 1997 (Cooley et al.1997). Dans cet environnement, la tache est d’extraire de maniere automatique la facondont les utilisateurs naviguent sur un site web. Depuis 1995, Catledge et Pitkow ont etu-die la maniere de categoriser les comportements utilisateurs sur un site web (Catledge1995). Le processus d’extraction de connaissance – pre-traitement, fouille, interpreta-tion – est base sur la disponibilite de donnees fiables : divers travaux on ete menes sur lafacon de traiter les donnees recuperables depuis un site web (Cooley et al. 1999, Pitkow1997, Chevalier et al. 2003). Une grande majorite de chercheurs utilisent de manieresystematique les informations contenues dans les enregistrements du serveur (fichiersde logs), mais ces donnees, sous forme brute, ne sont pas completes : un pre-traitementest donc necessaire. L’etape suivante du Web Usage Mining consiste a apprendre desmodeles de comportement utilisateurs depuis ces donnees. Ainsi, ces dernieres annees,de nombreuses methodes de traitement (Tanassa et al. 2004) et d’apprentissage ontete utilisees dans ce domaine : recherche de sequences frequentes (Frias-Martinez 2002,Gery 2003), travaux sur l’utilisation de modeles structures de type chaıne de Markov oumodele de Markov cache (Hmm) (Pitkow 1999, Bidel et al. 2003). Certains chercheursont notamment travailles sur des modeles grammaticaux : certains (Borges 1999) en uti-lisant des n-grams, d’autres (Karampatziakis et al. 2004) en etudiant le comportement

- 113 - RNTI-E-5

Page 42: Egc05 atelier rnti-e-5_(extraits)

Mesure d’audience sur Internet par populations de fourmis artificielles

Nicolas Labroche

UPMC, LIP6, Pole IA, 8 rue du Capitaine Scott

75015 Paris [email protected]

http://lofti.lip6.fr

Résumé. Nous présentons dans ce travail un outil pour la mesure d’audience sur Internet, reposant sur l’extraction de profils de navigation représentatifs de l’activité des internautes sur les sites. Ces profils sont obtenus par l’application d’un algorithme de classification non supervisée – inspiré du système de reconnaissance chimique des fourmis – sur des sessions de navigations construites à partir des fichiers log du site étudié. Cet algorithme de classification a été associé à une représentation multimodale des sessions utilisateurs permettant d’employer l’ensemble des informations à disposition dans les fichiers log (impacts sur les pages, heure de connexion, durée, séquence des pages, …), ainsi qu’à une mesure de similarité adaptée pour créer les profils de chacun des clusters obtenus. Il reste cependant d’autres modalités (basées sur le contenu des documents accédés) qui pourraient améliorer la capacité de l’outil à donner du sens aux profils découverts.

1 Introduction La mesure d’audience sur Internet s’attache à extraire et à donner du sens aux navigations

des internautes. Ses champs d’applications sont nombreux : personnalisation automatique des sites Web en fonction des pages accédées (Mobasher et al., 1999) ou encore recommandation dynamique de pages aux internautes en fonction de leur navigation passée (Yan et al., 1996). Dans ce cadre, la représentation des navigations des internautes est cruciale car elle détermine le type de recherche d’informations qui pourra être conduit par la suite.

Généralement, les informations de navigation des internautes sur un site Internet sont

extraites d’un fichier log, présent sur le serveur Web, qui recense, pour simplifier et de manière idéale, l’ensemble des demandes de pages du site de la part des internautes. Ces requêtes clientes sont ensuite triées, filtrées et regroupées en sessions qui constituent pour chaque internaute, l’ensemble des informations issues de leur navigation sur un site à un moment donné (Cooley et al., 1999).

Plusieurs représentations des sessions ont été utilisées dans la littérature. Par exemple, le

système WebMiner (Cooley et al., 1999) utilise un vecteur de transactions qui indique pour chacune des pages du site si elle a été accédée au moins une fois durant la session de façon à extraire des règles d’association. Dans Masseglia et al. (1999), les auteurs conservent les dates d’accès à chacune des pages pour extraire des règles séquentielles. D’autres représentations ont été utilisées comme la durée de visite ou le nombre d’impacts par page

- 119 - RNTI-E-5

Page 43: Egc05 atelier rnti-e-5_(extraits)

Apprentissage d’une hiérarchie de concepts pour la conception de modèles de domaine d’hypermédias

Hermine Njike Fotzo, Thierry Artières, Patrick Gallinari, Julien Blanchard, Guillaume

Letellier LIP6, Université Paris 6

8 rue du capitaine Scott, 75015, Paris, France {Prénom.Nom}@lip6.fr

Résumé. Nous décrivons comment apprendre automatiquement une hiérarchie de concepts à partir d'une collection de documents. Les concepts, identifiés par des ensembles de mots-clés, sont organisés en une hiérarchie de type spécialisation/généralisation. Cette hiérarchie peut être utilisée pour construire un modèle de domaine pour des collections de documents hypermédias. Nous proposons des idées sur la façon de construire des modèles d’utilisateurs à partir de tels modèles de domaine. Les modèles d’utilisateurs et de domaine peuvent être visualisés à l’aide d’outils efficaces comme les Treemaps.

1 Introduction Un hypermédia adaptatif est personnalisé, dynamiquement, en fonction de l’utilisateur.

La personnalisation peut consister en une adaptation du contenu de l’hypermédia ou à des aides à la navigation en ajoutant/enlevant des liens (Brusilovsky 1996). La personnalisation repose sur un modèle de l’utilisateur. Il n’existe pas aujourd’hui de consensus sur la définition d’un modèle d’utilisateur, souvent défini de façon ad-hoc, mis à part pour les hypermédias éducatifs et les systèmes tutoriaux (Da Silva 1998, De Bra 2003, Henze 1999). Ces systèmes utilisent un modèle de domaine, conçu manuellement, à partir duquel on définit les modèles d’utilisateurs. Un modèle de domaine est un graphe des concepts abordés dans l’hypermédia, caractérisant l’ensemble des connaissances accessibles dans l’hypermédia. On utilise alors des modèles d’utilisateurs du type Overlay user models, qui partagent la même représentation que le modèle de domaine. Ce sont des vecteurs d’attributs (un pour chaque concept) qui représentent une mesure d’intérêt ou de connaissance de l’utilisateur dans les concepts (Da Silva 1998, De Bra 2003, Kavcic 2000). Les modèles sont mis à jour à partir de la navigation de l'utilisateur. On peut également faire de l'inférence dans ces modèles en utilisant le formalisme des réseaux bayésiens (Da Silva 1998, Henze 1999).

Dans ce papier, nous nous intéressons à la définition automatique d’un modèle de domaine pour un hypermédia quelconque, à partir de son contenu. Il s’agit d’une étape préliminaire pour construire des versions adaptatives de systèmes hypermédias quelconques. Nous présentons ici une approche qui permet d’apprendre automatiquement une hiérarchie des concepts abordés dans un corpus de documents textuels, à partir du contenu de ceux-ci. Cette hiérarchie traduit une relation de spécialisation/généralisation entre les concepts. Comme nous le montrons, cette approche fournit une vue hiérarchique alternative du site web. Cette représentation du contenu thématique d’un site web permet de définir des modèles utilisateurs plus appropriés, en utilisant par exemple le formalisme des modèles bayésiens pour l'inférence. En outre, cette représentation associée à un outil de visualisation (tel que les Treemaps) permet la maintenance et/ou l’analyse des modèles d'utilisateurs.

- 125 - RNTI-E-5

Page 44: Egc05 atelier rnti-e-5_(extraits)

Partie II

_

Extraction de Connaissances

Et

Web

- 131 - RNTI-E-5

Page 45: Egc05 atelier rnti-e-5_(extraits)

Chapitre 4

Métadonnées et Adaptabilité pour les Systèmes d'Information sur le Web �

Les Systèmes d'Information basés sur le Web (SIW) sont à la base du traitement et de la diffusion de larges volumes d'informations sur le Net. S'appuyant sur l'infrastructure sous-jacente, ils permettent, entre autres, de gérer l'information organisée en structure hypermédia. Les limites des outils actuels de gestion de l'information sont essentiellement liées au fait qu'ils sont proposés à un utilisateur “générique”. Dans ce contexte, la notion de Systèmes d'Informations Adaptatifs (SIA) vise à proposer des informations adaptées (tant au niveau du fond que de la présentation) à chaque (groupe d’)individu(s), notamment au travers de systèmes de recommandation, de recherche d'information, de filtrage, basés sur la prise en compte de profils et une personnalisation dynamique. Dans ce contexte, les métadonnées peuvent jouer un double rôle. D'une part, elles sont utilisées pour décrire et identifier les différents types d'information (donnée structurée, texte, image, audio, vidéo) qui participent aux ressources d'un SIW. Les modèles sous-jacents sont, dans ce contexte, définis et exploités pour indexer et rechercher l'information. D'autre part, les métadonnées sont utilisées pour décrire et identifier différents profils utilisateurs. Les modèles sont exploités à des fins de personnalisation et d'adapta/bilité/tivité pour que, à la fois services, contenu et présentation des informations, soient adaptés aux besoins et préférences de l'utilisateur, selon son niveau de connaissance, ses centres d'intérêts, sa disponibilité, son comportement, la configuration du matériel sur le poste de travail utilisé,... Seront mis plus particulièrement en avant dans ce qui suit les formalismes semi-structurés, comme RDF, MPEG-7, OWL, XMLSchema, pour la description des métadonnées, mais aussi les besoins et usages de formalismes plus déclaratifs, comme les ontologies, tant au

Responsables du chapitre : F. Sèdes, J.Gensel, H. Martin

- 133 - RNTI-E-5

Page 46: Egc05 atelier rnti-e-5_(extraits)

niveau des ressources que des requêtes. Ces formalismes sont autant de réponses aux problèmes liés aux contraintes d’accès à l’information pour les ressources à partager, mutualiser, adapter, à l’hétérogénéité desdites ressources, à l’assurance d’une intéropérabilité « sémantique », ceci en l’absence de modèles de références comme alternative aux normes, exhaustives mais lourdes, et un besoin récurrent d’annotations contextualisées. Les connaissances sont à construire et à partager, l’adaptation n’étant plus seulement « physique » mais également sémantique. Nous nous sommes attachés à exposer dans ce chapitre différents points de vue selon différents contextes applicatifs, dans des domaines tels que la télédétection, le biomédical, les web services, l’indexation sémiotique et la création d’œuvres médiatiques. Le point commun de ces travaux, marqués pas un fort contexte pluridisciplinaire, est leur apport à la synthèse et à l'extraction de ces modèles, pour l'interrogation, la personnalisation et l'adaptation de SIW.

Comité de programme et d'organisation :

Jérôme Gensel (LSR-IMAG, Univ. P. Mendès-France, Grenoble, [email protected] ) Hervé Martin (LSR-IMAG, Univ. Joseph Fourier, Grenoble, Herve.Martin @imag.fr ) Florence Sèdes (IRIt, Univ. Paul Sabatier, Toulouse, [email protected]) Ikram Amous-Ben Amors, LARIM, Sfax, Tunisie Laurent Amsaleg, projet TEXMEX, IRISA, Rennes Emmanuel Bruno , SIS, Université de Toulon et du Var Bruno Defude, Institut National des Télécommunications, Evry Chabane Djeraba, LIFL, Université de Lille Mohand-Saïd Hacid, LIRIS, Université Claude Bernard, Lyon Genevieve Jomier, LAMSADE, Université Paris Sorbonne Thérèse Libourel, LIRMM, Université de Montpellier Philippe Lopisteguy , Université de Pau et des Pays de l'Adour, IUT, Bayonne Michel Mainguenaud, INSA Rouen Philippe Mulhem, CLIPS-IMAG, CNRS Elisabeth Murisasco, SIS, Université de Toulon et du Var Marlène Villanova-Oliver, LSR-IMAG, Université Pierre Mendès France, Grenoble

- 134 -RNTI-E-5

Page 47: Egc05 atelier rnti-e-5_(extraits)

Interface adaptable de requêtes pour un service deMétaDonnées

Julien Barde∗, Jacques Divol∗∗

Thérèse Libourel∗∗, Pierre Maurel∗

∗UMR-TETIS, Maison de la télédétection, 500 rue Jean François Breton34093 Montpellier Cedex 05

[email protected], [email protected],∗∗LIRMM, 161 rue Ada, 34392 Montpellier Cedex 05

[email protected], [email protected]

Résumé. Dans le cadre d’un projet pluridisciplinaire relatif à la gestionintégrée du littoral (projet Syscolag), nous proposons un système de mu-tualisation de ressources et de connaissances. Ce système repose sur unservice de métadonnées, une base de données inventaire d’objets géogra-phiques de référence et un vocabulaire thématique co-construit par l’en-semble des partenaires. L’accès aux ressources partagées est guidé par uneinterface adaptable au gré de l’usage et axée sur des critères de recherchethématique, spatiaux et temporels.

1 Introduction

Le projet Syscolag (Systèmes Côtiers et lagunaires) soutenu par la région Languedoc-Roussillon-Septimanie (Inscrit dans le contrat Etat-Région 2000-2006) est un pro-gramme de recherche appliquée, fédérateur et pluridisciplinaire au service d’une mu-tualisation des connaissances et des savoirs. Il a comme perspective l’élaboration d’unobservatoire régional du littoral.Un tel observatoire utilisera une approche proactive : la Gestion Intégrée des ZonesCôtières (Henocque 2001). L’aspect multi-disciplinaire, multi-acteur, multi-ressource,multi-projet de cette approche nécessite la mise en place de méthodologies et d’outilsdivers. Le volet relevant du domaine informatique est principalement dédié à la gestion(stockage, maintenance, traitements) et à la restitution de l’information disponible.L’enjeu est de fournir une restitution adéquate et donc adaptée à la variété de publicsciblés (depuis les chercheurs jusqu’au grand public en passant par les milieux profes-sionnels et décideurs). La réflexion menée au sein du projet a préconisé la mise en placed’une infrastructure à trois niveaux de mutualisation de ressources et de connaissances(Barde et al. 2004). Dans cette proposition, nous présentons les concepts qui régissentl’interface adaptative pour l’aide à la recherche d’informations via le service de mé-tadonnées de notre projet. La section 2 décrira sommairement la mutualisation desressources via les métadonnées, nous aborderons ensuite, section 3, la mutualisationdes connaissances (référentiels et ontologie) et enfin nous décrirons brièvement, section4, comment ces deux aspects collaborent au sein de l’interface d’interrogation.

- 135 - RNTI-E-5

Page 48: Egc05 atelier rnti-e-5_(extraits)

Gestion de connaissances et de données dans l'aide à laconception de Tissue Microarrays

Julie Bourbeillon, Catherine Garbay, Françoise Giroud

Laboratoire TIMC-IMAG, IN3S, Faculté de Médecine, 38706 La Tronche [email protected], [email protected], [email protected]

1 Introduction

La technique des « Tissue MicroArrays » (TMA) est une technologie récente, déjà trèsutilisée en oncologie (Kallioniemi et al., 2001). Selon cette technique: 1) on sélectionne despatients, en fonction de l'étude à réaliser ; 2) un pathologiste analyse une lame histologiquedes biopsies des patients et détermine des régions d'intérêt, puis 3) on réalise le TMA. Pource faire, des carottes de tissu sont prélevées dans les zones prédéfinies du bloc de paraffinede la biopsie (bloc donneur). Ces carottes sont insérées dans un bloc receveur vierge (blocTMA) à partir duquel des lames sont réalisées et traitées selon les méthodesconventionnelles. Des images de ces lames TMA sont acquises puis ensuite partitionnées etfont l'objet d'une annotation et d'une analyse pour quantification de marquage...

Par rapport à des études menées avec des techniques classiques, celles utilisant cettetechnologie permettent des économies de réactifs et de matériel biologique et apportent unedimension statistique au travail du pathologiste. Ces avantages peuvent être complétés par lerecours au concept de lame TMA virtuelle : des images de spots existantes peuvent êtresélectionnées et réagencées pour une nouvelle étude sans construction d'un nouveau bloc.

Même si cette technologie semble prometteuse elle souffre d'un manque de connaissancesformalisées et d'automatisation. Les outils développés actuellement autour de la technique seconsacrent surtout à de la gestion de données (Berman et al., 2003, Henshall, 2003). Il paraîtdonc nécessaire de proposer un outil d'assistance à deux étapes du cycle présenté ci-dessus :

— aide à la conception de blocs TMA réels, par génération de représentations virtuellesde blocs TMA en fonction de l'étude à réaliser,

— accompagnement de la fouille de données par génération de lames TMA virtuellesassociées à des informations pertinentes pour l'étude en cours.

Le système devra générer ces deux types de représentation à la volée selon une requêteutilisateur exprimant le but de l'étude. Afin d'être utiles, ces représentations devront consisteren une composition complexe de données hétérogènes, ce qui a conduit à les considérercomme des documents multimédia adaptés en fonction des besoins utilisateur. Enconséquence, nos travaux s'inscrivent dans la lignée des systèmes d'information adaptatifs(Wu et al, 2002, Brusilovsky, 2002).

Dans cet article nous présentons une approche préliminaire pour formaliser le processusd'adaptation. La section 2 donne un aperçu de notre approche du problème. La section 3présente les besoins de représentation des connaissances pour la mise en place du système.La section 4 introduit un début de réflexion sur l'architecture du futur système.

2 La conception de TMA : analyse du problème

Étant donné une requête, il s'agit de proposer une représentation de lame ou bloc TMApertinente. Ces représentations peuvent être considérées comme des collections de documents

- 141 - RNTI-E-5

Page 49: Egc05 atelier rnti-e-5_(extraits)

Un modèle d'adaptation pour les oeuvres médiatiques

Anis Ouali*, Brigitte Kerhervé* Odile Marcotte*, Paul Landon**

Université du Québec à Montréal

Case postale 8888, succursale Centre-ville, H3C 3P8, Montréal (Québec) Canada

*Département d'informatique http://www.info.uqam.ca

[email protected] {kerherve.brigitte, marcotte.odile}@uqam.ca

**École des arts visuels et médiatiques http://eavm.uqam.ca

[email protected]

Résumé. Les artistes en arts visuels et médiatiques explorent l'utilisation de nouvelles technologies pour créer des oeuvres multimédia et qui sont diffusées en ligne, lors d'expositions ou d'installations. L'utilisation des technologies faites par ces créateurs pose de nombreux défis en termes de mécanismes à mettre en oeuvre pour concevoir, créer, expérimenter et diffuser ces oeuvres. Dans cet article, nous nous intéressons aux mécanismes d'adaptation pour la création d'oeuvres médiatiques adaptatives et interactives. A travers un cas concret, nous proposons un modèle d'adaptation intégrant la gestion de différents types de métadonnées pour réaliser aussi bien l'adaptation sémantique que l'adaptation physique et qui peut être spécialisé selon les besoins spécifiques.

1 Introduction

La plupart des approches d'adaptation de la livraison du contenu multimédia sont centrées sur les problèmes d'allocation de ressources pour prendre en compte différents types d'équipements (téléphone cellulaire, ordinateur de poche, etc.) et différentes conditions de communication (réseaux sans fil, projections HD, etc.).

De nouvelles expérimentations dans la création d'oeuvres audio-vidéo adaptatives, diffusées en ligne ou lors d'expositions permettent d'envisager les approches d'adaptation, non plus comme seulement la résolution d'un problème technique et d'infrastructure mais aussi comme la résolution d'un problème sémantique, à savoir le respect du message artistique.

Nous nous sommes intéressés alors à l'oeuvre « The Man of the Crowd » créée par Paul Landon en 2003. L'interface adaptative de l'installation sert à reproduire le mouvement aléatoire de la foule urbaine par le biais de quatre moniteurs diffusant des séquences vidéo sonorisées montrant plusieurs personnages superposés, marchant à différentes vitesses, directions et profondeurs. Les séquences vidéo diffusées sont organisées en quatre classes: «No Movement» (NM), «light movement» (LM), «medium movement» (MM) et «heavy movement» (HM).

- 147 - RNTI-E-5

Page 50: Egc05 atelier rnti-e-5_(extraits)

Adaptabilité à l’utilisateur dans le contexte des services Web

Céline Lopez-Velasco*, Marlène Villanova-Oliver* Jérôme Gensel*, Hervé Martin*

*Laboratoire LSR-IMAG

BP 72 38402 Saint Martin d’Hères cedex

Grenoble, France [email protected]

http://www-lsr.imag.fr/Les.Personnes/Prenom.Nom

Résumé. Les services Web sont des technologies émergentes permettant une interopérabilité entre les différents acteurs (fournisseurs et demandeurs de services) du fait de leur architecture reposant sur des technologies standard. Cependant à ce jour, aucun des standards des services Web ne prend cependant réellement en charge le concept d’adaptation. Ceci est d’autant plus problématique que les utilisateurs de services Web attendent d’eux non seulement qu’ils répondant à leur besoin mais aussi qu’ils soient adaptés à leur profil (caractéristique personnelles, et celles de leur environnement). Nous proposons une extension du standard de description des services Web (WSDL), appelée AWSDL, afin de supporter l’adaptation des services Web. Un module a été développé pour mettre en correspondance les descriptions AWSDL des Services Web Adaptés (SWA) et les demandes des utilisateurs.

1 Introduction Les Services Web (SW) permettent aujourd’hui l’utilisation d’applications distantes par

d’autres applications. L’architecture sous-jacente aux services Web repose sur trois standards : WSDL – Web Service Description Language (Chinnici et al., 2004) qui permet de décrire un service, UDDI1 (Universal, Discovery, Description, and Integration) qui permet de référencer ce service, et SOAP – Simple Object Access Protocol (Mitra, 2003) qui décrit la communication avec ce service. Une fois publiés, ces SW sont potentiellement utilisables par des utilisateurs de profils hétérogènes à partir de différents dispositifs d’accès (station de travail fixe, téléphone portable, etc.). Pour faire face à cette diversité, il apparaît donc souhaitable pour les concepteurs de SW de disposer de moyens visant à rendre ces services adaptés, afin d’assurer leur pérennité mais aussi leur utilisabilité.

Les travaux de recherche existants sur l’adaptabilité des SW mettent l’accent sur le contexte d’utilisation (configuration matérielle utilisée, bande passante, etc.) mais peu sur le profil de l’utilisateur. En effet, (Paques et al., 2003) et (Amor et al., 2003) ne prennent pas en compte le destinataire de l’adaptabilité (l’utilisateur et son contexte). Le travail présenté dans cet article propose d’intégrer le profil de l’utilisateur dans WSDL. Ce profil comprend tant les caractéristiques personnelles de l’utilisateur que les caractéristiques du contexte d’utilisation du SW. L’extension proposée, appelée AWSDL (Adapted Web Service

1 www.uddi.org

- 153 - RNTI-E-5

Page 51: Egc05 atelier rnti-e-5_(extraits)

Génération de descripteurs : interrogation d’images satellitaires par les métadonnées

Florence Sèdes *

* IRIT

118 Route de Narbonne 31062 Toulouse cedex 4

[email protected]

1 Introduction La télédétection est un domaine d’investigation riche et prometteur pour les

problématiques de modélisation et d’interrogation, comme en témoignent les énormes volumes de données stockées, toujours inexploitées. Le passage à la très haute résolution permettra en effet de visualiser et d’analyser des objets jamais vus auparavant en télédétection (voitures, bâtiments, arbres, etc.), posant de nouveaux challenges en terme de passage à l’échelle et de prise en compte de l’hétérogénéité des images pour acquérir des informations sur la scène.

Notre approche tente de renouveler les processus classiques d’exploitation de cette imagerie pour en permettre une exploitation plus complète, compte tenu de la faible utilisation actuelle de ce type d’approche en télédétection, afin de parvenir à des processus d’analyse et d’enrichissement via l’extraction et la modélisation d’attributs et caractéristiques élicités. L’objectif ici n’est pas de discuter des nombreuses méthodes de segmentation disponibles (Gonzalez et al., 1993 ; Pal et al., 1993) mais d’aider à accroître leur « couverture », dans le but de trouver la méthode la plus adaptée à une famille d’application donnée, et de permettre une recherche d’information a posteriori. Le processus adopté permet de disposer d’une information sur les relations spatiales entre les objets pendant la segmentation, générant d’une part des attributs propres aux objets, et d’autre part des attributs d’organisation spatiale entre eux. C’est cette dualité qui rend original le couplage de la méthode de segmentation développée et la construction de descripteurs via les métadonnées ainsi extraites. La description appropriée des objets devra permettre de les traiter sans accéder à l’image initiale, seulement en manipulant les métadonnées via des requêtes (Smith et al., 1999), hormis pour l’affichage des résultats.

2 Construction des descripteurs

La figure 1 détaille les étapes du processus de segmentation qui guide la construction des

descripteurs. Les caractéristiques extraites sur chaque région et sur ses relations avec les régions adjacentes sont autant de métadonnées sur lesquelles il est possible d’évaluer des prédicats et conditions. Deux catégories de caractéristiques issues de l’extraction sont donc associées au sein des descripteurs, (i) les caractéristiques intrinsèques, spécifiques de

- 159 - RNTI-E-5

Page 52: Egc05 atelier rnti-e-5_(extraits)

Chapitre 5

Extraction et Gestion de Connaissances dans les

Environnements Informatiques pour l’Apprentissage Humain �

Cet atelier a été proposé dans le but de faire se rencontrer les deux communautés EGC et

EIAH afin de débuter ou développer des collaborations. Ces deux communautés peuvent collaborer fructueusement en apportant d'un côté un nombre important de données recueillies lors de l'utilisation des EIAH et de l'autre côté des techniques appropriées pour en extraire les connaissances pertinentes.

En effet, lors de l'utilisation des EIAH, de nombreuses informations sur le comportement ou

le parcours des apprenants peuvent être recueillies, afin d'en extraire des connaissances pour le diagnostic, ou pour modifier le comportement des EIAH en fonction des connaissances acquises sur l'apprenant. D'autre part, le développement important des TICE et de leurs usages conduit à la création de nombreuses ressources pédagogiques numériques. Pour pouvoir les retrouver et les réutiliser, il est indispensable de les indexer. Un travail conséquent en cours concerne la définition des métadonnées et d'ontologies dans ce domaine. Une indexation performante des ressources pédagogiques permettra de créer de nouvelles formations à partir de ces ressources et pourra ensuite donner la possibilité à l'apprenant de construire sa formation à partir des composants qui lui sembleront les plus appropriés.

Du côté EGC, de nombreuses méthodes de recherche d'informations et de gestion de celles-ci sont élaborées, améliorées et validées depuis plusieurs années. Mais l'application de ces

Responsables du chapitre : F. Le Calvez, F.-X. Jollois, H. Giroire

- 165 - RNTI-E-5

Page 53: Egc05 atelier rnti-e-5_(extraits)

techniques sur des données réelles est toujours riche d'enseignement sur les possibilités qu'elles offrent effectivement et leurs performances. Ainsi, la possibilité de pouvoir réaliser des essais sur des données provenant d'EIAH, en partenariat avec des experts du domaine ayant permis de récolter et de créer ces données, est une perspective très intéressante pour les chercheurs du domaine EGC.

Au cours de l'atelier, cinq présentations ont été faites et une table ronde coanimée par

Monique Grandbastien (Loria, Nancy) et Edwin Diday (Ceremade, Paris 9) a permis de discuter des différentes techniques utilisables dans ces problématiques.

La limitation du nombre de pages ne nous a pas permis de rassembler toutes les contributions, nous avons retenu l'article de Pierre Camps et ses coauteurs qui développent une plate forme pédagogique pour faire émerger une conscience de groupe et qui ont besoin d'extraire des connaissances à partir de l'utilisation de cette plate-forme pour la rendre adaptative. Le projet Pepite, présenté par Elisabeth Delozanne et ses coauteurs est un projet pluridisciplinaire qui a pour objectif de permettre un diagnostic fin des compétences des élèves en algèbre élémentaire. Les connaissances extraites à partir des réponses des élèves à des exercices permettent d'établir un profil cognitif de ces élèves. L'article de Sylvain Dehors et ses coauteurs est un exemple de collaboration entre deux équipes de recherche l'une de la communauté Gestion de connaissances et Web sémantique et l'autre dans le domaine du e-learning. Enfin Agathe Merceron présente les résultats de son étude statistique sur l'utilisation des traces fournies par la résolution d'exercices de Logic-ITA par des étudiants de l'université de Sydney.

Lors de la discussion, il est apparu que l'utilisation de méthodes de Fouille de Données pouvait apporter un plus indéniable dans l'analyse et le traitement des informations recueillies par le biais des EIAH. Notamment, les treillis de Gallois, les règles d'association et les méthodes d'analyse de données sont des techniques très intéressantes à exploiter dans ce domaine, toutes capables de travailler sur des données de taille réduite, caractéristique courante en EIAH.

Nous remercions tous les participants de cet atelier qui nous ont permis de débattre de ces

problématiques et espérons que cet atelier sera le début de fructueuses collaborations.

Comité de programme et d'organisation : Françoise Le Calvez (CRIP5-Paris5) François-Xavier Jollois (CRIP5-Paris5) Hélène Giroire (LIP6-Paris6)

- 166 -RNTI-E-5

Page 54: Egc05 atelier rnti-e-5_(extraits)

Extraction d' Information Pédagogique à l'aide de Fouilles de Données: une étude de cas

Agathe Merceron

Département Génie Informatique

Ecole Supérieure d' Ingénieurs Léonard de Vinci, PULV 92916 Paris La Défense - Cedex (France)

[email protected] http://aldebaran.devinci.fr/~merceron

Résumé. Les systèmes d'apprentissage qui utilisent les TIC peuvent enregistrer sous forme électronique de nombreuses données. Ces données peuvent être fouillées par des logiciels adéquats pour en retirer des informations pédagogiques. Cet article illustre cette approche en prenant pour exemple le Logic-ITA, un système d'apprentissage pour les preuves formelles en logique.

1 Introduction L'utilisation des Technologies de l' Information et de la Communication dans les

systèmes d'apprentissage permet de recueillir de nombreuses données sous forme électronique, donc traitables par logiciels.

Les fouilles de données (Han et Kamber 2001) recouvrent des techniques diverses aussi bien dans les méthodes que dans les buts. Des logiciels de fouilles de données sont de plus en plus utilisés dans les entreprises commerciales, en particulier dans les banques et dans la téléphonie mobile. Le but de cet article est de montrer un exemple de leur utilisation dans l'enseignement pour en tirer des informations à but pédagogique. Les données utilisées sont le travail d' étudiants enregistré par le Logic-ITA, un outil tuteur en ligne dans le domaine de la logique des propositions.

2 Les données du Logic-ITA Le Logic-ITA (Merceron et Yacef 2004b) est un logiciel accessible sur le Web qui

permet aux étudiants de s'exercer à faire des dérivations formelles en logique des propositions. Il est utilisé à l' Université de Sydney depuis 2001. Un exercice en dérivation formelle est composé d'un ensemble de formules : les hypothèses et la conclusion. Le but d'un exercice est de dériver la conclusion à partir des hypothèses. Pour cela, l'étudiant doit dériver de nouvelles formules, pas à pas, en utilisant des règles de logique et en les appliquant aux formules déjà dérivées, ou aux hypothèses, jusqu'à ce que la conclusion soit obtenue. Il n'y a pas nécessairement une solution unique et tout cheminement valide est accepté. Le module expert vérifie que chaque pas entré par l'étudiant est valide, et donne un message d'erreur et éventuellement une indication si le pas est incorrect. Le Logic-ITA est en libre-service et est offert aux étudiants comme une ressource complémentaire au cours en face à face. En conséquence, il n'y a ni un nombre fixe ni un ensemble fixe d'exercices faits par tous les étudiants.

Le modèle d'un apprenant enregistre toutes ses réponses, ce qui comprend tous les pas qu'il a entrés, y compris les erreurs, pour la résolution d'un exercice. Un module permet au professeur de rassembler tous ces modèles dans une base données qui peut être interrogée et

- 167 - RNTI-E-5

Page 55: Egc05 atelier rnti-e-5_(extraits)

Un Web sémantique de formation par questionnement

Sylvain Dehors*, Catherine Faron-Zucker**, Alain Giboin*, Jean-Paul Stromboni**

* ACACIA, INRIA, 2004 route des Lucioles, BP 93, 06902 Sophia-Antipolis cedex {Sylvain.Dehors, Alain.Giboin}@sophia.inria.fr

** MAINLINE, I3S, 930 route des Colles, BP 145, 06903 Sophia-Antipolis cedex {Catherine.Faron, strombon}@essi.fr

Résumé. Nous présentons dans cet article un EIAH conçu et développé selon des méthodes et techniques du Web sémantique et de l’ingénierie des connaissances. L'environnement d'apprentissage est conçu comme une mémoire de formation et le système que nous avons développé constitue un Web sémantique de formation (par extension de la notion de Web sémantique d’entreprise). Une approche d'acquisition et de gestion des connaissances a été adoptée pour expliciter la stratégie pédagogique d'un enseignant, acquérir des ressources pédagogiques à partir d'un document de cours initial et organiser ces ressources. La visualisation des ressources et la navigation de l'apprenant dans la mémoire ou le Web de formation est basée sur l'utilisation d'un moteur de recherche sémantique.

1 Introduction Dans le cadre de l'AS WebLearn, nous avons élaboré un EIAH guidé par des questions en

appliquant des techniques et des méthodes du Web sémantique et de l’ingénierie des connaissances. Nous envisageons l'environnement d'apprentissage comme une forme de Web sémantique communautaire. Nous l'appelons un « Web sémantique de formation ». Les ressources pédagogiques y sont annotées dans le langage RDF et des requêtes sémantiques permettent d'accéder à ces ressources. Nous reposons pour cela sur le moteur de recherche sémantique Corese (Corby et al. 2004). Les réponses aux requêtes permettent des visualisations des ressources augmentées de liens hypertextuels, de sorte que celles-ci sont organisées en une mémoire de formation (Abel et al. 2004).

Nous décrivons dans la section suivante l'approche pédagogique dite « par questionnement ». La section 3 aborde la modélisation que nous avons faite de cette approche, en particulier l'ontologie que nous avons élaborée et les annotations sémantiques des ressources pédagogiques. La partie 4 décrit comment cette ontologie et ces annotations sont intégrées dans un Web sémantique de formation offrant aux apprenants une navigation « intelligente » dans les ressources pédagogiques de la formation.

2 Apprentissage individuel par questionnement

Dans un EIAH, la « mise en ligne » du cours consiste généralement à présenter le contenu du cours sous la forme d'un hypertexte. De nombreux exemples illustrent cette méthode : AHA (DeBra et al. 2003), Metalinks (Murray 2003), (Brusilovsky 2003). Chacun de ces systèmes présente des possibilités d'adaptation à l'utilisateur (documents dynamiques, liens adaptés, etc.). L'activité de navigation (browsing) de l’apprenant combinée avec des

- 173 - RNTI-E-5

Page 56: Egc05 atelier rnti-e-5_(extraits)

Extraction de pépites de connaissances dans des réponses

d’élèves en langage naturel

Sylvie Normand-Assadi*, Lalina Coulange*

Elisabeth Delozanne**, Brigitte Grugeon***

* IUFM de Créteil, Rue Jean Macé, 94861 BONNEUIL Cedex, France

(sylvie normand, lalina.coulange)@creteil.iufm.fr

** CRIP5 - Paris V, 45-46 rue des Saints-Pères, 75 006 PARIS, France

[email protected]

http://www.math-info.univ-paris5.fr/~delozanne

*** IUFM d’Amiens 49, boulevard de Châteaudun 80044 AMIENS CEDEX,

[email protected]

Résumé. Le projet Pépite a pour objectif la construction d’un diagnostic des

compétences d’élèves en algèbre élémentaire permettant aux enseignants de

gérer la diversité cognitive de leurs élèves. Dans cet article, nous présentons

une étude pluridisciplinaire (linguistique, didactique et informatique),

s’appuyant sur un corpus de productions d’élèves utilisant le logiciel Pépite.

Le corpus est analysé selon les points de vue croisés de la linguistique et de la

didactique. L’objectif de cette démarche est d'améliorer l'évaluation des

réponses d’élèves aux questions ouvertes quand ces derniers répondent avec

leurs propres mots. Après avoir situé notre étude, nous présentons la

méthodologie retenue et les premiers résultats. Nous montrons ensuite la

pertinence de ces résultats avec le point de vue de la recherche sur

l’enseignement des mathématiques. Nous terminons par les perspectives

ouvertes par ce travail en nous interrogeant sur les apports d’approches EGC à

la problématique du diagnostic de compétences.

1 Introduction L’analyse des réponses d’élèves exprimées dans leurs propres mots est un verrou sur

lequel butent de nombreux projets en EIAH (Rosé et al 2003a). Beaucoup de travaux

s’intéressent à l’analyse automatique des explications produites en langage naturel et des

interactions verbales d’étudiants (avec des pairs, avec l’enseignant), ou se centrent sur

l’utilisation de modèles linguistiques dans la conception de logiciels d’apprentissage (Aleven

et al 2002), (Arroyo et al 2001), (Rosé et al 2003). Comment prendre en compte la diversité des

productions spontanées d’élèves « dans leurs propres mots » dans une analyse informatisée ?

En quoi la nature de ces productions peut-elle nous informer sur les apprentissages ou leurs

dysfonctionnements ? Notre étude vise à apporter des éléments de réponses à ces questions,

dans le contexte très spécifique d’un logiciel d’évaluation diagnostique en algèbre

élémentaire. Cette étude se situe dans le cadre du projet Pépite qui vise à concevoir un

logiciel pour évaluer des compétences en algèbre élémentaire. Il s’agit d’analyser les erreurs

et les cohérences de raisonnement d’élèves en algèbre en tenant compte de leurs réponses à

un test couvrant les principales dimensions de la compétence algébrique de base. L’objectif

est, à partir de ce diagnostic de proposer des situations d’apprentissage adaptées aux profils

d’élèves ainsi repérés. Le logiciel Pépite ne se contente pas de répertorier des erreurs, mais

- 179 - RNTI-E-5

Page 57: Egc05 atelier rnti-e-5_(extraits)

Un cadre pour l’étude des comportements sur une plate-forme pédagogique : du parcours individuel à la conscience du

groupe

P. Camps*,**,***, M.-F. Canut*, A. Péninou*, F. Sedes*,**

*LGC, IUT "A" Paul Sabatier, 129 Av. de Rangueil, BP 67701, F-31077 Toulouse Cedex 4 {canut, peninou}@iut-blagnac.fr

**IRIT, 118 route de Narbonne, F-31062 Toulouse Cedex 4, [email protected] ***ENFA, Ecole Nationale de Formation Agronomique

2 route de Narbonne, BP 22687, F-31326 CASTANET-TOLOSAN Cedex [email protected]

RÉSUMÉ. Lorsqu'ils sont fortement prescriptifs, les Environnement Interactifs pour l'Apprentissage Humain (EIAH) cloisonnent les utilisateurs entre eux. Pour mettre en valeur le travail de chacun, nous voulons faire prendre conscience aux utilisateurs qu'ils font partie d'un groupe qui a des intérêts convergents. Nous pensons qu'un système adaptatif est le support approprié pour faire émerger la prise de conscience d'un groupe et ainsi développer des pratiques coopératives. Nous proposons de formaliser une architecture qui définit des services autonomes opérant en tâche de fond, pour extraire du système les données pertinentes déclenchant les mécanismes de signalisation adéquat. Notre support d'expérimentation est une plateforme pour la formation des professeurs stagiaires de l'enseignement agricole public.

1 Problématique (Moran et al., 2002) considèrent que même le web traditionnel, bien que partagé par des

millions d'utilisateurs qui y naviguent depuis leur environnement personnel, demeure pour eux un endroit "privé", car utilisé sans prendre conscience des autres, de leurs intérêts ou de leur comportement. Pourtant, malgré la multiplicité de ces (micro)espaces privés, malgré l'utilisation en apparence individuelle de ressources partagées, l'observation de similarités/régularités de comportements et la récurrence dans l'utilisation de ces fonctionnalités atteste, d'un point de vue "macro", de l'aide que pourrait apporter la conscience de ces potentialités collectives. En restreignant notre cadre d'étude aux systèmes où l'activité de l'utilisateur est prescrite, nous proposons de formaliser une architecture qui, bien que définissant des services autonomes opérant en tâche de fond, vise à faire émerger une conscience de groupe et ainsi favoriser la coopération entre utilisateurs, entre utilisateurs et système, afin de dépasser le contexte a priori individuel.

2 Etat de l'art

Dans la perspective de mise en oeuvre de mécanismes de prise de conscience de

comportements potentiellement collectifs, nous nous sommes intéressés aux travaux portant sur la conscience de groupe (ou awareness) et sur l'adaptativité.

La conscience de groupe (ou awareness) est à la fois un état (somme des connaissances extraites de l'environnement) et un processus (mise à jour de ces connaissances par

- 185 - RNTI-E-5

Page 58: Egc05 atelier rnti-e-5_(extraits)

Chapitre 6

De la construction d’entrepôts de données

à l’extraction de connaissances sur grilles �

L'évolution technologique en matière de moyens d’acquisition, de stockage et de puissance de calcul des machines a conduit à la prolifération de grandes masses de données dans différents domaines. Très souvent, ces données sont hétérogènes provenant de différentes sources géographiquement réparties, et disséminent des connaissances insoupçonnées. Les attentes d’interprétation, d’analyse, de recoupement de ces données représentent aujourd’hui, et plus encore dans le futur, un défi majeur.

Fournissant une infrastructure cohérente alliant puissance de calcul, dynamicité, sécurité et

capacité de stockage et de partage de gros volumes de données, les grilles informatiques apparaissent comme des candidates naturelles pour relever un tel défi. Néanmoins, l’exploitation d’une telle infrastructure de manière efficace n’est possible que si un certain nombre de verrous scientifiques et technologiques sont levés : organisation et stockage des données, optimisation des accès aux données, sécurité, etc. Ces verrous constituent autant de problématiques suscitant de nombreuses activités de recherche soutenues par les Actions Concertées Incitatives (ACI) du Ministère de la Recherche telles que Masse de données, IMPBio, Grid, Sécurité, etc.

Le but de ce chapitre est de traiter certaines de ces problématiques notamment celles portant sur la construction d’entrepôts de données distribués, l’optimisation des accès aux données et l’extraction de connaissances dans le contexte des grilles informatiques. Ces problématiques ont fait l’objet de trois articles ayant été sélectionnés dans le cadre du premier atelier sur

Responsables du chapitre : N. Melab, E.-G. Talbi

- 191 - RNTI-E-5

Page 59: Egc05 atelier rnti-e-5_(extraits)

l’« Extraction et Gestion Parallèles Distribuées des Connaissances », organisé conjointement avec la conférence « Extraction et Gestion des Connaissances » (EGC2005).

• Pascal Wehrle, Maryvonne Miquel, Anne Tchounikine. Entrepôts de données sur

grilles de calcul. La technologie des entrepôts de données et les outils OLAP permettent de recueillir et organiser de grandes masses de données et de naviguer sur des vues matérialisées au moyen d’opérateurs adaptés (opérateurs OLAP). De tradition, les entrepôts de données ont pour vocation la centralisation d’un ensemble de données multi-source, préalablement nettoyées et homogénéisées puis mises sous un schéma commun, le schéma de l’entrepôt. Cet article propose un modèle d’architecture distribuée pour la construction d’entrepôts de données sur grilles informatiques. Y sont abordés les problèmes de répartition des données, de leur indexation et leur échange entre nœuds de la grille.

• Yonny Cardenas, Jean-Marc Mierson, Lionel Brunie. Service de Cache pour les

Grilles de Calcul. L’accès aux données d’un entrepôt se traduit par l’exécution de requêtes, parfois complexes, sur des bases de données distribuées sur la grille. Les données manipulées sont toujours associées à des méta-données décrivant, entre autres, le contexte d’acquisition et l’interprétation de ces données. Cependant, la gestion de caches n’est que peu abordée en tenant compte de la sémantique des données, et donc des méta-données associées. Or, l’accès aux données n’est efficace que si l’accès et la gestion complète des méta-données sont prises en compte. Cet article présente une architecture de cache collaboratif sur grilles basée sur l’exploitation de méta-données. Celle-ci est constituée d’un ensemble de caches répartis et d’une couche de coopération permettant leur collaboration. Cette architecture est très intéressante pour les applications nécessitant un fort mouvement de données, telles que les applications d’extraction de connaissances.

• Sébastien Cahon, Nordine Melab, El-Ghazali Talbi. Sélection d’attributs en fouille

de données sur grilles. Le développement d’applications, notamment d’extraction de connaissances, sur grilles informatiques nécessite de re-penser les algorithmes existants pour en assurer le passage à l’échelle. La complexité des grilles rend cet exercice souvent difficile. Ce qui a conduit à l’émergence d’intergiciels ou middlewares permettant de simplifier cette tâche en rendant l’accès au parallélisme et à la distribution transparents à l’utilisateur. Le but de cet article est de décrire une plate-forme logicielle ou framework open source d’aide au développement de méthodes d’optimisation approchées ou méta-heuristiques parallèles distribuées sur grilles. Cette plate-forme est appliquée à un problème d’extraction de connaissances à grande échelle dans le domaine de la spectroscopie proche infrarouge. Il s’agit de découvrir en utilisant une approche enveloppante des modèles de prédiction à partir d’un échantillon de spectres. L’application a été expérimentée sur une grille de 122 machines. Les résultats obtenus

- 192 -RNTI-E-5

Page 60: Egc05 atelier rnti-e-5_(extraits)

montrent l’efficacité de l’approche utilisée tant en terme de précision des modèles extraits qu’en terme de performance à l’exécution.

Comité de programme et d'organisation : Nordine Melab (LIFL - CNRS UMR 8022 - melab,@lifl.fr) El-Ghazali Talbi (LIFL - CNRS UMR 8022 - [email protected])

- 193 - RNTI-E-5

Page 61: Egc05 atelier rnti-e-5_(extraits)

Entrepôts de données sur grilles de calculPascal Wehrle, Maryvonne Miquel, Anne Tchounikine

LIRIS UMR 5205 INSA, Campus de la Doua,

Bâtiment Blaise Pascal (501), 20, avenue Albert Einstein 69621 VILLEURBANNE CEDEX

<prenom>.<nom>@insa-lyon.frhttp://liris.cnrs.fr

1 IntroductionL'objectif d’un entrepôt de données est de mettre à disposition des outils d'aide à la

décision à partir de grands volumes de données produits par des systèmes d'informations deproduction (Inmon 1992). Les « dimensions » du modèle multidimensionnel représentent lesaxes d'analyse et sont hiérarchisées en niveaux de détail. Les données sont modélisées sousforme d’hypercubes navigables grâce aux outils OLAP (On Line Analytical Processing). Lastructure interne classique d'un entrepôt de données est celle du schéma en étoile, introduitpar Kimball (Kimball 1996). Celui-ci est constitué d'une table de faits centrale contenant lesdonnées les plus détaillées de l'entrepôt, appelées « faits » ou « mesures ». Celles-ci sontassociées via des clés étrangères à des tables de dimension accueillant les données concernantles axes d'analyse. Afin d'améliorer les temps de réponse aux requêtes, des agrégats commepar exemple la somme ou la moyenne sur les faits sont pré-calculés au sein de l'entrepôt.

Les besoins croissants en termes de capacité de traitement et de stockage causés par laconception et l'exploitation d'entrepôts de données de plus en plus complexes et volumineuxpar exemple dans le secteur geno-médical (Brunie et al. 2003) favorisent l'utilisation desystèmes distribués puissants. Le concept récent des grilles de calcul fournit une approchedécentralisée à la construction d'infrastructures à hautes performances efficientes,économiques et extensibles dont les principes de base sont exposés par Foster (Foster 2003).Leurs services de gestion et d'information mettent à disposition un accès transparent à ungrand nombre de ressources hétérogènes distantes dans le but d'offrir à l'utilisateur unequalité de service « non triviale ».

Le modèle d'architecture proposé dans cet article a pour objectif l'intégration d'unentrepôt de données sur une infrastructure de grille de calcul. Les avantages principaux d'undéploiement de grands volumes de données détaillées et de leurs agrégats sur une grille sontles possibilités de traitement et d'accès parallèles, de stockage et d'échange décentralisés desdonnées ou résultats de requêtes. Du coté utilisateur, l'objectif est de proposer un serviced'entrepôt aux spécialistes connectés à différents points d'accès de la grille.

2 Identification et fragmentation des donnéesL'entrepôt de données doit être entièrement réparti parmi les noeuds de la grille afin de

s'adapter à l'infrastructure de grille de calcul et de permettre une gestion et un accèsdécentralisé. Pour faciliter la recherche et l'échange de données entre noeuds de la grille nousintroduisons une méthode d'identification unique et globale des données de l'entrepôt.Des identifiants uniques pour les données les plus détaillées sont facilement trouvés grâceaux membres de dimension directement associés aux faits. Il est important pour une gestionefficace des ensembles de données de pouvoir ordonner et comparer ces identifiants.

- 195 - RNTI-E-5

Page 62: Egc05 atelier rnti-e-5_(extraits)

Service de Cache pour les Grilles de Calcul 1

Yonny Cardenas, Jean-Marc Pierson et Lionel Brunie LIRIS, CNRS UMR 5205

INSA de Lyon, Bât. B. Pascal, 7 av. Jean Capelle, 69621 Villeurbanne cedex, France

<prenom>.<nom>@liris.cnrs.fr http://liris.cnrs.fr

Résumé. Nous proposons un système fédérateur de caches pour les grilles que les applications de la grille utilisent comme un service de cache uniforme. Le système est fondé sur le concept de l'activité de données où les applications partagent et réutilisent l'information sémantique liée à l'activité des données sous la forme de métadonnées. Ces métadonnées représentent la connaissance sur les données et sur leur gestion. Elles permettent d'optimiser, suivant le contenu et l'utilisation de ces données, leur placement, leur recherche, leur durée de vie et leur pertinence vis-à-vis de leur exploitation.

1 Introduction Les grilles de calcul sont la conséquence de l'évolution des systèmes distribués. Leur

principale caractéristique est la capacité à réunir dynamiquement des ressources distribuées pour offrir des moyens de calcul et de stockage à grande échelle. Dans ce cadre, plusieurs institutions peuvent établir une « organisation virtuelle » à partir de ces infrastructures informatiques (Foster et al. 2003). Ainsi, les grilles de calcul mettent en oeuvre la technologie permettant l'intégration et le partage de données entre différentes organisations.

Les mécanismes d'accès aux données qui sont disponibles aujourd'hui dans les intergiciels de grille OGSA-WSRF (Globus 2005) sont assez rudimentaires pour le traitement et la gestion de données complexes, ce qui est le cas par exemple dans le domaine médical, domaine cible du projet RagTime 1. Cela amène potentiellement à une prolifération de copies des données alors même que les mécanismes d'utilisation des métadonnées sur la structure, la disponibilité et la localisation de ces données ne sont pas assez avancés. La gestion des métadonnées sur la grille souffre de l'absence de mécanismes de haut niveau pour le partage d'information. Ce partage permettrait aux applications d'exploiter efficacement (en particulier pour des applications d'extraction des connaissances) la disponibilité de certaines données présentes sur la grille. Le service de cache pour grilles présenté ici a comme double objectif de permettre un accès global aux données dispersées dans la grille et d'optimiser l'usage des ressources de données (stockage et communication des données).

1 Ce travail est soutenu par la Région Rhône-Alpes (project RagTime), et l'ACI Masse de Données.

- 199 - RNTI-E-5

Page 63: Egc05 atelier rnti-e-5_(extraits)

Sélection d’attributs en fouille de données sur grilles 1

Sébastien Cahon, Nouredine Melab et El-Ghazali Talbi Laboratoire d’Informatique Fondamentale de Lille

UMR CNRS 8022, Cité scientifique INRIA Futurs – DOLPHIN

59655 Villeneuve d’Ascq cedex <prenom>.<nom>@lifl.fr http://www.lifl.fr/OPAC/

1 Introduction En Data Mining, les données manipulées sont généralement larges et denses. Aussi, leur

exploitation se révèle difficile en pratique. Le Data Mining Hautes Performances (DMHP) (Zaki 1999) s'applique à l'analyse efficace de telles masses de données. Différentes approches combinent la mise en oeuvre de méthodes performantes et extensibles (heuristiques), et le déploiement d'algorithmes sur architectures parallèles ou distribuées. A l'instar des techniques d'échantillonnage et de discrétisation, la sélection d'attributs constitue un troisième aspect, orienté « données », du DMHP. En effet, selon l'objet de l'étude, un certain nombre d'attributs s'avèrent non pertinents, signifiant que leur valeurs n'affectent en rien la procédure de traitement. D'autres, également inutiles, sont dits redondants i.e. fortement corrélés à d'autres champs de la structure n'apportant que peu d'information utile. Ceci justifie une sélection préalable des attributs, afin de réduire le coût de l'analyse de ces données.

On distingue généralement deux classes de méthodes selon que la sélection tienne compte ou non des résultats mesurés en phase d'apprentissage (Kohavi et al. 1996). Dans la première approche, dite « filtrante », la sélection se réalise une et une seule fois, avant le traitement et se base généralement sur une mesure de distance entre les enregistrements ou de similitude entre les attributs. Au contraire, l'approche « enveloppante » procède par cycles, composé chacun d'une étape de sélection puis d'exploitation des enregistrements réduits. On réitère le procédé où chaque nouvelle sélection générée est optimisée en tenant compte de la qualité du précédent modèle déduit. Cette approche est reconnue plus rigoureuse et la sélection est adaptée au processus d'extraction de connaissances, mais également plus coûteuse, puisqu'il convient d'appliquer tout un processus d'apprentissage pour chacune des sélections candidates. L'exploitation des grilles (Foster et al. 1999) permet, outre la distribution des calculs, le déploiement de modèles de résolution robustes basés sur l'hybridation d'algorithmes (Talbi 2002).

Ce chapitre est organisé ainsi : nous présentons d'abord le problème de sélection d'attributs en spectroscopie proche infra-rouge. Puis, nous proposons un algorithme génétique coopératif parallèle pour la résolution du problème. Enfin, avant de conclure, nous présentons les résultats expérimentaux obtenus sur une grille de 122 machines en utilisant la plate-forme ParadisEO-CMW dédiée à la conception de métaheuristiques parallèles hybrides sur grilles.

1 Ce travail a été réalisé dans le cadre du projet Géno-Médicale (GGM) de l’ACI Masse de données.

- 203 - RNTI-E-5

Page 64: Egc05 atelier rnti-e-5_(extraits)

Chapitre 7

Extraction de motifs temporels pour la

détection en ligne de situations critiques�

La détection en ligne de situations critiques est un domaine dont l'importance grandit et les applications sont multiples, qu'il s'agisse de vidéo-surveillance (surveillance d'incidents dans les parkings par exemple), de monitoring en médecine (détection d'alarmes chez les patients en anesthésie-réanimation par exemple), de surveillance de l'environnement (surveillance des évolutions climatiques par exemple) ou d'assistance à la conduite de process ou de véhicules.

L'extraction peut se faire à partir de données soit récoltées directement à partir des capteurs

(et mémorisées dans des bases de données), soit résultant d'une simulation. L'extraction peut utiliser des techniques supervisées ou non. La parenté entre ces différents problèmes provient du caractère temporel des données, de leur hétérogénéité et de leur grande dimensionnalité. Un autre problème est la complexité de cette extraction en raison de la difficulté à contraindre la recherche de tels motifs temporels.

L'objectif premier de cet atelier était de faire se rencontrer des chercheurs travaillant sur ce thème et sur des applications variées afin de créer échanges et discussions. Cet objectif fut largement atteint puisque vingt huit personnes se sont inscrites à l'atelier.

Responsable du chapitre : R. Quiniou

- 209 - RNTI-E-5

Page 65: Egc05 atelier rnti-e-5_(extraits)

Par ailleurs, une session discussion était réservée à des présentations courtes sur des problématiques ou des applications motivantes et suscitant des questions. Huit communications ont été présentées lors de l'atelier parmi lesquelles cinq ont été retenues pour ces actes. Elles sont représentatives des présentations effectuées et abordent des aspects aussi variés que l'abstraction temporelle symbolique de signaux issus de capteurs ou l'extraction et l'apprentissage de motifs temporels dans des domaines tels que la télésurveillance médicale à domicile, la supervision de réseaux de télécommunications ou la détection dynamique de conflits ethno-politiques. Comité de programme et d'organisation :

Marie-Odile Cordier (IRISA, Rennes) Michel Dojat (INSERM U594, Grenoble) Catherine Garbay (TIMC, Grenoble) René Quiniou (IRISA, Rennes) Michèle Rombaut (LIS, Grenoble)

- 210 -RNTI-E-5

Page 66: Egc05 atelier rnti-e-5_(extraits)

Apprentissage relationnel de motifs temporels

Marie-Odile Cordier∗, Rene Quiniou∗,IRISA

Campus de BeaulieuF-35042 RENNES Cedex

{Marie-Odile.Cordier,Rene.Quiniou}@irisa.frhttp ://www.irisa.fr/dream/site/

Resume. Nous presentons deux exp´eriences d’apprentissage relationnel de mo-tifs temporels comportant des contraintes num´eriques - des chroniques - `a par-tir de series temporelles. La premi`ere concerne l’apprentissage d’arythmiescardiaques `a partir d’electrocardiogrammes. La deuxi`eme realise l’apprentis-sage de r`egles predisant la d´egradation de la qualit´e de service dans un r´eseaude telecommunications `a partir de donn´ees d’exploitation. L’influence de lamethode de discr´etisation et de segmentation des donn´ees sur la qualit´e desresultats est discut´ee.

1 Introduction

Une maniere de realiser la supervision de syst`emes dynamiques, tels des proc´edes indus-triels ou des patients en unit´e de soins intensifs, consiste `a rechercher dans les valeurs fourniespar un ensemble de capteurs des configurations particuli`eres, indicatrices de comportementspathologiques. Les configurations les plus simples sont des changements notables sur la ten-dance d’une variable indiqu´ee par la valeur d’un capteur. Bien souvent, une simple variation surla tendance, baisse ou hausse plus ou moins brutale, n’est pas suffisamment discriminante etplusieurs variations se produisant sur une ou plusieurs variables doivent ˆetre prises en comptesimultanement. De plus, la dur´ee des variations ainsi que leur espacement sont souvent desindications precieuses permettant de mieux diagnostiquer les ph´enomenes auxquels le syst`emeobserve est soumis. Les chroniques (Dousson et al. 1993; Dousson et Vu Duong 1999) sontparticulierement bien adapt´ees pour repr´esenter de telles configurations complexes : une chro-nique comprend un ensemble d’´evenements soumis `a des contraintes temporelles portant surles delais minimum et maximum entre leurs occurrences respectives.

La detection en ligne de situations critiques consiste `a reconnaˆıtre de telles chroniques eninstanciant les ´evenements sp´ecifies dans la chronique `a desevenements observ´es sur le flotde donnees en entr´ee eta verifier, au fur et `a mesure de l’instanciation, que les contraintesspecifiees sont bien respect´ees. Parmi les avantages de cette m´ethode on trouve le fait qu’iln’est pas n´ecessaire que les ´evenements sp´ecifies par une chronique soient contigus dans leflot d’entree (des ´evenements parasites peuvent apparaˆıtre entre les ´evenements recherch´es).

- 211 - RNTI-E-5

Page 67: Egc05 atelier rnti-e-5_(extraits)

Extraction non supervisee de motifs temporels,multidimensionnels et heterogenes

Application a la telesurveillance medicale a domicile

Florence Duchene∗, Catherine Garbay∗ et Vincent Rialle∗ ∗∗

∗Laboratoire TIMC-IMAG, Faculte de medecine de [email protected], [email protected]

∗∗Departement d’Informatique Medicale (SIIM), Hopital Michallon, [email protected]

Resume. Une methode generique pour l’extraction non supervisee demotifs dans des sequences temporelles multidimensionnelles et heterogenesest proposee, puis experimentee pour l’identification des comportementsrecurrents d’une personne a domicile. L’objectif est de concevoir un syste-me d’apprentissage des habitudes de vie, a partir des donnees de capteurs,pour la detection d’evolutions critiques a long terme.

1 Introduction

Dans l’objectif de detecter les evolutions critiques a long terme de personnes adomicile, on souhaite mettre en place un systeme d’apprentissage d’un profil compor-temental dans la vie quotidienne. Toute modification des activites habituelles pouvantcorrespondre a une degradation de l’etat de sante, un ecart par rapport a ce profilest considere inquietant. Il s’agit d’extraire des motifs “haut niveau” de sequencestemporelles “bas niveau” collectees de capteurs installes au domicile. Un motif est lerepresentant d’une classe de sous-sequences recurrentes, et correspond a un comporte-ment type de la personne. Les caracteristiques de ce problene sont les suivantes :

1. Methode – L’extraction de motifs est non supervisee pour s’adapter aux speci-ficites individuelles de comportement et au manque de connaissances a priori.

2. Sequences temporelles – Les sequences analysees sont multidimensionnelles,heterogenes (donnees qualitatives ou quantitatives), et mixtes : elles contiennenta la fois des sous-sequences representatives de motifs et des “non motifs”.

3. Motifs – On recherche des motifs multidimensionnels afin d’eviter une sur-simplification du systeme observe, et la non detection de certaines evolutionscritiques. Par ailleurs, les instances d’un motif ont les caracteristiques suivantes :– Variabilite dans les valeurs, due a celle des comportements humains.– Presence d’interruptions dans la realisation d’une activite (toilettes, etc.).– Deformations et translation dans le temps, car une meme activite se

repete a des instants et sur des durees variables.

Dans ce contexte non supervise, et concernant de larges ensembles de donnees tem-porelles, l’extraction de motifs se rapporte a un probleme de fouille de donnees tempo-relles (Antunes 2001, Roddick 2002). Pour prendre en compte l’ecart entre le bas niveaudes donnees des capteurs et les objectifs d’apprentissage a long terme, plusieurs niveaux

- 217 - RNTI-E-5

Page 68: Egc05 atelier rnti-e-5_(extraits)

Améliorer la découverte de chroniques par une découpe intelligente d'un log d'alarmes

Françoise Fessant, Christophe Dousson, Fabrice Clérot

France Télécom R&D, 2 avenue P. Marzin, 22307 Lannion

{francoise.fessant, christophe.dousson, fabrice.clerot}@francetelecom.com http://www.rd.francetelecom.com

Résumé. Cet article décrit une méthode de prétraitement destinée à faciliter la découverte de motifs fréquents dans un log d'alarmes. Au cours d'une première étape les types d'alarmes qui présentent un comportement temporel similaire sont regroupés à l'aide d'une carte auto-organisatrice. Puis on recherche les parties du log qui sont riches en alarmes pour les différents groupes. Des sous logs sont construits à partir des alarmes des zones sélectionnées. La méthode a été validée sur un log provenant d'un réseau ATM.

1 Introduction La complexité croissante des réseaux de télécommunications nécessite le développement

d'outils de supervision et de corrélation d'alarmes pour aider les opérateurs à contrôler leurs réseaux. Ces outils sont chargés de diminuer la quantité d'informations remontée et de focaliser l'attention de l'opérateur sur des problèmes critiques. Le principal obstacle à la mise en œuvre de ces outils est la difficulté d'acquisition de l'expertise nécessaire à leur fonctionnement (le plus souvent sous forme de règles, Moller et al. 1995, Nygate 1995).

Le logiciel FACE (Frequency Analyser for Chronicle Extraction) apporte une aide à l'acquisition d'expertise en analysant les journaux d'alarmes. A partir de la fréquence d'apparition des alarmes, FACE va découvrir et construire automatiquement plusieurs motifs temporels plus ou moins complexes qui se sont produits un certain nombre de fois dans le log (ces motifs sont baptisés « modèles de chronique », Dousson et al. 1999). FACE peut aider à réduire le flot d'alarmes présenté à l'opérateur lors de la supervision : si une chronique correspond à un défaut de fonctionnement elle sera remontée à l’opérateur, sinon celle-ci pourra être filtrée. La qualification défaut/normal d’une chronique reste du ressort d'un expert chargé d'analyser les modèles de chroniques découverts par les algorithmes.

Le processus de recherche de chroniques implémenté dans FACE repose sur une exploration exhaustive des instances des chroniques dans le log et est donc très consommateur d'espace mémoire. Le facteur principal responsable de cette explosion est la taille du log.

Actuellement les utilisateurs de FACE, pour s'affranchir de ce problème, sont amenés à sélectionner certains types d'alarmes et/ou certaines périodes temporelles dans le log de manière à extraire des morceaux du log qui puissent être traités par l'outil. Le but du travail décrit ici est de permettre l'extraction automatique de morceaux du log pertinents de façon à s'affranchir de l'étape manuelle de prétraitement.

- 223 - RNTI-E-5

Page 69: Egc05 atelier rnti-e-5_(extraits)

Extraction de motifs temporels pour la détection dynamique de conflits ethno-politiques

Laure Mouillet* **, Bernadette Bouchon-Meunier*, Emmanuel Collain**

* UPMC, LIP6, Pole IA 8 rue du Capitaine Scott

75015 Paris France

[email protected] http://www.lip6.fr

**Thales, division Systèmes Terre et Interarmées 160 boulevard de Valmy

92704 Colombes France

{Emmanuel.Collain, Laure.Mouillet}@fr.thalesgroup.com http://www.thalesgroup.com

Résumé. Nous présentons une réalisation en cours sur l'extraction de motifs temporels à partir de séquences d'événements dans le cadre de la détection dy-namique des conflits ethno-politiques. Notre contexte d'application présente plusieurs difficultés : le phénomène que l'on cherche à modéliser est fortement variable et les données sont bruitées. Mais nous disposons d'une connaissance a priori du domaine qui peut être exploitée pour guider l'apprentissage en contraignant l'espace de recherche des motifs. Nous proposons une méthode supervisée d'apprentissage de scénarios dont l'originalité est d'utiliser une me-sure de pertinence qualitative par opposition aux mesures basées sur la fré-quence. Cette méthode intègre des concepts de logique floue.

1 Introduction Les travaux présentés dans cet article s'inscrivent dans un projet de détection dynamique

des conflits ethno-politiques. Cependant la méthode présentée dans ce rapport est générale et peut être appliquée à d'autres types de situations à surveiller. Nous appelons conflits ethno-politiques les conflits armés internes opposant le gouvernement à un groupe ethnique ou politique qui revendique du territoire, un droit de participation plus active au pouvoir ou encore un meilleur statut. Ces conflits sont particulièrement surveillés d'une part à cause des catastrophes humanitaires qu'ils engendrent et d'autre part parce qu'ils risquent de remettre en cause la stabilité de la région dans laquelle ils se produisent. Par la suite, nous les appelons plus simplement crises. La détection est qualifiée de dynamique car elle prend en compte des événements et permet de suivre la situation au jour le jour.

Le but de nos travaux est d'aider les experts du domaine à constituer une base de scéna-rios décrivant des déroulements typiques de crises. Ces scénarios sont modélisés dans le formalisme des gabarits (Collain 1995), (Eude 1998). Un gabarit décrit les types d’événements qui participent au scénario et les contraintes qui s’appliquent aux événements ou aux couples d’événements. Les gabarits alimentent un système de reconnaissance de scé-

- 229 - RNTI-E-5

Page 70: Egc05 atelier rnti-e-5_(extraits)

Vers une analyse de la dynamique des paramètres physiologiques en Unité de Soins Intensifs

S. Sharshar*, M-C. Chambrin*

* EA 2689, INSERM IFR 114 ITM, Bât. Vancostenobel, CH&U de Lille, Place de Verdun

F-59037 Lille Cedex [email protected] [email protected]

Résumé. Le monitorage des paramètres physiologiques en milieu de Réanimation génère un flux abondant et continu de données. L’extraction et la synthèse des informations sont une étape obligatoire pour tout système d’aide à la décision. L’Analyse de la Tendance Linéaire par Morceaux (A.T.L.M.) est une méthode originale d’analyse de la dynamique qui utilise deux niveaux d’interprétation. Le premier niveau, monoparamétrique, exprime la variation de chaque paramètre en quatre classes (constant, diminue, augmente, transitoire) selon la méthode décrite dans (Calvelo et al. 2001). Le second niveau, multiparamétrique, définit le comportement du système par une variable continue ; l'introduction de la connaissance du domaine est alors nécessaire pour différencier des états. La combinaison des deux niveaux d’informations permet l’élaboration de scénarios. Le propos de ce document est d'exposer la méthode sur des signaux simulés présentant des modifications pouvant s’observer en clinique et d’introduire les perspectives offertes par son implémentation en ligne.

1 Introduction De façon générale, l’approche de l’aide à la décision peut être exprimée en termes de

transformation de paramètres en données puis en information, enfin en connaissance (Coiera 1994, Mora et al. 1993). Le passage d’un niveau d’abstraction au suivant implique de mettre en œuvre des moyens de transcodage pour effectuer le passage d’un système de représentation à un autre. Cette chaîne d’abstraction (Calvelo 1999) peut être schématisée en un processus qui comprend :

1. L’acquisition des paramètres, 2. Le traitement univarié des paramètres, 3. Le traitement multivarié des paramètres, 4. L’intégration des connaissances du domaine, 5. La présentation des différentes informations au personnel soignant. La connaissance du domaine peut intervenir à chacune des étapes 1 à 3 mais sans pour

autant être nécessaire. L’étape 1 fait appel aux procédés classiques du traitement de signal. Elle est, pour les paramètres étudiés, déjà intégrée aux moniteurs. L’A.T.L.M. ou Analyse de la Tendance Linéaire par Morceaux s’applique aux étapes 2 et 3 de ce processus d’abstraction en n’introduisant l’intervention de l’expertise qu’en bout de chaîne.

L’A.T.L.M. procède en différentes étapes détaillées dans la section 2. Pour illustrer les résultats de la méthode, nous avons choisi 6 paramètres simulés a à f reportés sur la figure 1.

- 235 - RNTI-E-5

Page 71: Egc05 atelier rnti-e-5_(extraits)

Partie III

_

Données Complexes

- 243 - RNTI-E-5

Page 72: Egc05 atelier rnti-e-5_(extraits)

Chapitre 8

Fouille de données complexes dans un processus

d'extraction des connaissances

L’atelier sur la fouille de données complexes dans un processus d’extraction de connaissances

est organisé à l'instigation du groupe de travail « Fouilles de Données Complexes » (http://morgon.univ-lyon2.fr/GT-FDC/) et s’inscrit dans le cadre de la conférence EGC. La première édition de cet atelier avait pris place au sein d’EGC2004 à Clermont-Ferrand.

L'objectif de cet atelier est de dresser un panorama des travaux récents dans le domaine de la fouille de données complexes par des articles présentant un état de l'art ou des perspectives ouvertes dans ce domaine. Avec cette deuxième édition nous avons voulu reprendre et étendre cet objectif. Ainsi, en plus des communications longues ou courtes, nous avons proposé une session exposant des problématiques de recherche (position papers). Cette session a permis d’offrir un tour d’horizon sur des recherches récemment enclenchées dans le domaine de la fouille de données complexes.

Enfin, nous avons voulu que la grande variété de thèmes abordés par les papiers sélectionnés pour cette édition de l’atelier permette de couvrir un large spectre de ce que l’on peut entendre par « fouille de données complexes ». Cette diversité fut un élément constructif pour la réunion du groupe de travail qui s’est tenue à la fin de cette journée.

Responsables du chapitre : P. Gançarski, F. Masseglia

- 245 - RNTI-E-5

Page 73: Egc05 atelier rnti-e-5_(extraits)

Le recueil d’articles proposé dans cet ouvrage

Sélectionner les articles à paraître dans cet ouvrage était une tâche délicate en raison de la qualité des papiers retenus lors de l’atelier, mais aussi de leur grand nombre. Dans le présent ouvrage, nous avons proposé d’inscrire les articles qui ont été acceptés en « version longue » pour une communication orale afin d’offrir un spectre aussi large que possible sur les travaux actuels du domaine. Quelques mots sur la fouille de données complexes

Dans tous les domaines, les données à traiter pour y extraire de la connaissance utilisable sont de plus en plus complexes et volumineuses. Ainsi est-on amené à devoir manipuler des données :

• Souvent non structurées • Issues de diverses provenances comme des capteurs ou sources physiques

d'informations variées ; • Représentant la même information à des dates différentes ; • Regroupant différents types d'informations (images, textes) ou encore de différentes

natures • (logs, contenu de documents, ontologies, etc.).

De plus, la fouille de données complexes ne doit plus être considérée comme un processus

isolé mais davantage comme une des étapes du processus plus général d'extraction de connaissances à partir de données (ECD). En effet, les difficultés liées à la complexité des données se répercutent sur toutes les étapes du processus d’ECD. Les thèmes liés à la fouille de données complexes peuvent donc comprendre :

• Pré-traitement, structuration et organisation des données ; • Données manquantes ou erronées ; • Fusion de données et de résultats ; • Processus et méthodes de fouille de données complexes ; • Utilisation des connaissances (domaine analysé ou domaine de l'analyste) en ECD

complexe ; • Post-traitement (tri, filtres, lisibilité) ; • Visualisation et aide à l'interprétation des résultats ; • Applications et retours d'expériences (Web, sciences du vivant).

Comité de programme et d'organisation : Aufaure Marie-Aude (SUPELEC) Masseglia Florent (INRIA) Bouet Marinette (LIMOS) Morin Annie (IRISA) Boussaid Omar (ERIC) Napoli Amedeo (LORIA) Briand Henri (IRIN) Nugier Sylvaine (EDF)

- 246 -RNTI-E-5

Page 74: Egc05 atelier rnti-e-5_(extraits)

Djeraba Chabane (LIFL) Petit Jean-Marc (LIMOS) Elfaouzi Nour-Eddin (INRETS) Philipp-Foliguet Sylvie (ENSEA) Fertil Bernard (IMED) Poncelet Pascal (LGI2P) Gallinari Patrick (LIP6) Saidi-Glandus Alexandre (LIRIS) Gancarski Pierre (LSIIT) Teisseire Maguelonne (LIRMM) Hacid Mohand-Said (LIRIS) Trousse Brigitte (INRIA) Hebrail Georges (ENST) Vrain Christel (LIFO) Lebart Ludovic (CNRS & ENST) Wemmert Cedric (LSIIT) Lechevallier Yves (INRIA) Zeitouni Karine (PRISM) Martin Arnaud (ENSIETA) Zighed Djamel (ERIC)

Remerciements

Les responsables de l’atelier tiennent à remercier : • Les auteurs pour la qualité de leurs contributions. • Les membres du comité de lecture pour leur travail indispensable à la qualité de cet

atelier. • Florence CLOPPET et Chabane DJERABA, responsables des ateliers pour EGC

2005. • Nicole VINCENT présidente du comité d’organisation d’EGC 2005. • Fabrice ROSSI : relecteur additionnel qui a travaillé dans des délais très courts.

- 247 - RNTI-E-5

Page 75: Egc05 atelier rnti-e-5_(extraits)

Extraction d’indices spatiaux et temporelsdans des sequences video couleur

Sebastien Lefevre∗, Nicole Vincent∗

∗ LSIIT – Universite Louis Pasteur (Strasbourg I)Parc d’Innovation, Bd Brant, BP 10413, 67412 Illkirch Cedex

[email protected]∗∗ CRIP5 – Universite Rene Descartes (Paris V)45 rue des Saints Peres, 75270 Paris Cedex 06

[email protected]

Resume. Dans cet article, nous considerons les sequences video cou-leur comme des donnees complexes. Notre contribution porte sur deuxmethodes adaptees a ce type de donnees et permettant d’extraire desindices spatiaux et temporels. Nous pensons que ces methodes peuventetre integrees avec succes dans un processus plus complexe de fouille dedonnees multimedia, aspect qui ne sera pas aborde ici. Les methodespresentees sont basees sur l’espace Teinte Saturation Luminance. L’ex-traction d’indices spatiaux est assimilee au probleme de la separation dufond et des objets, resolu par une approche multiresolution ne necessitantqu’une seule image. L’extraction d’indices temporels correspond a la detec-tion des changements de plans dans une sequence d’images, obtenue parl’utilisation de mesures de distances independantes du contexte. Les ca-racteristiques communes de nos deux methodes sont l’utilisation de l’es-pace TSL, l’efficacite calculatoire, et la robustesse aux artefacts. Nousillustrons ces approches par des resultats obtenus sur des sequences videosportives.

1 Introduction

A l’ere de la societe de l’information et de la communication, les donnees numeriquesoccupent une place de plus en plus importante et il devient necessaire de disposerd’outils adaptes pour les traiter, les synthetiser, les fouiller. En particulier, les sequencesvideo issues des canaux televisuels fournissent des volumes de donnees dont la taille nepermet plus aujourd’hui un parcours lineaire. L’acces aux elements pertinents requiertla description des donnees par des indices.

Nous nous interessons ici au probleme de l’extraction d’indices dans les sequencesvideo. Puisque celles-ci sont le plus souvent composees d’images couleur, nous pro-posons d’utiliser l’espace couleur Teinte Saturation Luminance qui fournit des ca-racteristiques interessantes. En se basant sur cet espace, nous cherchons tout d’aborda extraire des indices spatiaux, que nous assimilons aux differents elements contenusdans les images : les objets et l’arriere-plan de la scene. Puis nous nous focalisonssur l’extraction d’indices temporels representant les limites des differents plans d’unesequence. Notre article sera donc organise de la maniere suivante : apres avoir presente

- 249 - RNTI-E-5

Page 76: Egc05 atelier rnti-e-5_(extraits)

Fusion de classifieurs pour la classification d’images sonar

Arnaud Martin

ENSIETA / E3I2, EA38762, rue Francois Verny, 29806 Brest cedex 9

[email protected]://www.ensieta.fr/e3i2

Resume. Nous presentons dans ce papier des approches de fusion d’informa-tions haut niveau applicables pour des donnees numeriques ou des donnees sym-boliques. Nous etudions l’interet des telles approches particulierement pour lafusion de classifieurs. Une etude comparative est presentee dans le cadre de lacaracterisation des fonds marins a partir d’images sonar. Reconnaıtre le type desediments sur des images sonar est un probleme difficile en soi en partie a causede la complexite des donnees. Nous comparons les approches de fusion d’infor-mations haut niveau et montrons le gain obtenu.

1 Introduction

La fusion d’informations est apparue afin de gerer des quantites tres importantes de donneesmultisources dans le domaine militaire. Depuis quelques annees des methodes de fusion ontete adaptees et developpees pour des applications en traitement du signal. Plusieurs sens sontdonnes a la fusion d’informations, nous reprenons ici la definition proposee par (Bloch 2003) :La fusion d’informations consiste a combiner des informations issues de plusieurs sources afind’aider a la prise de decision.

Nous ne cherchons pas ici a reduire les redondances contenues dans les informations issuesde plusieurs sources, mais au contraire a en tenir compte afin d’ameliorer la prise de decision.De meme nous cherchons a modeliser au mieux les differentes imperfections des donnees(imprecisions, incertitudes, conflit, ambiguıte, incompletude, fiabilite des sources, ...) non paspour les supprimer, mais encore pour l’aide a la decision.

Differents niveaux de fusion ont ete propose dans la litterature. Ce qui est communementretenu, est une division en trois niveaux (Dasarathy 1997), celui des donnees (ou bas niveau),celui des caracteristiques (i.e. des parametres extraits) (ou fusion de niveau intermediaire) etcelui des decisions (ou fusion de haut niveau).

Le choix du niveau de fusion doit se faire en fonction des donnees disponibles et de l’archi-tecture de la fusion retenue (centralisee, distribuee, ...) qui sont liees a l’application recherchee.Ainsi, nous pouvons chercher a fusionner des informations issues de differents capteurs telsque des radars de frequences differentes afin d’estimer au mieux la reflexion d’une cible. Dansce cas une approche de fusion bas niveau sera preferable.

Dans ce papier, nous considerons une application dans le cadre de la classification. Plu-sieurs classifieurs peuvent fournir une information sur la classe de l’objet observe. Ainsi, nousretenons des approches de fusion haut niveau pour resoudre un tel probleme. Les donnees ex-primant une decision peuvent etre de type numerique (tel que les sorties des classifieurs) ousymbolique (tel que les classes decidees par les classifieurs exprimees sous forme de sym-

- 259 - RNTI-E-5

Page 77: Egc05 atelier rnti-e-5_(extraits)

Fouille de collections de documents en vue d’une caractérisation thématique

de connaissances textuelles

Abdenour Mokrane, Gérard Dray, Pascal Poncelet

Groupe Connaissance et Systèmes Complexes LGI2P – Site EERIE – EMA

Parc scientifique Georges Besse, 30035 Nîmes cedex 1 - France Tél : +33 (0)4 66 38 70 94 Fax : +33 (0)4 66 38 70 74

{abdenour.mokrane, gerard.dray, pascal.poncelet}@ema.fr

Résumé. De nos jours, les entreprises, organismes ou individus se trouvent submergés par la quantité d'information et de documents disponibles. Les utilisateurs ne sont plus capables d’analyser ou d’appréhender ces informations dans leur globalité. Dans ce contexte, il devient indispensable de proposer de nouvelles méthodes pour extraire et caractériser de manière automatique les informations contenues dans les bases documentaires. Nous proposons dans cet article l’approche IC-Doc de caractérisation automatique et thématique du contenu de collections de documents textuels. IC-Doc est basée sur une méthode originale d’extraction et de classification de connaissances textuelles prenant en considération les co-occurrences contextuelles et le partage de contextes entre les différents termes représentatifs du contenu. IC-Doc permet ainsi une extraction automatique de KDMs (Knowledge Dynamic Maps) sur les contenus des bases documentaires. Ces KDMs permettent de guider et d’aider les utilisateurs dans leurs tâches de consultations documentaires. Ce papier présente également une expérimentation de notre approche sur des collections de documents textuels.

Mots-Clefs. Caractérisation thématique, Similarité textuelle, Partage de contextes, Knowledge Dynamic Map.

1 Introduction

La fouille de données textuelles vise essentiellement à résoudre les problèmes de surabondance d’informations et faciliter l’extraction des connaissances enfouies dans les documents disponibles sur les bases de données ou sur le Web. Chaque jour, en particulier en raison de l’essor des communications électroniques, le nombre de documents disponibles croît de manière exponentielle et l’utilisateur (entreprise, organisme ou individu) se trouve submergé par la quantité d’informations disponibles. Ces utilisateurs ne sont donc plus capables d’analyser ou d’appréhender ces informations dans leur globalité.

De nombreux travaux de recherche, notamment issus du Web Mining et du Text Mining, s’intéressent aux traitements de bases de documents textuels (Baldi et Di meglio 2004,

- 269 - RNTI-E-5

Page 78: Egc05 atelier rnti-e-5_(extraits)

Recherche d’information multimédia : Apport de la fouille de données et des ontologies

Marie-Aude Aufaure *, Marinette Bouet **

* Supélec, Plateau du Moulon, Département Informatique, F-91192 Gif-sur Yvette Cedex, France

[email protected] www.supelec.fr/ecole/si/pages_perso/aufaure.html

** LIMOS, UMR 6158 CNRS – Université Blaise Pascal (Clermont-Ferrand II) Campus des Cézeaux – 24, Avenue des Landais – 63173 AUBIERE Cedex – France

[email protected]

Résumé. A ce jour, le média image est omniprésent dans de nombreuses applications. Un volume de données considérable est produit ce qui conduit à la nécessité de développer des outils permettant de retrouver efficacement de l’information pertinente. Les systèmes de recherche actuels montrent aujourd’hui leurs limites en raison de l’absence de sémantique. Une voie qui semble intéressante à explorer afin de combler le fossé existant entre les propriétés extraites et le contenu sémantique, est la fouille de données. C’est un domaine de recherche encore immature mais très prometteur. Cet article présente des travaux préliminaires sur la manière de définir de nouveaux descripteurs intégrant la sémantique. Le clustering et la caractérisation des classes obtenues sont utilisés pour réduire l’espace de recherche et produire une vue résumée de la base. La navigation basée sur une ontologie visuelle est un moyen puissant et convivial pour retrouver de l’information pertinente.

1 Introduction Durant la dernière décennie, un volume considérable de données multimédia a été

produit. Ces données sont par essence complexes, non structurées et volumineuses et les applications ayant besoin de rechercher des images pertinentes de manière efficace, de plus en plus nombreuses. Du fait qu’une image ne contient pas directement d’information interprétable de manière automatique, les méta-données vont jouer un rôle très important. L’étape de pré-traitement permet d’extraire un ensemble de méta-données comme : (1) les méta-données relatives au type de donnée multimédia, (2) les méta-données descriptives : nom de l’auteur, date, etc., (3) les méta-données relatives au contenu (sémantique, visuel, relations spatiales) : le contenu visuel est décrit en termes de couleur, forme et texture, et le contenu sémantique est une interprétation de l’image.

Le but est de pouvoir traiter les données du pixel à la connaissance puisque par le vocable « image », on entend image numérique c’est-à-dire une image qui se présente sous la forme d’une matrice de pixels. Il est à noter aussi que le média image ne concerne que les images fixes; les images animées étant dénotées par l’expression « média animation ». Au niveau pixel, des descripteurs visuels sont extraits et les requêtes sont basées sur le contenu. De nombreux travaux existent dans le domaine de la vision par ordinateur sur la partie descripteurs visuels. Dans ce cas, la recherche d’information consiste en une recherche par similarité (Content Based Image Retrieval) basée sur une distance entre les descripteurs visuels extraits des images (Venters et Cooper 2000). Le niveau d’abstraction suivant est

- 279 - RNTI-E-5

Page 79: Egc05 atelier rnti-e-5_(extraits)

������������� �������������������������������������������

�����������������

������������� � ���������������� ������������� ����������� �

� ������������ ���������!������� ������"�����#� ���������������������������$�����%&&%'�

#�( ��)*������)�����+��,�����-.��������������/���0��10��2�

34��1�����5������������!������� ������"�����#� ���������������'%6'7�$����������8��4��,�����

������0�����/��*�����0��� ���9�:*5���� ;�������� ������<����� ���������������!���4���� ��<! ��������

���1�� ��� ��������7=&����������:������*%&>>>�?� �����)���01���/���*�����0����

������� ���� 1�� ������ � � ���� ����������� ���� ��� ������� �<"+ ��� ��� ���#�������������@�!���9"#@;��� ������ ������ !��A������������� !��4����� ����� �����A����� ����������!����A��<��1���� �������<�1!�� ����������� ���+� ��1�� �� ������ ���4���0� �B����<����� �<��� )� �� �� �������� ���� ��� C����1��+� !�D����1����������<"#@�����<�� �1����������1��������!��� ���� ��������� !���� ��� ��� �� �� ���1��+� !0� @!����� ��� ���1��+� !� ��� �<"#@�� �������� !������� ����E ����������������� �����4��� ����4������� ���B����<�������������� !�����������������!��0�@����� ��� ������1�����!1����� A�����4��� ������������������!���+����������� ���������1��+� !���"#@���� ����� � �<�11������ �)� !��4���� ��� �11������ ��� ���!���� ��� ��� �)� F�������1��+��0��

�� �����������

�B����<����������<������ ��� ��������������������!���9� ����� �������������A��������������� ��� ������� ����� ������ �0;�� ����1�������������)� F������������� �����������!���9�� ���� ���� ����� ������ � �0;�� ���� ������� ������ ��� @�!��� 9�@;� �� � ��� ��� ��� � � ������� � ��� �<�������0� �<�+1��� � ��� ��� ���� �������� ��� ��!��� �� ������� �� �������� �� �������!����������!�������������������� ������������1��<�� ��������������� ��11���A����� ����4�����<"+ ��� ������#�������������@�!��0����1����������<"+ ��� ������#�������������@�!���9"#@;��� ��!����������G�C����

����������� ����� ����������������������������������������������� �� �������� �

� ����� ��������������������������D�9,�))������� � ��)*:��1����� ���0�7%%6;0�#<�� ���1���������� ���� ���� �� !�� ������1��4�� ��������������! �1�������������!�������1������1����8� ����� ����9��������������7%%6;0�����1�� ������� �������������������������������<"#@� �� � ����� � ����� !�� A� ���� �������� !�� 4��� �� � ���� ����� ��+� ����� 1������1����1�����������1���������9�0�0� ���������� ���� ����������������� �� � �� ������� � ����� ����� � ���� �� ���� � ;0� #�1��� �� �<��� )� �� �� �������� ���� ��� C��������� ��D� ���1��������� �<"#@�� ��� <�� � 1��� ��� ���� 1���� ��� �!��� ��� � � ��� ����� !���� ��� ��� �� �����1��+� !0�������������� ������� ��!!������ ������!�!���������������������1��+� !����

- 289 - RNTI-E-5

Page 80: Egc05 atelier rnti-e-5_(extraits)

Une representation des arborescences pour larecherche de sous-structures frequentes

Federico Del Razo Lopez, Anne Laurent, Maguelonne Teisseire

LIRMM - Universite Montpellier II161 rue Ada 34392 Montpellier cedex 5

{delrazo,laurent,teisseire}@lirmm.fr

Resume. La recherche de structures frequentes au sein de donnees ar-borescentes est une problematique actuellement tres active qui trouvede nombreux interets dans le contexte de la fouille de donnees comme,par exemple, la construction automatique d’un schema mediateur a par-tir de schemas XML. Dans ce contexte, de nombreuses propositions ontete realisees mais les methodes de representation des arborescences sonttres souvent trop couteuses. Dans cet article, nous proposons donc unemethode originale de representation de ces donnees. Les proprietes decette representation peuvent etre avantageusement utilisees par les algo-rithmes de recherche de structures frequentes (sous-arbres frequents). Larepresentation proposee et les algorithmes associes ont ete evalues surdes jeux de donnees synthetiques montrant ainsi l’interet de l’approcheproposee.

1 Introduction

L’explosion du volume de donnees disponible sur internet conduit aujourd’hui areflechir sur les moyens d’interroger les grosses masses d’information afin de retrouverles informations souhaitees. Les utilisateurs ne pouvant pas connaıtre les modeles sous-jacents des donnees qu’ils souhaitent acceder, il est donc necessaire de leur fournirles outils automatiques de definition de schemas mediateurs. Un schema mediateurfournit une interface permettant l’interrogation des sources de donnees par l’utilisateurau travers de requetes. L’utilisateur pose alors ses requetes de maniere transparente al’heterogeneite et la repartition des donnees.

XML etant maintenant preponderant sur internet, la recherche de moyens d’integra-tion de tels schemas est indispensable. Si les recherches permettant l’acces aux donneesquand un schema d’interrogation est connu sont maintenant bien avancees (Xyleme,2001), les recherches concernant la definition automatique d’un schema mediateur res-tent incompletes et sont donc non satisfaisantes (Tranier et al., 2004). Dans le but deproposer une approche permettant de repondre a cette derniere problematique, nousnous focalisons sur la recherche de sous-structures frequentes au sein d’une base dedonnees de schemas XML. Une sous-structure frequente est un sous-arbre se trouvantdans la plupart des schemas XML consideres. Cette proportion est examinee au sensd’un support qui correspond a un nombre minimal d’arbres de la base dans lesquelsdoit se retrouver le sous-arbre pour etre considere comme frequent. Une telle recherche

- 299 - RNTI-E-5

Page 81: Egc05 atelier rnti-e-5_(extraits)

Classement d'objets incomplets dans un arbre de décision probabiliste

Lamis Hawarah, Ana Simonet , Michel Simonet*

*TIMC-IMAG Institut d'Ingénierie et de l'information de Santé

Faculté de Médecine – IN3S 38700 LA TRONCHE

{Lamis.Hawarah, Ana.Simonet, Michel.Simonet}@imag.fr http://www-timc.imag.fr

Résumé. Nous présentons une approche probabiliste pour déterminer les valeurs manquantes des objets incomplets pendant leur classement dans les arbres de décision. Cette approche est dérivée de la méthode d’apprentissage supervisé appelée Arbres d’Attributs Ordonnés proposée par Lobo et Numao en 2000, qui construit un arbre de décision pour chacun des attributs, selon un ordre croissant en fonction de l’information mutuelle entre chaque attribut et la classe. Notre approche étend la méthode de Lobo et Numao d’une part en prenant en compte les dépendances entre les attributs pour la construction des arbres d’attributs, et d’autre part en fournissant un résultat de classement d’un objet incomplet sous la forme d’une distribution de probabilités (au lieu de la classe la plus probable).

1 Introduction Le problème des valeurs manquantes est un problème connu dans le domaine de la fouille

de données, où, dans la base d’apprentissage, on rencontre des objets ayant des valeurs manquantes pour certains attributs. Nous étudions ce problème dans le cadre des arbres de décision. Un arbre de décision est construit à partir d’un ensemble d’apprentissage selon l’approche divide-and-conquer (Quinlan 1993). Une fois l’arbre construit, il est utilisé pour classer de nouveaux objets. Pour cela on parcourt l'arbre en commençant par la racine et en suivant les branches correspondant aux valeurs de l’objet, jusqu’à une feuille. La classe associée à cette feuille est la classe de cet objet. Les arbres de décision sont confrontés au problème des données manquantes, à la fois lors de leur construction et lors du classement d'objets. Lors de la construction, l'existence de valeurs manquantes pose problème pour le calcul de gain d’information, nécessaire au choix de l’attribut test, ainsi que pour la partition de l’ensemble d’apprentissage selon l’attribut test choisi. Le classement d'un objet avec des valeurs manquantes soulève également des problèmes lorsqu’un nœud correspondant à un attribut manquant est rencontré dans le parcours de l’arbre. Dans ce travail nous nous intéressons exclusivement au second problème, c’est-à-dire le classement d'objets incomplets.

Les méthodes qui traitent les valeurs manquantes dans les arbres de décision, remplacent un attribut manquant par une seule valeur, qui peut être la valeur la plus probable (Kononenko et al. 1984) ou la plus similaire (Breiman et al. 1984), etc. Ce type d’approche présente l’inconvénient d’oublier les autres valeurs possibles. Notre approche vise à une détermination probabiliste des valeurs manquantes, en prenant en compte les dépendances entre l’attribut manquant et les autres attributs de l’objet, ce qui permet d’utiliser le maximum de l’information contenue dans l’objet pour le calcul des valeurs manquantes. De plus, nous voulons un résultat sous la forme d’une distribution de probabilités plutôt que la valeur la plus probable, ce qui donne une information plus fine. Parce que les arbres de décision sont

- 309 - RNTI-E-5

Page 82: Egc05 atelier rnti-e-5_(extraits)

Fouille de donnees du genome a l’aide de modeles deMarkov caches

Sebastien Hergalant ∗ ∗∗, Bertrand Aigle ∗

Pierre Leblond∗, Jean-Francois Mari∗∗

∗Laboratoire de Genetique et Microbiologie, UMR-UHP-INRA, IFR 110,54506 Vandœuvre-les-Nancy, France

{bertrand.aigle,pierre.leblond}@nancy.inra.fr,∗∗LORIA UMR-CNRS 7503, 54506 Vandœuvre-les-Nancy, France

{hergalan,jfmari}@loria.frhttp ://www.loria.fr/~jfmari/ACI/

Resume. Nous decrivons un processus de fouille de donnees en bioinfor-matique. Il se traduit par la specification de modeles de Markov cachesdu second-ordre, leur apprentissage et leur utilisation pour permettre unesegmentation de grandes sequences d’ADN en differentes classes qui tra-duisent chacune un etat organisationnel et structural des motifs d’ADNlocaux sous-jacents. Nous ne supposons aucune connaissance a priori surles sequences que nous etudions. Dans le domaine informatique, ce tra-vail est dedie a la definition d’observations structurees (les k-d-k-mers)permettant la localisation en contexte d’irregularites, ainsi qu’a la des-cription d’une methode de classification utilisant plusieurs classifieurs.Dans le domaine biologique, cet article decrit une methode pour prediredes ensembles de genes co-regules, donc susceptibles d’avoir des fonctionsliees en reponse a des conditions environnementales specifiques.

1 Introduction

L’accumulation des sequences issues des projets de sequencage oblige la mise enœuvre de methodes de fouille de donnees efficaces pour comprendre les mecanismes im-pliques dans l’expression, la transmission et l’evolution des genes. Nous nous interessonsaux modeles stochastiques et methodes classificatoires permettant de predire les se-quences promotrices et autres petites sequences regulatrices chez les bacteries. Unemaniere de cerner notre ignorance vis a vis des motifs et segments d’ADN impliquesdans les mecanismes decrits plus haut est de modeliser l’evolution et la structuration dugenome par des processus stochastiques capables d’apprentissage statistique necessitantun minimum de connaissances a priori . Ces modeles stochastiques sont utilises commerevelateurs d’organisations locales remarquables qu’un expert doit interpreter.

Nous nous interessons a la localisation de sites de fixation de proteines. Ces sites defixation – appeles TFBS (Transcription Factor Binding Sites) ou encore promoteurstranscriptionnels – sont constitues de trois sequences adjacentes de nucleotides :

Nx—Ny—Nz avec N ∈ {A,C, G, T}3 ≤ x, z ≤ 90 ≤ y ≤ 25

- 319 - RNTI-E-5

Page 83: Egc05 atelier rnti-e-5_(extraits)

Exploration visuelle d’images IRMfbasee sur des Gaz Neuronaux Croissants

Jerzy Korczak∗, Jean Hommet∗, Nicolas Lachiche∗, Christian Scheiber∗∗∗LSIIT, CNRS, Illkirch

<jjk,hommet,lachiche>@lsiit.u-strasbg.fr∗∗CHU Lyon

[email protected]

Resume. Les algorithmes actuels de fouille de donnees ne supportent quede facon tres limitee les mecanismes de guidage et d’engagement d’expertdans le processus de decouverte. Dans cet article, nous presentons unenouvelle approche interactive de fouille des images IRMf, guidee par lesdonnees, permettant l’observation du fonctionnement cerebral. La discri-mination des voxels d’image du cerveau qui presentent une reelle activiteest en general tres difficile a cause d’un faible rapport signal sur bruit etde la presence d’artefacts. L’exploration de donnee visuelle se focalise surl’integration de l’utilisateur dans le processus de decouverte de connais-sance en utilisant des techniques de visualisation efficaces, d’interactionet de transfert de connaissances. Dans ce travail, nous montrons sur lesdonnees reelles, que l’exploration visuelle permet d’accelerer le proces-sus d’exploration d’images IRMf et aboutit a de meilleurs resultats dotesd’une confiance accrue.

1 Introduction

Les techniques modernes d’imagerie cerebrale, comme l’Imagerie par ResonanceMagnetique fonctionnelle (IRMf), offrent la possibilite d’enregistrer en meme tempsl’activite de l’ensemble du cerveau. C’est une force, mais cela genere une masse dedonnees considerable (environ 300000 voxels, ”pixels tridimensionnels”, pour lesquelson recueille entre 100 et 1000 observations). Du point de vue de la fouille de donnees, lecerveau est un objet complexe par excellence. En general, la discrimination des voxelsd’image du cerveau qui presentent une reelle activite est tres difficile a cause d’unfaible rapport signal sur bruit et de la presence d’artefacts. Les premiers tests desalgorithmes actuels de fouille dans ce domaine ont montre que leurs performances etleurs qualites de reconnaissance sont faibles (Sommer and Wichert, 2003). En raisonde la difficulte qu’il y a a manipuler de telles quantites d’informations, l’essentiel desetudes ne cherchent pas a les explorer, mais s’en servent pour tester un modele parle biais de statistiques univariees effectuees en chacun des points. C’est le principe delogiciels de traitement tels que Statistical Parametric Mapping (SPM) (Friston et al.,1995), AFNI (Cox, 1996) ou BrainVoyager (Goebel, 1997) qui consiste a mettre enevidence les voxels plus actifs dans une condition par rapport a une autre.

Sur le plan international, un grand nombre de recherches methodologiques sonten cours pour mettre en evidence les variations qui ont du sens. On peut regroupercelles-ci en deux grandes familles. La plus commune est l’approche par les statistiques

- 329 - RNTI-E-5

Page 84: Egc05 atelier rnti-e-5_(extraits)

Mise en evidence d’invariants dans une populationde cas chirurgicaux

Melanie Raimbault∗, Ricco Rakotomalala∗∗

Xavier Morandi∗,∗∗∗, Pierre Jannin∗

∗Laboratoire Idm, 2 avenue du Pr. Leon Bernard, 35043 [email protected] ://idm.univ-rennes1.fr

∗∗Laboratoire Eric, 5 avenue Pierre Mendes France, 69676 [email protected]

http ://eric.univ-lyon2.fr∗∗∗Hopital Pontchaillou, Service de neurochirurgie, 35000 Rennes

Resume. Ces dernieres annees, les progres en informatique et en image-rie numerique ont fait emerger une nouvelle discipline, la chirurgie assisteepar ordinateur. Les systemes de chirurgie assistee par ordinateur contri-buent a l’amelioration du deroulement des procedures chirurgicales. Undes objectif a long terme de nos travaux est de proposer des solutionsd’amelioration de ces systemes, basees sur les connaissances du chirur-gien quant au deroulement de la procedure, par l’utilisation d’un modelegenerique qui permet de capturer et de representer ces connaissances. Cetarticle presente une methodologie d’exploitation d’un ensemble de caschirurgicaux decrits a l’aide de ce modele generique, par des algorithmesissus de l’extraction de connaissance a partir de donnees, afin de mettre enevidence des invariants dans les descriptions structurees du deroulementdes cas chirurgicaux. Il detaille en outre les difficultes rencontrees de parnotamment le caractere complexe des donnees etudiees.

1 Introduction et contexte

Les continuels progres de l’informatique, l’amelioration des techniques d’imagerienumerique et la banalisation de l’usage des ordinateurs au sein de l’univers chirurgical,ont participe a l’emergence d’un nouveau domaine : la chirurgie assistee par ordina-teur. Un eventail d’expertises et de competences en biologie, en medecine, en sciencesde l’ingenieur et en sciences informatiques participe a l’amelioration constante de cedomaine de recherche (Shahidi et al 2001). Les benefices apportes par l’utilisation detels systemes ont deja ete mis en evidence dans de nombreuses disciplines chirurgicales,en particulier la neurochirurgie, et notamment la neurochirurgie guidee par l’image ouneuronavigation. Ces systemes contribuent a rendre la chirurgie plus sure et moinsinvasive.

Un des objectifs de nos travaux est de proposer une solution permettant l’amelio-ration d’une ou plusieurs phases du processus de neurochirurgie guidee par l’image,par la modelisation des connaissances du neurochirurgien quant a son experience, ac-quise pendant sa formation et tout au long de sa pratique chirurgicale. Notre demarche

- 339 - RNTI-E-5

Page 85: Egc05 atelier rnti-e-5_(extraits)

Chapitre 9

Extraction de Connaissance à partir d’images �

La création d’un atelier autour du thème de l’image dans le cadre d’un congrès traitant du thème de la Connaissance apparaissait à la fois comme une nécessité et une gageure. Malgré tous les efforts consentis, la communication entre les deux communautés en est à ses balbutiements.

Pour un gestionnaire et un extracteur de connaissance, l’image est un matériau non structuré. Pour un analyseur d’images, la plupart d’entre elles constitue un matériau au contraire extrêmement structuré. Là est la gageure, trouver une représentation commune pour l’articulation Image-Connaissance.

Pourtant les techniques utilisées de part et d’autre sont familières aux deux communautés : segmentation, partition, reconnaissance des formes, interprétation font partie d’un vocabulaire commun.

Pour cette première interaction formelle dans le cadre d’EGC, nous avons souhaité donner à cet atelier une couleur fédératrice. Aussi, le thème de la représentation et du raisonnement spatial semblait constituer un bon terrain de rencontres.

L’importance du raisonnement spatial nous est encore apparue dernièrement lors d’un projet transversal avec des biologistes. Les cellules cancéreuses peuvent être caractérisées visuellement en fonction de la configuration spatiale des protéines autour du cytoplasme de la cellule relativement au noyau : alignement des protéines, répartition homogène à l’extérieur ou à l’intérieur du cytoplasme (cf. FIG-1).

Responsables du chapitre : N. Loménie, G. Stamon

- 349 - RNTI-E-5

Page 86: Egc05 atelier rnti-e-5_(extraits)

FIG. 1- De gauche à droite : image cellulaire microscopique, régions segmentées à partir de l'image (le cytoplasme sous la forme d’un contour rouge, le noyau sous la forme d’une région noire et les protéines sous la forme de taches ponctuelles vertes), configurations schématiques

des classes de cellules fournies par un biologiste Les quatre articles présentés ici abordent tous cette problématique : Comment représenter et

raisonner spatialement dans une image ? Guray Erus expose comment exhiber automatiquement un modèle structurel 2D d’une catégorie d’objets à partir d’images contenant ces objets. Abdel Hafiane et Sylvie Philipp s’interroge sur la capacité à intégrer une analyse spatiale évoluée des régions segmentées dans le cadre de systèmes de recherche d’images par le contenu. Enfin, Erick Lopez-Ornelas posent les jalons pour un système de raisonnement spatial intégrant les modules de structuration sémantique et syntaxique d’une image.

Les enjeux industriels, pour les applications, civiles ou militaires, notamment en robotique

extérieure, en analyse d’images aéroportées, en guidage d’engins, … sont majeurs, particulièrement dans des contextes où des décisions doivent être prises sans l’intervention d’un opérateur humain pour valider les résultats de traitements.

Des avancées dans le domaine de l’extraction, la modélisation et l’utilisation de connaissances extraites d’images dépendra notre capacité à réaliser des systèmes de vision capable d’appréhender le monde extérieur dans sa complexité et de remplir leur fonction automatiquement dans l’ensemble de leur contexte d’emploi. Sans oublier que la problématique porte autant sur notre capacité de gestion de la méconnaissance que sur notre maîtrise de la connaissance.

Force est de constater que le chemin à parcourir reste long et qu’il passe par une collaboration étroite entre l’ensemble des communautés intéressées par l’acquisition, la représentation et l’exploitation de la Connaissance. Cette collaboration sera sans nul doute particulièrement riche et stimulante, à la hauteur des chalenges à relever, comme l’ont montré toutes les tentatives menées jusqu’ici dans cette voie.

Comité de programme et d'organisation : Nicolas Loménie (SIP-CRIP5, Université René Descartes - Paris 5, [email protected]) Georges Stamon (SIP-CRIP5, Université René Descartes -Paris 5) Daniel Duclos (SAGEM SA Branche Défense et Sécurité, [email protected])

- 350 -RNTI-E-5

Page 87: Egc05 atelier rnti-e-5_(extraits)

Apprentissage Automatique des Modeles Structurelsd’Objets Cartographiques

Guray Erus, Nicolas Lomenie

Universite de Paris 5, Laboratoire SIP-CRIP5.45 rue des Saints Peres ; 75006 ; Paris ; France

{egur,Nicolas.Lomenie}@math-info.univ-paris5.fr

Resume. Pour reconnaıtre les objets cartographiques dans les imagessatellitales on a besoin d’un modele d’objet qu’on recherche. Nous avonsdeveloppe un systeme d’apprentissage qui construit le modele structureld’objets cartographiques automatiquement a partir des images satellitalessegmentees. Les images contenants les objets sont decomposees en formesprimitives et transformees en Graphes Relationnels Attribues (ARGs).Nous avons genere les modeles d’objets a partir de ces graphes en utilisantdes algorithmes d’appariement de graphes. La qualite d’un modele estevaluee par la distance d’edition des exemples a ce modele.

1 Introduction

Notre objectif est de generer des modeles d’objets cartographiques automatique-ment a partir d’une base d’images satellitales segmentees. Une etude detaillee de lareconnaissance d’objets en utilisant des modeles est presentee dans (Pope). Dans laplupart des travaux, les objets sont representes par des graphes et particulierementpar des ARGs. (Petrakis et Faloutsos) proposent une metrique de distance entre deuxARGs pour detecter les images semblables dans une base de donnee images. Dans (Cor-della et al.) on presente une methode d’apprentissage des figures representees par desARGs. Une etude des algorithmes d’appariement de graphes se trouve dans (Bunke).

Nous disposons d’une banque de donnees-objets dans lequel des ponts et des ronds-points isoles sont extraites d’ images SPOT5-THR a une resolution de 2,5 metres.Notre systeme se compose de deux modules. L’objectif du module de pre-traitementest la decomposition des images segmentees de ponts et de ronds-points en figuresgeometriques primitives. Ensuite, nous transformons les images decomposees en ARGspour generer les modeles d’objet.

2 Decomposition en Figures Geometriques

Nous avons propose deux decompositions en parallele, une par des cercles et desrectangles et une autre par des cercles et des segments. Nous avons d’abord detecteles cercles dans les images en utilisant la transformee de Hough. Pour detecter lesrectangles, la premiere etape est l’extraction des contours en utilisant le gradient mor-phologique. Le contour obtenu est une courbe. Pour approximer ce courbe par dessegments, nous avons utilise l’algorithme de la corde. Parmi tous les segments, nousavons choisi les segments paralleles, et nous avons detectes les rectangles encadrees par

- 351 - RNTI-E-5

Page 88: Egc05 atelier rnti-e-5_(extraits)

Application des courbes de Peano en recherched’image par le contenu

Adel Hafiane, Bertrand ZavidoviqueInstitut d’Electronique Fondamentale, Universite de Paris-Sud XI, 91405 Orsay, France

{prenom.nom}@ief.u-psud.fr

Resume. Dans cet article nous presentons une application des courbes dePeano pour la caracterisation de regions par leur texture et l’etablissementd’inter- relations spatiales a des fins de ”CBIR”. Les resultats obtenus sontcomparables a ceux d’un humain sur une base de 330 images aeriennes.

1 Introduction

La segmentation est un facteur clef de la recherche d’images par le contenu (CBIR).La couleur, la texture et la forme sont les principaux attributs visuels en CBIR (Fli-ckner et al. 1995, Carson et al. 1999). Ils ne garantissent pas des reponses assez sures.On les complete donc par des relations spatiales entre objets, supposant que l’imageest organisee (Chang et al. 1987, Gudivada et Raghavan. 1995, El-Kwae et Kabuka.1999). L’abstraction et la semantique limitees sont ici fondees sur les regions. Comptetenu de l’application (Systeme d’Information Geographique) nous considerons que lesregions significatives correspondent a un effort minimal d’analyse de texture, tel quepeut le produire un non specialiste. Elles sont extraites par balayages de Peano locale-ment optimaux et co-occurrence de gradients constante, lies a la couleur (moyenne etvariance R,V,B presque constantes). Les relations spatiales exploitent la droite inter-centres. Le tout est represente par un graphe (ARG) (Hafiane et al. 2004). Le calculdes liens entre regions exploite le meme type de representation, renforcant le caracteresemantique limite de la distance entre images. Notre etude recouvre 1) caracterisationdes regions extraites par l’humain et verifiees efficaces pour la requete, 2) conceptiond’une segmentation automatique en regions basee sur les memes variables 3) verificationexperimentale de ”rappel” et ”precision” comparables pour l’automate et l’humain. Lecaractere naturellement multi-resolution de notre segmentation/codage d’images four-nit un degre de liberte supplementaire pour adapter la methode a des classes d’imagesplus specifiques en cas de besoin. Nous rappelons brievement dans la suite ce qu’estun balayage de Peano et la structure d’arbre associee puis le calcul de distance dansl’arbre. Nous expliquons la segmentation par ”Fuzzy C-means” (FCM) modifie avantde conclure sur quelques resultats comparant l’homme et la machine.

2 Les Courbes de Peano

Les courbes de Peano appliquent recursivement les points d’un espace (e.g. image)sur une courbe (e.g. balayage) en les ordonnant en sequence de motifs (figure 1 a).Etant donne un entier x ∈ Z, son code de Peano ”en Z” dans le plan est :

p2(x) = 22blog

2xc + p

2(x − 2blog2

xc) avec p2(0) := 0 (1)

RNTI-E-5- 355 -

Page 89: Egc05 atelier rnti-e-5_(extraits)

Recherche d’image par le contenu : requête partielle ou globale, apprentissage en ligne

Sylvie Philipp-Foliguet

ETIS, CNRS UMR8051 ,

6 avenue du Ponceau 95014 Cergy-Pontoise Cedex

[email protected] http://www-etis.ensea.fr/~philipp/

Résumé. Nous présentons dans cet article deux méthodes d’élaboration des signatures, une méthode globale à l’aide d’histogrammes et une méthode de description des régions et de leur disposition dans l’image. Nous exposons ensuite une méthode dédiée à la requête partielle qui est basée sur la mise en correspondance de graphes de régions et une méthode interactive basée sur l’apprentissage statistique.

1 Introduction La recherche d'image dans des bases est un domaine de recherche en plein essor à cause

des innombrables images acquises chaque jour dans des domaines aussi variés que la médecine, la télédétection ou avec les appareils photographiques personnels, pour n'en citer que quelques-uns. Cette nouvelle thématique emploie les techniques de la reconnaissance des formes dont elle est une application particulière. Ce qui la caractérise par rapport aux applications précédentes de l'interprétation d'images est de s'attacher davantage à la sémantique de l'image et de s'effectuer en interaction avec l'utilisateur. En effet les applications de la reconnaissance des formes qui fonctionnent sont par exemple la lecture des chèques ou la reconnaissance des empreintes digitales. La sémantique est ici quasiment inexistante, on recherche le "tout automatique". Autrement plus difficile est la recherche pour une agence de presse d’une photographie illustrant tel président devant tel édifice ou pire un concept aussi abstrait que la "misère".

Nous exclurons dans ce papier l'emploi d'autre information que l'image elle-même, nous concentrant sur la recherche d'image par le contenu, à partir d'une image requête. Comme la sémantique est difficile à représenter numériquement, l'utilisateur est souvent mis à contribution pour guider la recherche dans une procédure dite de "bouclage de pertinence".

Un système de recherche d'images par le contenu comprend une phase de description de l'image qui a pour but de la représenter numériquement à l’aide d’une signature. Cette phase, parfois très longue s'effectue hors-ligne. La phase de recherche proprement dite s'effectue en ligne et consiste à comparer, via les signatures, les images entre elles ou avec une image fournie en entrée par l'utilisateur.

2 Description de l’image sous forme de signature Les signatures d'images couramment utilisées font soit appel à des descripteurs globaux,

caractérisant l'ensemble de l'image, soit à des descripteurs locaux calculés sur des régions ou des points caractéristiques.

- 359 - RNTI-E-5

Page 90: Egc05 atelier rnti-e-5_(extraits)

Extraction de connaissances pour la description d’images satellitaires à très haute résolution spatiale

Erick Lopez-Ornelas*, Florence Sèdes **

* LTHR, 118 Route de Narbonne, 31062 Toulouse cedex 4, [email protected]

** IRIT, 118 Route de Narbonne, 31062 Toulouse cedex 4, [email protected]

Résumé. L’arrivée des images de télédétection à très haute résolution spatiale impose de reconsidérer les méthodes de description des surfaces représentées dans les images satellites. Dans ce qui suit, nous proposons une approche de segmentation morphologique auto-adaptative d’images satellitaires à très haute résolution spatiale. La segmentation est associée à l’exploitation des données élicitées tout au long du processus, dans l’objectif de collecter, modéliser et homogénéiser ces données au sein de descripteurs. Exploiter l’information ainsi disponible sur les objets implique la prise en compte des relations spatiales, décrivant les relations entre les objets, et leurs caractéristiques. La modélisation et la génération de descripteurs proposées rendent une telle approche opérationnelle originale dans le contexte des méthodes de télédétection.

1 Introduction L’imagerie spatiale à très haute résolution fait évoluer actuellement la perception que l’on

avait de la Terre, en donnant une vision proche de celle qui est délivrée par les images aériennes. Aujourd’hui, la résolution des images d’observation civile atteint les niveaux métriques et infra métriques : les satellites SPOT5 (Cnes, France), ALOS (Nasda, Japon), IKONOS (Space Imaging, Etats-Unis), QUICKBIRD (DigitalGlobe, Etats-Unis) fournissent des images entre 2.5 m et 0.6 m de résolution. Ces progrès ont été réalisés en un laps de temps très court et les techniques de traitement d’images (Cocquerez et al., 1995), utilisées, dans ce contexte précis, en télédétection n’ont pas évolué aussi vite que les technologies d’acquisition, laissant d’énormes volumes de données stockées inexploitées.

L’amélioration de la perception permet de visualiser et d’analyser des objets jamais vus auparavant en télédétection (voitures, bâtiments, arbres, etc.) ce qui génère des images très hétérogènes. Il devient dès lors nécessaire de développer de nouvelles méthodes d’exploitation de cette imagerie pour en permettre une exploitation exhaustive. Dans cette perspective, la segmentation des images d’observation de la Terre est un domaine dans lequel de nombreux travaux sont indispensables, compte tenu de la faible utilisation actuelle de ce type d’approche en télédétection, afin de parvenir à des processus d’analyse et d’enrichissement via l’extraction et la modélisation de connaissances élicitées, avec comme objectif une recherche d’information a posteriori.

L’enjeu de ces travaux est de rechercher une stratégie de segmentation permettant de traiter le plus grand nombre de situations possibles, et c’est dans ce but que nous avons choisi d’utiliser une description par des graphes et des opérateurs de morphologie

- 365 - RNTI-E-5

Page 91: Egc05 atelier rnti-e-5_(extraits)

Chapitre 10

Qualité des Données et des Connaissances

Les problèmes de qualité des données stockées dans les bases ou les entrepôts de données s’étendent à tous les domaines gouvernemental, commercial, industriel et scientifique. La découverte de connaissances et la prise de décision à partir de données de qualité médiocre (c’est-à-dire contenant des erreurs, des doublons, des incohérences, des valeurs manquantes, etc.) ont des conséquences directes et significatives pour les entreprises et pour tous leurs utilisateurs. Le thème de la qualité des données et des connaissances est pour cela devenu, depuis ces dernières années, un des sujets d’intérêt émergeant à la fois dans le domaine de la recherche et dans les entreprises.

Toutes les applications dédiées à l’analyse des données (telles que la fouille de données

textuelles par exemple) requièrent différentes formes de préparation des données avec de nombreuses techniques de traitement, afin que les données passées en entrée aux algorithmes de fouille se conforment à des distributions relativement « sympathiques », ne contenant pas d’incohérences, de doublons, de valeurs manquantes ou incorrectes. Seulement, entre la réalité des données disponibles et toute la machinerie permettant leur analyse, un assez vaste fossé demeure.

In fine, l'évaluation des résultats issus du processus de traitement des données, est généralement effectuée par un spécialiste (expert, analyste,...). Cette tâche est souvent très lourde, et un moyen de la faciliter consiste à aider le spécialiste en lui fournissant des critères de décision sous la forme de mesures de qualité ou d'intérêt des résultats. Ces mesures de qualité des

Responsable du chapitre : L. Berti-Equille

- 371 - RNTI-E-5

Page 92: Egc05 atelier rnti-e-5_(extraits)

connaissances doivent être conçues afin de combiner deux dimensions : une dimension objective liées à la qualité des données, et une dimension subjective liées aux intérêts du spécialiste. L’atelier Qualité des Données et des Connaissances - DKQ 2005 (Data and Knowledge Quality) - associé à EGC'2005 concerne les méthodes, les techniques d’analyse et de nettoyage, les méthodologies, les approches algorithmiques et les métriques de qualité des données et des connaissances permettant de comprendre, d’explorer les données, de détecter et corriger les problèmes de qualité des données et de qualité des connaissances extraites à partir des données.

Comité de programme et d'organisation :

Laure Berti-Équille (IRISA-CNRS Rennes, France) Fabrice Guillet (IRIN, Université de Nantes France)

Ansaf Salleb (IRISA-CNRS Rennes, France)

Pascale Kuntz, (IRIN, Université de Nantes, France)

Jérôme Azé (LRI, Université de Paris-Sud, France)

Stéphane Lallich (ERIC, Université de Lyon 2, France)

Mokrane Bouzeghoub (PRISM, Université de Versailles, France)

Ludovic Lebart (ENST-CNRS, Paris, France)

Henri Briand (IRIN, Université de Nantes, France)

Philippe Lenca (ENSTbr, Brest, France)

Béatrice Duval (Université d’Angers, France)

Amedeo Napoli (LORIA, Nancy, France)

Johann-Christoph Freytag (Humboldt-Universität zu Berlin, Germany)

Gilbert Ritschard (Université de Genève, Switzerland)

Helena Galhardas (INESC, Lisboa, Portugal) Monica Scannapieco (Universita’ di Roma “La Sapienza”, Italy)

Régis Gras (IRIN, Université de Nantes, France) Dan A. Simovici (University of Massachussets, Boston, U.S.)

Yves Kodratoff (LRI, Université de Paris-Sud, France) Einoshin Suzuki (Yokohama National University, Japan)

Djamel Zighed (ERIC, Université de Lyon 2, France)

Remerciements Nous remercions tout particulièrement les auteurs et les membres du comité de relecture pour

leur contribution au succès de l’atelier DKQ2005.

- 372 -RNTI-E-5

Page 93: Egc05 atelier rnti-e-5_(extraits)

Data Freshness Evaluation in Different Application Scenarios1

Verónika Peralta, Mokrane Bouzeghoub

Laboratoire PRISM, Université de Versailles 45, avenue des Etats-Unis

78035, Versailles cedex, FRANCE {Veronika.Peralta, Mokrane.Bouzeghoub}@prism.uvsq.fr

Abstract. Data freshness has been identified as one of the most important data quality attributes in information systems. This importance increases especially in the context of systems that integrate a large set of autonomous data sources. In this paper we describe a quality evaluation framework which allows evaluation of data freshness in different architectural contexts. We also show how this quality factor may impact the reconfiguration of a data integration system to fulfill user expectations.

1 Introduction Data freshness has been identified as one of the most important attributes of data quality for

data consumers (Shin 2003) (Wang et al. 1996). Specifically, the increasing need to access to information which is available in several data sources introduces the problem of choosing between alternative data providers and of combining data having different freshness values (Naumann et al. 1999). This paper deals with data freshness evaluation in the context of a Data Integration System (DIS) that integrates data from different independent data sources and provides the users a uniform access to this data.

Data freshness represents a family of quality factors among which currency and timeliness are representative examples: currency describes how stale is data with respect to the sources and timeliness describes how old is data. In (Bouzeghoub et al. 2004) we analyze these factors and several metrics proposed to measure them. In (Peralta et al. 2004), we proposed a framework for analyzing and evaluating data freshness based on a calculation dag which abstracts a workflow of integration activities. After a brief recall of this framework, this paper shows how it can practically be used in different application scenarios and how the data integration system can be improved in order to fulfill user requirements in terms of data freshness.

The rest of the document is organized as follows: Section 2 briefly describes the data quality evaluation framework and discusses how to use it through different application scenarios. Section 3 focuses on the possible improvement actions to put on the DIS workflow to achieve user requirements. Finally, section 4 concludes with our general remarks.

1 This research was partially supported by the French Ministry of Research and New Technolologies under

the ACI program devoted to Data Masses (ACI-MD), project #MD-33.

- 373 - RNTI-E-5

Page 94: Egc05 atelier rnti-e-5_(extraits)

Nettoyage des données XML : combien ça coûte ?

Laure Berti-Équille

IRISA, Campus Universitaire de Beaulieu, 35042 Rennes cedex [email protected]

http://www.irisa.fr

Résumé. L'objectif de cet article est de présenter un travail en cours qui consiste à proposer, implanter et valider expérimentalement un modèle pour estimer le coût d’un processus de nettoyage de documents XML. Notre approche de calcul de coût est basée sur une méthode par calibration selon une analyse probabiliste. Pour cela, nous proposons de calculer des probabilités de pollution et au préalable de détection des différents types de pollutions. Pour valider notre modèle, nous avons choisi de polluer artificiellement une collection de données XML avec l'ensemble des types d'erreurs possibles (erreurs typographiques, ajout de doublons, de valeurs manquantes, tronquées, censurées, etc.) et d'estimer, grâce au modèle proposé, le nombre et le coût des opérations nécessaires au nettoyage des données afin de proposer des stratégies de réparation ciblées et économes. Les expérimentations en cours ne sont pas rapportées dans cet article.

1 Introduction Le nettoyage automatique des données se décompose classiquement en trois étapes : 1)

examiner les données afin de détecter les incohérences, les données manquantes, les erreurs, les doublons, etc. 2) choisir les transformations pour résoudre les problèmes, 3) et enfin, appliquer les transformations choisies au jeu de données. La plupart des outils utilisés pour le nettoyage des données par Extraction-Transformation-Loading (ETL) permettent l'extraction d'expressions régulières et structures (patterns) à partir des données, ainsi que leur transformation et formatage par l'application de différentes fonctions (sélection, fusion, clustering, etc.) (Vassiliadis 2003) dont généralement, on ignore a priori le coût. Bien qu’il existe de nombreux travaux (Dasu 2003), (Winkler 2003), (Rahm 2000) outils et prototypes (Telcordia (Caruso 2000), AJAX (Galhardas 2001), Potter’s Wheel (Raman 2001), Arktos (Vassiliadis 2000), IntelliClean (Low 2000), Tailor (Elfeky 2002)) développés pour « nettoyer » les données relationnelles, très peu de travaux à l’exception des récents travaux de Weis et Naumann (Weis 2004), ont jusqu’ici été menés pour le nettoyage de données XML et, à notre connaissance, aucun n’a abordé l’estimation du coût d’un nettoyage de données a fortiori pour des données XML. C’est dans ce cadre qu’a débuté notre travail dont l’objectif est de proposer, d'implanter et valider expérimentalement un modèle de coût global permettant d’estimer combien peut coûter un processus de nettoyage sur un document XML artificiellement pollué pour les besoins de nos expériences.

La suite de l’article s’organise de la façon suivante : la section 2 propose notre démarche illustrée par un exemple simple qui énumère les différents types de pollution possibles dans un document XML. La section 3 présente plus formellement notre modèle de coût avec ses

- 379 - RNTI-E-5

Page 95: Egc05 atelier rnti-e-5_(extraits)

Extraction de Règles en Incertain par la Méthode Implicative

Régis Gras*, Raphaël Couturier**, Fabrice Guillet*, Filippo Spagnolo***

** LINA– Ecole Polytechnique de l’Université de Nantes - BP 60601 44306 Nantes [email protected] et [email protected]

** Institut Universitaire de Technologie de Belfort, BP 527, rue E. Gros, 90016 Belfort [email protected]

*** G.R.I.M., Department of Mathematics, University of Palermo [email protected].

Résumé. En relation avec des approches classiques de l’incertain, l’analyse statistique implicative (A.S.I.) peut apparaître innovante, particulièrement pour l’opérateur d’implication. L’article montre en effet que la notion de variables à valeurs intervalles et celle de variables-intervalles sont efficaces dans la détermination de leur distribution et dans la recherche de règles entre variables floues. De plus, elles apportent de riches informations sur la qualité de ces règles, tout en permettant d’étudier le rôle des variables supplémentaires dans l’existence de ces règles. Cette nouvelle perspective épistémologique de l’incertain ouvre d’intéressantes perspectives d'application.

1 Introduction Partant du cadre défini et formalisé par (Lofti et al. 2001), (Dubois et al. 1987), ce texte

vise à étudier les proximités formelle et sémantique des cadres de l’incertain et de l’analyse statistique implicative (A.S.I.) entre variables à valeurs intervalles et variables-intervalles (Gras et al. 2001). On s’intéresse particulièrement à l’opérateur « implication »avec lequel on extrait des règles d’association. Ce texte s’inscrit dans le cadre initié par (Gras 1979) sur l’analyse de données, A.S.I., qui vise à extraire et représenter, des règles d’association entre variables ou conjonctions de variables, du type a⇒ b. Nous considérons celles qui croisent des sujets et des variables, présentant des modalités nettes ou floues. La qualité de la règle sera d’autant plus grande que son nombre de contre-exemples sera invraisemblablement petit sous l’hypothèse d’indépendance a priori, eu égard aux occurrences. .

2 problématique Bien que les applications de la logique floue soient nombreuses en intelligence artificielle

(par exemple en matière de diagnostic médical ou de reconnaissance des formes), plusieurs questions restent bien souvent latentes : comment obtient-on des distributions des degrés d’appartenance dans le cas de variables numériques ? Sur quelles connaissances sont-elles établies ? Sont-elles données a priori et mises à l’épreuve de la réalité ou bien sont-elles des construits ?S’il s’agit de ce dernier cas, quel processus d’extraction de connaissances à partir de données peut y conduire et quel type de règle peut-on alors extraire dans ce cadre ? Quelle signification peut-on donner à une règle associant deux sous-ensembles ou deux attributs flous ? On rejoint alors une des problématiques du data mining et de la qualité des règles.

- 385 - RNTI-E-5

Page 96: Egc05 atelier rnti-e-5_(extraits)

IPEE : Indice Probabiliste d’Ecart a l’Equilibrepour l’evaluation de la qualite des regles

Julien Blanchard, Fabrice GuilletHenri Briand, Regis Gras

LINA – FRE 2729 CNRSPolytech’Nantes

La Chantrerie – BP 5060944306 – Nantes cedex 3 – France

[email protected]

Resume. La mesure de la qualite des connaissances est une etape clefd’un processus de decouverte de regles d’association. Dans cet article, nouspresentons IPEE, un indice de qualite de regle qui a la particularite uniqued’associer les deux caracteristiques suivantes : d’une part, il est fonde surun modele probabiliste, et d’autre part, il mesure un ecart a l’equilibre(incertitude maximum de la conclusion sachant la premisse vraie).

1 Introduction

Parmi les modeles de connaissances utilises en Extraction de Connaissances dansles Donnees (ECD), les regles d’association (Agrawal et al., 1993) sont devenues unconcept majeur qui a donne lieu a de nombreux travaux de recherche. Ces regles sontdes tendances implicatives a → b ou a et b sont des conjonctions d’items (variablesbooleennes de la forme attribut = valeur). Une telle regle signifie que la plupart desenregistrements qui verifient a dans les donnees verifient aussi b.

Une etape cruciale dans un processus de decouverte de regles d’association est lavalidation des regles apres leur extraction. En effet, de par leur nature non supervisee,les algorithmes de data mining peuvent produire des regles en tres grande quantite etdont beaucoup sont sans interet. Pour aider le decideur (expert des donnees etudiees) atrouver des connaissances pertinentes parmi ces resultats, l’une des principales solutionsconsiste a evaluer et ordonner les regles par des mesures de qualite (Tan et al., 2004)(Guillet, 2004) (Lallich and Teytaud, 2004) (Lenca et al., 2004). Nous avons montredans (Blanchard et al., 2004) qu’il existe deux aspects differents mais complementairesde la qualite des regles : l’ecart a l’independance et l’ecart a ce que nous appelonsl’equilibre (incertitude maximum de la conclusion sachant la premisse vraie). Ainsi, lesmesures de qualite se repartissent en deux groupes :

– les indices d’ecart a l’independance, qui prennent une valeur fixe quand les va-riables a et b sont independantes (n.nab = nanb) ;

– les indices d’ecart a l’equilibre, qui prennent une valeur fixe quand les nombresd’exemples et de contre-exemples sont egaux (nab = nab = 1

2na).Les mesures de qualite peuvent egalement etre classees selon leur nature descriptive oustatistique (Lallich and Teytaud, 2004) :

- 391 - RNTI-E-5

Page 97: Egc05 atelier rnti-e-5_(extraits)

Le rôle de l'utilisateur dans un processus d'extraction derègles d'association

Cyril Nortet*, Ansaf Salleb** Teddy Turmeaux*, Christel Vrain*

* LIFO Rue Léonard de Vinci BP 6759 45067 Orléans Cedex 02{Cyril.Nortet, Teddy.Turmeaux, Christel.Vrain}@lifo.univ-orleans.fr

** INRIA Projet Dream, Campus Universitaire de Beaulieu, 35042 Rennes [email protected]

Résumé. De nombreux travaux ont porté sur l'extraction de règlesd'association. Cependant, cette tâche continue à intéresser les chercheurs enfouille de données car elle soulève encore plusieurs défis. En particulier, sonutilisation en pratique reste difficile : d'une part, le nombre de règles apprisesest souvent très grand, d'autre part, le traitement des valeurs numériques danscette tâche est loin d'être maîtrisé. Nous nous intéressons dans cet article aurôle que peut jouer l'utilisateur pour pallier ces difficultés. Il s'agit d'impliquerl'utilisateur dans le processus de recherche de règles d'association qui est dansce cas interactif et guidé par des schémas de règles qu'il aurait choisis. Nousillustrons notre propos avec QuantMiner qui est un outil convivial et interactifque nous avons développé. La présence de l'expert reste indispensable duranttout le processus d'extraction de règles.

Mots clé. Fouille de Données Interactive, Règle d'Association Quantitative,Optimisation.

1 Introduction

L'extraction de règles d'association est devenue aujourd'hui une tâche populaire en fouillede données. Elle a pour but de dégager des relations intelligibles entre des attributs dans unebase de données. Une règle d'association (Agrawal et al. 1993) est une implication C1 ⇒ C2,ou C1 et C2 expriment des conditions sur les attributs de la base de données. La qualité d'unerègle est classiquement évaluée par un couple de mesures support et confiance, définies par :• Support(C), ou C exprime des conditions sur les attributs, est le nombre de n-uplets

(lignes de la base de données) qui satisfont C. • Support(C1 ⇒ C2) = Support(C1 ∧ C2 ) • Confiance(C1 ⇒ C2) = Support(C1 ∧ C2 )/Support(C1)

Une règle d'association est dite solide, si son support et sa confiance dépassent deuxseuils fixés a priori, MinSupp et MinConf respectivement. De nombreux travaux se sontintéressés au problème crucial de performance que pose cette tâche (par ex. (Brin et al. 1997,

- 397 - RNTI-E-5

Page 98: Egc05 atelier rnti-e-5_(extraits)

Arbre BIC optimal et taux d’erreur

Gilbert Ritschard

Departement d’econometrie, Universite de [email protected]

Resume. Nous reconsiderons dans cet article le critere BIC pour arbres d’induc-tion propose dans Ritschard et Zighed (2003, 2004) et discutons deux aspects liesa sa portee. Le premier concerne les possibilites de le calculer. Nous montronscomment il s’obtient a partir des statistiques du rapport vraisemblance utiliseespour tester l’independance ligne-colonne de tables de contingence. Le secondpoint porte sur son interet dans une optique de classification. Nous illustrons surl’exemple du Titanic la relation entre le BIC et le taux d’erreur en generalisationlorsqu’on regarde leur evolution selon la complexite de l’arbre. Nous esquissonsun plan d’experimentation en vue de verifier la conjecture selon laquelle le BICminimum assurerait en moyenne le meilleur taux d’erreur en generalisation.

1 IntroductionLa qualite des arbres de classification, comme pour d’autres classifieurs, est le plus souvent

etablie sur la base du taux d’erreur de classement en generalisation. Si l’on examine l’evolutionde ce taux en fonction de la complexite du classifieur, il est connu qu’il passe par un minimumau dela duquel on parle de sur-apprentissage (overfitting). Intuitivement, l’explication de cephenomene tient au fait qu’au dela d’un certain seuil, plus on augmente la complexite, plusl’arbre devient dependant de l’echantillon d’apprentissage utilise, au sens ou il devient de plusen plus probable que de petites perturbations de l’echantillon entraıneront des modificationsdes regles de classification. Lorsqu’il s’agit d’utiliser l’arbre pour la classification, il sembledes lors naturel de retenir celui qui minimise le taux d’erreur en generalisation.

Mais comment s’assurer a priori que l’arbre induit sera celui qui minimisera le taux engeneralisation ? Il s’agit de disposer d’un critere qui, tout en se calculant sur l’echantillond’apprentissage, nous assure que le taux d’erreur sera en moyenne minimum pour tout en-semble de donnees supplementaires. A defaut de pouvoir mesurer a priori le taux d’erreur engeneralisation, on s’interesse a la complexite qu’il s’agit de minimiser et l’on tentera de retenirle meilleur compromis entre qualite d’information sur donnees d’apprentissage et complexite.Le critere BIC (Bayesian Information Criteria) pour arbre que nous avons introduit dans Rit-schard et Zighed (2003, 2004) pour comparer la qualite de la description des donnees fourniespar differents arbres nous semble pouvoir etre une solution de ce point de vue puisqu’il com-bine un critere d’ajustement (la deviance) avec une penalisation pour la complexite (le nombrede parametres). D’autres criteres, dont la description minimale de donnees (Rissanen, 1983) etle message de longueur minimal, MML, (Wallace et Freeman, 1987) qui combinent egalementune qualite d’information et une penalisation pour la complexite pourraient egalement s’averer

- 403 - RNTI-E-5

Page 99: Egc05 atelier rnti-e-5_(extraits)

������������� ���������������������������� �!��"�#����$��� �%�&�'�(�&���*),+"�-��.������*/�� ������� 01/"�����'��2���� +3�4�5���6�7��������3�&���8�+�������),�&����/��9�� ���

:<;�=?><@BADCE�FHGJI∗ KHL ENMH=OGJP ARQTSUGJVJVWA X ∗ K Y GWZUP�A�Z[X$\^]UGJVJGW_H_`; ∗∗ KUa AbZH=OG c"=OGdENZUI ∗ KUe ;bf7GJgTQT=8Ehg ∗

∗ i jlkTmonqp P r<VWAD\�r<Vts[XOAbP8]HZUGJu[SHADIvA'Vxw SHZUGtF<A�=Og?GtXO;DIvA k ENZ[X?Aygi E#z"]`E{Z[XO=?A�=OGWA n c�\}|h~7�h~<� n^�7�[� ~<� k ENZ[X?Ayg3P�AbIvA�� �

� A�=?r<@�A7� IUE�FvGJI K � ENMH=OGJP�A7� f7SUGJVJVtA�X K =?Abf7GJgb� f7=8Ehg K ]HA�ZH=OGx� MH=OGdENZUI��T_`r7Vts�X?AyP8] � SUZUGtF n Z`E{Z[XOAbg�� � = K∗∗\�Ab= � r7=O@#ENZ`��A�� m � n"m XOVdENZH_`r<VWA n"i E L VWA�SU=OGdE�s7A nq�h�7��� ~.z�EN=Ou<SHA � r7S

FHGWZUP AbZ<Xy� _H]UGJVJGW_H_`A{�T_�Ab= � r7=O@#ENZUg?A7� � =�.���y�����`����y�<�����T���b�<���9�U�  <�7�¢¡y�y�t£¤����¥�£¤¦N�#�U� �O§7¨v�8�©¥�£����¢¥l�O§N¥� 7���t���T�8¦{�{¥����h 7�9�[�y�7� <�9¥l�8�©¥��<�q�8¦{ª9¨v«O¥l���7�8�8�5�8¦{ª9¨v¦y�©¥l��ª9���{¥l�{�¤���5£��<¬J¦y�lª��¥�£���«y­N�<¦{ 7�5¨<��¦{¨v¦y��¦{�<�5 [�7�"ª9«?®¥l¯<¦N�[��¡7£��l�{�y¥D°��O§N¥l�l�y£����R�<�8���¦{ <�±®x���7����ª¢²[���8�9�<��¥l�8�lª9�8�9���b�l�y�?¥l«8�l£��©¥�£�³h <�8� h¥�£t�t£¤�l«8�¨v¦{ 7���[«8�O�l£������<�8�����b�l�y�?¥l´8���8��¨<��µh�?¯<¦{��¦y¶{£�³7 7�8�8·7¸q¦b¥l�����b¨[¨<��¦h�?¯7�"�8¦{�<�l£��©¥l�y­7�b¨<��´8�¹�º� �O§N®¥��l�b�O¥�£�¦{�¢�[��¥��8�lª�8�8­b°�«O¡b�y�t <�8�»���8� �b���l¦h�8£t��¥�£�¦{�7�»¨v¦y�l�l£�²[���8�»���y¥l����¥l�8�lª9�8�»�O¥ ���b�l�b�O¥l´8���8�¨<�©µ7�?¯7¦{��¦y¶N£¤³7 7�8�5³7 <£[�©¥l�l 7�O¥� 7�����{¥��¤�q�8¦y��¨� 7�5���D�8� �b¨<¨[ 7µN�y�y¥��l <�����3¥l¯<«8¦y�l£��q�<�"�d� £tª9¨[�t£ ®�8�b¥l£�¦{�R�©¥���¥�£��©¥�£�³h <�y·

¼ ½ ����5�.���&/^�� ���

i Ayg�IvrvP SU@�A�Z[XOg�g�r7SUg � r7=O@BA1IvA&X?A��[XOAbgB=?Ab_H=?;bg?A�Z[X?AbZ<X.IvAbg�u[S�ENZ<X8GtXO;bg�I w GWZ � [email protected]{XOGWr7Z¾P r<VWr<g ngOEhVWAbgb� i w p �[XO=8EhP�X8GWrhZ¿IvABz"r7ZHZ�EhGJg?g8ENZUP Ayg¢À�_�EN=�XOGW=TIvA�Á5A ��X?Ayg� p z�Á¢Ã�r7S1XOA ��X n @�GWZUGWZHf K FvGJg�ARÀA ��XO=8ENGW=?A'IHAbg$P r7ZHZ�EhGJg?g8ENZUP Ayg�_`Ab=�XOGWZUA�Z<XOAyg K P r7Z[X?AbZ[SUAbg$IUENZUg¢IvAbg$IHrhZUZH;�Ayg�X?A��[XOSHAyVJVtAyg K ÀBVxw¤EhGJIvAIvAyg�@�r�IvÄyVWAbg�SvX8GJVJGJg�;yg"AbZ p ��X?=8EhP XOGWr7Z&IvAyg¢z"rhZUZ�EhGWgOgOENZUP Ayg�IUENZUg3VWAyg�CTr7ZHZU;�Abgb�v\¹EN=O@#GÅVWAyg�@Br nIvÄyVWAbg�SvX8GJVJGJg�;bg�A�Z p z�Á K VdE9Iv;bP�rhSHF7Ab=�XOA3IvA3=?Ä�f<VWAbg¹I»w¤Ehg?g�rvP�GdE{X8Gtr7ZUg¹A�Z[X?=?A�XOAb=O@BAbg¹P�r7Z<XOA�Z�SUg¹IUENZUgVWAbg"XOA �[XOAyg"AyglX3g?rhSHF7AbZ<X3SvX8GJVWGJg?;�ABÂxÆ�ENAbIHP8]HADENZUI1�[X8E7ENM KUÇ ~7~7~HÈv:[ENZHA�XOÉ�Ê7rRA X$EhVx� KHÇ ~h~ � È e r�P8]HA KÇ ~7~ � Ã��i Ayg9=?Ä�f<VWAbgI»w¤Ehg?g�rvP�GdE{X8GWrhZ¾Â m f7=8E�Ë3EhV�A�X'EhVx� K¹Ì �h� � ÃTg�r7Z<X'IvAygTXOA�ZUIUENZUP�AbgDGJ@B_UVJGJPbE{X8GtF<Abg a ⇒ bA�Z[XO=?A&E{X?XO=OGtMUSvX8g�M`r�r7VW;bA�ZUgBPbEN=8EhP�XO;�=OGJg?;�Abg�_�EN=BIHA�Sv�Í@BAyg�SH=?Ayg�Î�VWA�g�SH_U_�r7=�X�A X�VdE¿P r7ZHÏ`E{Z�P A7�\¹EN=O@�GqVWAyg'GWZUIUGWP�AbgREhV�XOAb=?Z�E{XOG � g�IvA�u<S�EhVJGtXO;#_H=?r7_`r<g�;yg�IUENZUg�VdEÐVWGtXO;�=8E{XOSH=?A�ÂÑÁ�ENZÒA XBEhVx� K�Ç ~7~ � ÈQTS�GWVJVWA�X K»Ç ~7~ � È i A�ZUPyE#A XDEhVÑ� K»Ç ~7~ � à K ZHr7SUgTZHr7SUg9GWZ<XO;�=?Ayg?g�r7ZUg9À.VdE.@BAyg�SH=?ARI w GWZ[X?AbZUg?GtXO;RI»w GJ@ n_UVJGJPbE{X8GWr7Z1Iv;�ÏHZ�GtAD_�EN= e �`QT=8EhgD©QT=8Ehg K Ì � � �vÈ`QT=8Ehg�A�XTENVx� K Ì �h�7�<Ã��z"A�_`AbZUIUENZ<XTE�F7ENZ<X$I»w SHXOGJVJGJg�Ab=�VWAyg"X?AyPO]UZUGJu<SHAyg�I»w p z�C K VWAyg�Ivr7ZHZH;bAbg�VJGWZHf7SUGJg�XOGJu[SHAbg�Ivr<GtF7AbZ<X$g�S nMUGW=^SHZHA3_U]�Ehg�A$IvA$Á5=8EhG�XOAy@BA�Z[X m SvXOr<@#E{X8GJu<SHA$IvS i E{ZUf<ENf7A'ÂxÁ mTi à K Ivr7Z[XqVWA3MHSvXqAbg�XqI»w r7MvXOAbZUGW=À&_�EN=�XOGW=�I»w SHZÓX?A��[XOA K VJE1VJGJglXOA#IHAbgXOA�=O@BAygDu[S w GJV^P r7Z[XOGWAbZ<Xy��CTA#ZUr7@�MH=?AbSUg�Ayg'EN_H_H=?rvP8]HAbg'g?rhZ[X_H=?r7_`r<g�;�Ayg�Î�EN_H_U=?r�P8]HAbgDg�X8E{X8GJglX8GJu<SHAyg#±�vEhVWAy@ K¹Ì �7Ô7�<à K EN_H_H=?rvPO]HAygDVJGWZHf7SUGJglX8GJu<SUAbg�ÂxCE�FHGJI�ENZUI\qVdENZ<XOA K�Ì �h�h~HÈ�:[EhP�u[SHAb@#GWZ K"Ì �7� � à K r7SÕ@�Gt��XOAbgRu<S�G�P r<@'M�GWZHA�Z[XBVWAbgRIHA�Sv�ÕEN_H_H=?rvPO]UAbgR_H=?;bP�; nIvAbZ<XOAbg'©��@#EhI � E K Ì �7� � ÈUCEhGJVJVWA K»Ì �7� � Ã8�p ZÒZHr7SUg�GtZ�g?P =OGtF7ENZ[XRÀ1Vxw GWZ[XOA�=Og�AyP�X8GWrhZÒIvAyg'[email protected]'IvA�VdE�=?AyPO]UA�=OP8]HA.I»w GWZ � [email protected]ÓA XRIvSXOA ��X n @�GWZUGWZHf K ZHr7SUg5_U=?rh_`r<g�r7ZUg�SHZUA�@B;�X?]Ur�IvA�I»w ; XOSUIvA�A X¹IvAqF7EhVJGJIUE{XOGWr7ZRI»w SUZHA�GWZ�IvA �UEyX8GWr7Z�_�EN=IvAyg¢_H=?r7ÏUVJg¢_UglsHPO]Ur7VWr7f<GJu<SUAbgTIvARIvr�P�SU@BAbZ<X8g$X?=8EhGtX�ENZ<X9IHA'M�GJVJENZUgTIvARP�r<@B_`; XOA�Z�P AbgTP r<@B_`r7=�XOA n@BAbZ<X�EhVWAbgBIUENZUg�VWA&PbEhIv=?A&IHA&VdEÐX?]U;�r7=OGWA&IvA1VÑw GJ@B_�VWGJPyE{XOGWr7ZÕglX�E{XOGJg�XOGJu[SHA7� i w r7M � AyP�X8G � IvA&ZHrhXO=?A; XOSUIHA¢AbglX�I»w¤ENgOg�r�PbGWA�=�ÀDPO]`ENu[SHATPyE{=8EhP X?Äb=?A¢I»w SHZ�_H=?r7ÏUV�_UglsHPO]Hr<VWr7f<GJu<SHA K SHZHATPbVdENgOg�A¢IHA$X?Ab=O@BAyg��

- 409 - RNTI-E-5

Page 100: Egc05 atelier rnti-e-5_(extraits)

ARQAT : plateforme exploratoire pour la qualite desregles d’association

Xuan-Hiep Huynh∗, Fabrice Guillet∗, Henri Briand∗∗LINA CNRS FRE 2729 - Ecole polytechnique de l’universite de Nantes

La Chantrerie, BP 50609, 44306 Nantes Cedex 3, France{xuan-hiep.huynh, fabrice.guillet, henri.briand}@polytech.univ-nantes.fr

Resume. Le choix de mesures d’interet pour la validation des regles d’as-sociation constitue un defi important dans le contexte de l’evaluation de laqualite en fouille de donnees. Mais, comme l’interet depend a la fois de lastructure des donnees et des buts de l’utilisateur (decideur, analyste), cer-taines mesures peuvent s’averer pertinentes dans un contexte donne, et neplus l’etre dans un autre. Dans cet article, nous proposons un outil originalARQAT afin d’etudier le comportement specifique de 34 mesures d’interetdans le contexte d’un jeu de regles, selon une approche resolument explo-ratoire mettant en avant l’interactivite et les representations graphiques.

1 Introduction

L’etude et la conception de mesures d’interet (MI) adaptees aux regles d’associationconstitue un important defi pour l’evaluation de la qualite des connaissances en ECD.Les regles d’association (Agrawal et al. 1993) proposent un modele non supervise pourla decouverte de tendances implicatives dans les donnees. Malheureusement, en phasede validation, l’utilisateur (expert des donnees, ou analyste) se trouve confronte a unprobleme majeur : une grande quantite de regles parmi lesquelles il doit isoler lesmeilleures en fonction de ses preferences. Une maniere de reduire le cout cognitif decette tache consiste a le guider a l’aide de mesures d’interet adaptees a la fois a sespreferences et a la structure des donnees etudiees.

Les travaux precurseurs sur les regles d’association (Agrawal et al. 1993) (Agra-wal et Srikant 1994) proposent l’utilisation de 2 mesures statistiques : le support etla confiance. Ce couple de mesures dispose de vertus algorithmiques acceleratrices,mais n’est pas suffisant pour capter l’interet des regles. Afin de compenser cette li-mite, de nombreuses mesures complementaires ont ete proposees dans la litteratureet dissociees en 2 groupes (Freitas 1999) : les mesures objectives et les mesures sub-jectives. Les mesures subjectives dependent essentiellement des buts, connaissances,croyances de l’utilisateur qui doivent etre prealablement recueillis. Elles sont associeesa des algorithmes supervises ad hoc (Padmanabhan et Tuzhilin 1998) (Liu et al. 1999)permettant de n’extraire que les regles conformes ou au contraire en contradiction avecles croyances de l’utilisateur, et ainsi d’orienter la notion d’interet vers la nouveaute(novelty) ou l’inattendu (unexpectedness). Les mesures objectives, quant a elles, sontdes mesures statistiques s’appuyant sur la structure des donnees ou plus exactementla frequence des combinaisons frequentes d’attributs (itemsets). De nombreux travauxde synthese recapitulent et comparent leurs definitions et leurs proprietes (Bayardoet Agrawal 1999) (Hilderman et Hamilton 2001) (Tan et al. 2002) (Tan et al. 2004)

- 415 - RNTI-E-5

Page 101: Egc05 atelier rnti-e-5_(extraits)

Mesurer l’int eret des regles d’association

Benoıt Vaillant∗, Patrick Meyer∗∗∗, Elie Prudhomme∗∗,Stephane Lallich∗∗, Philippe Lenca∗, Sebastien Bigaret∗

∗GET ENST Bretagne / Departement LUSSI – CNRS UMR 2872Technopole de Brest Iroise - CS 83818, 29238 Brest Cedex, France

{prenom.nom}@enst-bretagne.fr∗∗Laboratoire ERIC - Universite Lumiere - Lyon 2

5 avenue Pierre Mendes-France, 69676 Bron Cedex, [email protected]

∗∗∗Service de Mathematiques Appliquees, Faculte de Droit,d’Economie et de Finance, Universite du Luxembourg,

162a, avenue de la Faıencerie, L-1511 [email protected]

Resume. Cet article presente nos travaux sur la mesure de l’interˆet des reglesd’association. Une vingtaine de mesures ont ete retenues, sur la base d’uncritere d’eligibilite. Differentes proprietes sont d’abord proposees qui fondentune etude formelle des mesures. Cette etude formelle se double d’une etudede comportement, grace a HERBS, une plate-forme developpee pour experi-menter les mesures sur des bases de regles. Il est alors possible de confronterla typologie formelle des mesures et la typologie experimentale. Une foistransformees en criteres, ces proprietes fondent une methode d’assistance auchoix de l’utilisateur. Le probleme de la validation est enfin aborde, ou l’onpresente une methode de controle du risque multiple adaptee au probleme.

1 Introduction

Nous nous interessons aux mesures relatives a l’interet des regles d’associationA → B

telles que definies dans (Agrawalet al., 1993) : dans une base de donnees transactionnelles,A → B signifie que si les articles qui constituentA sont dansle panier d’une menagere, alorsle plus souvent les articles qui constituentB le sont aussi. Les algorithmes de type APRIORI

(fonde sur le support et la confiance) ont tendance a produire un grand nombre de regles pastoujours interessantes du point de vue de l’utilisateur. Les mesures d’interet jouent alors unrole essentiel en permettant de pre-filtrer les regles extraites.

Cet article presente une synthese de l’ensemble de nos travaux sur la qualite des reglesd’association. C’est un resume de (Vaillantet al., 2005).

Differentes voies ont ete explorees. Ainsi, nous definissons des mesures et proposonsdes proprietes souhaitables section 2. La section 3 concerne le developpement de la pla-teforme experimentale HERBS. La section 4 est relative au developpement d’une aide a laselection de bonnes mesures. Les deux typologies des mesures, l’une fondee sur une ap-proche experimentale, l’autre sur une approche formelle sont mises en regard section 5.Enfin, la section 6 s’interesse a la validation des regles.

- 421 - RNTI-E-5