rentes sources envisagées et d'y accéder de façon homogène. Notre approche a consisté à construire une ontologie modulaire permettant de répondre aux besoins d'exploitation propres à chaque source de données. Cette approche permet de réduire partiellement la complexité et l'hétérogénéité des données, et ainsi de faciliter le peuplement de l'ontologie. Une caractéristique commune aux observations de la Terre est qu'elles peuvent être liées via leurs propriétés topologiques spatiales et temporelles. Un préalable au peuplement de l'ontologie (i.e. la production d'entrepôts RDF), a été de convertir les différents ensembles de données géo-spatiales fournis dans des formats hétérogènes (shapefile, KML, CSV, GeoJSON, TIFF), en un format commun, JSON, voire d'assurer, le cas échéant, la compatibilité de leurs propriétés et relations spatiales et temporelles, puis de les stocker dans une base de données NoSQL MongoDB.

Nous présentons dans cet article le vocabulaire que nous avons défini pour assurer la description sémantique homogène des différents types de données sous forme d'entités ayant des propriétés spatiales et temporelles. Une partie des données géospatiales à intégrer aux méta-données d'image sont des données contextuelles mesurées à la surface de la Terre, que nous traitons comme des données de capteurs. Ce vocabulaire spécialise ainsi des vocabulaires connus du web des données (LOD pour Linked Open Data), dont SOSA<fnref n="1" /> pour les données de capteurs, GeoSPARQL [17] pour gérer les relations et coordonnées spatiales, et OWL Time<fnref n="2" /> pour traiter la dimension temporelle. De fait, nous nous sommes appuyés sur une topologie des entités, en distinguant notamment les données dynamiques, dont la validité est fournie par la composante temporelle, et les données statiques, pour lesquelles la composante spatiale joue un rôle plus primordial.

Nous montrons, à travers un cas d'étude, comment cette ontologie permet de prendre en compte les spécificités de différentes sources en termes de vocabulaire, périodicité et volume, et comment elle peut améliorer l'accès aux données. A titre d'exemple, nous avons généré des entrepôts RDF qui mettent en relation des informations sur la couverture terrestre (pourcentage de forêts, d'eau, etc.) d'une part, et des relevés de stations météorologiques (tempéramenture, humidité, etc.) d'autre part, avec les images satellites. Ce travail est mené dans le cadre du projet SparkinData visant à construire une plate-forme cloud de données d'observations de la Terre. Le cas d'étude s'appuie sur l'annotation sémantique de méta-données d'images brutes fournies par le CNES (Centre National d'Etudes Spatiales).

Le reste de l'article est organisé ainsi : la partie 2 expose des travaux liés ; en partie 3, nous présentons le modèle d'intégration ; son exploitation pour représenter en RDF les diverses sources d'informations envisagées est l'objet de la partie 4 ; la partie 5 décrit différentes stratégies mises en

oeuvre pour intégrer les données des entrepôts RDF via les relations topologiques. Enfin, nous concluons et présentons des perspectives à ce travail en partie 6.

# 2 Travaux liés

## 2.1 Modèle sémantique pour l'imagerie spatellitaire

Le projet européen TELIOS (Virtual Observatory Infrastructure for Earth Observation Data)<fnref n="3" /> a été pionnier dans l'utilisation de représentations sémantiques pour décrire des images de satellites et faciliter l'accès à des données d'observation de la Terre par des agences telles que la NASA ou l'ESA. Le cadre applicatif de ce projet est la gestion des incendies en Grèce [29]. Les images sont classifiées et représentées sous forme vectorielle, et à chaque vecteur est associée une estimation des risques d'incendie. Les vecteurs sont liés à des sources de données externes par le biais d'ontologies [28]. Ces ontologies exploitent notamment le standard stRDF qui étend RDF pour les données spatiales et temporelles ; seule la composante spatiale est exploitée dans les analyses réalisées.

Le travail de [10] et [11] a été influencé par TELEIOS. Leur système permet d'ajouter des annotations sémantiques à des images produites par des radars à synthèse d'ouverture (SAR) selon le processus suivant : 1) extraction des informations pertinentes à partir des fichiers de métadonnées des images (fichiers XML); 2) division de l'image en tuiles de tailles différentes et organisation de ces tuiles sous une forme pyramidale; 3) extraction puis transformation sous forme de vecteurs des caractéristiques de chaque tuile. Ce système est capable de trouver de l'information en utilisant des requêtes portant sur les méta-données, la sémantique et le contenu spatial des images. Cette approche associe aux images d'observation de la Terre, des données provenant des sources externes comme Corine Land Cover, Urban Atlas, Geonames et LinkedGeoData. Elle s'appuie sur un modèle ontologique, SAR, qui réutilise la taxonomie TerraSARX et étend celle de [28].

L'approche de [16] utilise à la fois des sources de données externes et des relations temporelles. Elle s'appuie sur le concept de *prisme spatio-temporel* ("space-time prism") qui décrit les caractéristiques de trajectoires. Un outil très connu pour l'analyse spatiale est le *buffer* ; il s'agit d'une zone située autour d'une région d'intérêt, mesurée dans une certaine unité spatiale. Le *prisme spatio-temporel* est similaire à un *buffer* auquel on a ajouté une dimension temporelle. Une fois la zone autour de la caractéristique d'intérêt définie, il est possible d'identifier d'autres propriétés contenues dans le *prisme spatio-temporel*. Ainsi, dans les trajectoires étudiées par [16], certains points sont caractérisés par des valeurs temporelles de type `xsd:datetime`. Les valeurs extraites déterminent si un élément est contenu ou non dans un *prisme spatio-temporel* donné.

<footnote n="1">1. https://www.w3.org/2015/spatial/wiki/SOSA/</footnote>

<footnote>_Ontology</footnote>

<footnote n="2">2. https://www.w3.org/TR/owl-time/ (10/2017)</footnote>

<footnote n="3">3. http://www.earthobservatory.eu (08/2018)</footnote>
Compte-tenu du volume d'information à gérer, la recommandation RDF DataCube du W3C [7] suggère de lier les images à des tuiles de telle sorte à faire des assertions sur les tuiles. Dans ce cadre, les tuiles sont des zones carrées géo-localisées définies suite à une décomposition de la surface de la terre à partir d'une grille. Chaque image fournie par Sentinel-2 Single Tile (S2ST) a déjà une tuile. Nous nous appuyons également sur la notion de tuile dans notre processus d'intégration.

## 2.2 Données géographiques et LOD

La collecte et l'intégration de données géographiques produites par une diversité de disciplines est au cœur du projet Digital Earth [13]. Rendre les données géographiques disponibles puis interopérables à un niveau sémantique est une préoccupation qui conduit à appliquer les principes du Linked Data [6], et ainsi exposer, partager, et intégrer les données sur le Web via des URI déréférencables [15]. Les recommandations du W3C pour publier des données spatiales sous forme de données liées du LOD attirent l'attention sur la représentation des relations spatiales et des systèmes de référence (CRS pour "Coordinate Reference Systems") [27]. Ainsi, de nombreuses ontologies et vocabulaires sont proposés pour représenter des données géospatiales volumineuses au format raster. Le W3C suggère l'ontologie RDF Data Cube (QB), combinée à d'autres ontologies standards du W3C et de l'OGC dont SSN (Semantic Sensor Network)<fnref n="4" />, OWL-Time<fnref n="5" />, SKOS<fnref n="6" />, PROV-O<fnref n="7" /> et la récente extension de DataCube pour les entités spatio-temporelles, QB4ST<fnref n="8" />.

L'OGC a introduit la notion de données géo-liées ("geolinked data") pour faire référence aux données liées géographiquement. Dans les premiers travaux, la géométrie était stockée dans un ensemble de données géospatiales séparé, et non directement comme valeur d'attributs. Cette option étant trop contraignante lorsqu'il faut comparer la géométrie de chaque entité, les entrepôts actuels mémorisent ensemble, une représentation RDF de la géométrie et des entités spatiales. [3] a identifié divers types de géométries (point, ligne ou polygone) et divers outils pour construire une représentation RDF de la géométrie (comme Geometry2RDF<fnref n="9" /> ou TripleGeo<fnref n="10" />). Il modélise aussi quatre vocabulaires pour représenter les CRS, les entités topographiques et leurs géométries. Ces ontologies étendent des vocabulaires existant et offrent deux avantages supplémentaires : l'utilisation explicite du CRS identifié par des URI pour la géométrie, et la possibilité de décrire des géométries structurées en RDF. Ces données sont publiées comme la base de données française GEOFLA.

Une autre considération à intégrer pour représenter des

données d'observations de la Terre est la différence de validité temporelle des données. Certaines données, comme la position des stations météorologiques, des villes et de la plupart des lieux administratifs, et même la couverture terrestre, sont valides pour une très longue période, plus longue que celle de l'application, et peuvent être considérées stables ou statiques. Les flux de données, au contraire, fournissent en continu de nouvelles données à intervalles de temps réguliers. Par exemple, les mesures de température sont données toutes les 3 heures par les bulletins Météo France, et des dizaines d'images satellites et leurs méta-données sont disponibles sur le serveur PEPS chaque jour.

# 3 Le modèle d'intégration

## 3.1 Rôle de la géolocalisation et de la date

<figure><img src="image_45.png" /><figcaption>FIGURE 1 – Illustration du rôle pivot de la géométrie et de la date pour associer les données par des relations spatiales et temporelles.</figcaption></figure>

Le modèle retenu pour intégrer des données aux méta-données des images repose sur l'hypothèse que ces données sont géolocalisées et datées. Pour chacune, on doit connaître a minima un point déterminé par sa latitude / longitude, ou une zone géolocalisée (appelée « géométrie » dans la Figure 1). C'est par le biais de la géométrie que des données peuvent être associées à une même image ou à une zone dans une image. Par exemple sur la Figure 1, les mesures météorologiques (humidité, température, pression) ainsi que les unités administratives (villes, régions, etc.) sont géolocalisées et couvrent une superficie plus ou moins grande. Pour comparer les géométries des données à lier, il faut les ramener à une même unité, ce qui permet de savoir quelle zone de l'image est concernée ou décrite par ces données. Les images étant datées, dès lors que les autres données sont aussi datées, comme les mesures météorologiques, il est possible de les lier par des relations temporelles, et de savoir par exemple quelles sont les températures relevées sur la zone couverte par l'image durant les 3 jours qui ont précédé la prise d'image.

Nous détaillons à présent le modèle conçu comme support à cette approche. Pour permettre l'intégration de divers types de données, ce modèle, présenté sur la Figure 2 comporte une partie générique (les trois cadres *time*, *sosa*

<footnote n="4">4. http://purl.oclc.org/NET/ssnx/ssn</footnote>

<footnote n="5">5. https://www.w3.org/TR/owl-time</footnote>

<footnote n="6">6. http://www.w3.org/2004/02/skos/core</footnote>

<footnote n="7">7. https://www.w3.org/TR/prov-o</footnote>

<footnote n="8">8. https://www.w3.org/TR/qb4st/</footnote>

<footnote n="9">9. https://github.com/boricles/geometry2rdf</footnote>

<footnote n="10">10. https://github.com/GeoKnow/TripleGeo</footnote>
<figure><img src="image_46.png" /><figcaption>FIGURE 2 – Le modèle d’intégration de données.</figcaption></figure>

et *geo* de la partie haute de la figure), composée de classes et de propriétés tirés de vocabulaires existants (respectivement OWL-Time, SOSA, GeoSPARQL), et une partie spécifique aux données à intégrer (cadres de la partie basse de la Figure 2). La partie spécifique comprend a minima un vocabulaire pour décrire les métadonnées d'images (cadre *eom* pour "Earth Observation Model") et autant de vocabulaires que de types de données à intégrer (un seul vocabulaire est mentionné ici, *mfo* "pour MétéoFrance Observation", représentant les données météorologiques).

## 3.2 Les vocabulaires réutilisés

Pour faciliter le partage de connaissances, une bonne pratique dans la construction d'ontologies consiste à identifier des ontologies existantes à réutiliser, à les connecter ou les étendre. Nous commençons donc par décrire les vocabulaires sur lesquels s'appuie la partie générique de notre modèle : OWL-Time, SOSA et GeoSPARQL, désignés par la suite respectivement par les préfixes *time*, *sosa* et *geo*. D'autres vocabulaires peuvent être réutilisés en fonction des données à intégrer pour la partie spécifique.

**Vocabulaire pour représenter méta-données d'images et données de capteurs.** Un grand nombre de modèles ont été développés pour représenter des méta-données d'observations par les communautés des sciences de la Terre et de l'environnement. O&M (Observations and Measurements), développé par le groupe SWE de l'OGC, fournit une vision utilisateur des observations. L'OGC Sensor Observation Service and Web Feature Service en a

fourni une implémentation XML (spécification XSD). Plus général, DCAT est un vocabulaire recommandé par le W3C pour publier des métadonnées de catalogues sur le Web et disponible au format RDF [22].

Pour faciliter l'intégration de données provenant de différents types de capteurs, l'ontologie SSN<fnref n="11" /> décrit des réseaux de capteurs numériques ainsi que les fonctionnalités, propriétés et mesures de ces capteurs. Construite comme une sous-couche de l'ontologie formelle DOLCE-UltraLite (DUL), SSN est générique au sens où elle ne définit pas toutes les propriétés spécifiques à des capteurs et des observations particuliers. En revanche, on peut la lier à des ontologies ou des vocabulaires propres à un domaine tels que l'ontologie SWEET (Semantic Web for Earth and Environmental Terminology) qui décrit des données environnementales [24]. Pour faciliter sa réutilisation, et éviter les risques d'incompatibilité notamment avec les déclarations DUL, une version modulaire de SSN a été publiée. Elle est composée de plusieurs ontologies couvrant le même domaine, mais avec une portée sémantique différente pour s'adapter à des contextes d'utilisation différents. SOSA (Sensor, Observation, Sample, and Actuator) est le module ontologique noyau de la nouvelle version de SSN ; à ce titre, il regroupe les termes centraux de l'ontologie. [9] proposent des alignements entre différents modèles de données d'observations, dont SOSA, à l'aide de l'ontologie PROV-O, pour faciliter l'intégration des données produites

<footnote n="11">11. https://www.w3.org/TR/vocab-ssn/</footnote>
avec chacun d'eux. Les axiomes d'alignement sont fournis en RDF dans un module de la spécification SOSA/SSN. Ils s'appuient notamment sur le fait qu'une observation dans le vocabulaire SOSA (sosa:Observation) est considérée comme une activité (prov:Activity) de capteur, i.e. tout processus (calcul, simulation, interprétation, etc.) appliquant une procédure pour obtenir une estimation d'une valeur de propriété. La classe sosa:Observation y est ainsi définie comme une sous-classe de prov:Activity. Nous avions dans un premier temps fait le choix de DCAT et SSN pour représenter respectivement les catalogues de méta-données d'images et les données issues de stations météorologiques [1, 2]. SOSA étant pertinent pour une vaste gamme d'applications, dont l'imagerie satellite, nous l'avons finalement retenu pour représenter à la fois les méta-données d'image et les données météorologiques.

**Vocabulaire pour représenter la composante spatiale des données.** Pour représenter l'information géospatiale, une des normes les plus connues est GeoSPARQL, un standard de l'OGC qui définit une petite ontologie pour la représentation de caractéristiques, de relations et de fonctions spatiales [17, 4, 23]. Le cadre geo de la Figure 2 présente les principales classes de GeoSPARQL. La classe geo:Feature représente toute entité du monde réel ayant une empreinte spatiale. Cette empreinte est décrite par une "géométrie" (point, polygone, etc.), instance de la classe geo:Geometry. Une entité est liée à sa géométrie via la propriété geo:hasGeometry. Les coordonnées d'une géométrie sont décrites via la propriété geo:asWKT. Il est possible de lier GeoSPARQL à une ontologie de n'importe quel domaine en spécialisant la classe geo:Feature par une classe de l'ontologie de domaine considérée.

Parmi les alternatives à GeoSPARQL, GeoRDF sert à représenter des propriétés géographiques de points telles que la latitude, la longitude, l'altitude (en utilisant WGS84 comme référentiel); GeoOWL permet de représenter l'empreinte d'objets spatiaux plus complexes (lignes, retangles, polygones); stSPARQL est une autre extension de SPARQL conçue pour interroger des graphes RDF spatio-temporels [18, 5]. Nous avons retenu GeoSPARQL car il offre la possibilité de raisonner sur des entités (geo:Feature) ayant une forme géométrique (geo:Geometry), à savoir proposer des relations entre des entités sur la base des relations entre leurs géométries (inclusion, recouvrement, etc). GeoSPARQL assure l'expression de relations spatiales binaires sous forme de propriétés des geometries et des features, et de fonctions servant à les comparer sur la base des propriétés. Parmi les fonctions spatiales de GeoSPARQL, on peut citer equals, disjoint, intersects, touches, within, contains, overlaps, et crosses. Grâce à des requêtes utilisant ces fonctions, il est possible de comparer, à la volée, deux geometries ou deux features, ou de comparer une ressource géolocalisée à une position fournie expliquement. La requête GeoSPARQL ci-après recherche les "objets" situés dans (fonction GeoSPARQL sfWithin) un

polygone (un triangle) défini par les coordonnées de ses trois sommets :

```sql
select ?obj_loc
WHERE (
    ?obj_loc a geo:Feature .
    ?obj_loc geo:hasGeometry ?geo_obj .
    FILTER ( geof:sfWithin( ?geoobs , "POLYGON ((-3.562096 42.073807, -0.442349999999998 42.476536, -0.789792999999997 43.973148) )"^geo:wktLiteral) )
)
```

**Vocabulaire pour représenter la composante temporelle des données.** Parmi les modèles de données et langages de requête du web sémantique gérant la composante temporelle de données, on trouve OWL-Time<fnref n="12" />, le standard du W3C, et SWRL Temporal Ontology. Le cadre *time* de la Figure 2 présente les principales classes de OWL Time. La classe *time:TemporalEntity* représente toute entité ayant une temporalité, i.e. une date de début (propriété *time:hasBeginning*) et une date de fin (propriété *time:hasEnd*), et donc une durée (propriété *time:hasDuration*). Une entité dont la durée n'est pas nulle ("début" et "fin" sont différents) est un *intervalle*, sinon il s'agit d'un *instant* (*time:Interval* et *time:Instant* étant des spécialisations de *time:TemporalEntity*). Les entités temporelles peuvent être liées par des relations binaires comme *meets*, *overlaps*, *during* issues de l'algèbre des intervalles d'Allen et servant de base pour les raisonnements spatio-temporels.

Le temps a été associé aux triplets RDF à diverses fins. Ainsi, pour donner à un triplet RDF une dimension temporelle représentant sa période de validité (*valid-time*), notion issue des Bases de Données temporelles, qui s'oppose à celle de "date de transaction" (*transaction-time*) indiquant quand un élément a été enregistré dans la base, [18, 5] proposent le langage stRDF. Un fait y est représenté par un quadruplet *<s,p,o>*:t où t est une variable de type *xsd:datetime* (un instant) ou *strdf:period* (un intervalle de temps). stSPARQL, le langage de requête associé à stRDF, propose des fonctions pour établir des relations temporelles et ainsi rechercher des faits qui se sont produits entre deux dates. Des représentations plus complexes permettent de représenter les évolutions d'objets au cours du temps. Ainsi le modèle Continuum s'appuie sur une ontologie des *fluents* et enrichit GeoSPARQL pour modéliser les changements qui s'opèrent sur des entités spatiales [14]. Pour représenter la date des observations, SOSA intègre une dimension temporelle basée sur OWL-Time. Nous utilisons donc aussi ce vocabulaire.

## 3.3 Les vocabulaires spécifiques du modèle

Nous avons donc adopté SOSA pour décrire les données d'observations (méta-données d'image, observations météorologiques, etc.). La propriété

<footnote n="12">12. https://www.w3.org/TR/owl-time/ (10/2017)</footnote>
g-mfo:obs_07005_20180204150000_tminsol a mfo:Observation .
g-mfo:obs_07005_20180204150000_tminsol sosa:phenomenonTime
g-mfo:interval_1517713200-1517756400 a time:Interval .
g-mfo:interval_1517713200-1517756400 time:hasBeginning g-mfo:instant_1517713200 .
g-mfo:interval_1517713200-1517756400 time:hasEnd g-mfo:instant_1517756400 .
g-mfo:instant_1517713200 a time:Instant .
g-mfo:instant_1517713200 time:inXSDDatetime "2018-02-04T03:00:00"^^xsd:datetime .
g-mfo:instant_1517713200 time:inXSDDatetimeStamp "1517713200"^^xsd:datetimeStamp .
g-mfo:obs_07005_20180204150000_tminsol sosa:hasResult
g-mfo:obs_07005_20180204150000_tminsol_result .
g-mfo:obs_07005_20180204150000_tminsol_result a mfo:Result .
g-mfo:obs_07005_20180204150000_tminsol_result a qudt-1-1:QuantitativeValue .
g-mfo:obs_07005_20180204150000_tminsol_result qudt-1-1:unit qudt-unit-1-1:Kelvin .
g-mfo:obs_07005_20180204150000_tminsol_result qudt-1-1:numericValue "274.75"^^xsd:double .
g-mfo:obs_07005_20180204150000_tminsol sosa:hasFeatureOfInterest
<http://melodi.irit.fr/lod/mfo/foi_07005> .
g-mfo:obs_07005_20180204150000_tminsol sosa:observedProperty g-mfo:Temperature .
g-mfo:obs_07005_20180204150000_tminsol sosa:madeBySensor g-mfo:station_07005_Thermometer .
g-mfo:obs_07005_20180204150000_tminsol sosa:usedProcedure g-mfo:procedure_tminsol .

<caption>TABLE 1 – Extrait de la représentation RDF d'un relevé de température réalisé le 04/02/2018, entre 3h et 15h.</caption>

sosa:phenomenomTime ayant sosa:Observation pour domaine et time:TemporalEntity pour co-domaine sert à représenter la période de temps durant laquelle le résultat d'une observation a été obtenu. Pour représenter les relations spatiales, nous complétons notre modèle avec GeoSPARQL. Nous partons du principe que pour toute observation géolocalisée, son "point d'intérêt" (FeatureOfInterest) correspond à la zone observée; cette zone étant caractérisée par une géométrie, elle est représentée comme un geo:Feature. Ainsi, pour chaque type d'observations issues de capteurs, notre approche consiste à définir un nouveau vocabulaire, avec un espace de nom spécifique, approprié à la source des données. Ce vocabulaire comporte au moins une classe qui spécialise à la fois sosa:FeatureOfInterest et geo:Feature.

Les deux cadres en bas de la Figure 2 correspondent
à deux vocabulaires développés selon cette approche
pour représenter les méta-données d'images satellites pour
l'un (eom), les mesures de stations météorologiques pour
l'autre (mfo). Ces vocabulaires sont présentés dans la
partie 4.1. Dès lors qu'on est capable de représenter
la composante spatiale d'une image comme instance de
geo:Feature, on peut la lier à d'autres informations
ayant une composante spatiale également définie comme
une geo:Feature. De même, on peut lier par une relation
temporelle un enregistrement de méta-données d'image
avec des mesures observées par ailleurs, telles que les don-
nées météo, ou avec des périodes d'intérêt (par exemple
"une semaine après la prise de l'image").

4 Entrepôts RDF pour les données d'observations de la Terre

Nous précisons ici comment nous avons adapté les onto-
logies réutilisées pour concevoir un vocabulaire propre à
chaque source de données. Parmi les données géolocali-
sées, nous avons distingué les données dynamiques, dont

la validité est fournie par la composante temporelle, et les
données statiques, qui ne sont pas datées a priori ou aux-
quelles sont associés de très longs intervalles de temps.
Nous présentons à présent les deux (sous-)modèles résul-
tant et leur instanciation pour enrichir les méta-données
d'images. Il est à noter que la propriété time:hasTime de
OWL-Time est définie comme "un prédicat générique pour
associer une entité temporelle à n'importe quoi". Donc
même si notre modèle ne le mentionne pas, toute entité dé-
crite par une URI peut être estampillée par une composante
temporelle (une date ou un intervalle de temps).

4.1 Les observations (données dynamiques)

Le modèle est spécialisé dans 2 modules dédiés à chacune
des sources d'observations issues de capteurs décrites ici,
à savoir les images satellites et les observations météo.

Les méta-données d'images. Dans le projet SparkIn-
Data, nous utilisons des enregistrements de méta-données
d'images Sentinel<fnref n="13" />. La périodicité de Sentinel-1 est
de douze jours, celle de Sentinel-2 étant de cinq jours.
Les enregistrements de méta-données sont obtenus au
format GeoJSON à partir de RESTO, un service géré
par le CNES [12]. L'API RESTO permet de spécifier
les paramètres à retrouver, à savoir des métadonnées
d'enregistrements comme la couverture nuageuse,
l'intervalle de temps, la zone géographique d'intérêt,
etc. Nous collectons ces informations toutes les nuits.
L'URL suivante fait appel à RESTO pour retourner
tous les enregistrements de métadonnées de la collec-
tion S2ST pour la France, captés entre le 19/09/2017
23:00 et le 25/09/2017 00:00 : https://peps.
cnes.fr/resto/api/collections/S2ST/search.
json?q=France\&startDate=17-09-19T23:00:
00\&completionDate=2017-09-25T00:00:00.

<footnote n="13">13. https://sentinel.esa.int/web/sentinel/
missions/ (07/2018)</footnote>
Les méta-données d'images sont obtenues sous forme de fichiers GeoJSON; elles sont converties en RDF et représentées à l'aide du vocabulaire *eom* comme des "observations de la Terre", i.e. des instances de *eom:EarthObservation* (cadre *eom* de la Figure 2). Cette classe étant une sous-classe de *sosa:Observation*, la composante spatiale des observations est fournie via la classe *eom:Footprint*, spécialisation de *geo:Feature* et *sosa:FeatureOfInterest*: un footprint est décrit par un polygone fermé (une géométrie) délimitant la zone terrestre couverte par l'image. La classe *eom:Footprint* étant une sous-classe de *geo:Feature*, connaissant l'empreinte des images (leur footprint), il est facile d'identifier les caractéristiques d'un autre type de données qui recouvrent la position des images. La *dimension temporelle* d'un enregistrement de méta-données d'image indique le moment où l'image a été prise. Elle est fournie via la propriété *sosa:phenomenomTime* de l'observation correspondante.

Le module est complété par ailleurs pour fournir des données propres aux images satellites telles que le domaine spectral de l'image (infrarouge, UV, etc.), la direction orbitale du satellite (ascendante, descendante) ou encore la couverture nuageuse de l'image.

**Les observations météorologiques.** Comme données contextuelles dynamiques, nous utilisons les informations météo de SYNOP Meteo France<fnref n="14" />. Ces observations sont réalisées toutes les trois heures par chacune des 62 stations françaises. Un fichier séparé contient la liste des stations avec leur position respective (un point fixe répéré par ses coordonnées géographiques). Selon une approche très similaire à celle de [19], nous utilisons des classes tirées de SOSA que nous spécialisons pour définir des classes propres au domaine de la météorologie. Dans un premier temps, nous sommes restés au plus près du schéma de la source MétéoFrance utilisée. Nous envisageons de faire évoluer ce modèle en intégrant le vocabulaire SWEET [24], devenu un standard pour les données météorologiques.

Nous représentons une station météo comme une instance de la classe *mfo:MeteoStation*, une sous-classe de *sosa:Platform*. Les capteurs fonctionnant sur une station météo sont représentés comme instances de *mfo:MeteoSensor*, sous-classe de *sosa:Sensor*. La position géographique où s'effectuent les mesures est représentée comme instance de la classe *mfo:MeteoFeatureOfInterest*, une sous-classe de *sosa:FeatureOfInterest*.

Comme pour *eom*, le module *mfo* a été complété pour représenter les variables fournies avec les relevés météo; il y a 28 variables par relevé, mais beaucoup d'entre elles ne sont pas renseignées. Nous avons ainsi instancié la classe *sosa:ObservableProperty* avec notamment des individus représentant la température

(*mfo:Temperature*), l'humidité (*mfo:HUMIDITY*) ou la vitesse du vent (*mfo:WIND_SPEED*), variables dont une value est relevée toutes les trois heures (cf. Table 1). Le module est enrichi régulièrement par de nouvelles instances (tous les 5 ou 12 jours pour les images satellites, quotidiennement pour les relevés météo).

## 4.2 Les données supports (statiques)

Le modèle peut être enrichi pour représenter des données dites statiques, i.e. qui ont une composante spatiale mais dont la représentation de la composante temporelle n'est pas nécessaire car leur valeur ne varie pas dans l'échelle de temps considérée. Nous avons créé deux modules de ce type, *admin* et *grid*, présentés sur la Figure 3. Pour mettre en relation ces données avec les données dynamiques via des relations spatiales, un concept de chacun de ces modules spécialise la classe *geo:Feature*. Les classes de ces modules sont instanciées une fois pour toutes.

<figure><img src="image_47.png" /><figcaption>FIGURE 4 – Les tuiles de l'ESA définies pour la France métropolitaine</figcaption></figure>

**Les tuiles d'images.** Les images Sentinel ont des caractéristiques différentes en fonction du capteur qui les a prises. En septembre 2016, l'ESA a commencé à diffuser des images Sentinel 2 sous forme de paquets de tuiles simples (images S2ST), chaque tuile représentant une zone fixe de la surface du globe de taille approximative de 100 x 100 km. Une image S2ST correspond donc à un fragment d'image S2. L'intérêt par rapport à une image S2 est que l'utilisateur peut mieux sélectionner la surface qui l'intéresse et ne télécharger que l'information souhaitée. Un fichier S2ST est aussi moins volumineux : il peut faire environ 500 Mo alors que celui d'une image S2 avant tuilage peut faire plus de 3 Go.

La grille de l'ESA décrivant le tuilage de la surface terrestre (Cf. Figure 4), i.e l'empreinte de chaque tuile, est fournie dans un fichier Grid au format KML <fnref n="15" />. Nous avons converti ce fichier en RDF à l'aide du vocabulaire *grid* dé-

<footnote n="14">14. https://donneespubliques.meteofrance.fr/ (07/2018)</footnote>

<footnote n="15">15. https://sentinel.esa.int/web/sentinel/missions/sentinel-2/news/-/article/sentinel-2-tiling-grid-updated</footnote>
<figure><img src="image_48.png" /><figcaption>FIGURE 3 – Les vocabulaires admin etgrid intégrant des données "statiques".</figcaption></figure>

crit en bas de la Figure 3 : chaque tuile est représentée comme une instance de la classe *Tile*, spécialisation de *geo:Feature*, dont la propriété *geo:hasGeometry* correspond à son empreinte. Le module *eom* (cf. Section 4.1) a été enrichi avec la propriété *eom:isTile* pour associer une tuile au *footprint* d'une image. Ainsi en reliant des données à une tuile, on associe indirectement ces données à toutes les images associées à cette tuile.

**La couverture terrestre.** Pour associer des données aux tuiles, nous avons utilisé une autre source de données statiques, le GLC-SHARE (Global Land Cover SHARE) produit par le FAO, qui donne des informations sur la couverture terrestre. Cette dernière est définie à partir d'une nomenclature permettant de classer les zones en fonction du type d'occupation des sols ou du type de surface (surface artificielle, terre cultivée, zone forestière, etc.). Les données du GLC-SHARE sont fournies sous forme d'une image au format TIFF dont chaque pixel correspond à une échelle spatiale approximativement de 1 km². La valeur d'un pixel est un entier indiquant la classe la plus fréquente pour la zone couverte par le pixel. Nous avons donc calculé la composition de la couverture terrestre de chaque tuile de l'ESA de la France. Avec le vocabulaire *grid*, une tuile est liée à un ensemble de graphes RDF (via la propriété *hasLandCoverPercentage*) décrivant chacun le pourcentage d'une classe GLC-SHARE (*CropLand*, *Baresoil*, etc.) sur la surface couverte par la tuile.

**Les stations météorologiques.** Les informations sur les stations météo, tirées du fichier fourni par SYNOP Meteo France, fournissent entre autre la position géographique des mesures météo. Le modèle *mfo* (cf. Section 4.1) a ainsi été complété notamment avec la propriété *hasPosition* dont le codomaine est une spécialisation de *geo:Feature*. Le code suivant est un extrait de la représentation RDF de la station météorologique d'Embrun :

```
g-mfo:MS_07591 rdf:type mfo:Meto Station .
g-mfo:MS_07591 sosa:hosts g-mfo:Sensor_07591_humidity .
g-mfo:MS_07591 sosa:hosts g-mfo:Sensor_07591_temperature .
g-mfo:MS_07591 mfo:hasId "07591"^^xsd: String .
g-mfo:MS_07591 mfo:hasName "EMBRUN"^^xsd: String .
g-mfo:MS_07591 mfo:hasPosition g-mfo:MS_pos_07591 .
g-mfo:MS_pos_07591 rdf:type geo:Feature .
g-mfo:MS_pos_07591 geo:hasGeometry g-mfo:MSgeo_07591 .
g-mfo:MS geo_07591 rdf:type geo:Geometry .
g-mfo:MS geo_07591 geo:asWKT
"POINT ((6.502333 44.565667))^^geo:wktLiteral" .
```

La Figure 5 est un graphe d'instances illustrant (partiellement) la représentation d'observations météo avec le vocabulaire *mfo*: 2 observations mesurant respectivement les précipitations et la pression atmosphérique, ont été réalisées par la même la station météo. La figure met en évidence qu'une seule URI (*g-mfo:Meto Station_pos_07005* sur l'exemple) est utilisée pour représenter à la fois la position de la station (propriété *mfo:hasPosition*) et le lieu de chacune des observations (propriété *sosa:hasFeatureOfInterest*).

**Les unités administratives.** Afin de lier les observations de la Terre à des entités administratives (villes, départe-
<figure><img src="image_49.png" /><figcaption>FIGURE 5 – Instanciation du sous-modèle "mfo" : le "feature of interest" des observations d'une station météo est le lieu où se trouve la station.</figcaption></figure>

ments, régions, etc.) françaises à partir de leur position géographique (point ou polygone), nous avons enrichi le modèle avec le module `admin` (Cf. Figure 3). La classe `AdministrativeUnit` est caractérisée par une propriété `hasSpatialRepresentation` dont le co-domaine est une sous-classe de `geo:Feature`.

Le modèle a été instancié avec des données provenant de la plate-forme ouverte des données publiques françaises `data.gouv.fr`<fnref n="16" />. Ces données sont fournies au format shapefile. Les entités administratives de notre triplestore (instances de `AdministrativeUnit`) sont alignées via la propriété `owl:sameAs` avec les territoires français de l'on-tologie géographique de l'INSEE<fnref n="17" />, qui ne peut pas être utilisée directement pour établir des relations spatiales car elle ne contient pas d'information géométrique. Ci-après un exemple de graphe RDF, celui de la région 54 :

```
admin:region_54 a admin:AdministrativeUnit .
admin:region_54 a admin:Region .
admin:region_54 owl:sameAs <http://id.insee.fr/geo/region/54> .
admin:region_54 admin:hasInseeCode "54"^^xsd:String .
admin:region_54 admin:hasName "Poitou-Charentes"^^xsd:String .
admin:region_54 a geo:Feature .
admin:region_54 geo:hasGeometry l_admin:region_54 geo .
admin:region_54 geo:hasWKT "MULTIPOLYGON((
  -1.0988062299633785 45.64032288975508, ...
  -1.0988062299633785 45.64032288975508))... )"^^wkt:Literal .
```

# 5 Intégration de données RDF via leurs relations spatiales

Chacun des modules des Figures 2 et 3 est décrit dans un fichier OWL spécifique. Le modèle global est ainsi composé de 4 ontologies<fnref n="18" />. Le calcul des relations spatiales et temporelles permet de relier les données de chacun de ces entrepôts, et exploite le tuilage. En liant des éléments spatiaux aux tuiles de l'ESA, les connaissances s'y rapportant sont extrapolées au niveau des images. Par exemple, sachant que les images `[img1, img2, img3]` partagent la tuile `tile1`, et que cette tuile recouvre `adminUniti`, il est possible d'inférer que `[img1, img2, img3]` recouvrent aussi `adminUniti`.

Pour calculer une relation spatiale R (appartenance ou non-intersection, par exemple) entre deux ensembles de données S et T d'une base de connaissances, nous comparons chaque entité s de S à chaque entité t de T, pour vérifier l'existence de R(s,t). Ceci est réalisé à l'aide d'une requête comme celle ci-dessous qui recherche l'ensemble des triplets `<s, geo:sfIntersects, t>` tels que les empreintes géographiques de s et t ont une intersection non vide :

```
CONSTRUCT (?s geo:sfIntersects ?t .)
WHERE (
  GRAPH <S> (?s geo:hasGeometry/geo:asWKT ?s_geometry.)
  GRAPH <T> (?t geo:hasGeometry/geo:asWKT ?t_geometry.)
  FILTER( geof:sfIntersects(?s_geometry, ?t_geometry) )
)
```

<footnote n="16">16. https://www.data.gouv.fr</footnote>

<footnote n="17">17. http://rdf.insee.fr/def/index.html</footnote>

<footnote n="18">18. http://melodi.irit.fr/ontologies/eom.owl;
http://melodi.irit.fr/ontologies/mfo.owl;
http://melodi.irit.fr/ontologies/grid.owl; http://melodi.irit.fr/ontologies/administrativeUnits.owl</footnote>
Cette approche, consistant à faire le produit cartésien de deux ensembles, est de complexité quadratique si bien que, dès que les jeux de données à combiner sont volumineux, calculer ces relations au moment de l'interrogation peut être extrêmement coûteux en temps et inacceptable pour les applications temps-réel. C'est pourquoi il est préférable de les pré-calculer. Nous avons distingué le cas des données à composante spatiale seule (statiques) de celles ayant en plus une composante temporelle (dynamiques).

## 5.1 Intégration des données statiques

Pour les données statiques, il est raisonnable d'envisager d'enregistrer dans l'entrepôt RDF les relations spatiales entre les données RDF correspondantes, si ces jeux de données ont une taille raisonnable. Si le volume est trop conséquent, il est nécessaire d'avoir recours à des techniques d'optimisation. Ainsi, en nous appuyant sur l'indexation spatiale fournie par le tuilage des images S2ST, nous avons calculé les relations entre les données de chacun des jeux que nous venons de présenter : stations météo de mfo, unités administratives de admin et tuiles de grid. Ainsi, il est possible de lier les stations météorologiques aux images en calculant uniquement les relations spatiales entre les stations météo et les tuiles de l'ESA. La requête SPARQL ci-dessous interroge les jeux de données instanciant les modèles eom, grid et admin. Elle retrouve les images S2ST avec une couverture nuageuse inférieure à 10%, collectées à un moment donné, et dont l'empreinte géographique couvre (propriété geo:sfContains) une zone géographique particulière et ayant un type d'occupation du sol particulier. L'utilisateur a défini une date qui, comme la couverture nuageuse et le type d'occupation du sol, est utilisée pour filtrer les données pertinentes (cf. les deux dernières clauses FILTER).

```sql
select distinct ?s2st_result ?tileId
{
    ?s2st a md:EarthObservation .
    ?s2st md:featureOfInterest ?fi .
    ?s2st md:result ?s2st_result .
    ?s2st_result md:product ?s2st_product .
    ?s2st_product md:cloudCoverPercentage ?s2st_cloudCover .
    ?s2st md:phenomenomTime ?s2st_period .
    ?s2st_period time:hasBeginning ?s2st_time .
    ?fi md:isTile ?tile .
    ?tile geo:hasGeometry ?tile_geometry .
    ?tile_geometry geo:sfContains ?admin_geometry .
    ?adminUnit admin:hasSpatialRepresentation ?admin sr .
    ?admin sr geo:hasGeometry ?admin_geometry .
    ?adminUnit admin:hasName ?adminUnitName .
    ?adminUnitName bif:contains 'Alpes' .
    ?tile grd:hasLandCoverInfo ?tile lc .
    ?tile lc grd:hasLandCoverPercentage ?lc Perc .
    ?lc Perc grd:about ?lc_class .
    ?lc Perc grd:percentage_value ?lc_value .
    ?tile grd:tileId ?tileId .
FILTER (?s2st_time = ?user_time)
FILTER (?lc_value>1 and ?lc_class=grd:ArtificialSurface
  and ?s2st_cloudCover<10)
}
```

Nous avons testé deux méthodes pour calculer les relations spatiales et créer les triplets RDF les représentant. Nous venons d'exposer la première qui met en oeuvre des requêtes SPARQL incluant des fonctions GeoSPARQL. La seconde a consisté à développer un programme en Python, à l'aide du module Shapely qui permet de faire des opérations spatiales sur des données au format WKT. Avec la solution Python, il faut 0,50s (sans optimisation particulière) pour calculer toutes les relations spatiales entre 1 élément d'un jeu de données S et 50 éléments d'un jeu de données T, alors qu'il faut 11s avec GeoSPARQL pour calculer une seule relation entre 1 élément de S et 50 éléments de T.

## 5.2 Intégration des données ayant une composante temporelle

Il est possible d'établir des relations temporelles entre un enregistrement de méta-données d'image et des données ayant une indication temporelle comme les relevés météo, ou des périodes d'intérêt définies par l'utilisateur. A défaut de disposer d'entités qui servent de référentiel temporel (le pendant des tuiles de l'ESA pour la composante spatiale), nous exploitons l'intervalle de temps défini par un utilisateur lors de la recherche d'images, comme un buffer temporel fournissant un contexte aux enregistrements de méta-données.

La Figure 6 illustre ce principe. Une interface permet à l'utilisateur de dessiner un rectangle pour spécifier des contraintes spatiales et de saisir une période de temps pour définir un empan temporel. A partir de ces informations, le système génère une requête GeoSPARQL qui permet de retrouver les observations météo, les métadonnées et les images dont la composante temporelle recouvre l'empan temporel et dont la localisation vérifie les contraintes spatiales (plus précisément, l'empreinte de ces images a une intersection non nulle avec le rectangle choisi par l'utilisateur). Les images recherchées sont des images Sentinel 2 "classiques", qui ne sont pas liées à une unique tuile comme les S2ST, et donc pour lesquelles les relations spatiales n'ont pas été pré-calculées. La requête SPARQL ci-dessous sélectionne des enregistrements de méta-données d'images dont les mesures météorologiques associées respectent deux contraintes :

1. elles proviennent de stations situées dans l'empreinte de l'image : ?img_geometry étant la géométrie d'une image et ?ws_geometry celle d'une station météo, la géométrie de l'image doit contenir celle de la station météo, ce qu'indique la fonction geof:sfContains dans le filtre FILTER (geof:sfContains(?img_geometry, ?ws_geometry));

2. elles ont été collectées durant une période donnée ; l'utilisateur a défini une période d'intérêt d'une semaine après la prise d'image (24x7=168 heures, 'PT168H'), qui est utilisée au sein des deux dernières clauses FILTER.

```sql
SELECT ?img ?obs_time ?humidityDataVal ?humidityUnits
WHERE {
    ?img a eom:EarthObservation .
    ?img eom:featureOfInterest ?img_foi .
    ?img_foi geo:hasGeometry ?img_geometry .
    ?img eom:phenomenomTime ?img_temp .
    ?img_temp time:hasEnd/time:inXSDDatetime ?img_end .
    ?ws a mfo:MetoStation .
    ?ws mfo:hasPosition ?ws_pos .
    ?ws_pos geo:hasGeometry ?ws_geometry .
    ?ws sosa:hosts ?sensor .
    ?sensor sosa:observes mfo:HUMIDITY .
    ?obs sosa:madeBySensor ?sensor .
    ?obs sosa:hasResult ?humidity .
    ?humidity mfo:hasQuantitativeValue ?humidityDataVal .
    ?humidityVal mfo:isClassifiedBy ?humidityUnits .
    ?obs sosa:phenomenomTime ?obs_time .
    ?obs_time time:hasEnd/time:inXSDDatetime ?obs_end .
    BIND (?img_temp-?obs_time as ?diffDateTime)
FILTER (geof:sfContains(?img_geometry, ?ws_geometry))
FILTER (?diffDateTime<'PT168H'^^xsd:dayTimeDuration)
FILTER (?diffDateTime>'PT0H'^^xsd:dayTimeDuration)
}
```

Faute de place, nous n'avons pas indiqué les éléments de la requête filtrant les images présentes dans la zone spécifiée par l'utilisateur.

La Figure 6 montre l'information météorologique associée à une image faisant partie de la liste retournée par une requête de ce type. L'empreinte de l'image est représentée par un polygone
<figure><img src="image_50.png" /><figcaption>FIGURE 6 – Affichage des informations météorologiques associées à une image satellite en réponse à la requête.</figcaption></figure>

orange. Chaque cercle bleu correspond à une station météorologique. En bas de la carte, figurent des séries temporelles qui représentent l'évolution de la variable *Temperature* pendant la période choisie.

# 6 Conclusion

Nous avons proposé une ontologie pour l'intégration de données d'observation de la Terre et données contextuelles, basée sur des relations topologiques spatiales et temporelles. Cette ontologie spécialise des standards, notamment SOSA, GeoSPARQL et OWL-Time. Nous avons défini également un processus d'intégration qui sélectionne, transforme et intègre de données géospatiales hétérogènes (méta-données d'image satellite, données météorologiques, unités administratives, couverture terrestre, etc.). Ce processus s'appuie sur le tuitage des images pour traiter les données ayant une composante spatiale fixe, les relations temporelles, quant à elle, sont calculées à la volée à partir d'une topologie temporelle. Nous avons présenté un cas d'étude basé exploitant des méta-données d'image satellite Sentinel.

Dans la continuité de ces travaux, nous envisageons de considérer des sources propres à un domaine métier pour traiter un cas d'usage (l'agriculture et des rapports bulletins agricoles) et fournir des règles et des fonctionnalités de raisonnement pour faciliter les analyses. Il serait intéressant aussi d'identifier des patrons qui augmenteraient la pertinence de l'image, en s'appuyant sur des règles et du raisonnement. On pourrait par exemple analyser les

séries temporelles de température et détecter une canicule. Nous envisageons également d'intégrer des alignements automatiques pour mettre en correspondance les métadonnées d'images et les vocabulaires, mais également les données annotées et d'autres sources du LOD.

# Références

[1] H. Arenas, N. Aussenac-Gilles, C. Comparot, and C. Trojahn. Semantic integration of geospatial data from earth observations. In *Knowledge Engineering and Knowledge Management - EKAW 2016 Satellite Events*, pages 97–100, 2016.

[2] H. Arenas, N. Aussenac-Gilles, C. Comparot, and C. Trojahn. Un modèle pour l'intégration sémantique de données géolocalisées liées à l'observation de la terre. In *Spatial Analysis and Geomatics - Atelier EXtraction de Connaisances à partir de donnéEs Spatialisées (SAGEO-EXCES)*, Nice, 2016.

[3] G. A. Atemezing. *Publishing and consuming geo-spatial and government data on the semantic web*. PhD thesis, The- sis, 04 2015.

[4] R. Battle and D. Kolas. Enabling the Geospatial Semantic Web with Parliament and GeoSPARQL. *Semantic Web, 3(October 2012):355–370, 2012.
[5] K. Bereta, P. Smeros, and M. Koubarakis. Representation and querying of valid time of triples in linked geospatial data. In *The Semantic Web: Semantics and Big Data*, pages 259–274, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.

[6] L. M. V. Blázquez, B. Villazón-Terrazas, Ó. Corcho, and A. Gómez-Pérez. Integrating geographical information in the linked digital earth. *Int. Journal of Digital Earth*, 7(7):554–575, 2014.

[7] D. Brizhinev, S. Toyer, K. Taylor, and Z. Zhang. Publishing and using earth observation data with the rdf data cube and the discrete global grid system. Technical report, W3C and OGC, 2017.

[8] M. Console and M. Lenzerini. Reducing global consistency to local consistency in ontology-based data access - extended abstract. In *Informal Proceedings of the 27th International Workshop on Description Logics, Vienna, Austria, July 17-20, 2014.*, pages 496–499, 2014.

[9] S. Cox. Prov ontology supports alignment of observational data (models). In *Modeling and Simulation Society of Australia and New Zealand*, pages 403–409, 2017.

[10] D. Espinoza-Molina and M. Datcu. Earth-observation image retrieval based on content, semantics, and metadata. *IEEE Trans. on Geoscience and Remote Sensing*, 51(11):5145–5159, 2013.

[11] D. Espinoza-Molina, C. Nikolaou, C. O. Dumitru, K. Bereta, M. Koubarakis, G. Schwarz, and M. Datcu. Very-High-Resolution SAR Images and Linked Open Data Analytics Based on Ontologies. *IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing*, 8(4):1696–1708, 2015.

[12] J. Gasperi. Semantic Search Within Earth Observation Products Database Based on Automatic Tagging of Image Content. In *Proc. of the Conf. on Big Data from Space*, pages 4–6, 2014.

[13] A. Gore. The digital earth. *Australian Surveyor*, 43(2):89–91, 1998.

[14] B. Harbelot, H. Arenas, and C. Cruz. un modèle sémantique spatio-temporel pour capturer la dynamique des environnements. In *14ème conférence Extraction et Gestion des Connaissances*, page 39 à 54, Rennes, France, 2014.

[15] T. Heath and C. Bizer. *Linked Data: Evolving the Web into a Global Data Space*; *Lectures on the Semantic Web: Theory and Technology*. Morgan & Claypool, 2011.

[16] C. Keßler and C. J. Q. Farmer. Querying and integrating spatial-temporal information on the Web of Data via time geography. *Journal of Web Semantics*, 35:25–34, 2015.

[17] D. Kolas, M. Perry, and J. Herring. Getting started with GeoSPARQL. Technical report, OGC, 2013.

[18] M. Koubarakis and K. Kyzirakos. Modeling and querying metadata in the semantic sensor web: The model strdf and the query language stsparql. In *The Semantic Web: Research and Applications*, pages 425–439, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.

[19] L. Lefort, J. Bobruk, A. Haller, K. Taylor, and A. Woolf. A linked sensor data cube for a 100 year homogenised daily temperature dataset. In *Proc. of the 5th International Conference on Semantic Sensor Networks - Volume 904*, SSN'12, pages 1–16. CEUR-WS.org, 2012.

[20] M. Lefrançois, A. Zimmermann, and N. Bakerally. A SPARQL extension for generating RDF from heterogeneous formats. In *Proc. Extended Semantic Web Conference (ESWC'17)*, Portoroz, Slovenia, May 2017.

[21] M. Lenzerini. Ontology-based data management. In *Proc. of the 20th ACM Int. Conference on Information and Knowledge Management*, CIKM '11, pages 5–6, New York, USA, 2011. ACM.

[22] F. Maali and J. Erickson. Data Catalog Vocabulary (DCAT), 2014.

[23] M. Perry and J. Herring. OGC GeoSPARQL-A geographic query language for RDF data. Technical report, Open Geospatial Consortium, 2012.

[24] R. Raskin. Guide to SWEET Ontologies. Technical Report 9, NASA/Jet Propulsion Lab, Pasadena, CA, USA, 2006.

[25] F. Reitsma and J. Albrecht. Modeling with the semantic web in the geosciences. *IEEE Intelligent Systems*, 20(2):86–88, 2005.

[26] D. Sukhobok, H. Sánchez, J. Estrada, and D. Roman. Linked data for common agriculture policy: Enabling semantic querying over sentinel-2 and lidar data. In *Proceedings of the ISWC 2017 Posters & Demonstrations and Industry Tracks co-located with 16th Int. Semantic Web Conference, Vienna, Austria, Oct. 23-25, 2017, 2017*.

[27] J. Tandy, L. van den Brink, and P. Barnaghi. Spatial data on the web best practices, w3c working group note. Technical report, W3C and OGC, 2017.

[28] TELEIOS. Virtual Observatory Infrastructure for Earth Observation Data. http://www.earthobservatory.eu/search/node/ontologies, 2016. Accessed: 2018-03.

[29] The TELEIOS Team. Building Remote Sensing Applications Using Scientific Database And Semantic Web Technologies. In *Image Information Mining Conference: Knowledge Discovery from Earth Observation Data*, pages 2–5, 2012.
# Choisir un encodage CNF de contraintes de cardinalité performant pour SAT

T. Delacroix

IMT Atlantique - Dépt. LUSSI, Brest, France

thomas.delacroix@imt-atlantique.fr

## Résumé

Cet article répond à une double problématique : (1) comment choisir un encodage CNF pour des contraintes de cardinalité de type $\#k(x_1, ..., x_n)$ où $\#$ peut être l'un des symboles $\leq, =, \geq$; (2) déterminer un encodage CNF performant pour les contraintes de cardinalité plus générales $\in K(x_1, ..., x_n)$ où $K \subset [0, n]$. Pour ce faire, on introduit d'abord un nouvel encodage séquentiel bidirectionnel. On décrit alors un processus pour choisir l'encodage le plus performant pour une contrainte de cardinalité donnée s'appuyant sur une comparaison de différents encodages pour tous les cas possibles de valeurs $n$ et $k$. Enfin, on montre que l'encodage séquentiel bidirectionnel permet de répondre à la problématique (2).

## Mots Clef

CNF, SAT, encodage, contraintes de cardinalité.

## Abstract

This article has a double aim : (1) define a process for choosing the most efficient CNF encoding for cardinality constraints of type $\#k(x_1, ..., x_n)$ where $\#$ is one of the following symbols $\leq, =, \geq$; (2) determine an efficient CNF encoding for the more general cardinality constraints of type $\in K(x_1, ..., x_n)$ where $K \subset [0, n]$. In order to do this, we introduce a new sequential bidirectional encoding. We then describe a process for choosing the most efficient encoding for a given cardinality constraint based on a comparison of different encodings for all possible values of $n$ and $k$. Finally, we show that the sequential bidirectional encoding can be used to reach our second aim.

## Keywords

CNF, SAT, encoding, cardinality constraints.

## 1 Introduction

Parmi les solveurs modernes en programmation sous contrainte les plus performants, on trouve aujourd'hui un certain nombre de solveurs CNF-SAT. Les palmarès récents du MiniZinc Challenge en témoignent [13, 11].

Un solveur CNF-SAT permet d'obtenir une valuation pour laquelle une expression logique sous forme conjonctive normale (CNF) donnée est satisfaite lorsqu'il en existe une. Pour une contrainte particulière, la performance du solveur dépend donc à la fois de l'algorithme de résolution du

sol-veur et à la fois de la façon dont la contrainte est exprimée sous forme CNF.

De nombreux travaux se sont donc penchés sur la question de savoir comment exprimer des contraintes classiques des CSP sous forme CNF de manière performante pour les solveurs CNF-SAT [1, 2, 3, 4, 5, 7, 10, 14, 15]. C'est le cas notamment pour les contraintes de cardinalité<fnref n="1" /> de type $\#k(x_1, ..., x_n)$ où $\#$ peut être l'un des symboles $\leq, =, \geq$. En effet, un encodage naïf de ces contraintes contient, dès que $n$ augmente, beaucoup trop de clauses pour pouvoir être utilisé de manière raisonnable en pratique. De nombreux encodages CNF ont donc été proposés, fonctionnant tous sur le même principe général : des variables supplémentaires sont introduites de manière à réduire drastiquement le nombre de clauses.

Parmi les travaux existants, on trouve des comparaisons des différents encodages proposés [2, 9, 12]. Toutefois, ces comparaisons ne sont pas exhaustives. En effet, l'accent y est généralement mis sur le comportement des encodages lorsque $n$ tend vers l'infini. Or, en pratique, on peut également être amené à considérer de très nombreuses contraintes de cardinalité de faible dimension. Une comparaison exhaustive des encodages existants s'impose donc afin d'essayer d'optimiser au maximum l'étape du choix de l'encodage dans la résolution SAT et cela constitue un des éléments central de cet article. On s'aperçoit alors qu'il n'y a pas un encodage plus performant que tous les autres mais de nombreux encodages performants selon les paramètres du problème. On montre également qu'il est possible de combiner des encodages pour obtenir de meilleures performances.

Par ailleurs, on introduit dans cet article un nouvel encodage : l'encodage séquentiel bidirectionnel. Cet encodage, dont la définition est assez naturelle, est particulièrement adapté pour considérer des contraintes de cardinalité plus complexes, notamment les contraintes de cardinalité correspondant à un intervalle. On montre par ailleurs qu'il permet de considérer des contraintes de cardinalité de type $\in K(x_1, ..., x_n)$ où $K \subset [0, n]$ de manière performante ce qui représente une nouveauté.

<footnote n="1">1. Le terme contrainte de cardinalité est utilisé ici selon la nomenclature standard dans le contexte SAT et ne doit pas être confondu avec d'autres notions telles que celle de *global cardinality constraint* utilisée dans le contexte de la programmation sous contrainte.</footnote>
## 2 Encodage séquentiel bidirectionnel

Dans la suite, on considère des entiers $n$ et $k$ tels que $n \ge 2$ et $k \in [1, n-1]$, les autres cas étant évidemment triviaux. La démarche qui mène à définir l'encodage proposé dans cette section s'apparente à la démarche qui mène à l'encodage séquentiel proposé par Carsten Sinz dans [12]. En effet, dans l'article précité, l'auteur définit les sommes partielles $s_i = \sum_{m=1}^{i} x_m$ et considère le $j$-ième bit $s_{i,j}$ de la représentation unaire de $s_i$. Il transpose alors ces bits en variable booléenne dans un encodage CNF pour abouvir à l'encodage ci-dessous pour la contrainte de cardinalité $\le k(x_1, ..., x_n)$. Par la suite, on le désigne par le nom d'encodage séquentiel unidirectionnel et on le note $SeqU_{\le k}^n$.

$$ \left. \begin{array}{l} (\neg x_1 \lor s_{1,1}) \\ (\neg s_{1,j}) \quad \forall j \in [1, k] \\ (\neg x_i \lor s_{i,1}) \\ (\neg s_{i-1,1} \lor s_{i,1}) \\ (\neg x_i \lor \neg s_{i-1,j-1} \lor s_{i,j}) \\ (\neg s_{i-1,j} \lor s_{i,j}) \\ (\neg x_i \lor \neg s_{i-1,k}) \\ (\neg x_n \lor \neg s_{n-1,k}) \end{array} \right\} \forall i \in [1, n] \quad (SeqU_{\le k}^n) $$

Cependant, cette transposition contient une réduction qui aboutit à une perte d'information entre la variable $s_{i,j}$ tel qu'elle est encodée dans $SeqU_{\le k}^n$ par rapport au bit $s_{i,j}$ décrit précédemment. En effet, le bit $s_{i,j}$ est équivalent à $s_i \ge j$. Or l'encodage $SeqU_{\le k}^n$ donne $(s_i \ge j) \implies s_{i,j}$ mais pas l'implication réciproque. Cette perte d'information est volontaire car elle entraine un encodage plus restreint de la contrainte $\le k(x_1, ..., x_n)$. Toutefois, ce choix n'est pas forcément judicieux lorsque l'on considère une contrainte $= k(x_1, ..., x_n)$ ou deux contraintes $\ge k_1(x_1, ..., x_n)$ et $\le k_2(x_1, ..., x_n)$ définissant un intervalle.

L'encodage CNF qui suit permet d'encoder exactement l'ensemble des équivalences $(s_i \ge j) \iff s_{i,j}$ pour tout $i \in [1, n]$ et pour tout $j \in [1, k+1]$. On appelle encodage séquentiel bidirectionnel cet encodage et on le note $SeqB_{\#k}^n$.

$$ \left. \begin{array}{l} (x_1 \lor \neg s_{1,1}) \\ (\neg x_i \lor s_{i,1}) \quad \forall i \in [1, n] \\ (\neg s_{j-1,j}) \quad \forall j \in [1, k+1] \\ (\neg s_{i-1,j} \lor s_{i,j}) \\ (x_i \lor s_{i-1,j} \lor \neg s_{i,j}) \\ (s_{i-1,j-1} \lor \neg s_{i,j}) \\ (\neg x_i \lor \neg s_{i-1,j-1} \lor s_{i,j}) \end{array} \right\} \forall j \in [1, k+1] \quad \forall i \in [1, n] \quad (SeqB_{\#k}^n) $$

À partir de cet encodage, il est très facile d'obtenir la contrainte de cardinalité $\le k(x_1, ..., x_n)$. En effet, il suffit de rajouter la clause $\neg s_{n,k+1}$. De même, la contrainte $\ge k(x_1, ..., x_n)$ s'obtient simplement par le rajout de la clause $s_{n,k}$. Enfin, la contrainte $= k(x_1, ..., x_n)$ s'obtient par le

rajout de ces deux clauses. On note $SeqB_{\le k}^n$, $SeqB_{\ge k}^n$ et $SeqB_{=k}^n$ les encodages respectifs correspondants.

## 3 Choisir son encodage

### 3.1 Comparaisons des encodages

En plus des encodages décrits précédemment, on va également considérer l'encodage naïf ($N_{\le k}^n$) défini par :

$$ \bigwedge_{i \in C_n^{k+1}} \bigvee_{j=1}^{k+1} \neg x_{ij} \qquad (N_{\le k}^n) $$

où $i = (i_1, ..., i_{k+1})$ est une combinaison appartenant à l'ensemble $C_n^{k+1}$ des combinaisons de $k+1$ éléments de $[1, n]$. On rajoute l'encodage proposé par Bailleux & Boufkhad dans [3] ($BB_{\ge k_1, \le k_2}^n$). On note que les auteurs précités ne donnent pas d'expression explicite de leur encodage mais décrivent plutôt un algorithme permettant de le construire.

D'autres encodages de la littérature [15] ne sont pas considérés car ils ne satisfont pas la condition de performance relative à la propagation unitaire décrite initialement dans [3] (i.e. il ne permettent pas de vérifier la contrainte sur une valuation partielle des variables $x_i$).

Par ailleurs, par manque de temps, nous n'avons pas intégré ici d'encodage à base de réseaux [1, 2, 7]. En effet, nous souhaitons d'abord vérifier que la génération de tels encodages est bien linéaire en leur nombre total de clauses (ou de littéraux), de manière à ce que la comparaison soit valable. Ce travail reste donc à compléter sur ce point. En effet, de tels encodages peuvent comporter un nombre total de clauses inférieur à ceux des encodages considérés ici pour un certain nombre de valeurs de $n$ et $k$. Ceci est notamment le cas de l'encodage de la contrainte $\le k(x_1, ..., x_n)$ proposé par Asín et al. dans [2] dont le nombre total de clauses est égal à :

$$ \begin{gathered} -3m+6mK+\frac{3}{4}mK \log_2(K)+\frac{3}{4}mK \log_2(K)-3K-\frac{3}{2}K \log_2(K) \\ \text{avec } K = 2^{\lceil \log_2(k) \rceil} \text{ et } m = \lceil \frac{n}{K} \rceil. \end{gathered} $$

Le tableau 1 donne les nombres de clauses (avec le détail en fonction de la taille en nombre de littéraux de ces clauses) ainsi que le nombre de variables auxilaires pour chacun de ces encodages. Les valeurs figurant dans ce tableau ont été recalculées à partir des descriptions de ces encodages dans les articles précités [12, 3] ainsi que le présent article.

Dans la suite de cet article, on utilise les informations de ce tableau pour permettre de choisir l'encodage le mieux adapté aux différents cas étudiés. On fera également usage de la règle suivante pour obtenir un encodage d'une contrainte $\ge k(x_1, ..., x_n)$ en considérant l'encodage pour la contrainte $\le k(x_1, ..., x_n)$ via l'utilisation de la règle suivante :

$$ \ge k(x_1, ..., x_n) \iff \le (n-k)(\neg x_1, ..., \neg x_n) \quad (1) $$
De même, on pourra obtenir un encodage de la contrainte $= k(x_1, ..., x_n)$ en combinant différents encodages via l'utilisation de la constation suivante :

$$= k(x_1, ..., x_n) \iff (\leq k(x_1, ..., x_n) \wedge \geq k(x_1, ..., x_n)) \quad (2)$$

<table><caption>TABLE 1 – Nombre et tailles de clauses pour chaque encodage considéré</caption><thead><tr><th>Encodage</th><th colspan="2">Nombre de clauses composées de m littéraux</th><th>Nombre de variables auxiliaires</th></tr></thead><tbody><tr><td rowspan="4">SeqU<sup>n</sup><sub>≤k</sub></td><td>m = 1</td><td>k - 1</td><td rowspan="4">nk - k</td></tr><tr><td>m = 2</td><td>nk + 2n - 2k - 2</td></tr><tr><td>m = 3</td><td>nk - n - 2k + 2</td></tr><tr><td>Total</td><td>2nk + n - 3k - 1</td></tr><tr><td rowspan="4">SeqB<sup>n</sup><sub>#k</sub></td><td>m = 1</td><td>k</td><td rowspan="4">nk + n</td></tr><tr><td>m = 2</td><td>2nk + 2n - 2k</td></tr><tr><td>m = 3</td><td>2nk + n - 2k - 1</td></tr><tr><td>Total</td><td>4nk + 3n - 3k - 1</td></tr><tr><td>N<sup>n</sup><sub>≤k</sub></td><td>m = k + 1</td><td>(<sup>n</sup><sub>k+1</sub>)</td><td>0</td></tr><tr><td rowspan="3">BB<sup>n</sup><sub>≥k₁, ≤k₂</sub></td><td>m = 1</td><td>n - k₂ + k₁</td><td rowspan="3">n log₂(n)</td></tr><tr><td>m = 3</td><td>n<fnref n="2" /> + 2n log₂(n) + n - 2</td></tr><tr><td>Total</td><td>n<fnref n="2" /> + 2n log₂(n) + 2n - k₂ + k₁ - 2</td></tr></tbody></table>

## 3.2 Contrainte $\leq k(x_1, ..., x_n)$

Dans cette section, on compare différents encodages de $\leq k(x_1, ..., x_n)$.

<table><caption>TABLE 2 – Encodage de $\leq k(x_1, ..., x_n)$ donnant le nombre total minimal de clauses en fonction de n et k</caption><caption>Conditions sur n et k par encodage</caption><thead><tr><th>SeqU<sup>n</sup><sub>≤k</sub></th><th>BB<sup>n</sup><sub>≥0,≤k</sub></th><th>SeqB<sup>n</sup><sub>≥n-k</sub></th><th>N<sup>n</sup><sub>≤k</sub></th></tr></thead><tbody><tr><td colspan="4">n ≤ 5 et k ∈</td></tr><tr><td>∅</td><td>∅</td><td>∅</td><td>[[1, n]]</td></tr><tr><td colspan="4">6 ≤ n ≤ 8 et k ∈</td></tr><tr><td>[[1, k₁]]</td><td>∅</td><td>∅</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = n - 4.</td></tr><tr><td colspan="4">9 ≤ n ≤ 13 et k ∈</td></tr><tr><td>[[1, k₁]]</td><td>∅</td><td>∅</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = n - 3.</td></tr><tr><td colspan="4">14 ≤ n ≤ 30 et k ∈</td></tr><tr><td>[[1, k₂]]</td><td>∅</td><td>[[k₂, k₁]]</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = n - 3 et k₂ = [2/3(n + 1)].</td></tr><tr><td colspan="4">31 ≤ n ≤ 36 et k ∈</td></tr><tr><td>[[1, k₂]]</td><td>∅</td><td>[[k₂, k₁]]</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = n - 2 et k₂ = [2/3(n + 1)].</td></tr><tr><td colspan="4">37 ≤ n et k ∈</td></tr><tr><td>[[1, k₃]]</td><td>[[k₃, k₂]]</td><td>[[k₂, k₁]]</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = n - 2, k₂ = [3n<fnref n="2" /> - 2n log₂(n) - 2n + 2] / 4(n - 1)</td></tr><tr><td colspan="4">et k₃ = [n<fnref n="2" /> + 2n log₂(n) + n - 1] / 2(n - 1).</td></tr></tbody></table>

On remarque d'abord que pour une telle contrainte, l'encodage $SeqU<sup>n</sup><sub>≤k</sub>$ est clairement toujours plus performant que l'encodage $SeqB<sup>n</sup><sub>≤k</sub>$ donc on peut exclure ce dernier de notre comparaison. Par contre, en utilisant (1), on peut considérer l'encodage $SeqB<sup>n</sup><sub>≥n-k</sub>$ appliqué à $(\neg x_1, ..., \neg x_n)$. On note $SeqB<sup>n</sup><sub>≥n-k</sub>$ cet encodage.

On cherche donc à comparer les encodages $N<sup>n</sup><sub>≤k</sub>$, $SeqU<sup>n</sup><sub>≤k</sub>$, $SeqB<sup>n</sup><sub>≥n-k</sub>$, $BB<sup>n</sup><sub>≥0,≤k</sub>$. Une analyse complète des différents nombres totaux de clauses pour chacun de ces encodages permet de déterminer l'encodage offrant le plus petit nombre de clauses en fonction de n et k. On a réalisé cette analyse ici et regroupé les résultats dans le tableau 2. Ce tableau décrit, en fin de compte, une partition de l'ensemble des valeurs potentielles de n et k en 4 parties, chacune correspondant aux valeurs de n et k pour lesquelles l'encodage en colonne est optimal (pour le critère du nombre de clauses considéré ici).

<table><caption>TABLE 3 – Encodage de $\leq k(x_1, ..., x_n)$ donnant le nombre total minimal de littéraux en fonction de n et k</caption><caption>Conditions sur n et k par encodage</caption><thead><tr><th>SeqU<sup>n</sup><sub>≤k</sub></th><th>BB<sup>n</sup><sub>≥0,≤k</sub></th><th>SeqB<sup>n</sup><sub>≥n-k</sub></th><th>N<sup>n</sup><sub>≤k</sub></th></tr></thead><tbody><tr><td colspan="4">n ≤ 5 et k ∈</td></tr><tr><td>∅</td><td>∅</td><td>∅</td><td>[[1, n]]</td></tr><tr><td colspan="4">6 ≤ n ≤ 7 et k ∈</td></tr><tr><td>[[1, k₁]]</td><td>∅</td><td>∅</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = n - 3.</td></tr><tr><td colspan="4">8 ≤ n ≤ 10 et k ∈</td></tr><tr><td>[[1, k₁]]</td><td>∅</td><td>∅</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = n - 2.</td></tr><tr><td colspan="4">11 ≤ n ≤ 27 et k ∈</td></tr><tr><td>[[1, k₂]]</td><td>∅</td><td>[[k₂, k₁]]</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = n - 2 et k₂ = [10n<fnref n="2" /> - 3n - 3] / (3(n - 6)).</td></tr><tr><td colspan="4">28 ≤ n ≤ 148 et k ∈</td></tr><tr><td>[[1, k₂]]</td><td>∅</td><td>[[k₂, k₁]]</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = n - 1 et k₂ = [10n<fnref n="2" /> - 3n - 3] / (3(n - 6)).</td></tr><tr><td colspan="4">149 ≤ n et k ∈</td></tr><tr><td>[[1, k₃]]</td><td>[[k₃, k₂]]</td><td>[[k₂, k₁]]</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = n - 1, k₂ = [7n<fnref n="2" /> - 6n log₂(n) - 6n + 4] / (10(n - 1))</td></tr><tr><td colspan="4">et k₃ = [3n<fnref n="2" /> + 6n log₂(n) + 3n - 7] / (5n - 8).</td></tr></tbody></table>

Le tableau 2 permet de choisir un encodage en fonction du nombre de clauses de cet encodage mais il ne prend pas en compte la taille de ces clauses (i.e. le nombre de littéraux par clause). Or la taille des clauses dans une contrainte CNF peut avoir une influence importante sur la rapidité d'un solveur SAT sur cette contrainte. Comme l'évaluation d'une valuation d'une contrainte CNF est linéaire par rapport à son nombre total de littéraux, on pourrait également considérer le nombre total de littéraux de chacun de encodages plutôt que leur nombre de clauses comme critère pour choisir un encodage. Même si le nombre total de clauses est généralement utilisé comme critère de comparaison des encodages dans l'état de l'art précité, on penche plutôt pour l'utilisation du nombre total de littéraux. En

<footnote n="2">2. Les valeurs données ici sont exactes si n est une puissance de 2.</footnote>
tout état de cause, on présentera systématiquement par la
suite les valeurs obtenues pour chacun de ces deux critères.
Le tableau 3 permet de déterminer l'encodage avec le plus
petit nombre total de littéraux.

**3.3 Contrainte** ≥ k(x₁, ..., xₙ)

<table><caption>TABLE 4 – Encodage de ≥ k(x₁, ..., xₙ) donnant le nombre total minimal de clauses en fonction de n et k</caption><thead><tr><th colspan="4">Conditions sur n et k par encodage</th></tr><tr><th>N<sup>≥n</sup><sub>≤n-k</sub></th><th>SeqB<sup>n</sup><sub>≥k</sub></th><th>BB<sup>n</sup><sub>≥k,≤n</sub></th><th>SeqU<sup>≥n</sup><sub>≤n-k</sub></th></tr></thead><tbody><tr><td colspan="4">n ≤ 5 et k ∈</td></tr><tr><td>[[1, n]]</td><td>∅</td><td>∅</td><td>∅</td></tr><tr><td colspan="4">6 ≤ n ≤ 8 et k ∈</td></tr><tr><td>[[1, 5]]</td><td>∅</td><td>∅</td><td>[[5, n]]</td></tr><tr><td colspan="4">9 ≤ n ≤ 13 et k ∈</td></tr><tr><td>[[1, 4]]</td><td>∅</td><td>∅</td><td>[[4, n]]</td></tr><tr><td colspan="4">14 ≤ n ≤ 30 et k ∈</td></tr><tr><td>[[1, 4]]</td><td>[[4, k₁]]</td><td>∅</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = [n-1/3].</td></tr><tr><td colspan="4">31 ≤ n ≤ 36 et k ∈</td></tr><tr><td>[[1, 3]]</td><td>[[3, k₁]]</td><td>∅</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = [n-1/3].</td></tr><tr><td colspan="4">37 ≤ n et k ∈</td></tr><tr><td>[[1, 3]]</td><td>[[3, k₂]]</td><td>[[k₂, k₁]]</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = [n²-2n log₂(n)-n+1/2(n-1)]</td></tr><tr><td colspan="4">et k₂ = [n²+2n log₂(n)-2n-2/4(n-1)].</td></tr></tbody></table>

<table><caption>TABLE 5 – Encodage de ≥ k(x₁, ..., xₙ) donnant le nombre total minimal de littéraux en fonction de n et k</caption><thead><tr><th colspan="4">Conditions sur n et k par encodage</th></tr><tr><th>N<sup>≥n</sup><sub>≤n-k</sub></th><th>SeqB<sup>n</sup><sub>≥k</sub></th><th>BB<sup>n</sup><sub>≥k,≤n</sub></th><th>SeqU<sup>≥n</sup><sub>≤n-k</sub></th></tr></thead><tbody><tr><td colspan="4">n ≤ 5 et k ∈</td></tr><tr><td>[[1, n]]</td><td>∅</td><td>∅</td><td>∅</td></tr><tr><td colspan="4">n = 6 et k ∈</td></tr><tr><td>{1, 2, 3, 5}</td><td>∅</td><td>∅</td><td>k = 4</td></tr><tr><td colspan="4">n = 7 et k ∈</td></tr><tr><td>[[1, 4]]</td><td>∅</td><td>∅</td><td>[[4, n]]</td></tr><tr><td colspan="4">8 ≤ n ≤ 10 et k ∈</td></tr><tr><td>[[1, 3]]</td><td>∅</td><td>∅</td><td>[[3, n]]</td></tr><tr><td colspan="4">11 ≤ n ≤ 27 et k ∈</td></tr><tr><td>[[1, 3]]</td><td>[[3, k₁]]</td><td>∅</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = [5n²-15n+3/3(5n-6)].</td></tr><tr><td colspan="4">28 ≤ n ≤ 148 et k ∈</td></tr><tr><td>[[1, 2]]</td><td>[[2, k₁]]</td><td>∅</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = [5n²-15n+3/3(5n-6)].</td></tr><tr><td colspan="4">149 ≤ n et k ∈</td></tr><tr><td>[[1, 2]]</td><td>[[2, k₂]]</td><td>[[k₂, k₁]]</td><td>[[k₁, n]]</td></tr><tr><td colspan="4">où k₁ = [2n²-6n log₂(n)-11n+7/5n-8]</td></tr><tr><td colspan="4">et k₂ = [3n²+6n log₂(n)-4n-4/10(n-1)].</td></tr></tbody></table>

Dans cette section, on compare 5 encodages pour la
contrainte ≥ k(x₁, ..., xₙ). Par l'équivalence (1), on ob-

tient bien la contrainte souhaitée en appliquant les enco-
dages N<sup>n</sup><sub>≤n-k</sub>, SeqU<sup>n</sup><sub>≤n-k</sub> et SeqB<sup>n</sup><sub>≤n-k</sub> à (¬x₁, ..., ¬xₙ).
On note respectivement N<sup>≥n</sup><sub>≤n-k</sub>, SeqU<sup>≥n</sup><sub>≤n-k</sub> et SeqB<sup>≥n</sup><sub>≤n-k</sub>
ces trois encodages. On considère par ailleurs les deux en-
codages SeqB<sup>n</sup><sub>≥k</sub> et BB<sup>n</sup><sub>≥k,≤n</sub>.

Comme précédemment, on détermine les encodages don-
nant le nombre total minimal de clauses (tableau 4) ainsi
que les encodages donnant le nombre total minimal de lit-
téraux (5) en fonction de n et k. On remarque que, dans ce
cas, c'est l'encodage SeqB<sup>≥n</sup><sub>≤n-k</sub> qui est écarté systémati-
quement.

**3.4 Contrainte** = k(x₁, ..., xₙ)

Dans cette section, on compare 7 encodages différents de =
k(x₁, ..., xₙ) parmi lesquels 2 sont des encodages mixtes
entre deux encodages différents. Il s'agit des encodages :

1. $BB_{=k}^n$ (i.e. $BB_{\ge k, \le k}^n$);

2. $SeqB_{=k}^n$;

3. $SeqB_{=n-k}^{≥n}$;

4. $SeqU_{=k}^n$ (i.e. $SeqU_{≤k}^n$ et $SeqU_{≥n-k}^{≥n}$);

5. $N_{=k}^n$ (i.e. $N_{≤k}^n$ et $N_{≥n-k}^{≥n}$);

6. $NS_{=k}^n$ (i.e. $N_{≤k}^n$ et $SeqU_{≤n-k}^{≥n}$);

7. $SN_{=k}^n$ (i.e. $SeqU_{=k}^n$ et $N_{≥n-k}^{≥n}$).

Comme dans les deux sections précédentes, on a déterminé
les encodages donnant le nombre total de clauses minimal
en fonction de n et k ainsi que celui donnant le nombre to-
tal de littéraux minimal en fonction des mêmes paramètres.
Chacun de ces résultats étant difficilement synthétisable en
un seul tableau, on renvoie aux annexes pour le détail pour
tous les entiers $n \in [[6, 17]]$.

<table><caption>TABLE 6 – Encodage de = k(x₁, ..., xₙ) donnant le nombre total minimal de clauses en fonction de k pour $n ≥ 18$</caption><thead><tr><th>Encodage</th><th>Condition sur k</th><th>Proportion<br>en n → +∞</th></tr></thead><tbody><tr><td>$SN_{=k}^n$</td><td>$1 ≤ k < 3$</td><td>0%</td></tr><tr><td>$SeqB_{=k}^n$</td><td>$3 ≤ k < k_2$</td><td>25%</td></tr><tr><td>$BB_{=k}^n$</td><td>$k_2 ≤ k < k_1$</td><td>50%</td></tr><tr><td>$SeqB_{=n-k}^{≥n}$</td><td>$k_1 ≤ k < n-2$</td><td>25%</td></tr><tr><td>$NS_{=k}^n$</td><td>$n-2 ≤ k < n$</td><td>0%</td></tr><tr><td colspan="3">où $k_1 = \lfloor \frac{3n^2-2n \log_2(n)-2n+3}{4n-3} \rfloor$</td></tr><tr><td colspan="3">et $k_2 = \lfloor \frac{n^2+2n \log_2(n)-n-3}{4n-3} \rfloor$.</td></tr></tbody></table>

Pour $n \le 5$, c'est l'encodage naïf $N_{=k}^n$ qui donne les plus petits nombres de clauses et de littéraux quel que soit $k$. Les deux tableaux 6 et 7 donnent les résultats pour $n \ge 18$. On remarquera que les encodages $SeqU_{=k}^n$ et $N_{=k}^n$ en sont absents. Par ailleurs, on a indiqué, pour chaque encodage, la limite de la proportion à $n$ donné de valeurs différentes de $k$ pour laquelle cet encodage est optimal lorsque $n$ tend vers l'infini.
<table><caption>TABLE 7 – Encodage de $= k(x_1, ..., x_n)$ donnant le nombre total minimal de littéraux en fonction de $k$ pour $n ≥ 18$</caption><thead><tr><th>Encodage</th><th>Condition sur k</th><th>Proportion en n → +∞</th></tr></thead><tbody><tr><td>$SN^{n}_{=k}$</td><td>$k = 1$</td><td>0%</td></tr><tr><td>$SeqB^{n}_{=k}$</td><td>$2 ≤ k < k_2$</td><td>30%</td></tr><tr><td>$BB^{n}_{=k}$</td><td>$k_2 ≤ k < k_1$</td><td>40%</td></tr><tr><td>$SeqB^{n}_{=n-k}$</td><td>$k_1 ≤ k < n - 1$</td><td>30%</td></tr><tr><td>$NS^{n}_{=k}$</td><td>$k = n - 1$</td><td>0%</td></tr><tr><td colspan="3">où $k_1 = \left[ \frac{7n^2 - 6n \log_2(n) - 6n + 1}{10n - 9} \right]$<br>et $k_2 = \left[ \frac{3n^2 + 6n \log_2(n) - 3n - 1}{10n - 9} \right]$.</td></tr></tbody></table>

### 3.5 Contrainte $≥ k_1, ≤ k_2(x_1, ..., x_n)$

On étudie ici le cas d'une contrainte donnant un intervalle. On compare 7 encodages de cette contrainte, correspondant aux cas généraux des encodages de $= k(x_1, ..., x_n)$ de la section précédente. Il s'agit des encodages :

1. $BB^{n}_{≥k_1, ≤k_2}$;

2. $SeqB^{n}_{≥k_1, ≤k_2}$;

3. $SeqB^{n}_{≥n-k_2, ≤n-k_1}$;

4. $SeqU^{n}_{≥k_1, ≤k_2}$ (i.e. $SeqU^{n}_{≤k_2}$ et $SeqU^{n}_{≤n-k_1}$);

5. $N^{n}_{≥k_1, ≤k_2}$ (i.e. $N^{n}_{≤k_2}$ et $N^{n}_{≤n-k_1}$);

6. $SN^{n}_{≥k_1, ≤k_2}$ (i.e. $SeqU^{n}_{≤k_2}$ et $N^{n}_{≤n-k_1}$);

7. $NS^{n}_{≥k_1, ≤k_2}$ (i.e. $N^{n}_{≤k_2}$ et $SeqU^{n}_{≤n-k_1}$).

On ne fait pas ici une comparaison exhaustive de toutes les valeurs possibles de $k$ et $n$ comme on a pu le faire pour les contraintes précédentes car cela nous semble trop fastidieux et difficilement exposable de manière concise. On donne simplement les expressions des nombres totaux de clauses et nombres totaux de littéraux pour chacun de ces encodages. Ces expressions peuvent être évaluées au cas par cas pour déterminer une valeur minimale et choisir l'encodage associé lorsque $n$ est faible.

<table><caption>TABLE 8 – Nombre total de clauses pour les encodages de la contrainte $≥ k_1, ≤ k_2(x_1, ..., x_n)$</caption><thead><tr><th>Encodage</th><th>Nombre total de clauses</th></tr></thead><tbody><tr><td>$BB^{n}_{≥k_1, ≤k_2}$</td><td>$n^2 + 2n \log_2(n) + 2n - k_2 + k_1 - 2$</td></tr><tr><td>$SeqB^{n}_{≥k_1, ≤k_2}$</td><td>$4nk_2 + 3n - 3k_2 + 1$</td></tr><tr><td>$SeqB^{n}_{≥n-k_2, ≤n-k_1}$</td><td>$4n^2 - 4nk_1 + 3k_1 + 1$</td></tr><tr><td>$SeqU^{n}_{≥k_1, ≤k_2}$</td><td>$2n^2 + 2n(k_2 - k_1) - n - 3(k_2 - k_1) - 2$</td></tr><tr><td>$N^{n}_{≥k_1, ≤k_2}$</td><td>$(\binom{n}{k_2+1} + \binom{n}{k_1-1})$</td></tr><tr><td>$SN^{n}_{≥k_1, ≤k_2}$</td><td>$(\binom{n}{k_1-1} + 2nk_2 + n - 3k_2 - 1)$</td></tr><tr><td>$NS^{n}_{≥k_1, ≤k_2}$</td><td>$(\binom{n}{k_2+1} + 2n^2 - 2nk_1 - 2n + 3k_1 - 1)$</td></tr></tbody></table>

Sinon, en dehors de certains effets de bord quand $k_1 ≤ 2$ ou bien $k_2 ≥ n - 2$, on peut voir que, pour $n$ suffisamment grand, ce sont les trois premiers encodages qui sont les plus performants. On peut alors utiliser le protocole suivant pour choisir un encodage :

<table><caption>TABLE 9 – Nombre total de littéraux pour les encodages de la contrainte $≥ k_1, ≤ k_2(x_1, ..., x_n)$</caption><thead><tr><th>Encodage</th><th>Nombre total de littéraux</th></tr></thead><tbody><tr><td>$BB^{n}_{≥k_1, ≤k_2}$</td><td>$3n^2 + 6n \log_2(n) + 4n - k_2 + k_1 - 6$</td></tr><tr><td>$SeqB^{n}_{≥k_1, ≤k_2}$</td><td>$10nk_2 + 7n - 9k_2 - 1$</td></tr><tr><td>$SeqB^{n}_{≥n-k_2, ≤n-k_1}$</td><td>$10n^2 - 10nk_1 - 2n + 9k_1 - 1$</td></tr><tr><td>$SeqU^{n}_{≥k_1, ≤k_2}$</td><td>$5n^2 + 5n(k_2 - k_1) - 7n - 9(k_2 - k_1) + 2$</td></tr><tr><td>$N^{n}_{≥k_1, ≤k_2}$</td><td>$(n - k_2) \binom{n}{k_2} + k_1 \binom{n}{k_1}$</td></tr><tr><td>$SN^{n}_{≥k_1, ≤k_2}$</td><td>$k_1 \binom{n}{k_1} + 5nk_2 + n - 9k_2 + 1$</td></tr><tr><td>$NS^{n}_{≥k_1, ≤k_2}$</td><td>$(n - k_2) \binom{n}{k_2} + 5n^2 - 5nk_1 - 8n + 9k_1 + 1$</td></tr></tbody></table>

$$ \begin{array}{lll} \text{Si} & \min(k_2, n - k_1) \ge \frac{3}{10} n & \text{choisir } BB^{n}_{\ge k_1, \le k_2} \\ \text{Sinon si} & k_2 \le \min\left(\frac{3}{10} n, n - k_1\right) & \text{choisir } SeqB^{n}_{\ge k_1, \le k_2} \\ \text{Sinon} & & \text{choisir } SeqB^{n}_{\ge n-k_2, \le n-k_1} \end{array} \quad (3) $$

Le protocole ci-dessus utilise le critère du nombre total de littéraux minimal. Pour utiliser le critère du nombre total de clauses, il suffit de remplacer $\frac{3}{10}$ par $\frac{1}{4}$.

### 3.6 Contrainte $∈ K(x_1, ..., x_n)$

Dans cette section, on considère un sous-ensemble $K = \{k_1, ..., k_m\} \subset [0, n]$ avec $m ≥ 2$ et $k_1 < k_2 < ... < k_m$. Le cas général d'une contrainte d'appartenance du cardinal à un sous-ensemble $K$ se distingue entièrement des cas précédents. En effet, la proposition $k ∈ K$ est équivalente à la disjonction $\bigvee_{i=1}^{m} [k = k_i]$. Ainsi, à part le cas particulier d'un intervalle traité précédemment, on ne peut pas se ramener directement à une conjonction des encodages CNF décrits précédemment. Or obtenir une contrainte CNF à partir d'une disjonction de contraintes CNF nécessite une opération supplémentaire. Effectuer cette opération est prohibitif si l'on considère directement des disjonctions des encodages précédents. Toutefois, on peut également considérer ces disjonctions au sein d'un encodage séquentiel bidirectionnel unique ce qui permet de rendre cette opération tout à fait envisageable.

En effet, la contrainte suivante est bien un encodage de la contrainte $∈ K(x_1, ..., x_n)$.

$$ \text{SeqB}^{n}_{\#} \wedge \left( \bigvee_{i=1}^{m} (s_{n,k_i} \wedge \neg s_{n,k_i+1}) \right) \quad (4) $$

Cette encodage n'est pas une contrainte CNF mais on peut se ramener à une contrainte CNF équisatisfaisable facilement en introduisant $m$ variables supplémentaires $y_0, ..., y_{m-1}$ [8]. On définit ainsi l'encodage $SeqB^{n}_{∈K}$ de la contrainte $∈ K(x_1, ..., x_n)$ comme étant la contrainte CNF ci-dessous :
$$
\begin{align*}
\text{Seq}B_{\#}^{n} \quad &\wedge \bigwedge_{i=1}^{m} \left( s_{n,k_i} \lor \neg y_{i-1} \lor \left( \bigvee_{j=i}^{m-1} y_j \right) \right) \\
&\wedge \bigwedge_{i=1}^{m} \left( \neg s_{n,k_i+1} \lor \neg y_{i-1} \lor \left( \bigvee_{j=i}^{m-1} y_j \right) \right) \\
&\wedge y_0 \tag{Seq$B_{\#}^n \in \mathcal{K}$}
\end{align*}
$$

Cette contrainte a un nombre total de clauses égal à :

$$4nk_m + 3n - 3k_m + 2m \quad (5)$$

et un nombre total de littéraux égal à :

$$10nk_m + 7n - 9k_m + m^2 + 3m - 2 \quad (6)$$

Enfin, on peut remarquer que l'encodage $SeqB_{\#}^n \in \overline{\mathcal{K}}$ (où $\overline{\mathcal{K}}$ est le complémentaire de $\mathcal{K}$) appliqué à $(\neg x_1, ..., \neg x_n)$ donne également la contrainte $\in \mathcal{K}(x_1, ..., x_n)$. On note $SeqB_{\#}^{-n} \in \overline{\mathcal{K}}$ cet encodage. Il peut éventuellement être plus performant que l'encodage précédent selon $\mathcal{K}$. Son nombre total de clauses et son nombre total de littéraux s'obtiennent en remplaçant $k_m$ par $\max(\overline{\mathcal{K}})$ et $m$ par $n - m$ dans (5) et (6).

Le pire des cas est atteint pour une contrainte de type $k$ pair. On a alors un nombre de clauses de l'ordre de $4n^2$ et un nombre de littéraux de l'ordre de $10.5n^2$ ce qui est tout à fait raisonnable. Par ailleurs, à notre connaissance, il s'agit du seul encodage CNF de la littérature de la contrainte $\in \mathcal{K}(x_1, ..., x_n)$.

## 4 Conclusion

Lorsque l'on recherche un algorithme optimisé pour un problème donné, il est rare de découvrir un seul algorithme qui soit le plus optimisé pour chacune des occurrences de ce problème. Pour le problème d'une résolution CNF-SAT d'une contrainte de cardinalité, on peut remarquer que chacun des encodages d'une contrainte de cardinalité considérés dans cet article est préférable aux autres pour au moins quelques valeurs différentes de $k$ et $n$. Par ailleurs, les comportements des différentes solutions à l'infini ne préjugent en rien quant à leurs comportements en faible dimension. Par exemple dans le cas des contraintes $\le k(x_1, ..., x_n)$ et $\ge k(x_1, ..., x_n)$, l'encodage proposé par Bailleux et Boufkhad est préférable (selon le critère du nombre total de littéraux) dans environ 10% des cas lorsque $n$ est très grand mais n'est préférable en aucun cas lorsque $n < 149$. Afin de pouvoir déterminer l'encodage réellement le mieux adapté à une contrainte et des paramètres donnés, il est nécessaire de passer par une étude exhaustive des cas comme cela a été réalisé dans cet article.

On pourrait objecter que, si $n$ est petit alors la taille de l'encodage le sera également et qu'en conséquence, même si on reste loin de l'optimum possible, on pourra négliger

l'accroissement. Cet argument ne tient toutefois pas longtemps car un gain fixe sur une opération peut être non négligeable, d'autant plus si cette opération est répétée de nombreuses fois au cours d'un même processus.

Par ailleurs, le nouvel encodage séquentiel bidirectionnel qui est proposé dans cet article offre une performance nettement améliorée dans certains cas ainsi que des perspectives nouvelles.

En effet, dans le cas d'une contrainte de type $k(x_1, ..., x_n)$, les nombres totaux de clauses et de littéraux sont au mieux quadratiques en $n$ pour les autres encodages et ceci quel que soit $k$. Toutefois, dans un certain nombre de problèmes, $k$ est fixé indépendamment de $n$. Les nombres totaux de clauses et de littéraux de l'encodage séquentiel bidirectionnel sont alors linéaires en $n$. Cet encodage a ainsi pu être mis à profit dans le cas de la résolution SAT d'un problème d'emploi du temps en BTS [6] qui comporte un certain nombre de contraintes de type $= 3(x_1, ..., x_n)$. Cet encodage offre également de nouvelles perspectives via son application aux contraintes de type $\in \mathcal{K}(x_1, ..., x_n)$ pour lesquelles il n'existait pas avant, à notre connaissance, d'encodage performant.

Enfin, on peut noter que sa présentation explicite (semblable à celle de l'encodage séquentiel dans [12] et qui a sûrement contribué à sa popularité) en permet une implémentation directe.

Le travail de recherche présenté dans cet article est d'ordre théorique. Si les critères du nombre total de clauses ou du nombre total de littéraux sont généralement pertinents, ils ne suffisent pas à déterminer l'encodage le mieux adapté qui pourra dépendre non seulement du problème considéré mais également du solveur utilisé. Il appelle donc d'autres travaux qui permettront de mettre en pratique (tels que [6]) et de valider ces résultats. Il sera également prolongé de manière à intégrer au processus de choix des encodages à base de réseaux dont l'encodage de $\le k(x_1, ..., x_n)$ défini dans [2].

## 5 Annexe

<table><caption>TABLE 10 – Encodage de la contrainte $= k(x_1, ..., x_n)$ donnant le nombre total minimal de clauses pour $n \in [6, 17]$</caption><thead><tr><th>k</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th><th>16</th><th>17</th></tr></thead><tbody><tr><td>1</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td></tr><tr><td>2</td><td>5</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td></tr><tr><td>3</td><td>5</td><td>5</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td></tr><tr><td>4</td><td>5</td><td>5</td><td>5</td><td>4</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><td>5</td><td>7</td><td>7</td><td>7</td><td>4</td><td>1</td><td>1</td><td>1</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><td>6</td><td></td><td>7</td><td>7</td><td>7</td><td>3</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>7</td><td></td><td></td><td>7</td><td>7</td><td>7</td><td>3</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>8</td><td></td><td></td><td></td><td>7</td><td>7</td><td>7</td><td>3</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>9</td><td></td><td></td><td></td><td></td><td>7</td><td>7</td><td>7</td><td>3</td><td>3</td><td>1</td><td>1</td><td>1</td></tr><tr><td>10</td><td></td><td></td><td></td><td></td><td></td><td>7</td><td>7</td><td>7</td><td>3</td><td>1</td><td>1</td><td>1</td></tr><tr><td>11</td><td></td><td></td><td></td><td></td><td></td><td></td><td>7</td><td>7</td><td>7</td><td>3</td><td>3</td><td>3</td></tr><tr><td>12</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>7</td><td>7</td><td>7</td><td>3</td><td>3</td></tr><tr><td>13</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>7</td><td>7</td><td>7</td><td>7</td></tr><tr><td>14</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>7</td><td>7</td><td>7</td></tr><tr><td>15</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>7</td><td>7</td></tr><tr><td>16</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>7</td></tr></tbody></table>

Les tableaux 10 et 11 donnent, en fonction de $k$ et $n$, les encodages de $= k(x_1, ..., x_n)$ pour $n \in [6, 17]$ ayant un
<table><caption>TABLE 11 – Encodage de la contrainte = $k(x_1, ..., x_n)$ donnant le nombre total minimal de littéraux pour $n \in [6, 17]$</caption><thead><tr><th>k</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th><th>16</th><th>17</th></tr></thead><tbody><tr><td>1</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td></tr><tr><td>2</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>6</td><td>2</td></tr><tr><td>3</td><td>5</td><td>6</td><td>4</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><td>4</td><td>7</td><td>7</td><td>4</td><td>4</td><td>4</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><td>5</td><td>5</td><td>7</td><td>4</td><td>4</td><td>4</td><td>4</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><td>6</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>7</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>8</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>9</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>10</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>11</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>12</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>13</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>14</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>15</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>16</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

nombre total minimal de clauses et de littéraux respectivement. Les encodages sont indiqués dans le tableau par un numéro qui correspond à leur numérotation dans la section 3.4.

Références

[1] R. Asín, R. Nieuwenhuis, A. Oliveras, and E. Rodríguez-Carbonell. Cardinality networks and their applications. In *International Conference on Theory and Applications of Satisfiability Testing*, pages 167–180. Springer, 2009.

[2] R. Asín, R. Nieuwenhuis, A. Oliveras, and E. Rodríguez-Carbonell. Cardinality networks : a theoretical and empirical study. *Constraints*, 16(2):195–221, 2011.

[3] O. Bailleux and Y. Boufkhad. Efficient cnf encoding of boolean cardinality constraints. In *International conference on principles and practice of constraint programming*, pages 108–122. Springer, 2003.

[4] O. Bailleux, Y. Boufkhad, and O. Roussel. A translation of pseudo-boolean constraints to sat. *Journal on Satisfiability, Boolean Modeling and Computation*, 2:191–200, 2006.

[5] O. Bailleux, Y. Boufkhad, and O. Roussel. New encodings of pseudo-boolean constraints into cnf. In *International Conference on Theory and Applications of Satisfiability Testing*, pages 181–194. Springer, 2009.

[6] T. Delacroix. Planifier l'épreuve e5 à l'aide d'un solveur sat. In *APIA, Conférence Nationale sur les Applications Pratiques de l'Intelligence Artificielle*, 2018.

[7] N. Eén and N. Sorensson. Translating pseudo-boolean constraints into sat. *Journal on Satisfiability, Boolean Modeling and Computation*, 2:1–26, 2006.

[8] ENS. Concours d'admission - composition d'informationique - a -, 2016.

[9] A. M. Frisch and P. A. Giannaros. Sat encodings of the at-most-k constraint. some old, some new, some fast, some slow. In *Proc. of the Tenth Int. Workshop of Constraint Modelling and Reformulation*, 2010.

[10] J. Marques-Silva and I. Lynce. Towards robust cnf encodings of cardinality constraints. *Principles and Practice of Constraint Programming–CP 2007*, pages 483–497, 2007.

[11] MiniZinc. Minizinc challenge 2017 results, 2017.

[12] C. Sinz. Towards an optimal cnf encoding of boolean cardinality constraints. *CP*, 3709:827–831, 2005.

[13] P. J. Stuckey, T. Feydy, A. Schutt, G. Tack, and J. Fischer. The minizinc challenge 2008–2013. *AI Magazine*, 35(2):55–60, 2014.

[14] N. Tamura, M. Banbara, and T. Soh. Compiling pseudo-boolean constraints to sat with order encoding. In *Tools with Artificial Intelligence (ICTAI), 2013 IEEE 25th International Conference on*, pages 1020–1027. IEEE, 2013.

[15] J. P. Warners. A linear-time transformation of linear inequalities into conjunctive normal form. *Information Processing Letters*, 68(2):63–69, 1998.
<figure><img src="image_51.png" /></figure>
# Inférence bayésienne pour l'estimation de déformations larges par champs gaussien: application au recalage d'images multi-modales

Thomas Deregnaucourt¹

Chafik Samir¹

Anne-Françoise Yao²

¹LIMOS, CNRS UMR 6620, Université Clermont Auvergne, France

²LMBP, CNRS UMR 6158, Université Clermont Auvergne, France

thomas.deregnaucourt@uca.fr - chafik.samir@uca.fr - anne.yao@uca.fr

## Résumé

Le problème de recalage d'images consiste à estimer la déformation globale entre une image source $I_1$ et une image cible $I_2$. Dans ce contexte, nous nous intéressons à l'estimation d'un champ de déformation $U$ sur le domaine $\Omega = [0, 1]^2$ de $I_1$ sachant $U$ sur un ensemble fini de courbes $\beta \in \Omega$. Pour ce faire, nous proposons une nouvelle méthode basée sur des modèles gaussiens pour recaler des images multimodales. La méthode proposée commence par résoudre le problème de correspondance entre les courbes $\beta$s puis estime le déplacement sur tout $\Omega$. La solution optimale est calculée à l'aide du maximum de vraisemblance et de l'inférence bayésienne. D'après les résultats obtenus sur des données réelles et simulées, la déformation résultante a l'avantage d'être exacte sur les observations et d'être lisse sur $\Omega$.

## Mots Clef

Recalage d'images, Statistique spatiale, Processus gaussiens, Inférence bayésienne.

## Abstract

Image registration aims to estimate the global deformation between a target image $I_1$ and a reference image $I_2$. In this context, we will focus on estimating a random field $U$ on the $I_1$ domain $\Omega = [0, 1]^2$ based on observations of $U$ on a finite set of curves $\beta \in \Omega$. Indeed, we present a new multimodal image registration method based on Gaussian random fields. The proposed method first find the optimal correspondences between curves $\beta$s then estimate the deformation vector field on $\Omega$. The optimal solution is computed using Maximum Likelihood and Bayesian inference. Based on results using both real and simulated data, the resulting deformation has the advantage of being exact on the observations as being sufficiently smooth over the whole $\Omega$.

## Keywords

Image registration, Spatial statistics, Gaussian process, Bayesian inference.

# 1 Introduction

Le recalage d'images est une méthode qui vise à estimer la transformation, soumise à certaines contraintes, d'une image source $I_1$ vers une image cible $I_2$, afin de fusionner leurs informations complémentaires. Cette méthode est utilisée dans de nombreux domaines d'applications [11, 15, 2]. En imagerie médicale on utilise le recalage d'images pour détecter des maladies, valider un traitement, comparer les données du patient avec des atlas anatomiques, etc. [12]. L'estimation de cette déformation est basée soit sur les intensités, soit sur des caractéristiques géométriques, soit sur les deux [12, 10]. Dans le premier cas, on cherche une transformation concervant la correspondance entre les niveaux de gris, et dans le second la correspondance entre des points, des courbes, etc.

Pour cet article, nous nous sommes intéressés au problème de l'endométriose. Cette maladie est provoquée par l'apparition de muqueuse utérine, aussi appelé endomètre, en dehors de la cavité utérine. Elle touche approximativement 10% des femmes en âge de procréer, et peut provoquer divers symptômes tels que des douleurs pelviennes chroniques, une dysenterie sévère, une infertilité, etc. [3]. Il est alors nécessaire de pouvoir détecter si une patiente à l'endométriose afin de la traiter efficacement, que ce soit par des antalgiques, des traitements hormonaux, ou par chirurgie dans les cas les plus sévères. L'endomètre pouvant pénétrer d'autres tissus et organes, les méthodes de détection de l'endométriose se basent sur plusieurs modalités d'images, donnant des informations complémentaires. Plus précisément, l'échographie permet d'avoir une estimation de l'infiltration de l'endomètre dans d'autres tissus, et l'imagerie par résonance magnétique (IRM) une position précise des kystes [3]. La fusion des données IRM/échographie permet alors d'avoir un diagnostic précis, mais nécessite un recalage entre ces deux modalités.

Dans notre cas, les deux images $I_1$ et $I_2$ représentent respectivement l'échographie et l'IRM d'un même organe. Cependant, comme le montre la Figure 1, les modalités d'images ont des distributions d'intensités différentes, ce qui rend inefficace les méthodes de recalage basées sur les intensités. D'autre part, un spécialiste peut extraire le con-
tour des organes présents dans les deux images. Nous allons alors utiliser ces dernières pour effectuer le recalage. Pour ce faire, nous estimerons le champ de déformation entre les deux images, à l'aide des champs gaussiens.

<figure><img src="image_52.png" /><figcaption>Figure 1: Exemple de courbes extraites manuellement issues d'images multimodales représentant les mêmes organes (en rouge et en jaune respectivement) : échographie à gauche et IRM à droite.</figcaption></figure>

Le reste du papier est organisé de la manière suivante. Dans la section 2 nous formaliserons notre problème, et expliquerons en détail notre méthode de résolution. Puis nous présenterons nos résultats, sur des données synthétiques et réelles, dans la section 3. Enfin, la section 4 conclura ce papier.

# 2 Méthodologie

## 2.1 Formulation du problème

Soient $\Omega$ un domaine fermé de $\mathbb{R}^2$, $\beta_1 \subset I_1$ les courbes de l'échographie et $\beta_2 \subset I_2$ celles de l'IRM. On cherche à estimer un champ de déformation $\Psi$ sur $\Omega$ transformant $I_1$ en $I_2$. Ce champ doit déformer $\beta_1$ en $\beta_2$, tout en étant lisse. Pour résoudre ce problème, il nous faut:

1. Trouver une correspondance optimale entre $\beta_1$ et $\beta_2$.

2. Estimer une déformation $\Psi$ induite par un champ de déplacement $U$, c'est-à-dire telle que:

$$ \Psi : \Omega \to \Omega \\ X \mapsto \Psi(X) = X + U(X) $$

et vérifiant la contrainte $\Psi(\beta_1) = \beta_2$

Nous allons tout d'abord nous intéresser au premier problème.

## 2.2 Correspondance optimale entre courbes

Afin de trouver une correspondance optimale entre les courbes, nous adaptons les travaux de Srivastava et al. [13]. Dans ce papier, les auteurs s'intéressaient à l'analyse des formes, et cherchaient une invariance aux transformations préservant la forme, c'est-à-dire à la translation, la rotation, la mise à l'échelle et la re-paramétrisation. Dans notre cas, la translation et la rotation sont déjà fixées pour

toute l'image, et la mise à l'échelle n'est pas une nuisance. Ainsi, nous cherchons seulement l'invariance à la re-paramétrisation. Par brièveté, nous ne décrivons le processus que pour les courbes ouvertes, mais celui-ci peut être étendu simplement à des courbes fermés [7].

Soit $\beta : [0, 1] \to \mathbb{R}^2$ une courbe ouverte paramétrisée. On utilise par la suite la représentation square-root velocity function (SRVF) $q$ de $\beta$, défini par:

$$ q : [0, 1] \to \mathbb{R}^2 \\ t \mapsto \frac{\beta(\dot{t})}{\sqrt{\|\dot{\beta}(t)\|_2}} $$

Le mapping $\beta \iff (\beta(0), q)$ étant une bijection, il est possible de revenir aux courbes originales en stockant le premier point de ces dernières. On note $C$ l'espace de SRVFs:

$$ C = \{ q \in \mathbb{L}^2([0, 1], \mathbb{R}^2) \mid \int_0^1 \|q(t)\|_2^2 dt = 1 \} $$

Comme on recherche une représentation des courbes invariants aux re-paramétrisations, nous allons utiliser des classes d'équivalence. Nous définissons d'abord le groupe des re-paramétrisations $\Gamma$:

$$ \Gamma = \{ \gamma : [0, 1] \to [0, 1] \mid \gamma(0) = 0, \gamma(1) = 1, 0 < \dot{\gamma} < \infty \} $$

La re-paramétrisation d'une courbe $\beta$ par $\gamma \in \Gamma$ est donnée par $\beta \circ \gamma$, et la SRVF de cette courbe re-paramétrisée est alors $(q \circ \gamma)\sqrt{\dot{\gamma}}$. Ainsi, pour unifier tous les éléments de $C$ représentant la même courbe, on défini nos classes d'équivalence par $[q] = \{(q \circ \gamma)\sqrt{\dot{\gamma}} \mid \gamma \in \Gamma\}$. On note $S = C/\Gamma = \{[q], q \in C\}$ l'ensemble des classes d'équivalence. Afin de comparer deux courbes, on impose la métrique $\mathbb{L}^2$ à $S$. Sous la représentation SRVF, la métrique $\mathbb{L}^2$ correspond à une métrique élastique sur l'espace original des courbes [8], ce qui permet de déformer les courbes pour avoir la correspondance optimale. Cette déformation optimale entre deux points sur $S$ est obtenue par le chemin géodésique, et la distance entre elles est définie par la longueur du chemin.

Afin de voir comment ceci peut résoudre notre problème, on note $q_1$ et $q_2$ la représentation SRVF respective des deux courbes $\beta_1$ et $\beta_2$. Afin de calculer la géodésique entre leurs classes d'équivalence $[q_1]$ et $[q_2]$, on fixe $q_1$, et on cherche la re-paramétrisation optimale de $q_2$ en résolvant $\hat{\gamma} = \arg \inf_{\gamma \in \Gamma} \|q_1 - (q_2 \circ \gamma)\sqrt{\dot{\gamma}}\|_2^2$. La re-paramétrisation $\hat{\gamma}$ donnera alors la correspondance optimale entre les courbes. Par la suite, on note $\{X_i, i = 1, \dots, N\}$ l'ensemble de $N$ points représentant la discrétisation de $\beta_1$ et $\{U_i = U(X_i), i = 1, \dots, N\}$ les déplacements correspondants donnés par $\beta_2 \circ \hat{\gamma}$. Afin de résoudre le second problème, nous supposons que $U$ est un champ gaussien.

## 2.3 Champ de déformation gaussien

On rappelle qu'un champ gaussien $U$ est défini par:

$$ U(X) \sim \mathcal{N}(\mu(X), C(X)) $$
où $\mu(X)$ et $C(X)$ sont respectivement la moyenne et la variance de $U(X)$. Une loi gaussienne étant entièrement décrite par sa moyenne et sa variance, il nous suffit de trouver ces derniers pour définir notre champ. Pour ce faire, nous supposons tout d'abord que $U$ est un champ stationnaire, c'est-à-dire que $\mu(X) = \mu, \forall X \in \Omega$. On a alors:

$$ \mathcal{N}(\mu(X), C(X)) = \mu + \mathcal{N}(0, C(X)) $$

ce qui implique que $\mu$ est une translation sur l'image $I_1$. Nous pouvons alors supposer que $\mu = 0$. Nous estimons ensuite $C(X)$ par une méthode paramétrique. Il existe un grand choix de fonctions de covariance candidates dans la littérature [14, 1]. Dans ce travail, nous avons choisi $C$ comme fonction de covariance de Matérn :

$$ C(h) = \tau \frac{2^{1-\nu}}{\Gamma(\nu)} (h\alpha)^{\nu} K_{\nu}(h\alpha) \quad (1) $$

où $h$ est la corrélation spatiale et $K$ la fonction de Bessel modifiée de seconde espèce. Généralement, $\tau > 0$ est appelé le paramètre de variance (marginale), $\alpha > 0$ le paramètre d'échelle et $\nu > 0$ le paramètre de lissage. Si $\nu = \frac{1}{2} + k, k \in \mathbb{N}$, l'équation 1 se réduit au produit d'une exponentielle et d'un polynôme[5]:

$$ C(h) = \tau e^{-h\alpha} \sum_{l=0}^{k} \frac{(k+l)!}{(2k)!} \binom{k}{l} (2h\alpha)^{k-l} $$

Lorsque $\nu = \frac{1}{2}$, $C$ est la fonction de covariance exponentielle, et elle devient gaussienne pour $\nu = +\infty$. De manière plus générale, pour $\nu = \frac{1}{2} + k$, le champ $U$ sera de classe $C^k$. Par conséquent, définir notre champ rendant à estimer l'hyperparamètre $\theta = (\tau, \alpha, \nu)$ de la fonction de covariance. On note $C_\theta$ la fonction de covariance d'hyperparamètre $\theta$, et $\Sigma_\theta$ la matrice de covariance associée aux points $\{X_i, i = 1, \dots, N\}$, donnée par:

$$ \Sigma_{\theta} = \begin{pmatrix} C_{\theta} (\|X_1 - X_1\|) & \cdots & C_{\theta} (\|X_1 - X_N\|) \\ \vdots & \ddots & \vdots \\ C_{\theta} (\|X_N - X_1\|) & \cdots & C_{\theta} (\|X_N - X_N\|) \end{pmatrix} $$

## 2.4 Estimation des paramètres de la fonction de covariance

**Estimation par maximum de vraisemblance.** Le premier estimateur considéré est obtenu par maximum de vraisemblance. Dans notre modèle, la fonction de vraisemblance est définie par:

$$ L(\theta | U_X) = f(U_X | \theta) = \frac{1}{(2\pi)^{N/2} |\Sigma_\theta|^{1/2}} e^{-\frac{U_X^T \Sigma_\theta^{-1} U_X}{2}} $$

où $U_X = (U_1 \cdots U_N)$. Pour ce faire, nous devons minimiser la fonction de log-vraisemblance négative, donnée par:

$$ -\log(L(\theta | U_X)) = \frac{N}{2} \ln(2\pi) + \frac{N}{2} \ln(\tau) + \frac{\ln|V_{\alpha, \nu}|}{2} + \frac{U_X^T V_{\alpha, \nu}^{-1} U_X}{2\tau} $$

où $\tau V_{\alpha, \nu} = \Sigma_\theta$. Il n'existe cependant pas de solution analytique à cette équation, et devons alors utiliser des méthodes numériques pour déterminer $\tilde{\theta}$. Pour ce faire, nous avons choisi de comparer les méthodes de Nelder-Mead [9], la descente du gradient et de Newton. L'optimisation sur $\nu$ étant difficile dans notre cas, nous avons estimé ce paramètre par validation croisée.

**Estimation par inférence bayésienne.** Malgré l'utilisation de méthodes itératives, notre estimation de l'estimateur du maximum de vraisemblance peut converger vers des maximums locaux. Afin d'éviter cela, nous avons choisi d'utiliser d'autres estimateurs basés sur l'inférence bayésienne. On va alors trouver des estimateurs à partir de la loi a posteriori de nos paramètres $f(\theta | U_X)$. Cette dernière est construite, avec une loi a priori $\pi(\theta)$ sur nos paramètres, à l'aide de la règle de Bayes:

$$ f(\theta | U_X) = \frac{f(U_X | \theta) \pi(\theta)}{\pi(U_X)} \propto L(\theta | U_X) \pi(\theta) $$

Cependant, la loi de la densité a posteriori de nos paramètres n'étant pas calculable, nous allons alors échantilloner cette distribution. Pour ce faire nous utilisons une méthode de Monte-Carlo par chaîne de Markov (MCMC): l'algorithme de Metropolis-Hastings [6]. Ce dernier construit, à partir d'une loi de proposition $q(\cdot | \theta)$, une chaîne de Markov de la manière suivante.

* Choisir $\theta^1 \sim \pi(\theta)$

* Créer $\theta^{t+1}$ à l'aide de $\theta^t$

1. Générer $\theta^* \sim q(\cdot | \theta^t)$

2. Calculer la probabilité d'acceptation $p$:

$$ p = \min \left( 1, \frac{\pi(\theta^{t+1}) L(\theta^{t+1} | U_X) q(\theta^t | \theta^{t+1})}{\pi(\theta^t) L(\theta^t | U_X) q(\theta^{t+1} | \theta^t)} \right) $$

3. Choisir $\theta^{t+1} = \theta^*$ avec probabilité $p$, sinon choisir $\theta^{t+1} = \theta^t$

Afin de construire notre chaîne de Markov, nous devons définir les lois de $\pi(\theta)$ et $(q(\theta | \cdot))$. Pour ce faire, nous supposons tout d'abord que ces lois sont séparables, c'est-à-dire que $q(\theta | \cdot) = q(\tau | \cdot)q(\alpha | \cdot)q(\nu | \cdot)$ et $\pi(\theta) = \pi(\tau)\pi(\alpha)\pi(\nu)$. N'ayant que peu d'informations a priori sur nos paramètres, nous choisissons de mettre des lois peu informatives, dont un résumé est présenté en Tableau 1.

<table><caption>Tableau 1: Distribution a priori et de proposition sur le paramètre $\theta$.</caption><thead><tr><th>Lois a priori π(.)</th><th>Lois de proposition q(.)|θ̂</th></tr></thead><tbody><tr><td>α ~ U[0, 1]</td><td>α ~ U[α̃ − 0.05, α̃ + 0.05]</td></tr><tr><td>τ ~ U[0, 500]</td><td>τ ~ U[τ̃ − 50, τ̃ + 50]</td></tr><tr><td>ν ~ U[[1/2, ..., 11/2]]</td><td>ν ~ U[[ν̃ − 1, ..., ν̃ + 1]]</td></tr></tbody></table>
Une fois la chaine MCMC construite, nous avons choisi d'estimer $\hat{\theta}$ à partir de la loi a posteriori $f(\alpha | U_X)$, plutôt que de $f(\theta | U_X)$. Pour ce faire, on estime tout d'abord $\hat{\alpha}$, puis on sélectionne l'hyperparamètre $\hat{\theta}$ correspondant. Il existe trois estimateurs bayésiens, que nous utiliserons par la suite: le maximum a posteriori (MAP), la moyenne et la médiane.

## 2.5 Interpolation sur une nouvelle position

Une fois l'hyperparamètre $\hat{\theta}$ estimé, la fonction de covariance $\hat{C}$ est connue, et ainsi la loi de $U$ également. Il nous reste alors à interpoler le déplacement $U(X^*)$ sur une nouvelle position $X^*$. Pour ce faire, nous allons calculer l'espérance conditionnelle. Comme $U$ est un processus gaussien, ceci revient à effectuer un krigeage simple[4], défini par:

$$ U(X^*) = (U_1 \quad \dots \quad U_N) \hat{\Sigma}^{-1} \begin{pmatrix} \hat{C}(||X^* - X_1||) \\ \vdots \\ \hat{C}(||X^* - X_N||) \end{pmatrix} $$

# 3 Applications

Pour chaque exemple, on discrétise les courbes en 300 points. Avant de présenter nos résultats, nous présentons les critères de qualité du recalage.

## 3.1 Critères sur la qualité du recalage

Un bon recalage doit avoir une faible erreur d'interpolation, et doit être lisse. Pour évaluer la qualité d'interpolation de notre méthode, on utilise 200 points pour effectuer le recalage, et les 100 restants pour l'évaluation. La qualité est alors estimée entre les points d'évaluation à l'aide de la racine carrée des erreurs en moyenne quadratique (RMSE). Comme on utilise des courbes pour effectuer notre recalage, on peut aussi utiliser ces dernières pour estimer la qualité d'interpolation. Nous avons choisi d'utiliser la distance de Fréchet (FD) définie par:

$$ d_F(F_1, F_2) = \inf_{\gamma_1, \gamma_2 \in \Gamma} \max \{d(F_1 \circ \gamma_1, F_2 \circ \gamma_2)\} $$

où $\gamma_1$ et $\gamma_2$ sont des reparamétrisations. Concernant la régularité du champ de déformation, nous utilisons la carte de la norme du laplacien. Un maximum de la norme du laplacien (MaxLap) faible signifie alors que le champ de déformation est lisse.

## 3.2 Application à des données synthétiques

Afin d'évaluer la performance de notre approche, nous nous intéressons à des données synthétiques présentant différents degrés de déformation. Un exemple de résultat obtenu est présenté en Figure 2. En ce basant sur la courbe de la norme du laplacien, on remarque que la déformation est lisse et locale. De plus, d'après le Tableau 2, qui résume l'évaluation de chaque méthode sur cet exemple, le champ de déformation admet de faibles erreurs d'interpolation.

<table><caption>Tableau 2: Evaluation quantitative des différentes méthodes d'estimation des paramètres sur un exemple de données synthétique présenté en Figure 2.</caption><thead><tr><th>Méthode</th><th>RMSE</th><th>DF</th><th>MaxLap</th></tr></thead><tbody><tr><td>Nelder-Mead</td><td>0.0713</td><td>0.5813</td><td>0.2902</td></tr><tr><td>Gradient</td><td>0.0699</td><td>0.5541</td><td>0.2889</td></tr><tr><td>Newton</td><td><strong>0.0698</strong></td><td><strong>0.5477</strong></td><td><strong>0.2878</strong></td></tr><tr><td>MAP</td><td>0.0718</td><td>0.5909</td><td>0.2982</td></tr><tr><td>Moyenne</td><td>0.0721</td><td>0.5947</td><td>0.3003</td></tr><tr><td>Mediane</td><td>0.0718</td><td>0.5918</td><td>0.2990</td></tr></tbody></table>

## 3.3 Application sur des données réelles

Contrairement aux données synthétiques, plusieurs courbes peuvent être en correspondance pour le même recalage d'images IRM/échographie. La Figure 3 montre un exemple de ce type de données, dont les résultats obtenus sont résumés dans le Tableau 3. Sur cet exemple, les méthodes d'optimisation de Nelder-Mead et de Newton ne donnent pas de bons résultats. Pour la descente du gradient et l'inférence bayésienne, le recalage est lisse et donne de faibles erreurs d'interpolation.

Afin d'étudier la stabilité de notre méthode, nous l'avons appliqué sur 7 données réelles. Les résultats obtenus sont résumés sur la Figure 4. En moyenne, l'erreur d'interpolation est faible pour tous les estimateurs, avec un champ de déformation relativement lisse. Les estimateurs bayésiens sont plus performants car ils fournissent un champ de déformation plus lisse, tout en gardant une petite erreur d'interpolation.

<table><caption>Tableau 3: Évaluation quantitative des différentes méthodes d'estimation des paramètres sur un exemple de données réelle présenté en Figure 3.</caption><thead><tr><th>Méthode</th><th>RMSE</th><th>DF</th><th>MaxLap</th></tr></thead><tbody><tr><td>Nelder Mead</td><td>0.1272</td><td>0.1796</td><td>0.7550</td></tr><tr><td>Gradient</td><td>0.1353</td><td><strong>0.1132</strong></td><td>0.4091</td></tr><tr><td>Newton</td><td><strong>0.1268</strong></td><td>0.1755</td><td>0.7058</td></tr><tr><td>MAP</td><td>0.1383</td><td>0.1200</td><td><strong>0.3667</strong></td></tr><tr><td>Moyenne</td><td>0.1380</td><td>0.1190</td><td>0.3680</td></tr><tr><td>Mediane</td><td>0.1381</td><td>0.1201</td><td>0.3673</td></tr></tbody></table>

# 4 Conclusion

Nous avons construit un outil de recalage d'images, basé sur les champs gaussiens. Cette méthode est efficace car le champ estimé est lisse et admet de faibles erreurs d'interpolation.

Afin d'améliorer l'estimation des paramètres, et donc la qualité du recalage, plusieurs approches sont envisagées
<figure><img src="image_53.png" /><figcaption>Figure 2: Exemple de champ de déformation estimé sur des données synthétiques: (a) courbes sources, (b) courbes cible, (c) courbes sources (en noir) et cible (en bleu) superposées, (d) le champ de déformation connu (rouge) et estimé (bleu), (e) la grille uniforme déformée par le champ estimé, et (f) la carte de la norme du laplacien. De haut en bas, les résultats sont obtenus après utilisation de la méthode d'optimisation suivante: Nelder-Mead, descente du gradient, Newton, MapIA 2018.</figcaption></figure>
<figure><img src="image_54.png" /><figcaption>Figure 3: Exemple de champ de déformation estimé sur un recalage IRM/échographie: (a) courbes sources, (b) courbes cible, (c) courbes sources (en noir) et cible (en bleu) superposées, (d) le champ de déformation connu (rouge) et estimé (bleu), (e) (a) et (c) en 2015, (f) la carte de la norme du laplacien. De haut en bas, les résultats sont obtenus après utilisation de la méthode d'optimisation suivante: Nelder-Mead, descente du gradient, Newton, Map.</figcaption></figure>
<figure><img src="image_55.png" /><figcaption>Figure 4: Évaluation quantitative des différentes méthodes d'estimation des paramètres sur 7 données réelles: (1) Nelder-Mead, (2) descente du gradient, (3) Newton, (4) MAP, (5) moyenne, et (6) médiane. Pour chaque méthode, nous présentons un boxplot de (a) la RMSE, (b) la distance de Fréchet, et (c) le maximum de la norme du laplacien.</figcaption></figure>

et feront l'objet de futurs travaux. Tout d'abord, pour les méthodes de la descente du gradient et de Newton, une approximation des dérivées partielles semble nécessaire pour éviter les erreurs numériques. De plus, un pas adaptatif pourrait améliorer la convergence de ces algorithmes. Dans un second temps, on pourrait utiliser des lois a priori plus informatives sur nos paramètres, ainsi que des lois de propositions plus restreintes pour améliorer la convergence des chaines MCMC.

Références

[1] R. J. Adler and J. E. Taylor. *Random Fields and Geometry*. Springer Monographs in Mathematics, 2007.

[2] O. Arandjelović, D.-S. Pham, and S. Venkatesh. Efficient and accurate set-based registration of time-separated aerial images. *Pattern Recognition*, 48(11):3466-3476, 2015.

[3] L. P. Chamié, R. Blasbalg, R. M. A. Pereira, G. Warmbrand, and P. C. Serafini. Findings of pelvic endometriosis at transvaginal us, mr imaging, and laparoscopy. *Radiographics*, 31(4):E77-E100, 2011.

[4] N. Cressie. *Statistics for Spatial Data, Revised Edition*. Wiley, 1993.

[5] T. Gneiting, W. Kleiber, and M. Schlather. Matérn cross-covariance functions for multivariate random fields. *Journal of the American Statistical Association*, 105:1167–1177, 2010.

[6] W. K. Hastings. Monte carlo sampling methods using markov chains and their applications. *Biometrika*, 57(1):97–109, 1970.

[7] S. Kurtek, A. Srivastava, E. Klassen, and Z. Ding. Statistical modeling of curves using shapes and related features. *Journal of the American Statistical Association*, 107(499):1152–1165, 2012.

[8] W. Mio, A. Srivastava, and S. Joshi. On shape of plane elastic curves. *International Journal of Computer Vision*, 73(3):307–324, 2007.

[9] J. Nelder and R. Mead. A simplex method for function minimization. *The Computer Journal*, 7, issue. 4:308–313, 1965.

[10] K. Rohr. *Landmark-based image analysis: Using geometric and intensity models*. Kluwer Academic Publishing, 2001.

[11] J. E. Roos, D. Weishaupt, S. Wildermuth, J. K. Willmann, B. Marincek, and P. R. Hilfiker. Experience of 4 years with open mr defecography: pictorial review of anorectal anatomy and disease. *Radiographics*, 22(4):817–832, 2002.

[12] A. Sotiras, C. Davatazikos, and N. Paragios. Deformable medical image registration : A survey. *INRIA Report*, september 2012.

[13] A. Srivastava, E. Klassen, S. Joshi, and I. Jermyn. Shape analysis of elastic curves in Euclidean spaces. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 33:1415–1428, 2011.

[14] M. L. Stein. *Interpolation of Spatial Data*. Springer Series in Statistics, 1999.

[15] Z. Tu, W. Xie, J. Cao, C. Van Gemeren, R. Poppe, and R. C. Veltkamp. Variational method for joint optical flow estimation and edge-aware image restoration. *Pattern Recognition*, 65:11–25, 2017.
<figure><img src="image_56.png" /></figure>
# oogo : Ontologie des Outils utiles à la Gestion d'Ontologies

Sylvie Despres

Université Paris 13, Sorbonne Paris Cité, LIMICS, (U1142), INSERM, Sorbonne Universités, UPMC Université Paris6,
74 rue Marcel Cachin F-93017 Bobigny cedex, France

sylvie.despres@univ-paris13.fr

## Résumé

Cet article présente, oogo, une ontologie ayant pour objectif la description des outils utiles à la gestion d'ontologies. A l'origine, ce travail répondait à une demande qui était de présenter à des chercheurs et/ou des industriels des outils utilisables pour élaborer une ontologie de domaine et si nécessaire leur permettre de les sélectionner en fonction de leurs besoins. Une ontologie nous a semblé constituer la forme la plus adaptée pour délivrer cette information. Le modèle conceptuel la structurant est fondé sur le cycle classique de construction d'ontologies commun à toutes méthodologies. Les activités afférentes à la construction d'ontologies servent de guide à la présentation des fonctionnalités les plus utiles de ces outils. Les scénarios d'usage sont construits à partir des besoins des acteurs intervenant autour d'une ontologie. Un état de l'art relatif à chaque catégorie d'outils sous-tend la construction du modèle conceptuel de oogo.

## Mots Clef

oogo, ontologie, ingénierie des ontologies, outils pour l'ingénierie ontologique.

## Abstract

This paper presents oogo an ontology for describing tools that are used for the management of ontologies. Originally, this work responded to a request that was to present to researchers and/or manufacturers some tools used to develop a domain ontology and if necessary allow them to select among them the ones that were best fitted to their needs. An ontology seemed the most suitable form to deliver this information. The conceptual model structuring oogo is based on the classical cycle of the ontology design that is shared by all of the methodologies. Ontology building activities serve as a guide for presenting the most useful features of these tools. The usage scenarios are built from the needs of actors intervening around an ontology. A state of the art relating to each category of tools underlies the construction of the oogo conceptual model.

## Keywords

oogo, ontology, ontology engineering, tools for ontology engineering.

## 1 Introduction

Dans cet article, nous décrivons, oogo, une ontologie ayant pour objectif la description des outils utiles à la gestion d'ontologies. A l'origine, ce travail répondait à une demande des organisateurs de la journée PDIA2017 qui était de présenter à des chercheurs et/ou des industriels des outils utilisables pour élaborer une ontologie de domaine et si nécessaire leur permettre de les sélectionner en fonction de leurs besoins.

La première question qui s'est posée pour répondre à cette requête a été de trouver la forme la plus pertinente pour renseigner ces acteurs. Il existe en effet de nombreux articles décrivant les différents outils et de nombreuses comparaisons les concernant. Ces dernières sont difficiles à exploiter car elles sont statiques, dédiées à des catégories d'outils particulières et les critères de comparaison utilisés peuvent varier d'un article à l'autre. Dans ce contexte, l'utilisation d'une ontologie nous a semblé la forme la mieux adaptée pour donner accès à l'ensemble des caractéristiques des outils actuellement disponibles. Elle permet entre autres de répondre aux questions les plus fréquemment posées lors de la sélection des outils intervenant dans la gestion d'une telle ressource. Elle est destinée à être publiée pour être réutilisée et enrichie par la communauté d'ingénierie des ontologies. Les utilisateurs concernés par oogo sont des ingénieurs de la connaissance ou des chargés de mission en « information technology » en charge de la construction d'ontologies et s'interrogeant sur les fonctionnalités des outils existants.

Le modèle conceptuel de oogo est fondé sur les activités intervenant dans le cycle classique de construction d'ontologies (scénario 1 de la méthodologie Neon) commun à toutes méthodologies de construction [37]. Les activités afférentes à la construction d'ontologies servent de guide à la présentation des fonctionnalités les plus utilisées de ces outils [38]. Le périmètre de l'ontologie est établi en adoptant la méthodologie de [41]. Les scénarios d'usage identifiés sont issus de cas réels rencontrés lors de la construction d'ontologies. A partir de ces scénarios, une liste non exhaustive de questions de compétence, auxquelles oogo doit être en mesure de répondre, a été élaborée à partir des questions posées par les acteurs devant construire une ontologie. Un état de l'art relatif à chaque outil aide à la construction du modèle conceptuel de oogo.

Dans la suite de l'article, la section 2 décrit le modèle adopté pour le concept Outil à partir duquel les modèles des outils présentés dans la section 3 sont décrits. Puis nous concluons dans la section 4 sur l'intérêt et l'usage d'une telle ontologie.
## 2 Modèle adopté pour le concept Outil

Nous envisageons l'outil comme un moyen permettant d'obtenir un résultat correspondant à la mise en œuvre d'un service. Nous proposons un modèle pour le concept d'outil dédié à la construction de ressources du web sémantique que nous spécialiserons en fonction du type d'outil étudié. En utilisant plusieurs vocabulaires standards, un outil est identifié par une URI correspondant à sa homePage, une URI de documentation et une URI de téléchargement. Il peut être caractérisé par des mots-clés. Il a été conçu par un auteur ou une équipe d'auteurs et développé par une organisation. Il est exécutable sous un SE. Il est identifié par un type de licence. Il est mis à disposition selon différentes modalités. Il fournit un type de service. Il est interopérable avec d'autres outils. Il dispose d'un format de stockage pour les fichiers contenant les ressources. Il permet l'import et l'export de ressources. Il est capable de gérer les sauvegardes avec ou sans gestion de version.

<figure><img src="image_57.png" /><figcaption>Figure 1 – Modèle du concept Outil</figcaption></figure>

Plusieurs vocabulaires sont réutilisés pour la construction du modèle concept Outil : dcterms, doap, dvia, educore, foaf, org.

<figure><img src="image_58.png" /><figcaption>Figure 2 – Aperçu des vocabulaires réutilisés.</figcaption></figure>

## 3 Démarche de construction de l'ontologie oogo

Nous nous intéressons aux outils dédiés à la construction d'ontologie définie comme « une spécification formelle explicite d'une conceptualisation partagée » [36]. Le langage de représentation considéré pour la formalisation de ces ontologies est OWL/OWL2 standard du W3C.

Le cycle classique de développement d'une ontologie est constitué des étapes de spécification, planification, conceptualisation, formalisation, implémentation [38]. Au cours de ce cycle, les activités mises en œuvre [39] comportent les activités de gestion, orientées développement (pré-développement, développement, post-développement) et de support à la construction. Dans oogo, nous décrivons une partie des outils supportant les activités de support et de développement. Le cadre méthodologique dans lequel nous nous situons est celui du projet NeON (http://www.neon-project.org/). Nous adoptons le cycle classique de construction d'une ontologie (spécification, planification, conceptualisation, formalisation, implémentation) correspondant au scénario 1 de la méthodologie Neon.

La spécification des besoins auxquels doit répondre l'ontologie a été décrite dans l'introduction. La sélection des outils présentés reposent sur des critères qui sont relatifs à la disponibilité pour une installation, leur maintenance, leur actualité et leur formalisation en OWL. Elle est non exhaustive et pourra être étendue au fil de l'utilisation de l'ontologie. Une partie a été collectée via le site du w3c et de AI3 ( ) et les articles synthétisant les différents outils existants. Ces outils ont servi à l'élaboration des modèles leur correspondant et sont décrits dans oogo.

Nous avons identifié, pour chacun d'entre eux, les scénarios d'usage issus de l'expérience acquise au cours des différents projets de recherche menés au LIMICS et les questions de compétences qui leur sont associées, c'est-à-dire les questions auxquelles notre ontologie doit être en mesure de répondre. La construction des modèles de connaissances qui leur sont associés, est décrite dans la suite de ce paragraphe.

### 3.1 Activités de support

Les activités de support que nous considérons sont la modélisation des connaissances, la réutilisation, l'évaluation et la validation. Les outils pouvant supporter ces activités sont les outils de recherche d'ontologies (moteurs de recherche et bibliothèques d'ontologies) et les outils de validation.

#### 3.1.1 Outils servant à la modélisation

Des outils de modélisation graphique semi-formelle peuvent être utilisés dans la phase de conceptualisation. Ils permettent de construire le modèle conceptuel du domaine qui sera ensuite formalisé avec l'éditeur d'ontologie. Leur utilisation intervient au cours de la phase d'acquisition de connaissances qui est réalisée de manière incrémentale.
### 3.1.1.1 Les scénarios

Scénario 1 : L'utilisateur cherche à cerner le périmètre de l'ontologie à construire. Il doit choisir une représentation sous forme de carte cognitive.

Scénario 2 : L'utilisateur cherche à représenter graphiquement le modèle du domaine en partant d'un concept central. oogo doit décrire les outils de modélisation avec leurs propriétés.

### 3.1.1.2 Les questions de compétence

Question 1 : J'ai identifié un concept central et je cherche à décrire les entités connexes en indiquant les relations qui les lient. Quel outil me permet de le faire ?

Question 2 : Comment déterminer la granularité de la représentation ?

Question 3 : Est-il possible de traduire automatiquement les cartes obtenues au format OWL ?

### 3.1.1.3 Les outils de modélisation sélectionnés

Nous avons sélectionné les outils Yed Graph Editor, XMind et CmapsTools. Ces trois outils disposent de versions exploitables sousWindows, OsX et Linux. Nous ne considérons pas dans cet article les métamodèles de représentation de OWL dans le formalisme UML et le langage GOWL de modélisation graphique, polymorphique et typé pour la construction d'ontologie [14].

Yed Graph Editor est un éditeur de graphes de bas niveau, open source et multiplateforme, personnalisable par programme. Il est souple dans les options de présentation disponibles et possède plusieurs fonctionnalités de disposition automatique des éléments du graphe. Il permet d'exporter les graphes au format graphml, SVG, png, emf, eps, etc.

XMind est un outil de carte heuristique qui permet également la construction de carte conceptuelle. Il permet de créer, gérer et partager des cartes conceptuelles et de les exporter au format txt, html, image, SVG. XMind propose une version open source et une version payante. Dans la seconde version, il est possible d'exporter au format csv. Cette fonctionnalité peut ensuite être exploitée par d'autres outils de création semi-automatisée de l'ontologie.

CmapTools est un outil qui permet de créer et partager facilement des cartes conceptuelles. Il est utilisable en ligne via un simple navigateur ou téléchargeable sous la forme d'un exécutable. Il dispose d'options de mise en page automatique et permet d'exporter au format image, PDF, etc. Il permet de fusionner des nœuds identiques, de créer des nœuds imbriqués de valider des liens, de réparer automatiquement les liens rompus et d'annoter les nœuds. Il permet également la comparaison des cartes qui est une fonctionnalité utile pour la construction collaborative.

### 3.1.1.4 Le modèle pour les outils de modélisation

Le modèle du concept Outil de modélisation prend en compte les fonctionnalités qui leur correspondent. Nous avons en particulier retenu le mode de mise en forme, les formats d'export, leur licence, les options de partage, le mode d'exploitation (en ligne ou téléchargeable). Les notions de cartes heuristique et conceptuelle sont décrites.

## 3.1.2 Outils de recherche

### 3.1.2.1 Les scénarios

Scénario 1 : L'utilisateur cherche à réutiliser des ressources ontologiques pour construire sa propre ressource. Il s'interroge sur les outils lui permettant de réaliser cette recherche et le type de recherche qu'il peut effectuer. oogo doit représenter les outils avec les types de recherche associés.

Scénario 2 : L'utilisateur s'interroge sur le type de recherche utilisé par l'outil pour retrouver une ressource. oogo doit décrire les différentes modalités de recherche associées aux outils.

Scénario 3 : L'utilisateur a réalisé une recherche qui lui renvoie une liste de ressources, il cherche une explication du classement des ressources retournées. oogo doit préciser les métriques utilisée pour le classement (ranking) des ressources.

### 3.1.2.2 Les questions de compétence

Question 1 : Quels outils de recherche existent pour m'aider à trouver une ontologie de domaine ? (scénario 1)

Question 2 : Existe-t-il des vocabulaires dont je pourrais réutiliser les termes pour désigner les concepts ou les relations de mon ontologie ? (scénario 1)

Question 4 : Quelles sont les modalités de recherche mises en œuvre pour trouver une ressource ? (scénario 2)

Question 5 : Comment s'explique la classification des ressources proposées par l'outil de recherche ? (scénario 3)

### 3.1.2.3 Les outils de recherche sélectionnés

Parmi les outils de recherche permettant de trouver des ressources ontologiques répondant à des besoins de réutilisation figurent les moteurs de recherche sémantique, les portails et les bibliothèques d'ontologies.

- Les moteurs de recherche Swoogle [11], Watson [7] et Vocab.cc [32] sont dédiés à la recherche d'éléments d'ontologies dont les vocabulaires constituent un sous-ensemble. L'expression de la recherche se fait en langue naturelle avec des mots clés et les résultats produits sont classés. Les modalités de recherche sont les suivantes :
  - par URI ;
  - par mots-clés correspondant à une classe, une relation, un individu, et au périmètre de l'ontologie (Label, Commentaire, etc.) ;
  - par requêtes sur des triplets ((terme générique, relation, terme) (terme générique, relation, ?), (terme générique relation, ?)) [28].

- Le portail Linked Open Vocabularies (LOV) (une version indépendante est hébergée à l'OKFN), un des modules de Datalift [42], qui est destiné à cataloguer, trouver et choisir des ontologies. Chaque vocabulaire est maintenu et publié de manière indépendante tout en entretenant des liens de dépendance vis-à-vis des autres vocabulaires.

- Les bibliothèques d'ontologies (BioPortal, AgroPortal, OBOFoundry, ODP) dont la finalité est de permettre et faciliter l'interopérabilité, fournir des ontologies reconnues et testées. Elles sont caractérisées par leur domaine, leur contenu et leurs fonctionnalités.

- L'outil OntoFox prend en charge la réutilisation des ontologies. Il permet aux utilisateurs de saisir des termes, d'extraire des propriétés sélectionnées, des
annotations et certaines classes de termes connexes à
partir d'ontologies sources et de sauvegarder les
résultats à l'aide de la sérialisation RDF / XML du
langage OWL. Ontofox dispose également d'un
algorithme d'extraction de termes fondé sur SPARQL
qui extrait des termes liés à un ensemble donné de
termes de signature. En outre, Ontofox fournit une
option pour extraire la hiérarchie enracinée à un terme
d'ontologie spécifié.

3.1.2.4 Le modèle proposé pour les outils de recherche

Le modèle pour les moteurs et le portail LOV a été
construit à partir du tableau comparatif établi par [43].
Les caractéristiques retenues comportent la méthode
d'accès à la ressource (automatique et/ou manuelle), le
type de la ressource (Semantic Web Document,
concepts, termes de vocabulaire, vocabulaires), la
métrique de ranking, le filtrage du domaine, l'accès au
service web, etc.).

Le modèle pour les bibliothèques a été établi à partir du
tableau comparatif proposé par [22]. Les
caractéristiques décrites sont le domaine, les
fonctionnalités de navigation et de recherche (sujet,
structure, langue), le type d'appariement supporté (entre
classe ou ontologie), le processus de soumission,
l'utilisation et l'accès aux ontologies, les formats de
fichiers en entrée et sortie, les outils associés.

3.1.3 Outils de validation

3.1.3.1 Les scénarios

Scénario 1 : L'utilisateur cherche à valider l'ontologie qu'il a construite et s'interroge sur les outils lui permettant de réaliser cette tâche. L'ontologie doit décrire les outils permettant les différents types de validation.

Scénario 2 : Quels sont les critères garantissant la validité d'une ontologie ? oogo doit préciser les critères utilisés pour la validation et les outils leur correspondant.

3.1.3.2 Question de compétences

Question 1 : Existe-il des outils pour valider les ontologies ? (scénario 1)

Question 2 : Quel outil me permet de vérifier la
structure de mon ontologie ? (scénario 1 et 2)

Question 2 : Quel outil me permet de vérifier le modèle de l'expertise représenté dans mon ontologie ? (scénario 2)

3.1.3.3 Les outils de validation sélectionnés

Nous avons utilisé l'analyse des outils de validation réalisée par [27] pour la sélection des outils de validation. La validation de la qualité d'une ontologie se définit selon deux axes principaux qui sont la validation de la structure et la validation de la sémantique. La validation de la structure correspond à une validation formelle de la logique du modèle. Elle peut être réalisée automatiquement, grâce au développement d'outils dédiés. La validation de la sémantique consiste à mesurer l'adéquation du modèle conceptuel avec la réalité qu'il modélise. Cette étape nécessite une collaboration entre les ontologues et les spécialistes du domaine modélisé dans l'ontologie.

Les outils de validation de structure

Les raisonneurs permettent de vérifier la consistance et
la cohérence d'un modèle (cf. Les outils de
raisonnement, infra).

OntoCheck [29] constitue un module d'extension à l'éditeur d'ontologies Protégé et vise à contrôler le respect des conventions de nommage, ainsi que l'exhaustivité des méta-données. OntoCheck vérifie les cardinalités, la complétude des méta-données, les labels, les conventions typographiques ainsi que les métriques de l'ontologie.

XD Analyzer a été développé dans le cadre du projet NeOn , pour faire un retour qua- litatif à l'utilisateur en suivant la méthodologie XD. Cette dernière fournit une liste de bonnes pratiques (concernant entre autres, les labels, les commentaires, les concepts non utilisés) à respecter pour la construction d'ontologies. Le module d'extension RaDON [1?] a été ajouté à Neon Toolkit afin de faciliter les tâches de vérification de la consistance. Il comporte deux plugins permettant de travailler sur une ontologie ou un réseau d'ontologies.

OntOLogy Pitfall Scanner! (OOPS!) [26] est un outil indépendant de tout éditeur d'ontologies. Il s'utilise uniquement en ligne. Le but de OOPS ! est l'identification des anomalies ou des mauvaises pratiques dans une ontologie. L'application prend en entrée l'URI d'une ontologie ou le code source en RDF. L'ontologie est chargée *via* l'API Jena avant d'être analysée pour en extraire les erreurs potentielles. Le résultat est une page répertoriant les erreurs selon le piège (pitfall) identifié, avec une proposition de résolution de l'erreur. Les pitfalls peuvent concerner des éléments individuels, plusieurs éléments ou toute l'ontologie.

Les outils de validation sémantique

Les outils permettant de valider la sémantique d'une
ontologie nécessitent le recours à des experts du
domaine modélisé par l'ontologie. Des outils supportant
le développement de construction collaborative
d'ontologies contribue à la validation sémantique.

Le serveur Ontolinguua propose un environnement
collaboratif pour parcourir, créer, éditer, modifier ou
utiliser les ontologies (Farquhar et al., 1997),
WebProtégé a été développé en reprenant l'architecture
de Protégé. Il permet également le développement
collaboratif d'ontologies et est accessible *via* n'importe
quel navigateur web [40].

3.1.3.4 Le modèle pour les outils de validation

Le modèle des outils de validation décrit les
fonctionnalités concernant la validation collaborative
d'ontologies et précise les types de validation possible.

3.2 Activités de développement

Parmi les activités intervenant dans la phase de
développement, nous considérons la conceptualisation,
la formalisation, la modularisation, l'alignement. Les
outils supportant ces activités sont les outils d'édition,
les raisonneurs, les outils d'alignement et les outils de
visualisation.

3.2.1 Outils d'édition

Un éditeur d'ontologie est un outil permettant
d'inspecter, de parcourir, de codifier, de modifier les
ontologies et de soutenir de cette manière le
développement de l'ontologie et la tâche de
maintenance.

3.2.1.1 Les scénarios

Scénario 1 : L'ontologue est débutant et cherche un
éditeur pour construire une ontologie. Il n'a pas
forcément une idée précise de fonctionnalité de l'outil.
oogo doit décrire les différentes fonctionnalités de la
phase de développement de l'ontologie.

Scénario 2 : L'ontologue a une idée précise de la nature de l'ontologie qu'il souhaite construire et des tâches qu'elle permettra de réaliser (annotation, raisonnement).

3.2.1.2 Les questions de compétence

Question1 : Quels sont les éditeurs d'ontologie disponibles ? (scénario 1)

Question 2 : Quel est le meilleur éditeur d'ontologie pour un débutant ? (scénario 1)

Question 3 : Quelles sont les activités supportées par l'éditeur d'ontologie ? (scénario 2)

3.2.1.3 Les outils d'édition sélectionnés

Nous avons utilisé le wiki du W3C pour répertorier les
éditeurs les plus utilisés actuellement pour construire
des ressources ontologiques au sens où nous les avons
définis dans cet article. Par conséquent nous n'avons
pas retenu les éditeurs de vocabulaire. Parmi la liste des
éditeurs inventoriés nous avons retenu Protégé, NeOn
Toolkit, SWOOP et TopBraid Composer.

Nous avons également exploité les comparaisons des
différents éditeurs pour identifier les propriétés des
outils d'édition et construire un modèle de ces outils
([1], [2], [3], [16], [25], [30], [31].

3.2.1.4 Le modèle pour les outils d'édition

Nous avons retenu les caractéristiques servant à ces
comparaisons pour construire le modèle des outils
d'édition. Elles concernent l'architecture de l'outil et sa
capacité d'évolution, l'operérabilité, le paradigme de
représentation des connaissances et le support
méthodologique, les services d'inférences, les services
de visualisation, la gestion des versions et l'utilisabilité.
Certaines de ces caractéristiques sont déjà décrites dans
le modèle du concept Outil (cf. Figure 1).

L'étude de l'utilisabilité des éditeurs réalisée par [12]
pour des ontologues débutants met en évidence des
propriétés relatives à la facilité de prise en main des
outils. Certaines propriétés nous semble quantifiables
comme accessibilité du langage utilisé à une
communauté d'utilisateurs non spécialistes, la
visualisation hiérarchique des classes, la navigation
d'une classe vers ses instances, le filtrage des classes à
partir de critères fixés par l'utilisateur

3.2.2 Outils de raisonnement

Une ontologie exprimée en OWL peut être considérée comme un ensemble de formules FOL (First Order logic), appelées axiomes, et par conséquent comme une théorie logique. Le vocabulaire exprimé en OWL est bien défini et sans ambiguïté. Cependant, il y a souvent un décalage entre la représentation visée et la représentation réelle de la connaissance décrite dans l'ontologie. Alors que la connaissance du domaine d'intérêt est généralement bien maîtrisée ou tout au moins comprise, il n'est pas trivial de prévoir et de comprendre les conséquences logiques d'un ajout, d'un

retrait ou d'une modification d'axiome, notamment
quand la terminologie est fortement interconnectée.
Ainsi, un ontologue a besoin d'utiliser des systèmes de
déduction automatisés, communément appelés
raisonneurs, pour vérifier certaines formes de déduction
à partir d'axiomes préétablis et de rendre explicites ceux
qui sont déclarés implicitement. Les raisonneurs sont
donc, à l'heure actuelle, des éléments clés pour
travailler avec des ontologies [4].

3.2.2.1 Les scénarios

Scénario 1 : L'utilisateur cherche l'outil support du raisonneur (Neon, Protégé, Swoop, etc.). L'ontologie doit donc permettre de représenter les différents supports et de leur associer les raisonneurs existants.

Scénario 2 : L'utilisateur cherche à connaître les tâches supportées par un raisonneur. L'ontologie doit décrire les tâches de raisonnement et les entités sur lesquels ils portent.

Scénario 3 : L'utilisateur cherche les capacités d'explication et de gestion des erreurs du raisonneur.

Scénario 4 : L'utilisateur cherche le raisonneur adapté au contenu de l'ontologie à exploiter ? Dépend de la formalisation adoptée pour l'ontologie qui dépend elle-même des tâches à réaliser (annotation, raisonnement). Au différents profils sont associés des raisonneurs

3.2.2.2 Les questions de compétence

Question 1 : Sous quel système d'exploitation est-il exécutable ? Quel est le type de licence ? (scénario lié au modèle outil)

Question 2 : Avec quel éditeur le raisonneur est-il compatible ? Est-il standalone ?

Question 3 : Le raisonneur peut-il exploiter des règles et quel est le formalisme supporté ?

Question 4 : Le raisonneur prend t-il en charge le raisonnement sur les individus ?

Question 5 : Le raisonneur est-il adapté à la nature de l'ontologie que j'ai construite ?

Question 6 : Quels types de justification (explications sur les inconsistances) peut fournir le raisonneur ?

Question 7 : Quel type de profil OWL est pris en charge par le raisonneur ?

3.2.2.3 Les outils de raisonnement

Nous avons utilisé les comparaisons réalisées par [8], [1], [21] et [4] pour construire le modèle des outils de raisonnement.

[8] dressent une liste de caractéristiques guidant l'utilisateur dans le choix d'un raisonneur en fonction des besoins d'une application. Elle est envisagée selon deux dimensions : les caractéristiques du raisonnement et l'utilisabilité pratique. La première dimension regroupe : la procédure ou l'algorithme utilisé par le raisonneur pour le raisonnement en logique de description (algorithme Tableau, Hyper-Tableau et Consequence-Based), la robustesse et la complétude (vérifie si toutes les inférences possibles sont réalisées) qui peut aider à une accélération du temps de raisonnement, l'expressivité et la complétude (lien avec les profils OWL), la classification incrémentale (synchronisation du raisonneur), le support de l'utilisation de règles (par exemple, SWRL), la justification (explication pour un concept inconsistent, disjonction de concept, implication logique, etc.), le support des tâches de raisonnement sur la Abox
(raisonnement sur les individus, vérification de la
consistance de la Abox, etc.). La seconde a trait à la
disponibilité ( plugin, standalone), au type de licence et
d'autres caractéristiques comprenant le type de code, les
plateformes compatibles, l'interface Jena native, etc.

Après avoir décrit l'architecture des raisonneurs
raisonneurs Pellet, RACER, FaCT++ [39], Snorocket
SWRL-IQ, ELK, HermiT, CEL et TrOWL, [1] en
dresse une comparaison selon les caractéristiques
définies par [8].

[21] réalise une comparaison de 35 raisonneurs dont la plupart ont été développé entre 2010 et 2015. Elle est fondée sur des critères d'utilisabilité (services de raisonnement supporté, les niveaux d'expressivité et la complétude du raisonneur) et les algorithmes de raisonnement implémentés.

3.2.2.4 Le modèle pour les outils de raisonnement

Le modèle des outils de raisonnement a été établi à partir du tableau comparatif présenté par [4] qui est fondé sur l'article [21]. Les raisonneurs décrits sont actuellement FaCT++, Pellet, ELK, HermiT, Konclude [34], Euler/Eye et NoHR.

3.2.3 Outils de conversion de données en OWL

La finalité de ces outils est la conversion de données
contenues dans des feuilles de calcul en OWL.

3.2.3.1 Les scénarios

Scénario 1 : L'utilisateur dispose de documents existant sur la connaissance à formaliser, le plus souvent sous la forme de listes ou de feuilles de calcul. Il souhaite pouvoir les greffer facilement sur le squelette de son ontologie en utilisant les relations qu'il a prédéfinies.

Scénario 2 : L'utilisateur souhaite importer des éléments de hiérarchie à partir d'ontologies existantes avec cependant la possibilité de les amender ou de les compléter.

Scénario 3 : L'utilisateur souhaite mettre à la disposition d'intervenants extérieurs des parties de son travail en cours à des fins de vérification ou de validation.

Scénario 4 : L'utilisateur souhaite introduire dans l'ontologie d'importantes quantités de faits ou de caractéristiques sans avoir la charge de les éditer tous manuellement.

3.2.3.2 Les questions de compétence

Question 1 : L'outil permet-il l'import de données exprimées dans des tableaux (feuilles de calcul) ?

Question 2 : L’outil permet-il l’opération inverse (export vers des feuilles de calcul) d’extraits sélectionnés de son ontologie ?

Question 3 : Ces fonctionnalités sont-elles disponibles pour une utilisation en mode « ligne de commande » pour supporter un certain degré d'automatisation des tâches répétitives lors de l'enrichissement de son ontologie ?

3.2.3.3 Les outils de conversion de données

Nous avons sélectionné l'outil Cellfie un plugin
Protégé 5 intégrant MappingMaster [23] et l'outil FOE
[9]. Populous et WebPopulous offrent des
fonctionnalités similaires ainsi que l'option d'import
Excel disponible dans Topbraid Composer.

3.2.3.4 Le modèle pour les outils de conversion de données

Pour construire le modèle des outils de conversion de données, nous avons le type et d'export et les modalités

d'utilisation, le degré d'automatisation autorisé et les
constructions qu'il est possible de créer.

3.2.3 Outils d'alignement

Pour construire le modèle des outils d'alignement nous avons commencé à tester les outils répertoriés sur le site de AI3, la librairie des outils d'alignement hébergée par l'INRIA et le site du projet Ontobeep. Nous inventorions également les outils de visualisation d'alignement tels que [19]. Cette partie du travail est en cours et ne sera pas présenté dans l'article.

3.2.4 Outil de gestion d'évolution

Pour construire le modèle des outils d'évolution nous avons commencé à inventorier les outils existants [35]. Nous travaillons à partir des travaux récents de [18] qui réalisent une synthèse de ces outils du point de vue de la visualisation.

Les outils que nous analysons sont CODEX [13], REX [6], NeonToolkit [24].

3.2.5 Outils de visualisation

La visualisation d'ontologies est une tâche qui aide à la compréhension des modèles représentés. Elle est utile à l'ensemble des acteurs participant à sa construction. Or, il n'est pas simple de créer une visualisation des ontologies en raison de la complexité de ces ressources. Les entités à visualiser sont la hiérarchie des concepts, les relations entre les concepts, les attributs des concepts et les individus relevant des concepts représentés [17]. Nous avons identifié deux publications faisant références à des ontologies VO formalisant les connaissances utiles la visualisation d'ontologies [33] et [44] qui décrivent les primitives utilisées dans le domaine de la visualisation. Elles ne sont pas directement exploitables mais nous avons réutilisé certaines des classes modélisées.

3.2.5.1 Les scénarios

Scénario 1 : L'utilisateur souhaite visualiser la hiérarchie des concepts.

Scénario 2 : L'utilisateur souhaite se centrer sur un concept afin de visualiser globalement l'ensemble des liens qu'il entretient avec le réseau de concepts.

Scénario 3 : L'utilisateur souhaite visualiser les explications fournies par le raisonner et disposer d'une représentation graphique.

3.2.5.2 Les questions de compétence

Question 1 : Quel outil permet de visualiser l'ontologie ?

Question 2 : Quelles sont les entités visualisable de l'ontologie ?

Question 3 : Quelles sont les actions possibles pour visualiser l'ontologie ?

3.2.5.3 Les outils de visualisation

Les outils décrits dans la version actuelle de oogo sont
GraphViz, CropCircles, KC-Viz, Knoocks, LogDiffViz,
OntoGraph, OntologyVisualizer, Jambalaya,
OntoTGVizTab, VOWL, WebVOWL, Protupos.

3.2.5.4 Le modèle pour les outils de visualisation

Le modèle des outils de visualisation a été établi à partir
de la comparaison et l'évaluation des visualisations
d'ontologies présentées par [5] et des publications
relatives à certains outils [45], [20].
Dans le cadre de la construction du service web de visualisation centré utilisateur Protupos, [10] ont caractérisé les outils de visualisation actuellement utilisés :

- Graphviz est un plugin de Protégé qui s'exécute dans son propre onglet. Il sert principalement à la visualisation graphique d'ontologie grâce à l'utilisation d'un graphe de nœuds et d'arcs qu'il est possible d'étendre et de réduire dynamiquement via des actions sur des boutons. Sur le principe, Graphviz est très utile pour parcourir la hiérarchie et la manipuler (expansion, respectivement réduction, des propriétés relatives à un nœud). Il permet également la visualisation de la hiérarchie des classes inférées.

- VOWL est un plugin de Protégé qui s'exécute dans son propre onglet et qui ne prend pas en compte les actions effectuées par ailleurs. Par exemple, il n'est pas possible de se centrer sur un concept et de naviguer autour de ce dernier dans l'onglet VOWL. Sur le principe, VOWL est une spécification de notations graphiques pour les ontologies écrites en OWL http://purl.org/vowl/spec/. L'outil est clairement tourné vers l'ontologue.

- WebOWL (http://visualdataweb.de/webvowl/) est un service web implémentant VOWL indépendamment de Protégé. Les actions peuvent être effectuées grâce aux boutons et aux menus. Un inconvénient majeur de WebOWL est que comme pour tout service web, l'ontologie doit être téléchargée.

- CropCircles est un outil intégré à SWOOP qui permet de visualiser la hiérarchie des concepts. Un concept est représenté par un cercle, les fils de ce concept sont représentés à l'intérieur de ce cercle et la hiérarchie est visualisé selon un représentation en coupe. Il est possible de zoomer sur une couche particulière de la hiérarchie en cliquant dans le cercle et de naviguer dans la hiérarchie en cliquant à l'extérieur du cercle. La vision en coupe par niveau hiérarchique permet notamment de bien appréhender la densité d'un sous arbre par rapport à un autre.

Le développement de Protupos a permis de définir des fonctionnalités que nous avons utilisées pour construire le modèle des outils de visualisation :

- visualisation interactive de la hiérarchie : utilisation d'une représentation circulaire "zoomable" par actions de l'utilisateur ;

- de la hiérarchie par coupe de niveau ;

- visualisation de chaîne de propriétés centrée sur un nœud avec la possibilité de développer dynamiquement la construction de la chaîne ;

- visualisation sous la forme de réseaux d'un type de propriété ;

- visualisation centrée sur un concept en utilisant une fonction « élastique (permettant de modifier le focus) » ;

- nuage de tags associés à un concept.

## 4. Présentation et évaluation de oogo

oogo a été édité avec le logiciel Protégé (version 5.2.0). L'ontologie et la description de ses ressources et propriétés seront publiées selon les principes des données liées sur le web et le schéma sera identifié par l'URI HTTP https://www-limics.smbh.univ-

paris13.fr/oogo#.
Plusieurs vocabulaires sont utilisés pour la construction du modèle outil : dcterms, doap, dvia, foaf, org. Dans cette version de oogo, nous ne pouvons pas réutiliser dvia:url car le type anyUri n'est pas directement supporté par Protégé 5.

### 4.1 Métrique de oogo

<table><caption>Figure 3 – Métrique de l'ontologie oogo</caption><thead><tr><th colspan="2">Metrics</th></tr></thead><tbody><tr><td>Axiom</td><td>756</td></tr><tr><td>Logical axiom count</td><td>368</td></tr><tr><td>Declaration axioms count</td><td>208</td></tr><tr><td>Class count</td><td>155</td></tr><tr><td>Object property count</td><td>17</td></tr><tr><td>Data property count</td><td>12</td></tr><tr><td>Individual count</td><td>23</td></tr><tr><td>Annotation Property count</td><td>6</td></tr><tr><td>DL expressivity</td><td>ALCHOD</td></tr></tbody></table>

La métrique de l'ontologie est présentée Figure 3. Elle comporte actuellement 155 classes, 17 object property et 12 data property. Elle est en cours d'évolution.

<figure><img src="image_59.png" /><figcaption>Figure 4 – Vue globale de oogo (A) et Définition d'un outil (B)</figcaption></figure>

### 4.2 Aperçu des classes de oogo

Nous présentons une description du concept Outil dans oogo. Dans la classe ClasseOutil l'ensemble des outils étudiés sont décrits comme des sous-classes. Par exemple, la classe Protégé comporte les sous-classes Proétég3-x, Protégé4-x, Protégé5-x. Des individus relèvent de ces différentes sous-classes. Elle est également définie comme disposant d'un service d'édition. Les classes définies, comme OutilEdition de la figure 4(A), permettent d'utiliser le raisonneur pour caractériser les outils selon les services qui leur correspondent.

### 4.3 Requêtes DL Query

Nous montrons par le biais de quelques exemples de requêtes DL Query que les questions de compétence trouvent une réponse.

<figure><img src="image_60.png" /></figure>
<figure><img src="image_61.png" /><figcaption>Figure 5 – Requêtes DL Query</figcaption></figure>

Conclusion

Cet article présente un travail en cours qui répondait à une demande qui nous a permis de prendre conscience de la nécessité de centraliser l'expérience de la communauté de manière synthétique afin de répondre simplement et rapidement à des questions pratiques concernant la disponibilité des différents outils utilisables dans le cadre de la construction d'ontologies. L'ontologie ébauchée dans cet article est par nature destinée à évoluer régulièrement une fois qu'elle aura été mise en ligne dans sa version initiale. Actuellement, la langue utilisée pour le développement de oogo est le français néanmoins l'ensemble des entités sont décrites avec des labels et altlabel en anglais. Nous avons le projet de rendre sa construction collaborative lorsqu'elle sera publiée afin de s'assurer qu'elle ne devienne pas obsolète. De cette façon, les retours d'expérience pourront être valorisés et bénéficier à l'ensemble de la communauté.

Bibliographie

[1] Abburu, S. (2012). A Survey on Ontology Reasoners and Comparison. International Journal of Computer Applications, 57(17):33–39.

[2] Abburu, S., Babu, G. S. (2013). Survey on Ontology Construction Tools. International Journal of Scientific & Engineering Research, Volume 4, Issue 6, pp.1748-1752.

[3] Alatrish E. S. (2013). Comparison Some of Ontology Editors, in Management Information Systems, vol 8, n°2, pp. 018-024, 2013.

[4] Alaya N. (2016). Managing The Empirical Hardness of The Ontology Reasoning using The Predictive Modelling. Thèse de l'université de Tunis El Manar et de l'université Paris8.

[5] Balzer L., Do M.T., Maseluk D. (2015). Comparison and Evaluations of Ontology Visualizations. Rapport de recherche, H.5.2, I.2.4.

[6] Christen V., Gross V., Hartung M. Region Evolution eXplorer a tool for discovering evolution trends in ontology regions. Journal of Biomedical Semantics, 6:Article 26, 2015.

[7] D'Aquin M., Motta E. (2011). Watson, more than a Semantic Web search engine. Semantic Web 2(1): 55-63.

[8] Dentler K., Cornet R., & ten Teije A., & de Keizer N. (2011). Comparison of reasoners for large ontologies in the OWL 2 EL profile. Semant. web, 2(2):71–87.

[9] Despres S., Guezennec G. - Flat OWL Editor : un outil utilisant des feuilles de calcul pour découpler les

tâches des acteurs impliqués dans la gestion d'une ontologie. Toth2017, (à paraître).

[10] Despres S., Nobecourt J.- Quelles fonctionnalités pour un outil de visualisation d'ontologie ? Atelier VIF Visualisation d'informations, Interaction, et Fouille de données EGC 2018 (http://gt-vif.polytech.univ-nantes.fr/egc-vif2018/atelier_VIF_EGC2018.pdf

[11] Finin T., Ding L., Pa R., Joshi A., Kolari P. (2005). Java A., Peng Y. Swoogle: Searching for knowledge on the semantic web. In Anthony Cohn, editor, Proceedings of the 20th National Conference on Artificial Intelligence - Volume 4, AAAI'05, pages 1682–1683. AAAI Press.

[12] Garcia-Barriocanal E., Sicilia M. A. & Sanchez-Alonso S. (2006). Usability Evaluation of Ontology Editors. Knowledge Organization 32(1),1-9.

[13] Hartung M., Gross A., Rahm E. CODEX: Exploration of semantic changes between ontology versions. Bioinformatics, 26(6):895–896, 2012.

[14] Héon M., Nkambou R., Langheit C. (2016). Toward G-OWL: A graphical, polymorphic and typed syntax for building formal OWL2 ontologies. Proceedings of the 25th International Conference Companion on World Wide Web. International World Wide Web Conferences Steering Committee.

[15] Jain V., Prasad S.V.A.V. (2016). Evaluation and Validation of ontology using Protégé Tool. In International Journal of Research in Engineering & Technology (IMPACT: IJRET) ISSN (E): 2321-8843; ISSN (P): 2347-4599 Vol. 4, Issue 5, May 2016, 1-12.

[1?] Ji, Q., Haase, P., Qu, G., Hitzler, P., Stadtmoeller, S.: RaDON – repair and diagnosis in ontology networks. In: Aroyo, L., Traverso, P., Ciravegna, F., Cimiano, P., Heath, T., Hyvönen, E., Mizoguchi, R., Oren, E., Sabou, M., Simper, L.E. (eds.) ESWC 2009. LNCS, vol. 5554, pp. 863–867. Springer, Heidelberg (2009).

[16] Kapoor, B., Sharma, S.A. (2010). Comparative Study Ontology Building Tools for Semantic Web Applications. International journal of Web & Semantic Technology (IJWesT), 1(3).

[17] Katifori A., Halatsis C. Lepouras G., Vassilakis C., Giannopoulou E. (2007). Ontology Visualization Methods – A Survey. ACM Computing Surveys, Vol. 39, N°4, Article 10.

[18] Lambrix P., Dragisic Z., Ivanova V., Anslow C. Visualization for Ontology Evolution, VOILA 2016 Visualization and Interaction for Ontologies and Linked Data, 2016, pp.54-67.

[19] Lanzenberger M., Sampson J. (2011). Ontology Alignment Quality: A Framework and Tool for Validation. IJISMD 2(3): 1-23

[20] Lohmann S., Link V., Marbach E., Negru S. (2016). Visualizing ontologies with VOWL. 7(4),21. Already accepted papers for the EKAW 2014 special issue, extended version.

[21] Matentzoglu N., Leo J., Hudhra V., Sattler U., Parsia B.. (2015). A survey of current, stand-alone OWL reasoners. In Proceedings of the 4th International Workshop on OWL Reasoner Evaluation, pages 68–79.

[22] Naskar D., Dutta B. (2016) - Ontology Libraries: A Study from an Ontofier and an Ontologist Perspectives. 19th International Symposium on Electronic Theses and Dissertations, Lille.
[23] O'Connor M. J., Halaschek-Wiener C., Musen M. A. (2010). Mapping master: a flexible approach for mapping spreadsheets to OWL. In ISWC'10 Proceedings of the 9th international semantic web conference on The semantic web - Volume Part II, 194-208.

[24] Palma R., Zablith F., Haase P., Corcho O. Ontology evolution. In MC Suarez-Figueroa, A Gomez-Prez, E Motta, and A Gangemi, editors, Ontology Engineering in a Networked World, pages 235-255. 2012.

[25] Parveen, Kumar Sahni D.K., Khurana D., Nandal R. (2016). Ontology Development Tools and Languages: A Review. Vol. 5, Issue 6, June, 2016.

[26] Poveda-Villalo, M., Gomez-Perez, A., Suárez-Figueroa, M.C. (2014). OOPS! (OntOlogy Pitfall Scanner!): An On-line Tool for Ontology Evaluation. Int. J. Semantic Web Inf. Syst. 10(2): 7-34.

[27] Richard M. (2017). Apports de la modélisation ontologique pour le partage des connaissances en psychiatrie. Thèse de l'université Pierre et Marie Curie - Paris VI.

[28] Sabou M., D'Aquin M., Motta E. (2008). SCARLET: SemantiC RelAtion DiscoveRy by Harvesting OnLinE OnTologies. ESWC 2008: 854-858.

[29] Schober D., Tudose I., Svatek V., Boeker M. OntoCheck: verifying ontology naming conventions and metadata completeness in Protégé 4. In J Biomed Semantics. 2012; 3(Suppl 2): S4.

[30] Seongwook Y., Anchit A., Preetham C., Paavany J., Ashish M. and Shikha S. (2009). Survey about Ontology Development Tools for Ontology-based Knowledge Management, University of Southern California.

[31] Slimani, T. (2015). Ontology Development: A Comparing Study on Tools, Languages and Formalisms. In Indian Journal of Science and Technology, Vol 8(24), doi:10.17485/ijst/2015/v8i34/54249.

[32] Stadtmüller S., Harth A., Grobelnik M. (2013). Accessing information about linked data vocabularies with vocab.cc. In Juanzi Li, Guilin Qi, Dongyan Zhao, Wolfgang Nejdl, and Hai-Tao Zheng, editors, Semantic Web and Web Science, Springer Proceedings in Complexity, pages 391-396. Springer New York. doi:10.1007/978-1-4614-6880-6,34.

[33] Shu G., Avis N.J. (2008). Bringing semantic to vizualization services. Advances in Engineering Software 39. Pp.514-520.

[34] Steigmiller A., Liebig T., & Birte. G. (2014). Konclude: System description. Web Semantics: Science, Services and Agents on the World Wide Web, 27(1).

[35] Stojanovic L., Motik B. (2002) Ontology Evolution within Ontology Editors. In Conference on the Evaluation of Ontology-based Tools.

[36] Studer R., Benjamin V. R et FenselL. (1998). D. Knowledge Engineering: Principles and methods. Data & Knowledge Engineering 25, pp. 161-197.

[37] Suárez-Figueroa, M.C., Gomez-Perez, A., Fernadez-Lopez M. (2015). The NeOn Methodology framework: A scenario-based methodology for ontology development. Applied Ontology 10(2): 107-145.

[38] Suárez-Figueroa, M.C., Gomez-Perez, A., (2008). Towards a Glossary of Activities in the Ontology Engineering Field, LREC.

[39] Tsarkov D. & Horrocks I. (2006). Fact++ description logic reasoner: System description. In Proceedings of the Third International Joint Conference on Automated Reasoning, pages 292-297.

[40] Tudorache T., Nyulas C., Noy, N. F. & Musen, M. A. (2013). Webprotégé : A collaborative ontology editor and knowledge acquisition tool for the web. Semantic web, 4(1):89-99.
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3691821/.

[41] Uschold M., Gruninger M. (1996). Ontologies: Principles, methods and applications. The knowledge engineering review, vol. 11, no 2, p. 93-136.

[42] Vandenbussche P.Y., Vatant B. (2014). Linked Open Vocabularies. ERCIM news, 96:21-22.

[43] Vandenbussche P.Y., Atemezing G., Poveda-Villalon M., Vatant B. (2017). Linked Open Vocabularies (LOV): A gateway to reusable semantic vocabularies on the Web. Semantic Web 8(3): 447-452.

[44] Voigt M. & Polowinski J. (2011). Towards a Unifying Visualization Ontology. Technical Report – Technische Universität Dresden (3/2011).

[45] Kuhar S., Podgorelec, V. Ontology Visualization for Domain Experts: A New Solution, 2012 16th International Conference on Information Visualisation(IV), Montpellier, France, 2012, pp. 363-369. doi:10.1109/IV.2012.67V.
<figure><img src="image_62.png" /></figure>
# Categorization of B2B Service Offers: Lessons learnt from the Silex Use case

Molka Tounsi Dhouib¹²

Catherine Faron Zucker<fnref n="1" />

Andrea Tettamanzi<fnref n="1" />

## Résumé

Dans le domaine de la recherche d'information et du traitement automatique du langage, la tâche de classification de textes est devenue une tâche cruciale. Dans cet article, nous partageons notre expérience de la classification de textes dans un contexte industriel et présentons une évaluation comparative de différents algorithmes de classification binaire et multi-label appliqués à des textes décrivant des offres de services, issus de la plateforme B2B SILEX pour la recommandation de prestataires de services. Nous montrons que dans certains cas pratiques comme celui que nous considérons, une représentation des données sous la forme de "bags of words" donne de meilleurs résultats de classification qu'une représentation réputée plus prometteuse par "word embeddings".

## Mots Clef

Catégorisation de textes, Apprentissage automatique, Sac de mots, Plongement lexical

## Abstract

In the domain of Information Retrieval and Natural Language Processing, text classification has become a crucial task. In this article, we share our experience of text categorization in an industrial context and we present a comparative evaluation of binary and multi-label classification algorithms applied to texts describing service offers, in the SILEX B2B platform. We show that for some use cases like the one we consider, a traditional representation of texts by "bags of words" gives better classification results than the promising representation by "word embeddings".

## Keywords

Text categorization, Machine Learning, Bag of words, Word embedding

# 1 Introduction

The Silex France company offers a SaaS sourcing tool for identification of the service providers that are best suited to meet the service requests expressed by companies. The Silex platform is used by more than 5000 professionals to quickly identify and exchange with B2B service providers. Silex's ultimate aim is to provide a network of qualified

companies to service buyers combined with the best functionality to consult it.

In the framework of a collaborative project between Silex and the I3S research laboratory, we aim at introducing semantics into the B2B platform in order to enable automatic reasoning on service requests and offers and improve the recommendation of service providers.

As a first step, we are interested in automatically categorizing the textual description of companies, service requests and service offers. With data's exponential growth, text categorization has become a crucial issue in Natural Language Processing (NLP). It consists in classifying texts according to their contents, into one or more predefined categories [2]. In recent years, the number of machine learning (ML) techniques that automatically generate text categorization has increased considerably [3].

In this paper we report some experiments we conducted to answer the Silex use case, using supervised ML techniques to classify Silex textual data into predefined categories. Meanwhile, we addressed the following questions:

(1) What is the best representation of Silex textual descriptions of service offers and requests to categorize it?

(2) What is the best ML algorithm to categorize Silex textual descriptions of service offers and requests?

This paper is organized as follows: Section 2 presents state-of-the-art text categorization methods. Section 3 introduces our approach of text categorization to answer the SILEX use case. Section 4 reports and discusses the results of our experiments of categorization of NL descriptions of service requests and offers. Section 5 draws some conclusions and directions for future work.

# 2 Related Works

Text categorization is the task of classifying data into a predefined set of categories. In other words, given a set of categories and a set of textual documents, text categorization is the process of automatically finding the correct category for each document [4].

## 2.1 Feature Vector Models

In the text categorization process, the first step consists in preprocessing textual documents, to convert them into feature vectors, a representation that can be automatically interpreted by machine. This step includes tokenization,

<footnote n="1">¹ Université Côte d'Azur, Inria, CNRS, I3S, Sophia Antipolis, France</footnote>

<footnote n="2">² Silex France</footnote>

<footnote>{dhouib, faron, tettamanzi}@i3s.unice.fr</footnote>
stemming and removing of stop words before the creation of feature vectors.

**Bag-Of-Words (BOW).** is the most common feature vector model. In this model, the features are the frequencies of each word in the textual document. The feature space's dimension is the number of all different words in all documents [4]. The limitation of this model is that it ignores the semantic relations between words.

**Word Embedding (WE).** In order to overcome the weakness of BOW, a new model called Word Embedding (WE) has been successfully used in several NLP tasks. Word embeddings are projections in a continuous space of words that preserve the semantic and syntactic similarities between them [6]. There are many models that can produce a word embedding. In the following, we introduce the most important ones.

[7] proposes Word2Vec, a popular tool that produces word embeddings based on two models: CBOW and Skip-gram. CBOW is a Neural Network and log-linear model. It removes the non-linear hidden layer, and projects the contextual words on the same position. Word's prediction is obtained according to its past and future contexts. The process consists in computing the average of the contextual word vectors and running a log-linear classifier on the averaged vector.

Skip-gram is similar to CBOW and is also a Neural Network and log-linear model. Contrary to CBOW, Skip-gram predicts the contextual words given the current word [6]. Another model was introduced by [8] and is called GloVE. This model is based on global matrix factorization that calculates the co-occurrence of words in the corpus [6].

Finally, *FastText*<fnref n="1" /> is a library for learning word representations and sentence classification. FastText published pre-trained word vectors for 294 languages, trained on Wikipedia. These vectors with dimension 300 were obtained using the skip-gram model [13].

## 2.2 Binary classification

After the construction of feature vectors, the second step of text categorization is the learning step. We present here some of the many learning algorithms for binary classification and multi-label classification.

**Naive Bayes (NB) [9].** is a supervised, probabilistic algorithm based on Bayes theorem and the hypothesis of the independence between features. This algorithm is powerful due to the independence between features that ignores features' order, and consequently, the presence of a feature does not affect other features in classification tasks [14].

**Support Vector Machine (SVM) [10].** is one of the most common and successful supervised classification algorithm used for text classification tasks [14]. This algorithm transforms training data into higher dimensions and searches for linear optimal separating hyperplane [1].

**Neural Networks (NN).** The NN is composed by many layers to perform text categorization. The perceptron is the simplest kind of a neural network and it has only two layers: the input nodes receive the feature values, the output nodes produce the categorization status values, and the link weights represent dependence relations. The NN text categorization process starts by loading feature weights into the input nodes; the categorization's final result is present in the output nodes after the propagation of the activation of the nodes forward through the network. The neural networks are trained by back propagation in order to minimize the error. In case of misclassification, the error is propagated back through the network and modifies the link weights [15].

## 2.3 Multi-label classification

Multi-label classification is an approach to classification problems that allows each data point to be assigned to more than one class at the same time. There are two multi-label classification methods: (i) problem transformation and (ii) algorithm adaptation [11]. Here we describe the most popular algorithms of each category.

**Problem transformation.** A first approach consists in transforming the multi-label problem into one or more single label classification problem. Among the methods adopting this approach, we can highlight:

* **The Binary Relevance method (BR)** is based on one-vs-all ensemble approach. BR transforms any multi-label problem into binary problems to predict the relevance of each label to a data point. All binary classifiers are then aggregated to form a set of relevant labels [11].

* **The label PowerSet method (LP)** considers the multi-label problem as a single multi-class classification problem. In order to create a transformed multi-class dataset, each combination of relevant labels is mapped to a class [11].

* **The Random K-label set (RAKEL)** aims at finding a better balance between BR and LP. RAKEL generates a series of label subsets and builds a label powerset model for each of them [11].

**Algorithm adaptation.** Algorithm adaptation extends specific algorithms to carry out multi-label classification.

* **Multi-label lazy algorithm (ML-KNN)** is one of the most famous adaptation algorithms. MLKNN uses the maximum a posteriori principle in addition to the K-nearest neighbour algorithm [11].

* **Multi-label decision tree (ML-DT)** is an extension of C4.5 decision tree algorithm. ML-DT allows the creation of multiple labels in the leaves, and chooses node splits based on a pre-defined multi-label entropy function [11].

<footnote n="1">¹https://github.com/facebookresearch/fastText</footnote>
* AdaBoost is based on the addition of simple classifiers to a pool and the use of their weights to define the final classification [16].

# 3 Experimental methodology

To answer the Silex use case, we conducted some experiments to compare the performance of the above described state-of-the-art feature vector models and learning algorithms for the categorization of textual descriptions of service offers or requests.

## 3.1 Dataset

Silex distributes a service to purchasing departments that support the sourcing system within the company. Silex users can describe their company (company description), their needs (service request description) and the description of the offers provided by the company (service offer description) in Silex web application. All descriptions are written in French.

The dataset considered in our experiments comprises 3188 company descriptions, 580 service offers descriptions and 155 service requests descriptions.

Six main categories are defined by Silex to classify these descriptions. One description can be categorized in one or more classes. The categorization phase is done manually by experts in the current version of the Silex platform. Table 1 shows the distribution of all the descriptions into the different categories. We observe that the distribution of our dataset is unbalanced, for instance the *Informatique* (Information Technology) class has 915 more companies descriptions than the *Services_industriels* (Industrial Services) class.

<table><caption>Table 1: Distribution of the textual descriptions in the corpus.</caption><thead><tr><th>Categories</th><th>Companies descriptions</th><th>service offer descriptions</th><th>service request descriptions</th></tr></thead><tbody><tr><td>Informatique</td><td>1043</td><td>147</td><td>42</td></tr><tr><td>Finance</td><td>393</td><td>40</td><td>13</td></tr><tr><td>Services généraux</td><td>929</td><td>149</td><td>65</td></tr><tr><td>Marketing</td><td>926</td><td>160</td><td>18</td></tr><tr><td>Ressources humaines</td><td>297</td><td>57</td><td>7</td></tr><tr><td>Services industriels</td><td>128</td><td>32</td><td>19</td></tr></tbody></table>

## 3.2 Implementation

In our implementation, we focused first on two methods to construct our feature vectors:

* The BOW representation is achieved by applying a traditional process of tokenization, stop words removal and lemmatization. Then we use the TFIDF to construct the matrix. This matrix will be used in different algorithms.

<figure><img src="image_63.png" /><figcaption>Figure 1: Building WE feature vectors representing the Silex textual descriptions from pre-trained word embeddings</figcaption></figure>

* There are two methods to obtain Word embeddings representation: (i) build word embeddings from scratch using a model like word2vec or FastText. This approach needs a very large corpus to train these word embeddings; and (ii) use a pre-trained word embeddings in any desired language. For our case, we used the latter approach to obtain word embeddings because we do not have a large enough dataset. After studying the different pre-trained word embeddings, we decided to use the FastText model because it is the only model that provides French word embeddings pre-trained on a Wikipedia dump. This word embedding model<fnref n="2" /> contains 1,152,449 tokens, which are mapped to vectors in a space with 300 dimensions.

Our approach to produce the feature vectors representing the SILEX textual descriptions is inspired by [12] and [17]: As illustrated in Figure 1, the first step is to convert textual descriptions to lower case and remove all French stop words. Then the words are checked against the pretrained French vector. If the word exists in the dictionary, the vector representation of description is constructed by averaging the word embeddings vectors along each dimension for all the words in the description. If the dictionary does not contains the word, the zero vector is returned:

$$DescriptionWordEmbdings = \sum_{i=1}^{k} \frac{w_i}{k}$$

where k is the number of words in a description and $w_i \in \mathbb{R}^n$ denotes the word embeddings vector of the ith word. The vector representation of each description has exactly the same dimensions as the word embeddings vector $w_i$ [17]. The vector representations of each description are then used as features and input for each classifier.

<footnote n="2">²https://fasttext.cc/docs/en/pretrained-vectors.html</footnote>
In order to test our feature vectors, we trained two methods of categorization: (i) three binary classification algorithms (NB, SVC, RNN) and (ii) three multi-label classification algorithms: two of them are problem transformation methods (Binary Relevance, Label PowerSet) and three of them are algorithm adaptation methods (Multi-label lazy algorithm (ML-KNN)). All these algorithms are implemented using scikit-learn<fnref n="3" />, and executed on a machine with 8 GB of memory and an Intel Core i7-7500U CPU.

To deal with the unbalanced data, there are two main state-of-the-art approaches to adjust the distribution of dataset: (i) over-sampling adds copies of instances from the under-represented class. The most common technique of over-sampling is called Synthetic Minority Over-sampling Technique (SMOTE), (ii) under-sampling deletes instances from the over-represented class. In our implementation, we tested first a very large parameter with a grid function in scikit-learn to identify the best parameters for each classifier and the best method to deal with unbalanced data. We obtained the best results with SMOTE method for SVM algorithm, and RandomOver Sampler method for NB. Table 2 shows all parameters used in binary classification and Table 3 shows all parameters used in multi-label classification.

<table><caption>Table 2: Parameters used for binary classification</caption><thead><tr><th>Classifier</th><th>Unbalanced data</th><th>Parameters</th></tr></thead><tbody><tr><td>NB</td><td>RandomOver Sampler</td><td></td></tr><tr><td>SGDClassifier</td><td>SMOTE</td><td>penalty='l2'<br>alpha=0.0001</td></tr><tr><td>LinearSVC</td><td>SMOTE</td><td>C=0.1<br>penalty='l2'<br>loss='squared hinge'</td></tr><tr><td>SVC</td><td>SMOTE</td><td>kernel='rbf'<br>C=1000.0<br>gamma=0.0001</td></tr><tr><td>RNN</td><td>balanced</td><td>hidden size=32<br>Activation('relu')</td></tr></tbody></table>

<table><caption>Table 3: Parameters used for multi-label classification</caption><thead><tr><th>Classifier</th><th>multi-label methods</th><th>Parameters</th></tr></thead><tbody><tr><td>LSVC</td><td>Binary Relevance</td><td>C=1, penalty='l2'</td></tr><tr><td>LSVC</td><td>Label Powerset</td><td>C=1, penalty='l2'</td></tr><tr><td>MLkNN</td><td>Algorithm adaptation</td><td>-</td></tr></tbody></table>

# 4 Experiments and discussion

## 4.1 Evaluation procedure

The experiments were conducted using the 5-fold cross-validation methodology. To evaluate our experiments, we calculated the classification duration and various evaluation measures inspired by [18] and described in the following.

**Binary algorithms.** To evaluate binary classification algorithms, we used the **F1 score** measure, defined as the harmonic mean between precision and recall:

$$F1score = \frac{1}{N} \sum_{i=1}^{N} \frac{2 \times |h(xi) \cap yi|}{|h(xi) + yi|}$$

**Multi-label algorithms.** To evaluate multi labels algorithms we used the following metrics:

* **Accuracy** allows to compute the percentage of correctly predicted labels among all predicted and true labels. It is defined as follows:

$$Accuracy(h) = \frac{1}{N} \sum_{i=1}^{N} \frac{|h(xi) \cap yi|}{|h(xi) \cup yi|}$$

* **Micro-precision** is defined as the precision averaged over all the example/label pairs:

$$Micro_{precision} = \frac{\sum_{j=1}^{Q} tpj}{\sum_{j=1}^{Q} tpj + \sum_{j=1}^{Q} fpj}$$

where tpj, fpj are the number of true positives and false positive for label $\lambda_j$.

* **Micro-recall** is defined as recall averaged over all the example/label pairs:

$$Micro_{recall} = \frac{\sum_{j=1}^{Q} tpj}{\sum_{j=1}^{Q} tpj + \sum_{j=1}^{Q} fnj}$$

where fnj is the number of false negatives for the label $\lambda_j$.

* **Micro-F1** is the harmonic mean between micro-precision and micro-recall and is defined as:

$$Micro - F1 = \frac{2 \times micro_{precision} \times micro_{recall}}{micro_{precision} + micro_{recall}}$$

* **Hamming loss** allows to evaluate how many times an example-label pair is misclassified. The performance is perfect when the value of this metric is equal to 0. Hamming loss is defined as

$$Hamming\_loss(h) = \frac{1}{N} \sum_{i=1}^{N} \frac{1}{Q} |h(xi) \Delta yi|$$

where $\Delta$ is the symmetric difference between two sets, N is the number of examples and Q is the total number of possible class labels.

<footnote n="3">³http://scikit-learn.org/stable/</footnote>
## 4.2 Results and Analysis

The results of binary classification algorithms reported in Table 4, Table 5 and Table 6 show that there is not a significant difference between the results with a BOW representation and the results with a word embeddings representation. For example, for category "Informatique", we obtain the same precision value that equals to 0.82. The recall value equals to 0.82 for BOW representation, and is a bit better compared to WE recall value that equals to 0.79. The classification processing time is much better for WE (0.48 seconds) than for BOW (1572 seconds). This is due to the BOW expansive phases of lemmatization and matrix building compared to the vector representation of word embeddings.

<table><caption>Table 4: Best classifier of binary classification of companies descriptions</caption><thead><tr><th>Category</th><th>Method</th><th>P</th><th>R</th><th>F1</th><th>Time</th></tr></thead><tbody><tr><td rowspan="2">Informatique</td><td>LSVC + WE</td><td><strong>0.82</strong></td><td>0.79</td><td>0.80</td><td>0.48</td></tr><tr><td>SGD+BOW</td><td><strong>0.82</strong></td><td><strong>0.82</strong></td><td><strong>0.82</strong></td><td>1572</td></tr><tr><td rowspan="2">Finance</td><td>LSVC+WE</td><td>0.90</td><td><strong>0.87</strong></td><td><strong>0.88</strong></td><td>0.21</td></tr><tr><td>NB+BOW</td><td><strong>0.92</strong></td><td><strong>0.87</strong></td><td><strong>0.88</strong></td><td>1793</td></tr><tr><td rowspan="2">Services généraux</td><td>LSVC+ WE</td><td>0.87</td><td>0.84</td><td>0.85</td><td>0.4</td></tr><tr><td>NB + BOW</td><td><strong>0.90</strong></td><td><strong>0.89</strong></td><td><strong>0.89</strong></td><td>1925</td></tr><tr><td rowspan="2">Marketing</td><td>LSVC+WE</td><td>0.82</td><td>0.80</td><td>0.81</td><td>0.41</td></tr><tr><td>SGD + BOW</td><td><strong>0.85</strong></td><td><strong>0.85</strong></td><td><strong>0.85</strong></td><td>1517</td></tr><tr><td rowspan="2">Ressources humaines</td><td>LSVC + WE</td><td>0.91</td><td>0.83</td><td>0.86</td><td>0.19</td></tr><tr><td>NB + BOW</td><td><strong>0.92</strong></td><td><strong>0.84</strong></td><td><strong>0.87</strong></td><td>1904</td></tr><tr><td rowspan="2">Services industriels</td><td>LSVC+WE</td><td>0.94</td><td>0.89</td><td>0.91</td><td>0.05</td></tr><tr><td>NB+BOW</td><td><strong>0.97</strong></td><td><strong>0.94</strong></td><td><strong>0.95</strong></td><td>1914</td></tr></tbody></table>

<table><caption>Table 5: Best classifier of binary classification of service offer descriptions</caption><thead><tr><th>Category</th><th>Method</th><th>P</th><th>R</th><th>F1</th><th>Time</th></tr></thead><tbody><tr><td rowspan="2">Informatique</td><td>RNN+WE</td><td><strong>0.80</strong></td><td><strong>0.78</strong></td><td><strong>0.79</strong></td><td>8.53</td></tr><tr><td>RNN +BOW</td><td>0.78</td><td><strong>0.78</strong></td><td>0.78</td><td>332</td></tr><tr><td rowspan="2">Finance</td><td>SVC-RBF+ WE</td><td>0.82</td><td>0.87</td><td>0.84</td><td>0.083</td></tr><tr><td>SGD + BOW</td><td><strong>0.91</strong></td><td><strong>0.90</strong></td><td><strong>0.86</strong></td><td>323</td></tr><tr><td rowspan="2">Services généraux</td><td>RNN+ WE</td><td><strong>0.82</strong></td><td><strong>0.81</strong></td><td><strong>0.81</strong></td><td>6.97</td></tr><tr><td>RNN+BOW</td><td>0.79</td><td>0.79</td><td>0.79</td><td>348</td></tr><tr><td rowspan="2">Marketing</td><td>SGD+WE</td><td>0.80</td><td>0.77</td><td>0.78</td><td>0.028</td></tr><tr><td>NB + BOW</td><td><strong>0.90</strong></td><td><strong>0.90</strong></td><td><strong>0.90</strong></td><td>459</td></tr><tr><td rowspan="2">Ressources humaines</td><td>RNN + WE</td><td><strong>0.90</strong></td><td><strong>0.91</strong></td><td><strong>0.90</strong></td><td>7.42</td></tr><tr><td>NB + BOW</td><td>0.87</td><td>0.87</td><td>0.87</td><td>419</td></tr><tr><td rowspan="2">Services industriels</td><td>SVC-RBF+ WE</td><td>0.91</td><td>0.92</td><td>0.91</td><td>0.09</td></tr><tr><td>SVC-RBF+BOW</td><td><strong>0.96</strong></td><td><strong>0.97</strong></td><td><strong>0.96</strong></td><td>347</td></tr></tbody></table>

We can draw similar conclusions when comparing multi_label classification algorithms, with a slight advantage to BOW compared to word embeddings in terms of accuracy and hamming_loss but not in term of time.

If we compare binary classification and multi_label classification algorithms, we can see that the results of the first algorithm are better than the second one. These results are as expected because first we don't have a very large corpus, and second when we use a binary classification we can play

<table><caption>Table 6: Best classifier of binary classification of service request descriptions</caption><thead><tr><th>Category</th><th>Method</th><th>P</th><th>R</th><th>F1</th><th>Time</th></tr></thead><tbody><tr><td rowspan="2">Informatique</td><td>NB +WE</td><td><strong>0.82</strong></td><td><strong>0.77</strong></td><td><strong>0.79</strong></td><td>0.006</td></tr><tr><td>NB+ BOW</td><td>0.79</td><td>0.74</td><td>0.76</td><td>101.31</td></tr><tr><td rowspan="2">Finance</td><td>RNN +WE</td><td><strong>0.97</strong></td><td>0.48</td><td>0.62</td><td>2.44</td></tr><tr><td>LSVC + BOW</td><td>0.94</td><td><strong>0.94</strong></td><td><strong>0.92</strong></td><td>84.82</td></tr><tr><td rowspan="2">Services généraux</td><td>NB+ WE</td><td><strong>0.74</strong></td><td><strong>0.74</strong></td><td><strong>0.74</strong></td><td>0.006</td></tr><tr><td>NB + BOW</td><td><strong>0.74</strong></td><td><strong>0.74</strong></td><td><strong>0.74</strong></td><td>103.49</td></tr><tr><td rowspan="2">Marketing</td><td>RNN + WE</td><td>0.73</td><td>0.77</td><td>0.74</td><td>2.74</td></tr><tr><td>NB +BOW</td><td><strong>0.89</strong></td><td><strong>0.81</strong></td><td><strong>0.84</strong></td><td>104.10</td></tr><tr><td rowspan="2">Ressources humaines</td><td>NB+ WE</td><td>0.88</td><td>0.94</td><td>0.90</td><td>0.006</td></tr><tr><td>BOW</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td rowspan="2">Services industriels</td><td>RNN + WE</td><td>0.91</td><td>0.90</td><td>0.88</td><td>2.62</td></tr><tr><td>LSVC+BOW</td><td><strong>0.94</strong></td><td><strong>0.94</strong></td><td><strong>0.94</strong></td><td>79.07</td></tr></tbody></table>

<table><caption>Table 7: Best classifier of multi_label classifications.</caption><thead><tr><th>Classifier</th><th>Feature</th><th>Micro-F1</th><th>Accuracy</th><th>Hamming loss</th><th>Time</th></tr></thead><tbody><tr><td rowspan="2">MLKNN</td><td>WE</td><td>0.66</td><td>0.53</td><td>0.12</td><td>7.00</td></tr><tr><td>BOW</td><td>0.72</td><td>0.57</td><td>0.10</td><td>1945</td></tr><tr><td rowspan="2">BR</td><td>WE</td><td>0.61</td><td>0.35</td><td>0.17</td><td>6.54</td></tr><tr><td>BOW</td><td>0.73</td><td>0.52</td><td>0.10</td><td>1850</td></tr><tr><td rowspan="2">Label Powerser</td><td>WE</td><td>0.54</td><td>0.39</td><td>0.19</td><td>9.44</td></tr><tr><td>BOW</td><td>0.69</td><td>0.51</td><td>0.13</td><td>1945</td></tr></tbody></table>

on the classifier parameters for each category to enhance its performance, which is not the case for multi_label classification. The different binary classification algorithms perform more or less well in categorizing our dataset using the same representation. For example, only the LSVC algorithm categorized correctly this text as "informatique" "Ascot accompagne les dirigeants et cadres de PME dans la définition, la maitrise et le suivi de leur transformation numérique. Plus aucune organisation ne peut ignorer l'impact global sur son métier, ses outils et ses processus. Notre expérience, de plus de 20 ans, en Conseil, Assistance technique, Développement, Ingénierie, ... est entièrement dédié à nos clients. Sous contrat ou à la carte, nos prestations leur apportent valeur et sérénité.".

We obtained also different results when comparing the BOW and WE representations. For example, using the same LinearSVC algorithm, this text "Agence WebMarketing 360 de nouvelle génération exploitant de nombreux leviers marketing pour optimiser vos campagnes digitales & booster votre chiffre d'affaires Kalipseo développe pour vous les stratégies digitales les plus pertinentes et s'emploie à promouvoir l'image de votre marque." was wrongly categorized as "Informatique" when using the WE representation, but the categorization was right when using BOW representation.

As a conclusion, to best answer the Silex use case, we decided to use a binary classification algorithm with a word embedding representation. Table 8 shows the algorithms that are selected to classify each category of Silex data.
<table><caption>Table 8: Selected algorithms for Silex Company</caption><thead><tr><th>Category</th><th>Description</th><th>Representation</th><th>Algorithm</th></tr></thead><tbody><tr><td rowspan="3">Informatique</td><td>Companies</td><td>WE</td><td>NB</td></tr><tr><td>Service offer</td><td>WE</td><td>RNN</td></tr><tr><td>Service provider</td><td>WE</td><td>NB</td></tr><tr><td rowspan="3">Finance</td><td>Companies</td><td>WE</td><td>RNN</td></tr><tr><td>Service offer</td><td>WE</td><td>SVC-RBF</td></tr><tr><td>Service provider</td><td>WE</td><td>RNN</td></tr><tr><td rowspan="3">Services généraux</td><td>Companies</td><td>WE</td><td>NB</td></tr><tr><td>Service offer</td><td>WE</td><td>RNN</td></tr><tr><td>Service provider</td><td>WE</td><td>NB</td></tr><tr><td rowspan="3">Marketing</td><td>Companies</td><td>WE</td><td>RNN</td></tr><tr><td>Service offer</td><td>WE</td><td>SGD</td></tr><tr><td>Service provider</td><td>WE</td><td>RNN</td></tr><tr><td rowspan="3">Ressources Humaines</td><td>Companies</td><td>WE</td><td>NB</td></tr><tr><td>Service offer</td><td>WE</td><td>RNN</td></tr><tr><td>Service provider</td><td>WE</td><td>NB</td></tr><tr><td rowspan="3">Services industriels</td><td>Companies</td><td>WE</td><td>RNN</td></tr><tr><td>Service offer</td><td>WE</td><td>SVC-RBF</td></tr><tr><td>Service provider</td><td>WE</td><td>RNN</td></tr></tbody></table>

## 5 Conclusion

In this paper we reported the results of the experimental evaluations of various vector feature models and machine learning algorithms conducted to answer the real-world use case of the Silex company: how to categorize textual descriptions of service offers and requests with the ultimate goal of recommending service providers that better answer services requests. We compared the two main state-of-the-art feature vector models. A BOW representation is a bit better than a WE representation regarding the evaluation measures. This is due to the use of a generic pre-trained vector for WE descriptions, that is based on Wikipedia dump and that does not cover well our data set. On the other hand, a WE representation has the advantage of being less time consuming because of the additional lemmatization and matrix building phases specific to the BOW representation. Based on these results, we choose to use classifiers with word embeddings data for Silex company as shown in Table 8.

As future work, we aim to define a specific B2B pre-trained vector that best covers the Silex dataset instead of using a general reference like Wikipedia. We also aim to study a combined approach based on both word embeddings and knowledge engineering approaches. The objective is to improve the representation of texts by introducing semantics to increase the performance of algorithms. To achieve this, we are going to use our built ontologies to represent the sourcing domain, and we are going to enrich the original texts with additional information based on semantics relations between concepts such as generalization or specification.

## 6 Aknowledgement

This work is supported by the ANRT, CIFRE I3S-SILEX 2016/0947

## References

[1] Patra, Anuradha and Singh, Divaka A survey report on text classification with different term weighing methods and comparison between classification algorithms *International Journal of Computer Applications*, volume.75, pp.7.2013,Foundation of Computer Science.

[2] Sadiq, Ahmed T and Abdullah, Sura Mahmood, Hybrid intelligent technique for text categorization *Advanced Computer Science Applications and Technologies (ACSAT), 2012 International Conference on*, pp.238-245,2012,IEEE.

[3] Tan, Ah-Hwee and Lai, Fon-Lin, Text categorization, supervised learning, and domain knowledge integration *To appear, proceedings, KDD-2000 International Workshop on Text Mining, Boston, Vol.20,2000.*

[4] Feldman, Ronen and Sanger, James, The text mining handbook: advanced approaches in analyzing unstructured data, 2007, Cambridge university press.

[5] Sriram, Bharath and Fuhry, Dave and Demir, Engin and Ferhatosmanoglu, Hakan and Demirbas, Murat, Short text classification in twitter to improve information filtering, Proceedings of the 33rd international ACM SIGIR conference on Research and development in information retrieval, pp.841-842, 2010, ACM

[6] Ghannay, Sahar and Favre, Benoit and Esteve, Yannick and Camelin, Nathalie, Word Embedding Evaluation and Combination, LREC, 2016

[7] Mikolov, Tomas and Chen, Kai and Corrado, Greg and Dean, Jeffrey, Efficient estimation of word representations in vector space, arXiv preprint arXiv:1301.3781, 2013

[8] Pennington, Jeffrey and Socher, Richard and Manning, Christopher, Glove: Global vectors for word representation, Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp.1532-1543, 2014

[9] Schneider, Karl-Michael, Techniques for improving the performance of naive bayes for text classification, Computational Linguistics and Intelligent Text Processing, pp.682-693, 2005, Springer

[10] Cortes, Corinna and Vapnik, Vladimir, Support-vector networks, Machine learning, Vol.20,3, pp.273-297, 1995, Springer

[11] Pakrashi, Arjun and Greene, Derek and MacNamee, Brian, Benchmarking Multi-label Classification Algorithms, 24th Irish Conference on Artificial Intelligence and Cognitive Science (AICS'16), Dublin, Ireland, 20-21 September 2016, 2016, CEUR Workshop Proceedings