De´couverte de cardinalite´, base de connaissances.
The big semantic web knowledge bases have to be
enriched for applications in data mining, information
retrieval, question answering, etc. Indeed, their generation from
collaborative platforms or integration of various sources
leads to lack of information on the one hand, and
inconsistencies on the other hand. Fortunately, their volume makes
it possible to induce probable constraints. This is the aim
of the algorithm presented in this article, which extracts
maximum cardinality rules from a knowledge base. Adding
these new axioms to the knowledge base allows
applications to find more facts, positive or negative, which makes
more relevant the evaluations of the quality of the rules
generated by traditional datamining algorithms. Experiments
conducted on part of DBpedia and on an entire numismatic
knowledge base demonstrate the feasibility of the approach
and the relevance of the discovered contextual constraints.
Nous conside´rons de grandes bases de connaissances du
web, construites par des algorithmes de recherche
d’information a` partir de plateformes collaboratives (e.g.,
DBpedia [
Il est illusoire d’espe´rer des ajouts manuels de telles
contraintes d’inte´grite´ dans de grandes bases de
connaissances 1, qui soient correctes et suffisantes. Aussi, des
techniques de type re´tro-inge´nierie [
Enfin, des travaux re´cents sur la de´tection de contraintes
de clefs dans les bases de connaissances [
Contributions Etant donne´e une distribution de cardinalite´s (ni)i 1 observe´es dans une base de connaissances K pour un roˆle R dans un contexte C, nous commenc¸ons par proposer une me´thode de calcul d’une cardinalite´ maximale vraisemblable, en calculant une estimation du taux de cohe´rence re´el que la cardinalite´ i soit maximale. Cette estimation, note´e i, est calcule´e en prenant en compte tous les individus pour lesquels le roˆle R est complet. Son calcul est de´taille´ et justifie´ dans la section 4.2. Pour eˆtre statistiquement valide, une version corrige´e de cette estimation du taux de cohe´rence, note´e i, est e´galement introe duite. Des exemples d’estimations de taux cohe´rence, corrige´s ou non, sont repre´sente´s dans la table 1 pour les roˆles dbo:birthYear, dbo:parent et dbo:nationality en conside´rant le concept dbo:Person comme contexte. Etant donne´e une arborescence de concepts constituant les contextes candidats, nous proposons ensuite un algorithme d’exploration syste´matique d’un ensemble de contraintes contextuelles pour les roˆles desquels nous recherchons les cardinalite´s maximales. Cet algorithme, de´crit en section 4.3, vise a` limiter les calculs en e´laguant un maximum des contraintes possibles.
Enfin nous pre´sentons et analysons des re´sultats
expe´rimentaux obtenus sur une base de connaissances
re´sultant d’un processus d’inte´gration de 5 bases de
donne´es numismatiques [
Notre algorithme vise a` augmenter la connaissance sur
les donne´es contenues dans les grandes bases de
connaissances du web, en termes de validite´ comme en termes de
comple´tude par rapport a` la re´alite´ repre´sente´e. Il permet
d’enrichir la partie sche´ma (TBox en logiques de
description) de ces bases pour mieux utiliser leur partie donne´es
(ABox). Plusieurs travaux re´cents vont dans ce sens [
Dans [
Ce sont des cle´s au sens des bases de donne´es, donc des
contraintes au niveau du sche´ma, qui sont recherche´es
dans [
Ces diffe´rentes sortes d’information supple´mentaire sur la
qualite´ des donne´es de la base de connaissances, en termes
de validite´ comme en termes de comple´tude par rapport a` la
re´alite´ repre´sente´e, permettent d’ame´liorer le
fonctionnement des applications qui les utilisent, en re´duisant le flou
de l’hypothe`se du monde ouvert. Ainsi pour ame´liorer la
mesure de qualite´ de re`gles issues de processus de fouille
dans les bases de connaissances du web se´mantique, une
hypothe`se de comple´tude partielle est de´finie et utilise´e
dans [
La fouille de donne´es est loin d’eˆtre le seul domaine
qui be´ne´ficie d’axiomes tels que ceux de´couverts par
notre algorithme, par exemple, s’appuyant sur des
travaux de re´fe´rence en base de donne´es, les auteurs de [
Dans ce papier, nous conside´rons des bases de connaissances K = (T ; A) ou` T et A sont respectivement les TBox et ABox de K. T de´signe un ensemble d’axiomes terminologiques de´finis a` partir des concepts et roˆles atomiques de K, alors que A de´signe l’ensemble des assertions ou faits de K. Plus pre´cise´ment, A contient des expressions de la forme C(a) et R(a; b) ou` C est un concept, R est un roˆle, et a, b sont des individus.
Dans le cas de la base de connaissances DBpedia, dbo:Country et dbo:Person sont des exemples de concepts atomiques et dbo:nationality est un exemple de roˆle atomique de sa TBox. Par ailleurs, dbo:Country(M auritania) et dbo:nationality(Arby; M auritania) sont des exemples de faits ou assertions de sa ABox. Le premier indique que M auritania est un pays, alors que le second indique que Arby est de nationalite´ mauritanienne. Les logiques de description permettent de de´finir des axiomes pour enrichir la TBox d’une base de connaissances. Par exemple, la relation d’inclusion v permet d’indiquer qu’un concept C1 est inclus dans un concept C2, note´ C1 v C2. Plus pre´cise´ment, une base de connaissances K implique l’axiome C1 v C2 si pour toute interpre´tation I de K, C1I C2I . Par exemple, les axiomes 9dbo:nationality:> v dbo:Person et 9dbo:nationality :> v dbo:Country indiquent respectivement que le domaine du roˆle dbo:nationality est inclus dans le concept dbo:Person, et que le codomaine du roˆle dbo:nationality est inclus dans le concept dbo:Country. 3.2
maximale Soit R un roˆle d’une base de connaissances K = (T ; A). On conside`re ge´ne´ralement que ce roˆle satisfait dans K une contrainte de cardinalite´ maximale M si pour tout sujet s, le nombre d’objets o tels que R(s; o) soit pre´sent dans K (directement pre´sent dans sa ABox A ou infe´rable a` partir de ses TBox T et ABox A) est infe´rieur ou e´gal a` M . En logique de description, une telle contrainte peut se repre´senter par un axiome de la forme sqsubseteq en utilisant le constructeur de restriction de cardinalite´ ( M R). En effet, en terme logique, une base de connaissances K implique l’axiome 9R:> v ( M R) si pour toute interpre´tation I de K, fx : (9y)((x; y) 2 RI )g fx : #fy : (x; y) 2 RI g M g ou` #E repre´sente la cardinalite´ d’un ensemble E.
Plus pre´cise´ment, dans ce papier, nous cherchons a` identifier des contraintes contextuelles de cardinalite´ maximale, a` savoir des contraintes qui ne sont pas ne´cessairement ve´rifie´es par tous les sujets s d’un roˆle R, mais par tous les sujets instances d’un concept, qu’il soit atomique ou compose´, de´ja` de´fini dans K ou pas. Cette notion est introduite formellement dans la de´finition suivante : De´finition 3.1 (Contrainte contextuelle). Etant donne´s un roˆle R, un concept atomique ou de´fini C et un entier M , une contrainte contextuelle de cardinalite´ maximale de´finie sur R est une expression de la forme : C v ( M R). Le concept C est appele´ le contexte de la contrainte . La contrainte est satisfaite dans une base de connaissances K si et seulement si pour toute interpre´tation I de K, CI fx : #fy : (x; y) 2 RI g M g.
Par exemple, la contrainte contextuelle (dbo:Person) v ( 5 dbo:nationality) indique que toutes les personnes ont au plus 5 nationalite´s, alors que la contrainte contextuelle (dbo:Person u 9dbo:nationality:fChinag) v ( 1 dbo:nationality) indique que toutes les personnes de nationalite´ chinoise ont au plus une nationalite´. Dans ce travail, on cherche a` extraire des contraintes contextuelles de cardinalite´ maximale qui soient les plus ge´ne´rales possibles.
De´finition 3.2 (Contrainte contextuelle minimale). Soient deux contraintes contextuelles de cardinalite´ maximale 1 : C1 v ( M1 R) et 2 : C2 v ( M2 R) de´finies sur R. La contrainte 1 est dite plus ge´ne´rale que la contrainte 2 si C2 @ C1 et M1 M2. Etant donne´ un ensemble de contraintes de´finies sur R, une contrainte 1 2 est dite minimale dans s’il n’existe aucune contrainte 2 dans plus ge´ne´rale que 1.
Par exemple, la contrainte contextuelle (dbo:Person) v ( 2 dbo:nationality) est plus ge´ne´rale que la contrainte contextuelle (dbo:Person u 9dbo:nationality:fChinag) v ( 5 dbo:nationality) car (dbo:Personu 9dbo:nationality:fChinag) v dbo:Person) et 2 5.
La notion de minimalite´ a pour objectif de ne pas extraire de contraintes contextuelles qui soient redondantes. Intuitivement, conside´rons les deux contraintes 1 et 2 introduites dans la de´finition pre´ce´dente, et supposons que 1 soit plus ge´ne´rale que 2. Etant donne´e une base de connaissances K dans laquelle les contraintes 1 et 2 sont satisfaites, soit une instance s de C2 dans K. D’apre`s 2, nous savons que pour toute interpre´tation I de K, #fo : (s; o) 2 RI g M2. Mais comme 1 est plus ge´ne´rale que 2, nous savons par de´finition que C2 v C1. Il en de´coule que s est aussi une instance de C1 dans K, et d’apre`s 1, que pour tout interpre´tation I de K, #fo : (s; o) 2 RI g M1, ce qui est une contrainte plus forte que #fo : (s; o) 2 RI g M2. En effet, par de´finition de la minimalite´, nous savons que M1 M2. Par rapport a` la contrainte 1, la contrainte 2 est donc inutile car redondante, i.e. elle ne permet pas de de´duire d’information supple´mentaire.
Le proble`me traite´ dans ce papier est alors le suivant : e´tant donne´s une base de connaissances K, un roˆle R et une hie´rarchie de concepts (C; v), nous cherchons a` de´couvrir l’ensemble des contraintes contextuelles de cardinalite´ maximale de la forme C v ( M R) avec
En pratique, une base de connaissances telle que DBpedia est tre`s incomple`te (par exemple, de nombreuses personnes ont seulement un parent), et elle comporte de nombreuses incohe´rences (par exemple, des personnes peuvent avoir jusqu’a` 5 parents). Pour ces raisons, e´tant donne´e une base de connaissances K, il n’est pas pertinent de chercher a` extraire des contraintes de cardinalite´ qui soient parfaitement satisfaites dans K, mais les contraintes : — les plus probables et suffisamment probables par rapport a` un seuil donne´, de manie`re a` prendre en compte et tole´rer les incohe´rences, et — suffisamment certaines par rapport a` un degre´ de confiance, pour ne pas extraire des contraintes qui soient remises en cause re´gulie`rement par l’ajout de nouveaux faits dans la base de connaissances.
Nous de´taillons dans la section suivante comment e´valuer la probabilite´ qu’une contrainte soit satisfaite dans une base de connaissances K et comment mesurer la certitude que cette contrainte soit re´elle. 4
tuelles de cardinalite´ maximale Pour re´soudre le proble`me e´nonce´ pre´ce´demment, nous commenc¸ons par le reformuler en introduisant la notion de taux de cohe´rence dans la section 4.1, puis nous de´crivons dans la section 4.2 comment de´tecter une cardinalite´ maximale pour un roˆle R dans un contexte C. Ensuite, e´tant donne´ un ensemble de contextes candidats C, nous montrons dans la section 4.3 comment explorer efficacement l’ensemble des contraintes contextuelles possibles. 4.1
Etant donne´e une base de connaissances K = (T ; A), supposons que i soit la cardinalite´ maximale du roˆle R dans le contexte C. Soit s un individu de C dans K, complet pour le roˆle R dans K (dans le sens ou` tous les faits R(s; o) possibles repre´sentant le monde re´el sont dans A ou infe´rables). Dans le cas ou` il existe exactement i faits dans K de la forme R(s; o), cela renforce l’hypothe`se que i soit la cardinalite´ maximale de R dans le contexte C. Inversement, s’il existe plus de i faits dans K de la forme R(s; o), cela affaiblit l’hypothe`se que i soit la cardinalite´ maximale de R dans le contexte C. Ainsi dans le tableau 1, pour la classe dbo:Person, les individus comportant au moins 3 assertions pour le roˆle dbo:parent affaiblissent l’hypothe`se que la cardinalite´ maximale soit 2 mais ils restent peu nombreux au regard des 9 392 individus qui ont exactement 2 parents.
En suivant ce raisonnement, nous introduisons la notion de taux de cohe´rence pour e´valuer si une cardinalite´ i pour le roˆle R dans le contexte C a des chances d’eˆtre maximale : De´finition 4.1 (Taux de cohe´rence). Etant donne´e une base de connaissances K, le taux de cohe´rence de la cardinalite´ i pour le roˆle R dans le contexte C est le ratio : iC;R(K) = nC;R
i nC;iR ou` niC;R (resp. nC;iR) repre´sente le nombre de sujets s tels que i faits R(s; o) (resp. i faits ou plus) appartiennent a` K dans le contexte C.
Par exemple, dans le tableau 1, ndb2o:Person;dbo:parent est e´gal a` 9477 (9477 = 9392+75+9+1). De cette manie`re, le taux de cohe´rence 2dbo:Person;dbo:parent(K) est de 0,991 (i.e., 9392=9477). Par la suite, quand le contexte et la relation sont clairs, nous pouvons les omettre dans les notations. Dans ce cas, ni et i de´signent respectivement les termes niC;R et iC;R.
Maintenant nous allons formaliser le lien entre le taux de
cohe´rence et la notion de contrainte maximale.
Originellement introduit dans [
En pratique, le taux de cohe´rence mesure´ dans une base de connaissances est diffe´rent du taux de cohe´rence re´el : i(K) 6= i(K ). Par exemple, le taux de cohe´rence 2(K) pour le roˆle dbo:parent du tableau 1 est e´gal a` 0,991 alors que le taux de cohe´rence re´el est e´gal a` 1. Plus grave, on a dbo:Person;dbo:parent(K) = 1 ! Le taux de cohe´rence sur 6 K est donc une estimation peu fiable du taux de cohe´rence re´el sur K . 4.2
L’estimation i(K) de i(K ) doit eˆtre corrige´e pour eˆtre statistiquement valide. Pour ce faire, nous proposons d’utiliser l’ine´galite´ de Hoeffding qui a l’avantage d’eˆtre vraie pour toute distribution. En terme de probabilite´, si X est une variable ale´atoire indiquant pour un sujet s tire´ ale´atoirement, le nombre de faits R(s; o) appartenant a` K, alors i est une estimation fre´quentielle de la probabilite´ conditionnelle P (X = i = X i). Etant donne´ un niveau de confiance 1 , l’ine´galite´ de Hoeffding stipule que i(K ) est compris entre i(K) i et i(K) + i ou` i = q lo2gn(1=i ) . Dans ce contexte, afin de prendre des de´cisions les plus suˆres, nous proposons d’utiliser la borne infe´rieure de l’intervalle de confiance [ i i; i + i]. Plus formellement, on a la proprie´te´ suivante : Proprie´te´ 4.1 (Minoration). Etant donne´es une base de connaissances K et une confiance 1 , le taux de cohe´rence re´el i(K ) de la cardinalite´ i pour le roˆle R dans le contexte C est supe´rieur a` ei(K) : i(K ) ei(K) ou` ei(K) est le taux de cohe´rence pessimiste de´fini par : ei(K) = max ( ni n i s log(1= ) 2n i Cette proprie´te´ nous munit d’un outil efficace pour approximer le taux de cohe´rence re´el. Il survient alors la difficulte´ de choisir la cardinalite´ maximale une fois que l’on dispose pour chaque cardinalite´ i du taux de cohe´rence pessimiste i(K) (pour un roˆle R dans le contexte C).
e Plus pre´cise´ment, e´tant donne´s un seuil minimal de cohe´rence min et un niveau de confiance 1 , nous conside´rons que M est la cardinalite´ maximale de R dans le contexte C si et seulement si eM min et M = arg maxi 1 ei(K).
Quelques exemples d’estimations ei et de de´tection de cardinalite´s maximales contextuelles sont donne´s dans la table 1. Dans les 3 exemples, on a conside´re´ dbo:Person comme contexte, et on a cherche´ a` de´tecter la cardinalite´ maximale contextuelle de trois roˆles : dbo:birthYear, dbo:parent et dbo:nationality. Intuitivement, pour les deux premiers roˆles, on souhaiterait de´tecter des cardinalite´s maximales respectives de 1 et 2. Pour un niveau de confiance 1 = 99% et un seuil min = 0:97, on constate que les cardinalite´s maximales suppose´es sont effectivement de´tecte´es (cf. lignes en gras dans la table 1). De manie`re inte´ressante, avec ces meˆmes seuils, aucune cardinalite´ n’est de´tecte´e pour dbo:nationality.
Etant donne´s une base de connaissances K, un roˆle R, une arborescence de concepts (C; v), un degre´ de confiance et un seuil minimal de cohe´rence min , nous cherchons a` de´couvrir l’ensemble des contraintes contextuelles de cardinalite´ maximale de la forme C v ( M R) avec C 2 C, qui soient minimales et suffisamment certaines sur K. En pratique, notons que l’arborescence (C; v) peut eˆtre une arborescence de´ja` existante dans la TBox de la base de connaissances, ou une arborescence construite dans une phase pre´alable de pre´paration des donne´es (voir la section 5.1).
Dans un tel cadre, il y a potentiellement un tre`s grand nombre de contraintes contextuelles a` conside´rer, e´valuer et comparer. Ne´anmoins, il est possible de re´duire la taille de l’espace de recherche a` explorer en se basant sur les proprie´te´s 4.2 et 4.3 e´nonce´es ci-apre`s. Tout d’abord, la proprie´te´ 4.2 montre qu’une contrainte C v ( M R) ne peut pas eˆtre suffisamment certaine si le contexte C contient trop peu d’individus dans K, car alors l’intervalle de confiance du taux de cohe´rence calcule´ graˆce a` l’ine´galite´ de Hoeffding est tre`s large et sa borne infe´rieure ne peut eˆtre supe´rieure au seuil min impose´.
Proprie´te´ 4.2 (Nombre minimal d’observations). Etant donne´s une base de connaissances K, une contrainte contextuelle de cardinalite´ maximale C v ( M R) et un seuil min , le taux de cohe´rence eM (K) que M soit la cardinalite´ maximale de R dans C ne peut eˆtre supe´rieur a` min que si jCj 2(1logm(1i=n ))2 .
Par ailleurs, supposons qu’une contrainte de´finie par C v ( M R) avec M = 1 ait e´te´ de´tecte´e comme suffisamment certaine au cours de l’exploration. Alors, d’apre`s la proprie´te´ 4.3, il n’est pas ne´cessaire d’explorer les contraintes 0 de´finies par C0 v ( M 0 R) ou` C0 est plus spe´cifique que C. Cette proprie´te´ de´coule directement de la de´finition 3.2 de la minimalite´.
Proprie´te´ 4.3 (Contrainte minimale). Soient une base de connaissances K et une contrainte contextuelle de cardinalite´ maximale de´finie par C v ( M R) avec M = 1. Toute contrainte 0 de´finie par C0 v ( M 0 R) avec C0 v C et M 0 1 ne peut eˆtre minimale.
L’algorithme 1 de´taille notre fonction re´cursive d’exploration, la fonction C3M (pour Contextual Cardinality Constraint Mining). Cette fonction prend en entre´e une base de connaissances, un roˆle a` explorer, un contexte courant, une cardinalite´ maximale courante (M = 1 si aucune cardinalite´ maximale n’a encore pu eˆtre de´tecte´e), et enfin, des seuils et min . Le de´marrage de l’exploration d’une arborescence de racine > se fait en exe´cutant la fonction C3M (K; R; >; 1; ; min ).
Pour commencer, la fonction C3M de´termine si le nombre d’individus est suffisant dans le contexte C. Si ce n’est pas le cas, elle arreˆte l’exploration a` la ligne 2 conforme´ment a` la proprie´te´ 4.2. Sinon, le taux de cohe´rence ei est calcule´ pour chaque cardinalite´ i (lignes 4 a` 6) et la ligne 7 retient la cardinalite´ maximale la plus probable. Si le taux de cohe´rence correspondant n’est pas supe´rieur au seuil min , alors cela signifie qu’aucune cardinalite´ maximale n’a pu eˆtre de´tecte´e a` ce niveau et iM est fixe´ ligne 8 a` 1. Ensuite, si la cardinalite´ maximale de´tecte´e iM est strictement infe´rieure a` M (la cardinalite´ maximale de´tecte´e au niveau pre´ce´dent), alors on dispose d’une nouvelle contrainte minimale de cardinalite´ maximale iM et on l’ajoute a` , l’ensemble des contraintes recherche´es. Finalement, conforme´ment a` la proprie´te´ 4.3, si iM est e´gale a` 1, il n’est pas ne´cessaire de poursuivre l’exploration en parcourant les contextes plus spe´cifiques de C. Sinon, la fonction C3M est appele´e re´cursivement a` la ligne 12 pour tous les C0 qui sont des sous-concepts directs de C. Dans notre imple´mentation de la fonction C3M , nous avons applique´ une approche client-serveur ou` les distributions de cardinalite´ niC;R sont calcule´es par interrogation en SPARQL d’une base de connaissances localise´e sur un serveur. Dans un tel cadre, la complexite´ de notre me´thode en nombre de requeˆtes sur le serveur est en O(jCj) ou` jCj repre´sente le nombre de concepts dans l’arborescence C explore´e. Dans le pire des cas, coˆte´ client, la complexite´ en nombre d’ope´rations est en O(jCj imax) ou` imax Algorithm 1 C3M Input: Une base de connaissances K, un roˆle R, un contexte C, un entier M , un niveau de confiance et un seuil minimal de support min Output: Un ensemble de contraintes contextuelles de cardinalite´ maximale 1: := 2(1logm(1i=n ))2 et nC;0R := jCj 2: if (nC;0R < ) then return ; 3: := ; et imax := arg maxi2NfniC;R > 0g 4: for all i 2 [1::minfM; imaxg] do
( nC;R ) 5: ei := max niC;iR r lo2gn(C1;=iR) ; 0 6: end for 7: iM := arg maxi2[1::minfM;imaxg]feig 8: if (eiM < min ) then iM = 1 9: if (iM < M ) then := fC v ( iM R)g 10: if (iM > 1) then 11: for all C0 2 subClassOf (C) do 12: := [ C3M (K; R; C0; iM ; ;min ) 13: end for 14: end if 15: return repre´sente l’entier maximal pour lequel il existe au moins un sujet s tel que imax faits R(s; o) appartiennent a` la base de connaissances K, i.e. imax = arg maxi2Nfni>;R > 0g. 5
Outre les requeˆtes sur DBpedia (dont nous montrons des
e´chantillons de re´ponses en table 1), qui ont e´te´ utilise´es
pour mettre au point la de´finition du taux de cohe´rence,
nous avons expe´rimente´ l’algorithme 1 sur un jeu de
donne´es mis a` notre disposition par les auteurs de [
Le jeu de donne´es utilise´ porte sur le domaine numismatique, il est le re´sultat d’un processus d’inte´gration mene´ dans le cadre du projet europe´en ARIADNE 2. Ses auteurs ont utilise´ le CIDOC-CRM 3 pour inte´grer les contenus de 5 ressources construites par des institutions de diffe´rents pays europe´ens. Il contient 3 123 998 triplets, dont les de´finitions de 114 classes et 373 roˆles ou proprie´te´s du CIDOC-CRM et d’ARIADNE. Il est stocke´ et interroge´ avec le triplestore Blazegraph (v2.1.4), sur une machine virtuelle sous Linux avec 32 GB de me´moire virtuelle, sur un serveur ayant pour processeur un Dual Intel Xeon E5620 4 coeurs. L’algorithme 1 est imple´mente´ en Java et utilise la bibliothe`que de programmation pour RDF Jena 4. La base porte sur des pie`ces de monnaies mais, par choix des inte´grateurs, il n’existe pas de classe Coin. Les individus correspondant a` des pie`ces sont des instances de E22 Man Made Object caracte´rise´es par certains URIs (ex. <http://nomisma.org/id/coin>) comme va2. http://ariadne-infrastructure.eu/ 3. http://www.cidoc-crm.org/ 4. http://jena.apache.org leur objet de certains roˆles (ex. P2 has type). Plusieurs roˆles et plusieurs URIs sont utilise´s pour cela, aussi nous avons de´cide´ de construire notre propre arborescence d’exploration de la fac¸on suivante : Au premier niveau, notre arborescence contient tous les concepts Ci de la base, soit 114 concepts (i 2 [1::114]). Tous ces concepts sont des sous-concepts du concept racine > au niveau ze´ro, i.e. pour tout i, nous avons Ci v >. Au deuxie`me niveau notre arborescence contient tous les concepts Cij de´finis par Cij := Ci u (9Rj :>) ou` Ci (i 2 [1::114]) et Rj (j 2 [1::373]) sont respectivement des concepts et roˆles de la base. A ce niveau, 42 522 concepts Cij sont ainsi de´finis. Enfin, au troisie`me niveau, notre arborescence contient tous les concepts Cj;k de´finis par i Cj;k := Ci u (9Rj :fakg) ou` Ci (i 2 [1::114]) et Rj i (j 2 [1::373]) sont respectivement des classes et roˆles de la base, et ak est un individu du co-domaine de Rj , i.e. ak 2 (9Rj 1:>). Graˆce a` ce dernier niveau, il est possible de conside´rer des contextes a` la manie`re de notre exemple jouet ou` dbo:Person u 9dbo:nationality:fChinag. CNiojtonvs fiCnail.emGelonbtaqlueempeonut,r tcoeutttei; ajr;bko,rneoscuesnacveoncsoCmijp;okrvte 3 160 357 concepts, donc pour les 373 roˆles de la base de connaissances cela repre´sente plus d’un milliard de contraintes contextuelles possibles (exactement 1 178 813 161 contraintes). Ne´anmoins, comme nous le verrons dans la section suivante, l’utilisation des proprie´te´s 4.2 et 4.3 permet d’e´laguer une grande partie de l’espace de recherche. 5.2
Tous les re´sultats pre´sente´s dans cette section ont e´te´ obtenus avec un seuil minimal de confiance 1 = 0; 99% (pour des contraintes les plus certaines possibles) et un seuil minimal de cohe´rence min = 0; 95 (pour des contraintes suffisamment probables). Ce seuil a e´te´ de´fini expe´rimentalement. Sur des bases de connaissances de plus grande taille comme DBpedia, un seuil plus e´leve´ est pre´fe´rable. Ne´anmoins, l’approche est relativement peu sensible aux seuils (i.e., l’ensemble des contraintes trouve´es est stable).
Analyse quantitative. Avec ces parame`tres, la proprie´te´ 4.2 nous indique qu’une contrainte C v ( M R) ne peut eˆtre suffisamment certaine si son contexte C contient moins de = 2(1logm(1i=n ))2 = 922 instances. Ainsi, l’utilisation de la proprie´te´ 4.2 permet de n’explorer que 16 641 contraintes, soit moins de 0; 002% des plus de 1 milliard de contraintes possibles. Qui plus est, notre expe´rience montre que la proprie´te´ 4.3 permet de re´duire encore de 82; 5% la taille de l’espace de recherche a` explorer. Au final, avec les seuils choisis notre algorithme ne cherche a` de´tecter une cardinalite´ maximale que pour 2 909 contextes possibles, avec un temps de calcul complet de moins de 50 minutes.
La table 2 donne une vue globale et quantitative du re´sultat de l’exploration re´alise´e. Sur les 2 909 contraintes contextuelles possibles, notre algorithme a de´tecte´ au total 887 contraintes de cardinalite´ maximale, 595 d’entre elles e´tant des contraintes minimales. Sur cet exemple, le crite`re de minimalite´ permet donc de re´duire de pre`s de 67% le nombre de contraintes retourne´es. On constate que les contraintes les plus nombreuses sont des cardinalite´s maximales avec M = 1, ce qui correspond a` des contraintes ou` pour un roˆle donne´ R, tout sujet s est en relation avec au plus un objet o. Ne´anmoins de tre`s nombreuses contraintes sont trouve´es avec des cardinalite´s maximales M 2 f2; 3g (37% des contraintes minimales de´tecte´es). On note e´galement que si des contraintes de cardinalite´s maximales sont de´tecte´es de`s le niveau 0 (65 contraintes avec un contexte C >), la recherche de contraintes contextuelles est particulie`rement pertinente. Il faut en effet noter que les contraintes les plus nombreuses sont trouve´es au niveau 3 (75% des contraintes de´tecte´es), sachant que par construction de notre arborescence, c’est a` ce niveau que sont caracte´rise´es les pie`ces de monnaie.
Analyse qualitative. Tout d’abord, de`s le niveau 0, notre me´thode permet de retrouver des contraintes fonctionnelles attendues, par exemple, pour les 3 roˆles du CIDOCCRM P1 is identified by, P52 has current owner et P50 has current keeper, indiquant que si un sujet de´crit dans la base posse`de plus d’un identifiant, un proprie´taire ou un conservateur, alors on peut en de´duire que ces identifiants (respectivement, proprie´taires et conservateurs) sont identiques. Concernant le roˆle P45 consists of du CIDOC-CRM (permettant de de´crire les mate´riaux constitutifs d’un objet), il est inte´ressant de noter qu’une cardinalite´ maximale de 2 est de´tecte´e de`s le niveau 1 pour la classe E22 Man Made Object. La base de connaissances de´crit notamment des me´dailles constitue´es d’or et de pierre pre´cieuse (telle l’agate). Pour ce meˆme roˆle, une cardinalite´ maximale de 1 est de´tecte´e au niveau 3 pour les pie`ces de monnaie. Cette information est notamment repre´sente´e par la contrainte E22 Man Made Object u 9P2 has type:f<http://nomisma.org/id/coin>g v ( 1 P45 consists of). Cette contrainte est de´tecte´e bien qu’a` certaines pie`ces la relation P45 consists of associe deux mate´riaux ; mais c’est rare (et le plus souvent il s’agit du meˆme mate´riau dans deux langues diffe´rentes). Un meˆme type de contrainte (avec M = 1) est trouve´e au niveau 3 pour tous les contextes de´crivant des pie`ces, concernant le roˆ le P62 depicts (ce qui est de´peint sur l’objet). C’est raisonnable car dans le cas d’une pie`ce de monnaie, on trouve le plus souvent une seule repre´sentation figurative (sur une des deux faces de la pie`ce), alors qu’une telle contrainte n’est pas valide pour d’autres objets. Au passage, l’e´tude de l’ensemble des contraintes extraites par notre me´thode a mis en e´vidence des redondances dans la base, sans doute du fait des choix d’inte´gration. Dans une phase de post-traitement, la connaissance d’axiomes tel que 9P2 has type:f: : : coing v 9Thing has type Concept:f: : : monetag pourrait re´duire encore le nombre de contraintes extraites. 6
Nos expe´rimentations de´montrent la faisabilite´ d’une exploration syste´matique d’une base de connaissances, a` la recherche de contraintes contextuelles de cardinalite´ maximale, graˆce a` l’algorithme que nous proposons dans cet article : dans le cas e´tudie´, cela prend moins d’une heure pour une base de connaissances contenant plus de 3 millions de triplets, de´crits par une centaine de concepts et plus de 300 r oˆles. Les proprie´te´s utilise´es par notre algorithme font que seules 595 contraintes ont e´te´ obtenues, ce qui reste analysable manuellement. Cela nous a permis de ve´rifier que ces contraintes sont bien pertinentes dans le contexte de la base e´tudie´e. De plus, nos expe´rimentations de´montrent l’importance du contexte dans cette de´couverte de contraintes. Il s’agit a` notre connaissance de la premie`re proposition de calcul de contraintes contextuelles de cardinalite´ maximale dans une base de connaissances du web se´mantique. Ces grandes bases de connaissances, reflet d’une intelligence collective, sont ge´ne´re´es a` partir de l’expertise limite´e de nombreux contributeurs et souffrent encore, tantoˆ t de lacunes dans les informations, tantoˆ t d’incohe´rences. Utiliser leurs contenus courants afin de mieux caracte´riser les connaissances repre´sente´es est donc tre`s utile, comme montre´ dans l’e´tat de l’art : cela permet aux applications qui exploitent ces grandes bases de connaissances de produire des re´sultats plus fiables.
Nous avons donc pour perspective d’exploiter les contraintes extraites pour calculer la confiance associe´e a` des re`gles de´couvertes dans la base de connaissances ainsi enrichie. Mais avant cela, nous travaillons sur des posttraitements pour re´duire encore le nombre de contraintes pre´sente´es en re´sultat. Pour cela, nous explorons le potentiel des raisonnements possibles sur la TBox, en particulier comment les relations de subsomption entre classes peuvent e´liminer des redondances dans les ensembles de contraintes extraites.