=Paper=
{{Paper
|id=Vol-2133/cnia-paper7
|storemode=property
|title=Trois approches pour classifier les données du web des données(Three approaches for classifying data from web of data)
|pdfUrl=https://ceur-ws.org/Vol-2133/cnia-paper7.pdf
|volume=Vol-2133
|dblpUrl=https://dblp.org/rec/conf/rjcia/ReynaudTN18
}}
==Trois approches pour classifier les données du web des données(Three approaches for classifying data from web of data)==
https://ceur-ws.org/Vol-2133/cnia-paper7.pdf
Trois approches pour classifier les données du web des données
Justine Reynaud Yannick Toussaint Amedeo Napoli
Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
prénom.nom@loria.fr
Résumé Keywords
Dans cet article, nous nous intéressons au processus de Relational data, Formal Concept Analysis, Redescription
classification de données relationnelles issues du web des mining, DBpedia.
données. Nous disposons d’un ensemble d’objets entre les-
quels il existe des relations. Ces objets appartiennent à 1 Introduction
une ou plusieurs classes. Celles-ci sont définies en exten- Dans cet article, nous nous intéressons à la possibilité de
sion, et nous cherchons à construire une description en in- découvrir des définitions dans les données RDF issues du
tension en s’appuyant sur les relations des objets qui les web des données. Ces définitions peuvent être réutilisées
composent. Pour cela, nous employons trois approches : dans la conception de bases de connaissances (KBs) ou
les règles d’association qui s’appuient sur l’Analyse de dans l’enrichissement de KBs préexistantes. Étant donné
Concepts Formels (FCA), les redescriptions et les règles de l’immense quantité de données du web des données, il
traduction qui s’appuient sur la Longueur de Description s’agit d’un enjeu majeur.
Minimale (MDL). À partir d’expérimentations sur DBpe- Le problème est le suivant : nous disposons d’un ensemble
dia, nous discutons les spécificités et la complémentarité d’objets connectés par des relations, comme une ABox en
de ces trois approches. Nous montrons que les règles d’as- logique de descriptions (DL) (Baader et al., 2003). L’ob-
sociation sont les plus exhaustives tandis que les règles de jectif est de classifier ces objets en fonction des relations
traduction ont une meilleure couverture des données. Les dans lesquelles ils sont impliqués.
redescriptions pour leur part, sont les règles les plus fa- Les objets qui partagent des éléments communs appar-
ciles à appréhender et interpréter. tiennent à une même classe. Ce partage peut être exact —
les éléments sont identiques — ou approximatif — les élé-
Mots Clef ments sont similaires. Finalement, nous obtenons un en-
Données relationnelles, Analyse de Concepts Formels, semble de classes organisées selon un ordre partiel, et les
Fouille de redescriptions, DBpedia. descriptions associées à ces classes. Ces descriptions sont
nécessaires afin de construire les définitions des différentes
Abstract classes. Les définitions sont considérées comme des condi-
tions nécessaires (NC) et suffisantes (SC) pour classifier de
In this paper we study a classification process on relational nouveaux objets. Si x est une instance de la classe Rouge
data that can be applied to the web of data. We start with alors x a la couleur rouge (NC), et inversement, si x à la
a set of objects and relations between objects, and exten- couleur rouge alors x est une instance de la classe Rouge
sional classes of objects. We then study how to provide a (SC).
definition to classes, i.e. to build an intensional description Pour poursuivre l’analogie avec les DLs, l’idée dans cet ar-
of the class, w.r.t. the relations involving class objects. To ticle est de construire et d’appliquer des règles d’induction
this end, we propose three different approaches based on de la forme « si r(x, y) et y:C alors x:∃r.C ». Cela si-
Formal Concept Analysis (FCA), redescription mining and gnifie que, étant données y une instance de la classe C et
Minimum Description Length (MDL). Relying on some ex- r une relation telle que r(x, y), alors x appartient à une
periments on RDF data from DBpedia, where objects cor- classe, disons D, dont la description comprend ∃r.C. C’est-
respond to resources, relations to predicates and classes à-dire que les instances de D sont reliées à au moins une
to categories, we compare the capabilities and the com- instance de C par la relation r. Nous utilisons ce type de
plementarity of the three approaches. This research work règles pour construire les définitions des classes. Ces défi-
is a contribution to understanding the connections existing nitions sont de la forme Ci ≡ e1 u e2 u . . . u en où ej est
between FCA and other data mining formalisms which are une expression de la forme ∃r.Cj . Notre travail se divise en
gaining importance in knowledge discovery, namely redes- trois tâches principales, à savoir (i) préparer les données,
cription mining and MDL. (ii) découvrir les définitions, (iii) évaluer la qualité de ces
x1 : C1 ex : x0 ex : r1 ex : x1 . et l’ensemble de triplets correspondant. Le préfixe ex:
r1 ex : x0 ex : r2 ex : x2 . correspond à un namespace créé pour notre exemple, tan-
x0 : C 0 ex : x0 rdf : type ex : C0 .
dis que le préfix rdf: correspond à un namespace pré-
r2 ex : x1 rdf : type ex : C1 .
existant.rdf:type est la relation d’instanciation. Ainsi
x2 : C2 ex : x2 rdf : type ex : C2 .
le triplet hex:x0 rdf:type ex : C0 i indique que x0 est une
instance de la classe C0 .
F IGURE 1 – Exemple de données relationnelles et les tri-
Le LOD peut être interrogé grâce aux requêtes SPARQL.
plets associés.
Par exemple, la requête SELECT ?x WHERE { ?x
rdf:type ex:C0 } retourne toutes les instances de CO .
définitions. Nous nous appuyons ici sur trois approches, les Si l’on prend les données de la figure 1, seul ex:x0 est re-
règles d’association, la fouille de redescriptions et la dé- tourné.
couverte de règles de traduction. 2.2 Analyse de Concepts Formels
Cet article est dans la continuité de travaux de recherche
Nous utilisons ici l’Analyse de Concepts Formels (FCA)
sur la découverte de définitions dans le web des données.
de Ganter et Wille (1999) pour présenter et comparer les
Son originalité est de comparer trois approches qui ne s’ap-
différentes approches. Étant donné un ensemble G d’en-
puient pas sur les mêmes principes mais qui s’avèrent être
tités 1 , un ensemble M d’attributs et une relation binaire
complémentaires au vu des résultats de nos expérimenta-
I ⊆ G × M , (G, M, I) est un contexte formel. L’expres-
tions. À notre connaissance, il s’agit du premier article où
sion gIm s’interprète comme « l’entité g possède l’attri-
une telle comparaison est proposée à la fois à un niveau
but m». Les correspondances de Galois (notées .0 ) pour
théorique et à un niveau expérimental.
un ensemble d’entités X ⊆ G et un ensemble d’attributs
L’article est organisé comme suit : dans la section 2, nous Y ⊆ M sont définies comme suit :
présentons la nature des données sur lesquelles nous tra-
vaillons et les processus de classification dans le web des X 0 ={m ∈ M | ∀x ∈ X, xIm} et
données. Dans la section 3, nous détaillons les trois ap- 0
Y ={g ∈ G | ∀y ∈ Y, gIy}.
proches de classification et leurs applications. La section 5
présente les expériences qui ont été menées ainsi que l’éva- À partir des données RDF, nous construisons un contexte
luation des règles obtenues. Enfin, la section 6 présente une formel dont les entités sont les sujets des triplets. Les attri-
discussion ainsi que les pistes de recherches futures avant buts sont les paires (prédicat,objet) issues des triplets. Nous
la conclusion section 7. distinguons deux types d’attributs : des descriptions et des
classes. Le premier ensemble d’attributs, dénoté C, est
2 Représentation des données composée des paires de la forme (rdf:type, C), qui font
d’un sujet une instance de la classe C. Ce sont ces classes
2.1 Web des Données que nous cherchons à définir. Le second ensemble, dénoté
Dans cette section, nous présentons les données issues du D est composé de paires (p, o) telles que p 6= rdf:type.
Web des Données (LOD) que nous considérons. Le LOD Les attributs du contexte sont donc M = C ∪ D. Si l’on
peut être vu comme un ensemble de KBs interconnectées. prend l’exemple de la figure 1, la figure ?? présente le
Une KB est composée de deux éléments : une TBox qui contexte associé.
définit son schema et une ABox qui introduit les indivi- Attributs
dus et leurs relations. L’unité de base d’une KB est le tri- Descriptions Classes
plet RDF, noté hs, p, oi, qui encode une assertion sous la ∃r1:C1 ∃r2:C2 C0 C1 C2
forme sujet–prédicat–objet. Les différentes composantes x0 × × ×
d’un triplet peuvent être des ressources U identifiées de Objets x1 ×
manière unique, des littéraux L (chaîne de caractères, nu- x2 ×
mérique, date, . . .) ou des nœuds anonymes B (assimilables
à une variable existentiellement quantifiée), de telle sorte F IGURE 2 – Contexte formel associé aux données repré-
que hs, p, oi ∈ (B ∪U )×U ×(B ∪U ∪L). Dans cet article, sentées figure 1.
nous nous restreignons aux triplets composés uniquement
de ressources, c’est-à-dire tels que hs, p, oi ∈ U × U × U . À partir de là, il s’agit de trouver un ensemble de catégo-
Les ressources peuvent faire référence à n’importe quel ob- ries et un ensemble de descriptions de manière à ce que
jet ou abstraction et sont identifiées par une URI (Uniform leurs correspondances soient les mêmes. Sur la figure ??
Resource Identifier). Une URI est une adresse composée de par exemple, on a {C0 }0 = x0 et {∃r1 :C1 , ∃r2 :C2 }0 = x0 .
deux parties. La première partie est l’espace de nom (na- On peut alors construire la définition suivante :
mespace) qui indique de quelle KB viennent les ressources.
La seconde partie donne un nom à la ressource au sein de C0 ≡ ∃r1 :C1 u ∃r2 :C2
cette KB. 1. En FCA, G est l’ensemble des objets, renommés entités afin de ne
La figure 1, présente un exemple de données relationnelles pas confondre avec les objets en RDF.
Comme les données peuvent être incomplètes, il se peut utiliser un post-traitement afin de s’assurer que la règle
qu’on ne retrouve pas une égalité entre une classe Ci et ne contient que des catégories d’un côté et que des des-
sa description ∃r:Cj . Autrement dit {Ci }0 6= {∃r:Cj }0 . Il criptions de l’autre. Pour cela, seules les règles X → Y
nous faut donc des approches qui tolèrent une forme d’ap- qui satisfont l’une des deux contraintes alternatives sui-
proximation. C’est ce que permettent les trois algorithmes vantes sont conservées : (i) l’antécédent ne contient que
utilisés, et nous allons les détailler plus précisément dans des classes (X ⊆ C) et il y a au moins une description dans
la section suivante. la conséquence (Y ∩ D = 6 ∅) ; (ii) l’antécédent ne contient
que des descriptions (X ⊆ D) et il y a au moins une classe
3 Algorithmes de fouille de règles dans la conséquence (Y ∩ C 6= ∅). Les règles conservées
sont décomposées de manière à ne garder que des classes
3.1 Règles d’association
(resp. des descriptions) dans la conséquence si l’antécédent
Le but de la fouille de règles d’association (Agrawal et al., ne contient que des descriptions (resp. des classes).
1993; Klemettinen et al., 1994) est de trouver des dépen- Par exemple, ∃r1 :C1 , C0 → ∃r2:C2 n’est pas conser-
dances entre les attributs. Une règle d’association entre vée parce que l’antécédent contient à la fois une
deux ensembles d’attributs X et Y , notée X → Y , signifie catégorie et une description. En revanche, la règle
« si un objet a tous les attributs de X, alors il a tous les ∃r1 :C1 → ∃r2 :C2 , C0 peut être décomposée en deux
attributs de Y ». À cette règle est associée une confiance, règles r1 : ∃r1 :C1 → ∃r2 :C2 et r2 : ∃r1 :C1 → C0 . La
qui peut être vue comme une probabilité conditionnelle : règle r2 est conservée. Si sa réciproque est valide, la quasi-
définition obtenue est C0 ↔ ∃r1 :C1 .
|X 0 ∩ Y 0 |
conf(X → Y ) = ,
|X 0 | 3.2 Redescriptions
La fouille de redescriptions, introduite par Ramakrishnan
où .0 correspond à la correspondance de Galois. La
et al. (2004), a pour but de trouver des caractérisations mul-
confiance est une mesure de qualité des règles d’associa-
tiples d’un même ensemble d’entités. À la différence des
tion. Une règle d’association est valide si sa confiance est
règles d’association, les redescriptions s’appuient sur une
supérieure à un seuil θ défini par l’utilisateur. La confiance
séparation de l’ensemble des attributs en vues. Une vue est
n’est pas symétrique : X → Y peut être valide sans que
un sous-ensemble d’attributs. L’ensemble des vues forme
Y → X le soit. Si la confiance vaut 1, on dit qu’il s’agit
une partition des attributs. Nous utilisons ici deux vues, qui
d’une implication et l’on note X ⇒ Y . Si on a égale-
correspondent aux deux types d’attributs — classes et des-
ment Y ⇒ X, alors X et Y forment une définition, notée
criptions.
X ≡Y.
La similarité entre deux ensembles d’attributs, provenant
Nous nous intéressons ici à des définitions. Nous considé-
de deux vues différentes, est mesurée avec le coefficient de
rons donc conjointement X → Y et sa réciproque Y → X
Jaccard :
et cherchons à estimer à quel point ces règles s’approchent | A0 ∩ B 0 |
d’une implication. Pour cela, nous introduisons la notion jacc(A, B) = ,
| A0 ∪ B 0 |
de quasi-définition qui est à la définition ce que la règle
d’association est à l’implication. où .0 correspond à la correspondance de Galois. Une paire
d’ensembles d’attributs (A, B) est une redescription si le
Définition 1 (Quasi-définition). Étant donné deux en- coefficient de Jaccard jacc(A, B) est supérieur à un seuil
sembles d’attributs X et Y , une quasi-définition X ↔ Y donné. Le coefficient de Jaccard est symétrique, contraire-
est valide si, pour un seuil θ donné, ment à la confiance. Une redescription dont le coefficient
de Jaccard vaut 1 est une définition. Toutes les redescrip-
min(conf(X → Y ), conf(Y → X)) > θ. tions sont nécessairement des quasi-définitions. En effet,
L’algorithme Eclat (Zaki, 2000) est l’un des nombreux min(conf(A → B), conf(B → A)) > jacc(A, B).
algorithmes de fouille de règles d’association existant. Il
énumère de manière exhaustive toutes les règles d’associa- L’algorithme ReReMi (Galbrun et Miettinen, 2012) est uti-
tion valides pour un seuil donné. Nous utilisons cet algo- lisé ici. En plus des données binaires, ReReMi permet de
rithme pour notre comparaison. tenir compte de données numériques et catégorielles. Les
Une règle d’association r0 : x1 , . . . , xn → y1 , . . . , ym redescriptions obtenues peuvent être des fonctions boo-
peut se décomposer sous la forme de plusieurs règles d’as- léennes contenant des disjonctions et des négations d’at-
sociation ri : x1 , . . . , xn → yi pour i ∈ {1, . . . , m}. tributs. Afin de comparer les trois algorithmes, ReReMi
Si r0 est valide, l’ensemble des ri est valide. Pour que est ici restreint à des conjonctions d’attributs, raison pour
les règles obtenues définissent des classes comme nous le laquelle nous ne parlons pas de fonctions booléennes.
souhaitons, il faut que les règles d’association soient de Dans un premier temps, ReReMi cherche des paires d’at-
la forme «Classes → Descriptions» ou «Descriptions → tributs — un attribut de chaque vue — susceptibles de
Classes». C’est à dire que la règle X → Y est telle que prendre part à une définition, c’est-à-dire celles qui ont le
X ⊆ C, Y ⊆ D ou X ⊆ D, Y ⊆ C. Il nous faut donc coefficient de Jaccard le plus élevé. Ces paires sont ensuite
étendues tour à tour, en ajoutant à chaque fois un attribut à où Mask+ correspond aux éléments ajoutés au masque (er-
l’un des côtés de la redescription, jusqu’à ce que le nombre reurs introduites par la règle) et Mask− correspond aux élé-
d’attributs maximum soit atteint ou que le coefficient de ments retirés du masque (erreurs corrigées par la règle).
Jaccard n’augmente plus. Les redescriptions ainsi obtenues Des règles sont ajoutées tant que ∆ est positif.
qui satisfont les critères de sélection sont retournées à l’uti- L’algorithme Translator est le seul dont la mesure de
lisateur. qualité tient compte des règles déjà extraites. Le masque
étant mis à jour à chaque étape, la qualité d’une règle dé-
3.3 Règles de traduction
pend des règles déjà extraites. Ainsi, Translator favo-
rise un bon ensemble de règles plutôt qu’un ensemble de
Contexte K1
But : traduire K1 à partir K2 Contexte K2 bonnes règles. Chaque règle apporte une information qui
a b c d et K2 à partir de K1 e f g h n’est pas contenue dans les autres, ce qui limite la redon-
1 × × 1 × ×
2 × × 2 × × dance d’information.
3 × × × 3 × × ×
e f g h e f g h
4 × ×
1 × × 1 × ×
4 × × 4 Travaux connexes
2 × × 2
Règles 3 × × × 3 La FCA est un outil de conceptualisation qui permet de
r1 : a, b → g, h 4 × 4 × structurer une ontologie par une approche bottom-up. Sert-
r2 : c → f Temp. Masque
kaya (2011) fait une synthèse des différentes contributions
qui s’intéressent au lien entre la FCA et les ontologies.
F IGURE 3 – Intuition du fonctionnement de
La plupart des ontologies sont construites avec une ap-
Translator. Ici, seule la traduction de K1 vers
proche top-down, c’est à dire en construisant d’abord le
K2 est représentée. À chaque étape, le but est de trouver la
schéma. L’une des façons de tirer parti de la FCA est donc
règle qui va minimiser le nombre de croix dans le masque.
de consuire des connaissances qui vont enrichir une onto-
logie préexistante. C’est ce que nous faisons dans notre ap-
L’algorithme Translator (van Leeuwen et Galbrun, proche, en partant de triplets pour trouver des définitions.
2015) s’appuie également sur une séparation du contexte
Dans (Ferré et Cellier, 2016), les auteurs proposent une ex-
en deux vues, et cherche un ensemble d’associations entre
tension de la FCA pour les graphes conceptuels. Contrai-
ces deux vues. Ces associations ont la même forme que des
rement aux graphes RDF qui reposent sur des relations bi-
règles d’association, la différence se situant au niveau de la
naires, les graphes conceptuels permettent de tenir compte
constitution de l’ensemble de règles.
de relation n-aires. Les concepts construits correspondent
Cet ensemble doit être compact et représentatif. D’une
à une association entre une requête SPARQL et l’ensemble
part, il doit couvrir la majorité des données. D’autre part,
des solutions. Dans notre approche, nous cherchons à
les règles doivent être aussi petites que possible en terme
mettre en relation deux graph patterns et nous ne connais-
d’attributs. Afin de trouver un équilibre entre ces deux
sons pas a priori la requête SPARQL qui correspond à la
contraintes, Translator s’appuie sur le concept de Lon-
description d’une catégorie.
gueur de Description Minimum (MDL). Étant donné un
Notre travail poursuit un travail initié dans (Alam et al.,
contexte K et X ⊆ M un ensemble d’attributs, la longueur
2015). Les auteurs s’appuient sur la fouille de règles d’as-
de X est
sociation pour fournir un espace de navigation sur des don-
X | x0 | nées RDF. Pour cela, les auteurs recherchent des implica-
L(X) = − log2 P (x | K) où P (x | K) = .
|G| tions et les ordonnent en fonction de la confiance de leur
x∈X
réciproque. Dans notre approche, nous introduisons la sé-
Cette longueur correspond au nombre minimal de bits re- paration des attributs et nous comparons les règles d’asso-
quis pour encoder X. ciation avec les redescriptions et les règles de traduction.
Pour construire l’ensemble des règles, les auteurs font L’algorithme AMIE, proposé par Galárraga et al.
l’analogie avec la notion de traduction. Une règle est une (2013), est une référence en matière de fouille de
traduction d’une vue vers une autre. L’idée sous-jacente est règles sur le web des données. Ces règles sont de la
la suivante : on souhaite construire un ensemble de règles forme B1 , B2 , . . . Bn−1 → Bn où Bi correspond à
qui permettent, connaissant une des deux vues, de recons- une relation entre deux variables, que l’on peut expri-
truire la seconde et vice versa. L’idée générale est représen- mer sous forme de triplet . Par exemple,
tée figure 2. Les erreurs entre le contexte cible et le contexte manuf acturer(x, Samsung), successor(y, x) →
reconstruit sont corrigées à l’aide d’un masque. La taille de manuf acturer(y, Samsung) est une règle qui peut être
ce masque indique donc le nombre d’erreurs introduites. trouvée par AMIE. Les auteurs ajoutent une condition,
L’ensemble de règles est construit de manière itérative, en à savoir que toutes les variables doivent apparaître deux
prenant, à chaque étape, la règle X → Y qui maximise ∆ fois dans la règle. Si l’on considère les triplets sous
forme de graphe, il en résulte qu’une règle est un motif
∆(X → Y ) = L(Mask− ) − L(Mask+ ) − L(X → Y ) cyclique entre des variables (indépendamment de l’orien-
| {z } | {z }
Gain d’information Longueur de la règle tation des arcs). Dans notre cas, les motifs recherchés
caractérisent une seule ressource identifiée (motif en Smartphones et Sports_cars. Le triplet ?p a
étoile) et l’association est bidirectionnelle. On trouve owl:objectProperty assure que ?o n’est pas un
par exemple la règle Samsung_M obile_P hone(x) ↔ littéral.
manuf acturer(x, Samsung). Les triplets extraits sont divisés en deux groupes. L’en-
semble des triplets qui ont pour prédicat dct:subject
?t2 Samsung_Mobile_Phone
correspond aux attributs de classe (C). L’ensemble des tri-
ma
r e
so
nu
typ plets dont le prédicat n’est pas dct:subject correspond
fa
es f:
ct
cc rd aux attributs de description (D).
ur
su
er
?t1 ?t3 ?t0 Samsung 5.2 Résultats et évaluation
manufacturer manufacturer
TABLE 2 – Évaluation des résultats pour chaque jeu de don-
F IGURE 4 – Motifs recherchés dans la base de connais- nées. |Ci | (resp. |Di |) désigne le nombre moyen de catégo-
sances par AMIE et par notre approche. Les traits pleins ries (resp. de descriptions) dans une règle.
concernent la partie gauche de la règle, et les pointillés la
partie droite. Les ?ti sont des variables existentielles. Turing_Award_laureates
X Eclat ReReMi Translator
X
5 Expérimentations Bcand 47 12 11
X
Bdef 30 9 9
Nous avons réalisé nos expérimentations sur des don-
nées issues de DBpedia, qui est une KB construite à Précision .64 .75 .85
partir de Wikipédia. Nous cherchons à définir des caté- |Ci | — |Di | 2—4 1—1 3—5
gories, c’est-à-dire les ressources qui sont dans le co-
Sports_cars
domaine de la relation dct:subject. Pour cela, nous
extrayons un sous-ensemble de DBpedia à l’aide d’une re- X Eclat ReReMi Translator
X
quête SPARQL avant de transformer les triplets obtenus Bcand 132 52 31
en contexte comme mentionné en Section 2.2. Enfin, nous X
Bdef 95 30 23
utilisons les trois algorithmes présentés pour comparer et Précision .72 .68 .74
évaluer les résultats obtenus. |Ci | — |Di | 2.8 — 4.5 1.3 — 1.4 2.6 — 4.1
TABLE 1 – Statistiques sur les jeux de données extraits. Smartphones
Attributs X Eclat ReReMi Translator
Triplets Objets X
Bcand 810 98 41
Cat. Descr.
Turing_Award 2 642 65 503 857 X
Bdef 521 57 31
Smartphones 8 418 598 359 1 730 Précision .64 .58 .76
Sports_cars 9 047 604 435 2 295 |Ci | — |Di | 4.3 — 7.8 1.6 — 1.8 3.1 — 3.1
French_films 121 496 6 039 6 028 19 459
French_films
X Eclat ReReMi Translator
5.1 Méthodologie X
Bcand 546 36 93
Nous avons extrait quatre sous-ensembles de triplets de X
Bdef 371 12 89
DBpedia, de différents domaines 2 . Afin d’isoler un sous-
ensemble de triplets, nous avons récupéré tous les triplets Précision .68 .33 .96
dont le sujet est lié à une catégorie donnée. Pour cela, nous |Ci | — |Di | 2.8 — 4.4 1.2 — 1.1 2.3 — 4.2
avons utilisé la requête SPARQL suivante :
Chaque algorithme retourne un ensemble ordonné de
SELECT DISTINCT * WHERE {
quasi-définitions de la forme C0 , . . . , Cn ↔ D0 , . . . , Dm .
?s ?p ?o .
Chacune des quasi-définitions est évaluée manuellement
?s dct:subject dbc:X .
par trois personnes jouant le rôle d’experts. Étant donnée
?p a owl:ObjectProperty .
une quasi-définition C0 , . . . , Cn ↔ D0 , . . . , Dm d’un jeu
}
de données J, l’évaluateur répond à la question « Étant
Les quatres domaines utilisés (X) sont donné que nous parlons de J, est il correct de dire que faire
French_films, Turing_Award_laureates, partie à la fois de C0 , de ... et de Cn et avoir les propriétés
D0 , . . .et Dm est équivalent ? »
2. Les jeux de données ainsi que les résultats obtenus sont dis-
ponibles à l’adresse https://gitlab.inria.fr/jreynaud/ L’évaluation finale est l’évaluation majoritaire des trois ex-
DefinitionMiningComparison. perts. Si la règle est acceptée, elle rejoint l’ensemble des
définitions obtenues, dont 20 exemples sont présentés fi- ont un support d’au moins 3, elles ne sont plus que 105, et
gure 4. Les experts ont été du même avis dans 95.4% des 47 catégories seulement on un support d’au moins 5. Nous
cas. La règle R5 de la figure 4 est une règle qui n’a pas fait considérons donc le rappel non pas par rapport au nombre
l’unanimité. de catégories présentes dans le jeu de données, mais par
Les algorithmes sont comparés sur la base des définitions rapport aux catégories retrouvées par l’ensemble des algo-
extraites et des catégories définies. La figure 5 présente un rithmes, comme présenté figure 6.
diagramme de Venn pour chaque corpus, qui représente le
nombre de définitions extraites par chaque algorithme. Par 6.2 Forme et interprétation des règles
exemple, pour le corpus Turing_Award_laureates,
il y a 22 définitions trouvées uniquement par Eclat, et D’après la figure 6, 70% des catégories définies par
8 trouvées à la fois par Eclat et Translator. Au to- Eclat ou Translator sont définies par les deux algo-
tal, Eclat a extrait 30 définitions. La figure 6 présente rithmes. Translator extrait considérablement moins de
également un diagramme de Venn pour chaque corpus, qui règles que Eclat (jusqu’à 16 fois moins pour le corpus
correspond au nombre de catégories définies par chaque Smartphones). Cela s’explique par la façon dont sont
algorithme. Une catégorie est considérée comme définie générées les règles d’association. Si dans les données, la
dès lors qu’elle apparaît dans au moins une définition. Il règle A → B a le même support que la règle A → B, C,
peut donc y avoir une ou plusieurs catégories considérées alors seule la règle A → B, C est conservée. En revanche
comme définies pour une seule définition. C’est notament si le support de A → B est strictement supérieur au sup-
le cas des règles R2, R8 – R10, R12, R14, R17 – R20 de la port de A → B, C, Eclat génère deux règles. En consé-
figure 4. quence, on obtient avec Eclat des règles qui ne diffèrent
que d’un attribut, comme R9 et R10 par exemple, alors
6 Discussion que Translator ne génère qu’une seule règle, R8 dans
l’exemple.
Ci-dessous, Bcand [X] désigne l’ensemble de toutes les
quasi-définitions extraites par l’algorithme X et Bdef [X] ReReMi n’extrait aucune définition en commun avec
l’ensemble des définitions de X, c’est-à-dire, l’ensemble Eclat et Translator. Cette différence s’explique par
des quasi-définitions de Bcand [X] évaluées vraies par les l’heuristique employée par ReReMi. Si C est une caté-
experts. L’ensemble Bcand désigne la totalité des quasi- gorie, et que D1 et D2 sont deux descriptions telles que
définitions,indépendamment de l’algorithme qui les a ex- C 0 = D10 = D20 , alors ReReMi privilégie deux définitions
traites. De la même façon, Bdef désigne l’ensemble de C ≡ D1 et C ≡ D2 tandis que Eclat ne génère qu’une
toutes les définitions extraites. seule définition C ≡ D1 uD2 . C’est par exemple le cas des
définitions R6, R7 générées par ReReMi et R8, générée
6.1 Précision et rappel par Eclat (figure 4). Si C 0 = D10 et D10 ⊂ D20 , ReReMi
|Bdef
X
| génère la définition C ≡ D1 , tandis que Eclat génère la
La précision d’un algorithme X est . La précision définition C ≡ D1 u D2 . Ce cas a également été retrouvé
|Bcand
X
|
de ReReMi a une très forte variabilité (entre 33 et 75%) et dans nos résultats, comme le montrent les définitions R12
est globalement la plus faible, tout particulièrement sur le et R13.
jeu de données French_films. La précision d’Eclat La taille des définitions générées par ReReMi est infé-
est stable (entre 64 et 72%). La meilleure précision est ob- rieure à celle des définitions de Translator et Eclat.
tenue par Translator : quel que soit le jeu de données, Cela s’explique par l’heuristique de ReReMi déaillée dans
elle toujours supérieure à 74%. le paragraphe précédent. ReReMi a en moyenne entre 1 et
|BX | 2 attributs de chaque côté de la définition tandis que pour
Le rappel, défini comme |Bdef def |
ne peut pas être utilisé
comme une mesure de performance. En effet, certaines Eclat et Translator, il y a en moyenne 3 catégories
règles se recouvrent (ont des attributs en commun des deux et 4 descriptions par définition.
côtés). C’est le cas des règles R6 à R10 (figure 4) qui dé- Les conjonctions dans les définitions extraites par ReReMi
finissent toutes la catégorie McLaren_vehicles. Tan- n’ont pas le même sens que celles extraites par Eclat et
dis que Translator n’extrait qu’une seule règle (R8), Translator. Par exemple, si l’on considère la définition
ReReMi extrait 2 règles (R6 et R7) et Eclat en extrait 9 R15, l’attribut (a Device) peut être enlevé sans alté-
(seules R8 à R10 sont reportées ici). rer la définition : parce que toutes les entités considérées
La table ?? indique le nombre de catégories pour chaque sont des instances de Device. À l’inverse, dans la défi-
jeu de données. Si l’on se fie à ces valeurs, le rappel est très nition R14, aucun attribut ne peut être retiré sans que la
faible : dans le corpus Turing_Award_laureates par définition ne devienne fausse : tous les attributs font par-
exemple, pour 503 catégories dans les données de départ, tie de la condition nécessaire. Dans notre approche, il nous
seules 19 font partie d’une règle. Cela s’explique principa- semble plus pertinent de n’intégrer que des attributs qui
lement par la très faible densité des contextes ; une grande contribuent pleinement à la définition dont ils font partie.
quantité de catégories ne concerne qu’une seule entité du Ainsi, la définition R14 nous parait préférable à la défini-
jeu de données. Si l’on ne compte que les catégories qui tion R15, parce qu’elle est apparue plus facile à interpréter.
Turing_Award_laureates
R Harvard_University_alumni ↔ (almaMater Harvard_University) R1
ET Harvard_University_alumni, Turing_Award_laureates ↔ (a Agent), (a Person), (a Scientist), (almaMater Harvard_University) R2
E Turing_Award_laureates ↔ (a Agent), (a Person), (award Turing_Award) R3
ET Turing_Award_laureates ↔ (a Agent), (a Person), (a Scientist), (award Turing_Award) R4
E Modern_cryptographers ↔ (field Cryptography) R5
Sports_cars
R McLaren_vehicles ↔ (manufacturer McLaren_Automotive) R6
R McLaren_vehicles ↔ (assembly Surrey) R7
ET McLaren_vehicles, Sports_cars ↔ (a Automobile), (a MeanOfTransportation), (assembly Woking), (assembly Surrey), (as- R8
sembly England), (bodyStyle Coupé), (manufacturer McLaren_Automotive)
E McLaren_vehicles, Sports_cars ↔ (a Automobile), (a MeanOfTransportation), (assembly England), (assembly Surrey), (bo- R9
dyStyle Coupé)
E McLaren_vehicles, Sports_cars ↔ (a Automobile), (a MeanOfTransportation), (assembly Surrey), (bodyStyle Coupé) R10
Smartphones
ET Firefox_OS_devices, Open-source_mobile_phones, Smartphones, Touchscreen_mobile_phones ↔ (a Device), (opera- R11
tingSystem Firefox_OS)
R Nokia_mobile_phones ↔ (manufacturer Nokia) R12
ET Nokia_mobile_phones, Smartphones ↔ (a Device), (manufacturer Nokia) R13
R Samsung_Galaxy ↔ (manufacturer Samsung_Electronics), (operatingSystem Android_(operating_system)) R14
ET Samsung_Galaxy, Samsung_mobile_phones, Smartphones ↔ (a Device), (manufacturer Samsung_Electronics), (opera- R15
tingSystem Android_(operating_system))
French_films
R Pathé_films ↔ (distributor Pathé) R16
R Films_directed_by_Georges_Méliès ↔ (director Georges_Méliès) R17
ET Films_directed_by_Georges_Méliès, French_films, French_silent_short_films ↔ (a Film), (a Wikidata :Q11424), (a Work), R18
(director Georges_Méliès)
ET Films_directed_by_Jean_Rollin, French_films ↔ (a Film), (a Wikidata :Q11424), (a Work), (director Jean_Rollin) R19
ET Film_scores_by_Gabriel_Yared, French_films ↔ (a Film), (a Wikidata :Q11424), (a Work), (musicComposer Gabriel_Yared) R20
F IGURE 5 – Exemples de quasi-définitions obtenues par Eclat, ReReMi et Translator pour chaque corpus. Lorsque le
préfixe d’un attribut de droite n’est pas spécifié, il s’agit de dbo. Le préfixe des catégories (dbc) n’est pas spécifié.
7 Conclusion à partir des données RDF sont très creux. Dans le cas
d’Eclat et de ReReMi, un seuil de support étant utilisé,
Dans cet article, nous nous sommes intéressés à trois algo- l’existence d’attributs à très faible support n’a pas d’impact
rithmes pour trouver des définitions de classes dans le web sur les règles retrouvées. Pour Translator en revanche,
des données. Nous avons vu que chaque algorithme avait les règles doivent permettre de reconstruire intégralement
ses spécificités et nous avons vérifié empiriquement que les le contexte. Dans ce cas, il peut être pertinent de simplifier
résultats extraits reflètent ces spécificités. Nous avons aussi le contexte avant de procéder à la fouille de règles. Cela
montré que malgré des approches très différentes, les algo- peut notamment passer par la suppression des attributs à
rithmes Eclat et Translator extraient de nombreuses très faible support, ou au contraire, des attributs ayant un
règles communes. À l’inverse, ReReMi, malgré une me- support quasi maximal, et donc qui concernent toutes les
sure de qualité semblable à Eclat, extrait des règles plus entités. Nous pourrons également travailler sur le type des
courtes. L’intérêt de ces algorithmes dépend de l’objec- données en entrée, en intégrant notamment des valeurs nu-
tif de l’utilisateur. Dans le cas de notre expérimentation, mériques, ce qui nous permettra de prendre en compte des
Eclat est l’algorithme qui a qualifié le plus de catégo- triplets laissés de côté pour cette expérimentation, tels que
ries, au prix d’un nombre de règles extraites très important. les informations de date, d’âge, de taille, . . .
Translator extrait significativement moins de règles Pour améliorer le processus de fouille, il est possible
avec un nombre de catégories définies légèrement inférieur. d’ajouter des contraintes sur les règles obtenues afin de
Enfin, ReReMi, malgré un nombre de catégories définies restreindre l’espace de recherche, mais aussi d’obtenir des
plus faible, offre des définitions plus simples en n’incluant règles plus faciles à interpréter. Dans notre cas, n’autori-
pas les attributs qui ne participent pas pleinement à la règle. ser qu’une catégorie par règle serait une contrainte perti-
Par la suite, plusieurs directions de recherche sont envisa- nente. Nous pouvons également étendre l’expressivité des
gées, au niveau de la préparation des données, de la fouille règles recherchées en permettant par exemple des opéra-
et de l’évaluation. teurs logiques tels que les disjonctions ou les négations.
Comme mentionné précédemment, les contextes construits Si ReReMi permet déjà d’obtenir de telles formules lo-
Turing_Award_laureates Sports_cars Smartphones French_films
Eclat ReReMi Eclat ReReMi Eclat ReReMi Eclat ReReMi
22 0 9 80 0 30 494 0 57 292 0 12
0 0 0 0
8 0 15 0 27 0 79 0
1 8 4 10
Translator Translator Translator Translator
F IGURE 6 – Règles extraites par Eclat, ReReMi et Translator pour chaque jeu de données.
Turing_Award_laureates Sports_cars Smartphones French_films
Eclat ReReMi Eclat ReReMi Eclat ReReMi Eclat ReReMi
2 1 0 3 3 0 3 1 0 65 1 1
7 17 25 6
7 1 4 0 9 0 74 0
1 1 0 0
Translator Translator Translator Translator
F IGURE 7 – Catégories définies par Eclat, ReReMi et Translator pour chaque jeu de données.
giques, et que des travaux dans ce sens existent pour les L. A. G ALÁRRAGA, C. T EFLIOUDI, K. H OSE et F. M. S U -
règles d’association, ce n’est pas le cas pour les règles de CHANEK : AMIE : association rule mining under in-
traduction. Cela implique de revoir le calcul de la longueur complete evidence in ontological knowledge bases. In
d’une règle. WWW’13, p. 413–422, 2013.
Concernant l’évaluation, il nous faudra un moyen de com-
parer plus formellement les règles entre elles, peut-être via E. G ALBRUN et P. M IETTINEN : From Black and White
l’introduction d’une notion de redondance, qui permettrait to Full Color : Extending Redescription Mining Outside
de définir une base de règles. the Boolean World. Statistical Analysis and Data Mi-
ning, 5(4):284–303, 2012.
Remerciements
B. G ANTER et R. W ILLE : Formal concept analysis - ma-
Ce travail est financé avec le support de la Direction Géné- thematical foundations. Springer, 1999.
rale de l’Armement et de la Région Lorraine. Merci à Es-
ther Galbrun pour ses conseils ainsi que Quentin Brabant M. K LEMETTINEN, H. M ANNILA, P. RONKAINEN,
et Jérémie Nevin pour leur aide à l’évaluation des règles. H. T OIVONEN et A. I. V ERKAMO : Finding interesting
rules from large sets of discovered association rules. In
Références CIKM’94, p. 401–407, 1994.
R. AGRAWAL, T. I MIELI ŃSKI et A. S WAMI : Mining asso- N. R AMAKRISHNAN, D. K UMAR, B. M ISHRA, M. P OTTS
ciation rules between sets of items in large databases. In et R. F. H ELM : Turning CARTwheels : an Alternating
ACM SIGMOD Rec., vol. 22, p. 207–216. ACM, 1993. Algorithm for Mining Redescriptions. In KDD’04, p.
266–275, 2004.
M. A LAM, A. B UZMAKOV, V. C ODOCEDO et A. NAPOLI :
Mining definitions from rdf annotations using formal B. S ERTKAYA : A survey on how description logic on-
concept analysis. In IJCAI, p. 823–829, 2015. tologies benefit from formal concept analysis. CoRR,
abs/1107.2822, 2011.
F. BAADER, D. C ALVANESE, D. M C G UINNESS,
D. NARDI et P. PATEL -S CHNEIDER, éds. The M. van L EEUWEN et E. G ALBRUN : Association Disco-
Description Logic Handbook. Cambridge University very in Two-View Data. TKDE, 27(12):3190–3202, déc.
Press, Cambridge, UK, 2003. 2015.
M. J. Z AKI : Scalable algorithms for association mining.
S. F ERRÉ et P. C ELLIER : Graph-FCA in Practice. In
TKDE, 12(3):372–390, May 2000.
Proceedings of 22nd ICCS, p. 107–121, 2016.