2èmes Rencontres Inter-Associations (RIAs2006) AFIA …eric.univ-lyon2.fr/~rias2006/presentations/Actes_finaux_v2.pdfsur des concepts communs. ... pour thème « la représentation

2èmes Rencontres Inter-Associations (RIAs2006) AFIA – ARIA – EGC – INFORSID – SFC –SFDS – LMO

Avec le soutien de l’ASTI

La classification et ses applications Laboratoire ERIC, Université Lumière Lyon 2

- 20 & 21 mars 2006 - http://eric.univ-lyon2.fr/~rias2006/

Actes des Rencontres

(AFIA) : Association Française d’Intelligence Artificielle – (ARIA) : Association de Recherche d’Information et Applications – (EGC) Extraction et Gestion des Connaissances – (LMO) : Langages et Modèles Objets –

(INFORSID) : Systèmes d’Information – (SFC) : Société Francophone de Classification – (SFdS) : Société Française de Statistique.

ASTI : Fédération des Associations Françaises des Sciences et Technologies de l’Information

http://eric.univ-lyon2.fr/~rias2006/

2èmes Rencontres Inter-Associations (RIAs2006) AFIA – ARIA – EGC – INFORSID – SFC –SFDS – LMO

Avec le soutien de l’ASTI

La classification et ses applications Laboratoire ERIC, Université Lumière Lyon 2

- 20 & 21 mars 2006 - http://eric.univ-lyon2.fr/~rias2006/

Actes des Rencontres

(AFIA) : Association Française d’Intelligence Artificielle – (ARIA) : Association de Recherche d’Information et Applications – (EGC) Extraction et Gestion des Connaissances – (LMO) : Langages et Modèles Objets –

(INFORSID) : Systèmes d’Information – (SFC) : Société Francophone de Classification – (SFdS) : Société Française de Statistique.

ASTI : Fédération des Associations Françaises des Sciences et Technologies de l’Information

http://eric.univ-lyon2.fr/~rias2006/

PREFACE

L'objectif de ces rencontres est de promouvoir les échanges scientifiques entre les différentes associations proches dans les domaines de l'informatique et des mathématiques appliquées, notamment la statistique. Ces associations couvrent des communautés qui ne se connaissent pas toujours. Pourtant, elles travaillent parfois sur des concepts communs. Ces rencontres vont permettre d'échanger les points de vues, les expériences, les outils, etc. développés de manière quasi indépendantes dans chacune des communautés.

Les premières rencontres ont eu lieu en mars 2005 à l'ENST Paris. Elles avaient pour thème « la représentation des données et des connaissances » (voir http://www.infres.enst.fr/rdc05/ ). Une centaine de participants ont pris part à ces rencontres. Pour l'édition 2006 de ces rencontres, le thème fédérateur retenu est celui de la classification automatique. On entend par là, le clustering, la taxinomie, le regroupement conceptuel et tout ce qui gravite autour du principe du regroupement automatique d'objets (au sens large) semblables.

http://www.infres.enst.fr/rdc05/

TABLE DES MATIERES

Distances entre données et application aux cartes de Kohonen, Vincent Lemaire, Gilles Bisson .....................................................................................7

Visualisation des classifications, Ludovic Lebart ............................................8

Pourquoi utiliser des modèles de mélange de lois de probabilité en classification? Gilles Celeux ............................................................................9

Méthodes de classification: Problèmes fondamentaux et approches algorithmiques, Hans Bock ............................................................................10

Bases de données et application au données multimédias, Noureddine Mouaddib et José Martinez............................................................................11

Variations sur l'utilisation des treillis de Galois pour la classification de connaissances et la modélisation par objets, Florence Le Ber, Marianne Huchard .........................................................................................................12

Traitement automatique des langues et classification automatique : méthodes et applications pour la recherche d'informations, Bellot Patrice ...................13

SuSE: Subspace Selection embedded in an EM algorithm, Laurent Candillier, Isabelle Tellier, Fabien Torre, Olivier Bousquet ........................15

Une nouvelle méthode de classification automatique, Mathieu Feuilloy, Daniel Schang, Pascal Nicolas ......................................................................17

Classification préalable à la recherche de règles d’association, Marie Plasse, Ndeye Niang, Gilbert Saporta........................................................................19

Classification de flux de Données par échantillonnages sur fenêtres inclinées, Baptiste Csernel, Fabrice Clérot, Georges Hébrail ......................................21

Comparaison interactive de regroupements – Une application aux données d’expressions de Plasmodium Falciparum, Fabien Jalabert, Vincent Derozier, Sylvie Ranwez, Michel Crampes Classification des données de grande dimension: application à la vision par ordinateur, Charles Bouveyron, Stéphane Girard, Cordelia Schmid ................................................................23

Classification des données de grande dimension: application à la vision par ordinateur, Charles Bouveyron, Stéphane Girard, Cordelia Schmid ............25

Reconnaissance par segmentation automatique de trajectoires d'un fauteuil roulant, AICH Ali, LORIETTE Sophie ...........................................................27

Classification automatique en Web Usage Mining, Alzennyr Da Silva.........29

Préparation supervisée de données dynamiques, Sylvain Ferrandiz, Marc Boullé .............................................................................................................31

Modélisation de la Topologie avec le Graphe Génératif Gaussien, Pierre Gaillard, Michael Aupetit ..............................................................................33

Régression et modèle de mélange pour le débruitage de signaux, Etienne Côme, Allou Same, Latifa Oukhellou, Patrice Aknin.....................................35

Une classification hiérarchique de variables discrètes basée sur l'information mutuelle en pré-traitement d'un algorithme de sélection de variables pertinentes, Hélène Desmier, Pascale Kuntz, Ivan Kojadinovic....................37

Cartes de pages Web obtenues par un automate cellulaire, David Ratsimba, Hanene Azzag, Gilles Venturini, David Da Costa, Christiane Guinot ..........39

Utilisation de points d’intérêt pour la classification interactive de données, David Da Costa, Gilles Venturini ..................................................................41

Markov random fields for clustering genes, Matthieu Vignes, Florence Forbes ............................................................................................................43

Evaluation en cascade d'algorithmes de clustering, Laurent Candillier, Isabelle Tellier, Fabien Torre, Olivier Bousquet...........................................45

Sur l'apprentissage de la structure de réseaux bayésiens à partir de bases d'exemples incomplètes, Olivier François, Philippe Leray ...........................47

Construction et classification d'objets d'image de télédétection par une approche itérative guidée par des connaissances du domaine, Sébastien Derivaux.........................................................................................................49

Extraction de caractéristiques de textures d’images satellitaires pour la classification, hanifi majdoulayne, sedes florence, aboutajdine driss, lasfar abdelali...........................................................................................................51

Distances entre données et application aux cartes de Kohonen

Vincent Lemaire*, Gilles Bisson**

* Ingénieur Expert R&D à France Télécom R&D, [email protected]

** Chercheur CNRS

[email protected] En classification non-supervisée (ou clustering), les cartes de Kohonen constituent une

méthode exploratoire intéressante. En effet, elles permettent de réduire efficacement la dimensionalité des données tout en conservant au maximum la topologie de l'espace . L'organisation finale des individus sous la forme de carte 2D facilite en outre la visualisation et l'interprétation des résultats. Comme dans beaucoup de méthode de clustering, les cartes de Kohonen reposent sur l'utilisation d'une distance entre individus (par exemple Euclidienne et Manahalobis) représentés de manière vectorielle. Or, la représentation de situations complexes nécessite de plus en plus l'utilisation de langages de représentation relationnels, c'est à dire de langages permettent de décrire des ensembles d'objets correspondant à des graphes ou des expressions en logique des prédicats. Nous montrerons comment il est possible de définir un indice permettant de calculer une distance sur ce type de représentation, ce qui permet d'étendre le domaine d'utilisation des cartes de Kohonen.

2èmes Rencontres Inter-Associations (RIAs'2006) 7

Visualisation des classifications

Ludovic Lebart

CNRS -GET/ENST [email protected]

Les techniques de classification non supervisée et les outils de visualisation de données

complexes sont deux thèmes récurrents dans la communauté EGC (Extraction et Gestion des Connaissances). On passera brièvement en revue les problématiques et les points de vues présentés dans ce cadre. A l'intersection de ces deux thèmes se trouvent les méthodes de visualisation des classifications. Une première approche pour visualiser les classifications consiste à procéder à des usages simultanés et complémentaires des analyses an axes principaux (diverses déclinaisons de la décomposition en valeurs singulières ou SVD) et des méthodes de classification classiques (k-means, nuées dynamiques, classifications hiérarchiques). Une seconde approche consiste à intégrer la préoccupation de visualisation dans l'algorithme même de classification (cartes auto-organisées ou SOM). Après avoir évoqué ces deux approches, on montrera que les graphes constituent un outil susceptible de jeter quelques ponts intéressants entre elles.

8 2èmes Rencontres Inter-Associations (RIAs'2006)

Pourquoi utiliser des modèles de mélange de lois de

probabilité en classification?

Gilles Celeux

Directeur de Recherche, Inria Futurs, Dept. de mathématiques. [email protected]

Cet exposé vise à présenter les atouts du modèle de mélange en vue de la classification

non supervisée de données. On montrera notamment comment cette approche par un modèle probabiliste donne accès, sans effort, à de nombreux modèles permettant de faire face à de nombreuses situations de classification.

Les modèles pour des données continues ou discrètes seront présentés. Les algorithmes de résolution de type EM et restauration-maximisation seront présentés. On attachera une importance particulière à l'importante question du choix de modèles et notamment du choix du nombre de classes pour lequel le modèle de mélange fournit un cadre formel rigoureux et efficace.

Des approches récemment développées comme l'approche bayésienne seront évoquées ainsi que des logiciels.


Méthodes de classification: Problèmes fondamentaux et approches algorithmiques

Hans Bock

Professeur, Institute of Statistics,

RWTH Aachen University, Wuellnerstr. 3, Allemagne [email protected]

Les méthodes dites ’clustering’ (classification, apprentissage non-supervisé) partent d’un

jeu de données décrivant les propriétés d’un ensemble d’individus (ou d’objets) et ont tous l’objectif de détecter des sous-ensembles d’objets (classes, clusters) qui sont ’homogènes’ dans un sens large, ’séparés’ l’un de l’autre, et ’utiles’ pour une application. Malgré l’ubiquité de ce problème, sa formalisation en termes mathématiques ou statistiques se révèle toujours difficile à cause de l’ambiguïté et du flou des concepts sous-jacentes. – Notre contribution discute ce problème fondamental et aborde un éventail d’alternatives pour la modélisation et la solution algorithmique, classiques et ’modernes’. En particulier, nous considérerons les aspects suivants:

La définition de ’similarité’, de ’classe’ et d’ ’ensemble homogène’; Les différents approches probabilistes, géométriques, axiomatiques, heuristiques; L’évaluation des classes et d’une classification; Nouveaux types de données: ADN, les micro-puces, donnes symboliques, web data; Problèmes et techniques spéciaux: two-way clustering, additive plaid clustering,

ensemble méthodes. Notre présentation devrait montrer, en passant, que les visions du problème de

’clustering’ sont souvent divergentes dans les domaines de statistique, machine learning, réseaux neuronaux, et computational statistics


Bases de données et application au données multimédias

Noureddine Mouaddib et José Martinez

ATLAS-GRIM, INRIA & LINA

FRE CNRS 2729 {Noureddine.Mouaddib, Jose.Martinez}@univ-nantes.fr

L'information contenue dans des bases de données volumineuses doit être synthétisée pour être exploitable. Plusieurs approches sont apparues aussi bien dans la litérature que dans les produits commerciaux, comme les bases de données multidimensionnelles et les entrepôts de données. Typiquement, ces solutions permettent d'informer les décideurs afin qu'il puissent faire des choix pertinents. Elles sont toutefois trop lourdes à déployer pour certains besoins. Nous proposons une approche alternative qui, partant des connaissances du domaine possédées par l'expert, permet à ce dernier d'obtenir une vue synthétique, hiérarchisée et immédiatement compréhensible par lui puisque s'appuyant sur son vocabulaire propre.

Cette approche a été mise en oeuvre pour divers types de données (dossiers médicaux, clientèle bancaire, programmes de télévision, fichiers de l'immigration aux Etats-Unis). Nous avons en particulier appliqué cette technique à la classification de données non standards, à savoir multimédias et plus précisément des images. Outre la faisabilité, la combinaison de deux techniques de classification a permis de construire des index multimédias ayant une complexité acceptable, et facilement maintenable. De manière plus générale, la classification est devenue une étape incontournable pour la gestion des données multimédias.


Variations sur l'utilisation des treillis de Galois pour la classification de connaissances et la modélisation par objets

Florence Le Ber*, Marianne Huchard**

*CEVH (ENGEES – ULP) et Orpailleur (LORIA Nancy), [email protected]

** Professeur, LIRMM, UMR 5506, CNRS et Université Montpellier 2,

[email protected]

Dans cette présentation, nous rappellerons les notions de base sur les treillis de Galois dont la construction permet de faire émerger un ensemble de concepts par abstraction d'un ensemble d'individus décrits par des propriétés. Une extension de cette théorie, appelée RCA pour "Relational Concept Analysis", qui permet de prendre en compte des descriptions relationnelles dans lesquelles un individu est décrit par ses liens avec d'autres individus, sera également exposée.

Deux applications des treillis de Galois seront détaillées. Dans un premier temps, nous montrerons la manière dont l'Analyse Relationnelle de Concepts est appliquée pour la généralisation de diagrammes UML et quel est l'intérêt de ces travaux dans le cadre de l'ingénierie des modèles. Dans le cas des diagrammes structurels UML, différentes sortes d'individus telles que les classes, les associations, les attributs ou les méthodes sont prises en compte et généralisées par construction itérative de différents treillis (un pour chaque sorte d'individus). Dans ce processus, la construction d'un treillis pour une sorte d'individus à une étape donnée tire parti des connaissances acquises de la construction des treillis pour toutes les sortes d'individus aux étapes précédentes. Cette méthode a été appliquée dans le cadre de projets industriels et nous tirerons les leçons de cette expérience.

Dans un deuxième temps nous expliquerons comment les treillis de Galois peuvent être utilisés dans le cadre de la représentation de l'espace, pour relier des ensembles de relations et des opérations ensemblistes sur des régions spatiales. Le treillis ainsi construit et implanté dans un système de représentation par objets permet de vérifier et de classer des relations entre régions d'une image ou d'une carte. Cette approche est utilisée dans le cadre d'applications géographiques.


mailto: [email protected]

Traitement automatique des langues et classification automatique : méthodes et applications pour la recherche

d'informations

Bellot Patrice

Maître de conférences, Université d’Avignon, Laboratoire d’Informatique LIA,

[email protected]

La recherche d'information elle-même peut être vue comme un problème de classification partageant l'espace de recherche en deux classes : la classe des textes contenant des informations pertinentes par rapport à une requête, et la classe de ceux n'en contenant pas. Mais au delà de cette simple constatation, les objectifs des méthodes de classification en recherche d'informations textuelles sont multiples. Nous en présenterons les principaux en énonçant les méthodes les plus couramment utilisées dans des systèmes opérationnels et qui font face au double problème du volume des données à traiter et des spécificités du langage naturel.

Il peut s’agir d’améliorer les performances des moteurs de recherche documentaire en terme de précision et de rappel en classant les documents trouvés éventuellement en fonction de leurs références communes à d’autres documents pour faire apparaître les liens qui les unissent (cartographie), de construire automatiquement des thésaurus, de classer des textes issus d’un flot continu (dépêches de presse) ou d'identifier des thématiques (veille technologique).


SuSE: Subspace Selection embedded in an EM algorithm

Laurent Candillier∗,∗∗, Isabelle Tellier∗, Fabien Torre∗, Olivier Bousquet∗∗

∗GRAppA - Université Charles de Gaulle - Lille 3∗∗Pertinence - 32 rue des Jeûneurs - 75002 Paris

Le subspace clustering [Parsons et al. (2004)] est une extension du clustering traditionnel[Berkhin (2002)] qui recherche un ensemble de clusters qui peuvent être définis dans différentssous-espaces. C’est le cas, par exemple, des données présentées dans la figure 1. L’intérêt detelles techniques est important dans le cadre de données contenant un nombre important de di-mensions car elles permettent de faire face à la malédiction de la dimensionalité. De plus, ellespermettent de fournir une description réduite des clusters obtenus car les clusters sont alorsdéfinis par un nombre restreint de dimensions. Or, la problématique de la compréhensibilitédes résultats obtenus en clustering est également importante.

X

Y

Z

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

�

� � ��

��

++++++++++++

+++++

+++

+

++

+

+++++

+

�

∈ X × Z

�

∈ X × Z

�

∈ Y × Z

+ ∈ X × Y

FIG. 1 – Exemple de 4 clusters définis dans différents sous-espaces.

Dans l’étude que nous présentons, nous mettons en avant l’intérêt d’utiliser des modèlesprobabilistes pour le subspace clustering. En particulier, nous montrons que le problème diffi-cile de la spécification des paramètres des méthodes de subspace clustering peut être vu commeun problème de sélection de modèle dans un cadre probabiliste. Ceci nous permet alors de dé-velopper un algorithme de subspace clustering qui, contrairement aux méthodes existantes, nenécessite aucune connaissance a priori de la part de l’utilisateur.

Nous mettons également en avant l’intérêt de permettre le chevauchement des clusters dansce cadre. De plus, le problème de la détection du bruit qui peut exister dans les données s’in-tègre naturellement dans une telle modélisation probabiliste. Et nous montrons qu’être capablede détecter le bruit permet de fournir un résultat plus compréhensible. Enfin, la prise en comptede différents types de dimensions est également facilitée dans le cadre probabiliste.

Nous avons donc développé et testé un tel algorithme de subspace clustering statistiquenommé SuSE, ainsi qu’une méthode originale permettant de fournir une représentation com-préhensible des clusters obtenus. Différentes expérimentations, menées sur des données aussi


SuSE

bien artificielles que réelles, ont mis en avant la pertinence de notre approche dans le cadrede la détection des clusters et de leurs sous-espaces spécifiques, ainsi que dans celui de lacompréhensibilité des résultats produits.

SuSE est basé sur le modèle classique de mélange de distributions de probabilités et l’utili-sation de l’algorithme EM [Ye et Spetsakis (2003)]. Un paramètre noté k spécifie le nombre declusters du modèle, et un autre paramètre noté d le nombre de dimensions utilisées pour carac-tériser ces clusters. La méthode globale de SuSE est alors de générer différents modèles avecdifférentes valeurs pour ces paramètres k et d, puis de sélectionner le modèle le plus appropriéaux données.

La figure 2 montre l’intérêt du critère BIC [Ye et Spetsakis (2003)], basé sur le calcul dela vraisemblance du modèle par rapport aux données et la pénalisation des modèles plus com-plexes, dans ce cadre de sélection de modèle. Elle montre, sur données artificielles, l’évolutionde la valeur du critère BIC en fonction de la différence entre le nombre réel K de clusters etle nombre k de clusters recherchés, et de la différence entre le nombre réel D et le nombresélectionné d de dimensions utiles pour caractériser ces clusters. On remarque dès lors quela valeur optimale du critère BIC est atteinte lorsque le nombre de clusters recherchés et lenombre sélectionné de dimensions utiles atteignent les nombres réels.

-3 -2 -1 0 1 2 3 4-4-2

02

40

60012001800

K-kD-d

-BIC

FIG. 2 – Évolution de la valeur du critère BIC en fonction de (K − k) et de (D − d)[pour une meilleure visualisation, -BIC est reporté au lieu de BIC].

Références

Berkhin, P. (2002). Survey of clustering data mining techniques. Technical report, AccrueSoftware, San Jose, California.

Parsons, L., E. Haque, et H. Liu (2004). Evaluating subspace clustering algorithms. In Work-shop on Clustering High Dimensional Data and its Applications, SIAM Int. Conf. on DataMining, pp. 48–56.

Ye, L. et M. Spetsakis (2003). Clustering on unobserved data using mixture of gaussians.Technical report, York University, Toronto, Canada.


Une nouvelle méthode de classification automatique

Mathieu Feuilloy∗,∗∗, Daniel Schang∗

Pascal Nicolas∗∗

∗ESEO, 4, rue Merlet de la Boulaye, BP 926, 49009 ANGERS Cedex 01, France{mathieu.feuilloy, daniel.schang}@eseo.fr,

∗∗LERIA, Université d’Angers, 2, bd Lavoisier, 49045 ANGERS Cedex 01, [email protected]

1 Introduction

La classification automatique (Xu et Wunsch, 2005) est une tâche importante pour la com-préhension d’un problème où peu d’informations sont connues. Ainsi, pour estimer l’organi-sation des observations du problème, l’analyse de groupes ou de clusters est nécessaire. Laméthode proposée possède une architecture commune aux méthodes hybrides classiques, ainsila première étape partitionne les données en clusters, tandis que la seconde étape lie les sous-clusters obtenus lors du partionnement. Les méthodes hybrides classiques considèrent géné-ralement un critère fondé sur des distances (Jain et Dubes, 1988) dans la détermination desliaisons entre les sous-clusters (comme les algorithmes hiérarchiques de type agglomératifs,avec Single-Linkage et Complete-Linkage). La méthode présentée se caractérise par un cri-tère fondé sur la similitude de l’orientation des sous-clusters. Cet indice de liaison permet deconserver la disposition naturelle des données. Ce critère utilisé dans un réseau de neurones(GMR : Generalized Mapping Regressor, Cirrincione et al. (2003)) pour des applications liéesà des problèmes de régression réalise de bonnes performances pour la reconnaissance automa-tique de formes complexes noyées dans du bruit.

2 Méthode

La méthode proposée s’oriente vers une technique hybride classique, soit une premièrephase de partionnement, puis une phase de liaison. La phase de partionnement peut être ef-fectuée par des algorithmes standards (comme K-means). L’innovation dans notre méthodede clustering réside dans la liaison des sous-clusters, en effet notre critère de liaisons n’ex-ploite pas uniquement l’information de la proximité entre les sous-clusters, contrairement auxméthodes hybrides classiques, qui utilisent différentes mesures de proximité (Jain et Dubes,1988). Ainsi, en plus de l’information de la proximité entre les clusters, notre méthode de liai-son s’emploie à déterminer une similarité entre les sous-clusters pour optimiser les liaisonsafin de conserver la topologie, ou la représentation naturelle des données. Pour cela, nous dé-terminons les Composantes Principales des sous-clusters, afin d’obtenir leurs orientations etde mesurer leurs similarités. Suivant ce critère, l’algorithme cherche à lier les sous-clusterspossédant une similitude suivant leurs orientations, tout en respectant une certaine proximité.Une fois plusieurs sous-clusters sélectionnés à la liaison, le choix de la liaison se porte sur lessous-clusters où la direction de la liaison est la plus proche de la direction du cluster à lier.


Une nouvelle méthode de classification automatique

3 ExpérimentationsLes trois exemples proposés (figure 1) possèdent 800 points, du bruit de fond défini aléa-

toirement suivant une distribution uniforme a été ajouté à hauteur de 200 points (soit une pro-portion de 20% sur l’ensemble des données). 100 essais ont été réalisés avec une initialisationdifférente par l’algorithme K-means de la partition contenant les sous-clusters. Ainsi, le ta-bleau 1 montre les résultats obtenus en comparant notre algorithme à deux méthodes hybridesclassiques utilisant des liaisons Single-Linkage et Complete-Linkage.

FIG. 1 – Exemples de problèmes bruités à deux classes.

Notre méthode Hybride Single Linkage Hybride Complete Linkage

Sans bruit de fond2 cercles 3.95 ± 6.82 (0) 0.00 ± 0.00 (0) 21.47 ± 5.52 (11.25)

2 demi cercles 4.19 ± 8.68 (0) 1.67 ± 8.26 (0) 20.83 ± 6.07 (11.50)2 spirales 3.93 ± 9.00 (0) 45.44 ± 3.84 (33.00) 42.08 ± 4.01 (32.44)

Avec 20% de bruit de fond2 cercles 17.35 ± 12.93 (0) 49.50 ± 0.00 (49.5) 23.99 ± 9.02 (7.75)

2 demi cercles 21.82 ± 12.42 (0) 49.50 ± 0.00 (49.5) 24.29 ± 11.37 (5.87)2 spirales 14.57 ± 10.25 (0) 50.00 ± 0.00 (50) 46.58 ± 2.74 (34.89)

TAB. 1 – Erreur moyenne de classification (moyenne ± écart type (valeur minimale)) suivantles trois exemples, avec et sans bruit de fond.

4 ConclusionsLes expérimentations réalisées (tableau 1) permettent d’observer la qualité de la reconnais-

sance de formes non séparables linéairement. On peut observer la qualité de notre algorithmeà reconnaître les trois formes, dans le cas où il n’y a pas de bruit de fond, l’erreur moyenne estinférieur à 5%. Ces formes noyées dans un bruit de fond permettent à l’algorithme de montrersa robustesse par rapport aux méthodes hybrides classiques.

RéférencesCirrincione, G., M. Cirrincione, C. Lu, et S. VanHuffel (2003). A novel neural approach to

inverse problems with discontinuities. In IEEE-IJCNN International Joint Conference onNeural Networks.

Jain, A. K. et R. C. Dubes (1988). Algorithms for Clustering Data. Prentice Hall.Xu, R. et D. Wunsch (2005). Survey of clustering algorithms. IEEE Transactions on Neural

Networks 16(3), 645–678.


Classification préalable à la recherche de règles d’association

Marie Plasse* **, Ndeye Niang* Gilbert Saporta*

*CNAM Laboratoire CEDRIC 292 rue St Martin Case 441 Paris Cedex 03 complète

[email protected], [email protected] http://cedric.cnam.fr/

**PSA Peugeot Citroën 45 rue Jean-Pierre Timbaud 78307 Poissy Cedex [email protected]

Cette communication décrit l’utilisation conjointe des méthodes de recherche de règles d’association et de classification de variables dans le cadre d'une application du secteur au-tomobile où plus de 80000 véhicules sont décrits par plus de 3000 attributs binaires rares. Rechercher des règles d’association (Agrawal & Srikant, 1994) sur un grand ensemble d'évé-nements rares conduit à une profusion de résultats difficiles à interpréter de part leur nombre et leur complexité. Nous proposons de réaliser une classification préalable des variables (Plasse et al., 2005) afin d'obtenir des groupes homogènes d'attributs puis de rechercher les règles d'association à l'intérieur de chacun de ces groupes. Nous avons réalisé plusieurs classifications de variables (Nakache & Confais, 2005) à l’aide d’un algorithme divisif et d’un algorithme agglomératif avec différents indices de similarité entre variables. Après avoir comparé deux à deux toutes les partitions obtenues grâce à l’indice de Rand. Nous avons ensuite procédé à la recherche des règles d'association à l'inté-rieur de chaque classe de variables, dans toutes les partitions. La classification descendante permet directement une réduction importante du nombre de règles, contrairement aux classi-fications ascendantes, où la réduction est moindre. Cependant ces dernières permettent de mettre en évidence une forte liaison entre certains attributs dont les associations multiples produisent des règles complexes en grand nombre. En isolant ces attributs, la réduction du nombre de règles obtenues est alors supérieure à 99% quelque soit la méthode de classifica-tion employée. De plus, la complexité des règles n'excède pas 5 attributs. Après avoir montré l'apport d'une classification de variables préalable à la recherche de rè-gles d'association, nous travaillons actuellement sur l'apport de la classification croisée à cette approche.

Références

Agrawal R., Srikant R. (1994). Fast Algorithms for Mining Association Rules. Proceedings of the 20th Int'l Conference on Very Large Databases (VLDB), Santiago, Chile.

Nakache J.P., Confais J. (2005) Approche pragmatique de la classification, Ed. Technip, Paris

Plasse M., Niang N., Saporta G. (2005). Utilisation conjointe des règles d’association et de la classification de variables. Journées de Statistique, Pau, France.



Classification de flux de Données par échantillonnages surfenêtres inclinées

Baptiste Csernel∗, Fabrice Clerot∗∗

Georges Hébrail∗∗∗

∗École Nationale Supérieure des TélécommunicationsDépartement Informatique et Réseaux.

[email protected],http://www.infres.enst.fr/ csernel/

∗∗France Télécom R&D2 avenue P. Marzin, 22307 [email protected]://www.rd.francetelecom.com

∗∗∗École Nationale Supérieure des TélécommunicationsDépartement Informatique et Réseaux.

[email protected]://www.infres.enst.fr/ hebrail/

Résumé.Cet article présente un nouvel algorithme pour résoudre le problèmede la classification des flux de données. L’approche proposée ici est une ap-proche simple basée sur un échantillonnage du flux entrant suivi d’un stockageintelligent des échantillons ainsi obtenus de façon à permettre une étude portantsur tout ou partie du flux. Cet algorithme est bien sur à une seule passe et tire sesavantages de sa capacité à traiter rapidement de grandes masses de données et ceen particulier en hautes dimensions. L’algorithme présenté est ensuite comparéavec CluStream, un algorithme qui constitue une des références du domaine.

Introduction

Un flux de données est une séquence infinie d’éléments générés de façon continue à unrythme rapide par rapport aux capacités de traitement et de stockage disponibles. Dernièrementle domaine des flux de données a été le sujet d’un intérêt grandissant de la part de différentescommunautés (base de données, analyse de données, réseaux) et ceci aussi bien du côté in-dustriel qu’universitaire. Le but de la méthode présentée ici est de réaliser une classificationautomatique sur de tels flux.

Principe

L’algorithme présenté ici se base sur une approche en deux temps et utilise l’échantillon-nage. Lors du passage du flux, certains de ses éléments sont échantillonnés aléatoirement et àtaux fixeα et placés dans un échantillon. Lorsque cet échantillon atteint une taille fixéeT , sesdates de début et de fin sont enregistrées avec son contenu et il lui est assigné l’ordre0. Un


Classification de flux de données par échantillonnage : StreamSamp

autre échantillon est alors commencé. Dès que le nombre d’échantillons d’un ordreo dépasseune limite fixéel, les deux plus vieux échantillons de cet ordre sont fusionnés en un seul échan-tillon d’ordre o + 1 recouvrant la même période que celle couverte par ses pères. Le nouveléchantillon ainsi constitué est construit par tirage aléatoire deT/2 éléments issus de chacun deses échantillons pères.

Un échantillon portant sur tout ou partie du flux peut ensuite être créé en fusionnant unnombre plus ou moins grand des échantillons sauvegardés (la totalité pour un échantillon por-tant sur tout le flux). Les échantillons doivent dans ce cas être pondérés pour que chaque élé-ment garde une représentativité égale, en assignant à un échantillon d’ordreo un poids2o. C’estsur cet échantillon final constitué en fonction de la portion du flux à analyser que porteront lesréels analyses. Il a été choisi d’appliquer au fichier final l’algorithme des nuées dynamiques,mais tout autre algorithme aurait pu convenir.

Tests et Conclusion

Pour évaluer les performances de StreamSamp des tests ont été effectués en le comparantà l’algorithme CluStream présenté dans Aggarwal et al. (2003), les tests effectués ont portésur les fichiers de données d’intrusions fournis pour la coupe KDD en 1999, et utilisés parAggarwal dans son article. En revanche, pour des raisons de contraintes sur le pré-traitementdes données, seul le fichier représentant seulement 10 pourcent des données totales a pu êtreutilisé. Il apparaît que dans toutes les situations, StreamSamp donne en moyenne de meilleursrésultats que Clustream, même si ses scores ont un peu plus de variabilité en faisant doncune alternative attractive à ce dernier. De plus, sa vitesse d’exécution rapide, indépendantede la dimension des éléments du flux et peu influencée par la longueur de ce dernier ainsique le faible nombre de paramètres qu’il nécessite pour fonctionner sont autant d’avantagepour StreamSamp. Enfin, si le champ d’étude se limite ici à la classification, les échantillonsréalisés peuvent être utilisé pour tout autre traitement issu de la fouille de données.

Références

Aggarwal, C., J. Han, J. Wang, et P. Yu (2003). A framework for clustering evolving datastreams. InProceedings of the 29th VLDB Conference, Berlin, Germany.

Summary

This article presents a new algorithm for data stream clustering. The approach proposedhere is simply based on the fundamental technique of sampling the entering stream followed byan intelligent storage of the generated samples thus allowing for the study of the entire streamas well as a part of it. This algorithm is of course one pass and benefits from it’s capability toprocess large amounts of data at a fast speed however high its dimensionality. The results ofthis algorithm are then compared with the ones given by CluStream a reference algorithm inthe field.


��

��

��

�

�� !�"�#��$�� %��$&'(��##��#��!��)*��+�,--,.�/%��$�0�1�

!��)/��2��)3�

��455��)6� �)��)3�

� ��7��$��8��$9��6��:��$��$��9��$�33;��)�

!��0��:��$��$��;��0�;��;��$��9��$��6(��

��9��9��$��3��6;��9��6(��<��$��

3��$��$��=��6�>��3��$&��;�9$��?��6�@9�)�'9��9��

$��6��$��90��9��$��9�� ;��9��$9�$��)�

��$;�� A�33��9�� 9�$�33;��$��$��;�� ;��3�@9��)��6��$��

$��3��3��:��9��9��3��B��9��(��9��9��9��6��$�

��$&��3��)��6��6��$��$��9$�)��

#�� ;�� :� �� (�� 9�� 9�� $�� 6�� $��

��)��A�6��$A��;6��$�33;��$��9��$A9��"

��9��3)��9�"��9��A�$��90�$�33;��;��@9��$9��6��

9��$��$��$�33;��3��)�7��(��0��$��

�� $�� $�� 9�� 90� $��;�� $A�� $��

$A��;B��$A��6��$��9��;��3�@9��$��@9B��9��;��)��

/��;�;��@9;��:�&��$��$��;��$A�0��$��6(��)�!9��;��"

�;��9��9��;��;��:� ��9��$��6�9��"

��$��6(��$��9��$�33;��$��$��$�6��3;@9��9��;��

��6��;�9�;��$�33��;��)��

� ��9�� 9�� 6(�� A�0��$�33;�� &��":"$��@9�� 9��

��$9�6;��$9��'�/��6��$��9�:��(��$A9��

��;��)��A�6��$��$��$��;��9��$��)��6��9�"

$;�� 9�� $A�� 9��;�� A�0��$��9��9��6;��<.---�

6(�� ,-�---��A�9��>)��$��;��;�;3��$A9��

�6�9��9��@9��6;�;��;��9�9��3��;��@9��;��;��

��9��$��$�6��)��

!�9��9��9��$��$��;��A��$��;��@9�)��A9��9��6(��9��

B�� ;� :�$�33;��3��<��$��$9��9��9��;��>�@9��"

�B�� 9�� B�� ;�� :� $�33;�� 3�� $�� $�33;�� )� ��

�9�� $��;��@9A��9��$�33��$��$;��$��$�� A�33��$A9��;;"

��:�9��)��$��$A��3��6��$��$�33;��69C�;��

$��$;��$��0��)�/�9��$��D9��9��6�9��3�9�

E F�4�9�� ;;�� ;� :�$�33;�� 9��$�6;�$A�� :��9��

$&��)��


��$��6�9��

� �� !�9� ;��9�� ;�9��9�� 9��;�� 6�9�� 9��

��;��*��$��E1F�@9��3��;3;��)�!�9��9��G��;��9��;��

$�33;��;�9��$��9��9��$��3��%��$��

��9$��$��;�9��)��

!��$��0�� ;��3�@9��9�� &�� @9;� :�9��6��)��

��90��6�� A�0��$A9��9�� 3�� $��

�0�;��<�� $�69��)>��$��$��$�33;��G�90��

��9G�9�� 9��)�� 9� ��6��$��9�� 33��9��9�� "

6�9�� 9� ��@9�� $�� ;�9�� $��

�A;��9G�9��)�/�9�� 9��;� A��$��6��$��

��9��;6��$��;��0�;��9��)��6��9��

��;��$��;��$9�$��)��

! "��;��;��9��;6�� $��;��9��0��9��$��;�

9��9��9��$��6��;��9;)�!�9��9��9��9��@9��

��;��9�9��$(��$��3��E,F��;��9��:��9��!�39��E.F)��6��0��"

�� $��9�� $��;��$A�0�� 9��;��9�� 0�;��

��9��9��9��;��;��9��$��;��(��;��9��

!��EHF)��9��"$��9��9��;�9��9�)��

�

�

�

��

��

��

��

�[1] *��$��I�� !9��*��J��6�#��I�9��

� �� !��*��6��)�1��9�)�1��9"

69�� --,)�

[2] ��9��)�)�� !�� "�� #�� 9��3��#�6��64�'�69�$�$�K�9��3�'��)�L��$)��)��9��

M)�!�$��$��)�N�6��J��O��1LLP)�

[3] #�$��!)�#�� $��)��6��9��/9��9��%&��)�1HL"1Q-��1LRH)��[4] M�9��M)��$��)��$��M)�#�� ' ��

!��$��6��3��###��9��3��9�� -- �<��3�� -- >��=��)� R"

L�� -- ��*�� ')�

[5] M��)�� (�� $� �� $� )�� 9�� 3��"��9��*�7��3��3��*�S�� --H)�


Classification des données de grande dimension:application à la vision par ordinateur

Charles Bouveyron∗,∗∗, Stéphane Girard∗

Cordelia Schmid∗∗

∗LMC-IMAG, Université Grenoble 1,∗∗Projet Lear, INRIA Rhône-alpes.

Résumé. Nous présentons une paramétrisation des modèles de mélangegaus-sien adaptée aux données de grande dimension. Cette modélisation donne nais-sance à des méthodes de classification supervisée et non supervisée. Nous appli-quons ces méthodes pour reconnaître des objets dans des images.

1 Introduction

L’apprentissage statistique est devenu ces dernières années une discipline spécifique. Eneffet, de nombreux domaines scientifiques ont besoin d’analyser des données de plus en pluscomplexes. On peut citer par exemple la vision par ordinateur qui fournit des données de trèsgrande dimension. Cependant, la classification de telles données est un problème difficile. Eneffet, dans des espaces de grande dimension, les performances des méthodes d’apprentissagesouffrent du phénomène dit du fléau de la dimension. Ce phénomène est dû au fait que la taillede l’échantillon est souvent petite devant le nombre de paramètres àa estimer, qui est fonctionde la dimension de l’espace.

2 Modèle de mélange gaussien pour la haute dimension

Nous proposons donc une modélisation gaussienne adaptée aux données de grande dimen-sion pour la classification. Nous faisons l’hypothèse que les données de grande dimensionvivent dans des sous-espaces qui peuvent être différents etdont la dimension intrinsèque estinférieure àa la dimension de l’espace. Nous supposons que les densités des classes sont nor-males multivariées. Nous proposons en outre de travailler,pour chaque classe indépendam-ment, dans son espace propre et nous supposons que la matricede covariance de la classeCi

est bloc-diagonale et ne possède quedi + 1 valeurs propres différentes. Cela implique que lesdonnées de la classeCi vivent dans un sous-espace propre à la classe de dimensiondi < p etque la variance en dehors de ce sous-espace est constante et correspond au bruit d’acquisitiondes données. Cette modélisation donne naissance àa une nouvelle méthode de discrimination,nommée Analyse Discriminante de Haute Dimension (HDDA), etune nouvelle méthode declassification automatique basée sur l’algorithme d’estimation EM, nommée Clustering desDonnées de Haute Dimension (HDDC).


Classification des données de grande dimension

FIG . 1 – Localisation de l’objet «vélo» gràce à l’HDDC et notre approche probabiliste : àgauche, l’image originale, au milieu, les points d’intérêts détectés et, à droite, l’objet localiségrâce aux points ayant la plus grande probabilité d’appartenir à l’objet.

3 Application à la reconnaissance d’objets

En vision par ordinateur, un des problème les plus difficilesest la reconnaissance d’objetsdans des images naturelles. La difficulté de cette tâche est due au fait que, d’une part, lesdonnées sont de grande dimension (en général supérieure àa 100) et, d’autre part, l’annotationmanuelle des données d’apprentissage n’est pas possible vue le nombre d’images et d’objetsexistants. Dans notre approche, chaque objet est modélisé comme étant composé de parties.Nous combinons ensuite les méthodes de classification en grande dimension et une approchefaiblement supervisée pour apprendre un modèle discriminant de chaque objet. Nous pouvonsainsi reconnaître dans une nouvelle image chacun des objetsappris. Nous avons testé notreapproche sur une base récente d’images et les résultats obtenus montrent que notre méthodesurpasse les méthodes existantes. La Figure 1 présente le résultat de la localisation d’un objetdans une image réelle.

Summary

We present a parameterization of the Gaussian mixture modeldesigned for high-dimensionaldata. This parameterization gives rise to supervised and unsupervised classification methods.We apply these methods to recognize objects in images.


Reconnaissance par segmentation automatique detrajectoires d’un fauteuil roulant

Ali Aich, Sophie Loriette

Institut Charles Delaunay, Laboratoire ISTIT/M2SUniversité de Technologie de Troyes

12, rue Marie Curie BP2060, 10010 Troyes Cedex{ali.aich, sophie.loriette}@utt.fr

Résumé.Ce travail propose d’appliquer le paradigme du raisonnement à partirde cas dans le domaine d’assistance aux personnes handicapées moteurs. L’ob-jectif est de décharger les personnes lourdement handicapées des contraintesde conduite d’un fauteuil roulant en les assistant dans la reproduction des tra-jectoires fréquemment employées. L’approche proposée repose sur deux étapesimportantes. La première étape consiste à reconnaître le trajet emprunté par lefauteuil en se basant sur un calcul de similarité avec ceux qui ont été déjà effec-tués. Dans la deuxième étape, un apprentissage automatique de nouveaux trajetsest proposé pour qu’ils soient utilisés dans les futures reconnaissances.

1 Introduction

Notre travail s’inscrit dans le cadre de la navigation d’un véhicule mobile dans un envi-ronnement incertain ou partiellement connu. L’objectif est de doter un fauteuil roulant d’unecapacité d’anticipation et de reproduction des trajectoires fréquemment employées par son uti-lisateur supposé lourdement handicapé. Le résultat escompté est une réduction considérable dunombre de commande de direction que l’utilisateur doit transmettre au fauteuil.

L’étude est appliquée dans le cadre du projet VAHM (Véhicule Autonome pour Handicapésmoteurs) Pruski et Ennaji (2001). Le fauteuil roulant permet de récupérer des données décrivantl’environnement de son utilisation (espace libre autour du fauteuil :rétrécissement) et d’autresdonnées indiquant son état telles que l’orientation du robot par rapport au point de départ.

Un trajet correspond à un déplacement du fauteuil d’un point de départ à un point d’arrivéeet il est défini par des historiques d’évolution des valeurs des différents paramètres. Deuxtrajets sont considérés similaires s’ils ont la même forme géométrique (similarité d’évolutiondes valeurs des orientations) et si ils sont effectués dans le même environnement (similaritéd’évolution des valeurs des rétrécissements). La difficulté de notre travail réside dans l’absenced’information sur la destination souhaitée par l’utilisateur. Deux approches de reconnaissancede trajets complets ont été proposées dans Aich et Loriette (2006a), Aich et Loriette (2006b).


2 Approche proposée

L’approche proposée dans ce travail est basée sur deux étapes importantes. La premièreétape consiste à reconnaître le nouveau trajet emprunté sur la base de sa similarité partielleavec ceux qui ont été déjà effectués. La deuxième étape consiste à apprendre automatiquementde nouveaux trajets. Dans ce contexte, le raisonnement à partir de cas nous semble le plusintéressant car l’expérience a un rôle crucial dans l’assistance de l’utilisateur du fauteuil enreproduisant les trajets fréquemment employés.

Pour effectuer un trajet, l’utilisateur du fauteuil définit une suite de directions choisies àl’aide d’une console. Nous définissons un cas par un segment de trajet, effectué entre deuxchangements significatifs de son orientation par rapport à la direction initiale. Une base de casà deux niveaux est proposée : un niveau inférieur contenant des segments de trajets appelésdes cas sources et un niveau supérieur qui contient des trajets complets mémorisés sous formed’une séquence d’adresses des cas du premier niveau inférieur qui les composent.

Un cas cible représente un segment du nouveau trajet à reconnaître. La sélection du cassource le plus similaire au cas cible se fait en deux étapes. Dans la première étape, les cassources représentant une similarité de forme géométrique avec le cas cible sont sélectionnés(similarité des orientations et la distance parcourue). Durant la deuxième étape, les cas déjà sé-lectionnés sont parcourus pour sélectionner ceux qui représentent une similarité avec le nouvelenvironnement d’utilisation du fauteuil (similarité des rétrécissements).

Deux types d’apprentissage sont proposés. Si le nouveau trajet a été totalement ou partiel-lement reconnu (des morceaux de trajets représentant des cas sources ont été sélectionnés pourle reconnaître) alors les nouveaux segments effectués sont ajoutés dans la base de cas. Dans lecas contraire, le nouveau trajet est complètement inséré après sa segmentation.

Références

Aich, A., et S. Loriette (2006a). Apprentissage automatique de trajectoires d’un fauteuilroulant. Conférence Internationale Francophone d’Automatique-CIFA 2006, 6 pages.

Aich, A., et S. Loriette (2006b). Assistance aux personnes handicapées moteurs par réutilisa-tion d’expériences.14ième Atelier de Raisonnement à Partir de Cas, 14 pages.

Pruski, A., et M. Ennaji (2001). Symbiotic Humam-Machine Architecture for a smart wheel-chair control.European Conference for the advancement of assistive technology in europe.

Summary

This work presents the use of the case-based reasoning paradigm in the field of assistance topeople with disabilities. The objective is to discharge the user from the constraints of a wheel-chair control by assisting them in the reproduction of the trajectories frequently employed.The approach proposed is based on two important steps. The first one consists in recognizingthe trajectory followed by the wheelchair based on a measure of the similarity with each onealready carried out. In the second, the new trajectories are automatically learned so that theyare used in the future recognitions.


Classification automatique en Web Usage Mining

Alzennyr C. G. da Silva

Projet AxIS, INRIA-Rocquencourt

Domaine de Voluceau, B.P. 105, 78153 Le Chesnay Cedex, France

[email protected]

Résumé. L’apparition des nouvelles technologies d’information telles que le

Web a eu pour conséquence l’apparition d’une grande masse de donnés. Ré-

sumer ces données, pour mieux les exploiter, est devenu donc une évidence.

Notre approche consiste à construire automatiquement des classes homogènes

à partir de ces données et de définir des nouvelles unités statistiques décrivant

ces classes. Tout en réduisant de manière importante le tableau de donnes ini-

tiales, la représentation de ces données doit contenir d’un maximum

d’informations. C’est cette problématique qui est traitée dans le cadre du Web

Usage Mining. Dans ce travail, nous allons effectuer des analyses sur le site

Web du Centre d’Informatique (CIn) de l’université fédérale de Recife/Brésil

(www.cin.ufpe.br). Ce site est très bien structuré et son contenu sémantique est

bien défini. Pour cette analyse, nous avons utilisé les sources d’information

suivantes : les traces d’usage des internautes (fichiers « log ») et les informa-

tions sémantiques du site (structure, avis d’experts, etc.). Pour appliquer notre

méthode nous avons récupéré des fichiers contenant les traces d’accès au

site pendant la période d’une année complète (du 26 Juin 2002 jusqu’au 26

Juin 2003). Par la suite nous avons appliqué sur cet ensemble de données la

méthode de classification croisée dont l’objectif est de classer simultanément

les lignes et les colonnes d’un tableau de données croisées. La convergence de

l’algorithme est basée sur la cohérence entre la fonction d’affectation des li-

gnes et la fonction d’affectation des colonnes du tableau de données. La mé-

thode de classification croisée représente une solution efficace pour la recher-

che conjointe d’une typologie sur l’ensemble des individus (représentés par les

lignes du tableau de données) et une taxonomie sur les modalités des variables

(représentées par les colonnes du tableau de données). Comme résultat nous

avons identifié quatre groupes dominants d’utilisateurs. Dans ce contexte, l’un

des objectifs de l’analyse de l’usage est de bien comprendre le comportement

des utilisateurs d’un site Web et à partir de cette connaissance pouvoir meilleur

leur servir. Ceci type de connaissance est également envisagé par le commerce

électronique en ce qui concerne les définitions de nouvelles stratégies de mar-

keting.



Préparation supervisée de données dynamiques

Sylvain Ferrandiz∗,∗∗, Marc Boullé∗

∗France Télécom R&D,2, avenue Pierre Marzin, 22300 [email protected],

[email protected],∗∗GREYC, Université de Caen,

boulevard du Maréchal Juin, BP 5186, 14032 Caen Cedex,

Résumé. L’aspect technique représentant de moins en moins une contrainte, ilest aujourd’hui possible de suivre dans le temps les caractéristiques mesurées.Le statisticien est en conséquence confronté à la présence d’un nombre crois-sant de variables dynamiques. Dans le cadre de la préparation de données pourla classification supervisée, nous développons une méthode d’évaluation de lapertinence d’une variable dynamique. Le propos est illustré sur un problème declassification de courbes de consommation téléphonique.

1 Evaluation supervisée de variables dynamiques

Avec l’émergence des systèmes d’information au tournant des années 90, la récolte desdonnées brutes a été rendue indépendante de toute finalité statistique. Modéliser directementde telles données est devenu impossible. La phase de préparation des données, dont l’objectifest de construire une table de données pour modélisation à partir des données brutes, est doncdevenue une partie critique et souvent coûteuse en temps du processus de fouille de donnéesChapman et al. (2000).

L’évolution des moyens techniques le permettant, il est aujourd’hui possible de mesurerl’évolution dans le temps d’une caractéristique, et ce sur une longue période. A côté des va-riables usuelles, qu’on qualifie de statiques, sont donc de plus en plus présentes des variablesdynamiques : mesure de l’activité cardiaque en médecine, mesure de la pression en météoro-logie, mesure de la consommation téléphonique en télécommunication,. . .

En phase de préparation, les variables dynamiques sont placées dans le même contexteque les variables statiques et sont naturellement amenées à subir les mêmes traitements. Si oncherche à expliquer une variable cible symbolique, les tâches principales de préparation sontl’évaluation de la dépendance entre variable(s) explicative(s) et variable cible, et la sélectionde variables explicatives.

On se propose dans ce papier d’illustrer l’apport de la méthode introduite par Ferrandiz etBoullé (2006) à l’évaluation supervisée de variables dynamiques. Pour cela, on conduit uneexpérimentation sur un problème de classification de profils de consommation en téléphoniefixe.


Préparation de données dynamiques

FIG. 1 – Caractéristiques des groupes 1, 4 et 7. Les instances du groupe 1 correspondent à detrès fortes consommations, avec des pics très marqués. Le groupe 1 contient majoritairementdes instances de classe C.

2 Classification de profils de consommationOn illustre les apports de la méthode décrite dans Ferrandiz et Boullé (2006) pour l’éva-

luation de variables dynamiques. On considère un problème de classification de 2636 profilsde consommation suivant 4 classes cibles A, B, C et D. La distribution des classes cibles estuniforme sur l’échantillon. On dispose de 168 variables descriptives continues, chacune me-surant la consommation téléphonique sur une tranche horaire de la semaine, constituant ainsiune variable dynamique.

L’évaluation fournit une valeur du critère de 0.051, ce qui est très faible et caractérise unfort mélange des classes cibles. La méthode partitionne les instances en 7 groupes. En calculantla valeur moyenne de chacune des 168 variables et ce dans chaque groupe, on obtient 7 profilsde consommation caractéristiques. Trois de ces profils sont reportés sur la Figure 1, ainsi quele profil moyen de consommation (i.e. celui calculé sur tout l’ensemble d’apprentissage). Deplus, à chaque groupe est associée une distribution des classes cibles, qu’on représente par deshistogrammes groupés sur cette même figure.

Le résultat est facilement interprétable. Par exemple, le profil moyen des instances dugroupe 7 se distingue du profil moyen global par une consommation plus élevée. Ces ins-tances sont en grand nombre (35% des instances) et la répartition dans les classes cibles A, B,C, D est (41%, 26%, 15%, 17%). Le groupe 1 est quant à lui plus discriminant (la répartitiondans les classes cibles est (16%, 20%, 57%, 6%)), mais de taille réduite (4% des instances) : ilcaractérise un comportement atypique mais discriminant.

RéférencesChapman, P., J. Clinton, R. Kerber, T. Khabaza, T. Reinartz, C. Shearer, et R. Wirth (2000).

CRISP-DM 1.0 : step-by-step data mining guide.Ferrandiz, S. et M. Boullé (2006). Sélection supervisée d’instances : une approche descriptive.

In Actes de la conférence EGC, Volume 2, pp. 421–432.


Modélisation de la Topologie avec le Graphe GénératifGaussien

Pierre Gaillard∗, Michaël Aupetit∗

∗ CEA-DASEBP12 - 91680 - Bruyères-le-Châtel

{pierre.gaillard, michael.aupetit}@cea.fr

1 Introduction

Par topologie d’un nuage de points, nous entendons topologie des variétés principales dece nuage, i.e. des variétés supports de leur densité de probabilité sans le bruit. Modéliser latopologie ne doit pas être confondu avec le problème de la réduction de dimension par projec-tion qui permet de visualiser en 2D le nuage de point déformé. Le but n’est pas de visualisermais d’extraire du nuage de points l’information topologique (connexité, dimension intrin-sèque, nombres de Betti (nombres de trous, de tunnels, de vides...)). Les intérêts applicatifsse retrouvent dans l’analyse exploratoire de données (caractéristiques topologiques en sus descaractéristiques géométriques et statistiques)[1], dans la reconnaissance de formes (critères to-pologiques de comparaison), dans la classification non-supervisée (une composante connexecorrespond à une classe), dans la plannification de trajectoire (recherche du plus court cheminle long d’une variété)...Nous présentons dans cet article une méthode faisant référence à [2].

2 L’existant

L’idée principale des approches existantes [3] est le positionnement de prototypes sur lenuage de points (e.g. par quantification vectorielle) puis la construction d’un graphe de cesprototypes dont l’existence des liens est conditionnée à la présence de points dans leur régiond’influence. La forme des régions d’influences est le principal obstacle à l’introduction decritères statistiques pour la création des liens du graphe. En particulier, la présence de bruitdans les données entraine la création de liens en surplus qui altèrent la qualité du modèle.

3 Ce que nous proposons

Nous proposons une approche statistique basée sur l’idée que deux objets de même géo-métrie ont nécessairement même topologie. Tout d’abord, on suppose que les données sontissues d’une loi de probabilité p de support M. Dans notre cas, nous sommes en fait intéresséspar la topologie de M

prin (en référence à [4]) qui peut être vu comme le support M sans lebruit. On suppose que les données ont été générées par des points et des segments constituantainsi le support Mprin qui a été corrompu par un bruit additif gaussien de moyenne nulle et


Modélisation de la Topologie avec le Graphe Génératif Gaussien

−0.1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8−0.2

0

0.2

0.4

0.6

0.8

1

1.2

−0.1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8−0.2

0

0.2

0.4

0.6

0.8

1

1.2

(a) (b) (c) (d)

FIG. 1 – – (a) Points, prototypes et graphe de Delaunay. Modèle génératif (b) initial et (c) final. (d)Graphe modèle de la topologie.

de variance σ2. Nous définissons ensuite un modèle de mélange gaussien qui est formé de

deux noyaux gaussiens appelés "points gaussiens" et "segments gaussiens" afin d’expliquer lesdonnées observées. Le modèle ainsi formé est appelé le Graphe Génératif Gaussien (GGG).Les points gaussiens sont placés à l’aide d’un algorithme de quantification vectorielle puis lessegments gaussiens sont définis par les arcs du graphe de Delaunay des prototypes. Le modèlede mélange associé à ce graphe forme le modèle GGG. Afin de déterminer les paramètres opti-maux du modèle nous maximisons sa vraisemblance à l’aide de l’algorithme EM. La topologiedu graphe obtenu modélise alors celle du nuage de points (cf. Figure 1).

4 Conclusion

L’approche générative permet la prise en compte d’un modèle du bruit ce que ne permettentpas les approches précédentes purement géométriques. L’introduction d’un modèle statistiqueouvre la voie à tout l’arsenal théorique de l’apprentissage statistique pour la résolution duproblème de modélisation de la topologie. Dans nos futurs travaux, nous chercherons à utiliserles modèles de mélanges gaussiens pour positionner les points gaussiens mais aussi étendre cemodèle au cas supervisé.

Références

[1] M. Aupetit and T. Catz, High-dimensional labeled data analysis with topology representing graphs,Neurocomputing, 63:139-169, 2005.

[2] M. Aupetit, Learning topology with the gaussian generative graph and the EM algorithm, NIPS 2005

[3] V. de Silva and G. Carlsson, Topological estimation using witness complexes, Eurographics, Zurich,juin 2004.

[4] Tibshirani R, Principal curves revisited, Statiscal and Computing, 2:183-190, 1992.

Summary

We propose a generative model based on the Delaunay graph and the EM algorithm tomodel the topology of a set of points.


Régression et modèle de mélange pour le débruitage designaux

Etienne Côme∗, Allou Samé∗

Latifa Oukhellou∗, Patrice Aknin∗

∗Institut National de Recherche sur les Transports et leur Sécurité (INRETS)2, avenue du general Malleret-Joinville. 94114, Arcueil

{come,same,oukhellou,aknin}@inrets.fr

Résumé. Cet article propose une méthode de débruitage de signaux dans lecadre du diagnostic de défauts dans le domaine ferroviaire. La méthode propo-sée est basée sur un modèle de régression dans lequel le bruit, supposé additif,est distribué suivant un mélange de densités normales. Un algorithme de typeEM spécifique est utilisé pour estimer les paramètres de ce modèle.

1 Introduction : cadre du travail de thèseLe travail présenté ici s’inscrit dans le cadre plus large d’une thèse traitant du diagnostic

par suivi de point de fonctionnement avec une application dans le domaine ferroviaire.Le diagnostic d’un système complexe consiste à détecter et à identifier son mode de fonc-

tionnement à partir d’une ou de plusieurs mesures effectuées sur ce dernier. Le but est d’affecterun signal de mesure, représenté par plusieurs paramètres constituant un vecteur forme, à l’unedes différentes classes de fonctionnement.

La mise au point d’un tel système de diagnostic nécessite en général une étape préalablede paramétrisation du ou des signaux de mesure. La méthode proposée dans cet article estbasée sur un modèle de régression ; les coefficients de régression étant directement utiliséscomme paramètres. En outre, elle permet un débruitage fin des signaux grâce à l’utilisationd’un modèle de bruit suivant un mélange de densités normales.

2 Bruit additif et modèle de mélangeLe signal est représenté par un échantillon indépendant ((x1, y1), . . . , (xn

, yn)) issu du

couple (x, y) où x est la variable réelle indépendante, par exemple le temps et y la variableréelle dépendante qui désigne le signal à un instant donné.

Les connaissances physiques sur les signaux étudiés (Oukhellou et al., 2006) permettentde restreindre la classe des fonctions de regression aux polynômes du second degré. Le signalobservé est donc modélisé par : y = ax

2+bx+c+ε où ε est un bruit additif dont la distributionest indépendante de x.

Habituellement, le bruit ε est distribué suivant une densité normale centrée en zéro et l’es-timation des paramètres du modèle de régression se ramène à un problème de moindres carrés.


Régression et modèle de mélange pour le débruitage de signaux

Dans notre application, la présence d’une autre source de bruit liée à un paramètre physiqueintervenant dans le processus de mesure rend cette approche non valide. Pour résoudre ce pro-blème, nous supposons que le bruit ε est distribué suivant le mélange de deux lois normales :

f(ε) = π1N (ε; 0, σ2

1) + π2N (ε;µ, σ

2

2),

où N (·;µ, σ2) désigne la loi normale de moyenne µ et de variance σ

2, et π1 et π2 sont lesproportions du mélange vérifiant π1 + π2 = 1.

3 Estimation des paramètres par l’algorithme EMNous utilisons la méthode du maximum de vraisemblance pour estimer les paramètres du

modèle. On peut facilement vérifier que la densité de la variable y est donnée par le mélange

f(y;Ψ) = π1N (y ; ax2 + bx + c , σ

2

1) + π2N (y ; ax

2 + bx + c + µ , σ2

2),

où Ψ = (a, b, c, µ, σ2

1, σ

2

2) est le vecteur paramètre du modèle.

La maximisation de la vraisemblance étant difficile à effectuer directement, l’algorithmeGEM est utilisé (Dempster et al., 1977; Bartolucci et Scaccia, 2005).

4 Résultats et perspectivesL’approche présentée ci-dessus a été testée sur des signaux réels et fournit des résultats

satisfaisants (voir figure 1). Une étude complémentaire sur des signaux simulés est en cours,afin de valider la méthode et quantifier les erreurs de débruitage.

FIG. 1 – (A gauche) Signal réel et signal débruité ; (à droite) histogramme et densité mélange estimée du bruit

RéférencesBartolucci, F. et L. Scaccia (2005). The use of mixtures for dealing with non-normal regression

errors. Computational Statistics and Data Analysis 48, 821–834.Dempster, A. P., N. M. Laird, et D. B. Rubbin (1977). Maximum likelihood for incomplete

data via the em algorithm. J. Royal. Stat. Soc. (B) 39, 1–38.Oukhellou, L., P. Aknin, et E. Delechelle (2006). Infrastructure system diagnosis using empi-

rical mode decomposition and hilbert transform. ICASSP’06 Toulouse.


Une classification hiérarchique de variables discrètes baséesur l’information mutuelle en pré-traitement d’unalgorithme de sélection de variables pertinentes.

Hélène Desmier∗,∗∗ Pascale Kuntz∗

Ivan Kojadinovic∗

∗LINA CNRS FRE 2729, Site Polytech Nantes, rue Christian Pauc, 44306 Nantes, France{prenom.nom}@polytech.univ-nantes.fr,http://www.sciences.univ-nantes.fr/lina/fr/

∗∗PerformanSe SAS, Atlanpole La Fleuriaye, 44470 Carquefou, France{prenom.nom}@performanse.fr

http://www.performanse.fr

Le problème de la sélection de variables en discrimination se rencontre généralementlorsque le nombre de variables pouvant être utilisées pour expliquer la classe d’un individuest très élevé. Le rôle de la procédure de sélection de variables consiste alors à sélectionnerun sous-ensemble de variablespotentiellement discriminantespermettant d’expliquer la classede façon optimale. La nécessité de ce traitement préalable est essentiellement due au fait que,généralement, l’utilisation d’un nombre de variables discriminantes trop élevé dans un mo-dèle de discrimination détériore grandement sa capacité degénéralisation. D’un point de vuestructurel, une procédure de sélection de variables peut être vue comme composée de deuxéléments fondamentaux Liu et Motoda (1998) : unemesure de pertinence, utilisée pour mesu-rer l’influenced’un sous-ensemble de variables potentiellement discriminantes sur la variablequalitative à expliquer, et unalgorithme de recherche, dont le rôle est deparcourir l’ensembledes sous-ensembles de variables à la recherche d’un sous-ensembleoptimal ou sous-optimalau sens de la mesure de pertinence. Du point de vue de la définition de la mesure de perti-nence, les procédures de sélection de variables peuvent être essentiellement regroupées en deuxclasses Liu et Motoda (1998) : les procéduresfiltres et les procéduresmodèle-dépendantes.Dans le cas des procédures filtres, la sélection de variables est totalement indépendante dumodèle de discrimination choisi et s’effectue en tant que traitement préalable à la phase d’esti-mation. En revanche, dans le cas des procédures modèle-dépendantes, la mesure de pertinenceest définie à l’aide du modèle de discrimination choisi, généralement en fonction de l’erreurdu modèle sur un ensemble test. Bien que les procédures filtres soient en général plus rapidesen termes de temps de calcul, leur principal inconvénient est que le sous-ensemble de variablessélectionné risque de ne pas être optimal quel que soit le modèle de discrimination utilisé par lasuite.En ce qui concerne les procédures modèle-dépendantes, un prérequis fondamental du mo-dèle de discrimination choisi est que son estimation soit peu coûteuse en temps de calcul. Cettedernière condition implique que l’utilisation des modèles les plus populaires, tels que les arbresde décision, est difficilement envisageable lorsque le nombre de variables potentiellement dis-criminantes est élevé. Dans le cadre de ce travail, nous nous intéressons au cas où les variables


Une classification hiérarchique de variables discrètes basée sur l’information mutuelle.

potentiellement discriminantes sont toutes discrètes. Notre travail se découpe en deux parties.Tout d’abord, nous proposons des mesures de pertinence peu coûteuses en terme de temps decalcul fondées sur une troncaturek-additive de l’information mutuelle. L’utilisation de l’in-formation mutuelle en tant que mesure de pertinence a déjà été considérée à de nombreusesreprises dans la littérature (voir e.g. Wang et al. (1998); Hutter et Zaffalon (2005)). L’approxi-mation que nous présentons ici peut permettre d’envisager, même pour les problèmes de trèsgrande dimension, un parcours quasi-exhaustif des sous-ensembles de variables potentielle-ment discriminantes. Dans un deuxième temps, nous nous sommes intéressés à la réduction del’espace de recherche. Pour cela, nous avons choisi de faire, en pré-traitement de l’algorithmede sélection de variables, uneclassification ascendante hiérarchiquesur les variables poten-tiellement discriminantes. La notion de similarité entre variables coincide généralement dans lalittérature avec celle de dépendance fonctionnelle Nicolau et H.Bacelar-Nicolau (1998). Nousavons donc utilisé l’information mutuelle comme indice de similarité entre variables. Cetteétape nous permet de structurer notre ensemble de variables enk classes. Notre heuristique estde supposer que des variables d’une même classe sont suffisamment dépendantes pour n’engarder qu’une seule par classe.

Références

Hutter, M. et M. Zaffalon (2005). Distribution of mutual information from complete and in-complete data.Computational Statistics and Data Analysis 48, 633–657.

Liu, H. et H. Motoda (1998).Feature selection for knowledge discovery and data mining.Kluwer Academic Publishers.

Nicolau, F. et H.Bacelar-Nicolau (1998). Some trends in the classification of variables. InC. Hayashi, N. Ohsumi, K. Yajima, H. Bock, et Y. Baba (Eds.),Data Science, Classificationand related methods, pp. 89–98. Springer.

Wang, H., D. Bell, et F. Murtagh (1998). Relevance approach to feature subset selection.In H. Liu et H. Motoda (Eds.),Feature extraction, construction and selection, pp. 85–99.Kluwer Academic Publisher.


Classification par automate cellulaire appliqué àl’apprentissage de cartes de pages web

David Ratsimba∗, Hanene Azzag∗∗, David Da Costa∗∗

Christiane Guinot∗∗,∗∗∗ Gilles Venturini∗∗

∗Laboratoire ERIC, Université Lumière Lyon 2,Bat. L, 5 avenue Pierre Mendès, 69676 Bron Cédex, France.

[email protected], http://eric.univ-lyon2.fr/∗∗Laboratoire d’Informatique, Ecole Polytechnique de l’Université de Tours,

64, Avenue Jean Portalis, 37200 Tours, France.{david.dacosta,hanene.azzag, venturini}@univ-tours.fr,

http://www.antsearch.univ-tours.fr/webrtic∗∗∗C.E.R.I.E.S., 20, rue Victor Noir, 92521 Neuilly-sur-Seine Cédex, France.

[email protected]

La visualisation d’un ensemble de documents a pour objectifde présenter d’une manièrela plus informative possible ces documents à un utilisateurafin de lui permettre de naviguerdans cet ensemble et d’accomplir une tâche donnée. Si l’on considère le modèle visuel repré-senté par les cartes ("topic maps") (Kohonen 1988) (Wise 1999) par opposition aux systèmesutilisant des graphes (Kartoo, Mapstan, TouchGraph GoogleBrowser), des nuages de points etautres représentations (Cugini 2000), on peut dire que les avantages des cartes sont de pouvoirreprésenter un grand ensemble de documents et les regroupements que l’on peut y effectuer,de donner une vue globale de cet ensemble qui met en lumière les similarité locale entre do-cuments, et enfin d’utiliser une représentation cartographique familière à l’utilisateur et né-cessitant donc peu d’apprentissage. A notre connaissance,aucun algorithme de classificationvisuelle utilisant les automates cellulaires (AC) pour générer de telles cartes n’a été défini à cejour.

Notre méthode consiste donc à utiliser un AC pour la classification et la visualisation dedocuments, en prenant une matrice de similarité comme donnée d’entrée. Cet AC est constituéd’une grille 2D dont chaque case va pouvoir être soit vide, soit contenir un document. Il utilise4 règles locales d’évolution stochastique des états des cellules qui visent à faire apparaîtredans des cellules voisines des états (documents) similaires les uns aux autres. Une fois la carteapprise, il est possible soit d’obtenir un partitionnementavec un algorithme à germes, soitd’explorer visuellement les résultats.

Les résultats obtenus par ce premier AC appliqué à la classification de données ont étécomparés aux résultats de la CAH (classification ascendantehiérarchique), des K-means (10-means) ainsi qu’à des méthodes biomimétiques. Ces résultats ont montré que l’AC, avec lesrègles mises en place, peut classer automatiquement les données de manière efficace.

Avec cette méthode nous avons pu générer en HTML des cartes annotées de pages webqu’il est possible d’explorer interactivement (sélection, zoom). En perspectives, nous comptonstester des méthodes de visualisation plus avancées que le HTML en définissant notamment deszooms sémantiques (modification en temps réel du niveau d’abstraction de la carte).


Classification visuelle de documents par automate cellulaire

Après avoir mené des tests et obtenu des résultats intéressants sur des bases connues, nousavons utilisé l’automate cellulaire pour générer une cartographie de site web. Un point à retenirest que l’automate cellulaire, comme beaucoup d’autres méthodes de classification superviséeou non supervisée, est dépendant de la qualité de la mesure desimilarité entre deux objets.Dans notre cas ces deux objets sont des pages web.

Dans cette capture d’écran, nous pouvons observer le résultat de la classification de pageswebs générée en page xHTML plus javascript. Le résultat semble cohérent (les couleurs cor-respondant aux classes définies par les experts).Un point important est que la page xHTML ainsi générée n’est que le moyen le plus simple destocker et présenter la classification ainsi obtenue. D’autres moyens plus élaborés et interactifspeuvent être envisagés à partir cette première étape.

Références

[A1] Von Neumann J., Theory of Self Reproducing Automata., University of Illinois Press,Urbana Champaign, Illinois, 1966

[A2] Azzag H., Picarougne F., Guinot C., Venturini G., Un survol des algorithmes biomimé-tiques pour la classification. Classification et Fouille de Données, pages 13-24, RNTI-C-1,Cépaduès. 2004

[A3] Chen, H. ; Schuffels, C. ; Orwig, R. : Internet categorization and search : a self-organizingapproach. In : Journal of visual communication and image representation, 7 (1996) 1, p.88-102


Utilisation de points d’intérêt pour la classificationinteractive de données

David Da Costa∗,∗∗, Gilles Venturini∗

∗Laboratoire d’InformatiqueEcole Polytechnique de l’Université de Tours

64, Avenue Jean Portalis, 37200 Tours, France.{david.dacosta, venturini}@univ-tours.fr,http://www.antsearch.univ-tours.fr/webrtic

∗∗AgicomInstitut d’Etudes

3, degrés Saint Laumer, 41000 Blois, [email protected]

http://www.agicom.fr/

L’objectif de notre travail est de pouvoir représenter visuellement une classification de don-nées de tous types, en se basant uniquement sur l’existence d’une fonction de similarité entreles données et ceci en un temps le plus court possible afin de traiter de grands ensembles. Nousproposons dans ce résumé une méthode à base de points d’intérêts (POIs) permettant de visua-liser des données supervisées ou non, et, dans ce dernier cas, de les classifier interactivement.

Le principe de notre méthode consiste, à l’instar de systèmes de recherche documentairetels que Sqwid (McCrickard et Kehoe, 1997) ou Radviz (Hoffman et al., 1999), à placer desdonnées appelées point d’intérêt (POIs) sur un cercle et à représenter les autres données enfonction de leur ressemblance à ces POIs. Lorsqu’on travaille avec des données supervisées,notre méthode place le premier individu de chaque classe comme point d’intérêt initial et po-sitionne les données restantes en fonction de leur similarité aux POIs. Dans le cas où l’on tra-vaille avec une classification non supervisée, notre méthode choisit aléatoirementn données,n représentant le nombre de classes désirées par l’utilisateur, et place les autres données de lamême manière que la méthode supervisée. Cependant, d’autres choix automatiques sont pro-posés à l’utilisateur et d’autres règles de décisions peuvent être choisies pour définir nos POIscomme prendre les données ayant la meilleure similarité avec le plus grand nombre d’autresdonnées.

Pour être réellement efficace, notre méthode doit être interactive et permettre d’affiner dy-namiquement l’affichage et de répondre aux requêtes graphiques de l’utilisateur, permettantainsi à ce dernier de constituer des classes en regroupant des données à l’aide de la souris.Nous pouvons ainsi visualiser des ensembles de plusieurs centaines de milliers de données enquelques dizaines de secondes seulement.

Application non supervisée

Nous avons évalué cette méthode sur un ensemble de bases composées de différentes don-nées artificielles (Monmarché, 2000) et classiques. Voici un exemple sur la base classique


Classification supervisée et non supervisée

"WINE" (178 données, 3 classes) issue du "Machine Learning Repository" (Blake et Merz,1998). Nous avons ainsi représenté sur la figure 1(a) les données "WINE" avec pour POIs desdonnées prises aléatoirement. En utilisant une dilatationde la similarité (fig. 1(b)), on retrouvebien les formes des classes usuelles. Il nous reste alors à sélectionner les données (fig. 1(c)) età les étiquetter par une classe pour aboutir à une classification (fig. 1(d)).

(a) (b)

(c) (d)

FIG. 1 – Exemple sur la base "WINE" d’une classification visuelle et interactive de données.

Références

Blake, C. et C. Merz (1998). UCI repository of machine learning databases.

Hoffman, P., G. Grinstein, et D. Pinkney (1999). Dimensional anchors : a graphic primitivefor multidimensional multivariate information visualizations. InNPIVM ’99 : Proceedingsof the 1999 workshop on new paradigms in information visualization and manipulationin conjunction with the eighth ACM internation conference on Information and knowledgemanagement, New York, NY, USA, pp. 9–16. ACM Press.

McCrickard, S. et C. Kehoe (1997). Visualizing search results using sqwid. InProceedings ofthe Sixth International World Wide Web Conference.

Monmarché, N. (2000).Algorithmes de fourmis artificielles : applications à la classificationet à l’optimisation. Thèse de doctorat, Laboratoire d’Informatique, Université de Tours.


Markov Random Fields for clustering genes

Matthieu VIGNES∗ and Florence FORBES∗

∗ Inria Rhône-Alpes, 655 av.de l’Europe, 38330 Montbonnot, [email protected], [email protected],http://mistis.inrialpes.fr/people/vignes/

1 IntroductionClustering of genes into groups sharing common characteristics is a useful exploratory

technique for a number of subsequent biological analysis. Most of the clustering algorithmsconsider genes as independent entities or include relevant information on gene interactions in asub-optimal way. We propose an hidden Markov random field model which has the advantageto account for individual data (e.g. expression) and pairwise data (e.g. interaction informationarising from biological networks) simultaneously. As a probabilistic model, this model hasmany interesting theoretical features. Also, preliminary experiments on simulated and yeastreal data show promising results and points out the gain in using such an approach.

2 Hidden Markov fields for biological networksThe individual, usually multi-dimensional (e.g. expression profiles), data observed for

each of the n genes to be clustered are denoted by x1, . . . , xn. We model the probabil-

ity of observing xi

as P (xi|Ψ) =

K∑

k=1

P (Zi

= k|β) f(xi|θ

k), where f(x

i|θ

k) denotes the

multivariate Gaussian distribution with parameters θk. Notation Z

idenotes the random vari-

able representing the class of gene i, in one of K classes. Notation β denotes additionalparameters defining the distribution of the Z

i’s and Ψ denotes the whole model parameters

i.e. Ψ = (θk, β, k = 1 . . .K). Accounting for dependent genes requires the definition of

neighborhood relationships between genes. We think of a set of genes as a graph with edgesemanating from each gene to other genes within its neighborhood. We illustrate in the nextparagraph how such a graph can be built from biological network data. The dependenciesbetween genes are then modelled by further assuming that the distribution of Z1, . . . , Zn

is adiscrete Markov random field on this specific graph. Denoting z = (z1, . . . , zn

), we defineP (z|β) = W (β)−1 exp(−H(z, β)), where W (β) is a normalizing constant and H is a func-tion restricted to pair-wise interactions, i.e. with terms involving individual z

i’s or pairs of

neighbors {zi, z

j} at most.

Our aim is to classify each gene in one of the K classes. To do so we consider a MaximumPosterior Marginal (MPM) principle consisting in assigning gene i to class k that maximizesP (Z

i= k|x,Ψ). Such maximizations depend on Ψ which is usually unknown, or partly


Markov fields for gene clustering

unknown when prior knowledge is incorporated, and has to be estimated. In this work, we usesome of the procedures presented in Celeux et al. (2003). They are based on the EM algorithmand the mean field principle.

From biological networks to interaction graphs. Many kinds of biological networks arefreely available but the quality and the access to that information is far from being uniform.As an example, biological networks are not all related to the same objects. They may containlinks between genes, gene products, proteins complexes or families, etc. We choose to focus ongene expression data and metabolic networks like those given in the Reaction (part of Ligand)KEGG database (http://www.genome.ad.jp/kegg/reaction/). We build a geneinteraction graph made by linking pairs of genes if and only if they are associated (via enzymes)to the same reaction or to two different reactions sharing a common compound. Adding thenexpression data at the nodes of the graph, we present experiments on yeast data.

3 Results on yeast data and future workAlthough we made successful preliminary experiments on synthetic data (simulated ex-

pression profiles and available ground-truth for the classes), we focus as an illustration ondata related to Saccharomyces cerevisiae (backer’s yeast). The expression data we use are de-scribed by Chu et al. (1998). As regards network data, we use the KEGG Reaction databaseas described above. These experiments point out further interesting features of our approach.It leads to biologically more plausible and more fully identified clusters. When compared toclustering methods based on gene expression only, it has the advantage to produce clustersassociated to metabolic pathways with possible coordinated change in gene expression. Thusit overcomes a well-known limitation of such methods that only group genes with similar ex-pression profiles but miss out many others with dissimilar expression profiles. When comparedwith methods incorporating network data, it has the advantage to consist in a statistically wellfounded approach which does not require to choose a distance or a kernel function and allowsfurther statistical analysis regarding additional issues such as model selection. It also providesmembership probabilities instead of hard (usually more biased) classifications.

Future work would be to investigate this general methodology in other contexts, usinggenes or proteins as central concepts through a variety of information sources such as se-quences, structures, expression patterns, position in networks, etc. Before that, more specificanalysis would be useful as regards the generalization to missing data that often occur in bi-ological studies. Our EM-like framework allows such a generalization. Also, in a variety ofapplications, overlapping clustering, wherein some items are allowed to be members of two ormore discovered clusters, is more appropriate. Methods have been proposed that would worthmore investigation in the context of genetic data analysis.

ReferencesCeleux, G., F. Forbes, et N. Peyrard (2003). EM procedures using mean-field like approximations for

Markov-model based image segmentation. Pattern Recognition 36, 131–144.

Chu, S., J. L. DeRisi, M. B. Eisen, J. Mulholland, D. Botstein, P. Brown, et I. Herskowitz (1998). TheTranscriptional Program of Sporulation in Budding Yeast. Science 282, 699–705.


Évaluation en cascade d’algorithmes de clustering

Laurent Candillier∗,∗∗, Isabelle Tellier∗, Fabien Torre∗, Olivier Bousquet∗∗

∗GRAppA - Université Charles de Gaulle - Lille 3∗∗Pertinence - 32 rue des Jeûneurs - 75002 Paris

L’évaluation des résultats d’algorithmes de clustering, ainsi que la comparaison de telsalgorithmes, reste encore aujourd’hui une problématique ouverte importante. La difficulté vientprincipalement du fait que de telles évaluations sont subjectives par nature car il existe souventdifférentes manières pertinentes de regrouper un même ensemble de données.

Les techniques existantes dans ce cadre souffrent de quelques limitations. Utiliser des don-nées artificielles ou un expert d’un domaine particulier ne permet pas de généraliser les résul-tats à différents types de données réelles. Comparer les clusters obtenus aux classes prédéfiniesd’un jeu de données étiqueté est rarement approprié car d’autres regroupements peuvent êtreplus pertinents. Utiliser des critères numériques tels l’inertie intra-cluster et/ou la séparationinter-clusters est également subjectif par nature car basé sur des notions prédéfinies de la perti-nence d’un clustering (or parfois, des clusters qui se chevauchent sont plus pertinents que desclusters séparés).

En fait, ce que l’on souhaite évaluer, c’est la capacité d’une méthode de clustering à fournirde la connaissance nouvelle et utile dans un certain cadre. L’idée principale de notre approcheconsiste à considérer le clustering comme un prétraitement à une tâche que l’on sait évaluer :l’apprentissage supervisé par exemple. Ainsi, si les résultats d’un algorithme supervisé sontaméliorés lorsqu’il est aidé par de l’information provenant d’un algorithme de clustering, alorsnous postulons que cela signifie que le clustering a fourni une information nouvelle et utile.

Adaptant la technique de cascade generalization [Gama et Brazdil (2000)] au cas où unapprenant est non supervisé, la méthode d’évaluation en cascade d’algorithmes de clusteringque nous proposons consiste donc à :

1. effectuer un apprentissage supervisé sur un jeu de données étiqueté,

2. effectuer un apprentissage supervisé sur le même jeu de données enrichi par les résultatsde l’algorithme de clustering évalué,

3. et comparer les erreurs des deux classifieurs appris.

Cette méthode nous permet alors d’évaluer objectivement l’intérêt de l’information capturéepar le clustering. De plus, la diminution du taux d’erreur de l’algorithme supervisé lorsqu’ilest aidé par l’information issue du clustering nous permet de quantifier cet intérêt.

Nous avons mené plusieurs expérimentations avec cette méthode, en considérant :

1. plusieurs jeux de données issus de l’UCI Machine Learning Repository [Blake et Merz(1998)],

2. différentes façons d’enrichir les jeux de données à partir des résultats d’algorithmes declustering, parmi lesquelles celle proposée dans [Apte et al. (2002)],


Cascade evaluation

3. et différents algorithmes supervisés : C4.5 [Quinlan (1993)] basé sur la constructiond’arbres de décision, C5 boosté [Quinlan (2004)] basé sur la combinaison de plusieursarbres de décision, et DLG [Webb et Agar (1992)] basé sur l’utilisation de moindresgénéralisés.

Nous avons ainsi évalué plusieurs algorithmes de clustering utilisant des modèles de complexi-tés différentes : depuis K-means jusqu’à certains modèles probabilistes plus complexes.

Sur chaque jeu de données, pour chaque méthode d’enrichissement, chaque algorithmesupervisé et chaque algorithme de clustering utilisés, nous faisons cinq validations croiséesavec découpage du jeu de données en deux, comme proposé dans [Dietterich (1998)]. Pourchaque validation croisée, nous calculons les taux d’erreur pondérés de l’algorithme superviséavec ou sans information ajoutée par l’algorithme de clustering évalué. Puis nous utilisonsquatre mesures pour comparer les résultats :

1. le nombre de victoires de chaque méthode sur l’ensemble des jeux de données considé-rés,

2. le nombre de victoires significatives, en utilisant le 5×2cv F-test [Alpaydin (1999)] pourvérifier si les résultats sont significativement différents,

3. le wilcoxon signed rank test, qui indique si une méthode est significativement meilleurequ’une autre sur un ensemble de problèmes indépendants,

4. et l’erreur pondérée moyenne.

Nous avons ainsi mis en avant que quels que soient la méthode d’enrichissement et l’algo-rithme supervisé utilisés, l’ordre dans lequel les méthodes de clustering sont rangées par notreméthode d’évaluation reste toujours le même. Plus particulièrement, celle-ci met en avant lefait que plus le modèle utilisé par l’algorithme de clustering est complexe, plus l’informationqu’il capture est pertinente, en cela qu’il aide l’algorithme supervisé à améliorer ses perfor-mances. Ce résultat, loin de surprendre, montre le comportement cohérent de notre méthode.

Références

Alpaydin, E. (1999). Combined 5x2cv F-test for comparing supervised classification learningalgorithms. Neural Computation 11(8), 1885–1892.

Apte, C. V., R. Natarajan, E. P. D. Pednault, et F. A. Tipu (2002). A probabilistic estimatonframework for predictive model analytics. IBM Systems Journal 41(3).

Blake, C. et C. Merz (1998). UCI repository of machine learning databases[http ://www.ics.uci.edu/∼mlearn/MLRepository.html].

Dietterich, T. G. (1998). Approximate statistical test for comparing supervised classificationlearning algorithms. Neural Computation 10(7), 1895–1923.

Gama, J. et P. Brazdil (2000). Cascade generalization. Machine Learning 41(3), 315–343.

Quinlan, J. R. (1993). C4.5 : Programs for Machine Learning. KAUFM.

Quinlan, R. (2004). Data mining tools see5 and c5.0.

Webb, G. I. et J. W. M. Agar (1992). Inducing diagnostic rules for glomerular disease with theDLG machine learning algorithm. Artificial Intelligence in Medicine 4, 419–430.


Sur l’apprentissage de la structure de réseaux bayésiens àpartir de bases d’exemples incomplètes

Olivier François et Philippe Leray

Laboratoire LITIS (Informatique, Traitement de l’Information et Systèmes)INSA et Université de Rouen, BP08, 76801 Saint-Etienne-Du-Rouvray

[email protected], [email protected]://asi.insa-rouen.fr/~ofrancois/, http://asi.insa-rouen.fr/~pleray/

Résumé.Les réseaux bayésiens sont des modèles probabilistes de plus en plusutilisés pour la modélisation de systèmes complexes, l’aide à la décision et laclassification. De nombreuses heuristiques ont alors été proposées pour determi-ner la structure d’un réseau bayésien à partir de bases d’exemples complètementobservées. Néanmoins, les techniques existantes pour trouver cette structure àpartir de bases incomplètes restent rares et sont de complexité élevée. En nousinspirant de l’heuristiqueStructural-EM(SEM) introduite parFriedman(1998),nous proposons une méthoded’identification de réseau bayésien à partir debases d’exemples incomplètesrapide et optimale pour un critère de score dansl’espace des structures arborescentes. Nous introduisons également une méthodesimilaire à SEM dans l’espace plus complexe deséquivalents de Markov.

Résumé long

SelonRubin(1976), il est possible de différencier trois types de données manquantes selonle mécanisme qui les a générées. Pour les donnéesmanquantes au hasard(MAR) la probabi-lité qu’une variable ne soit pas mesurée ne dépend que de l’état de certaines autres variablesobservées. Lorsque cette probabilité ne dépend plus des variables observées, les données man-quantes sont ditesMCAR (missing completely at random). Dans ces deux cas, le mécanismed’absence des données est ditignorablecar il est possible d’inférer les données manquantesà l’aide des données observées. Par contre lorsque la probabilité qu’une variable soit man-quante dépend à la fois de l’état de certaines autres variables observées mais également dephénomènes extérieurs, les données sont ditesnon ignorables(NMAR).

À structure fixée, effectuer l’apprentissage des paramètres d’un réseau bayésien est uneproblématique bien résolue en présence de donnéesMCAR ou MAR en utilisant une techniquede typeEM (Heckerman(1998)). Friedman(1998) a été l’un des premiers à proposer uneméthode déterministe efficace pour rechercher une structure à partir de données incomplètes ense basant sur les principes de l’algorithmeEM. La méthodeSEM est itérative, de type recherchegloutonne, et propose de choisir la nouvelle solution parmi un ensemble de voisins du graphecourant.

Dans de précédents travaux (François et Leray(2004)), nous avons montré que, dans le casde données complètes, la méthodeMWST (maximum weight spanning tree) de recherche de


http://asi.insa-rouen.fr/~ofrancois/

http://asi.insa-rouen.fr/~pleray/

Apprentissage de RB à partir de données incomplètes

l’ arbre de recouvrement maximaladaptée aux modèles graphiques probabilistes (Heckerman(1998); Chow et Liu(1968)) permet d’obtenir ’très’ rapidement une structure simple représen-tant au mieux les données et pouvant également servir d’initialisation pour une méthode derecherche gloutonne. Nous proposons ici l’algorithmeitératif MWST-EM, adaptant cette mé-thode aux bases de données incomplètes en recherchant le meilleur graphe dans l’ensemble desarbres plutôt que le meilleur dans un voisinage. L’algorithmeMWST-EM, tout comme l’algo-rithme SEM, est une méthode itérative. Nous proposons ensuite d’initialiserSEM avec l’arbrerendu parMWST-EM pour étudier les apports éventuels d’une telle initialisation. Nous com-parerons empiriquement ces différentes approches pour des bases d’exemples jouets ainsi quesur des bases d’exemples incomplètes disponibles en ligne pour une problématique de classi-fication. Nous verrons ensuite comment utiliser cette méthodologie pour adapter l’algorithmeGES deChickering(2002) aux bases d’exemples incomplètes. Cet algorithme est égalementune méthode gloutonne d’identification de structure, mais qui travaille dans l’espace des repré-sentants des classes d’équivalence de Markov.

Références

Chickering, D. M. (2002). Optimal structure identification with greedy search.Journal ofMachine Learning Research 3, 507–554.

Chow, C. et C. Liu (1968). Approximating discrete probability distributions with dependencetrees.IEEE Transactions on Information Theory 14(3), 462–467.

François, O. et P. Leray (2004). Evaluation d’algorithmes d’apprentissage de structure dansles réseaux bayésiens. In14ieme Congrès francophone de Reconnaissance des formes etd’Intelligence artificielle, pp. 1453–1460.

Friedman, N. (1998). The Bayesian structural EM algorithm. In G. F. Cooper et S. Moral(Eds.),Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI-98), San Francisco, pp. 129–138. Morgan Kaufmann.

Heckerman, D. (1998). A tutorial on learning with bayesian network. In M. I. Jordan (Ed.),Learning in Graphical Models. Kluwer Academic Publishers.

Rubin, D. (1976). Inference and missing data.Biometrika 63, 581–592.

Summary

Bayesian Networks are probabilistic models that are famous in complex system modelisa-tion, decision support or classification task. Many heuristics have been proposed to learn thosemodels from complete datasets, but only few ones from incomplete datasets exist. Using theStructural-EM heuristics (SEM) introduced byFriedman(1998), we proposed a fast technic tolearn Bayesian Networks from incomplete datasets which is optimal in the tree DAGs space.We introduce the use of the same methodology to adapt the optimal technic GES introducedby Chickering(2002) to incomplete datasets.


Construction et classification d’objets d’image detélédétection par une approche itérative guidée par des

connaissances du domaine

Sébastien Derivaux

LSIIT, ULP/CNRS UMR 7005Pôle API, Bd Sébastien Brant - 67412 Illkirch, France

[email protected]

1 Introduction

L’évolution des technologies d’observation de la terre permettent d’obtenir des images derésolutions de l’ordre du mètre sur plusieurs bandes spectrales (satellites Ikonos ou Quick-bird). L’analyse de ces images consiste à passer de la représentation à base de pixel à unereprésentation sémantique de type couverture (route, bâti, . . .) ou usage (aéroport, bâtimentcommercial, . . .) des sols. Une méthode d’analyse automatique permettrait la mise à jour dessystèmes d’informations géographiques sans intervention manuelle.

La voie la plus prometteuse pour résoudre cette problématique se décompose en deuxétapes :

1. SegmentationUne segmentation est un processus qui consiste à regrouper des pixelshomogènes et spatialement connexes. La difficultée se situe au niveau du critère d’ho-mogénéité définissant l’agrégation de pixels. Idéalement, il doit exister une relation bi-jective entre les régions ainsi crées et les objets sémantiques recherchés.

2. ClassificationUne fois les régions obtenues, il devient possible d’extraire des indices deforme, des mesures géométriques et des indices de texture. La classification des régionspeut se faire par un algorithme de classification supervisé ou non.

Nous nous proposons d’étudier les améliorations que peuvent apporter les connaissances(ontologie, exemples, résultats antérieurs, . . .) aux différents niveaux du processus. Nous pré-sentons d’abord les pistes qui seront explorées durant la thèse pour l’étape de segmentationpuis celles pour l’étape de classification et nous finissons par proposer une piste pour modifierla segmentation selon les résultats de la classification.

2 Segmentation

Pour l’instant la plupart des algorithmes de segmentation fonctionnent de façon non super-visée (Carleer et al., 2005). Plusieurs pistes pour l’inclusion de diverses formes de connais-sances sont possible afin d’améliorer la segmentation.


Construction et classification d’objets d’image de télédection

Tout d’abord, l’utilisation d’exemples peut servir à la définition d’une nouvelle mesured’homogénéité. Nous passons d’une distance spectrale à une distance sémantique. Dans cettedistance sémantique, deux pixels spectralements éloignées d’une même classe ont une distancefaible. Inversement, deux pixels spectralement proches mais sémantiquement éloignés (parexemple de l’eau et de l’ombre) auront une grande distance.

Une deuxième approche utilise une ontologie1 afin d’aider la segmentation dans la construc-tion de régions. Si une région en cours de construction peut être classée avec une confianceforte, il est possible d’utiliser les critères de forme définis pour cette classe dans l’ontologiepour la suite de la construction de l’objet.

3 Classification

À partir d’une segmentation, l’étape de classification consiste à affecter une classe à chaquerégion. La littérature est abondante sur le sujet et propose diverses méthodes de classification.Si certaines sont générales, d’autres sont spécifiques, par exemple à la détection de route. Enfinles classifieurs non supervisés fournissent un ensemble de clusters sans sémantique.

La fusion de classifieurs est un champ d’intérêt croissant en fouille de données et montrequ’il est intéressant de combiner des approches complémentaires (Giacinto et al., 2000). Cetravail de thèse se propose d’étudier la combinaison de classifieurs dont les sorties ne sont pascomparables.

Comme pour la segmentation, l’utilisation des connaissances du domaine peut se faire sousla forme d’une ontologie construite par les experts du domaine. L’opérationnalisation de celle-ci permet la classification des régions. L’ontologie peut aussi servir à vérifier la cohérenced’une classification obtenue par une autre méthode.

4 Feedback de la classification sur la segmentation

À la section précédente nous avons fait l’hypothèse que la segmentation est correcte, c’està dire qu’à chaque région formée corresponde un et un seul objet sémantique. Néanmoins,il est impossible d’obtenir une segmentation idéale a priori. L’étape de classification devraitpermettre de détecter les régions possiblement mal segmentées. Cette information peut êtrerenvoyée au module de segmentation pour fournir une segmentation différente de la zone,celle-ci pouvant permettre une classification avec un indice de confiance plus élevé.

Références

Carleer, A. P., O. Debeir, et E. Wolff (2005). Assessement of very high spatial resolutionsatellite image segmentations.Photogrammetric Engineering and Remote Sensing 71(11),1285–1294.

Giacinto, G., F. Roli, et L. Bruzzone (2000). Combination of neural and statistical algorithmsfor supervised classification of remote-sensing image.Pattern Recognition Letters 21(5),385–397.

1Hiérarchie de concepts modélisant les connaissances de l’expert du domaine


��

��

��

��

�

��

� �� !��

""#��$��

%"&'(��)*�*+�,�

-��.� � /0 � �1��

�� .�22��3��4�5��

6��7��71!1�"&"6��!��1�

-��/0��1��12��

��

� �� 8��8��88��.��8� 4�� 2��

��9�� :�9�� :�� ;�� <� 8��

�: 2�5�� 1�)��8� 4�� 2�� 5�� 9��

5� �1� )=�� <�8�� 5��;��2��

��<�8�� ;��=�9�� ;��9��

� �� 1� )��5��8� �� 2 �� = ��2�� 9��1� ��

� �� <��=� �� 2� ��;��9�

�� 2��<�8�� 9�� 1��

�

��

�� 2�5��;��.� �� 22��

<��:��: 2�5�� 8�� 88��.��8�� 5 ��.��

;�� >�� 8��8��8� � ��9��1�

�� 8��8��88��.��:�9�� ;��9��<�

8�� : 2�5��!?�� 5�1�� (��98��:�88��.��

8��8�� :�98 � 2�� : �� ;� �� 1�

�

��

?�8��>�� 8��@�

4 ��8��2 >��8.��8� 4�� 2��9�� 5�� 9�

��5� �1�� <��<��.�;��8 9��:�� 5 �� 2��

�� 2�� 7��A",,B�",,#CD�

4 �� :��<�8�� 5��;��:�9�� ;�� D�

4 �� 3�D�

�: � �� <�� 8��3��8��

��5�� 9��5� �1�


*9�� ;��9��

�$��

$��.� � �8�� 5�� 2�5��9��1��:�88�� 5��

��8�� 8�� 2�5�� ""(� �9�28��D� �� : 2�5��

%(�%(�� 8�� E��F�� 2��A��G1�"C1�

� � � ��

��G1�"��

��

�� 8��:�� 5��1��

�� 4��2�� 8� � � ��5�� @�

� $�2�� :�9�28�� 8��

��

!� � � �� 5��

�� AHC�

��5�� "#� ''1(&�

��5�� "#� II16'�

��7�"�� !��

?��8��J� �� 2�� 4��;��2 �.��5��8��2 ��

�:�� 2� �� 8�� 88�� 9� � �� 5��

�� 3�1�

!� ��

�:�88��.�� 5 ��8�� 8��2�� 2�5��

��88� 2�� 9�� 5� �� 2 �� 2�� <�

�.�;��8 9��:�� 2�5��A,��2��C��;� ��8� ��5� ��8��2 2� ��

��>�� :�2 � �� 1��

�

� � ��

7��1�A",,BC1�*9�� )�� ;��9��8��)��5��*9��2��

G� �� 2�� !� ��8��5 ;�� 2�5�� .>�� )��

7��"��

7��1� A",,#C1��9�� 9�� K �.��.��.��8��.�� 5 �� 9��2��

�� 5��88��.��.�� )��7��1�

�� L��1�1� A",B,C1�M�� 9� ��88��.��9��N��8�� 5��.��

�***�� 3��2��'B��I1��

3�8 L��31�A",,#C1�� 5��.��O ��1��


Documents

2èmes Rencontres Inter-Associations (RIAs2006) AFIA …eric.univ-lyon2.fr/~rias2006/presentations/Actes_finaux_v2.pdfsur des concepts communs. ... pour thème « la représentation