Patent Publication Number: US-8117237-B2

Title: Optimized method and system for managing proper names to optimize the management and interrogation of databases

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     The present application claims priority to French Patent Application Serial No. 0807488, filed on Dec. 30, 2009, which is hereby incorporated by reference in its entirety. 
     TECHNICAL FIELD OF THE INVENTION 
     The subject of the present invention relates to an optimized method for managing proper names or named entities to optimize the management and interrogation of databases and knowledge bases. It relies notably on an automation of the method of matching graphical variants and syntactic variants of proper names or named entities that refer to a single name or entity. 
     The method leads to a modification of the content of the database allowing for a more rapid search in a base or to an optimized management of this same database. 
     It is thus used to improve and speed up the processes of feeding and managing databases or knowledge bases, and the information search processes. 
     BACKGROUND OF THE INVENTION 
     In the field of data or knowledge management, to feed the bases, the prior art uses information extraction tools applied to broad collections of texts that make it possible to identify named entities of different types: names of people, names of organizations, names of places, addresses, etc. 
     These entities are subject to a very great graphical and syntagmatic variability—because of typographic or spelling errors, because of transliteration and transcription problems, because also of the syntagmatic transformation process (reduction/extension), order of the words, creation of abbreviations, etc. While the process of extracting named entities is now fairly well mastered, the matching process is less so and the matching task is performed manually. 
     Thus, at the output of the named entity extraction process, there will be, for an entity of Person type, for example in the case of an individual named “Laurent Gbagbo”, a very significant list of variants from the quantitative point of view, including {Laurent Gbabgo, Laurent Gbagbo, L. Gbabgo, L. Gbagbo, etc.}. These variants refer to the same person and must be closely matched to be stored in the knowledge base, in order to ensure knowledge consistency. In the same way, in the Person databases, the individuals are often stored over several records of a database because of errors committed on inputting their name, their address, etc. Then the expression “Laurent Gbago” could be considered as the canonic form entity for all the variants cited above. 
     The issue of matching the named entities or names Of persons is widely discussed in the literature. The proposed methods, according to the knowledge of the Applicant, are principally based on the abovementioned methods of calculating the Levenshtein distance, of phonemization or of calculating similarities separately (without combinations of these techniques). 
     The Levenshtein method when used alone remains almost unusable because it does not give convincing results. Phonemization produces good results for the matching of entities, but it remains dependent on the language and imposes the intervention of experts to develop and maintain the rules of the phonemization device or phonemizer. The calculations of similarity or distance produce good results, which nevertheless remain dependent on the manner in which the named entities are processed (bi-grams only, tri-grams only, etc.). One objective of the present patent application is to optimize the results obtained by combining the abovementioned methods. 
     SUMMARY OF THE INVENTION 
     The inventive method relies, notably, on a combined use of linguistic methods and mathematical methods, notably a measurement of similarity that relies on the Levenshtein distance which measures the similarity between two character streams, the n-grams method, corresponding to a subsequence of n elements constructed from a given sequence, relational analysis and regularized similarity. These different methods are known to those skilled in the art and only reviews necessary to an understanding of the invention will be given in the present patent application. 
     The invention relates to a method making it possible to manage named entities that are presented in different graphical or syntactic forms and refer to the same entity, contained in a database, characterized in that it comprises at least the following steps:
         applying a Levenshtein method to said entities E i  in the database in order to create a similarity between said entities, defining the measurement of similarity between two entities in the following manner       

                 S   l     ⁡     (       E   i     ,     E   j       )       =     1   -       D   ⁡     (       E   i     ,     E   j       )         max   ⁡     (            E   i          ,          E   j            )                 
with S i  being the measurement of similarity between the two entities (E i ,E j ) in the database, D being the Levenshtein distance between the two entities, |E i | respectively |E j | being the number of characters of E i , respectively E j ,
         using the n-grams method to create a similarity S n  (E i ,E j ) between the A entities constituting the database,
 
by extracting from the two entities E i  and E j  the sets N i  of the n-grams of E i  and the set N j  of the n-grams of E j , then defining the number of n-grams |N i | deduced from E i  and the number of n-grams |N j | deduced from E j , the similarity between E i  and E j  is then defined by:
       

     
       
         
           
             
               
                 S 
                 n 
               
               ⁡ 
               
                 ( 
                 
                   
                     E 
                     i 
                   
                   , 
                   
                     E 
                     j 
                   
                 
                 ) 
               
             
             = 
             
               
                 
                    
                   
                     
                       N 
                       i 
                     
                     ⋂ 
                     
                       N 
                       j 
                     
                   
                    
                 
                 
                   min 
                   ⁡ 
                   
                     ( 
                     
                       
                          
                         
                           N 
                           i 
                         
                          
                       
                       , 
                       
                          
                         
                           N 
                           j 
                         
                          
                       
                     
                     ) 
                   
                 
               
               . 
             
           
         
       
         
         
           
             using a method of merging the data on said entities in the database in order to construct at least 2 classifications, respectively relating to the n-grams similarity with n greater than or equal to 2, said classifications corresponding to sets of entity classes P i . 
             finding the consensus partition P c  between the M partitions found, using the canonic form entity E c  to view the result or else modify the entities present in the database through the canonic form entity. 
           
         
       
    
     The merging method implemented can be the relational analysis method. 
     In the relational analysis step, in order to accomplish the relational analysis step to find the consensus partition between the determined partitions, the method uses, for example, the regularized similarity to weight the weight of each partition differently, in the calculation of the overall similarity deduced from the three partitions by executing the following steps the first step is to calculate the density δ i  of each partition P i , 
     this density is a measurement of the aggregation power of the partition concerned and is defined by the relationship: 
               δ   i     =         ∑     k   =   1     K     ⁢           ⁢     n   ik   2           nb   ⁢   _   ⁢   entities     2             
in which κ is the number of classes of the partition P i , n ik  the number of entities of the partition k and nb_entities is the number of entities present in the base, by denoting
 
               Δ   =       ∑     i   =   1     3     ⁢     δ   i         ,         
then the weight Π i  of the partition P i  will be:
 
     
       
         
           
             
               Π 
               i 
             
             = 
             
               0.5 
               × 
               
                 
                   ( 
                   
                     1 
                     - 
                     
                       
                         δ 
                         i 
                       
                       Δ 
                     
                   
                   ) 
                 
                 · 
               
             
           
         
       
     
     The method can include a step for the sending of a request from a user to find the canonic entities in a database and perform the replacement of said entities with the canonic entity found. 
     The invention also relates to a system making it possible to manage named entities that are presented in different graphical or syntactic forms and refer to the same entity, contained in a database in which the method will execute different physical actions at the database level to optimize the quality of the database and consequently obtain a better management thereof, characterized in that it comprises at least the following elements:
         a processor adapted to execute the various steps of the method according to the invention,   an unstructured database, this base can contain texts,   a buffer memory making it possible to store all the data for which the matching is required.       

     The system can also include a device for taking decisions following a request formulated by a user. 
     The system can also include a human-machine interface making it possible to display the classification results of the method presenting at least one of the abovementioned characteristics and the intervention of an operator to modify the initial database by replacing the entities present in the database with the canonic form entity. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Other characteristics and advantages of the device according to the invention will become more apparent from reading the following description of an exemplary embodiment, given as an illustration that is by no means limiting, with appended figures that represent: 
         FIG. 1 , an exemplary system making it possible to implement the method according to the invention, 
         FIG. 2 , a block diagram of the various steps implemented by the method according to the invention, 
         FIG. 3 , an exemplary use of the method after a request sent by a user, and 
         FIG. 4 , an example in the case of a named entity “Pierre Alchantel”. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In order to give a better understanding of the method according to the invention, the first example given is in relation to the management of a database containing a collection of unstructured data. 
       FIG. 1  represents an exemplary system in which the method will execute different physical actions at the database level to optimize the quality of the database and consequently obtain a better management thereof. The system  1  comprises a processor  2  adapted to execute the various steps of the method according to the invention, an unstructured database  3  which can contain texts, a buffer memory  4  which will make it possible to store all the data for which matching is required and possibly a storage database  5  in the case where the canonic data replacing the basic data are not stored in the initial database. The result of this processing will therefore be physical interactions with the databases, notably in the case of replacement of a datum with another datum. 
     The steps implemented by the method are represented in  FIGS. 1 and 2 . The first step E 1  consists in extracting from the collection of unstructured data  3 , using an information extraction mechanism known to those skilled in the art, a list of data consisting of a list of semantically-typed named entities L s , such as names of persons, places, organizations. The latter can be stored temporarily in the buffer memory  4  which will be used to store the data during processing in the case where the processor&#39;s working memory is insufficient. This first step E 1  can consist of a step for pre-processing and applying, linguistic data transformation rules. These pre-processing operations are known to those skilled in the art and will not be explained. For example, in a named entity of Organization type, the forms Ltd will be restored to the form Limited, Corp to the form Corporation, in order to assist the matching of entities such as XXX Limited, XXX Ltd. These pre-processing rules are of two types: some are independent of the categories of entities in the database concerned (passage with poor typography, deletion of punctuation marks, etc.); others are dependent on the categories of entities in the database concerned. The transformation rules are simple and open-ended; they do not require any sophisticated linguistic knowledge. 
     The list of entities pre-processed in this way will be placed in the buffer memory  4 , and the method will apply the matching method according to the invention to this list. For this, the method will execute similarity step E 2  by applying the Levenshtein distance method detailed hereinbelow to the data that are presented in the form of a list of N lines, N being the number of objects or entities to be matched. At the output of the step E 2 , there is a matrix comprising A lines and A columns, the elements E i  of this matrix or table corresponding to a similarity value between two objects. 
     The third step E 3  consists in applying the n-grams method to the outputs of E 2  then in measuring the similarity between the elements or named entities to be matched. 
     A fourth step E 4  will use a merging method, taking into account all the similarity matrices calculated previously. The relational analysis will, for example, be used to do this merging. The aim of the relational analysis is, notably, to determine, in the database being studied, classes of named entities, such that each class consists of all the written forms of one and the same entity. These classes are relative to the similarities defined by the Levenshtein distance method and the n-grams method. The C classifications, in which C is the number of different similarity measurements used, will give C partitions. The method once again uses the relational analysis to find the consensus partition between the C previous classifications, the one that will be the closest, from the C partitions found previously. 
     The method according to the invention will be explained in a more concrete manner through the following detailed example. The example will be given in the non-limiting context of use of the Levenshtein method and of the n-grams for the 2-grams and 3-grams. 
     Another function of the relational analysis is, notably, to consider m entities E i  belonging to one and the same class Ci and find the representative entity. In the context of an automatic process, it is this representative entity that will be stored in a database, which means that the entities initially present in a database will be replaced by their canonic form which is the entity E i  found after the consensus. In the context of a semi-automatic process, it is the user who will chose the representative canonic form. Thus, the initially unclassified data will be replaced by a single form, which will be considered to be the canonic form for all the entities. 
     The algorithm used by the method according to the invention and running on the processor consists of at least the following three parts: 
     Step 1 
     Use of a linguistic pre-processing 
     Step 2 
     Use and transformation of the Levenshtein distance to create a similarity. This transformation is fundamental, since the Levenshtein distance is not normed. In practice, if D(E 1 ,E 2 ) is the Levenshtein distance between the two entities E 1  and E 2 , and if |E 1 |, respectively |E 2 |, is used to denote the number of characters of E 1 , respectively E 2 , the only information that is available on D(E 1 ,E 2 ) is: 0≦D(E 1 ,E 2 )≦max(|E 1 |,|E 2 |). From this relationship, it is possible to define a similarity measurement S l (E 1 ,E 2 ) between the two entities, such that 0≦S l (E 1 ,E 2 )≦1, by the relationship: 
     
       
         
           
             
               
                 S 
                 l 
               
               ⁡ 
               
                 ( 
                 
                   
                     E 
                     1 
                   
                   , 
                   
                     E 
                     2 
                   
                 
                 ) 
               
             
             = 
             
               1 
               - 
               
                 
                   
                     D 
                     ⁡ 
                     
                       ( 
                       
                         
                           E 
                           1 
                         
                         , 
                         
                           E 
                           2 
                         
                       
                       ) 
                     
                   
                   
                     max 
                     ⁡ 
                     
                       ( 
                       
                         
                            
                           
                             E 
                             1 
                           
                            
                         
                         , 
                         
                            
                           
                             E 
                             2 
                           
                            
                         
                       
                       ) 
                     
                   
                 
                 · 
               
             
           
         
       
     
     Use of the n-grams (in particular the 2-grams and 3-grams) to create similarity S n (E 1 ,E 2 ) between entities. To define this similarity, there are extracted from the two entities E 1  and E 2 , the sets N 1  of the n-grams of E 1  and the set N 2  of the n-grams of E 2 , there are then defined the number of n-grams |N 1 | deduced from E 1  and the number of n-grams |N 2 | deduced from E 2 . The similarity between E 1  and E 2  is then defined by: 
                 S   n     ⁡     (       E   1     ,     E   2       )       =                N   1     ⋂     N   2              min   ⁡     (            N   1          ,          N   2            )         ·           
in which |N 1 ∩N 2 | is the number of n-grams common to the two sets N 1  and N 2 .
 
Step 3
 
     There are then constructed, by use of the theory of relational analysis, three classifications, for all the entities present in the database being studied, relative to the three similarities defined hereinabove (the similarity for the 2-grams, the similarity for the 3-grams and the similarity deduced from the Levenshtein distance). These three classifications will therefore give three partitions (three sets of entity classes) P i (i=1, 2, 3). 
     It will then be a matter of using the relational analysis to find the consensus partition P c  between the above three partitions (the one that will be the closest of the three partitions). 
     To accomplish the relational analysis step to find the consensus partition between the previous three partitions, the regularized similarity will be used to weight the weights of each partition differently, in the calculation of the overall similarity deduced from the three partitions. To this end, the first step is to calculate the density δ i  of each partition P i . This density is a measurement of the aggregation power of the partition concerned. It is defined by the relationship: 
               δ   i     =         ∑     k   =   1     K     ⁢     n   ik   2           nb   ⁢   _entities     2             
in which κ is the number of classes of the partition P i , n ik  is the number of named entities in the class k of the partition P i  and nb_entities is the number of entities present in the base. If we use
 
               Δ   =       ∑     i   =   1     3     ⁢     δ   i         ,         
then the weight Π i  of the partition P i  will be:
 
               Π   i     =     0.5   ×       (     1   -       δ   i     Δ       )     ·             
The greater the density of a partition, the less impact it will have in the calculation of the overall similarity.
 
     Another method consists in calculating the similarity S(E i ,E j ) for two named entities E i  and E j , as a combination of different similarities in the following manner:
 
 S ( E   i   ,E   j )= w   1   S   L ( E   i   ,E   j )+ w   2   S   n   2 ( E   i   ,E   j )+ w   3   S   n   3 ( E   i   ,E   j )+ . . . + w   k   S   n   k ( E   i   ,E   j )
 
in which:
         S L (E i ,E j ) is the Levenshtein similarity and S n   2 (E i ,E j ), S n   3 (E i ,E j ), . . . , S n   k (E i ,E j ) are the 2-grams, 3-grams, and so on similarities   w 1 , w 2 , w 3 , . . . , w k  are the weights applied to the different similarities
 
The end result will be a single similarity matrix to which the relational analysis will be applied to obtain a base partition. The relational analysis in this regard will be applied only once. Unlike the proposed method in which it is applied several times (as many times as there are similarities used and one last time for the merging of the different partitions obtained).
       

     The “consensus partition” is the partition that will be the closest of the partitions obtained in the step 3. For example, if the Levenshtein similarity+the 2-grams similarity+the 3-grams similarity are used, then, after the first use of the relational analysis on each of the similarity matrices, there will be three partitions. If we assume that, for the two entities named E i  and E j , the following results are obtained:
         E i  and E j  are in the same class of the partition obtained by the Levenshtein similarity,   E i  and E j  are in the same class of the partition obtained by the 2-grams similarity, but   E i  and E j  are not in the same class of the partition obtained by the 3-grams similarity,       

     Then, these two named entities will be in the same class of the final “consensus partition” because they were together for ⅔ of the partitions (this brings in the vote theory that is the basis of the relational analysis). This also is in line with the meaning of “closest classification” which is quite simply the compromise classification between the different classifications obtained in the sense that we have just explained. 
     The overall similarity at this stage is the sum of the three similarities (weighted thanks to the similarity regularised by weights). The term “overall” simply means that we have changed from individual similarities to a “combination similarity” of the different similarities. 
     The regularised similarity is a method of calculating similarity between the objects of a database, capable of automatically giving more or less significant weights to certain variables measured on the objects of the base. 
     The following explains how to use the relational analysis to obtain this consensus partition: 
     
       
         
           
             
               s 
               ij 
               k 
             
             = 
             
               { 
               
                 
                   
                     1 
                   
                   
                     
                       if 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ( 
                         
                           
                             E 
                             i 
                           
                           , 
                           
                             E 
                             j 
                           
                         
                         ) 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       are 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       in 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       the 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       same 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       class 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       of 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       the 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       partition 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       k 
                     
                   
                 
                 
                   
                     0 
                   
                   
                     otherwise 
                   
                 
               
             
           
         
       
     
     If κ is the number of partitions obtained in the first stage (classification of each of the similarities used individually), the overall similarity s ij , between two named entities E i  and E j , will then be: 
     
       
         
           
             
               s 
               ij 
             
             = 
             
               
                 ∑ 
                 
                   k 
                   = 
                   1 
                 
                 κ 
               
               ⁢ 
               
                 
                   w 
                   k 
                 
                 ⁢ 
                 
                   s 
                   ij 
                   k 
                 
               
             
           
         
       
     
     It is to this similarity that the relational analysis will be applied for the second time to find the consensus partition. 
     If ρ is the number of classes of a given partition P i  and nb_entities the total number of named entities in the base, then the relationship between n ik  and nb_entities is: 
     
       
         
           
             
               nb 
               ⁢ 
               _entities 
             
             = 
             
               
                 ∑ 
                 
                   k 
                   = 
                   1 
                 
                 p 
               
               ⁢ 
               
                 n 
                 ik 
               
             
           
         
       
     
       FIG. 3  diagrammatically represents an exemplary use of the system and of the method according to the invention, by a user represented in the figure by a request  20  which he sends to a database  3  containing, for example, the names of persons, places or organizations, or a set of these entities. The user will, for example, send a request to “search” on a name of a person, a place, an address, etc., and this request sent to the database to be managed will apply the method according to the invention. The processor triggers a step  21  making it possible to search for the close forms or matching method such as that detailed in  FIGS. 1 and 2 . All of the classes of the close forms detected  22  will be transmitted to a decision-making device  23 . This decision-making can be automatic,  24 , if, in the classes found, the similarity of the entities belonging to the class is 1. Conversely, if, in the classes found, the similarity is less than 1, the decision-making involves the user, through a human-machine interface  25 , and it is the user  26  who will control the modification in the database. 
       FIG. 4  represents the implementation of the system of  FIG. 3  in the precise case of an entity named “Pierre Alchantel”. On request from an operator, the method according to the invention will perform a search for the proper forms by applying the method according to the invention. It will obtain all the classes of the “close detected” forms. The analysis and visualization of the persons and associated information will be displayed on a screen  25  in order for the operator to be able to take a decision. 
     In the context of an application to the management of identification, in companies, of individuals, the method according to the invention makes it possible to apply “cleaning” processes to the databases. 
     For applications managing the identification of persons within a company database, the method will make it possible to identify a set of records that refer to a company using a single representative. 
     Also, the method according to the invention makes it possible at a given instant to perform “cleaning” operations on the databases (deleting false duplicates) which in turn will make it possible to merge the information associated with the false duplicates. 
     The method also offers automatic matching processes (not involving the database or knowledge base administrator). 
     The method according to the invention will be applied to numerous fields such as the matching of proper names, such as names of organizations, names of places, the matching of co-referent named entities, the interrogation of databases, the management of data and databases, the management of knowledge and knowledge bases, the management of identification, search for similarities between named entities, between proper names, the merging of data, the automatic processing of natural language.