$\beta_1 = 0.9$, $\beta_2 = 0.999$ et $\epsilon = 10^{-8}$. Le coefficient d'ap-
prentissage est commun à toutes les couches et fixé à $10^{-3}$
au début de l'entraînement, puis multiplié par 0.75 toutes
les 10 "epoch". Afin de limiter le problème d'explosion du
gradient, nous redimensionnons sa norme avec une stra-
tégie de gradient clipping [26]. Nous suivons [16] et ap-
pliquons un gradient clipping de min(3.0, profondeur),
où profondeur représente le nombre de GRU impliquées
dans la couche entraînée.

**Initialisation des paramètres.** Afin de faciliter la pro-
pagation du gradient lors de l'entraînement, nous utilisons
des matrices orthogonales générées aléatoirement comme
états initiaux pour les matrices de paramètres des GRU,
comme préconisé par Saxe et al. [27]. Les autres ma-
trices de paramètres sont initialisées avec des valeurs is-
sues d'une loi normal N(0, $\sqrt{2/n_{in}}$), où $n_{in}$ représente
le nombre de neurones entrant dans la couche concernée,
comme proposé par He et al [28]. Les vecteurs de biais
sont initialisés en tant que vecteurs nuls.

**Dimensions vectorielles utilisées.** La représentation vectorielle utilisée pour les mots en entrée du système et les représentations vectorielles des étiquettes EMS et chunking sont de dimension 50. Les états cachés des GRU sont de dimension 100 pour toutes les couches du modèle.

**Régularisation.** En suivant [16], nous fixons les coefficients $\lambda$ à $10^{-6}$ pour les matrices de paramètres des GRU et $10^{-5}$ pour les autres matrices de paramètres. Le coefficient de régularisation successif $\delta$ est fixé à $10^{-2}$ pour toutes les couches. Nous utilisons aussi Dropout [29] sur toutes les couches, avec taux de neurones affectés de 0.2.

**Données d'entraînement pour les couches EMS et chunking.** Nous utilisons le corpus issu de la tâche partagée CoNLL-2000 [30] avec les étiquettes associées pour entraîner les couches EMS et chunking.

**Données d'entraînement pour les couches DelCA et DetCA.** Nous utilisons le corpus Argument Annotated Essays (version 2) partagé par Stab et Gurevych [2] en suivant le découpage entraînement/test fourni pour l'entraînement des couches DelCA et DetCA.

**Arrêt de l'entraînement.** Dans un cas d'entraînement uni-tâche, une pratique généralement adoptée est d'arrêter l'entraînement du modèle peu avant le surapprentissage. Dans le cas de notre modèle, il n'est pas évident de déterminer le meilleur moment pour arrêter l'entraînement, puisque le modèle peut surapprendre sur une tâche particulière, mais pas sur les autres. Ainsi, nous arrêtons l'entraînement du modèle lorsqu'il surapprend sur les couches DelCA et DetCA, et reportons les meilleurs résultats obtenus pour chaque tâche avant le surapprentissage de celle-ci.

**DetCa simple.** Nous nommons DetCa simple la tâche DetCa avec la modification suivante : tous les segments des dissertations correspondant à des composants argumentatifs sont traités comme ne comportant qu'un unique mot spécial <VIDE>. L'hypothèse est que cette transformation

<table><caption>TABLE 1 – Macros f1-scores obtenus sur les différentes tâches.</caption>
   <thead>
    <tr>
     <td>
      Tâche
     </td>
     <td>
      w/o EMS &amp; chunking
     </td>
     <td>
      w/ EMS &amp; chunking
     </td>
    </tr>
   </thead>
   <tbody>
    <tr>
     <td>
      DelCA
     </td>
     <td>
      0.5934
     </td>
     <td>
      0.8688
     </td>
    </tr>
    <tr>
     <td>
      DetCA
     </td>
     <td>
      0.7464
     </td>
     <td>
      0.7105
     </td>
    </tr>
    <tr>
     <td>
      DetCA simple
     </td>
     <td>
      0.7529
     </td>
     <td>
      0.7911
     </td>
    </tr>
   </tbody>
  </table>

<table><caption>TABLE 2 – F1-scores obtenus sur les tâches DelCA et DetCA par Stab et Gurevych [2] et des agents humains.</caption>
   <thead>
    <tr>
     <td>
      Tâche
     </td>
     <td>
      F1-score obtenus en [2]
     </td>
     <td>
      F1-score humain
     </td>
    </tr>
   </thead>
   <tbody>
    <tr>
     <td>
      DelCA
     </td>
     <td>
      0.867
     </td>
     <td>
      0.886
     </td>
    </tr>
    <tr>
     <td>
      DetCA
     </td>
     <td>
      0.826
     </td>
     <td>
      0.868
     </td>
    </tr>
   </tbody>
  </table>

forcera le modèle à se concentrer sur le contexte entourant
les composants argumentatifs, et l'empêchera donc de se
surencaîner en considérant les mots à l'intérieur des com-
posants.

5.2 Résultats obtenus

Les résultats obtenus sur les données de test pour les tâches DelCA, DetCA et DetCA simple sont présentés en Table 1. La colonne "w/o EMS & chunking" fait référence à la version du modèle pour laquelle l'optimisation des couches EMS et chunking a été omise. La colonne "w/ EMS & chunking" fait référence à la version du modèle pour laquelle l'optimisation des couches EMS et chunking a été réalisée. Nous prenons comme référence les performances atteintes par des agents humains<fnref n="2" /> ainsi que les résultats présentés par Stab et Gurevych [2], illustrés en Table 2.

**Evaluation générale des performances.** Nous obtenons un macro f1-score de 0.8688 sur DelCA avec la version "w/ EMS & chunking". Ces résultats sont obtenus sans définition de caractéristiques manuelles et sont comparables à ceux enregistrés en [2]; ils atteignent 98,06% de la performance humaine. Concernant la classification des composants argumentatifs, nous obtenons un macro f1-score de 0.7911 avec DetCA simple pour la version "w/ EMS & chunking", ce qui représente 95,8% des performances obtenues en [2] et 91,1% de la performance humaine.

**Pertinence de DetCA simple.** Selon nous, les mots for-
mant un composant argumentatif ne sont pas réellement
caractéristiques de sa classe, et en se concentrant dessus,
le modèle peut être amené à modéliser du bruit l'empê-
chant de généraliser correctement. En revanche, le contexte
dans lequel apparaissent les composants semble très im-
portant. Par exemple, des mots tels que "we can receive the
same conclusion that" semblent indiquer que l'auteur va
annoncer une conclusion intermédiaire ou majeure. Cela
peut expliquer la différence de performances entre DetCA
et DetCA simple, notamment pour la version "w/ EMS

<footnote n="2">2. La performance humaine correspond à la moyenne des résultats obtenus par des annotateurs humains, tels que présentés en [2]</footnote>
& chunking", avec respectivement un f1-score de 0.7105 contre 0.7911, soit une amélioration de 11,3%.

**Pertinence du modèle multi-tâches.** Les macro f1-scores sur les tâches DelCA et DetCA simple sont respectivement de 0.5934 et 0.7529 pour la version "w/ EMS & chunking" et de 0.8688 et 0.7911, soit des améliorations de 46,4% et 5,1%. Ces résultats permettent donc de valider l'intérêt d'entraîner un modèle multi-tâches et incitent à l'ajout de tâches auxiliaires supplémentaires.

# 6 Travaux à venir et perspectives

Les résultats obtenus sont encourageants et pourraient sûrement être améliorés, notamment avec une recherche plus d'approfondie d'hyper-paramètres optimaux. La différence de performances entre les versions du modèle "w/ EMS & chunking" et "w/o EMS & chunking" portent à croire qu'implémenter davantage de tâches auxiliaires pourrait être bénéfique. Une piste serait d'introduire une couche modélisant un arbre de dépendances syntaxiques en complément de la couche chunking, comme effectué en [16].

En vue d'implémenter un système complet d'argument mining tel que présenté par Stab et Gurevych [2], nous prévoyons d'implémenter des couches permettant la génération automatique de graphes d'arguments. A cette fin il est nécessaire de déterminer s'il existe un arc entre chaque paire ordonnée de composants argumentatifs, ainsi que d'inférer l'étiquette portée par ledit arc.

# 7 Conclusion

Cet article a présenté une méthode d'extraction et d'analyse automatique d'arguments à partir de textes bruts. L'utilisation de techniques d'apprentissage profond nous permet de nous affranchir de la définition de caractéristiques manuellement définies. Par ailleurs, l'amélioration des performances de notre système par l'exploitation de paramètres optimisés sur des tâches auxiliaires met en avant l'intérêt de l'utilisation d'un modèle multi-tâches. Nous avons comme perspective la complétion de la chaîne de traitement existante en vue d'obtenir un système capable de synthétiser une dissertation par modélisation automatique d'un graphe d'arguments.

# Références

[1] M. Lippi et P. Torroni, Argumentation mining : State of the art and emerging trends, *ACM Transactions on Internet Technology (TOIT)*, 16(2), p.10, 2016.

[2] C. Stab et I. Gurevych, Parsing argumentation structures in persuasive essays, *Computational Linguistics*, 43(3), pp.619-659, 2017.

[3] N. Madnani, M. Heilman, J. Tetreault et M. Chodorow, Identifying high-level organizational elements in argumentative discourse, *Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies*, pp. 20-28, Association for Computational Linguistics, 2012.

[4] R. Levy, Y. Bilu, D. Hershcovich, E. Aharoni et N. Slonim, Context dependent claim detection, *Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers*, pp. 1489-1500, 2014.

[5] Y. Ajjour, W.F. Chen, J. Kiesel, H. Wachsmuth et B. Stein, Unit Segmentation of Argumentative Texts, *Proceedings of the 4th Workshop on Argument Mining*, pp. 118-128, 2017.

[6] T. Goudas, C. Louizos, G. Petasis et V. Karkaletsis, Argument extraction from news, blogs, and social media, *Hellenic Conference on Artificial Intelligence*, pp. 287-299, Springer, Cham, 2014.

[7] C. Sardianos, I.M. Katakis, G. Petasis et V. Karkaletsis, Argument extraction from news, *Proceedings of the 2nd Workshop on Argumentation Mining*, pp. 56-66, 2015.

[8] S. Eger, J. Daxenberger et I. Gurevych, Neural End-to-End Learning for Computational Argumentation Mining, *arXiv preprint arXiv:1704.06104*, 2017.

[9] J. Eckle-Kohler, R. Kluge et I. Gurevych, On the role of discourse markers for discriminating claims and premises in argumentative discourse, *Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing*, pp. 2236-2242, 2015.

[10] J. Park et C. Cardie, Identifying appropriate support for propositions in online user comments, *Proceedings of the 1st Workshop on Argumentation Mining*, pp. 29-38, 2014.

[11] I. Persing et V. Ng, End-to-End Argumentation Mining in Student Essays, *Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies*, Association for Computational Linguistics, pages 1384–1394, 2016.

[12] P. Potash, A. Romanov et A. Rumshisky, Here's My Point : Joint Pointer Architecture for Argument Mining, *Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing*, pp. 1364-1373, 2017.

[13] S. Ruder, An overview of multi-task learning in deep neural networks, CoRR, abs/1706.05098, 2017.

[14] A. Søgaard et Y. Goldberg, Deep multi-task learning with low level tasks supervised at lower layers, *Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)*, Vol. 2, pp.231-235, 2016.

[15] Z. Yang, R. Salakhutdinov et W. Cohen, Multi-task cross-lingual sequence tagging from scratch, *arXiv preprint arXiv:1603.06270*, 2016.
[16] K. Hashimoto, C. Xiong, Y. Tsuruoka et R. Socher, A joint many-task model: Growing a neural network for multiple nlp tasks, *Empirical Methods in Natural Language Processing (EMNLP)*, 2017.

[17] L. Mou, Z. Meng, R. Yan, G. Li, Y. Xu, L. Zhang et Z. Jin, How transferable are neural networks in nlp applications?, *Empirical Methods in Natural Language Processing (EMNLP)*, pp. 479–489, 2016.

[18] H.M Alonso et B. Plank, When is multitask learning effective? Semantic sequence prediction under varying data conditions, *15th Conference of the European Chapter of the Association for Computational Linguistics*, 2017.

[19] J. Bingel et A. Søgaard, Identifying beneficial task relations for multi-task learning in deep neural networks, *arXiv preprint arXiv:1702.08303*, 2017.

[20] J. Pennington, R. Socher et C. Manning, Glove: Global vectors for word representation. *Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)*, pp. 1532-1543, 2014.

[21] K. Cho, B. Van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk et Y. Bengio, Learning phrase representations using RNN encoder-decoder for statistical machine translation, *arXiv preprint arXiv:1406.1078*, 2014.

[22] V. Nair et G.E. Hinton, Rectified linear units improve restricted boltzmann machines, *Proceedings of the 27th international conference on machine learning (ICML-10)*, pp. 807-814, 2010.

[23] L.A. Ramshaw et M.P. Marcus, Text chunking using transformation-based learning, *Natural language processing using very large corpora*, pp. 157-176, Springer, Dordrecht, 1999.

[24] D. Bahdanau, K. Cho et Y. Bengio, Neural machine translation by jointly learning to align and translate, *ICLR*, 2015.

[25] D.P. Kingma et J. Ba, Adam: A method for stochastic optimization, *ICLR*, 2015.

[26] R. Pascanu, T. Mikolov et Y. Bengio, On the difficulty of training recurrent neural networks, *Proceedings of The 30th International Conference on Machine Learning*, pp. 1310–1318, 2013.

[27] A.M. Saxe, J.L. McClelland, S. Ganguli, Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, *Proceedings of the International Conference on Learning Representations (ICLR)*, 2014.

[28] K. He, X. Zhang, S. Ren et J. Sun, Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification, *ICCV*, 2015.

[29] N. Srivastava, G.E. Hinton, A. Krizhevsky, I. Sutskever et R. Salakhutdinov, Dropout: a simple way to prevent neural networks from overfitting, *Journal of machine learning research*, 15(1):1929–1958, 2014.

[30] E.F.T.K. Sang, S. Buchholz, Introduction to the CoNLL-2000 shared task: chunking, *Proceedings of the 2nd Workshop on Learning Language in Logic and the 4th Conference on Computational Natural Language Learning*, Lisbon, Portugal, vol. 7, 2000, pp. 127–132, 2000.
#AIDS Analyse Information Dangers Sexualité : caractériser les discours à propos du VIH dans les forums de santé

Yves Mercadier<fnref n="1" />

Erick Cuenca<fnref n="1" />

Jérôme Azé<fnref n="1" />

Céline Paganelli⁴

Sandra Bringay<fnref n="1" />,²

Pascal Poncelet<fnref n="1" />

Viviane Clavier³

Arnaud Sallaberry<fnref n="1" />,²

¹ LIRMM, Université de Montpellier, CNRS, Montpellier, France, prenom.nom@lirmm.fr

² AMIS, Université Paul Valéry, Montpellier, France

³ GRESEC EA 608 – Université Grenoble Alpes, France

⁴ LERASS EA 827, Université Paul Valéry, F34000, Montpellier, France

## Résumé

**Contexte** : Les forums de discussion consacrés au VIH remplissent trois fonctions. Tout d'abord, ils sont utilisés par les internautes comme sources d'information pour se renseigner sur les traitements, les risques d'infection liés au sida ou le « vivre avec » la maladie ou le virus. Ensuite, ils servent de média pour les institutions de santé ou les associations afin de communiquer des informations de prévention sur le VIH. Enfin, ils apparaissent comme sources de connaissances pour les professionnels de santé (médecins, soignants) pour comprendre les comportements liés au VIH, et pour les professionnels de la prévention, pour modérer les forums et adapter les campagnes de prévention aux différents publics.

**Objectif** : Notre objectif dans cet article est de proposer un processus d'ingénierie des connaissances complet, permettant : 1) de collecter des messages dans des médias sociaux; 2) de classifier ces messages de manière semi-automatique selon le genre, le niveau d'expertise, le niveau informationnel, le type de risque ainsi que les émotions exprimées; 3) de visualiser ces nouvelles connaissances dans une représentation originale prenant en compte la temporalité et la hiérarchie sous-jacente à la classification. Cette visualisation pourrait permettre aux gestionnaires de sites de forums et aux professionnels de santé de naviguer dans le flot de messages pour suivre l'évolution de l'importance de ces thématiques.

**Méthodes** : Notre approche combine une démarche quantitative et quantitative. Nous avons travaillé sur plus de 226 252 messages issus du forum Sida Info Service. Deux chercheurs en sciences de l'information et de la communication ont élaboré une grille d'analyse, puis ont annoté 4 481 messages selon cette grille. Ces données ont été utilisées pour apprendre des classifieurs qui ont permis d'établir l'ensemble des messages du site à notre disposition. Afin de définir les meilleurs classifieurs, nous avons comparé l'efficacité des méthodes de classification tradition-

nelles statistiques et plusieurs architectures d'apprentissage profond. Une fois les messages étiquetés, nous avons utilisé une visualisation de type streamgraph, combinée avec un outil de navigation hiérarchique, pour visualiser l'évolution de ces annotations dans le temps.

**Résultats** : Les résultats sont prometteurs et montrent l'efficacité des méthodes d'apprentissage profond pour caractériser les messages des forums de manière automatique. La méthode de visualisation mise en place permet d'exploiter les résultats de ces méthodes et ainsi faciliter l'accès aux connaissances.

## Mots Clef

Classification automatique de textes, Apprentissage profond, Visualisation, VIH

## Abstract

It's the English version of the abstract. Exactly as in French it must be short. It must speak of the same topics...

## Keywords

Example, model, template.

# 1 Introduction

À l'heure où 3,9 milliards d'individus dans le monde sont connectés à internet (soit 51% de la population mondiale), et où 2,91 milliards d'entre eux sont inscrits sur des réseaux sociaux (soit 29% de la population mondiale)<fnref n="1" />, les pratiques pour s'informer et communiquer ont considérablement évolué et sont marquées par les innovations technologiques récentes et la place occupée par le numérique. En 2017, 74% des français accèdent tous les jours à Internet (95% des 18-24 ans) et passent en moyenne 1 heure 15 par jour sur les réseaux sociaux.

Les travaux présentés dans cet article se déroulent dans le cadre du projet #AIDS (Analyse Information Dangers

<footnote n="1">1. https://www.blogdumoderateur.com/chiffres-reseaux-sociaux/</footnote>
Sexualité) qui réunit une équipe de chercheurs pluridis-
ciplinaire en sciences de l'information et de la commu-
nication et en informatique, ainsi que des acteurs de la
santé et de la prévention. Ce projet vise à analyser semi-
automatiquement les contenus échangés sur les médias so-
ciaux (forums de discussion, réseaux sociaux, plateformes
de microblogging) consacrés au VIH pour en extraire de
la connaissance. Avec plus de 35 millions de morts à ce
jour, le VIH continue de représenter un problème mondial
majeur de santé publique. En 2016, 1 million de personnes
sont décédées d'une ou des causes liées au VIH dans le
monde <fnref n="2" />. Toujours en 2016, en France, 6 003 personnes ont
découvert leur séropositivité.

Les médias sociaux consacrés aux VIH s'adressent principalement aux personnes infectées et aux malades dans une démarche de prévention ou d'accompagnement mais également aux internautes soucieux de connaître les risques de contamination. Les publications peuvent prendre plusieurs formes comme des dispositifs de prévention, d'accompagnement, d'amélioration de la santé mentale et physique, des espaces d'échanges où sont évoqués les traitements, le "vivre avec" la maladie ou le virus, et plus largement des questions de la vie de tous les jours ou encore donner lieu à des usages sexuels d'Internet.

Un grand nombre de ressources en ligne sont disponibles, à toute heure. De nombreux blogs comme *Je VIH avec* <fnref n="3" /> alimentés par des médecins, des porteurs du virus, des associations de malades sont présents sur le web. De nombreux groupes de discussion sont consacrés à ces thématiques sur des réseaux sociaux destinés aux patients comme Carenity <fnref n="4" /> ou encore sur le site généraliste Doctissimo<fnref n="5" />. On dénombre, au 1er mars 2018, une centaine de groupes facebook français en lien avec le VIH. Plus de 500 comptes twitter mentionnent les hashtags #VIH ou #SIDA dans l'intitulé de leur compte, au 1er mars 2018. Ces comptes émanent d'associations, de particuliers, d'institutions ou de médecins. Ils portent pour la plupart sur les traitements ou sur la vie quotidienne avec le VIH. Dans ce travail, nous nous focaliserons sur les messages qui nous ont été fournis par les gestionnaires du forum associé au site Sida Info Service (SIS) <fnref n="6" />.

Si les médias sociaux ont largement été étudiés, peu de tra-
vaux ont jusqu'à présent été menés sur les médias sociaux
consacrés au VIH et en particuliers les forums de santé.
L'originalité de ce travail est de considérer, d'une part ces
médias comme des dispositifs info-communicationnels sur
lesquels se développent de nouvelles formes d'échanges et
qui véhiculent des informations n'ayant pas leur place dans
d'autres espaces (cabinet médical, discussions familiales,
médias traditionnels...). D'autre part, les discours produits
sur ces médias reflètent des pratiques ordinaires relatives

aux questions de sexualité, de consommations de produits
illicites et d'addictions et permettent de détecter des pra-
tiques émergentes, de nouvelles conduites à risque. Notre
objectif dans cet article est de proposer une chaîne
de traitements incluant une phase de classification et
un outil de visualisation pour mieux analyser et com-
prendre les contenus de ces discours. Ces informations
sont essentielles pour la modération du site.

Notre approche combine une démarche qualitative et quantitative. Nous avons travaillé sur plus de 226 252 messages issus du forum SIS. Deux professionnels de l'information et de la communication ont élaboré une grille d'annotation, puis ont annoté 4 481 messages selon cette grille. Ces données ont été utilisées pour apprendre des classifieurs supervisés qui ont permis d'étiqueter dans un deuxième temps, les 226 252 messages de manière automatique. Une fois les messages étiquetés, nous avons utilisé une approche MultiStream [8] adaptée aux séries temporelles multiples. L'originalité est ici de pouvoir visualiser simultanément la hiérarchie associée aux annotations et leur évolution dans le temps.

Concernant la phase de classification automatique de textes il s'agit d'un sujet classique de Traitement Automatique de la Langue (TAL), qui consiste à assigner des catégories prédéfinies à des documents en texte libre. Les approches de classification classiques se concentrent sur le choix du meilleur classifieur (e.g. SVM ou régression logistique) et sur la définition des meilleures caractéristiques prises en entrée de ces classifieurs. La plupart des techniques sont basées sur les mots, les lexiques et sont spécifiques à une tâche particulière. Ces modèles ont été appliqués avec succès sur de très hautes caractéristiques dimensionnelles parfois éparses. Dernièrement, pour de nombreuses tâches de classification de textes, les méthodes d'apprentissage profond se sont révélées efficaces et ont permis de faire des progrès importants dans des domaines tels que la reconnaissance de formes (pattern recognition) [4] ou la bioinformatique [23].

Cette tendance s'est confirmée avec le succès des word em-
beddings [21, 22] et des méthodes d'apprentissage profond
[35]. L'apprentissage profond permet l'apprentissage auto-
matique de représentations à plusieurs niveaux.

[7] ont démontré qu'une architecture d'apprentissage profond, même simple, surpasse la plupart des approches classiques pour des tâches variées de TAL telles que la reconnaissance d'entités nommées (NER) [1], le Parsing [39, 45], l'étiquetage de rôles sémantiques (SRL) (Seman-tic Role Labeling) [13, 36], le marquage POS [3, 18], la classification de sentiments [32, 25, 15, 16], la traduc-tion automatique [37]. Depuis, de nombreux algorithmes complexes d'apprentissage profond ont été proposés pour résoudre ces tâches difficiles. Dans cet article, nous al-lons entre autres comparer l'efficacité des méthodes de classification traditionnelles et plusieurs architectures d'apprentissage profond.

<footnote n="2">2. http://www.who.int/mediacentre/factsheets/fs360/fr/</footnote>

<footnote n="3">3. http://je-vih-avec.over-blog.com/</footnote>

<footnote n="4">4. https://www.carenity.com/</footnote>

<footnote n="5">5. http://www.doctissimo.fr/</footnote>

<footnote n="6">6. https://www.sida-info-service.org/</footnote>
De nombreux travaux en visualisation portent sur la représentation de données textuelles<fnref n="7" /> [17] et/ou temporelles<fnref n="8" /> [2]. Une approche prometteuse, permettant de représenter des données temporelles issues de textes, a initialement été proposée par [12] sous le nom de *ThemeRiver*. Généralisée sous le nom de *StreamGraphs*, cette approche consiste à superposer des flots représentant l'évolution d'une valeur numérique (le plus souvent issue de textes) dans le temps [5]. De nombreuses évolutions ont été proposées, e.g. [9, 38, 42]. La principale limite de ces approches est la difficulté de représenter un grand nombre de flots et un long intervalle de temps. La méthode utilisée dans cet article appelée *MultiStream* [8], pallie ces problèmes en décrivant une approche de type *focus+contexte* combinant un ensemble de vues interactives. **Dans cet article, nous montrerons comment cette visualisation aide le chercheur en science de l'information et de la communication à analyser l'ensemble des messages du site.**

L'article est organisé en quatre sections. Dans la section 2, nous présentons notre processus. Dans la section 3, nous présentons l'évaluation de la chaîne de traitements proposée. Dans la section 4, nous discutons ces résultats et ouvrons des perspectives.

## 2 Méthodes

La figure 1 illustre la méthode proposée, structurée en 4 étapes : (1) Collecte et nettoyage de données, (2) Annota- tion manuelle par deux experts, (3) Prédiction automatique de catégories, (4) Visualisation temporelle et hiérarchique de ces catégories.

<figure><img src="image_85.png" /><figcaption>FIGURE 1 – Processus en 4 étapes</figcaption></figure>

### 2.1 Étape 1 : Collection et nettoyage des données

Nous avons effectué une analyse de contenu de 226 252 messages en français postés sur le forum SIS qui nous ont été fournis par les gestionnaires du forum <fnref n="9" />. Ces messages ont été anonymisés en supprimant les pseudonymes, noms, prénoms et localités. Puis les prétraitements suivants

ont été appliqués : suppression des ponctuations et des caractères spéciaux, changement des majuscules en minuscules, suppression des mots trop fréquents pour apporter de l'information à partir d'une liste de stop words et enfin stemmatisation consistant à ne conserver que le radical des mots, pour regrouper sous le même radical tous les mots d'une famille.

### 2.2 Étape 2 : Annotation manuelle

Deux chercheurs en sciences de l'information et de la communication impliqués dans le projet, ont élaboré une grille d'annotation permettant de caractériser les types d'informations véhiculées par les messages postés sur les médias sociaux à partir d'une typologie testée précédemment sur des forums de discussion de santé et en tenant compte de la temporalité de l'écriture, des thématiques abordées, des micro-échanges [28, 6]. 4 481 messages ont été annotés manuellement par les deux experts <fnref n="10" /> (sans croisement des annotations). Les chercheurs ont systématiquement annoté l'un des forums général de SIS (le plus volumineux), qui comporte plusieurs dizaines de fils de discussion, sans faire de sélection *a priori* des thématiques. La grille s'organise selon 5 dimensions :

1. le genre de l'auteur décliné en femme et homme;

2. le niveau d'expertise de l'auteur. On distingue les messages des modérateurs, correspondant à des sa- voirs, de ceux des patients, qui parfois citent leur source ou rapportent des discours;

3. le niveau informationnel du message. Les messages peuvent correspondre à des partages (d'expé- rience ou de connaissances), à des questions formu- lées explicitement ou non, à des témoignages fais- sant référence au vécu, à l'expérience, à des infor- mations spécialisées (qui rapportent notamment des discours professionnels) ou scientifique (contenu supposé objectif dont la validité ne s'appuie pas sur le vécu), à des conseils (informations pratiques, procédures, protocoles);

4. les émotions exprimées par les participants en considérant un spectre émotionnel : la panique, l'angoisse, la peur, l'inquiétude, la réassurance (le fait de rassurer quelqu'un) ou le fait d'être rassuré.

5. le risque. Un message peut faire référence à un risque encouru par les internautes lors d'un événe- ment passé, présent ou à venir, déclencheur d'une sensation de prise de risque. Les types de situation qui déclenchent une sensation de risque n'ont pas été annotées compte tenu du fait que ces situations sont bien connues des associations et figurent dans la rubrique « Questions fréquentes ». En revanche, nous avons laissé la possibilité à l'annotateur d'in- troduire un commentaire libre sur l'éventuelle prise

<footnote n="7">7. http://textvis.lnu.se/</footnote>

<footnote n="8">8. https://vcg.informatik.uni-rostock.de/~ct/timeviz/timeviz.html</footnote>

<footnote n="9">9. Accord CNIL, Certificat d'enregistrement 2-17031</footnote>

<footnote n="10">10. Avec l'aide de Amal Jaouzi, stagiaire, doctorante en sciences de l'information et la communication.</footnote>
d'alcool et de drogue durant l'événement déclencheur.

Un message peut donc être décrit selon ces 5 dimensions. Dans la Table 1, nous résumons la liste des classes définies après la phase d'annotation manuelle, ainsi que le nombre de messages annotés avec ces étiquettes. Chaque message peut être associé à zéro, une ou plusieurs classes. Ces classes seront utilisées comme sorties pour la prédiction de catégories.

<table><caption>TABLE 1 – Sortie de la prédiction</caption><thead><tr><th>Index</th><th>Dimensions d'analyse</th><th>Classe</th><th>Effectif</th></tr></thead><tbody><tr><td>C1</td><td>genre</td><td>Femme</td><td>36</td></tr><tr><td>C2</td><td>genre</td><td>Homme</td><td>67</td></tr><tr><td>C3</td><td>expertise</td><td>modérateur</td><td>46</td></tr><tr><td>C4</td><td>expertise</td><td>savoir patient</td><td>222</td></tr><tr><td>C5</td><td>expertise</td><td>sources citées</td><td>19</td></tr><tr><td>C6</td><td>expertise</td><td>discours rapporté</td><td>8</td></tr><tr><td>C7</td><td>information</td><td>demande</td><td>402</td></tr><tr><td>C8</td><td>information</td><td>informations scientifiques ou pratiques</td><td>661</td></tr><tr><td>C9</td><td>information</td><td>apport-réponse</td><td>874</td></tr><tr><td>C10</td><td>information</td><td>témoignage</td><td>284</td></tr><tr><td>C11</td><td>information</td><td>information vide</td><td>1144</td></tr><tr><td>C12</td><td>information</td><td>conseils</td><td>159</td></tr><tr><td>C13</td><td>émotion</td><td>peur</td><td>66</td></tr><tr><td>C14</td><td>émotion</td><td>inquiétude</td><td>109</td></tr><tr><td>C15</td><td>émotion</td><td>panique</td><td>34</td></tr><tr><td>C16</td><td>émotion</td><td>général</td><td>28</td></tr><tr><td>C17</td><td>émotion</td><td>angoisse</td><td>142</td></tr><tr><td>C18</td><td>émotion</td><td>réassurance</td><td>57</td></tr><tr><td>C19</td><td>émotion</td><td>rassuré</td><td>22</td></tr><tr><td>C20</td><td>risque</td><td>anticipé</td><td>8</td></tr><tr><td>C21</td><td>risque</td><td>passé</td><td>92</td></tr><tr><td>C22</td><td>risque</td><td>actuel</td><td>1</td></tr></tbody></table>

## 2.3 Étape 3 : Modèles pour la prédiction de catégories

Dans cette étude, nous explorons l'utilisation de méthodes d'apprentissage profond pour prédire les 22 catégories des messages collectés. Nous avons comparé les résultats des modèles d'apprentissage profond aux méthodes de classification traditionnelles. Dans cette section, nous détaillons comment chaque modèle est construit.

**Modèles.** Les modèles utilisés dans notre étude sont résumés dans le tableau 2. Les modèles d'apprentissages classiques comparés sont de type SVM (LSVC, SSVC), Naïve Bayes (MNB, BNB), Régression linéaire (SGDC), Arbre de décision (DT, AB, RF), K-plus-proches-voisins (KNC, PA). Dans ce qui suit, nous discutons plus précisément les modèles d'apprentissage profond. Tous nos modèles sont construits à partir de la même couche d'entrée et de la même couche de sortie. La couche d'entrée est une couche de type embedding permettant de caractériser chaque mot du document analysé par un vecteur de dimension 300. La couche de sortie contient elle, autant de neurones qu'il y a de classes dans notre ensemble de données. Ensuite, nous décrivons les couches intermédiaires de nos différents modèles de réseaux neuronaux. Nous invitons le lecteur à consulter des revues plus détaillées telles que celle de [33].

- Basic neural network (BNN) connecte directement la couche d'entrée avec la couche de sortie.

<table><caption>TABLE 2 – Modèles de Classification : classiques vs apprentissage profond</caption><thead><tr><th>Classiques</th><th>Apprentissage profond</th></tr></thead><tbody><tr><td>LinearSVC (LSVC)</td><td>Basic neural network (BNN)</td></tr><tr><td>SigmoidSVC (SSVC)</td><td>Multi-layer perceptrons (MLP)</td></tr><tr><td>MultinomialNB (MNB)</td><td>Deep Multi-layer perceptrons (DMLP)</td></tr><tr><td>BernoulliNB (BNB)</td><td>Long short-term memory (LSTM) RNN</td></tr><tr><td>SGDClassifier (SGDC)</td><td>Bidirectional Long short-term memory (BLSTM) RNN</td></tr><tr><td>Decision Tree (DT)</td><td>Gated Recurrent Unit (GRU) RNN</td></tr><tr><td>AdaBoost (AB)</td><td>Long-term Recurrent Convolutional Networks (LRCN)</td></tr><tr><td>Random Forest (RF)</td><td>Convolutional neural network (CNN)</td></tr><tr><td>KNeighborsClassifier (KNC)</td><td>Serial Convolutional neural network (SCNN)</td></tr><tr><td></td><td>Multi Channel Convolutional neural network (MCNN)</td></tr></tbody></table>

- Multilayer Perceptrons (MLP) est le modèle le plus simple d'apprentissage profond. Il est réalisé par une couche cachée de neurones entre la couche d'entrée et de sortie.

- Deep Multilayer Perceptrons (DMLP) est basé sur 20 couches cachées.

- Long Short-Term Memory (LSTM) est un sous-type de RNN. Les réseaux neuronaux récurrents permettent l'étude de séquences de données. Ces réseaux, composés de plusieurs couches, estiment leurs sorties en fonction des états de leurs couches précédentes en utilisant une mémoire intermédiaire. LSTM est basé sur des blocs de mémoire qui sont utilisés comme unités dans la couche récurrente pour capturer des dépendances à plus longue portée.

- Bidirectional Long Short-Term Memory (BLSTM) permet d'utiliser l'information après et avant les données étudiées par le réseau au temps t.

- Gated Recurrent Unit (GRU) est un réseau de neurones permettant une étude plus rapide que le LSTM tout en conservant les qualités de celui-ci.

- Long-term Recurrent Convolutional Networks (LRCN) associe en série un réseau convolutif et un réseau LSTM.

- Convolutional Neural Network (CNN) sont struc- turés par deux opérations : convolution puis max- pooling. La convolution est basée sur plusieurs filtres combinés pour extraire les nombreuses pro- priétés associées aux données. La seconde opéra- tion compresse les résultats de l'opération précéd-ente pour extraire des informations denses.

- Serial Convolutional neural network (SCNN) place séquentiellement quatre réseaux convolutionnels les uns après les autres.

- Multi Channel Convolutional neural network (MCNN) est basé sur six réseaux de convolution branchés sur la couche d'entrée. Chaque réseau de convolution possède un noyau différent des autres. Ensuite, nous associons la sortie des six réseaux de convolution à une seule couche pour construire une sortie mono-couche entièrement connectée.

**Entrées des modèles** : Les entrées des modèles sont les messages. Nous utilisons deux pré-traitements distincts
pour les deux types de méthodes de classification étudiées. Pour les méthodes de classification traditionnelles, nous appliquons une vectorisation basée sur la mesure Tf-Idf [30]. Pour les méthodes d'apprentissage profond, les données sont préparées différemment. Nous conservons les 5000 mots les plus fréquents (hors stop words) et nous représentons chaque document par une séquence de mots ce qui permet de conserver l'ordre des mots.

**Sorties des Modèles** : Les effectifs dans les classes sont très déséquilibrés. Nous avons donc mis en place deux stratégies que nous appelons *précise* et *imprécise*. Dans la stratégie *précise*, l'objectif est de décrire finement un message, par exemple selon la dimension émotion, en l'associant à l'étiquette *peur* ou *angoisse*. Dans la stratégie *imprécise*, le niveau de description attendu est plus général et le message pourrait être associé à une émotion négative. Nous avons donc regroupé manuellement, après discussion avec les experts, certaines classes. Par ailleurs, un grand nombre de messages ne sont pas étiquetés comme le montre le tableau 1. Pour le niveau d'expertise, les émotions et le risque, nous avons considéré une classe *Autres* correspondant à des messages non étiquetés. Nous effectuons sur ces échantillons un ré-échantillonnage de la taille de la classe majoritaire (non étiquetée). Une description des classes finales est donnée dans la table 3.

<table><caption>TABLE 3 – Classes utilisées dans les modèles selon les deux stratégies précise et imprécise</caption><thead><tr><th>Stratégie</th><th>Précise (Nombre de posts)</th><th>Imprécise (Nombre de posts)</th></tr></thead><tbody><tr><td>Genre</td><td>genre_1<br>C1 (57)<br>C2 (28)</td><td></td></tr><tr><td>Niveau d'expertise</td><td>expe_1<br>C3 (222)<br>C4 (46)<br>C5/C6 (74)</td><td>expe_2<br>C3/C4/C5/C6 (342)<br>Autres (342)</td></tr><tr><td>Niveau informationnel</td><td>info_1<br>C7 (402)<br>C8 (661)<br>C9 (874)<br>C10 (284)<br>C11 (1144)<br>C12 (159)</td><td>info_2<br>C7 (402)<br>C8/C9/C10/C12 (1978)<br>C11 (1144)</td></tr><tr><td>Émotion</td><td>emot_1<br>C13/C14 (65)<br>C15/C17 (544)<br>C18/C19 (30)</td><td>emot_2<br>C13/C14/C15/C16 (609)<br>C18/C19 (30)<br>Autres (609)</td></tr><tr><td>Risque</td><td></td><td>risq<br>C20/C21/C22 (101)<br>Autres (101)</td></tr></tbody></table>

**Partitionnement des données et entraînement** Afin d'évaluer les différents modèles, nous appliquons une validation croisée en dix plis. L'ensemble de données est divisé en dix sous-ensembles. Nous utilisons neuf sous-ensembles pour la phase d'apprentissage et un sous-ensemble pour la phase de validation. Nous avons répété ce processus dix fois. Pour chaque pli, nous utilisons un sous-ensemble de différentes phases de validation et nous avons calculé une métrique pour évaluer la performance.

Pour les algorithmes de classification classiques, nous

utilisons l'outil sklearn<fnref n="1" /> avec les paramètres par défaut. Pour toutes les architectures d'apprentissage profond, nous avons utilisé les paramètres par défaut pour la taille du Mini-batch (c.-à-d. Le nombre d'instances d'entraînement à considérer en même temps), la dimension d'intégration (embedding dimension, chaque mot est décrit par un vecteur de dimension *n*), le nombre d'epoch (le nombre d'itérations sur l'ensemble d'entraînement), la fonction d'activation et le taux d'abandon (Dropout ratio, ratio d'unités cachées à désactiver dans chaque formation de Mini-batch). Ensuite, nous utilisons une configuration avec un Mini-batch de taille 32, une dimension d'intégration de 300, une couche cachée de taille 256, un nombre d'epoch de 25, la fonction d'activation selu et un Dropout de 0,3.

**Mesure de la performance** Pour tous les modèles, nous nous sommes basés sur une métrique couramment utilisée dans le domaine de la classification. Chaque sortie est un vecteur de dimension *n* correspondant aux *n* classes à pré dire. Nous mesurons la qualité des classificateurs avec la mé trique *exactitude* (accuracy). Celle-ci exprime le nombre de classes prédites justes en regard du nombre total de prédic tions de classes réalisées. Nous avons choisi d'utiliser une métrique stricte en considérant une sortie comme juste uni quement si l'intégralité des classes prédites sont exactes.

**Exemple 1** Considérons 3 documents décrits par un vecteur d'annotations pour 4 classes. Chaque élément *i* de ce vecteur correspond à la présence (1) ou à l'absence (0) de la classe *i* pour le document.

Document1 → 0010

Document2 → 1000

Document3 → 0100

Considérons maintenant un modèle retournant 3 vecteurs de prédicitions de ces 4 classes. Chaque élément *i* de ce vecteur correspond à la prédiction (1) ou à l'absence de prédiction (0) de la classe *i* pour le document.

prédiction1 → 0010

prédiction2 → 0010

prédiction3 → 1100

Seule la première prédiction sera considérée comme juste pour les trois prédicitions émises. L'exactitude du modèle sera égale à : $acc = \frac{1}{3} = 0.333$

## 2.4 Étape 4 : Visualisation temporelle et hiérarchique

Le flux de messages peut être représenté sous la forme d'une série temporelle multiple, c'est-à-dire un ensemble de variables quantitatives associées à un même intervalle temporel. Au cours des dernières années, les visualisations de type *Streamgraphs* [5] ont été largement utilisées pour représenter l'évolution de plusieurs séries temporelles. Cependant, les *Streamgraphs* posent deux problèmes majeurs : (1) Comment gérer un long intervalle de

<footnote n="1">1. http://scikit-learn.org/stable/</footnote>
temps ? (2) Comment gérer un grand nombre de séries temporelles ?

Pour résoudre le problème (1), des méthodes de type vue d'ensemble+détail ou encore focus+contexte peuvent être mises en place (voir [24] pour une introduction). Les méthodes vue d'ensemble+détail consistent à combiner deux vues, une montrant l'ensemble des données de façon agréée, l'autre montrant en détail un sous ensemble sélectionné. Les méthodes de type focus+contexte consistent à intégrer les parties agrégées (contexte) et les parties détaillées (focus) dans une seule et même vue. La plus connue de ces méthodes est sans doute le *fisheye* qui consiste à appliquer une distortion sur la visualisation de façon à agrandir la zone du focus en réduisant la zone du contexte.

Pour résoudre le problème (2), les séries temporelles peuvent être agrégées selon leur proximité pour former une structure hiérarchique visualisable sous forme d'arbre. Cet arbre peut aider à sélectionner les niveaux de détail affichés.

La méthode que nous utilisons ici [?] repose sur 3 vues permettant de traiter les problèmes susmentionés. Une première vue (voir Fig. 2 cadre 1) permet de voir les séries agrégées sur l'ensemble de l'intervalle de temps, et de sélectionner un sous-intervalle (vue d'ensemble). Une seconde vue (voir Fig. 2 cadre 2) affiche les séries sur l'intervalle sélectionné (détail). Cette vue inclut un *fisheye*, i.e. une zone dans laquelle les séries sont détaillées (focus), entourée par des zones dans lesquelles les séries sont agréées (contexte). La troisième vue (voir Fig. 2 cadre 3) permet de visualiser l'arbre d'agrégation, dans notre cas la hiérarchie des classes présentées dans la table 1 et de sélectionner les niveaux devant être utilisés pour les zones agrégées et pour les zones détaillées.

<figure><img src="image_86.png" /><figcaption>FIGURE 2 – Visualisation des séries temporelles avec un focus sur la période 2008-2011.</figcaption></figure>

# 3 Résultats

## 3.1 Comparaison des modèles de classification

Le tableau 4 synthétise les résultats des différents classifi-

<figure><img src="image_87.png" /><figcaption>FIGURE 3 – Visualisation de la dimension "Niveau informationnel" dans laquelle les messages relatifs à la classe "Information vide" ont été filtrés grâce à l'arbre d'agrégation.</figcaption></figure>

<table><caption>TABLE 4 – Comparaison des performances des classifi-fieurs.</caption><thead><tr><th rowspan="2">Stratégie</th><th colspan="4">Précise</th><th colspan="4">Imprécise</th></tr><tr><th>emot_1</th><th>genre_1</th><th>expe_1</th><th>info_1</th><th>emot_2</th><th>expe_2</th><th>info_2</th><th>risq</th></tr></thead><tbody><tr><td>LSVC</td><td>0.318</td><td>0.621</td><td>0.735</td><td>0.255</td><td>0.533</td><td>0.659</td><td>0.488</td><td><strong>0.638</strong></td></tr><tr><td>SSVC</td><td><strong>0.325</strong></td><td>0.624</td><td>0.735</td><td>0.242</td><td>0.532</td><td>0.422</td><td>0.000</td><td>0.440</td></tr><tr><td>MNB</td><td>0.020</td><td>0.631</td><td>0.701</td><td>0.175</td><td>0.472</td><td>0.662</td><td>0.406</td><td>0.603</td></tr><tr><td>BNB</td><td>0.058</td><td><strong>0.660</strong></td><td>0.725</td><td>0.280</td><td><strong>0.563</strong></td><td><strong>0.672</strong></td><td>0.371</td><td>0.603</td></tr><tr><td>SGDC</td><td>0.309</td><td>0.640</td><td>0.711</td><td>0.238</td><td>0.518</td><td>0.630</td><td><strong>0.490</strong></td><td>0.608</td></tr><tr><td>DT</td><td>0.244</td><td>0.533</td><td>0.664</td><td>0.206</td><td>0.468</td><td>0.625</td><td>0.362</td><td>0.564</td></tr><tr><td>AB</td><td>0.300</td><td>0.563</td><td>0.718</td><td>0.248</td><td>0.493</td><td>0.600</td><td>0.450</td><td>0.633</td></tr><tr><td>RF</td><td>0.0</td><td>0.650</td><td><strong>0.752</strong></td><td>0.0</td><td>0.116</td><td>0.379</td><td>0.0</td><td>0.440</td></tr><tr><td>KNC</td><td>0.227</td><td>0.533</td><td>0.677</td><td><strong>0.323</strong></td><td>0.439</td><td>0.589</td><td>0.281</td><td>0.461</td></tr><tr><td>BNN</td><td>0.718</td><td>0.945</td><td>0.966</td><td>0.372</td><td>0.841</td><td>0.894</td><td>0.883</td><td>0.883</td></tr><tr><td>MLP</td><td>0.662</td><td>0.945</td><td>0.966</td><td>0.356</td><td>0.745</td><td>0.901</td><td>0.909</td><td><strong>0.921</strong></td></tr><tr><td>DMLP</td><td>0.627</td><td>0.658</td><td>0.788</td><td>0.308</td><td>0.801</td><td>0.342</td><td>0.291</td><td>0.376</td></tr><tr><td>LSTM</td><td><strong>0.827</strong></td><td><strong>0.990</strong></td><td><strong>0.969</strong></td><td><strong>0.564</strong></td><td><strong>0.882</strong></td><td><strong>0.922</strong></td><td><strong>0.940</strong></td><td>0.906</td></tr><tr><td>BLSTM</td><td>0.776</td><td>0.927</td><td>0.953</td><td>0.521</td><td>0.855</td><td>0.906</td><td>0.898</td><td>0.902</td></tr><tr><td>GRU</td><td>0.502</td><td>0.684</td><td>0.884</td><td>0.355</td><td>0.441</td><td>0.805</td><td>0.745</td><td>0.805</td></tr><tr><td>LRCN</td><td>0.795</td><td>0.954</td><td>0.926</td><td>0.516</td><td>0.832</td><td>0.881</td><td>0.893</td><td>0.907</td></tr><tr><td>CNN</td><td>0.713</td><td>0.954</td><td>0.963</td><td>0.408</td><td>0.841</td><td>0.900</td><td>0.883</td><td>0.897</td></tr><tr><td>SCNN</td><td>0.741</td><td>0.954</td><td>0.959</td><td>0.416</td><td>0.829</td><td>0.905</td><td>0.893</td><td>0.892</td></tr><tr><td>MCNN</td><td>0.734</td><td>0.963</td><td>0.956</td><td>0.382</td><td>0.847</td><td>0.905</td><td>0.881</td><td>0.892</td></tr></tbody></table>
gies. Comme l'on pouvait s'y attendre, les résultats pour les stratégies de classification précises sont inférieurs aux résultats pour les stratégies de classification imprécises. Par exemple, pour la dimension relative au niveau informationnel, l'exactitude pour la classification info_1 (stratégie précise) est au mieux de 0,564 alors que pour info_2 (stratégie imprécise) est de 0,906. Pour chaque type de classification, les meilleurs classifieurs traditionnels ont obtenu des résultats inférieurs aux classifieurs en apprentissage profond. Par exemple, pour la classification du genre, le meilleur classificateur traditionnel obtient une exactitude de 0,660 alors que le meilleur classifieur en apprentissage profond obtient une exactitude de 0,990. Pour 7 types de classification sur 8, la meilleure architecture est LSTM. Ce résultat est cohérant avec la littérature. Par exemple, [14] obtiennent également des résultats performants sur des textes avec LSTM. La classification du genre, de l'expertise, du risque et du niveau d'expérience obtiennent en apprentissage profond des exactitudes supérieures à 0,9 dans le cas imprécis et même parfois précis. Les résultats sont plus mitigés pour les émotions et le niveau informationnel qui correspondent aux classes très déséquilibrées, en particulier avec les classifieurs classiques. Par exemple, le classifieur RF ne fonctionne pas sur les classes déséquilibrées telles que emot_1 ou emot_2. Il serait intéressant de réannoter un nombre suffisant d'exemples pour rééquilibrer ces classes.

## 3.2 Visualisation

La visualisation obtenue à partir des 226 252 messages annotés automatiquement à partir du meilleur modèle (LSTM) est disponible sur le site du projet Multistream<fnref n="11" />. La figure 2 permet de repérer un pic d'activité du forum en 2009 et une majorité d'information de type "Information vide" révélant la part importante de messages de convivialité ou de soutien, les conseils étant également très recherchés dans des forums modérés par des professionnels de la prévention. La figure 3 est obtenue après sélection des classes à afficher dans l'arbre d'agrégation, en filtrant les messages de type "Information vide". On remarque alors que l'information de type "Demande" domine le pic de messages de 2009, ce qu'il n'était pas possible de visualiser avant le filtrage. Ces deux figures illustrent le processus de navigation dynamique dans le flux de messages, rendu possible par l'outil MultiStream.

Nous allons détailler dans la suite les 5 dimensions identifiées lors de la phase d'annotation manuelle (le genre, le niveau d'expertise, le niveau informationnel, le risque et les émotions) et illustrer avec des exemples ce qu'il est possible de repérer dans ces flots d'informations, et l'exploitation éventuelle qui peut en être faite.

Concernant la dimension *Genre*, on remarque qu'il y a plus de messages d'hommes que de femmes. Cette situation

est spécifique au VIH, puisque les femmes sont souvent plus présentes sur les forums de santé [27]. Dans le cas du sida, les hommes ayant des relations sexuelles avec d'autres hommes (HARSAH), en termes de prévalence, sont les plus touchés par le VIH, ils sont aussi la cible des campagnes de prévention et sont bien informés des risques d'exposition au sida [10]. Ces résultats nous laissent penser que les forums constituent des médias alternatifs et complémentaires [31] indispensables pour des hommes plutôt moins acculturés aux messages de prévention, qui se renseignent pour des prises de risques plus exceptionnelles (par exemple dans le cadre de relations extra-conjugales hétéro ou homosexuelles).

Concernant la dimension *Niveau d'expertise*, les messages annotés montrent que se développent sur les forums de nouvelles formes d'expertise, hors de la sphère médicale et relayées par le biais des participants ou des modérateurs. Ces informations sont de première importance pour les professionnels (de santé et de la prévention) qui peuvent ainsi appréhender les connaissances qui circulent sur le VIH. Ainsi, la majorité des messages correspondent à des "savoirs patients" et dans une moindre proportion à des messages de modérateurs ou à des messages contenant des sources citées et des discours rapportés. Dans le cas du VIH, les patients apparaissent comme experts de leur propre maladie, de leur cas singulier bien qu'ils ne soient pas spécialistes de la maladie en général ni de la médecine. Ces derniers ont été conduits à côtoyer des professionnels de santé dont ils rapportent les propos, ce qui légitime les conseils qu'ils donnent aux autres participants : "Merci de m'avoir répondu, c'est vrai vous m'avez bien rassurée ms je ne peux m'empecher de penser qu'il y a un risque, j'en ai parlé à 2 médecins qui travaillent avec moi, ils me disent que le risque est minime ms qu'il y en a un, ils ont l'habitude de soigner des séropositifs puisqu'ils accueillent des patients ayant eu un accident exposant au sang comme on dit chez nous". Les forums sont aussi le moyen de transmettre des sources spécialisées qui participent à la circulation des savoirs sur le VIH : "En tout cas pour tout ce qui est des modes de transmission du vih tu trouveras tout ce qu'il te faut savoir ici : http://www.sida-info service.org/forums ... hp4?t=3257[ ... ]."

Concernant le *Niveau informationnel*, la majorité des messages sont vides, au sens où ils renvoient à des messages de convivialité (ex. "Bonjour tous", "@ bientôt", "Merci++"). Une fois ces messages filtrés, deux types d'informations apparaissent : des demandes ou des apports d'information associés à ces demandes. Ces messages concernent essentiellement des informations pratiques ou scientifiques : "Bonjour, J'ai lu que les anticorps apparaissent généralement entre 20 et 45 jours après un risque. Ca veut donc dire que ||nom|| n'est tres fiable qu'apres 6 semaines ? Je sens que je vais avoir la reponse sybilline "1 mois=bonne indication, 3 mois= sur", mais j'aimerais savoir ce que ca veut dire bonne indication (je suis negatif a 4 semaines avec

<footnote n="11">11. http://advanse.lirmm.fr/multostream/ - jeu de données AIDS</footnote>
des ganglions et des courbatures partout... Et pouvez-vous aussi me dire si le test ||nom|| detecte le VIH-1 et le VIH-2 ? Merci pour vos reponses!!", et dans une moindre mesure des témoignages relatant le vécu des porteurs du virus. Les participants au forum directement concernés par le VIH cherchent en premier lieu des informations relatives à cette maladie, aux symptômes, aux traitements. Ils cherchent également à mieux comprendre le discours des experts en amont d'un rendez-vous médical ou en aval pour trouver la définition de termes spécialisés ou confirmer le discours des professionnels de santé. Pour les proches non directement concernés par le virus, la recherche d'information permet de découvrir des conseils pratiques pour accompagner une personne malade.

Concernant le risque, il faut distinguer une dimension objective du risque, incarnée dans une connaissance plus ou moins partagée des facteurs de prise de risque, qui se confronte à des perceptions variables du risque en lien notamment avec l'expérience personnelle de l'individu, son environnement social, affectif et culturel. La dimension subjective du risque motive l'essentiel des demandes : "Bonjour, ma copine est séropositive depuis peu, mon 1er test est négatif. J'attends 3 mois pour confirmer le résultat. Comme j'entends tout et n'importe quoi a propos des fellerions, je voulais savoir si je risquais un risque ou pas lors d'une fellation dans mon cas. Merci pour votre réponse. C'est nouveau pour moi et je gère assez mal la situation." Ainsi, les trois quarts des messages portent sur un risque passé, peu de personnes posant des questions avant une situation présumée risquée. Dans les forums où priment l'émotion, c'est la panique, le stress qui dominent. Cette situation engendre de la part des répondants des messages de réassurance, la catégorie d'émotion qui est la plus représentée en termes de pourcentage d'apports d'information. En effet, de nombreux messages d'encouragements, par exemple lors de l'attente d'un dépistage viennent soutenir les membres ayant pris un risque. Peu de messages ont cependant été étiquetés selon le risque lié à l'alcool et à la prise de substance psychotrope. Ce constat est certainement lié au fait qu'un forum institutionnel de type SIS n'est pas le lieu pour évoquer les pratiques à risques autres que celles liées à la sexualité.

## 3.3 Limites de l'étude

Notre approche préliminaire présente de nombreuses limites que nous détaillons dans cette section.

Concernant la phase d'annotation, la grille utilisée pourrait être retravaillée. La dimension relative au Niveau Informationnel pourrait être scindée en deux pour distinguer les messages relevant de l'interaction (demande ou apport de réponse à une question) des messages uniquement destinés à l'apport d'information (Information Scientifique et pratique, témoignage et conseil) ou encore les messages vides au niveau informationnel. Cela est tout à fait possible car la visualisation utilisée permet d'afficher plusieurs niveaux

de hiérarchie.

Concernant la phase de classification, la principale limite est que nous avons utilisé uniquement l'exactitude comme métrique pour évaluer la performance des classificateurs. Le rappel et la précision sont deux mesures importantes pour évaluer la qualité d'un classificateur et devrait être prises en considération. Une autre limitation porte sur l'interprétation de l'apprentissage profond. Ces modèles sont des "boîtes noires". Ils ne fournissent pas d'explication même si la prédiction est efficace [34]. Cependant, malgré un nombre de messages manuellement annotés limité, cette étude a montré que la performance des modèles traditionnels était beaucoup plus faible que la performance de l'apprentissage profond. De nouvelles techniques d'apprentissage profond sont étudiées pour faciliter l'interprétation de tels modèles [20, 19] et pourraient s'avérer judicieuses dans ce contexte.

Nous avons également identifié des limites liées à la temporalité utilisée pour la visualisation de l'ensemble des données du site SIS. Actuellement, la temporalité est le mois. Or, la période temporelle d'interaction est généralement le jour ou la semaine dans le contexte des échanges sur les forums. Une possibilité de focus sur une période plus courte permettrait de repérer des épisodes liés à des questions sur une prise de risque et le délai pour se faire dépister. En effet, 48h après une prise de risque, il existe un traitement préventif qui peut être suggéré par les internautes. Les résultats du premier test permettant de savoir s'il y a eu contamination sont obtenus entre 6 semaines et 90 jours. Cette période s'accompagne de messages contenant des émotions négatives, de la réassurance et dans la majorité des cas se finit par des messages de la personne rassurée comme nous avons pu l'observer dans de nombreux fils de discussion. De même, la visualisation pourrait être améliorée par l'affichage d'informations supplémentaires comme l'heure des messages. Cette information est essentielle notamment lorsque l'on s'intéresse aux émotions exprimées dans les messages. Par exemple, les angoisses s'expriment généralement la nuit. La quantification de ces phénomènes est important pour le site SIS en terme de planification de leurs équipes de modérateurs.

Pour finir, une dernière limite de notre étude est liée à la généralisation de nos résultats. En effet, la tâche est très spécifique au sujet d'étude, le VIH, au type de textes que sont les messages des forums, ce qui rend difficile la généralisation de notre approche. Toutefois, notre méthodologie et les résultats peuvent être utilisés comme référence pour d'autres études sur l'identification automatique de catégories à partir de données sociales.

## 4 Conclusion et perspectives

Notre étude a souligné l'efficacité des architectures d'apprentissage profond pour prédire des thèmes sur des données de forum. La visualisation originale sous forme de StreamGraph permet d'explorer de manière efficace tout en quantifiant les différentes catégories de
messages. La faisabilité de notre approche peut conduire
à de nouvelles applications en santé basées sur les médias
sociaux destinés aux patients et aux professionnels de
santé.

Nos résultats montrent clairement le besoin d'études capables d'analyser automatiquement des forums et d'en extraire des informations utiles. Nous proposons l'utilisation de l'apprentissage automatique et de la visualisation interactive pour relever ces défis. Cette étude reste préliminaire. Une étude plus approfondie sur les différents types de préparation des données, paramètres des algorithmes, modèles d'apprentissage permettrait d'affiner l'interprétation des résultats de la phase 3. En particulier, différents regroupement de classes et l'interprétation des liens entre classes serait pertinent. Quels sont les sentiments associés à une prise de risque ? Est-ce que les réponses apportées dans les fils sont rassurantes ou satisfaisantes ? Comment s'information les participants dans les forums ? Pour finir, une étude poussée sur l'utilité et l'utilisabilité de la visualisation présentée en phase 4 est également nécessaire. Nous suggérons 4 perspectives.

Premièrement, nous prévoyons d'entreprendre une analyse
à grande échelle en utilisant une collection de médias so-
ciaux plus large (Autres forums, Facebook, Twitter, ...).
Cette analyse inclura l'application de méthode d'appren-
tissage non supervisé de type Latent Dirichlet Allocation
(LDA) [29, 41] pour extraire les thèmes émergeant des dis-
cussions et l'exploration du style linguistique des différents
utilisateurs [44, 43, 40]. Une attention particulière sera por-
tée sur l'identification d'une typologie des risques encou-
rus en lien avec le VIH (e.g. consommation de drogue,
comportements sexuels atypiques, etc).

Deuxièmement, nous pensons que lorsque les ensembles de données sont petits, l'apprentissage est difficile. Une amélioration significative serait la mise en œuvre de techniques d'apprentissage actif [26]. En effet, dans ce type de tâche, il est important d'optimiser les informations disponibles afin que les systèmes de classification puissent les utiliser le plus efficacement possible pendant la phase d'apprentissage tout en préservant l'acquisition de nouveaux échantillons étiquetés [11]. L'utilisation de la visualisation pour guider les annotateurs vers des messages à annoter pourrait s'avérer également intéressante.

Troisièmement, au sein d'un ensemble de données suffis-
samment important, nous pouvons tirer parti des modèles
d'apprentissage automatique pour utiliser des fonctionna-
lités plus complexes pour caractériser les utilisateurs qui
postent ces messages. Nous suggérons de mettre l'accent
sur les groupes d'utilisateurs, y compris les professionnels
de la santé, les célébrités, le grand public et les associa-
tions. Cela nous amènera à comprendre quel groupe d'uti-
lisateurs est important, peut jouer le rôle d'influenceur, les
incitant à partager leurs messages, à les aimer et à leur ré-
pondre.

Pour finir, nous prévoyons d'étudier la distribution tempo-

relle des messages pour nous concentrer sur la dynamique
des thématiques au fils du temps. Nous pouvons étudier les
corrélations temporelles entre les réactions des internautes
et les événements du monde réel comme les soirées de
type Sidaction. Cette analyse exploratoire pourrait aider
à identifier les facteurs contribuant à la sensibilisation.
Au-delà, nous pouvons également analyser la répartition
géographique des messages.

Ce type d'étude est importante pour convaincre les parties
prenantes, les professionnels de la santé et le grand public
de s'impliquer et d'utiliser le Web 3.0 comme intelligence
collective pour repousser les maladies telles que le VIH.

5 Remerciements

Ce travail s'intègre dans le projet #AIDS et a été sou-
tenu par une subvention ANRS <fnref n="12" /> en 2016. Les auteurs
souhaitent remercier les gestionnaires du site Sida-Info-
Service pour le partage des données et ses participants pour
leur engagement à combattre le VIH.

Références

[1] Joint Named Entity Recognition and Disambiguation
(September 2015).

[2] AIGNER, W., MIKSCH, S., SCHUMANN, H., AND TOMINSKI, C. *Visualization of Time-Oriented Data*. Springer, 2011.

[3] ANDOR, D., ALBERTI, C., WEISS, D., SEVERYN, A., PRESTA, A., GANCHEV, K., PETROV, S., AND COLLINS, M. Globally normalized transition-based neural networks, 2016. cite arxiv :1603.06042.

[4] BACCOUCHE, M., MAMALET, F., WOLF, C., GARCIA, C., AND BASKURT, A. Sequential deep learning for human action recognition. In *Proceedings of the Second International Conference on Human Behavior Understanding* (Berlin, Heidelberg, 2011), HBU’11, Springer-Verlag, pp. 29–39.

[5] BYRON, L., AND WATTENBERG, M. Stacked Graphs - Geometry & Aesthetics. *IEEE Transactions on Visualization and Computer Graphics* 14, 6 (2008), 1245–1252.

[6] CLAVIER, V., AND PAGANELLI, C. Une approche méthodologique croisée du traitement des données de la recherche : le cas d'un corpus d'échanges issus de médias sociaux dans le domaine de la santé. In *Colloque COSSI 2017, Méthodes et stratégies de gestion de l'information par les organisations : des "Big Data"aux "Thick Data", 85ème congrès de l'ACFAS, Université McGill* (2017).

[7] COLLOBERT, R., WESTON, J., BOTTOU, L., KARLEN, M., KAVUKCUOGLU, K., AND KUKSA, P. Natural language processing (almost) from scratch. *J. Mach. Learn. Res.* 12 (Nov. 2011), 2493–2537.

<footnote n="12">12. http://www.anrs.fr/fr</footnote>
[8] CUENCA, E., SALLABERRY, A., WANG, F. Y., AND PONCELET, P. MultiStream : A Multiresolution Streamgraph Approach to Explore Hierarchical Time Series. *IEEE Transactions on Visualization and Computer Graphics*, to appear (2018).

[9] CUI, W., LIU, S., TAN, L., SHI, C., SONG, Y., GAO, Z., QU, H., AND TONG, X. TextFlow : Towards Better Understanding of Evolving Topics in Text. *IEEE Transactions on Visualization and Computer Graphics* 17, 12 (2011), 2412–2421.

[10] DE OLIVEIRA, J.-P. *Communication publique et formes de gouvernabilité contemporaines de l'Etat : le cas de l'homosexualité dans les campagnes de prévention du sida en France* (1987-2007). PhD thesis, Université Stendhal, Grenoble, 2012.

[11] DUCOFFE, M., AND PRECIOSO, F. QBDC : query by dropout committee for training deep supervised architecture. CoRR abs/1511.06412 (2015).

[12] HAVRE, S., HETZLER, E., AND NOWELL, L. ThemeRiver : Visualizing Theme Changes over Time. In *Proceedings of the IEEE Symposium on Information Visualization* (2000), IEEE, pp. 115–123.

[13] HE, L., LEE, K., LEWIS, M., AND ZETTLEMOYER, L. Deep semantic role labeling : What works and what's next. In *Proceedings of the Annual Meeting of the Association for Computational Linguistics* (2017).

[14] JOHNSON, R., AND ZHANG, T. Supervised and semi-supervised text categorization using lstm for region embeddings. In *Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48* (2016), ICML'16, JMLR.org, pp. 526–534.

[15] KALCHBRENNER, N., GREFENSTETTE, E., AND BLUNsom, P. A convolutional neural network for modelling sentences. In *ACL (1)* (2014), The Association for Computer Linguistics, pp. 655–665.

[16] KIM, Y. Convolutional neural networks for sentence classification. In *Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014*, October 25-29, 2014, Doha, Qatar, A meeting of SIGDAT, a Special Interest Group of the ACL (2014), A. Moschitti, B. Pang, and W. Daelemans, Eds., ACL, pp. 1746–1751.

[17] KUCHER, K., AND KERREN, A. Text visualization techniques : Taxonomy, visual survey, and community insights. In *Proceedings of the IEEE Pacific Visualization Symposium (PacificVis)* (2015), pp. 117–121.

[18] KUMAR, A., IRSOY, O., ONDRUSKA, P., IYYER, M., BRADBURY, J., GULRAJANI, I., ZHONG, V., PAULUS, R., AND SOCHER, R. Ask me anything : Dynamic memory networks for natural language processing. In *Proceedings of The 33rd International Conference on Machine Learning* (New York, New York, USA, 20–22 Jun 2016), M. F. Balcan and K. Q. Weinberger, Eds., vol. 48 of *Proceedings of Machine Learning Research*, PMLR, pp. 1378–1387.

[19] LIPTON, Z. C. The mythos of model interpretability. CoRR abs/1606.03490 (2016).

[20] LIU, W., WANG, Z., LIU, X., ZENG, N., LIU, Y., AND ALSAADI, F. E. A survey of deep neural network architectures and their applications. *Neurocomputing* 234 (2017), 11–26.

[21] MIKOLOV, T., KARAFIÁT, M., BURGET, L., CERNOCKÝ, J., AND KHUDANPUR, S. Recurrent neural network based language model. In *INTERSPEECH* (2010), T. Kobayashi, K. Hirose, and S. Nakamura, Eds., ISCA, pp. 1045–1048.

[22] MIKOLOV, T., SUTSKEVER, I., CHEN, K., CORRADO, G. S., AND DEAN, J. Distributed representations of words and phrases and their compositionality. In *Advances in Neural Information Processing Systems* 26, C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, Eds. Curran Associates, Inc., 2013, pp. 3111–3119.

[23] MIN, S., LEE, B., AND YOON, S. Deep learning in bioinformatics. CoRR abs/1603.06430 (2016).

[24] MUNZNER, T. *Visualization Analysis and Design*. A.K. Peters visualization series. A K Peters, 2014.

[25] NAKOV, P., RITTER, A., ROSENTHAL, S., SEBASTIANI, F., AND STOYANOV, V. Semeval-2016 task 4 : Sentiment analysis in twitter. In *Proceedings of the 10th International Workshop on Semantic Evaluation* (2016), pp. 1–18.

[26] OLSSON, F. A literature survey of active machine learning in the context of natural language processing. Tech. Rep. T2009:06, 2009.

[27] PAGANELLI, C., AND CLAVIER, V. Le forum de discussion : une ressource informationnelle hybride entre information grand public et information spécialisée. *Yasri-Labrique Eleonore. Les forums de discussion : agoras du XXIe siècle ? Théories, enjeux et pratiques discursives, L'harmattan (collection Langue et Parole)* (2011), 39–55.

[28] PAGANELLI, C., AND CLAVIER, V. S'informer via des médias sociaux de santé : quelle place pour les experts ? 141–143.

[29] PENNACCHIOTTI, M., AND GURUMURTHY, S. Investigating topic models for social media user recommendation. In *Proceedings of the 20th International Conference Companion on World Wide Web* (New York, NY, USA, 2011), WWW '11, ACM, pp. 101–102.

[30] RAMOS, J. Using tf-idf to determine word relevance in document queries, 1999.
[31] RENAHY, E., AND CHAUVIN, P. Internet uses for health information seeking: A literature review. *Revue Epidémiologique de Santé Publiqu* 54, 3 (2006), 263-275.

[32] ROSENTHAL, S., NAKOV, P., KIRITCHENKO, S., MOHAMMAD, S., RITTER, A., AND STOYANOV, V. Semeval-2015 task 10: Sentiment analysis in twitter. In *Proceedings of the 9th International Workshop on Semantic Evaluation* (2015), pp. 451–463.

[33] SCHMIDHUBER, J. Deep learning in neural networks: An overview. *Neural Networks* 61 (2015), 85–117. Published online 2014; based on TR arXiv:1404.7828 [cs.NE].

[34] SHWARTZ-ZIV, R., AND TISHBY, N. Opening the black box of deep neural networks via information. *CoRR abs/1703.00810* (2017).

[35] SOCHER, R., PERELYGIN, A., WU, J. Y., CHUANG, J., MANNING, C. D., NG, A. Y., AND POTTS, C. Recursive deep models for semantic compositionality over a sentiment treebank. In *EMNLP* (2013), vol. 1631, p. 1642.

[36] SRIVASTAVA, R. K., GREFF, K., AND SCHMIDHUBER, J. Training very deep networks. In *Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2* (Cambridge, MA, USA, 2015), NIPS’15, MIT Press, pp. 2377–2385.

[37] SUKHBAATAR, S., SZLAM, A., WESTON, J., AND FERGUS, R. End-to-end memory networks. In *Advances in Neural Information Processing Systems* 28, C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, Eds. Curran Associates, Inc., 2015, pp. 2440–2448.

[38] SUN, G., WU, Y., LIU, S., PENG, T.-Q., ZHU, J. H., AND LIANG, R. EvoRiver: Visual Analysis of Topic Coopetition on Social Media. *IEEE Transactions on Visualization and Computer Graphics* 20, 12 (2014), 1753–1762.

[39] VINYALS, O., KAISER, L. U., KOO, T., PETROV, S., SUTSKEVER, I., AND HINTON, G. Grammar as a foreign language. In *Advances in Neural Information Processing Systems* 28, C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, Eds. Curran Associates, Inc., 2015, pp. 2773–2781.

[40] WANG, S., J.PAUL, M., AND DREDZE, M. Exploring health topics in chinese social media: an analysis of sina weibo. *AAAI Workshop on the World Wide Web and Public Health Intelligence* 23 (2014), 20–23.

[41] WANG, Y., AGICHTEIN, E., AND BENZI, M. Tmlda: Efficient online modeling of latent topic transitions in social media. In *Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining* (New York, NY, USA, 2012), KDD ’12, ACM, pp. 123–131.

[42] WU, Y., LIU, S., YAN, K., LIU, M., AND WU, F. OpinionFlow: Visual Analysis of Opinion Diffusion on Social Media. *IEEE Transactions on Visualization and Computer Graphics* 20, 12 (2014), 1763–1772.

[43] ZENG, Q. T., AND TSE, T. Viewpoint paper: Exploring and developing consumer health vocabularies. *JAMIA* 13, 1 (2006), 24–29.

[44] ZHAN, Y., LIU, R., LI, Q., LEISCHOW, S., AND ZENG, D. Identifying topics for e-cigarette user-generated contents: a case study from multiple social media platforms. *J Med Internet Res* 19, 1 (2017), e24.

[45] ZHU, M., ZHANG, Y., CHEN, W., ZHANG, M., AND ZHU, J. Fast and accurate shift-reduce constituent parsing, 2013.
<figure><img src="image_88.png" /></figure>
# Optimisation en temps réel de la gestion des convergences ferroviaires

Valentina Pozzoli¹

François Ramond¹

¹SNCF Innovation et Recherche
40, avenue des Terroirs de France
75611 Paris Cedex

Valentina.Pozzoli@sncf.fr
François.Ramond@sncf.fr

## Résumé

L'exploitation ferroviaire en zone dense est une tâche complexe. La densité des circulations provoque une propagation très rapide des retards, même de petite amplitude. Afin de prendre des décisions d'exploitation rapides et optimales il est nécessaire de se doter d'outils d'aide à la décision performants.

Dans cet article, nous présentons un système d'aide à la gestion optimale en temps réel des zones de convergences ferroviaires, afin d'améliorer la ponctualité des voyageurs de la ligne. Nous détaillons les enjeux liés au projet, ainsi que les choix de modélisation et l'architecture du prototype. Le système a été testé avec succès sur un site pilote en Île-de-France : nous montrons les résultats de ces expérimentations et donnons les perspectives pour la suite du projet.

## Mots Clef

Aide à la décision, Optimisation, Exploitation ferroviaire, Algorithmes en temps réel, Convergences ferroviaires

## Abstract

Railway traffic management in mass transit system is a complex task. Trains run so frequently and so close to each other that delays propagate very fast. Operators have to take efficient decisions depending on a multitude of factors, that impact a large number of trains, and thus of passengers. Artificial intelligence methods come in help in the decision process.

In this paper, a real-time decision-support tool for the optimal management of junction areas is presented. It proposes the best order of trains to run through a junction, such that the passenger punctuality is maximized. Details are given on the modelling and the architecture of the tool, as well as on the goals and ambitions of the project. The results of promising experiments on a case-study on a junction in a Parisian area are presented.

## Keywords

Decision-support, Optimization, Traffic management, Mass transit, Real-time algorithms, Railway junctions

## 1 Introduction

L'exploitation ferroviaire en zone dense, où la fréquence des trains est élevée et le nombre de voyageurs important, est un vrai défi dont l'enjeu principal est la qualité du service offert aux voyageurs. L'optimisation de l'exploitation ferroviaire relève de plusieurs facteurs avec des échéances temporelles différentes. En amont de la production se situent, par exemple, la conception de plans de transport robustes et résilients, la maintenance des voies et du matériel, l'affectation des conducteurs et la gestion des rames. En gestion opérationnelle, la mise en œuvre de mesures de régulation efficaces est nécessaire afin d'optimiser la production : changements de la desserte ou des voies utilisées, adaptation d'offre, etc. La gestion des zones de convergence figure parmi ces mesures de régulation.

Les zones de convergences sont des endroits du réseau ferroviaire où deux ou plusieurs voies se réunissent. L'exemple le plus simple, qui sera étudié au cours de cet article, est montré en Figure 1. La gestion des zones de convergence consiste à choisir l'ordre de passage des trains lors que deux trains de deux branches différentes s'apprêtent à rentrer dans la zone de convergence. Bien que la thématique d'optimisation de l'ordre de passage existe pour toutes zones de convergence, en zone dense le choix est particulièrement impactant : en effet, dans un réseau dense les retards se propagent facilement sur les trains suivants. Chaque décision de régulation peut donc avoir un impact sur un grand nombre de trains, et de conséquence sur un nombre important de voyageurs. Ces décisions dépendent de nombreux paramètres : par exemple, les retards des trains, leur desserte, le nombre de passagers dans les trains et sur les quais. En plus, les choix doivent être pris rapidement par le régulateur : pour ces raisons il est nécessaire de se doter d'outils d'aide à la décision performants qui puissent venir en support du travail des régulateurs.

En Île-de-France, SNCF Mobilités, via son activité Transilien, et RATP sont les principaux opérateurs de transport ferroviaire. Ils opèrent par le compte d'Île-de-France Mobilité, qui définit également les objectifs de performance des opérateurs de transport. Transilien fait circuler 6200 trains chaque jour, qui transportent au quotidien 3 millions de voyageurs, nombre qui connait une augmentation de 3% par an en moyenne (source Transilien). L'amélioration de la 'ponctualité des
voyageurs', premier élément pour la satisfaction des clients, est l'objectif principal de Transilien et le critère utilisé par Île-de-France Mobilité pour évaluer la performance d'une ligne.

Dans ce contexte, la gestion des zones de convergence, est particulièrement complexe et impactant. En effet, ces zones sont spécialement sollicitées car les trains des deux branches doivent y passer : la fréquence de passage peut aller jusqu'à 32 trains par heure. L'ordonnancement des trains dans une zone de convergence peut être modifié par les opérateurs. Bien que les horaires théoriques indiquent l'ordre de passage des trains à une zone de convergence, cet ordre peut être remis en cause par les aléas : la décision optimale doit considérer l'impact de ce choix sur toute la ligne d'un point de vue des voyageurs concernés.

La Direction de l'Innovation et de la Recherche de SNCF a développé pour Transilien un outil d'aide à la gestion des zones de convergence en temps réel. Cet outil préconise l'ordre de passage des trains à la convergence permettant de maximiser la performance globale de la ligne, définie par le critère de 'ponctualité des voyageurs'.

L'article est organisé de la façon suivante : la Section 2 est consacrée à une présentation succincte des travaux déjà existants sur le sujet ; la Section 3 détaille le critère d'optimisation et les enjeux du projet, la Section 4 décrit la modélisation du problème et l'architecture de l'outil ; la Section 5 présente les résultats de l'expérimentation menée dans un contexte opérationnel sur un site pilote ; enfin, des conclusions et perspectives sont exposées en Section 6.

<figure><img src="image_89.png" /><figcaption>Figure 1 - Schéma d'une zone de convergence</figcaption></figure>

## 2 Travaux antérieurs

La gestion du trafic en temps réel est un problème largement abordé dans la littérature. Une revue extensive des approches pour réduire les conséquences des incidents est présentée dans [1], en distinguant entre petits aléas et perturbations importantes. Les actions à mettre en place sont différentes dans les deux cas, et incluent la replanification d'itinéraires, la gestion des correspondances, la replanification des engins ou des conducteurs. Au niveau des adaptations du plan de transport en temps réel, les stratégies utilisées en zone dense sont la rétention d'un train en gare, l'ajustement de la vitesse, le changement de desserte, et l'ordre de passage en certains points du réseau. L'ordonnancement des trains à une convergence est un cas particulier de cette dernière stratégie de replanification.

L'article [2] résume les modèles existants dans la planification et replanification ferroviaire, dont les décisions d'ordonnancement à une convergence, ou de replanification d'itinéraires. Une autre revue des modèles de contrôle de trafic en temps réel est proposée par [3].

L'optimisation de l'exploitation du point de vue des voyageurs, et non pas que des retards des trains, est traitée dans plusieurs articles : par exemple dans [4], les horaires d'arrivée et de départ des métros sont choisis afin de minimiser les temps d'atteintes et de trajet, ainsi que la congestion; [5] proposent un algorithme de replanification qui minimise l'insatisfaction des voyageurs.

Plusieurs articles traitent spécifiquement le problème de gestion des convergences ferroviaires : [6] propose un modèle d'ordonnancement optimal des trains aux convergences afin de minimiser une somme pondérée des retards des trains aux gares desservies. Ce modèle est résolu grâce à un algorithme à évolution différentielle et, sur les instances de test, permet de réduire les retards par apport à une stratégie du type premier entré, premier sorti. Un modèle de replanification en temps réel qui inclut l'optimisation de la vitesse des trains afin de minimiser les retards est proposé dans [7]. Une comparaison entre différentes stratégies de résolution des conflits aux convergences est décrite dans [8]: premier arrivé premier servi, priorité selon le type de train, et minimisation du nombre et de la durée des retards grâce à une heuristique. Les trois scénarios sont évalués grâce à des simulations.

Les travaux présentés dans cet article proposent un approche différent car centré sur une gestion optimale du point de vue de la performance globale de la ligne, en considérant le point de vue des voyageurs, et non pas que le retard des trains.
## 3 Critère d'optimisation

L'objectif de nos travaux est d'optimiser la gestion d'une zone de convergence afin de maximiser la performance globale de la ligne.

Aujourd'hui, en cas de conflit dans une zone de convergence, la décision d'ordonnancement des trains est prise au cas par cas grâce à l'expertise humaine du régulateur, et dépend principalement des retards de deux trains en conflit, ainsi que de leurs missions. En cas de perturbation, le régulateur a une charge de travail élevée et doit prendre des décisions rapides qui ont un impact majeur sur toute la ligne. L'idée est de venir en aide aux régulateurs, en leur fournissant en outil qui puisse à la fois les décharger d'une partie de leur charge cognitive, leur donner des informations pour mieux analyser la situation, et leur proposer le meilleur ordonnancement du point de vue de la performance globale de la ligne.

Un des principaux indicateurs de la performance globale d'une ligne est appelé 'ponctualité voyageurs'. Ce critère mesure le nombre de voyageurs arrivés à leur gare de destination moins de 5 minutes après leur heure d'arrivée théorique. Il est utilisé pour évaluer la qualité de service de SNCF par Île-de-France Mobilités, et c'est le critère d'optimisation choisi dans l'outil d'aide à la gestion des zones de convergence.

Pour calculer la ponctualité voyageurs, des données statistiques sur le nombre de voyageurs pour chaque couple origine-destination par heure sont utilisées afin d'affecter les voyageurs aux différents trains, en se basant sur les horaires théoriques. Les données sur le nombre de voyageurs sont issues de comptages manuels des voyageurs effectués régulièrement sur les lignes concernées. Grâce à ces données et aux horaires théoriques des trains, il est possible de calculer l'horaire théorique d'arrivée de chaque passager à la gare d'origine et à la gare de destination. Une fois les trains circulés, les horaires réels d'arrivée des voyageurs à destination sont calculés grâce aux horaires réels de passage des trains par les différentes gares. On considère que chaque voyageur arrive en gare à l'horaire théorique prévu, et monte ensuite dans le premier train qui dessert sa destination. Par la suite, on calcule l'indicateur de ponctualité voyageurs comme le pourcentage de voyageurs arrivant à la gare de destination avec moins de 5 minutes de retard par rapport à l'horaire théorique.

L'indicateur de ponctualité voyageurs a pour but de s'affranchir de la simple notion de retard du train pour représenter la perception du voyageur. En effet, en zone dense, où la fréquence des trains est élevée, l'horaire théorique du train réellement emprunté a peu d'importance pour les voyageurs par rapport à d'autres paramètres tels que le temps d'atteinte en gare et le temps de trajet.

Le critère de ponctualité voyageurs diffère de celui du simple retard des trains pour plusieurs aspects :

- Le retard d'un train transportant beaucoup de voyageurs a plus d'impact sur le critère de

ponctualité voyageurs par rapport au même retard d'un train moins chargé.

- Il est possible d'avoir des voyageurs en retard dans un train à l'heure (par exemple, si un train est supprimé et que celui d'après et à l'heure, les voyageurs qui voulaient prendre le premier train seront en retard).

- Il est également possible d'avoir des voyageurs à l'heure dans un train en retard (notamment si un train roule à l'horaire du train suivant, donc en retard, les voyageurs souhaitant prendre le deuxième train pourront monter dans le premier est être à l'heure).

Ces aspects rendent difficile pour les opérateurs une prise de décision en fonction du critère de ponctualité voyageurs, ce qui justifie le besoin d'un outil d'aide à la décision. En effet, selon le choix d'ordonnancement les voyageurs pourront être affectés à des trains différents, et le choix peut impacter les retards des trains suivants (et donc l'horaire d'arrivée à destination des voyageurs qui voudrait monter dans ces trains). La présence de missions directes et de missions omnibus, avec des temps de parcours différents, complexifie d'avantage la compréhension des impacts du choix sur la ponctualité voyageurs.

## 4 Modélisation du problème et architecture

La Direction de l'Innovation et de la Recherche a développé un outil visant à aider le choix d'ordonnancement des trains du point de vue de la ponctualité voyageurs. L'outil calcule la ponctualité voyageurs associée aux différents scénarios d'ordonnancement des trains en se basant sur un flux de géolocalisation des trains en temps réel. Les résultats sont restitués via une interface homme-machine (IHM). L'architecture du projet est synthétisée en Figure 2.

En entrée nous avons des données structurelles et des données temps réel. Les données structurelles incluent la modélisation du réseau et des paramètres de circulations tels que les espacements minimaux entre les trains, le plan de transport théorique et les données statistiques sur le nombre des voyageurs par heure par couple origine/destination. Certaines de ces données sont fixes pour un calcul donné, comme la modélisation du réseau, d'autre sont journalières, comme le plan de transport théorique. La modélisation du réseau inclut des informations sur les zones aux alentours de la convergence (voir Figure 3). En particulier, il contient une définition de la zone de décision, c'est-à-dire la zone en amont de la convergence où les trains doivent se trouver pour qu'il soit possible et pertinent d'effectuer un réordonnancement.

Les données temps réel incluent les messages de géolocalisation des trains et les messages déclenchés par les actions de régulation telles que les adaptations de l'offre.
La localisation des trains se fait grâce à un système de balises placées sur les rails : le passage d'un train sur une balise déclenche un message de géolocalisation. Cela signifie que la connaissance de la position des trains n'est pas connue en continue, mais de façon discrète : une fois le train passé sur une balise, il n'est pas possible de connaitre sa position ou sa vitesse jusqu'au passage par la balise suivante.

<figure><img src="image_90.png" /><figcaption>Figure 2 - Architecture du logiciel</figcaption></figure>

Toutefois, une estimation de la position d'un train à un instant donné est possible en se basant sur l'horaire de passage à la dernière balise, sur les temps de trajet théorique et sur la position des autres trains sur le réseau.

À la réception de chaque nouveau message de localisation d'un train, l'outil met à jour la position des trains dans le réseau, identifie les différentes possibilités d'ordonnancement pour les trains concernés et simule l'impact de chaque possibilité sur les horaires des trains de l'instant présent jusqu'à la fin de la journée. Cela permet au module de ponctualité de

calculer la ponctualité voyageurs pour chaque scénario d'ordonnancement, et d'identifier le meilleur choix.

Tout d'abord le module de gestion des calculs reçoit les données de localisation et identifie les trains présents dans les différentes zones du réseau montrée en Figure 3. Les trains dans la 'zone de décision' sont potentiellement concernés par la décision d'ordonnancement. Bien que plusieurs trains de chaque branche puissent être dans la zone de décision à un instant donné, nous considérons que le réordonnancement n'est possible qu'entre les deux les plus proches de la convergence. Deux situations sont donc à examiner (en se référant à la Figure 3) : le train A passe avant le train B, et le train B passe devant le train A.

Le module de gestion des calculs transmet au simulateur de trafic l'information des trains concernés par le réordonnancement, ainsi que l'information sur le dernier message de localisation reçu. Le simulateur met à jour les positions des trains grâce au message de localisation, et une simulation est ensuite lancée pour chacun de scénarios d'ordre de passage. Ces simulations permettent d'évaluer l'impact du choix d'ordonnancement sur tous les trains de la ligne. La simulation est menée grâce à un simulateur de trafic développé à la Direction de l'Innovation et de la Recherche de la SNCF [9]. Le simulateur prend en entrée les horaires théoriques et les horaires réels de localisation des trains pour calculer les circulations futures des trains du début jusqu'à la fin de la journée.

Le simulateur retourne l'information sur l'estimation des horaires de passage à chaque gare pour tous les trains de la ligne. Le module de calcul de la ponctualité utilise cette information pour évaluer la ponctualité voyageurs telle que décrite dans la Section 3. Il retourne la valeur de l'indicateur de ponctualité voyageurs pour les deux scénarios d'ordonnancement (A passe devant B et B passe devant A).

Les informations sont par la suite transmises au module de gestion des calculs qui les élabore et les transmette à

<figure><img src="image_91.png" /><figcaption>Figure 3 - Schéma des zones aux alentours de la convergence</figcaption></figure>
l'IHM. L'interface a été élaborée en concertation avec des experts en design et en sciences cognitives, ainsi qu'avec les utilisateurs, afin de donner les indicateurs pertinents de façon simple et immédiate. Les enjeux principaux dans l'élaboration de l'interface ont été d'une part la nécessité d'expliquer le choix proposé par l'outil, et d'autre part de ne pas surcharger l'utilisateur avec trop d'informations. Cela est particulièrement crucial dans un contexte opérationnel où la charge de l'opérateur est élevée, notamment en cas de perturbations.

## 5 Cas d'étude et expérimentations

Afin d'éprouver la qualité des préconisations de l'outil pour l'amélioration de la ponctualité voyageurs, nous avons mené des expérimentations sur le périmètre de la ligne L et du RER A (voir Figure 4). L'outil propose en continu une préconisation d'ordre de passage à la convergence pour les deux trains dans la zone de prise de décision: le prochain train au départ de Poissy et le premier train en aval de la gare de Conflans Fin d'Oise. Ces trains sont marqués en rouge dans la Figure 4. Par rapport au schéma dans la Figure 3, il n'y a pas de zone amont pour les trains en provenance de Poissy, et le train est en zone de décision jusqu'à la détection de son départ de la gare d'origine.

<figure><img src="image_92.png" /><figcaption>Figure 4 – Schéma de la zone de convergence étudiée</figcaption></figure>

Les expérimentations se sont déroulées pendant trois semaines sur la pointe du matin, de 7:30 à 9:30, à la présence constante d'un membre de l'équipe projet. Dans une première phase, nous avons suivi le travail des régulateurs sans imposer la mise en place des préconisations de l'outil. Cela a permis d'évaluer la cohérence et l'apport de l'outil par rapport à la situation existante. Ensuite, une application systématique des préconisations a été demandée : cela a permis d'évaluer la qualité des préconisations de l'outil dans un contexte opérationnel.

### Qualité des prévisions par rapport au réalisé

Nous nous sommes d'abord intéressés à l'étude de la qualité des prévisions des positions des trains par rapport au réalisé.

Pour cela, nous avons calculé les écarts entre les positions simulées et réalisées des trains sur des différentes plages horaires de 0 à 30 minutes à partir du moment de préconisation. La distribution de ces écarts, basée sur 1500 simulations, est montrée en Figure 5. Bien évidemment, nous ne pouvons à chaque fois que

confronter le scénario correspondant au réordonnancement réalisé.

L'erreur moyenne sur la position de chaque train entre 0 et 5 minutes après la simulation est de 5 secondes. Cette erreur devient plus important le plus on s'éloigne du moment de la simulation, tout en restant acceptable pour nos applications. Par exemple, il est inférieur à 40 secondes en moyenne pour le calcul des positions des trains entre 25 et 30 minutes après la simulation, bien que l'écart type soit plus important. L'augmentation de l'écart-type est due aux aléas ou incidents qui peuvent apparaître sur la ligne, et dont le simulateur ne peut pas avoir connaissance au moment du déclanchement de la simulation.

Nous pouvons noter que les sous-estimations des retards (partie droite du graphe) sont plus importantes que les sure estimations. Cette différence est normale : le simulateur ne prévoit pas la possibilité qu'un train puisse rattraper son retard, car cela signifierait un temps de parcours plus court par rapport au temps de parcours théorique. Il y a tout de même des cas où le simulateur peut surestimer un retard : notamment si ce retard est dû à l'espacement avec un train qui sera au final supprimé.

La qualité de la simulation est très bonne par rapport à la précision requise pour nos usages, et nous conforte sur la qualité des préconisations données par l'outil.

<figure><img src="image_93.png" /><figcaption>Figure 6 – Pourcentage de réordonnancements préconisés vs réalisés</figcaption></figure>

### Réordonnancements : effectués et préconisés

Nous avons par la suite analysé les réordonnancements effectués par le régulateur par rapport aux réordonnancements préconisés par l'outil. Les résultats sont montrés en Figure 6.

Nous retrouvons un accord entre la préconisation de l'outil et la décision de l'opérateur dans le 84% des cas (partie bleu et partie verte du graph). Cet accord montre que les préconisations de l'outil sont globalement cohérentes, bien qu'une marge
d'optimisation importante reste possible : 11% des réordonnancements proposés ne sont pas effectués, et 5% des réordonnancements effectués n'étaient pas préconisés par l'outil. La cause principale de cette discordance est à rechercher dans la complexité du critère de ponctualité voyageurs : en effet, la plupart de réordonnancements non effectués (partie jaune) ne réduisait pas les retards des trains. Ce dernier critère est plus facile à estimer par l'opérateur par rapport au critère de ponctualité voyageurs. D'autres raisons de désaccord entre l'outil et la réalité incluent l'utilisation des voies supplémentaires afin de décharger la zone de convergences, ou la nécessité de faire passer un train en premier pour des sujets de réutilisation des rames ou de réaffectation des conducteurs. Certains de ces aspects pourront être intégrés par des versions futures de l'outil, bien que la disponibilité en temps réel des données nécessaires à l'implémentation de ces fonctionnalités reste pour l'instant un point bloquant.

## Analyse de la phase d'application systématique des préconisations de l'outil

L'objectif est de comprendre si l'application des préconisations a amélioré la ponctualité voyageurs, comme prédit par l'outil. Pour cela, nous avons analysé dans le détail les situations où l'opérateur a suivi la préconisation de l'outil, mais où il aurait pris la décision opposée en dehors du cadre des expérimentations, sans l'outil à disposition. Un exemple est analysé en Figure 7, qui montre les Graphiques Espace-Temps (GET) pour les deux scénarios d'ordonnancement des trains. Les GET affichent en abscisse les horaires et en ordonnée les positions sur la ligne. Les deux trains A et B viennent de deux branches différentes, mais nous affichons sur le graphique la position par rapport à la convergence.

La décision a des impacts sur les trains suivants, mais nous ne montrons par simplicité que les deux trains réordonnancés.

Le scénario réalisé est celui du réordonnancement : B passe devant A. La simulation prévoit les positions des trains avec une bonne précision par rapport au réalisé. À noter qu'à chaque fois nous manquons d'informations sur la qualité de la simulation par rapport au scénario non retenu.

<figure><img src="image_94.png" /><figcaption>Figure 7 – GET pour le scénario A passe devant B et B passe devant A (scénario retenu)</figcaption></figure>

Une analyse de chaque groupe de voyageurs impacté par la décision a confirmé l'amélioration de la ponctualité voyageurs par rapport au scénario non préconisé.

## Estimation du gain en ponctualité voyageurs

Une estimation solide du gain en ponctualité voyageurs demanderait l'application systématique des préconisations de l'outil sur une période de plusieurs semaines, afin d'analyser si la ponctualité est

<figure><img src="image_95.png" /><figcaption>Figure 5 - Distribution des écarts entre réalisé et simulé sur des plages horaires de 5 minutes entre 0 et 30 minutes après la préconisation</figcaption></figure>
significativement améliorée par rapport à une période de référence. Cela n'était pas possible dans le cadre de cette expérimentation. Nous nous sommes contentés d'effectuer une estimation moins fine en faisant une simple somme des gains en ponctualité générés par un suivi régulier de l'outil : grâce à une application systématique des préconisations, il serait possible d'éviter la perte en ponctualité liée aux réordonnancements non préconisés et réalisés (partie rouge du graphe en Figure 6) et de profiter du gain générés par l'application des réordonnancements préconisés mais non réalisés (partie jaune du graphe en Figure 6). L'estimation montre qu'un nombre important aujourd'hui en retard pourrait arriver à l'heure en suivant les ordonnancements préconisés par l'outil.

## Retours des utilisateurs

Suite aux expérimentations, les utilisateurs ont complété un questionnaire de retour. Les questions visaient à comprendre le ressenti de leur travail quotidien, en particulier pour ce qui concerne la gestion de la convergence, en terme de difficulté et charge cognitive. Des avis ont été demandés sur les expérimentations et l'outil : confiance dans les préconisations, pertinence des informations présentée, etc. Les opérateurs ont donné un avis positif sur les préconisations de l'outil et les informations montrées au niveau de l'interface. La conduite du changement reste à travailler pour permettre l'utilisation de ce type d'algorithmes dans un contexte opérationnel. Malgré les nombreux échanges avec les utilisateurs pendant la conception du prototype, il reste difficile de changer des pratiques d'exploitations consolidées, notamment dans le cadre d'une expérimentation d'une durée de quelques semaines.

# 6 Conclusions et perspectives

Dans cet article, nous avons présenté un outil d'aide à la gestion des zones de convergence ferroviaire, et son application à un cas de test.

L'outil s'est montré pertinent sur plusieurs aspects : aider les décisions des opérateurs au quotidien, en leur fournissant des éléments objectifs pour une prise de décision rapide et optimale ; réduire la variabilité liée au facteur humain, en rendant l'exploitation plus homogène d'un jour à l'autre ; améliorer la ponctualité voyageurs, objectif primaire de Transilien. Suite à ces résultats, le passage en industrialisation du prototype est prévu.

Du point de vue du projet de recherche, des améliorations sont envisageables pour traiter des cas plus complexes : par exemple, pour aider la gestion des lignes avec des convergences multiples, ou pour intégrer d'autres décisions en temps réel comme des adaptations de l'offre.

## Bibliographie

[1] V. Cacchiani, D. Huisman, M. Kidd, L. Kroon, P. Toth, L. Veelenturf, et J. Wagenaar (2014). An overview of recovery models and algorithms for real-time railway rescheduling. Transportation Research Part B: Methodological, 63, pages 15-37.

[2] A. Toletti, M. Laumanns, P. Grossenbacher et U. Weidmann (2015). Meeting functional requirements for real-time railway traffic management with mathematical model. Advanced Systems in Public Transport Conference.

[3] F. Corman and L. Meng (2013). A review of online dynamic models and algorithms for railway traffic control. Intelligent Rail Transportation (ICIRT), 2013 IEEE International Conference, pages 128-133.

[4] C. J. Goodman et S. Murata (2001). Metro traffic regulation from the passenger perspective. Proceedings of the Institution of Mechanical Engineers, Part F: Journal of Rail and Rapid Transit, Vol 215, Issue 2, pages 137-147.

[5] N. Tomii, Y. Tashiro, N. Tanabe, C. Hirai et K. Muraki (2005). Train rescheduling algorithm which minimizes passengers' dissatisfaction. Ali M., Esposito F., Innovations in Applied Artificial Intelligence. IEA/AIE. Lecture Notes in Computer Science, vol 3533. Springer, Berlin, Heidelberg

[6] L. Chen, F. Schmid, M. Dasigi, B. Ning, C. Roberts, and T. Tang. (2010). Real-time train rescheduling in junction areas. Proceedings of the Institution of Mechanical Engineers, Part F: Journal of Rail and Rapid Transit, 224(6), pages 547-557.

[7] A. Galapitage, A. R.Albrechta, P. Pudneyab, X. Vua et P. Zhoua (2017). Optimal real-time junction scheduling for trains with connected driver advice systems. Journal of Rail Transport Planning & Management.

[8] S. Van Thielen, S. Burggraeve, and P. Vansteenwegen (2015). "Optimal train rescheduling after conflict detection". Conference on Advanced Systems in Public Transport (CASPT)

[9] J. Damay, A. Boillot, (2014). "An efficient macroscopic railway system simulator". 20th Conference of the International Federation of Operational Research Societies (IFORS).

## Remerciements

Ces travaux ont été financés par SNCF Transilien et ont été menés par la Direction de l'Innovation de la SNCF. Nous tenons à exprimer nos remerciements à toutes personnes impliquées dans le projet : le comité de pilotage, le Lab Mass Transit, la DSI de SNCF Mobilité, les opérateurs et les responsables du centre opérationnel où nous avons testé l'outil, les équipes de développements du logiciel, les fournisseurs des données de géolocalisation et de plans de transport.
<figure><img src="image_96.png" /></figure>
# Trois approches pour classifier les données du web des données

Justine Reynaud

Yannick Toussaint

Amedeo Napoli

Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

prénom.nom@loria.fr

## Résumé

Dans cet article, nous nous intéressons au processus de classification de données relationnelles issues du web des données. Nous disposons d'un ensemble d'objets entre lesquels il existe des relations. Ces objets appartiennent à une ou plusieurs classes. Celles-ci sont définies en extension, et nous cherchons à construire une description en extension en s'appuyant sur les relations des objets qui les composent. Pour cela, nous employons trois approches : les règles d'association qui s'appuient sur l'Analyse de Concepts Formels (FCA), les redescriptions et les règles de traduction qui s'appuient sur la Longueur de Description Minimale (MDL). À partir d'expérimentations sur DBpedia, nous discutons les spécificités et la complémentarité de ces trois approches. Nous montrons que les règles d'association sont les plus exhaustives tandis que les règles de traduction ont une meilleure couverture des données. Les redescriptions pour leur part, sont les règles les plus faciles à appréhender et interpréter.

## Mots Clef

Données relationnelles, Analyse de Concepts Formels, Fouille de redescriptions, DBpedia.

## Abstract

In this paper we study a classification process on relational data that can be applied to the web of data. We start with a set of objects and relations between objects, and extensional classes of objects. We then study how to provide a definition to classes, i.e. to build an intensional description of the class, w.r.t. the relations involving class objects. To this end, we propose three different approaches based on Formal Concept Analysis (FCA), redescription mining and Minimum Description Length (MDL). Relying on some experiments on RDF data from DBpedia, where objects correspond to resources, relations to predicates and classes to categories, we compare the capabilities and the complementarity of the three approaches. This research work is a contribution to understanding the connections existing between FCA and other data mining formalisms which are gaining importance in knowledge discovery, namely redescription mining and MDL.

## Keywords

Relational data, Formal Concept Analysis, Redescription mining, DBpedia.

# 1 Introduction

Dans cet article, nous nous intéressons à la possibilité de découvrir des définitions dans les données RDF issues du web des données. Ces définitions peuvent être réutilisées dans la conception de bases de connaissances (KBs) ou dans l'enrichissement de KBs préexistantes. Étant donné l'immense quantité de données du web des données, il s'agit d'un enjeu majeur.

Le problème est le suivant : nous disposons d'un ensemble d'objets connectés par des relations, comme une ABox en logique de descriptions (DL) (Baader et al., 2003). L'objectif est de classifier ces objets en fonction des relations dans lesquelles ils sont impliqués.

Les objets qui partagent des éléments communs appartiennent à une même classe. Ce partage peut être exact — les éléments sont identiques — ou approximatif — les éléments sont similaires. Finalement, nous obtenons un ensemble de classes organisées selon un ordre partiel, et les descriptions associées à ces classes. Ces descriptions sont nécessaires afin de construire les définitions des différentes classes. Les définitions sont considérées comme des conditions nécessaires (NC) et suffisantes (SC) pour classifier de nouveaux objets. Si $x$ est une instance de la classe Rouge alors $x$ a la couleur rouge (NC), et inversement, si $x$ a la couleur rouge alors $x$ est une instance de la classe Rouge (SC).

Pour poursuivre l'analogie avec les DLs, l'idée dans cet article est de construire et d'appliquer des règles d'induction de la forme « $si r(x,y) et y:C$ alors $x:\exists r.C$ ». Cela signifie que, étant données y une instance de la classe C et $r$ une relation telle que $r(x,y)$, alors $x$ appartient à une classe, disons D, dont la description comprend $\exists r.C$. C'est-à-dire que les instances de D sont reliées à au moins une instance de C par la relation $r$. Nous utilisons ce type de règles pour construire les définitions des classes. Ces définitions sont de la forme $C_i \equiv e_1 \sqcap e_2 \sqcap \dots \sqcap e_n$ où $e_j$ est une expression de la forme $\exists r.C_j$. Notre travail se divise en trois tâches principales, à savoir (i) préparer les données, (ii) découvrir les définitions, (iii) évaluer la qualité de ces
<figure><img src="image_97.png" /><figcaption>FIGURE 1 – Exemple de données relationnelles et les triplets associés.</figcaption></figure>

définitions. Nous nous appuyons ici sur trois approches, les règles d'association, la fouille de redescriptions et la découverte de règles de traduction.

Cet article est dans la continuité de travaux de recherche sur la découverte de définitions dans le web des données. Son originalité est de comparer trois approches qui ne s'appliquent pas sur les mêmes principes mais qui s'avèrent être complémentaires au vu des résultats de nos expérimentations. À notre connaissance, il s'agit du premier article où une telle comparaison est proposée à la fois à un niveau théorique et à un niveau expérimental.

L'article est organisé comme suit : dans la section 2, nous présentons la nature des données sur lesquelles nous travaillons et les processus de classification dans le web des données. Dans la section 3, nous détaillons les trois approches de classification et leurs applications. La section 5 présente les expériences qui ont été menées ainsi que l'évaluation des règles obtenues. Enfin, la section 6 présente une discussion ainsi que les pistes de recherches futures avant la conclusion section 7.

# 2 Représentation des données

## 2.1 Web des Données

Dans cette section, nous présentons les données issues du Web des Données (LOD) que nous considérons. Le LOD peut être vu comme un ensemble de KBs interconnectées. Une KB est composée de deux éléments : une TBox qui définit son *schema* et une ABox qui introduit les individus et leurs relations. L'unité de base d'une KB est le triplet RDF, noté $\langle s, p, o \rangle$, qui encode une assertion sous la forme sujet-prédicat-objet. Les différentes composantes d'un triplet peuvent être des ressources *U* identifiées de manière unique, des littéraux *L* (chaîne de caractères, numérique, date, ...) ou des nœuds anonymes *B* (assimilables à une variable existentiellement quantifiée), de telle sorte que $\langle s, p, o \rangle \in (B \cup U) \times U \times (B \cup U \cup L)$. Dans cet article, nous nous restreignons aux triplets composés uniquement de ressources, c'est-à-dire tels que $\langle s, p, o \rangle \in U \times U \times U$. Les ressources peuvent faire référence à n'importe quel objet ou abstraction et sont identifiées par une URI (*Uniform Resource Identifier*). Une URI est une adresse composée de deux parties. La première partie est l'espace de nom (*namespace*) qui indique de quelle KB viennent les ressources. La seconde partie donne un nom à la ressource au sein de cette KB.

La figure 1, présente un exemple de données relationnelles

et l'ensemble de triplets correspondant. Le préfixe ex: correspond à un namespace créé pour notre exemple, tandis que le préfixe rdf: correspond à un namespace préexistant. rdf:type est la relation d'instanciation. Ainsi le triplet $\langle ex:x_0 rdf:type ex: C_0 \rangle$ indique que $x_0$ est une instance de la classe $C_0$.

Le LOD peut être interrogé grâce aux requêtes SPARQL. Par exemple, la requête `SELECT ?x WHERE { ?x rdf:type ex:C0}` retourne toutes les instances de $C_0$. Si l'on prend les données de la figure 1, seul ex:x0 est retourné.

## 2.2 Analyse de Concepts Formels

Nous utilisons ici l'Analyse de Concepts Formels (FCA) de Ganter et Wille (1999) pour présenter et comparer les différentes approches. Étant donné un ensemble *G* d'entités<fnref n="1" />, un ensemble *M* d'attributs et une relation binaire $I \subseteq G \times M$, $(G, M, I)$ est un contexte formel. L'expression $gIm$ s'interprète comme « l'entité *g* possède l'attribut *m*». Les correspondances de Galois (notées .') pour un ensemble d'entités $X \subseteq G$ et un ensemble d'attributs $Y \subseteq M$ sont définies comme suit :

$$X' = \{m \in M \mid \forall x \in X, xIm\} \text{ et}$$

$$Y' = \{g \in G \mid \forall y \in Y, gIy\}.$$

À partir des données RDF, nous construisons un contexte formel dont les entités sont les sujets des triplets. Les attributs sont les paires (prédicat, objet) issues des triplets. Nous distinguons deux types d'attributs : des descriptions et des classes. Le premier ensemble d'attributs, dénoté *C*, est composée des paires de la forme $(rdf:type, C)$, qui font d'un sujet une instance de la classe *C*. Ce sont ces classes que nous cherchons à définir. Le second ensemble, dénoté *D* est composé de paires $(p, o)$ telles que $p \neq rdf:type$. Les attributs du contexte sont donc $M = C \cup D$. Si l'on prend l'exemple de la figure 1, la figure ?? présente le contexte associé.

<table><caption>FIGURE 2 – Contexte formel associé aux données représentées figure 1.</caption><thead><tr><th colspan="4">Attributs</th></tr><tr><th></th><th>Descriptions</th><th colspan="2">Classes</th></tr><tr><th></th><th>$\exists r1:C_1$</th><th>$\exists r2:C_2$</th><th>$C_0$</th><th>$C_1$</th><th>$C_2$</th></tr></thead><tbody><tr><th>$x_0$</th><td>$\times$</td><td>$\times$</td><td>$\times$</td><td></td><td></td></tr><tr><th><strong>Objets</strong></th><td>$x_1$</td><td></td><td>$\times$</td><td></td><td></td></tr><tr><th>$x_2$</th><td></td><td></td><td></td><td>$\times$</td><td></td></tr></tbody></table>

À partir de là, il s'agit de trouver un ensemble de catégories et un ensemble de descriptions de manière à ce que leurs correspondances soient les mêmes. Sur la figure ?? par exemple, on a $\{C_0\}' = x_0$ et $\{\exists r_1:C_1, \exists r_2:C_2\}' = x_0$. On peut alors construire la définition suivante :

$$C_0 \equiv \exists r_1:C_1 \cap \exists r_2:C_2$$

<footnote n="1">1. En FCA, *G* est l'ensemble des *objets*, renommés *entités* afin de ne pas confondre avec les *objets* en RDF.</footnote>
Comme les données peuvent être incomplètes, il se peut qu'on ne retrouve pas une égalité entre une classe $C_1$ et sa description $\exists r:C_j$. Autrement dit $\{C_1\}' \neq \{\exists r:C_j\}'$. Il nous faut donc des approches qui tolèrent une forme d'approximation. C'est ce que permettent les trois algorithmes utilisés, et nous allons les détailler plus précisément dans la section suivante.

# 3 Algorithmes de fouille de règles

## 3.1 Règles d'association

Le but de la fouille de règles d'association (Agrawal et al., 1993; Klemettinen et al., 1994) est de trouver des dépendances entre les attributs. Une règle d'association entre deux ensembles d'attributs X et Y, notée $X \to Y$, signifie « si un objet a tous les attributs de X, alors il a tous les attributs de Y ». À cette règle est associée une confiance, qui peut être vue comme une probabilité conditionnelle :

$$ \mathrm{conf}(X \to Y) = \frac{|X' \cap Y'|}{|X'|}, $$

où $'$ correspond à la correspondance de Galois. La confiance est une mesure de qualité des règles d'association. Une règle d'association est valide si sa confiance est supérieure à un seuil $\theta$ défini par l'utilisateur. La confiance n'est pas symétrique : $X \to Y$ peut être valide sans que $Y \to X$ le soit. Si la confiance vaut 1, on dit qu'il s'agit d'une implication et l'on note $X \to Y$. Si on a également $Y \Rightarrow X$, alors $X$ et $Y$ forment une définition, notée $X \equiv Y$.

Nous nous intéressons ici à des définitions. Nous considérons donc conjointement $X \to Y$ et sa réciproque $Y \to X$ et cherchons à estimer à quel point ces règles s'approchent d'une implication. Pour cela, nous introduisons la notion de quasi-définition qui est à la définition ce que la règle d'association est à l'implication.

**Définition 1 (Quasi-définition).** Étant donné deux ensembles d'attributs X et Y, une quasi-définition $X \leftrightarrow Y$ est valide si, pour un seuil $\theta$ donné,

$$ \min(\mathrm{conf}(X \to Y), \mathrm{conf}(Y \to X)) \geq \theta. $$

L'algorithme Eclat (Zaki, 2000) est l'un des nombreux algorithmes de fouille de règles d'association existant. Il énumère de manière exhaustive toutes les règles d'association valides pour un seuil donné. Nous utilisons cet algorithme pour notre comparaison.

Une règle d'association $r_0 : x_1, \dots, x_n \to y_1, \dots, y_m$ peut se décomposer sous la forme de plusieurs règles d'association $r_i : x_1, \dots, x_n \to y_i$ pour $i \in \{1, \dots, m\}$. Si $r_0$ est valide, l'ensemble des $r_i$ est valide. Pour que les règles obtenues définissent des classes comme nous le souhaitons, il faut que les règles d'association soient de la forme «Classes → Descriptions» ou «Descriptions → Classes». C'est à dire que la règle $X \to Y$ est telle que $X \subseteq C, Y \subseteq D$ ou $X \subseteq D, Y \subseteq C$. Il nous faut donc

utiliser un post-traitement afin de s'assurer que la règle ne contient que des catégories d'un côté et que des descriptions de l'autre. Pour cela, seules les règles $X \to Y$ qui satisfont l'une des deux contraintes alternatives suivantes sont conservées : (i) l'antécédent ne contient que des classes ($X \subseteq C$) et il y a au moins une description dans la conséquence ($Y \cap D \neq \emptyset$); (ii) l'antécédent ne contient que des descriptions ($X \subseteq D$) et il y a au moins une classe dans la conséquence ($Y \cap C \neq \emptyset$). Les règles conservées sont décomposées de manière à ne garder que des classes (resp. des descriptions) dans la conséquence si l'antécédent ne contient que des descriptions (resp. des classes).

Par exemple, $\exists r_1:C_1, C_0 \to \exists r_2:C_2$ n'est pas conservée parce que l'antécédent contient à la fois une catégorie et une description. En revanche, la règle $\exists r_1:C_1 \to \exists r_2:C_2, C_0$ peut être décomposée en deux règles $r_1: \exists r_1:C_1 \to \exists r_2:C_2$ et $r_2: \exists r_1:C_1 \to C_0$. La règle $r_2$ est conservée. Si sa réciproque est valide, la quasi-définition obtenue est $C_0 \leftrightarrow \exists r_1:C_1$.

## 3.2 Redescriptions

La fouille de redescriptions, introduite par Ramakrishnan et al. (2004), a pour but de trouver des caractérisations multiples d'un même ensemble d'entités. À la différence des règles d'association, les redescriptions s'appuient sur une séparation de l'ensemble des attributs en vues. Une vue est un sous-ensemble d'attributs. L'ensemble des vues forme une partition des attributs. Nous utilisons ici deux vues, qui correspondent aux deux types d'attributs — classes et descriptions.

La similarité entre deux ensembles d'attributs, provenant de deux vues différentes, est mesurée avec le coefficient de Jaccard :

$$ \mathrm{jacc}(A, B) = \frac{|A' \cap B'|}{|A' \cup B'|}, $$

où $'$ correspond à la correspondance de Galois. Une paire d'ensembles d'attributs $(A, B)$ est une redescription si le coefficient de Jaccard $jacc(A, B)$ est supérieur à un seuil donné. Le coefficient de Jaccard est symétrique, contrairement à la confiance. Une redescription dont le coefficient de Jaccard vaut 1 est une définition. Toutes les redescriptions sont nécessairement des quasi-définitions. En effet,

$$ \min(\mathrm{conf}(A \to B), \mathrm{conf}(B \to A)) \geq \mathrm{jacc}(A, B). $$

L'algorithme ReReMi (Galbrun et Miettinen, 2012) est utilisé ici. En plus des données binaires, ReReMi permet de tenir compte de données numériques et catégorielles. Les redescriptions obtenues peuvent être des fonctions booléennes contenant des disjonctions et des négations d'attributs. Afin de comparer les trois algorithmes, ReReMi est ici restreint à des conjonctions d'attributs, raison pour laquelle nous ne parlons pas de fonctions booléennes.

Dans un premier temps, ReReMi cherche des paires d'attributs — un attribut de chaque vue — susceptibles de prendre part à une définition, c'est-à-dire celles qui ont le coefficient de Jaccard le plus élevé. Ces paires sont ensuite
étendues tour à tour, en ajoutant à chaque fois un attribut à l'un des côtés de la redescription, jusqu'à ce que le nombre d'attributs maximum soit atteint ou que le coefficient de Jaccard n'augmente plus. Les redescriptions ainsi obtenues qui satisfont les critères de sélection sont retournées à l'utilisateur.

## 3.3 Règles de traduction

<figure><img src="image_98.png" /><figcaption>FIGURE 3 – Intuition du fonctionnement de *Translator*. Ici, seule la traduction de $\mathcal{K}_1$ vers $\mathcal{K}_2$ est représentée. À chaque étape, le but est de trouver la règle qui va minimiser le nombre de croix dans le masque.</figcaption></figure>

L'algorithme *Translator* (van Leeuwen et Galbrun, 2015) s'appuie également sur une séparation du contexte en deux vues, et cherche un ensemble d'associations entre ces deux vues. Ces associations ont la même forme que des règles d'association, la différence se situant au niveau de la constitution de l'ensemble de règles.

Cet ensemble doit être compact et représentatif. D'une part, il doit couvrir la majorité des données. D'autre part, les règles doivent être aussi petites que possible en terme d'attributs. Afin de trouver un équilibre entre ces deux contraintes, *Translator* s'appuie sur le concept de Longueur de Description Minimum (MDL). Étant donné un contexte $\mathcal{K}$ et $X \subseteq M$ un ensemble d'attributs, la longueur de $X$ est

$$L(X) = - \sum_{x \in X} \log_2 P(x | \mathcal{K}) \quad \text{où } P(x | \mathcal{K}) = \frac{|x'|}{|G|}.$$

Cette longueur correspond au nombre minimal de bits requis pour encoder $X$.

Pour construire l'ensemble des règles, les auteurs font l'analogie avec la notion de traduction. Une règle est une traduction d'une vue vers une autre. L'idée sous-jacente est la suivante : on souhaite construire un ensemble de règles qui permettent, connaissant une des deux vues, de reconstruire la seconde et vice versa. L'idée générale est représentée figure 2. Les erreurs entre le contexte cible et le contexte reconstruit sont corrigées à l'aide d'un masque. La taille de ce masque indique donc le nombre d'erreurs introduites.

L'ensemble de règles est construit de manière itérative, en prenant, à chaque étape, la règle $X \to Y$ qui maximise $\Delta$

$$\Delta(X \to Y) = \underbrace{L(Mask^-) - L(Mask^+)}_{\text{Gain d'information}} - \underbrace{L(X \to Y)}_{\text{Longueur de la règle}}$$

où $Mask^+$ correspond aux éléments ajoutés au masque (erreurs introduites par la règle) et $Mask^-$ correspond aux éléments retirés du masque (erreurs corrigées par la règle). Des règles sont ajoutées tant que $\Delta$ est positif.

L'algorithme *Translator* est le seul dont la mesure de qualité tient compte des règles déjà extraites. Le masque étant mis à jour à chaque étape, la qualité d'une règle dépend des règles déjà extraites. Ainsi, *Translator* favorise un bon ensemble de règles plutôt qu'un ensemble de bonnes règles. Chaque règle apporte une information qui n'est pas contenue dans les autres, ce qui limite la redondance d'information.

## 4 Travaux connexes

La FCA est un outil de conceptualisation qui permet de structurer une ontologie par une approche *bottom-up*. Sertkaya (2011) fait une synthèse des différentes contributions qui s'intéressent au lien entre la FCA et les ontologies. La plupart des ontologies sont construites avec une approche *top-down*, c'est à dire en construisant d'abord le schéma. L'une des façons de tirer parti de la FCA est donc de consuire des connaissances qui vont enrichir une ontologie préexistante. C'est ce que nous faisons dans notre approche, en partant de triplets pour trouver des définitions.

Dans (Ferré et Cellier, 2016), les auteurs proposent une extension de la FCA pour les graphes conceptuels. Contrairement aux graphes RDF qui reposent sur des relations binaires, les graphes conceptuels permettent de tenir compte de relation *n*-aires. Les concepts construits correspondent à une association entre une requête SPARQL et l'ensemble des solutions. Dans notre approche, nous cherchons à mettre en relation deux *graph patterns* et nous ne connaissons pas *a priori* la requête SPARQL qui correspond à la description d'une catégorie.

Notre travail poursuit un travail initié dans (Alam et al., 2015). Les auteurs s'appuient sur la fouille de règles d'association pour fournir un espace de navigation sur des données RDF. Pour cela, les auteurs recherchent des implications et les ordonnent en fonction de la confiance de leur réciproque. Dans notre approche, nous introduisons la séparation des attributs et nous comparons les règles d'association avec les redescriptions et les règles de traduction.

L'algorithme AMIE, proposé par Galárraga et al. (2013), est une référence en matière de fouille de règles sur le web des données. Ces règles sont de la forme $B_1, B_2, \dots, B_{n-1} \to B_n$ où $B_i$ correspond à une relation entre deux variables, que l'on peut exprimer sous forme de triplet $\langle?x \ r \ ?y\rangle$. Par exemple, $\mathit{manufacturer}(x, \mathit{Samsung})$, $\mathit{successor}(y, x) \to \mathit{manufacturer}(y, \mathit{Samsung})$ est une règle qui peut être trouvée par AMIE. Les auteurs ajoutent une condition, à savoir que toutes les variables doivent apparaître deux fois dans la règle. Si l'on considère les triplets sous forme de graphe, il en résulte qu'une règle est un motif cyclique entre des variables (indépendamment de l'orientation des arcs). Dans notre cas, les motifs recherchés
caractérisent une seule ressource identifiée (motif en étoile) et l'association est bidirectionnelle. On trouve par exemple la règle Samsung_Mobile_Phone(x) ↔ manufacturer(x, Samsung).

<figure><img src="image_99.png" /><figcaption>FIGURE 4 – Motifs recherchés dans la base de connaissances par AMIE et par notre approche. Les traits pleins concernent la partie gauche de la règle, et les pointillés la partie droite. Les ?tᵢ sont des variables existentielles.</figcaption></figure>

# 5 Expérimentations

Nous avons réalisé nos expérimentations sur des données issues de DBpedia, qui est une KB construite à partir de Wikipédia. Nous cherchons à définir des catégories, c'est-à-dire les ressources qui sont dans le domaine de la relation **dct:subject**. Pour cela, nous extrayons un sous-ensemble de DBpedia à l'aide d'une requête SPARQL avant de transformer les triplets obtenus en contexte comme mentionné en Section 2.2. Enfin, nous utilisons les trois algorithmes présentés pour comparer et évaluer les résultats obtenus.

<table><caption>TABLE 1 – Statistiques sur les jeux de données extraits.</caption><thead><tr><th rowspan="2"></th><th rowspan="2">Triplets</th><th rowspan="2">Objets</th><th colspan="2">Attributs</th></tr><tr><th>Cat.</th><th>Descr.</th></tr></thead><tbody><tr><td>Turing_Award</td><td>2 642</td><td>65</td><td>503</td><td>857</td></tr><tr><td>Smartphones</td><td>8 418</td><td>598</td><td>359</td><td>1 730</td></tr><tr><td>Sports_cars</td><td>9 047</td><td>604</td><td>435</td><td>2 295</td></tr><tr><td>French_films</td><td>121 496</td><td>6 039</td><td>6 028</td><td>19 459</td></tr></tbody></table>

# 5.1 Méthodologie

Nous avons extrait quatre sous-ensembles de triplets de DBpedia, de différents domaines<fnref n="2" />. Afin d'isoler un sous-ensemble de triplets, nous avons récupéré tous les triplets dont le sujet est lié à une catégorie donnée. Pour cela, nous avons utilisé la requête SPARQL suivante :

```sql
SELECT DISTINCT * WHERE {
    ?s ?p ?o .
    ?s dct:subject dbc:X .
    ?p a owl:ObjectProperty .
}
```

Les quatres domaines utilisés (X) sont French_films, Turing_Award_laureates,

Smartphones et Sports_cars. Le triplet ?p a owl:objectProperty assure que ?o n'est pas un littéral.

Les triplets extraits sont divisés en deux groupes. L'ensemble des triplets qui ont pour prédicat dct:subject correspond aux attributs de classe (C). L'ensemble des triplets dont le prédicat n'est pas dct:subject correspond aux attributs de description (D).

# 5.2 Résultats et évaluation

<table><caption>TABLE 2 – Évaluation des résultats pour chaque jeu de données. |Cᵢ| (resp. |Dᵢ|) désigne le nombre moyen de catégories (resp. de descriptions) dans une règle.</caption><thead><tr><th colspan="4">Turing_Award_laureates</th></tr><tr><th>X</th><th>Eclat</th><th>ReReMi</th><th>Translator</th></tr></thead><tbody><tr><td>|B<sup>X</sup><sub>cand</sub>|</td><td>47</td><td>12</td><td>11</td></tr><tr><td>|B<sup>X</sup><sub>def</sub>|</td><td>30</td><td>9</td><td>9</td></tr><tr><td>Précision</td><td>.64</td><td>.75</td><td>.85</td></tr><tr><td>|C<sub>i</sub>| — |D<sub>i</sub>|</td><td>2 — 4</td><td>1 — 1</td><td>3 — 5</td></tr></tbody><thead><tr><th colspan="4">Sports_cars</th></tr><tr><th>X</th><th>Eclat</th><th>ReReMi</th><th>Translator</th></tr></thead><tbody><tr><td>|B<sup>X</sup><sub>cand</sub>|</td><td>132</td><td>52</td><td>31</td></tr><tr><td>|B<sup>X</sup><sub>def</sub>|</td><td>95</td><td>30</td><td>23</td></tr><tr><td>Précision</td><td>.72</td><td>.68</td><td>.74</td></tr><tr><td>|C<sub>i</sub>| — |D<sub>i</sub>|</td><td>2.8 — 4.5</td><td>1.3 — 1.4</td><td>2.6 — 4.1</td></tr></tbody><thead><tr><th colspan="4">Smartphones</th></tr><tr><th>X</th><th>Eclat</th><th>ReReMi</th><th>Translator</th></tr></thead><tbody><tr><td>|B<sup>X</sup><sub>cand</sub>|</td><td>810</td><td>98</td><td>41</td></tr><tr><td>|B<sup>X</sup><sub>def</sub>|</td><td>521</td><td>57</td><td>31</td></tr><tr><td>Précision</td><td>.64</td><td>.58</td><td>.76</td></tr><tr><td>|C<sub>i</sub>| — |D<sub>i</sub>|</td><td>4.3 — 7.8</td><td>1.6 — 1.8</td><td>3.1 — 3.1</td></tr></tbody><thead><tr><th colspan="4">French_films</th></tr><tr><th>X</th><th>Eclat</th><th>ReReMi</th><th>Translator</th></tr></thead><tbody><tr><td>|B<sup>X</sup><sub>cand</sub>|</td><td>546</td><td>36</td><td>93</td></tr><tr><td>|B<sup>X</sup><sub>def</sub>|</td><td>371</td><td>12</td><td>89</td></tr><tr><td>Précision</td><td>.68</td><td>.33</td><td>.96</td></tr><tr><td>|C<sub>i</sub>| — |D<sub>i</sub>|</td><td>2.8 — 4.4</td><td>1.2 — 1.1</td><td>2.3 — 4.2</td></tr></tbody></table>

Chaque algorithme retourne un ensemble ordonné de quasi-définitions de la forme $C_0, \dots, C_n \leftrightarrow D_0, \dots, D_m$. Chacune des quasi-définitions est évaluée manuellement par trois personnes jouant le rôle d'experts. Étant donnée une quasi-définition $C_0, \dots, C_n \leftrightarrow D_0, \dots, D_m$ d'un jeu de données J, l'évaluateur répond à la question « Étant donné que nous parlons de J, est il correct de dire que faire partie à la fois de $C_0$, de ... et de $C_n$ et avoir les propriétés $D_0$, ... et $D_m$ est équivalent ? »

L'évaluation finale est l'évaluation majoritaire des trois experts. Si la règle est acceptée, elle rejoint l'ensemble des

<footnote n="2">2. Les jeux de données ainsi que les résultats obtenus sont disponibles à l'adresse https://gitlab.inria.fr/jreynaud/DefinitionMiningComparison.</footnote>
définitions obtenues, dont 20 exemples sont présentés figure 4. Les experts ont été du même avis dans 95.4% des cas. La règle R5 de la figure 4 est une règle qui n'a pas fait l'unanimité.

Les algorithmes sont comparés sur la base des définitions extraites et des catégories définies. La figure 5 présente un diagramme de Venn pour chaque corpus, qui représente le nombre de définitions extraites par chaque algorithme. Par exemple, pour le corpus *Turing_Award_laureates*, il y a 22 définitions trouvées uniquement par *Eclat*, et 8 trouvées à la fois par *Eclat* et *Translator*. Au total, *Eclat* a extrait 30 définitions. La figure 6 présente également un diagramme de Venn pour chaque corpus, qui correspond au nombre de catégories définies par chaque algorithme. Une catégorie est considérée comme définie dès lors qu'elle apparaît dans au moins une définition. Il peut donc y avoir une ou plusieurs catégories considérées comme définies pour une seule définition. C'est notamment le cas des règles R2, R8-R10, R12, R14, R17-R20 de la figure 4.

# 6 Discussion

Ci-dessous, $B_{cand}[X]$ désigne l'ensemble de toutes les quasi-définitions extraites par l'algorithme $X$ et $B_{def}[X]$ l'ensemble des définitions de $X$, c'est-à-dire, l'ensemble des quasi-définitions de $B_{cand}[X]$ évaluées vraies par les experts. L'ensemble $B_{cand}$ désigne la totalité des quasi-définitions, indépendamment de l'algorithme qui les a extraites. De la même façon, $B_{def}$ désigne l'ensemble de toutes les définitions extraites.

## 6.1 Précision et rappel

La précision d'un algorithme $X$ est $\frac{|B_{def}^X|}{|B_{cand}^X|}$. La précision de ReReMi a une très forte variabilité (entre 33 et 75%) et est globalement la plus faible, tout particulièrement sur le jeu de données *French_films*. La précision d'Eclat est stable (entre 64 et 72%). La meilleure précision est obtenue par *Translator*: quel que soit le jeu de données, elle toujours supérieure à 74%.

Le rappel, défini comme $\frac{|B_{def}^X|}{|B_{def}^X|}$ ne peut pas être utilisé comme une mesure de performance. En effet, certaines règles se recouvrent (ont des attributs en commun des deux côtés). C'est le cas des règles R6 à R10 (figure 4) qui définissent toutes la catégorie *McLaren_vehicles*. Tandis que *Translator* n'extrait qu'une seule règle (R8), ReReMi extrait 2 règles (R6 et R7) et Eclat en extrait 9 (seules R8 à R10 sont reportées ici).

La table ?? indique le nombre de catégories pour chaque jeu de données. Si l'on se fie à ces valeurs, le rappel est très faible : dans le corpus *Turing_Award_laureates* par exemple, pour 503 catégories dans les données de départ, seules 19 font partie d'une règle. Cela s'explique principalement par la très faible densité des contextes ; une grande quantité de catégories ne concerne qu'une seule entité du jeu de données. Si l'on ne compte que les catégories qui

ont un support d'au moins 3, elles ne sont plus que 105, et 47 catégories seulement on un support d'au moins 5. Nous considérons donc le rappel non pas par rapport au nombre de catégories présentes dans le jeu de données, mais par rapport aux catégories retrouvées par l'ensemble des algorithmes, comme présenté figure 6.

## 6.2 Forme et interprétation des règles

D'après la figure 6, 70% des catégories définies par *Eclat* ou *Translator* sont définies par les deux algorithmes. *Translator* extrait considérablement moins de règles que *Eclat* (jusqu'à 16 fois moins pour le corpus *Smartphones*). Cela s'explique par la façon dont sont générées les règles d'association. Si dans les données, la règle $A \to B$ a le même support que la règle $A \to B, C$, alors seule la règle $A \to B, C$ est conservée. En revanche si le support de $A \to B$ est strictement supérieur au support de $A \to B, C$, *Eclat* génère deux règles. En conséquence, on obtient avec *Eclat* des règles qui ne diffèrent que d'un attribut, comme R9 et R10 par exemple, alors que *Translator* ne génère qu'une seule règle, R8 dans l'exemple.

ReReMi n'extrait aucune définition en commun avec *Eclat* et *Translator*. Cette différence s'explique par l'heuristique employée par ReReMi. Si $C$ est une catégorie, et que $D_1$ et $D_2$ sont deux descriptions telles que $C' = D'_1 = D'_2$, alors ReReMi privilégie deux définitions $C \equiv D_1$ et $C \equiv D_2$ tandis que *Eclat* ne génère qu'une seule définition $C \equiv D_1 \sqcap D_2$. C'est par exemple le cas des définitions R6, R7 générées par ReReMi et R8, générée par *Eclat* (figure 4). Si $C' = D'_1$ et $D'_1 \subset D'_2$, ReReMi génère la définition $C \equiv D_1$, tandis que *Eclat* génère la définition $C \equiv D_1 \sqcap D_2$. Ce cas a également été retrouvé dans nos résultats, comme le montrent les définitions R12 et R13.

La taille des définitions générées par ReReMi est inférieure à celle des définitions de *Translator* et *Eclat*. Cela s'explique par l'heuristique de ReReMi déaillée dans le paragraphe précédent. ReReMi a en moyenne entre 1 et 2 attributs de chaque côté de la définition tandis que pour *Eclat* et *Translator*, il y a en moyenne 3 catégories et 4 descriptions par définition.

Les conjonctions dans les définitions extraites par ReReMi n'ont pas le même sens que celles extraites par *Eclat* et *Translator*. Par exemple, si l'on considère la définition R15, l'attribut (*a Device*) peut être enlevé sans altérer la définition : parce que toutes les entités considérées sont des instances de *Device*. À l'inverse, dans la définition R14, aucun attribut ne peut être retiré sans que la définition ne devienne fausse : tous les attributs font partie de la condition nécessaire. Dans notre approche, il nous semble plus pertinent de n'intégrer que des attributs qui contribuent pleinement à la définition dont ils font partie. Ainsi, la définition R14 nous parait préférable à la définition R15, parce qu'elle est apparue plus facile à interpréter.
Turing_Award_laureates

<table><tr><td>R</td><td>Harvard_University_alumni</td><td>↔</td><td>(almaMater Harvard_University)</td><td>R1</td></tr><tr><td>ET</td><td>Harvard_University_alumni, Turing_Award_laureates</td><td>↔</td><td>(a Agent), (a Person), (a Scientist), (almaMater Harvard_University)</td><td>R2</td></tr><tr><td>E</td><td>Turing_Award_laureates</td><td>↔</td><td>(a Agent), (a Person), (award Turing_Award)</td><td>R3</td></tr><tr><td>ET</td><td>Turing_Award_laureates</td><td>↔</td><td>(a Agent), (a Person), (a Scientist), (award Turing_Award)</td><td>R4</td></tr><tr><td>E</td><td>Modern_cryptographers</td><td>↔</td><td>(field Cryptography)</td><td>R5</td></tr></table>

Sports_cars

<table><tr><td>R</td><td>McLaren_vehicles</td><td>↔</td><td>(manufacturer McLaren_Automotive)</td><td>R6</td></tr><tr><td>R</td><td>McLaren_vehicles</td><td>↔</td><td>(assembly Surrey)</td><td>R7</td></tr><tr><td>ET</td><td>McLaren_vehicles, Sports_cars</td><td>↔</td><td>(a Automobile), (a MeanOfTransportation), (assembly Woking), (assembly Surrey), (assembly England), (bodyStyle Coupé), (manufacturer McLaren_Automotive)</td><td>R8</td></tr><tr><td>E</td><td>McLaren_vehicles, Sports_cars</td><td>↔</td><td>(a Automobile), (a MeanOfTransportation), (assembly England), (assembly Surrey), (bodyStyle Coupé)</td><td>R9</td></tr><tr><td>E</td><td>McLaren_vehicles, Sports_cars</td><td>↔</td><td>(a Automobile), (a MeanOfTransportation), (assembly Surrey), (bodyStyle Coupé)</td><td>R10</td></tr></table>

Smartphones

<table><tr><td>ET</td><td>Firefox_OS-devices, Open-source_mobile_phones, Smartphones, Touchscreen_mobile_phones</td><td>↔</td><td>(a Device), (operatingSystem Firefox_OS)</td><td>R11</td></tr><tr><td>R</td><td>Nokia_mobile_phones</td><td>↔</td><td>(manufacturer Nokia)</td><td>R12</td></tr><tr><td>ET</td><td>Nokia_mobile_phones, Smartphones</td><td>↔</td><td>(a Device), (manufacturer Nokia)</td><td>R13</td></tr><tr><td>R</td><td>Samsung_Galaxy</td><td>↔</td><td>(manufacturer Samsung_Electronics), (operatingSystem Android_(operating_system))</td><td>R14</td></tr><tr><td>ET</td><td>Samsung_Galaxy, Samsung_mobile_phones, Smartphones</td><td>↔</td><td>(a Device), (manufacturer Samsung_Electronics), (operatingSystem Android_(operating_system))</td><td>R15</td></tr></table>

French_films

<table><tr><td>R</td><td>Pathé_films</td><td>↔</td><td>(distributor Pathé)</td><td>R16</td></tr><tr><td>R</td><td>Films_directed_by_Georges_Méliès</td><td>↔</td><td>(director Georges_Méliès)</td><td>R17</td></tr><tr><td>ET</td><td>Films_directed_by_Georges_Méliès, French_films, French_silent_short_films</td><td>↔</td><td>(a Film), (a Wikidata:Q11424), (a Work), (director Georges_Méliès)</td><td>R18</td></tr><tr><td>ET</td><td>Films_directed_by_Jean_Rollin, French_films</td><td>↔</td><td>(a Film), (a Wikidata:Q11424), (a Work), (director Jean_Rollin)</td><td>R19</td></tr><tr><td>ET</td><td>Film_scores_by_Gabriel_Yared, French_films</td><td>↔</td><td>(a Film), (a Wikidata:Q11424), (a Work), (musicComposer Gabriel_Yared)</td><td>R20</td></tr></table>

FIGURE 5 – Exemples de quasi-définitions obtenues par Eclat, ReReMi et Translator pour chaque corpus. Lorsque le préfixe d'un attribut de droite n'est pas spécifié, il s'agit de dbo. Le préfixe des catégories (dbc) n'est pas spécifié.

# 7 Conclusion

Dans cet article, nous nous sommes intéressés à trois algorithmes pour trouver des définitions de classes dans le web des données. Nous avons vu que chaque algorithme avait ses spécificités et nous avons vérifié empiriquement que les résultats extraits reflètent ces spécificités. Nous avons aussi montré que malgré des approches très différentes, les algorithmes Eclat et Translator extraient de nombreuses règles communes. À l'inverse, ReReMi, malgré une mesure de qualité semblable à Eclat, extrait des règles plus courtes. L'intérêt de ces algorithmes dépend de l'objectif de l'utilisateur. Dans le cas de notre expérimentation, Eclat est l'algorithme qui a qualifié le plus de catégories, au prix d'un nombre de règles extraites très important. Translator extrait significativement moins de règles avec un nombre de catégories définies légèrement inférieure. Enfin, ReReMi, malgré un nombre de catégories définies plus faible, offre des définitions plus simples en n'incluant pas les attributs qui ne participent pas pleinement à la règle. Par la suite, plusieurs directions de recherche sont envisagées, au niveau de la préparation des données, de la fouille et de l'évaluation.

Comme mentionné précédemment, les contextes construits

à partir des données RDF sont très creux. Dans le cas d'Eclat et de ReReMi, un seuil de support étant utilisé, l'existence d'attributs à très faible support n'a pas d'impact sur les règles retrouvées. Pour Translator en revanche, les règles doivent permettre de reconstruire intégralement le contexte. Dans ce cas, il peut être pertinent de simplifier le contexte avant de procéder à la fouille de règles. Cela peut notamment passer par la suppression des attributs à très faible support, ou au contraire, des attributs ayant un support quasi maximal, et donc qui concernent toutes les entités. Nous pourrons également travailler sur le type des données en entrée, en intégrant notamment des valeurs numériques, ce qui nous permettra de prendre en compte des triplets laissés de côté pour cette expérimentation, tels que les informations de date, d'âge, de taille, ...

Pour améliorer le processus de fouille, il est possible d'ajouter des contraintes sur les règles obtenues afin de restreindre l'espace de recherche, mais aussi d'obtenir des règles plus faciles à interpréter. Dans notre cas, n'autoriser qu'une catégorie par règle serait une contrainte pertinente. Nous pouvons également étendre l'expressivité des règles recherchées en permettant par exemple des opérateurs logiques tels que les disjonctions ou les négations. Si ReReMi permet déjà d'obtenir de telles formules lo-
<figure><img src="image_100.png" /></figure>

<figure><img src="image_101.png" /></figure>

<figure><img src="image_102.png" /></figure>

<figure><img src="image_103.png" /><figcaption>FIGURE 6 – Règles extraites par Eclat, ReReMi et Translator pour chaque jeu de données.</figcaption></figure>

<figure><img src="image_104.png" /></figure>

<figure><img src="image_105.png" /></figure>

<figure><img src="image_106.png" /></figure>

<figure><img src="image_107.png" /><figcaption>FIGURE 7 – Catégories définies par Eclat, ReReMi et Translator pour chaque jeu de données.</figcaption></figure>

giques, et que des travaux dans ce sens existent pour les règles d'association, ce n'est pas le cas pour les règles de traduction. Cela implique de revoir le calcul de la longueur d'une règle.

Concernant l'évaluation, il nous faudra un moyen de comparer plus formellement les règles entre elles, peut-être *via l'introduction d'une notion de redondance, qui permettrait de définir une base de règles.*

## Remerciements

Ce travail est financé avec le support de la Direction Générale de l'Armement et de la Région Lorraine. Merci à Esther Galbrun pour ses conseils ainsi que Quentin Brabant et Jérémie Nevin pour leur aide à l'évaluation des règles.

## Références

R. AGRAWAL, T. IMIELIŃSKI et A. SWAMI : Mining association rules between sets of items in large databases. In *ACM SIGMOD Rec.*, vol. 22, p. 207–216. ACM, 1993.

M. ALAM, A. BUZMAKOV, V. CODOCEDO et A. NAPOLI : Mining definitions from rdf annotations using formal concept analysis. In *IJCAI*, p. 823–829, 2015.

F. BAADER, D. CALVANESE, D. MCGUINNESS, D. NARDI et P. PATEL-SCHNEIDER, éds. *The Description Logic Handbook*. Cambridge University Press, Cambridge, UK, 2003.

S. FERRÉ et P. CELLIER : Graph-FCA in Practice. In *Proceedings of 22nd ICCS*, p. 107–121, 2016.

L. A. GALÁRRAGA, C. TEFLIOUDI, K. HOSE et F. M. SUCHANEK : AMIE : association rule mining under incomplete evidence in ontological knowledge bases. In *WWW’13*, p. 413–422, 2013.

E. GALBRUN et P. MIETTINEN : From Black and White to Full Color : Extending Redescription Mining Outside the Boolean World. *Statistical Analysis and Data Mining*, 5(4):284–303, 2012.

B. GANTER et R. WILLE : *Formal concept analysis - mathematical foundations*. Springer, 1999.

M. KLEMETTINEN, H. MANNILA, P. RONKAINEN, H. TOIVONEN et A. I. VERKAMO : Finding interesting rules from large sets of discovered association rules. In *CIKM’94*, p. 401–407, 1994.

N. RAMAKRISHNAN, D. KUMAR, B. MISHRA, M. POTTS et R. F. HELM : Turning CARTwheels : an Alternating Algorithm for Mining Redescriptions. In *KDD’04*, p. 266–275, 2004.

B. SERTKAYA : A survey on how description logic ontologies benefit from formal concept analysis. *CoRR*, abs/1107.2822, 2011.

M. van LEEUWEN et E. GALBRUN : Association Discovery in Two-View Data. *TKDE*, 27(12):3190–3202, déc. 2015.

M. J. ZAKI : Scalable algorithms for association mining. *TKDE*, 12(3):372–390, May 2000.
# Découverte de cardinalité maximale contextuelle dans les bases de connaissances

E. A. Sidi Aly<fnref n="1" />,²

M. L. Diakité<fnref n="1" />

A. Giacometti²

B. Markhoff²

A. Soulet²

¹ Département Mathématiques et Informatique - Université de Nouakchott Al Aasriya (Mauritanie)

² Laboratoire d'Informatique Fondamentale et Appliquée de Tours - Université de Tours (France)

arbi2fr@yahoo.fr, diakite@una.mr, prenom.nom@univ-tours.fr

3 juillet 2018

## Résumé

Les bases de connaissances du web sémantique doivent être enrichies par des informations utiles aux applications de fouille, de recherche d'information, de question-réponse, etc. En effet, leur génération à partir de plate-formes collaboratives ou d'intégration de sources diverses produit des manques d'information, d'une part, et des erreurs ou incohérences d'autre part. Heureusement, leur volume important permet d'en induire des contraintes vrais-emblables. Tel est l'objet de l'algorithme présenté dans cet article, qui extrait des règles de cardinalité maximale à partir d'une base de connaissances. L'enrichissement de la base par ces nouveaux axiomes permet d'y trouver plus de faits, positifs ou négatifs, ce qui rend plus pertinentes les évaluations de la qualité des règles générées par des algorithmes de fouille classiques. Les expérimentations menées sur une partie de DBpedia et sur l'ensemble d'une base de connaissances numismatiques démontrent la faisabilité de l'approche et la pertinence des contraintes extraites.

## Mots Clef

Découverte de cardinalité, base de connaissances.

## Abstract

The big semantic web knowledge bases have to be enriched for applications in data mining, information retrieval, question answering, etc. Indeed, their generation from collaborative platforms or integration of various sources leads to lack of information on the one hand, and inconsistencies on the other hand. Fortunately, their volume makes it possible to induce probable constraints. This is the aim of the algorithm presented in this article, which extracts maximum cardinality rules from a knowledge base. Adding these new axioms to the knowledge base allows applications to find more facts, positive or negative, which makes more relevant the evaluations of the quality of the rules generated by traditional datamining algorithms. Experiments conducted on part of DBpedia and on an entire numismatic knowledge base demonstrate the feasibility of the approach and the relevance of the discovered contextual constraints.

## Keywords

Cardinality discovery, knowledge base.

## 1 Introduction

Nous considérons de grandes bases de connaissances du web, construites par des algorithmes de recherche d'information à partir de plateformes collaboratives (e.g., DBpedia [2]) et/ou d'intégration de sources diverses. Pour en désigner les éléments, nous utilisons les termes concept, rôle et individu au sens des logiques de description.

**Contexte et motivations** En représentation des connaissances les restrictions numériques précisant le nombre d'occurrences d'un rôle sont particulièrement utiles [3]. Parmi elles, les contraintes de cardinalité maximale permettent de savoir quand toutes les assertions sur un rôle donné pour un individu donné existent dans la base. C'est utile pour qualifier les réponses aux requêtes sur une base de connaissances, c'est-à-dire les compléter par des informations précises sur leur qualité en terme de *rappel* par rapport à une réalité [13, 17].

Il est illusoire d'espérer des ajouts manuels de telles contraintes d'intégrité dans de grandes bases de connaissances<fnref n="1" />, qui soient correctes et suffisantes. Aussi, des techniques de type rétro-ingénierie [14] applicables sur ces grandes bases doivent être considérées, afin de les rechercher systématiquement. Des propositions existent déjà pour trouver des contraintes de clés [1, 11, 15, 16] dans des données RDF. Mais à notre connaissance, il n'y a pas encore de travaux sur l'extraction de contraintes de cardinalité maximale dans les bases de connaissances.

**Challenge** L'extraction de contraintes de cardinalité à partir des données existantes est connue comme un problème important de la rétro-ingénieérie des bases de données relationnelles [14, 18]. Par rapport au cadre des bases de données traditionnelles, ce problème est bien plus complexe pour les bases de connaissances du web. Tout d'abord, ces bases de connaissances contiennent généralement des données incohérentes, que ce soient

<footnote n="1">1. [5] présente néanmoins un outil pour le faire sur Wikidata.</footnote>
des assertions fausses ou des assertions dupliquées. De ce fait, la cardinalité maximale observée pour un rôle donné ne saurait être considérée comme sa cardinalité maximale la plus vraisemblable. Par exemple, il est vraisemblable qu'une personne ait au plus une année de naissance et deux parents. Pourtant dans DBpedia (voir les rôles `db:birthYear` et `db:parent` dans la table 1), certaines personnes ont 5 années de naissance ou 6 parents ! Ces quelques assertions incohérentes ne doivent pas influencer la caractérisation des cardinalités maximales.

Ensuite, ces bases de connaissances sont souvent **incomplètes pour un rôle donné**. Pour cette raison, la cardinalité la plus observée n'est pas forcément la cardinalité maximale. Typiquement, la plupart des personnes décrites dans DBpedia n'ont qu'un seul parent renseigné (voir le rôle `db:parent` dans la table 1). Toutefois, certaines en ont plus et ceci n'est pas une anomalie, il faut en tenir compte : la cardinalité maximale du rôle `db:parent` pour une personne ne doit pas être sous-estimée (ici à 1) au vu de l'ensemble des cardinalités observées.

Enfin, des travaux récents sur la détection de contraintes de clefs dans les bases de connaissances [16] ont montré que de nombreuses contraintes intéressantes ne sont valides que sur une partie d'une base de connaissances. Par exemple, s'il semble difficile de déterminer une cardinalité maximale pour le nombre de nationalités d'une personne en général, comme certains états limitent le nombre de nationalités à 1 il est possible de détecter cette limite pour les ressortissants de tels états. Il est donc essentiel non seulement de détecter des cardinalités maximales, mais aussi d'identifier les contextes dans lesquels de telles contraintes peuvent être détectées.

**Contributions** Etant donnée une distribution de cardinalités $(n_i)_{i \ge 1}$ observées dans une base de connaissances $\mathcal{K}$ pour un rôle $R$ dans un contexte $C$, nous commençons par proposer une méthode de calcul d'une cardinalité maximale vraisemblable, en calculant une estimation du taux de cohérence réel que la cardinalité $i$ soit maximale. Cette estimation, notée $\tau_i$, est calculée en prenant en compte tous les individus pour lesquels le rôle $R$ est complet. Son calcul est détaillé et justifié dans la section 4.2. Pour être statistiquement valide, une version corrigée de cette estimation du taux de cohérence, notée $\tilde{\tau}_i$, est également introduite. Des exemples d'estimations de taux cohérence, corrigés ou non, sont représentés dans la table 1 pour les rôles `db:birthYear`, `db:parent` et `db:nationality` en considérant le concept `db:Person` comme contexte.

Etant donnée une arborescence de concepts constituant les contextes candidats, nous proposons ensuite **un algorithme d'exploration systématique d'un ensemble de contraintes contextuelles** pour les rôles desquels nous recherchons les cardinalités maximales. Cet algorithme, décrit en section 4.3, vise à limiter les calculs en élaguant un maximum des contraintes possibles.

Enfin nous présentons et analysons des résultats expérimentaux obtenus sur une base de connaissances

résultant d'un processus d'intégration de 5 bases de données numismatiques [6].

`db:Person` / `db:birthYear`

<table><thead><tr><th><i>i</i></th><th><i>n</i><sub>i</sub></th><th><i>τ</i><sub>i</sub></th><th><i>τ̃</i><sub>i</sub></th></tr></thead><tbody><tr><td>5</td><td>1</td><td>1.0</td><td>0.0</td></tr><tr><td>4</td><td>2</td><td>0.667</td><td>0.0</td></tr><tr><td>3</td><td>4</td><td>0.571</td><td>0.0</td></tr><tr><td>2</td><td>91</td><td>0.928</td><td>0.775</td></tr><tr><td><b>1</b></td><td><b>159841</b></td><td><b>0.999</b></td><td><b>0.996</b></td></tr></tbody></table>

`db:Person` / `db:parent`

<table><thead><tr><th><i>i</i></th><th><i>n</i><sub>i</sub></th><th><i>τ</i><sub>i</sub></th><th><i>τ̃</i><sub>i</sub></th></tr></thead><tbody><tr><td>6</td><td>1</td><td>1.0</td><td>0.0</td></tr><tr><td>4</td><td>9</td><td>0.9</td><td>0.420</td></tr><tr><td>3</td><td>75</td><td>0.882</td><td>0.718</td></tr><tr><td><b>2</b></td><td><b>9392</b></td><td><b>0.991</b></td><td><b>0.975</b></td></tr><tr><td>1</td><td>10643</td><td>0.529</td><td>0.518</td></tr></tbody></table>

`db:Person` / `db:nationality`

<table><caption>TABLE 1 – Distributions de cardinalités de rôles de personnes dans DBpedia ($i$ est la cardinalité; $n_i$ le nombre d'individus étant $i$ fois sujets du rôle considéré; $\tau_i$ est une estimation fréquentielle du taux de cohérence réel; $\tilde{\tau}_i$ en est une version corrigée s'appuyant sur la borne de Hoeffding)</caption><thead><tr><th><i>i</i></th><th><i>n</i><sub>i</sub></th><th><i>τ</i><sub>i</sub></th><th><i>τ̃</i><sub>i</sub></th></tr></thead><tbody><tr><td>8</td><td>2</td><td>1,000</td><td>0,000</td></tr><tr><td>6</td><td>1</td><td>0,333</td><td>0,000</td></tr><tr><td>5</td><td>1</td><td>0,250</td><td>0,000</td></tr><tr><td>4</td><td>13</td><td>0,765</td><td>0,397</td></tr><tr><td>3</td><td>167</td><td>0,908</td><td>0,796</td></tr><tr><td>2</td><td>3 263</td><td>0,947</td><td>0,921</td></tr><tr><td>1</td><td>123 386</td><td>0,973</td><td>0,969</td></tr></tbody></table>

## 2 Etat de l'art

Notre algorithme vise à augmenter la connaissance sur les données contenues dans les grandes bases de connaissances du web, en termes de validité comme en termes de complétude par rapport à la réalité représentée. Il permet d'enrichir la partie schéma (TBox en logiques de description) de ces bases pour mieux utiliser leur partie données (ABox). Plusieurs travaux récents vont dans ce sens [1, 11, 15, 16, 10] et d'autres s'en rapprochent [7, 13, 17] mais ciblent des individus (assertions de la ABox) plutôt que des concepts (assertions de la TBox).

Dans [17], une technique de fouille de textes de Wikipédia pour ajouter des précisions sur le degré de complétude des informations dans Wikidata est décrite. Notre proposition est complémentaire puisque notre algorithme traite les données déjà contenues dans les bases de connaissances. Mais surtout, il ne caractérise pas les rôles par rapport à des individus précis mais à des concepts définis (au sens des logiques de description). Les auteurs de [7, 13] présentent également des propositions pour déterminer quand est-ce qu'un rôle particulier (comme `db:parent`) manque pour un individu particulier (comme *Obama*). Plus générale, notre proposition consiste à calculer les cardinalités maximales vraisemblables des rôles relativement à des concepts
définissant des contextes : elle enrichit donc la partie schéma.

Ce sont des clés au sens des bases de données, donc des contraintes au niveau du schéma, qui sont recherchées dans [1, 11, 15, 16]. L'idée est de trouver des axiomes indiquant que tout individu d'un certain concept doit posséder une valeur unique pour un rôle donné R. Cela constitue donc une cardinalité maximale du rôle R pour le concept C. Egalement très proches de nos travaux, dans [10], les auteurs proposent de déterminer automatiquement quels rôles devraient être obligatoirement renseignés pour un concept donné de la base de connaissances. Pour cela ils comparent la densité du rôle pour les individus de ce concept par rapport à sa densité pour les individus d'autres concepts, qui lui sont liés dans la hiérarchie des concepts. Notre proposition s'appuie sur d'autres critères pour calculer la cardinalité maximale du rôle pour un contexte (notion plus générale que seulement les concepts de la base). Elle peut être adaptée au calcul de la cardinalité minimale, auquel cas elle trouverait, entre autres, quels rôles ont une cardinalité minimale au moins supérieure à 1 pour un concept donné, soit plus d'information que seulement savoir si le rôle devrait exister ou pas.

Ces différentes sortes d'information supplémentaire sur la qualité des données de la base de connaissances, en termes de validité comme en termes de complétude par rapport à la réalité représentée, permettent d'améliorer le fonctionnement des applications qui les utilisent, en réduisant le flou de l'hypothèse du monde ouvert. Ainsi pour améliorer la mesure de qualité de règles issues de processus de fouille dans les bases de connaissances du web sémantique, une hypothèse de complétude partielle est définie et utilisée dans [8, 7] : cette règle stipule que si un rôle est renseigné pour un individu, alors les informations concernant ce rôle pour cet individu sont considérées complètes. Si on peut noter que cette hypothèse est contredite par l'observation de DBpedia (voir l'extrait fourni dans la table 1), elle rend tout de même plus précis le calcul de la confiance associée aux résultats de fouille. Ces auteurs ont démontré le besoin pour la fouille de ce qu'ils appellent des oracles de complétude, et proposé un certain nombre d'heuristiques pour en définir, comme par exemple la popularité des individus (qui augmente les chances que les faits renseignés sur eux soient complets), etc.

La fouille de données est loin d'être le seul domaine qui bénéficie d'axiomes tels que ceux découverts par notre algorithme, par exemple, s'appuyant sur des travaux de référence en base de données, les auteurs de [4, 12] et plus récemment [9] proposent de caractériser les réponses obtenues par des requêtes, en fonction des informations connues concernant le degré de complétude de la base de connaissances interrogée, par rapport à la réalité représentée.

# 3 Préliminaires

## 3.1 Bases de connaissances

Dans ce papier, nous considérons des bases de connaissances $\mathcal{K} = (\mathcal{T}, \mathcal{A})$ où $\mathcal{T}$ et $\mathcal{A}$ sont respectivement les TBox et ABox de $\mathcal{K}$. $\mathcal{T}$ désigne un ensemble d'axiomes terminologiques définis à partir des concepts et rôles atomiques de $\mathcal{K}$, alors que $\mathcal{A}$ désigne l'ensemble des asserptions ou faits de $\mathcal{K}$. Plus précisément, $\mathcal{A}$ contient des expressions de la forme $C(a)$ et $R(a, b)$ où $C$ est un concept, $R$ est un rôle, et $a, b$ sont des individus.

Dans le cas de la base de connaissances DBpedia, `dbo:Country` et `dbo:Person` sont des exemples de concepts atomiques et `dbo:nationality` est un exemple de rôle atomique de sa TBox. Par ailleurs, `dbo:Country(Mauritania)` et `dbo:nationality(Arby, Mauritania)` sont des exemples de faits ou assertions de sa ABox. Le premier indique que *Mauritania* est un pays, alors que le second indique que *Arby* est de nationalité mauritanienne.

Les logiques de description permettent de définir des axiomes pour enrichir la TBox d'une base de connaissances. Par exemple, la relation d'inclusion $\subseteq$ permet d'indiquer qu'un concept $C_1$ est inclus dans un concept $C_2$, noté $C_1 \subseteq C_2$. Plus précisément, une base de connaissances $\mathcal{K}$ implique l'axiome $C_1 \subseteq C_2$ si pour toute interprétation $\mathcal{I}$ de $\mathcal{K}$, $C_1^I \subseteq C_2^I$. Par exemple, les axiomes $\exists \mathcal{dbo}:\mathcal{n}ationality. \top \sqsubseteq \mathcal{dbo}:\mathcal{P}erson$ et $\exists \mathcal{dbo}:\mathcal{n}ationality. \neg \top \sqsubseteq \mathcal{dbo}:\mathcal{C}ountry$ indiquent respectivement que le domaine du rôle $\mathcal{dbo}:\mathcal{n}ationality$ est inclus dans le concept $\mathcal{dbo}:\mathcal{P}erson$, et que le domaine du rôle $\mathcal{dbo}:\mathcal{n}ationality$ est inclus dans le concept $\mathcal{dbo}:\mathcal{C}ountry$.

## 3.2 Contraintes contextuelles de cardinalité maximale

Soit $R$ un rôle d'une base de connaissances $\mathcal{K} = (\mathcal{T}, \mathcal{A})$. On considère généralement que ce rôle satisfait dans $\mathcal{K}$ une contrainte de cardinalité maximale $M$ si pour tout sujet $s$, le nombre d'objets $o$ tels que $R(s, o)$ soit présent dans $\mathcal{K}$ (directement présent dans sa ABox $\mathcal{A}$ ou inférable à partir de ses TBox $\mathcal{T}$ et ABox $\mathcal{A}$) est inférieur ou égal à $M$.

En logique de description, une telle contrainte peut se représenter par un axiome de la forme $\mathit{sqsubseteqq}$ en utilisant le constructeur de restriction de cardinalité ($\leq MR$). En effet, en terme logique, une base de connaissances $\mathcal{K}$ implique l'axiome $\exists R. \top \sqsubseteq (\leq MR)$ si pour toute interprétation $\mathcal{I}$ de $\mathcal{K}$, $\{x : (\exists y)((x, y) \in R^I)\} \subseteq \{x : \#\{y : (x, y) \in R^I\} \leq M\}$ où $\#E$ représente la cardinalité d'un ensemble $E$.

Plus précisément, dans ce papier, nous cherchons à identifier des contraintes contextuelles de cardinalité maximale, à savoir des contraintes qui ne sont pas nécessairement vérifiées par tous les sujets $s$ d'un rôle $R$, mais par tous les sujets instances d'un concept, qu'il soit atomique ou composé, déjà défini dans $\mathcal{K}$ ou pas. Cette notion est introduite
formellement dans la définition suivante :

**Définition 3.1 (Contrainte contextuelle).** *Etant donnés un rôle R, un concept atomique ou défini C et un entier M, une contrainte contextuelle de cardinalité maximale définie sur R est une expression $\gamma$ de la forme : $C \sqsubseteq (\le MR)$. Le concept C est appelé le contexte de la contrainte $\gamma$. La contrainte $\gamma$ est satisfaite dans une base de connaissances $\mathcal{K}$ si et seulement si pour toute interprétation $\mathcal{I}$ de $\mathcal{K}$, $C^I \subseteq \{x : \#\{y : (x, y) \in R^I\} \le M\}$.*

Par exemple, la contrainte contextuelle (dbo:Person) $\sqsubseteq$ ($\le 5$ dbo:nationality) indique que toutes les personnes ont au plus 5 nationalités, alors que la contrainte contextuelle (dbo:Person $\sqcap \exists$ dbo:nationality.{$China$}) $\sqsubseteq$ ($\le 1$ dbo:nationality) indique que toutes les personnes de nationalité chinoise ont au plus une nationalité.

Dans ce travail, on cherche à extraire des contraintes contextuelles de cardinalité maximale qui soient les plus générales possibles.

**Définition 3.2 (Contrainte contextuelle minimale).** *Soient deux contraintes contextuelles de cardinalité maximale $\gamma_1$ : $C_1 \sqsubseteq (\le M_1 R)$ et $\gamma_2 : C_2 \sqsubseteq (\le M_2 R)$ définies sur R. La contrainte $\gamma_1$ est dite plus générale que la contrainte $\gamma_2$ si $C_2 \sqsubseteq C_1$ et $M_1 \le M_2$. Etant donné un ensemble de contraintes $\Gamma$ définies sur R, une contrainte $\gamma_1 \in \Gamma$ est dite minimale dans $\Gamma$ s'il n'existe aucune contrainte $\gamma_2$ dans $\Gamma$ plus générale que $\gamma_1$.*

Par exemple, la contrainte contextuelle (dbo:Person) $\sqsubseteq$ ($\le 2$ dbo:nationality) est plus générale que la contrainte contextuelle (dbo:Person $\sqcap \exists$ dbo:nationality.{$China$}) $\sqsubseteq$ ($\le 5$ dbo:nationality) car (dbo:Person $\sqcap \exists$ dbo:nationality.{$China$}) $\sqsubseteq$ dbo:Person) et $2 \le 5$.

La notion de minimalité a pour objectif de ne pas extraire de contraintes contextuelles qui soient redondantes. Intuitivement, considérons les deux contraintes $\gamma_1$ et $\gamma_2$ introduites dans la définition précédente, et supposons que $\gamma_1$ soit plus générale que $\gamma_2$. Etant donnée une base de connaissances $\mathcal{K}$ dans laquelle les contraintes $\gamma_1$ et $\gamma_2$ sont satisfaites, soit une instance $s$ de $C_2$ dans $\mathcal{K}$. D'après $\gamma_2$, nous savons que pour toute interprétation $\mathcal{I}$ de $\mathcal{K}$, $\#\{o : (s, o) \in R^I\} \le M_2$. Mais comme $\gamma_1$ est plus générale que $\gamma_2$, nous savons par définition que $C_2 \sqsubseteq C_1$. Il en découle que $s$ est aussi une instance de $C_1$ dans $\mathcal{K}$, et d'après $\gamma_1$, que pour tout interprétation $\mathcal{I}$ de $\mathcal{K}$, $\#\{o : (s, o) \in R^I\} \le M_1$, ce qui est une contrainte plus forte que $\#\{o : (s, o) \in R^I\} \le M_2$. En effet, par définition de la minimalité, nous savons que $M_1 \le M_2$. Par rapport à la contrainte $\gamma_1$, la contrainte $\gamma_2$ est donc inutile car redondante, i.e. elle ne permet pas de déduire d'information supplémentaire.

Le problème traité dans ce papier est alors le suivant : *étant donnés une base de connaissances $\mathcal{K}$, un rôle $R$ et une hiérarchie de concepts ($C, \sqsubseteq$), nous cherchons à découvrir l'ensemble des contraintes contextuelles de cardinalité maximale de la forme $C \sqsubseteq (\le MR)$ avec $C \in \mathcal{C}$, qui soient satisfaites sur $\mathcal{K}$ et minimales dans $\mathcal{C}$.*

En pratique, une base de connaissances telle que DBpedia est très incomplète (par exemple, de nombreuses personnes ont seulement un parent), et elle comporte de nombreuses incohérences (par exemple, des personnes peuvent avoir jusqu'à 5 parents). Pour ces raisons, étant donnée une base de connaissances $\mathcal{K}$, il n'est pas pertinent de chercher à extraire des contraintes de cardinalité qui soient parfaitement satisfaites dans $\mathcal{K}$, mais les contraintes :

- les plus probables et suffisamment probables par rapport à un seuil donné, de manière à prendre en compte et tolérer les incohérences, et

- suffisamment certaines par rapport à un degré de confiance, pour ne pas extraire des contraintes qui soient remises en cause régulièrement par l'ajout de nouveaux faits dans la base de connaissances.

Nous détaillons dans la section suivante comment évaluer la probabilité qu'une contrainte soit satisfaite dans une base de connaissances $\mathcal{K}$ et comment mesurer la certitude que cette contrainte soit réelle.

# 4 Extraction de contraintes contextuelles de cardinalité maximale

Pour résoudre le problème énoncé précédemment, nous commençons par le reformuler en introduisant la notion de taux de cohérence dans la section 4.1, puis nous décrivons dans la section 4.2 comment détecter une cardinalité maximale pour un rôle $R$ dans un contexte $C$. Ensuite, étant donné un ensemble de contextes candidats $\mathcal{C}$, nous montrons dans la section 4.3 comment explorer efficacement l'ensemble des contraintes contextuelles possibles.

## 4.1 Taux de cohérence

Etant donnée une base de connaissances $\mathcal{K} = (\mathcal{T}, \mathcal{A})$, supposons que $i$ soit la cardinalité maximale du rôle $R$ dans le contexte $C$. Soit $s$ un individu de $\mathcal{C}$ dans $\mathcal{K}$, complet pour le rôle $R$ dans $\mathcal{K}$ (dans le sens où tous les faits $R(s, o)$ possibles représentant le monde réel sont dans $\mathcal{A}$ ou inférables). Dans le cas où il existe exactement $i$ faits dans $\mathcal{K}$ de la forme $R(s, o)$, cela renforce l'hypothèse que $i$ soit la cardinalité maximale de $R$ dans le contexte $C$. Inversement, s'il existe plus de $i$ faits dans $\mathcal{K}$ de la forme $R(s, o)$, cela affaiblit l'hypothèse que $i$ soit la cardinalité maximale de $R$ dans le contexte $C$. Ainsi dans le tableau 1, pour la classe dbo:Person, les individus comportant au moins 3 assertions pour le rôle dbo:parent affaiblissent l'hypothèse que la cardinalité maximale soit 2 mais ils restent peu nombreux au regard des 9 392 individus qui ont exactement 2 parents.

En suivant ce raisonnement, nous introduisons la notion de
taux de cohérence pour évaluer si une cardinalité *i* pour le rôle *R* dans le contexte *C* a des chances d'être maximale :

**Définition 4.1** (Taux de cohérence). Etant donnée une base de connaissances $\mathcal{K}$, le taux de cohérence de la cardinalité $i$ pour le rôle $R$ dans le contexte $C$ est le ratio :

$$ \tau_i^{C,R}(\mathcal{K}) = \frac{n_i^{C,R}}{n_{\ge i}^{C,R}} $$

où $n_i^{C,R}$ (resp. $n_{\ge i}^{C,R}$) représente le nombre de sujets s tels que $i$ faits $R(s, o)$ (resp. $i$ faits ou plus) appartiennent à $\mathcal{K}$ dans le contexte $C$.

Par exemple, dans le tableau 1, $n_{\ge 2}^{\text{dbo:Person,dbo:parent}}$ est égal à 9477 (9477 = 9392+75+9+1). De cette manière, le taux de cohérence $\tau_2^{\text{dbo:Person,dbo:parent}}(\mathcal{K})$ est de 0,991 (i.e., 9392/9477). Par la suite, quand le contexte et la relation sont clairs, nous pouvons les omettre dans les notations. Dans ce cas, $n_i$ et $\tau_i$ désignent respectivement les termes $n_i^{C,R}$ et $\tau_i^{C,R}$.

Maintenant nous allons formaliser le lien entre le taux de cohérence et la notion de contrainte maximale. Originellement introduit dans [13], $\mathcal{K}^* = (\mathcal{T}^*, \mathcal{A}^*)$ désigne une hypothétique base de connaissances idéale qui contiendrait tous les axiomes et toutes les assertions du monde réel. Comme $\mathcal{K}^*$ est correcte et complète, le taux de cohérence au sein de $\mathcal{K}^*$, noté $\tau_M^{C,R}(\mathcal{K}^*)$, est égal à 1 si et seulement si $C \subseteq (\le M R)$ appartient à $\mathcal{T}^*$.

En pratique, le taux de cohérence mesuré dans une base de connaissances est différent du taux de cohérence réel : $\tau_i(\mathcal{K}) \neq \tau_i(\mathcal{K}^*)$. Par exemple, le taux de cohérence $\tau_2(\mathcal{K})$ pour le rôle `dbo:parent` du tableau 1 est égal à 0,991 alors que le taux de cohérence réel est égal à 1. Plus grave, on a $\tau_6^{\text{dbo:Person,dbo:parent}}(\mathcal{K}) = 1!$ Le taux de cohérence sur $\mathcal{K}$ est donc une estimation peu fiable du taux de cohérence réel sur $\mathcal{K}^*$.

## 4.2 Détection d'une contrainte

L'estimation $\tau_i(\mathcal{K})$ de $\tau_i(\mathcal{K}^*)$ doit être corrigée pour être statistiquement valide. Pour ce faire, nous proposons d'utiliser l'inégalité de Hoeffding qui a l'avantage d'être vraie pour toute distribution. En terme de probabilité, si $X$ est une variable aléatoire indiquant pour un sujet $s$ tiré aléatoirement, le nombre de faits $R(s, o)$ appartenant à $\mathcal{K}$, alors $\tau_i$ est une estimation fréquentielle de la probabilité conditionnelle $P(X = i | X \ge i)$. Etant donné un niveau de confiance $1 - \delta$, l'inégalité de Hoeffding stipule que $\tau_i(\mathcal{K}^*)$ est compris entre $\tau_i(\mathcal{K}) - \epsilon_i$ et $\tau_i(\mathcal{K}) + \epsilon_i$ où $\epsilon_i = \sqrt{\frac{\log(1/\delta)}{2n_i}}$. Dans ce contexte, afin de prendre des décisions les plus sûres, nous proposons d'utiliser la borne inférieure de l'intervalle de confiance $[\tau_i - \epsilon_i, \tau_i + \epsilon_i]$. Plus formellement, on a la propriété suivante :

**Propriété 4.1** (Minoration). Etant données une base de connaissances $\mathcal{K}$ et une confiance $1 - \delta$, le taux de

cohérence réel $\tau_i(\mathcal{K}^*)$ de la cardinalité $i$ pour le rôle $R$ dans le contexte $C$ est supérieur à $\tilde{\tau}_i(\mathcal{K})$ :

$$ \tau_i(\mathcal{K}^*) \geq \tilde{\tau}_i(\mathcal{K}) $$

où $\tilde{\tau}_i(\mathcal{K})$ est le taux de cohérence pessimiste défini par :

$$ \tilde{\tau}_i(\mathcal{K}) = \max \left\{ \frac{n_i}{n_{\ge i}} - \sqrt{\frac{\log(1/\delta)}{2n_{\ge i}}}; 0 \right\} $$

Cette propriété nous munit d'un outil efficace pour approximer le taux de cohérence réel. Il survient alors la difficulté de choisir la cardinalité maximale une fois que l'on dispose pour chaque cardinalité $i$ du taux de cohérence pessimiste $\tilde{\tau}_i(\mathcal{K})$ (pour un rôle $R$ dans le contexte $C$).

Plus précisément, étant donnés un seuil minimal de cohérence $min_\tau$ et un niveau de confiance $1 - \delta$, nous considérons que $M$ est la cardinalité maximale de $R$ dans le contexte $C$ si et seulement si $\tilde{\tau}_M \geq min_\tau$ et $M = \arg\max_{i \geq 1} \tilde{\tau}_i(\mathcal{K})$.

Quelques exemples d'estimations $\tilde{\tau}_i$ et de détection de cardinalités maximales contextuelles sont donnés dans la table 1. Dans les 3 exemples, on a considéré `dbo:Person` comme contexte, et on a cherché à détecter la cardinalité maximale contextuelle de trois rôles : `dbo:birthYear`, `dbo:parent` et `dbo:nationality`. Intuitivement, pour les deux premiers rôles, on souhaiterait détecter des cardinalités maximales respectives de 1 et 2. Pour un niveau de confiance $1 - \delta = 99\%$ et un seuil $min_\tau = 0.97$, on constate que les cardinalités maximales supposées sont effectivement détectées (cf. lignes en gras dans la table 1). De manière intéressante, avec ces mêmes seuils, aucune cardinalité n'est détectée pour `dbo:nationality`.

## 4.3 Exploration de l'espace de recherche

Etant donnés une base de connaissances $\mathcal{K}$, un rôle $R$, une arborescence de concepts $(C, \sqsubseteq)$, un degré de confiance $\delta$ et un seuil minimal de cohérence $min_\tau$, nous cherchons à découvrir l'ensemble des contraintes contextuelles de cardinalité maximale de la forme $C \subseteq (\le M R)$ avec $C \in \mathcal{C}$, qui soient minimales et suffisamment certaines sur $\mathcal{K}$. En pratique, notons que l'arborescence $(C, \sqsubseteq)$ peut être une arborescence déjà existante dans la TBox de la base de connaissances, ou une arborescence construite dans une phase préalable de préparation des données (voir la section 5.1).

Dans un tel cadre, il y a potentiellement un très grand nombre de contraintes contextuelles à considérer, évaluer et comparer. Néanmoins, il est possible de réduire la taille de l'espace de recherche à explorer en se basant sur les propriétés 4.2 et 4.3 énoncées ci-après. Tout d'abord, la propriété 4.2 montre qu'une contrainte $C \subseteq (\le M R)$ ne peut pas être suffisamment certaine si le contexte $C$ contient trop peu d'individus dans $\mathcal{K}$, car alors l'intervalle de confiance du taux de cohérence calculé grâce à l'inégalité de Hoeffding est très large et sa borne inférieure ne peut être supérieure au seuil $min_\tau$ imposé.
**Propriété 4.2** (Nombre minimal d'observations). *Etant donnés une base de connaissances K, une contrainte contextuelle de cardinalité maximale C ⊑ (≤ M R) et un seuil min<sub>τ</sub>, le taux de cohérence $\tilde{\tau}_M(K)$ que M soit la cardinalité maximale de R dans C ne peut être supérieur à min<sub>τ</sub> que si |C| ≥ log(1/δ) / (2(1-min<sub>τ</sub>)<sup>2</sup>).*

Par ailleurs, supposons qu'une contrainte $\gamma$ définie par $C \sqsubseteq (\leq M R)$ avec $M = 1$ ait été détectée comme suffisamment certaine au cours de l'exploration. Alors, d'après la propriété 4.3, il n'est pas nécessaire d'explorer les contraintes $\gamma'$ définies par $C' \sqsubseteq (\leq M' R)$ où $C'$ est plus spécifique que $C$. Cette propriété découle directement de la définition 3.2 de la minimalité.

**Propriété 4.3** (Contrainte minimale). *Soient une base de connaissances K et une contrainte contextuelle de cardinalité maximale $\gamma$ définie par $C \sqsubseteq (\leq M R)$ avec $M = 1$. Toute contrainte $\gamma'$ définie par $C' \sqsubseteq (\leq M' R)$ avec $C' \sqsubseteq C$ et $M' \geq 1$ ne peut être minimale.*

L'algorithme 1 détaille notre fonction récursive d'exploration, la fonction C3M (pour *Contextual Cardinality Constraint Mining*). Cette fonction prend en entrée une base de connaissances, un rôle à explorer, un contexte courant, une cardinalité maximale courante ($M = \infty$ si aucune cardinalité maximale n'a encore pu être détectée), et enfin, des seuils $\delta$ et $min_{\tau}$. Le démarrage de l'exploration d'une arborescence de racine $\top$ se fait en exécutant la fonction $C3M(K, R, \top, \infty, \delta, min_{\tau})$.

Pour commencer, la fonction C3M détermine si le nombre d'individus est suffisant dans le contexte C. Si ce n'est pas le cas, elle arrête l'exploration à la ligne 2 conformément à la propriété 4.2. Sinon, le taux de cohérence $\tilde{\tau}_i$ est calculé pour chaque cardinalité i (lignes 4 à 6) et la ligne 7 retient la cardinalité maximale la plus probable. Si le taux de cohérence correspondant n'est pas supérieur au seuil $min_{\tau}$, alors cela signifie qu'aucune cardinalité maximale n'a pu être détectée à ce niveau et $i_M$ est fixé ligne 8 à $\infty$. Ensuite, si la cardinalité maximale détectée $i_M$ est strictement inférieure à M (la cardinalité maximale détectée au niveau précédent), alors on dispose d'une nouvelle contrainte minimale de cardinalité maximale $i_M$ et on l'ajoute à $\Gamma$, l'ensemble des contraintes recherchées. Finalement, conformément à la propriété 4.3, si $i_M$ est égale à 1, il n'est pas nécessaire de poursuivre l'exploration en parcourant les contextes plus spécifiques de C. Sinon, la fonction C3M est appelée récursivement à la ligne 12 pour tous les $C'$ qui sont des sous-concepts directs de C.

Dans notre implémentation de la fonction C3M, nous avons appliqué une approche client-serveur où les distributions de cardinalité $n_i^{C,R}$ sont calculées par interrogation en SPARQL d'une base de connaissances localisée sur un serveur. Dans un tel cadre, la complexité de notre méthode en nombre de requêtes sur le serveur est en $O(|C|)$ où $|C|$ représente le nombre de concepts dans l'arborescence C explorée. Dans le pire des cas, côté client, la complexité en nombre d'opérations est en $O(|C| \times i_{max})$ où $i_{max}$

**Algorithm 1 C3M**

**Input:** Une base de connaissances K, un rôle R, un contexte C, un entier M, un niveau de confiance $\delta$ et un seuil minimal de support $min_{\tau}$
**Output:** Un ensemble $\Gamma$ de contraintes contextuelles de cardinalité maximale

1. $\alpha := \frac{\log(1/\delta)}{2(1-min_{\tau})^2}$ et $n_{\ge 0}^{C,R} := |C|$

2. **if** ($n_{\ge 0}^{C,R} < \alpha$) **then** $\emptyset$

3. $\Gamma := \emptyset$ et $i_{max} := \arg\max_{i \in N}\{n_i^{C,R} > 0\}$

4. **for all** $i \in [1..min\{M, i_{max}\}]$ **do**

5. $\tilde{\tau}_i := \max \left\{ \frac{n_i^{C,R}}{\sum_{j \ge i}^{n_i^{C,R}}} - \sqrt{\frac{\log(1/\delta)}{2n_i^{C,R}}} ; 0 \right\}$

6. **end for**

7. $i_M := \arg\max_{i \in [1..min\{M, i_{max}\}]}\{\tilde{\tau}_i\}$

8. **if** ($\tilde{\tau}_{i_M} < min_{\tau}$) **then** $i_M = \infty$

9. **if** ($i_M < M$) **then** $\Gamma := \{C \sqsubseteq (\leq i_M R)\}$

10. **if** ($i_M > 1$) **then**

11. **for all** $C' \in subClassOf(C)$ **do**

12. $\Gamma := \Gamma \cup C3M(K, R, C', i_M, \delta, min_{\tau})$

13. **end for**

14. **end if**

15. **return** $\Gamma$

représente l'entier maximal pour lequel il existe au moins un sujet s tel que $i_{max}$ fait $R(s, o)$ appartiennent à la base de connaissances K, i.e. $i_{max} = \arg\max_{i \in N}\{n_i^{\top,R} > 0\}$.

# 5 Expérimentations

Outre les requêtes sur DBpedia (dont nous montrons des échantillons de réponses en table 1), qui ont été utilisées pour mettre au point la définition du taux de cohérence, nous avons expérimenté l'algorithme 1 sur un jeu de données mis à notre disposition par les auteurs de [6].

## 5.1 Données et protocole

Le jeu de données utilisé porte sur le domaine numisma-tique, il est le résultat d'un processus d'intégration mené dans le cadre du projet européen ARIADNE<fnref n="2" />. Ses auteurs ont utilisé le CIDOC-CRM<fnref n="3" /> pour intégrer les contenus de 5 ressources construites par des institutions de différents pays européens. Il contient 3 123 998 triplets, dont les définitions de 114 classes et 373 rôles ou propriétés du CIDOC-CRM et d'ARIADNE. Il est stocké et interrogé avec le triplestore Blazegraph (v2.1.4), sur une machine virtuelle sous Linux avec 32 GB de mémoire virtuelle, sur un serveur ayant pour processeur un Dual Intel Xeon E5620 4 cœurs. L'algorithme 1 est implémenté en Java et utilise la bibliothèque de programmation pour RDF Jena<fnref n="4" />. La base porte sur des pièces de monnaies mais, par choix des intégrateurs, il n'existe pas de classe *Coin*. Les individus correspondant à des pièces sont des instances de E22_Man_Madeرين caracérisées par certains URIs (ex. <http://nomisma.org/id/coin>) comme va-

<footnote n="2">2. http://ariadne-infrastructure.eu/</footnote>

<footnote n="3">3. http://www ci doc-crm org/</footnote>

<footnote n="4">4. http://jena apache org/</footnote>
leur objet de certains rôles (ex. P2_has.type). Plusieurs rôles et plusieurs URIs sont utilisés pour cela, aussi nous avons décidé de construire notre propre arborescence d'exploration de la façon suivante :

Au premier niveau, notre arborescence contient tous les concepts C<sub>i</sub> de la base, soit 114 concepts (i ∈ [1..114]). Tous ces concepts sont des sous-concepts du concept racine ⊤ au niveau zéro, i.e. pour tout i, nous avons C<sub>i</sub> ⊑ ⊤. Au deuxième niveau notre arborescence contient tous les concepts C<sub>i</sub><sup>j</sup> définis par C<sub>i</sub><sup>j</sup> := C<sub>i</sub> ∩ (∃R<sub>j</sub>.⊤) où C<sub>i</sub> (i ∈ [1..114]) et R<sub>j</sub> (j ∈ [1..373]) sont respectivement des concepts et rôles de la base. A ce niveau, 42 522 concepts C<sub>i</sub><sup>j</sup> sont ainsi définis. Enfin, au troisième niveau, notre arborescence contient tous les concepts C<sub>i</sub><sup>j,k</sup> définis par C<sub>i</sub><sup>j,k</sup> := C<sub>i</sub> ∩ (∃R<sub>j</sub>.{a<sub>k</sub>}) où C<sub>i</sub> (i ∈ [1..114]) et R<sub>j</sub> (j ∈ [1..373]) sont respectivement des classes et rôles de la base, et a<sub>k</sub> est un individu du co-domaine de R<sub>j</sub>, i.e. a<sub>k</sub> ∈ (∃R<sub>j</sub><sup>-1</sup>.⊤). Grâce à ce dernier niveau, il est possible de considérer des contextes à la manière de notre exemple jouet où dbo:Person ∩ ∃dbo:nationality.{China}. Notons finalement que pour tout i, j, k, nous avons C<sub>i</sub><sup>j,k</sup> ⊑ C<sub>i</sub><sup>j</sup> ⊑ C<sub>i</sub>. Globalement, cette arborescence comporte 3 160 357 concepts, donc pour les 373 rôles de la base de connaissances cela représente plus d'un milliard de contraintes contextuelles possibles (exactement 1 178 813 161 contraintes). Néanmoins, comme nous le verrons dans la section suivante, l'utilisation des propriétés 4.2 et 4.3 permet d'élaguer une grande partie de l'espace de recherche.

## 5.2 Résultats

Tous les résultats présentés dans cette section ont été obtenus avec un **seuil minimal de confiance** $1 - \delta = 0,99\%$ (pour des contraintes les plus certaines possibles) et un **seuil minimal de cohérence** $min_{\tau} = 0,95$ (pour des contraintes suffisamment probables). Ce seuil a été défini expérimentalement. Sur des bases de connaissances de plus grande taille comme DBpedia, un seuil plus élevé est préférable. Néanmoins, l'approche est relativement peu sensible aux seuils (i.e., l'ensemble des contraintes trouvées est stable).

**Analyse quantitative.** Avec ces paramètres, la propriété 4.2 nous indique qu'une contrainte $C \subseteq (\leq M R)$ ne peut être suffisamment certaine si son contexte $C$ contient moins de $\alpha = \frac{\log(1/\delta)}{2(1-min_{\tau})^2} = 922$ instances. Ainsi, l'utilisation de la propriété 4.2 permet de n'explorer que 16 641 contraintes, soit moins de 0,002% des plus de 1 milliard de contraintes possibles. Qui plus est, notre expérience montre que la propriété 4.3 permet de réduire encore de 82,5% la taille de l'espace de recherche à explorer. Au final, avec les seuils choisis notre algorithme ne cherche à détecter une cardinalité maximale que pour 2 909 contextes possibles, avec un temps de calcul complet de moins de 50 minutes.

La table 2 donne une vue globale et quantitative du résultat de l'exploration réalisée. Sur les 2 909 contraintes contextuelles possibles, notre algorithme a détecté au total 887 contraintes de cardinalité maximale, 595 d'entre elles étant des contraintes minimales. Sur cet exemple, le critère de minimalité permet donc de réduire de près de 67% le nombre de contraintes retournées. On constate que les contraintes les plus nombreuses sont des cardinalités maximumes avec $M = 1$, ce qui correspond à des contraintes où pour un rôle donné $R$, tout sujet $s$ est en relation avec au plus un objet $o$. Néanmoins de très nombreuses contraintes sont trouvées avec des cardinalités maximales $M \in \{2, 3\}$ (37% des contraintes minimales détectées). On note également que si des contraintes de cardinalités maximumes sont détectées dès le niveau 0 (65 contraintes avec un contexte $C \equiv \top$), la recherche de contraintes contextuelles est particulièrement pertinente. Il faut en effet noter que les contraintes les plus nombreuses sont trouvées au niveau 3 (75% des contraintes détectées), sachant que par construction de notre arborescence, c'est à ce niveau que sont caractérisées les pièces de monnaie.

<table><caption>TABLE 2 – Répartition par niveau et cardinalité maximale $M$ des contraintes minimales détectées</caption><thead><tr><th rowspan="2">M</th><th colspan="4">Niveau dans l'arborescence</th><th rowspan="2">Total</th></tr><tr><th>0</th><th>1</th><th>2</th><th>3</th></tr></thead><tbody><tr><td>1</td><td>60</td><td>28</td><td>10</td><td>222</td><td>320</td></tr><tr><td>2</td><td>3</td><td>6</td><td>9</td><td>90</td><td>108</td></tr><tr><td>3</td><td>0</td><td>7</td><td>14</td><td>92</td><td>113</td></tr><tr><td>4</td><td>1</td><td>0</td><td>8</td><td>20</td><td>29</td></tr><tr><td>5</td><td>1</td><td>0</td><td>0</td><td>16</td><td>17</td></tr><tr><td>6</td><td>0</td><td>0</td><td>0</td><td>8</td><td>8</td></tr></tbody><tfoot><tr><th>Total</th><td>65</td><td>41</td><td>41</td><td>448</td><td>595</td></tr></tfoot></table>

Analyse qualitative. Tout d'abord, dès le niveau 0, notre méthode permet de retrouver des contraintes fonctionnelles attendues, par exemple, pour les 3 rôles du CIDOC-CRM P1_is_identified_by, P52_has_current的家庭 et P50_has_current_keeper, indiquant que si un sujet décrit dans la base possède plus d'un identifiant, un propriétaire ou un conservateur, alors on peut en déduire que ces identifiants (respectivement, propriétaires et conservateurs) sont identiques. Concernant le rôle P45_consists_of du CIDOC-CRM (permettant de décrire les matériaux constitutifs d'un objet), il est intéressant de noter qu'une cardinalité maximum de 2 est détectée dès le niveau 1 pour la classe E22_Man_Made. La base de connaissances décrit notamment des médailles constituées d'or et de pierre précieuse (telle l'agate). Pour ce même rôle, une cardinalité maximale de 1 est détectée au niveau 3 pour les pièces de monnaie. Cette information est notamment représentée par la contrainte E22_Man_MadeObject ∩ ∃P2_has_type.{<http://nomisma.org/id/coin>} ⊑ (≤ 1 P45_consists_of). Cette contrainte est détectée bien qu'à certaines pièces la relation P45_consists_of associate deux matériaux; mais c'est rare (et le plus souvent il
s'agit du même matériau dans deux langues différentes). Un même type de contrainte (avec $M = 1$) est trouvée au niveau 3 pour tous les contextes décrivant des pièces, concernant le rôle *P62Depicts* (ce qui est dépeint sur l'objet). C'est raisonnable car dans le cas d'une pièce de monnaie, on trouve le plus souvent une seule représentation figurative (sur une des deux faces de la pièce), alors qu'une telle contrainte n'est pas valide pour d'autres objets.

Au passage, l'étude de l'ensemble des contraintes extraites par notre méthode a mis en évidence des redondances dans la base, sans doute du fait des choix d'intégration. Dans une phase de post-traitement, la connaissance d'axiomes tel que $∃P2\_has\_type.\{...coin\}$, $∃Thing\_has\_type\_Concept.\{...moneta\}$ pourrait réduire encore le nombre de contraintes extraites.

## 6 Conclusion

Nos expérimentations démontrent la faisabilité d'une exploration systématique d'une base de connaissances, à la recherche de contraintes contextuelles de cardinalité maximum, grâce à l'algorithme que nous proposons dans cet article : dans le cas étudié, cela prend moins d'une heure pour une base de connaissances contenant plus de 3 millions de triplets, décrits par une centaine de concepts et plus de 300 rôles. Les propriétés utilisées par notre algorithme font que seules 595 contraintes ont été obtenues, ce qui reste analyisable manuellement. Cela nous a permis de vérifier que ces contraintes sont bien pertinentes dans le contexte de la base étudiée. De plus, nos expérimentations démontrent l'importance du contexte dans cette découverte de contraintes. Il s'agit à notre connaissance de la première proposition de calcul de contraintes contextuelles de cardinalité maximum dans une base de connaissances du web sémantique. Ces grandes bases de connaissances, reflet d'une intelligence collective, sont générées à partir de l'expertise limitée de nombreux contributeurs et souffrent encore, tantôt de lacunes dans les informations, tantôt d'incohérences. Utiliser leurs contenus courants afin de mieux caractériser les connaissances représentées est donc très utile, comme montré dans l'état de l'art : cela permet aux applications qui exploitent ces grandes bases de connaissances de produire des résultats plus fiables.

Nous avons donc pour perspective d'exploiter les contraintes extraites pour calculer la confiance associée à des règles découvertes dans la base de connaissances ainsi enrichie. Mais avant cela, nous travaillons sur des post-traitements pour réduire encore le nombre de contraintes représentées en résultat. Pour cela, nous explorons le potentiel des raisonnements possibles sur la TBox, en particulier comment les relations de subsomption entre classes peuvent éliminer des redondances dans les ensembles de contraintes extraites.

## Références

[1] Atencia, M., David, J., Scharffe, F. : Keys and pseudo-keys detection for web datasets cleansing and interlinking. In :

EKAW. pp. 144–153. Springer (2012)

[2] Auer, S., Bizer, C., Kobilarov, G., Lehmann, J., Cyganiak, R., Ives, Z. : Dbpedia : A nucleus for a web of open data. In : The semantic web, pp. 722–735. Springer (2007)

[3] Baader, F., Sattler, U. : Expressive number restrictions in description logics. Journal of Logic and Computation 9(3), 319–350 (1999)

[4] Darari, F., Nutt, W., Pirrò, G., Razniewski, S. : Completeness statements about rdf data sources and their use for query answering. In : ISWC. pp. 66–83. Springer Berlin Heidelberg (2013)

[5] Darari, F., Razniewski, S., Prasojo, R.E., Nutt, W. : Enabling Fine-Grained RDF Data Completeness Assessment. In : Web Engineering. pp. 170–187. Springer International Publishing, Cham (2016)

[6] Felicetti, A., Gerth, P., Meghini, C., Theodoridou, M. : Integrating heterogeneous coin datasets in the context of archaeological research. In : EMF-CRM@ICTPDL. pp. 13–27. CEUR-WS.org (2015)

[7] Galárraga, L., Razniewski, S., Amarilli, A., Suchanek, F.M. : Predicting completeness in knowledge bases. In : WSDM. pp. 375–383. ACM (2017)

[8] Galárraga, L.A., Teflioudi, C., Hose, K., Suchanek, F. : Amie : Association rule mining under incomplete evidence in ontological knowledge bases. In : WWW. pp. 413–422. ACM (2013)

[9] Galárraga, L., Hose, K., Razniewski, S. : Enabling Completeness-aware Querying in SPARQL. In : Proceedings of WebDB. pp. 19–22. ACM (2017)

[10] Lajus, J., Suchanek, F.M. : Are All People Married? Determining Obligatory Attributes in Knowledge Bases. In : WWW (2018)

[11] Pernelle, N., Saïs, F., Symeonidou, D. : An automatic key discovery approach for data linking. Web Semantics : Science, Services and Agents on the World Wide Web 23, 16–30 (2013)

[12] Razniewski, S., Korn, F., Nutt, W., Srivastava, D. : Identifying the extent of completeness of query answers over partially complete databases. In : SIGMOD. pp. 561–576. ACM (2015)

[13] Razniewski, S., Suchanek, F., Nutt, W. : But what do we actually know ? In : 5th Workshop on Automated Knowledge Base Construction. pp. 40–44 (2016)

[14] Soutou, C. : Relational database reverse engineering : algorithms to extract cardinality constraints. Data & Knowledge Engineering 28(2), 161–207 (1998)

[15] Symeonidou, D., Armant, V., Pernelle, N., Saïs, F. : Sakey : Scalable almost key discovery in RDF data. In : ISWC. pp. 33–49. Springer (2014)

[16] Symeonidou, D., Galárraga, L., Pernelle, N., Saïs, F., Suchanek, F. : Vickey : Mining conditional keys on knowledge bases. In : ISWC. pp. 661–677. Springer (2017)

[17] Tanon, T.P., Stepanova, D., Razniewski, S., Mirza, P., Weikum, G. : Completeness-aware rule learning from knowledge graphs. In : ISWC. pp. 507–525. Springer (2017)

[18] Yeh, D., Li, Y., Chu, W. : Extracting entity-relationship diagram from a table-based legacy database. Journal of Systems and Software 81(5), 764–771 (2008)
# Activité AfIA

## 1er août 2016 – 31 juillet 2018

Éditeurs : Conseil d'Administration de l'AfIA – Année 2018
<figure><img src="image_108.png" /></figure>
Table des matières

<table><tr><td>Flyer AflA 2018.<br>À propos de l'AflA</td><td>v</td></tr><tr><td>Conseil d'Administration de l'AflA.<br>CA AflA</td><td>vii</td></tr><tr><td>Collèges AflA.<br>Collèges RR, SIC et SMAA</td><td>ix</td></tr><tr><td>Prix de Thèse IA.<br>2017 et 2018</td><td>xv</td></tr><tr><td>Bulletins Trimestriels.<br>Du n°094 au n°101</td><td>xvii</td></tr><tr><td>Journées propres.<br>PDIA et FIIA</td><td>xix</td></tr><tr><td>Compétitions.<br>Compétitions</td><td>xxv</td></tr><tr><td>Journées communes.<br>Journées communes</td><td>xxix</td></tr><tr><td>Plates-formes IA.<br>PFIA 2017, PFIA 2018</td><td>xlvii</td></tr></table>
<figure><img src="image_109.png" /></figure>
# A propos de l'AFIA

L'objet de l'AFIA, Association Loi 1901 sans but lucratif, est de promouvoir et de favoriser le développement de l'Intelligence Artificielle (IA) sous ses différentes formes, de regrouper et de faire croître la communauté française en IA, et, à la hauteur des forces de ses membres, d'en assurer la visibilité.

L'AFIA anime la communauté par l'organisation de grands rendez-vous annuels. L'AFIA organise ainsi chaque année une semaine de l'IA, la « Plate-forme IA » (PFIA 2017 Caen, PFIA 2018 Nancy) au sein de laquelle se tiennent la « Conférence Nationale d'Intelligence Artificielle » (CNIA), les « Rencontres des Jeunes Chercheurs en IA » (RJCIA) et la « Conférence sur les Applications Pratiques de l'IA » (APIA) ainsi que des conférences thématiques qui peuvent évoluer d'une année à l'autre, sans récurrence obligée.

C'est ainsi que du 2 au 6 juillet 2018 à Nancy, lors de son édition 2018, la Plate-Forme IA hébergera, outre les 21ème CNIA, 16ème RJCIA et 4ème APIA, les 29èmes IC et les 13èmes JFPDA. Y sont également programmées cinq journées communes organisées avec d'autres associations ou institutions. La Plate-Forme IA 2018, quant à elle, se tiendra du 1au 5 juillet 2019 à Toulouse, dates à réserver sur vos agendas !

Forte du soutien de ses 514 adhérents à jour de leur cotisation en 2017, l'AFIA assure :

* Le maintien d'un [Site Web](#) dédié à l'IA, reproduisant également les Brèves de l'IA,

* Une journée recherche annuelle sur les Perspectives et Défis en IA ([PDIA 2017](#)),

* Une journée industrielle annuelle ou [Forum Industriel en IA (FIIA 2018)](#),

* La remise annuelle d'un [Prix de Thèse](#) de Doctorat en IA,

* Le soutien à plusieurs [Collèges](#), actuellement au nombre de 4, ayant leur propre activité :

* Collège Industriel (depuis janvier 2016),

* Collège Science de l'Ingénierie des Connaissances (depuis avril 2016),

* Collège Systèmes Multi-Agents et Agents Artificiels (depuis octobre 2016),

* Collège Représentation et Raisonnement (depuis avril 2017)

* La parution trimestrielle des [Bulletins](#) de l'AFIA, en accès libre à tous depuis le site web,

* Un lien entre adhérents sur les réseaux sociaux [LinkedIn](#), [Facebook](#) et [Twitter](#),

* Le [parrainage](#), scientifique, mais aussi éventuellement financier, aux événements en IA,

* La diffusion mensuelle de Brèves sur les actualités de l'IA en France ([inscription](#) aux Brèves)

* La réponse aux consultations officielles ou officieuses (Ministères, Missions, Organismes)

* La réponse aux questions de la presse écrite et de la presse orale, également sur internet.

L'AFIA organise aussi mensuellement des Journées communes avec d'autres Associations (en 2018 : EGC & IA avec EGC, Santé & IA avec AIM, TAL & IA avec ATALA, Statistiques et IA avec la SFdS) et avec d'autres institutions (en 2018 : Ethique & IA avec INRIA/COERLE, IA pour l'Education avec la MEN/DNE, Rob & IA avec le CNRS / GdR Robotique).

Enfin, l'AFIA contribue à la participation de ses membres aux grands événements de l'IA. Ainsi, les membres de l'AFIA, pour leur inscription à PFIA, bénéficient-ils d'une réduction équivalente à deux fois le coût de leur adhésion à l'AFIA, leur permettant d'assister à PFIA 2018 sur 5 jours au tarif de 95,00 € !

Rejoignez-nous vous aussi et adhérez à l'AFIA pour contribuer au développement de l'IA en France. L'adhésion peut être individuelle ou, à partir de cinq adhérents, être réalisée au titre de personne morale (institution, laboratoire, entreprise). Pour adhérer, il suffit de vous rendre sur le site des [adhésions](#) de l'AFIA.

Merci également de susciter de telles adhésions en diffusant ce document autour de vous !
<figure><img src="image_110.png" /></figure>