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 :