Brevet FR2940693A1 — publié le 20100702

Procédé et système optimisé de gestion des noms propres pour l'optimisation de la gestion et de l'interrogation des bases de données L'objet de la présente invention concerne un procédé optimisé de gestion des noms propres ou entités nommées pour l'optimisation de la gestion et de l'interrogation des bases de données et de bases de connaissances. Elle repose notamment sur une automatisation du procédé d'appariement de variantes graphiques et de variantes syntaxiques de noms propres ou d'entités nommées qui se réfèrent à un nom ou à une entité unique. Le procédé conduit à une modification du contenu de la base de données permettant une recherche plus rapide dans une base ou à une gestion optimisée de cette même base de données. Il est ainsi utilisé pour améliorer et accélérer les processus d'alimentation et de gestion des bases de données ou bases de connaissances, ainsi que les processus de recherche d'information. Dans le domaine de la gestion des données ou des connaissances, pour alimenter les bases l'art antérieur utilise des outils d'extraction d'information appliqués à de larges collections de textes qui permettent d'identifier des entités nommées de différents types : noms de personnes, noms d'organisations, noms de lieux, adresses, etc. Ces entités sont soumises à une variabilité graphique et syntagmatique très importante ù du fait d'erreurs typographiques ou orthographiques, du fait de problèmes de translittération et de transcription, du fait aussi de processus de transformation syntagmatique (réduction/extension), ordre des mots, siglaison, etc. Si le processus d'extraction d'entités nommées est aujourd'hui assez bien maîtrisé, le processus d'appariement l'est moins et la tâche d'appariement est effectuée manuellement. Ainsi, en sortie du processus d'extraction d'entités nommées, on aura pour une entité de type Personne, par exemple dans le cas d'un individu nommé � Laurent Gbagbo �, une liste de variantes très importante du point de vue quantitatif parmi lesquelles {Laurent Gbabgo, Laurent Gbagbo, L.Gbabgo, L.Gbagbo, ..}. Ces variantes renvoient à la même personne et doivent être très appariées pour être stockées dans la base de connaissances, ceci en vue d'assurer la cohérence des connaissances. De la même manière dans les bases de données Personne, les individus sont souvent stockés sur plusieurs enregistrements d'une base de données du fait w d'erreurs commises lors de la saisie sur leur nom, leur adresse, etc.... La problématique de l'appariement des entités nommées ou noms de personnes est très largement abordée dans la littérature. Les méthodes proposées, à la connaissance du Demandeur, s'appuient principalement sur 15 les méthodes précitées de calcul de la distance de Levenshtein, de phonémisation ou de calcul des similarités séparément (sans combinaisons de ces techniques). La méthode de Levenshtein utilisée seule reste peu exploitable ne donnant pas de résultats probants. La phonémisation produit de bons 20 résultats pour l'appariement d'entités, toutefois, elle reste dépendante de la langue et impose l'intervention d'experts pour développer et maintenir les règles du dispositif de phonémisation ou phonémiseur. Les calculs de similarité ou de distance produisent de bons résultats, qui restent néanmoins dépendants de la façon dont sont traitées les entités nommées (bi-grams 25 seuls, tri-grams seuls, etc.). L'un des objectifs de la présente demande de brevet est d'optimiser les résultats obtenus par la combinaison des méthodes précitées. Le procédé selon l'invention repose, notamment, sur une utilisation conjointe de méthodes linguistiques et de méthodes 30 mathématiques, notamment, d'une mesure de similarité qui repose sur la distance de Levenshtein qui mesure la similarité entre deux chaînes de caractères, de la méthode des N-Grams, correspondant à une sous-séquence de n éléments construite à partir d'une séquence donnée, de l'analyse relationnelle et de la similarité régularisée. Ces différentes méthodes sont connues de l'Homme du métier et seuls les rappels nécessaires à la compréhension de l'invention seront donnés dans la présente demande de brevet. L'invention concerne un procédé permettant de gérer des entités nommées se présentant sous différentes formes graphiques ou syntaxiques et référant à la même entité contenues dans une base de données, caractérisé en ce qu'il comporte au moins les étapes suivantes : • appliquer une méthode de Levenshtein sur lesdites entités E, dans la base de données afin de créer une similarité entre lesdites entités, définir la mesure de similarité entre deux entités de la manière 15 suivante S1(E,E~)=1-- maxVE,.I, l Eil) avec Si , la mesure de similarité entre les deux entités (Ei, E1) de la base de données, D la distance de Levenshtein entre les deux entités, IE. respectivement E. le nombre de caractères de E, respectivement E. 20 • utiliser la méthode de n-grams pour créer une similarité Si, (E;, E1)entre les A entités constituant la base de données, en extrayant des deux entités E1 et Ei les ensembles Ni des n-grams de E; et l'ensemble Ni des n-grams de E., définir ensuite le nombre de n-grams 'Nil déduits de E, et le nombre de n-grams Nfl déduits de E., IN n Nl ) .i 25 la similarité entre E, et E1 est alors définie par : Sn(E,E1 min(INi,N1) • utiliser une méthode de fusion des données sur lesdites entités de la base de données afin de construire au moins 2 classifications, relatives respectivement à la similarité n-grams avec n supérieur ou égal à 2, lesdites classifications correspondant à des ensembles de classes d'entités Pi, • trouver la partition consensus P, entre les M partitions trouvées, utiliser l'entité de forme canonique E,, pour visualiser le résultat ou encore modifier les entités présentes dans la base de données par l'entité de forme canonique. io Le procédé de fusion mis en oeuvre peut être la méthode d'analyse relationnelle. Lors de l'étape d'analyse relationnelle, le procédé pour accomplir l'étape d'analyse relationnelle pour trouver la partition consensus entre les partitions déterminées utilise, par exemple, la similarité régularisée pour 15 pondérer différemment le poids de chaque partition, dans le calcul de la similarité globale déduite des trois partitions en exécutant les étapes suivantes on commence par calculer la densité 8, de chaque partition P; , cette densité est une mesure du pouvoir d'agrégation de la partition K Enk 20 considérée et est définie par la relation : 8. = k-' 2 où Kest le nombre nb_entites de classes de la partition Pi, n;k le nombre d'entités de la partition k et nb_entites est le nombre d'entités présentes dans la base, 3 En notant A = l8; , alors le poids n; de la partition P, sera : i=l II; =0.5x/1--L A, Le procédé peut comporter une étape d'émission d'une requête d'un utilisateur pour trouver les entités canoniques dans une base de données et effectuer le remplacement desdites entités par l'entité canonique trouvée. L'invention concerne aussi un système permettant de gérer des entités nommées se présentant sous différentes formes graphiques ou syntaxiques et référant à la même entité contenues dans une base de données dans lequel le procédé va exécuter différentes actions physiques au niveau de la base de données pour optimiser la qualité de la base de io données et par suite en obtenir une meilleure gestion caractérisé en ce qu'il comporte au moins les éléments suivants : • un processeur adapté à exécuter les différentes étapes du procédé selon l'invention, • une base de données non structurées, cette base peut contenir des 15 textes • une mémoire tampon permettant le stockage de toutes les données dont il faut réaliser l'appariement. Le système peut aussi comporter un dispositif de prise de décision suite à une requête formulée par un utilisateur. 20 Le système peut aussi comporter une interface homme machine permettant l'affichage des résultats de classification du procédé présentant au moins une des caractéristiques précitées et l'intervention d'un opérateur pour modifier la base de données initiale en remplaçant les entités présentes dans la base de données par l'entité de forme canonique. 25 D'autres caractéristiques et avantages du dispositif selon l'invention apparaîtront mieux à la lecture de la description qui suit d'un exemple de réalisation donné à titre illustratif et nullement limitatif annexé des figures qui représentent : 30 • La figure 1, un exemple de système permettant la mise en oeuvre du procédé selon l'invention, • La figure 2, un synoptique des différentes étapes mises en oeuvre par le procédé selon l'invention, • La figure 3, un exemple d'utilisation du procédé après une requête émise par un utilisateur, et • La figure 4 un exemple dans le cas d'une entité nommée � Pierre Alchantel �. Afin de mieux faire comprendre le procédé selon l'invention, le premier exemple donné est en relation avec la gestion d'une base de données contenant une collection de données non structurées. io La figure 1 représente un exemple de système dans lequel le procédé va exécuter différentes actions physiques au niveau de la base de données pour optimiser la qualité de la base de données et par suite en obtenir une meilleure gestion. Le système 1 comporte un processeur 2 adapté à exécuter les différentes étapes du procédé selon l'invention, une 15 base de données non structurées 3 qui peut contenir des textes, une mémoire tampon 4 qui va permettre le stockage de toutes les données dont il faut réaliser l'appariement et éventuellement une base de données de stockage 5 dans le cas où les données canoniques remplaçant les données de base ne sont pas stockées dans la base de données initiale. Il va donc 20 résulter de ce traitement des interactions physiques avec les bases de données, notamment dans le cas de remplacement d'une donnée par une autre donnée. Les étapes mises en oeuvre par l'invention sont représentées aux figures 1 et 2. La première étape El consiste à extraire de la collection de 25 données non structurées 3 par un mécanisme d'extraction d'information connu de l'Homme du métier, une liste de données constituées d'une liste d'entités nommées typées sémantiquement Ls, telles que des noms de personnes, de lieux, d'organisations. Ces dernières pourront être stockées temporairement dans la mémoire tampon 4 qui va être utilisée pour stocker 30 les données en cours de traitement dans le cas où la mémoire de travail du processeur est insuffisante. Cette première étape El peut consister en une étape de pré-traitement et d'application de règles linguistiques de transformation des données. Ces prétraitements sont connus de l'Homme du métier et ne seront pas explicités. Par exemple, dans une entité nommée de type Organisation, on ramènera les formes Ltd à la forme Limited, Corp à la forme Corporation, ceci en vue d'aider à l'appariement d'entités telles que XXX limited, XXX Ltd. Ces règles de prétraitement sont de deux types : certaines sont indépendantes des catégories d'entités de la base de données considérée (passage en typographie pauvre, suppression de signes de ponctuation, etc ...) ; d'autres sont dépendantes des catégories d'entités de la base de données considérée. Les règles de transformation sont simples et évolutives ; elles ne requièrent pas de connaissances linguistiques avancées. La liste d'entités ainsi pré-traitée va être mise dans la mémoire tampon 4, et le procédé va mettre en oeuvre la méthode d'appariement selon l'invention sur cette liste. Pour cela, le procédé va exécuter une étape E2 de similarité en appliquant la méthode de distance de Levenshtein détaillée ci-après sur les données qui se présentent sous la forme d'une liste de N lignes, N étant le nombre d'objets ou d'entités à apparier. En sortie de l'étape E2, on dispose d'une matrice comprenant A lignes et A colonnes, les éléments Ei de cette matrice ou tableau correspondant à une valeur de similarité ente deux objets. La troisième étape E3 consiste à appliquer la méthode des NGrams sur les sorties de E2 puis à mesurer la similarité entre les éléments ou entités nommées à apparier. Une quatrième étape E4 va utiliser une méthode de fusion, prenant en compte toutes les matrices de similarités précédemment calculées. On utilisera, par exemple, l'analyse relationnelle pour faire cette fusion. Le but de l'analyse relationnelle est, notamment de déterminer, dans la base de données étudiée, des classes d'entités nommées, telles que chaque classe est constituée de toutes les graphies d'une même entité. Ces classes étant relatives aux similarités définies par la méthode de la distance de Levenshtein et de la méthode des N-Grams. Les C classifications, où C est le nombre de mesures de similarités différentes utilisées, donneront C partitions. Le procédé utilise une nouvelle fois l'analyse relationnelle pour trouver la partition consensus entre les C précédentes classifications, celle qui sera la plus proche des C partitions trouvées précédemment. L'exemple détaillé qui suit, va permettre d'expliciter de manière plus concrète le procédé selon l'invention. II sera donné dans le cadre non limitatif d'utilisation de la méthode de Levenshtein et des N-grams pour les 2-grams et 3-grams. to Une autre fonction de l'analyse relationnelle est, notamment, de considérer m entités E, appartenant à une même classe Ci et rechercher l'entité représentante. Dans le cadre d'un processus automatique, c'est cette entité représentante qui va être mémorisée dans une base de données, c'est-à-dire que les entités initialement présentes dans une base de données 15 seront remplacées par leur forme canonique qui est l'entité Ei trouvée après le consensus. Dans le cadre d'un processus semi-automatique, c'est l'utilisateur qui choisira la forme canonique représentante. Ainsi les données non classifiées initialement vont être remplacées par une seule forme, qui sera considérée comme la forme canonique pour toutes les entités) 20 L'algorithme utilisé par le procédé selon l'invention et se déroulant sur le processeur se compose au moins des trois parties suivantes: Etape 1 Utilisation d'un prétraitement linguistique 25 Etape 2 Utilisation et transformation de la distance de Levenshtein pour créer une similarité. Cette transformation est fondamentale, puisque la distance de Levenshtein n'est pas normée. En effet si, D(E,, E2) est la distance de Levenshtein entre les deux entités E, et E2, et si l'on note E, 30 respectivement 1E2 le nombre de caractères de E, respectivement E2, la seule information que l'on possède sur D(E,,E2) est : 0 D(E,, E2) IN, nN2I 10 entre E, et E2 est alors définie par : S(E,,E2)= l min(IN,I, N2I) Où IN1 nN2I est le nombre de n-grams communs aux deux ensembles N, et N2. Etape 3 On construit ensuite, en utilisant la théorie de l'analyse 15 relationnelle, trois classifications, pour l'ensemble des entités présentes dans la base de données étudiée, relatives aux trois similarités définies ci-dessus (la similarité pour les 2-grams, la similarité pour les 3-grams et la similarité déduite de la distance de Levenshtein). Ces trois classifications donneront donc trois partitions (trois ensembles de classes d'entités) P; (i =1,2,3). 20 II s'agira ensuite d'utiliser l'analyse relationnelle pour trouver la partition consensus PP entre les trois précédentes partitions (celle qui sera la plus proche des trois partitions). Pour accomplir l'étape d'analyse relationnelle pour trouver la partition consensus entre les trois précédentes partitions, on va utiliser la 25 similarité régularisée pour pondérer différemment le poids de chaque partition, dans le calcul de la similarité globale déduite des trois partitions. A cet effet, on commence par calculer la densité 8, de chaque partition Pi. Cette densité est une mesure du pouvoir d'agrégation de la partition K 2 nik considérée. Elle est définie par la relation : 5 = k=' 2 où x est le nb entites nombre de classes de la partition P; , n,k le nombre d'entités de la partition k 5 et nb_entites est le nombre d'entités présentes dans la base. Si on note 3 ( 8" A = , alors le poids FI, de la partition P ; sera : II, = 0.5x 1ù ` . Plus la densité d'une partition sera grande, moins elle aura d'importance dans le calcul de la similarité globale. La figure 3 schématise un exemple d'utilisation du système et du -w procédé selon l'invention, par un utilisateur représenté sur la figure par une requête 20 qu'il émet vers une base de données 3 contenant, par exemple, des noms de personne, de lieux ou d'organisations, ou un ensemble de ces entités. L'utilisateur va par exemple émettre une requête `recherche' sur un nom de personne, un lieu, une adresse, etc., cette requête émise sur la 15 base de données à gérer va mettre en oeuvre le procédé selon l'invention. Le processeur déclenche une étape 21 permettant la recherche des formes proches ou méthode d'appariement telle que celle détaillée aux figures 1 et 2. L'ensemble des classes des formes proches détectées 22 va être transmis à un dispositif 23 de prise de décision. Cette prise de décision peut être 20 automatique, 24, si dans les classes trouvées la similarité des entités appartenant à la classe est de 1. A l'inverse si dans les classes trouvées la similarité est inférieure à 1, la prise de décision fait intervenir l'utilisateur, par l'intermédiaire d'une interface Homme-machine 25, c'est l'utilisateur 26 qui va commander la modification dans la base de données. 25 La figure 4 représente la mise en oeuvre du système de la figure 3 dans le cas précis d'une entité nommée � Pierre Alchantel �. Sur requête d'un opérateur, le procédé selon l'invention va effectuer une recherches des formes propres en mettant en oeuvre le procédé selon l'invention. Il va obtenir l'ensemble des classes des formes � proches détectées �. L'analyse et la visualisation des personnes et des informations associées vont être affichées sur un écran 25 afin que l'opérateur puisse prendre une décision. Dans le cadre d'une application à la gestion d'identification dans les entreprises, d'individus, le procédé selon l'invention permet de mettre en oeuvre des processus de � nettoyage � ou cleaning des bases de données. Pour des applications de gestion d'identification de personnes au sein d'une base de données entreprise, le procédé permettra d'identifier un ensemble d'enregistrement qui renvoient à une entreprise à l'aide d'un seul représentant. D'autre part, le procédé selon l'invention permet à un instant donné d'effectuer des opérations de nettoyage ou � cleaning � des bases de données (suppression de faux doublons) qui permettront elles-mêmes de fusionner les informations, associées aux faux doublons. Le procédé offre aussi des processus d'appariement automatique (sans intervention de l'administrateur de la base de données ou de la base de connaissances). Le procédé selon l'invention va s'appliquer dans de nombreux domaines tels que l'appariement de noms propres, tels que des noms d'organisations, des noms de lieux, l'appariement d'entités nommées coréférentes, l"interrogation de bases de données, la gestion de données et de base de données, la gestion de connaissance et de bases de connaissances, la gestion de l'identification, la recherche de similarités entre entités nommées, entre noms propres, la fusion de données, le traitement automatique de langage naturel. REVENDICATIONS1 ù Procédé permettant de gérer des entités nommées se présentant sous différentes formes graphiques ou syntaxiques et référant à la même entité contenues dans une base de données (3), caractérisé en ce qu'il comporte au moins les étapes suivantes : • appliquer une méthode de Levenshtein sur lesdites entités E. dans la base de données afin de créer une similarité entre lesdites entités, 10 définir la mesure de similarité entre deux entités de la manière suivante S,(E,Ej)=1ù D(E; max(IE;I, E~ ) avec S; , la mesure de similarité entre les deux entités (E , E;) de la base de données, D la distance de Levenshtein entre les deux entités, 15 IE;I respectivement E1I le nombre de caractères de E, respectivement E. • utiliser la méthode de n-grams pour créer une similarité Sn (E;, Ej)entre les A entités constituant la base de données, en extrayant des deux entités E; et Ei les ensembles N. des n-grams de E; et l'ensemble N. des n-grams de E., définir ensuite le nombre de n-grams 20 !Nil déduits de E; et le nombre de n-grams N1 déduits de E., 'N; nN la similarité entre E, et E1 est alors définie par : Sn (E; , E~ )= min j N; , N • utiliser une méthode de fusion des données sur lesdites entités de la base de données afin de construire au moins 2 classifications, relatives respectivement à la similarité n-grams avec n supérieur ou 25 égal à 2, lesdites classifications correspondant à des ensembles de classes d'entités P, ,• trouver la partition consensus PP entre les M partitions trouvées, utiliser l'entité de forme canonique E,, pour visualiser le résultat ou encore modifier les entités présentes dans la base de données par l'entité de forme canonique. 2 ù Procédé selon la revendication 1 caractérisé en ce que le procédé de fusion est la méthode d'analyse relationnelle. 3 ù Procédé selon la revendication 2 caractérisé en ce que lors de l'étape de 10 l'analyse relationnelle, le procédé pour accomplir l'étape d'analyse relationnelle pour trouver la partition consensus entre les partitions déterminées va utiliser la similarité régularisée pour pondérer différemment le poids de chaque partition, dans le calcul de la similarité globale déduite des trois partitions en exécutant les étapes suivantes 15 on commence par calculer la densité 8, de chaque partition Cette densité est une mesure du pouvoir d'agrégation de la partition Z2 nik considérée et est définie par la relation : 5 = k=1 2 où x est le nombre nb_entites de classes de la partition nik le nombre d'entités de la partition k et nb_entites est le nombre d'entités présentes dans la base, 3 20 En notant A = E8; alors le poids IZ; de la partition P; sera : ( 8 \ II, =0.5x1--L -'4 ù Procédé selon l'une des revendications 1 à 3 caractérisé en ce qu'il comporte une étape d'émission d'une requête d'un utilisateur pour trouver les 25 entités canoniques dans une base de données et effectuer le remplacement desdites entités par l'entité canonique trouvée.55 - Système permettant de gérer des entités nommées se présentant sous différentes formes graphiques ou syntaxiques et référant à la même entité contenues dans une base de données dans lequel le procédé va exécuter différentes actions physiques au niveau de la base de données pour optimiser la qualité de la base de données et par suite en obtenir une meilleure gestion caractérisé en ce qu'il comporte au moins les éléments suivants : • un processeur (2) adapté à exécuter les différentes étapes du procédé io selon l'invention, • une base de données non structurées (3) qui peut contenir des textes, • une mémoire tampon (4) permettant le stockage de toutes les données dont il faut réaliser l'appariement. 15 6 û Système selon la revendication 5 caractérisé en ce qu'il comporte un dispositif de prise de décision (23) suite à une requête (20) formulée par un utilisateur. 7 û Système selon la revendication 5 caractérisé en ce qu'il comporte une 20 interface homme machine (25) permettant l'affichage des résultats de classification du procédé selon l'une des revendications 1 à 4 et l'intervention d'un opérateur pour modifier la base de données initiale en remplaçant les entités présentes dans la base de données par l'entité de forme canonique.