=Paper=
{{Paper
|id=Vol-2133/cnia-paper6
|storemode=property
|title=Découverte de cardinalité maximale contextuelle dans les bases de connaissances(Mining contextual maximum cardinality in knowledge bases)
|pdfUrl=https://ceur-ws.org/Vol-2133/cnia-paper6.pdf
|volume=Vol-2133
|dblpUrl=https://dblp.org/rec/conf/rjcia/AlyDGMS18
}}
==Découverte de cardinalité maximale contextuelle dans les bases de connaissances(Mining contextual maximum cardinality in knowledge bases)==
https://ceur-ws.org/Vol-2133/cnia-paper6.pdf
Découverte de cardinalité maximale contextuelle dans les bases de connaissances
E. A. Sidi Aly1,2 M. L. Diakité1 A. Giacometti2 B. Markhoff2 A. Soulet2
1
Département Mathématiques et Informatique - Université de Nouakchott Al Aasriya (Mauritanie)
2
Laboratoire d’Informatique Fondamentale et Appliquée de Tours - Université de Tours (France)
arbi2fr@yahoo.fr, diakite@una.mr, prenom.nom@univ-tours.fr
3 juillet 2018
Résumé Keywords
Les bases de connaissances du web sémantique doivent Cardinality discovery, knowledge base.
être enrichies par des informations utiles aux applica-
tions de fouille, de recherche d’information, de question- 1 Introduction
réponse, etc. En effet, leur génération à partir de plate- Nous considérons de grandes bases de connaissances du
formes collaboratives ou d’intégration de sources diverses web, construites par des algorithmes de recherche d’infor-
produit des manques d’information, d’une part, et des er- mation à partir de plateformes collaboratives (e.g., DBpe-
reurs ou incohérences d’autre part. Heureusement, leur vo- dia [2]) et/ou d’intégration de sources diverses. Pour en
lume important permet d’en induire des contraintes vrai- désigner les éléments, nous utilisons les termes concept,
semblables. Tel est l’objet de l’algorithme présenté dans rôle et individu au sens des logiques de description.
cet article, qui extrait des règles de cardinalité maximale à
Contexte et motivations En représentation des connais-
partir d’une base de connaissances. L’enrichissement de la
sances les restrictions numériques précisant le nombre
base par ces nouveaux axiomes permet d’y trouver plus de
d’occurrences d’un rôle sont particulièrement utiles [3].
faits, positifs ou négatifs, ce qui rend plus pertinentes les
Parmi elles, les contraintes de cardinalité maximale per-
évaluations de la qualité des règles générées par des algo-
mettent de savoir quand toutes les assertions sur un rôle
rithmes de fouille classiques. Les expérimentations menées
donné pour un individu donné existent dans la base. C’est
sur une partie de DBpedia et sur l’ensemble d’une base de
utile pour qualifier les réponses aux requêtes sur une base
connaissances numismatiques démontrent la faisabilité de
de connaissances, c’est-à-dire les compléter par des infor-
l’approche et la pertinence des contraintes extraites.
mations précises sur leur qualité en terme de rappel par
Mots Clef rapport à une réalité [13, 17].
Il est illusoire d’espérer des ajouts manuels de telles
Découverte de cardinalité, base de connaissances. contraintes d’intégrité dans de grandes bases de connais-
Abstract sances 1 , qui soient correctes et suffisantes. Aussi, des tech-
niques de type rétro-ingénierie [14] applicables sur ces
The big semantic web knowledge bases have to be enri- grandes bases doivent être considérées, afin de les re-
ched for applications in data mining, information retrie- chercher systématiquement. Des propositions existent déjà
val, question answering, etc. Indeed, their generation from pour trouver des contraintes de clés [1, 11, 15, 16] dans
collaborative platforms or integration of various sources des données RDF. Mais à notre connaissance, il n’y a pas
leads to lack of information on the one hand, and inconsis- encore de travaux sur l’extraction de contraintes de cardi-
tencies on the other hand. Fortunately, their volume makes nalité maximale dans les bases de connaissances.
it possible to induce probable constraints. This is the aim
Challenge L’extraction de contraintes de cardinalité à
of the algorithm presented in this article, which extracts
partir des données existantes est connue comme un
maximum cardinality rules from a knowledge base. Adding
problème important de la rétro-ingéniérie des bases de
these new axioms to the knowledge base allows applica-
données relationnelles [14, 18]. Par rapport au cadre des
tions to find more facts, positive or negative, which makes
bases de données traditionnelles, ce problème est bien plus
more relevant the evaluations of the quality of the rules ge-
complexe pour les bases de connaissances du web.
nerated by traditional datamining algorithms. Experiments
Tout d’abord, ces bases de connaissances contiennent
conducted on part of DBpedia and on an entire numismatic
généralement des données incohérentes, que ce soient
knowledge base demonstrate the feasibility of the approach
and the relevance of the discovered contextual constraints. 1. [5] présente néanmoins un outil pour le faire sur Wikidata.
des assertions fausses ou des assertions dupliquées. De ce résultant d’un processus d’intégration de 5 bases de
fait, la cardinalité maximale observée pour un rôle donné données numismatiques [6].
ne saurait être considérée comme sa cardinalité maxi-
male la plus vraisemblable. Par exemple, il est vraisem- dbo:Person / dbo:birthYear
blable qu’une personne ait au plus une année de nais- i ni τi τei
5 1 1.0 0.0
sance et deux parents. Pourtant dans DBpedia (voir les
4 2 0.667 0.0
rôles dbo:birthYear et dbo:parent dans la table 1), 3 4 0.571 0.0
certaines personnes ont 5 années de naissance ou 6 pa- 2 91 0.928 0.775
rents ! Ces quelques assertions incohérentes ne doivent pas 1 159841 0.999 0.996
influencer la caractérisation des cardinalités maximales. dbo:Person / dbo:parent
Ensuite, ces bases de connaissances sont souvent in- i ni τi τei
complètes pour un rôle donné. Pour cette raison, la car- 6 1 1.0 0.0
dinalité la plus observée n’est pas forcément la cardinalité 4 9 0.9 0.420
maximale. Typiquement, la plupart des personnes décrites 3 75 0.882 0.718
dans DBpedia n’ont qu’un seul parent renseigné (voir le 2 9392 0.991 0.975
rôle dbo:parent dans la table 1). Toutefois, certaines en 1 10643 0.529 0.518
ont plus et ceci n’est pas une anomalie, il faut en tenir dbo:Person / dbo:nationality
i ni τi τei
compte : la cardinalité maximale du rôle dbo:parent pour
8 2 1,000 0,000
une personne ne doit pas être sous-estimée (ici à 1) au vu
6 1 0,333 0,000
de l’ensemble des cardinalités observées. 5 1 0,250 0,000
Enfin, des travaux récents sur la détection de contraintes 4 13 0,765 0,397
de clefs dans les bases de connaissances [16] ont montré 3 167 0,908 0,796
que de nombreuses contraintes intéressantes ne sont va- 2 3 263 0,947 0,921
lides que sur une partie d’une base de connaissances. Par 1 123 386 0,973 0,969
exemple, s’il semble difficile de déterminer une cardinalité
maximale pour le nombre de nationalités d’une personne TABLE 1 – Distributions de cardinalités de rôles de per-
en général, comme certains états limitent le nombre de na- sonnes dans DBpedia (i est la cardinalité ; ni le nombre
tionalités à 1 il est possible de détecter cette limite pour les d’individus étant i fois sujets du rôle considéré ; τi est une
ressortissants de tels états. Il est donc essentiel non seule- estimation fréquentielle du taux de cohérence réel ; τei en est
ment de détecter des cardinalités maximales, mais aussi une version corrigée s’appuyant sur la borne de Hoeffding)
d’identifier les contextes dans lesquels de telles contraintes
peuvent être détectées.
Contributions Etant donnée une distribution de cardina- 2 Etat de l’art
lités (ni )i≥1 observées dans une base de connaissances K Notre algorithme vise à augmenter la connaissance sur
pour un rôle R dans un contexte C, nous commençons par les données contenues dans les grandes bases de connais-
proposer une méthode de calcul d’une cardinalité maxi- sances du web, en termes de validité comme en termes de
male vraisemblable, en calculant une estimation du taux complétude par rapport à la réalité représentée. Il permet
de cohérence réel que la cardinalité i soit maximale. Cette d’enrichir la partie schéma (TBox en logiques de descrip-
estimation, notée τi , est calculée en prenant en compte tous tion) de ces bases pour mieux utiliser leur partie données
les individus pour lesquels le rôle R est complet. Son cal- (ABox). Plusieurs travaux récents vont dans ce sens [1, 11,
cul est détaillé et justifié dans la section 4.2. Pour être sta- 15, 16, 10] et d’autres s’en rapprochent [7, 13, 17] mais
tistiquement valide, une version corrigée de cette estima- ciblent des individus (assertions de la ABox) plutôt que des
tion du taux de cohérence, notée τei , est également intro- concepts (assertions de la TBox).
duite. Des exemples d’estimations de taux cohérence, cor- Dans [17], une technique de fouille de textes de Wikipe-
rigés ou non, sont représentés dans la table 1 pour les rôles dia pour ajouter des précisions sur le degré de complétude
dbo:birthYear, dbo:parent et dbo:nationality en des informations dans Wikidata est décrite. Notre proposi-
considérant le concept dbo:Person comme contexte. tion est complémentaire puisque notre algorithme traite les
Etant donnée une arborescence de concepts constituant données déjà contenues dans les bases de connaissances.
les contextes candidats, nous proposons ensuite un algo- Mais surtout, il ne caractérise pas les rôles par rapport à des
rithme d’exploration systématique d’un ensemble de individus précis mais à des concepts définis (au sens des
contraintes contextuelles pour les rôles desquels nous logiques de description). Les auteurs de [7, 13] présentent
recherchons les cardinalités maximales. Cet algorithme, également des propositions pour déterminer quand est-ce
décrit en section 4.3, vise à limiter les calculs en élaguant qu’un rôle particulier (comme dbo:parent) manque pour
un maximum des contraintes possibles. un individu particulier (comme Obama). Plus générale,
Enfin nous présentons et analysons des résultats notre proposition consiste à calculer les cardinalités maxi-
expérimentaux obtenus sur une base de connaissances males vraisemblables des rôles relativement à des concepts
définissant des contextes : elle enrichit donc la partie 3 Préliminaires
schéma.
3.1 Bases de connaissances
Ce sont des clés au sens des bases de données, donc des Dans ce papier, nous considérons des bases de connais-
contraintes au niveau du schéma, qui sont recherchées sances K = (T , A) où T et A sont respectivement les
dans [1, 11, 15, 16]. L’idée est de trouver des axiomes indi- TBox et ABox de K. T désigne un ensemble d’axiomes
quant que tout individu d’un certain concept doit posséder terminologiques définis à partir des concepts et rôles ato-
une valeur unique pour un rôlé donné R. Cela constitue miques de K, alors que A désigne l’ensemble des asser-
donc une cardinalité maximale du rôle R pour le concept tions ou faits de K. Plus précisément, A contient des ex-
C. Egalement très proches de nos travaux, dans [10], les pressions de la forme C(a) et R(a, b) où C est un concept,
auteurs proposent de déterminer automatiquement quels R est un rôle, et a, b sont des individus.
rôles devraient être obligatoirement renseignés pour un Dans le cas de la base de connaissances DBpedia,
concept donné de la base de connaissances. Pour cela dbo:Country et dbo:Person sont des exemples
ils comparent la densité du rôle pour les individus de ce de concepts atomiques et dbo:nationality
concept par rapport à sa densité pour les individus d’autres est un exemple de rôle atomique de sa TBox.
concepts, qui lui sont liés dans la hiérarchie des concepts. Par ailleurs, dbo:Country(M auritania) et
Notre proposition s’appuie sur d’autres critères pour calcu- dbo:nationality(Arby, M auritania) sont des
ler la cardinalité maximale du rôle pour un contexte (notion exemples de faits ou assertions de sa ABox. Le premier
plus générale que seulement les concepts de la base). Elle indique que M auritania est un pays, alors que le second
peut être adaptée au calcul de la cardinalité minimale, au- indique que Arby est de nationalité mauritanienne.
quel cas elle trouverait, entre autres, quels rôles ont une car- Les logiques de description permettent de définir des
dinalité minimale au moins supérieure à 1 pour un concept axiomes pour enrichir la TBox d’une base de connais-
donné, soit plus d’information que seulement savoir si le sances. Par exemple, la relation d’inclusion v permet
rôle devrait exister ou pas. d’indiquer qu’un concept C1 est inclus dans un concept
C2 , noté C1 v C2 . Plus précisément, une base de
Ces différentes sortes d’information supplémentaire sur la connaissances K implique l’axiome C1 v C2 si pour
qualité des données de la base de connaissances, en termes toute interprétation I de K, C1I ⊆ C2I . Par exemple,
de validité comme en termes de complétude par rapport à la les axiomes ∃dbo:nationality.> v dbo:Person et
réalité représentée, permettent d’améliorer le fonctionne- ∃dbo:nationality− .> v dbo:Country indiquent res-
ment des applications qui les utilisent, en réduisant le flou pectivement que le domaine du rôle dbo:nationality
de l’hypothèse du monde ouvert. Ainsi pour améliorer la est inclus dans le concept dbo:Person, et que le co-
mesure de qualité de règles issues de processus de fouille domaine du rôle dbo:nationality est inclus dans le
dans les bases de connaissances du web sémantique, une concept dbo:Country.
hypothèse de complétude partielle est définie et utilisée
dans [8, 7] : cette règle stipule que si un rôle est renseigné
3.2 Contraintes contextuelles de cardinalité
pour un individu, alors les informations concernant ce rôle maximale
pour cet individu sont considérées complètes. Si on peut Soit R un rôle d’une base de connaissances K = (T , A).
noter que cette hypothèse est contredite par l’observation On considère généralement que ce rôle satisfait dans K une
de DBpedia (voir l’extrait fourni dans la table 1), elle rend contrainte de cardinalité maximale M si pour tout sujet s,
tout de même plus précis le calcul de la confiance associée le nombre d’objets o tels que R(s, o) soit présent dans K
aux résultats de fouille. Ces auteurs ont démontré le be- (directement présent dans sa ABox A ou inférable à partir
soin pour la fouille de ce qu’ils appellent des oracles de de ses TBox T et ABox A) est inférieur ou égal à M .
complétude, et proposé un certain nombre d’heuristiques En logique de description, une telle contrainte peut se
pour en définir, comme par exemple la popularité des in- représenter par un axiome de la forme sqsubseteq en utili-
dividus (qui augmente les chances que les faits renseignés sant le constructeur de restriction de cardinalité (≤ M R).
sur eux soient complets), etc. En effet, en terme logique, une base de connaissances K
implique l’axiome ∃R.> v (≤ M R) si pour toute in-
La fouille de données est loin d’être le seul domaine terprétation I de K, {x : (∃y)((x, y) ∈ RI )} ⊆ {x :
qui bénéficie d’axiomes tels que ceux découverts par #{y : (x, y) ∈ RI } ≤ M } où #E représente la cardina-
notre algorithme, par exemple, s’appuyant sur des tra- lité d’un ensemble E.
vaux de référence en base de données, les auteurs de [4, Plus précisément, dans ce papier, nous cherchons à identi-
12] et plus récemment [9] proposent de caractériser les fier des contraintes contextuelles de cardinalité maximale,
réponses obtenues par des requêtes, en fonction des infor- à savoir des contraintes qui ne sont pas nécessairement
mations connues concernant le degré de complétude de la vérifiées par tous les sujets s d’un rôle R, mais par tous les
base de connaissances interrogée, par rapport à la réalité sujets instances d’un concept, qu’il soit atomique ou com-
représentée. posé, déjà défini dans K ou pas. Cette notion est introduite
formellement dans la définition suivante : Le problème traité dans ce papier est alors le suivant :
étant donnés une base de connaissances K, un rôle R
Définition 3.1 (Contrainte contextuelle). Etant donnés un et une hiérarchie de concepts (C, v), nous cherchons
rôle R, un concept atomique ou défini C et un entier M , à découvrir l’ensemble des contraintes contextuelles de
une contrainte contextuelle de cardinalité maximale définie cardinalité maximale de la forme C v (≤ M R) avec
sur R est une expression γ de la forme : C v (≤ M R). C ∈ C, qui soient satisfaites sur K et minimales dans C.
Le concept C est appelé le contexte de la contrainte γ. La
contrainte γ est satisfaite dans une base de connaissances En pratique, une base de connaissances telle que DBpedia
K si et seulement si pour toute interprétation I de K, C I ⊆ est très incomplète (par exemple, de nombreuses personnes
{x : #{y : (x, y) ∈ RI } ≤ M }. ont seulement un parent), et elle comporte de nombreuses
incohérences (par exemple, des personnes peuvent avoir
Par exemple, la contrainte contextuelle jusqu’à 5 parents). Pour ces raisons, étant donnée une base
(dbo:Person) v (≤ 5 dbo:nationality) in- de connaissances K, il n’est pas pertinent de chercher à ex-
dique que toutes les personnes ont au plus 5 traire des contraintes de cardinalité qui soient parfaitement
nationalités, alors que la contrainte contextuelle satisfaites dans K, mais les contraintes :
(dbo:Person u ∃dbo:nationality.{China}) v — les plus probables et suffisamment probables par
(≤ 1 dbo:nationality) indique que toutes les per- rapport à un seuil donné, de manière à prendre en
sonnes de nationalité chinoise ont au plus une nationalité. compte et tolérer les incohérences, et
— suffisamment certaines par rapport à un degré de
Dans ce travail, on cherche à extraire des contraintes confiance, pour ne pas extraire des contraintes qui
contextuelles de cardinalité maximale qui soient les plus soient remises en cause régulièrement par l’ajout de
générales possibles. nouveaux faits dans la base de connaissances.
Nous détaillons dans la section suivante comment évaluer
Définition 3.2 (Contrainte contextuelle minimale). Soient
la probabilité qu’une contrainte soit satisfaite dans une base
deux contraintes contextuelles de cardinalité maximale γ1 :
de connaissances K et comment mesurer la certitude que
C1 v (≤ M1 R) et γ2 : C2 v (≤ M2 R) définies sur R.
cette contrainte soit réelle.
La contrainte γ1 est dite plus générale que la contrainte
γ2 si C2 @ C1 et M1 ≤ M2 . Etant donné un ensemble de 4 Extraction de contraintes contex-
contraintes Γ définies sur R, une contrainte γ1 ∈ Γ est dite
minimale dans Γ s’il n’existe aucune contrainte γ2 dans Γ tuelles de cardinalité maximale
plus générale que γ1 . Pour résoudre le problème énoncé précédemment, nous
commençons par le reformuler en introduisant la notion de
Par exemple, la contrainte contextuelle
taux de cohérence dans la section 4.1, puis nous décrivons
(dbo:Person) v (≤ 2 dbo:nationality) est
dans la section 4.2 comment détecter une cardinalité maxi-
plus générale que la contrainte contextuelle
male pour un rôle R dans un contexte C. Ensuite, étant
(dbo:Person u ∃dbo:nationality.{China}) v
donné un ensemble de contextes candidats C, nous mon-
(≤ 5 dbo:nationality) car (dbo:Personu
trons dans la section 4.3 comment explorer efficacement
∃dbo:nationality.{China}) v dbo:Person) et
l’ensemble des contraintes contextuelles possibles.
2 ≤ 5.
4.1 Taux de cohérence
La notion de minimalité a pour objectif de ne pas extraire
de contraintes contextuelles qui soient redondantes. Intui- Etant donnée une base de connaissances K = (T , A),
tivement, considérons les deux contraintes γ1 et γ2 in- supposons que i soit la cardinalité maximale du rôle R
troduites dans la définition précédente, et supposons que dans le contexte C. Soit s un individu de C dans K, com-
γ1 soit plus générale que γ2 . Etant donnée une base de plet pour le rôle R dans K (dans le sens où tous les faits
connaissances K dans laquelle les contraintes γ1 et γ2 R(s, o) possibles représentant le monde réel sont dans A
sont satisfaites, soit une instance s de C2 dans K. D’après ou inférables). Dans le cas où il existe exactement i faits
γ2 , nous savons que pour toute interprétation I de K, dans K de la forme R(s, o), cela renforce l’hypothèse que
#{o : (s, o) ∈ RI } ≤ M2 . Mais comme γ1 est plus i soit la cardinalité maximale de R dans le contexte C. In-
générale que γ2 , nous savons par définition que C2 v C1 . versement, s’il existe plus de i faits dans K de la forme
Il en découle que s est aussi une instance de C1 dans R(s, o), cela affaiblit l’hypothèse que i soit la cardinalité
K, et d’après γ1 , que pour tout interprétation I de K, maximale de R dans le contexte C. Ainsi dans le tableau 1,
#{o : (s, o) ∈ RI } ≤ M1 , ce qui est une contrainte plus pour la classe dbo:Person, les individus comportant au
forte que #{o : (s, o) ∈ RI } ≤ M2 . En effet, par moins 3 assertions pour le rôle dbo:parent affaiblissent
définition de la minimalité, nous savons que M1 ≤ M2 . l’hypothèse que la cardinalité maximale soit 2 mais ils res-
Par rapport à la contrainte γ1 , la contrainte γ2 est donc tent peu nombreux au regard des 9 392 individus qui ont
inutile car redondante, i.e. elle ne permet pas de déduire exactement 2 parents.
d’information supplémentaire. En suivant ce raisonnement, nous introduisons la notion de
taux de cohérence pour évaluer si une cardinalité i pour le cohérence réel τi (K∗ ) de la cardinalité i pour le rôle R
rôle R dans le contexte C a des chances d’être maximale : dans le contexte C est supérieur à τei (K) :
Définition 4.1 (Taux de cohérence). Etant donnée une τi (K∗ ) ≥ τei (K)
base de connaissances K, le taux de cohérence de la car-
dinalité i pour le rôle R dans le contexte C est le ratio : où τei (K) est le taux de cohérence pessimiste défini par :
( s )
nC,R ni log(1/δ)
τiC,R (K) = i τei (K) = max − ;0
nC,R
≥i
n≥i 2n≥i
Cette propriété nous munit d’un outil efficace pour ap-
où nC,R
i (resp. nC,R
≥i ) représente le nombre de sujets s tels proximer le taux de cohérence réel. Il survient alors la dif-
que i faits R(s, o) (resp. i faits ou plus) appartiennent à K
ficulté de choisir la cardinalité maximale une fois que l’on
dans le contexte C.
dispose pour chaque cardinalité i du taux de cohérence pes-
Par exemple, dans le tableau 1, n≥2 dbo:Person,dbo:parent
est simiste τei (K) (pour un rôle R dans le contexte C).
égal à 9477 (9477 = 9392+75+9+1). De cette manière, le Plus précisément, étant donnés un seuil minimal de
taux de cohérence τ2dbo:Person,dbo:parent (K) est de 0,991 cohérence minτ et un niveau de confiance 1 − δ, nous
(i.e., 9392/9477). Par la suite, quand le contexte et la re- considérons que M est la cardinalité maximale de R
lation sont clairs, nous pouvons les omettre dans les no- dans le contexte C si et seulement si τeM ≥ minτ et
tations. Dans ce cas, ni et τi désignent respectivement les M = arg maxi≥1 τei (K).
termes nC,R et τiC,R . Quelques exemples d’estimations τei et de détection de
i
Maintenant nous allons formaliser le lien entre le taux de cardinalités maximales contextuelles sont donnés dans la
cohérence et la notion de contrainte maximale. Originel- table 1. Dans les 3 exemples, on a considéré dbo:Person
lement introduit dans [13], K∗ = (T ∗ , A∗ ) désigne une comme contexte, et on a cherché à détecter la cardinalité
hypothétique base de connaissances idéale qui contiendrait maximale contextuelle de trois rôles : dbo:birthYear,
tous les axiomes et toutes les assertions du monde réel. dbo:parent et dbo:nationality. Intuitivement, pour
Comme K∗ est correcte et complète, le taux de cohérence les deux premiers rôles, on souhaiterait détecter des car-
au sein de K∗ , noté τM C,R
(K∗ ), est égal à 1 si et seulement dinalités maximales respectives de 1 et 2. Pour un niveau
si C v (≤ M R) appartient à T ∗ . de confiance 1 − δ = 99% et un seuil minτ = 0.97, on
constate que les cardinalités maximales supposées sont ef-
En pratique, le taux de cohérence mesuré dans une base
fectivement détectées (cf. lignes en gras dans la table 1).
de connaissances est différent du taux de cohérence réel :
De manière intéressante, avec ces mêmes seuils, aucune
τi (K) 6= τi (K∗ ). Par exemple, le taux de cohérence τ2 (K)
cardinalité n’est détectée pour dbo:nationality.
pour le rôle dbo:parent du tableau 1 est égal à 0,991 alors
que le taux de cohérence réel est égal à 1. Plus grave, on a 4.3 Exploration de l’espace de recherche
τ6dbo:Person,dbo:parent (K) = 1 ! Le taux de cohérence sur
Etant donnés une base de connaissances K, un rôle R, une
K est donc une estimation peu fiable du taux de cohérence
arborescence de concepts (C, v), un degré de confiance δ
réel sur K∗ .
et un seuil minimal de cohérence minτ , nous cherchons à
4.2 Détection d’une contrainte découvrir l’ensemble des contraintes contextuelles de car-
dinalité maximale de la forme C v (≤ M R) avec C ∈ C,
L’estimation τi (K) de τi (K∗ ) doit être corrigée pour être qui soient minimales et suffisamment certaines sur K. En
statistiquement valide. Pour ce faire, nous proposons d’uti- pratique, notons que l’arborescence (C, v) peut être une
liser l’inégalité de Hoeffding qui a l’avantage d’être vraie arborescence déjà existante dans la TBox de la base de
pour toute distribution. En terme de probabilité, si X connaissances, ou une arborescence construite dans une
est une variable aléatoire indiquant pour un sujet s tiré phase préalable de préparation des données (voir la sec-
aléatoirement, le nombre de faits R(s, o) appartenant à K, tion 5.1).
alors τi est une estimation fréquentielle de la probabilité Dans un tel cadre, il y a potentiellement un très grand
conditionnelle P (X = i / X ≥ i). Etant donné un ni- nombre de contraintes contextuelles à considérer, évaluer
veau de confiance 1 − δ, l’inégalité de Hoeffding stipule et comparer. Néanmoins, il est possible de réduire la taille
∗
que τi (Kq ) est compris entre τi (K) − i et τi (K) + i de l’espace de recherche à explorer en se basant sur les
où i = log(1/δ)
2n≥i . Dans ce contexte, afin de prendre des propriétés 4.2 et 4.3 énoncées ci-après. Tout d’abord, la
décisions les plus sûres, nous proposons d’utiliser la borne propriété 4.2 montre qu’une contrainte C v (≤ M R)
inférieure de l’intervalle de confiance [τi − i , τi + i ]. Plus ne peut pas être suffisamment certaine si le contexte C
formellement, on a la propriété suivante : contient trop peu d’individus dans K, car alors l’inter-
valle de confiance du taux de cohérence calculé grâce à
Propriété 4.1 (Minoration). Etant données une base de l’inégalité de Hoeffding est très large et sa borne inférieure
connaissances K et une confiance 1 − δ, le taux de ne peut être supérieure au seuil minτ imposé.
Propriété 4.2 (Nombre minimal d’observations). Etant Algorithm 1 C3M
donnés une base de connaissances K, une contrainte Input: Une base de connaissances K, un rôle R, un contexte C,
contextuelle de cardinalité maximale C v (≤ M R) et un entier M , un niveau de confiance δ et un seuil minimal de
un seuil minτ , le taux de cohérence τeM (K) que M soit la support minτ
cardinalité maximale de R dans C ne peut être supérieur à Output: Un ensemble Γ de contraintes contextuelles de cardina-
log(1/δ) lité maximale
minτ que si |C| ≥ 2(1−min τ)
2. log(1/δ) C,R
1: α := 2(1−min )2 et n≥0 := |C|
τ
C,R
Par ailleurs, supposons qu’une contrainte γ définie par 2: if (n≥0 < α) then return ∅
C v (≤ M R) avec M = 1 ait été détectée comme 3: Γ := ∅ et imax := arg maxi∈N {ni
C,R
> 0}
suffisamment certaine au cours de l’exploration. Alors, 4: for all i ∈ [1..min{M,
( imax }] do )
d’après la propriété 4.3, il n’est pas nécessaire d’explorer C,R
ni
r
log(1/δ)
les contraintes γ 0 définies par C 0 v (≤ M 0 R) où C 0 est 5: τei := max C,R − C,R ;0
n≥i 2n≥i
plus spécifique que C. Cette propriété découle directement 6: end for
de la définition 3.2 de la minimalité. 7: iM := arg maxi∈[1..min{M,imax }] {e τi }
τiM < minτ ) then iM = ∞
8: if (e
Propriété 4.3 (Contrainte minimale). Soient une base de
9: if (iM < M ) then Γ := {C v (≤ iM R)}
connaissances K et une contrainte contextuelle de cardi- 10: if (iM > 1) then
nalité maximale γ définie par C v (≤ M R) avec M = 1. 11: for all C 0 ∈ subClassOf (C) do
Toute contrainte γ 0 définie par C 0 v (≤ M 0 R) avec 12: Γ := Γ ∪ C3M (K, R, C 0 , iM , δ,minτ )
C 0 v C et M 0 ≥ 1 ne peut être minimale. 13: end for
14: end if
L’algorithme 1 détaille notre fonction récursive d’explo- 15: return Γ
ration, la fonction C3M (pour Contextual Cardinality
Constraint Mining). Cette fonction prend en entrée une
base de connaissances, un rôle à explorer, un contexte cou- représente l’entier maximal pour lequel il existe au moins
rant, une cardinalité maximale courante (M = ∞ si au- un sujet s tel que imax faits R(s, o) appartiennent à la base
cune cardinalité maximale n’a encore pu être détectée), et de connaissances K, i.e. imax = arg maxi∈N {n>,R > 0}.
i
enfin, des seuils δ et minτ . Le démarrage de l’explora-
tion d’une arborescence de racine > se fait en exécutant 5 Expérimentations
la fonction C3M (K, R, >, ∞, δ, minτ ).
Pour commencer, la fonction C3M détermine si le nombre Outre les requêtes sur DBpedia (dont nous montrons des
d’individus est suffisant dans le contexte C. Si ce n’est pas échantillons de réponses en table 1), qui ont été utilisées
le cas, elle arrête l’exploration à la ligne 2 conformément pour mettre au point la définition du taux de cohérence,
à la propriété 4.2. Sinon, le taux de cohérence τei est cal- nous avons expérimenté l’algorithme 1 sur un jeu de
culé pour chaque cardinalité i (lignes 4 à 6) et la ligne données mis à notre disposition par les auteurs de [6].
7 retient la cardinalité maximale la plus probable. Si le 5.1 Données et protocole
taux de cohérence correspondant n’est pas supérieur au
seuil minτ , alors cela signifie qu’aucune cardinalité maxi- Le jeu de données utilisé porte sur le domaine numisma-
male n’a pu être détectée à ce niveau et iM est fixé ligne tique, il est le résultat d’un processus d’intégration mené
8 à ∞. Ensuite, si la cardinalité maximale détectée iM dans le cadre du projet européen ARIADNE 2 . Ses auteurs
est strictement inférieure à M (la cardinalité maximale ont utilisé le CIDOC-CRM 3 pour intégrer les contenus de
détectée au niveau précédent), alors on dispose d’une nou- 5 ressources construites par des institutions de différents
velle contrainte minimale de cardinalité maximale iM et on pays européens. Il contient 3 123 998 triplets, dont les
l’ajoute à Γ, l’ensemble des contraintes recherchées. Fina- définitions de 114 classes et 373 rôles ou propriétés du
lement, conformément à la propriété 4.3, si iM est égale CIDOC-CRM et d’ARIADNE. Il est stocké et interrogé
à 1, il n’est pas nécessaire de poursuivre l’exploration en avec le triplestore Blazegraph (v2.1.4), sur une machine
parcourant les contextes plus spécifiques de C. Sinon, la virtuelle sous Linux avec 32 GB de mémoire virtuelle,
fonction C3M est appelée récursivement à la ligne 12 pour sur un serveur ayant pour processeur un Dual Intel Xeon
tous les C 0 qui sont des sous-concepts directs de C. E5620 4 coeurs. L’algorithme 1 est implémenté en Java et
Dans notre implémentation de la fonction C3M , nous utilise la bibliothèque de programmation pour RDF Jena 4 .
avons appliqué une approche client-serveur où les distribu- La base porte sur des pièces de monnaies mais, par choix
tions de cardinalité nC,Ri sont calculées par interrogation des intégrateurs, il n’existe pas de classe Coin. Les in-
en SPARQL d’une base de connaissances localisée sur un dividus correspondant à des pièces sont des instances de
serveur. Dans un tel cadre, la complexité de notre méthode E22 Man Made Object caractérisées par certains URIs
en nombre de requêtes sur le serveur est en O(|C|) où |C| (ex. ) comme va-
représente le nombre de concepts dans l’arborescence C 2. http://ariadne-infrastructure.eu/
explorée. Dans le pire des cas, côté client, la complexité 3. http://www.cidoc-crm.org/
en nombre d’opérations est en O(|C| × imax ) où imax 4. http://jena.apache.org
leur objet de certains rôles (ex. P2 has type). Plusieurs Niveau dans l’arborescence
rôles et plusieurs URIs sont utilisés pour cela, aussi nous 0 1 2 3 Total
M > Ci Cij Cij,k
avons décidé de construire notre propre arborescence d’ex-
ploration de la façon suivante : 1 60 28 10 222 320
2 3 6 9 90 108
Au premier niveau, notre arborescence contient tous les
3 0 7 14 92 113
concepts Ci de la base, soit 114 concepts (i ∈ [1..114]). 4 1 0 8 20 29
Tous ces concepts sont des sous-concepts du concept ra- 5 1 0 0 16 17
cine > au niveau zéro, i.e. pour tout i, nous avons Ci v >. 6 0 0 0 8 8
Au deuxième niveau notre arborescence contient tous les Total 65 41 41 448 595
concepts Cij définis par Cij := Ci u (∃Rj .>) où Ci
(i ∈ [1..114]) et Rj (j ∈ [1..373]) sont respectivement des TABLE 2 – Répartition par niveau et cardinalité maximale
concepts et rôles de la base. A ce niveau, 42 522 concepts M des contraintes minimales détectées
Cij sont ainsi définis. Enfin, au troisième niveau, notre
arborescence contient tous les concepts Cij,k définis par
Cij,k := Ci u (∃Rj .{ak }) où Ci (i ∈ [1..114]) et Rj tuelles possibles, notre algorithme a détecté au total 887
(j ∈ [1..373]) sont respectivement des classes et rôles de contraintes de cardinalité maximale, 595 d’entre elles étant
la base, et ak est un individu du co-domaine de Rj , i.e. des contraintes minimales. Sur cet exemple, le critère de
ak ∈ (∃Rj−1 .>). Grâce à ce dernier niveau, il est possible minimalité permet donc de réduire de près de 67% le
de considérer des contextes à la manière de notre exemple nombre de contraintes retournées. On constate que les
jouet où dbo:Person u ∃dbo:nationality.{China}. contraintes les plus nombreuses sont des cardinalités maxi-
Notons finalement que pour tout i, j, k, nous avons Cij,k v males avec M = 1, ce qui correspond à des contraintes
Cij v Ci . Globalement, cette arborescence comporte où pour un rôle donné R, tout sujet s est en relation
3 160 357 concepts, donc pour les 373 rôles de la avec au plus un objet o. Néanmoins de très nombreuses
base de connaissances cela représente plus d’un mil- contraintes sont trouvées avec des cardinalités maximales
liard de contraintes contextuelles possibles (exactement M ∈ {2, 3} (37% des contraintes minimales détectées). On
1 178 813 161 contraintes). Néanmoins, comme nous note également que si des contraintes de cardinalités maxi-
le verrons dans la section suivante, l’utilisation des pro- males sont détectées dès le niveau 0 (65 contraintes avec
priétés 4.2 et 4.3 permet d’élaguer une grande partie de un contexte C ≡ >), la recherche de contraintes contex-
l’espace de recherche. tuelles est particulièrement pertinente. Il faut en effet noter
que les contraintes les plus nombreuses sont trouvées au
5.2 Résultats niveau 3 (75% des contraintes détectées), sachant que par
Tous les résultats présentés dans cette section ont été obte- construction de notre arborescence, c’est à ce niveau que
nus avec un seuil minimal de confiance 1 − δ = 0, 99% sont caractérisées les pièces de monnaie.
(pour des contraintes les plus certaines possibles) et un
Analyse qualitative. Tout d’abord, dès le niveau 0, notre
seuil minimal de cohérence minτ = 0, 95 (pour des
méthode permet de retrouver des contraintes fonction-
contraintes suffisamment probables). Ce seuil a été défini
nelles attendues, par exemple, pour les 3 rôles du CIDOC-
expérimentalement. Sur des bases de connaissances de
CRM P1 is identified by, P52 has current owner
plus grande taille comme DBpedia, un seuil plus élevé
et P50 has current keeper, indiquant que si un su-
est préférable. Néanmoins, l’approche est relativement
jet décrit dans la base possède plus d’un identi-
peu sensible aux seuils (i.e., l’ensemble des contraintes
fiant, un propriétaire ou un conservateur, alors on peut
trouvées est stable).
en déduire que ces identifiants (respectivement, pro-
Analyse quantitative. Avec ces paramètres, la pro- priétaires et conservateurs) sont identiques. Concernant
priété 4.2 nous indique qu’une contrainte C v (≤ M R) le rôle P45 consists of du CIDOC-CRM (permet-
ne peut être suffisamment certaine si son contexte C tant de décrire les matériaux constitutifs d’un objet),
log(1/δ)
contient moins de α = 2(1−min τ)
2 = 922 instances. il est intéressant de noter qu’une cardinalité maxi-
Ainsi, l’utilisation de la propriété 4.2 permet de n’explo- male de 2 est détectée dès le niveau 1 pour la classe
rer que 16 641 contraintes, soit moins de 0, 002% des plus E22 Man Made Object. La base de connaissances décrit
de 1 milliard de contraintes possibles. Qui plus est, notre notamment des médailles constituées d’or et de pierre
expérience montre que la propriété 4.3 permet de réduire précieuse (telle l’agate). Pour ce même rôle, une car-
encore de 82, 5% la taille de l’espace de recherche à ex- dinalité maximale de 1 est détectée au niveau 3 pour
plorer. Au final, avec les seuils choisis notre algorithme les pièces de monnaie. Cette information est notamment
ne cherche à détecter une cardinalité maximale que pour représentée par la contrainte E22 Man Made Object u
2 909 contextes possibles, avec un temps de calcul complet ∃P2 has type.{} v
de moins de 50 minutes. (≤ 1 P45 consists of). Cette contrainte est détectée bien
La table 2 donne une vue globale et quantitative du résultat qu’à certaines pièces la relation P45 consists of asso-
de l’exploration réalisée. Sur les 2 909 contraintes contex- cie deux matériaux ; mais c’est rare (et le plus souvent il
s’agit du même matériau dans deux langues différentes). EKAW. pp. 144–153. Springer (2012)
Un même type de contrainte (avec M = 1) est trouvée [2] Auer, S., Bizer, C., Kobilarov, G., Lehmann, J., Cyganiak,
au niveau 3 pour tous les contextes décrivant des pièces, R., Ives, Z. : Dbpedia : A nucleus for a web of open data.
concernant le rôle P62 depicts (ce qui est dépeint sur In : The semantic web, pp. 722–735. Springer (2007)
l’objet). C’est raisonnable car dans le cas d’une pièce de [3] Baader, F., Sattler, U. : Expressive number restrictions in
monnaie, on trouve le plus souvent une seule représentation description logics. Journal of Logic and Computation 9(3),
figurative (sur une des deux faces de la pièce), alors qu’une 319–350 (1999)
telle contrainte n’est pas valide pour d’autres objets. [4] Darari, F., Nutt, W., Pirrò, G., Razniewski, S. : Comple-
Au passage, l’étude de l’ensemble des contraintes teness statements about rdf data sources and their use for
extraites par notre méthode a mis en évidence des re- query answering. In : ISWC. pp. 66–83. Springer Berlin
dondances dans la base, sans doute du fait des choix Heidelberg (2013)
d’intégration. Dans une phase de post-traitement, la [5] Darari, F., Razniewski, S., Prasojo, R.E., Nutt, W. : En-
connaissance d’axiomes tel que ∃P2 has type.{. . . coin} abling Fine-Grained RDF Data Completeness Assessment.
In : Web Engineering. pp. 170–187. Springer International
v ∃Thing has type Concept.{. . . moneta} pourrait
Publishing, Cham (2016)
réduire encore le nombre de contraintes extraites.
[6] Felicetti, A., Gerth, P., Meghini, C., Theodoridou, M. : In-
tegrating heterogeneous coin datasets in the context of ar-
6 Conclusion chaeological research. In : EMF-CRM@ICTPDL. pp. 13–
Nos expérimentations démontrent la faisabilité d’une ex- 27. CEUR-WS.org (2015)
ploration systématique d’une base de connaissances, à la [7] Galárraga, L., Razniewski, S., Amarilli, A., Suchanek,
recherche de contraintes contextuelles de cardinalité maxi- F.M. : Predicting completeness in knowledge bases. In :
male, grâce à l’algorithme que nous proposons dans cet ar- WSDM. pp. 375–383. ACM (2017)
ticle : dans le cas étudié, cela prend moins d’une heure pour [8] Galárraga, L.A., Teflioudi, C., Hose, K., Suchanek, F. :
une base de connaissances contenant plus de 3 millions de Amie : Association rule mining under incomplete evidence
triplets, décrits par une centaine de concepts et plus de 300 in ontological knowledge bases. In : WWW. pp. 413–422.
rôles. Les propriétés utilisées par notre algorithme font que ACM (2013)
seules 595 contraintes ont été obtenues, ce qui reste analy- [9] Galárraga, L., Hose, K., Razniewski, S. : Enabling
sable manuellement. Cela nous a permis de vérifier que ces Completeness-aware Querying in SPARQL. In : Procee-
contraintes sont bien pertinentes dans le contexte de la base dings of WebDB. pp. 19–22. ACM (2017)
étudiée. De plus, nos expérimentations démontrent l’im- [10] Lajus, J., Suchanek, F.M. : Are All People Married ? De-
portance du contexte dans cette découverte de contraintes. termining Obligatory Attributes in Knowledge Bases . In :
WWW (2018)
Il s’agit à notre connaissance de la première proposition
de calcul de contraintes contextuelles de cardinalité maxi- [11] Pernelle, N., Saı̈s, F., Symeonidou, D. : An automatic
key discovery approach for data linking. Web Semantics :
male dans une base de connaissances du web sémantique.
Science, Services and Agents on the World Wide Web 23,
Ces grandes bases de connaissances, reflet d’une intelli- 16–30 (2013)
gence collective, sont générées à partir de l’expertise li-
[12] Razniewski, S., Korn, F., Nutt, W., Srivastava, D. : Iden-
mitée de nombreux contributeurs et souffrent encore, tantôt tifying the extent of completeness of query answers over
de lacunes dans les informations, tantôt d’incohérences. partially complete databases. In : SIGMOD. pp. 561–576.
Utiliser leurs contenus courants afin de mieux caractériser ACM (2015)
les connaissances représentées est donc très utile, comme [13] Razniewski, S., Suchanek, F., Nutt, W. : But what do we ac-
montré dans l’état de l’art : cela permet aux applications tually know ? In : 5th Workshop on Automated Knowledge
qui exploitent ces grandes bases de connaissances de pro- Base Construction. pp. 40–44 (2016)
duire des résultats plus fiables. [14] Soutou, C. : Relational database reverse engineering : algo-
Nous avons donc pour perspective d’exploiter les rithms to extract cardinality constraints. Data & Knowledge
contraintes extraites pour calculer la confiance associée à Engineering 28(2), 161–207 (1998)
des règles découvertes dans la base de connaissances ainsi [15] Symeonidou, D., Armant, V., Pernelle, N., Saı̈s, F. : Sakey :
enrichie. Mais avant cela, nous travaillons sur des post- Scalable almost key discovery in RDF data. In : ISWC. pp.
traitements pour réduire encore le nombre de contraintes 33–49. Springer (2014)
présentées en résultat. Pour cela, nous explorons le poten- [16] Symeonidou, D., Galárraga, L., Pernelle, N., Saı̈s, F., Su-
tiel des raisonnements possibles sur la TBox, en particu- chanek, F. : Vickey : Mining conditional keys on knowledge
lier comment les relations de subsomption entre classes bases. In : ISWC. pp. 661–677. Springer (2017)
peuvent éliminer des redondances dans les ensembles de [17] Tanon, T.P., Stepanova, D., Razniewski, S., Mirza, P., Wei-
contraintes extraites. kum, G. : Completeness-aware rule learning from know-
ledge graphs. In : ISWC. pp. 507–525. Springer (2017)
Références [18] Yeh, D., Li, Y., Chu, W. : Extracting entity-relationship dia-
gram from a table-based legacy database. Journal of Sys-
[1] Atencia, M., David, J., Scharffe, F. : Keys and pseudo-keys
tems and Software 81(5), 764–771 (2008)
detection for web datasets cleansing and interlinking. In :