Statistical record linkage calibration for multi token fields without the need for human interaction

• US 8,135,679 B2
• Filed: 04/24/2009
• Issued: 03/13/2012
• Est. Priority Date: 04/24/2008
• Status: Active Grant

• Current Assignee: LexisNexis Risk Solutions, Inc. (RELX PLC)
• Original Assignee: LexisNexis Risk Solutions, Inc. (RELX PLC)
• Inventors: Bayliss, David Alan
• Primary Examiner(s): Thai, Hanh
• Application Number:
  US12/429,337
• Publication Number:
  US 20090292694A1
• Time in Patent Office: 1,054 Days
• Field of Search: 707687-749
• US Class Current: 707/688
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Disclosed is a system for, and method of, calculating parameters used to determine whether records and entity representations should be linked. The system and method utilize blended field weights to account for certain types of partial matches. The system and method apply iterative techniques such that parameters from each linking iteration are used in the next linking iteration. The system and method need no human interaction in order to calibrate and utilize record matching formulas used for the linking decisions.

Claims

1. A computer implemented iterative process for generating entity representations in a computer implemented database using a record matching formula and for generating parameters for the record matching formula, each entity representation comprising at least one record, the database comprising a plurality of records, each record comprising a plurality of fields, each field capable of containing a field value, each field value comprising at least one token, wherein at least a portion of parameters for the record matching formula are configured for a first particular field value and a non-identical second particular field value, the first particular field value and a second particular field value associated with a selected field, the first particular field value comprising a plurality of particular tokens, wherein the process provides for linking records and entity representations with non-identical field values, the process comprising:

calculating, for each of the plurality of particular tokens, an associated token weight, each token weight comprising a logarithm of a first probability that an arbitrary record in the database comprises the associated particular token in the selected field of the arbitrary record, wherein each first probability comprises a ratio of records in the database that contain an associated particular token to a total number of records in the database;

calculating a field value weight, the field value weight comprising a logarithm of a second probability that an arbitrary record in the database comprises the first particular field value in the selected field of the arbitrary record, wherein the second probability comprises a ratio of records in the database that contain the particular field value to a total number of records in the database;

calculating a blended field value weight for the first particular field value and the second particular field value, the blended field value weight for the first particular field value and the second particular field value being derived from at least the token weights associated with each of the plurality of particular tokens and from the field value weight;

forming a plurality of entity representations in the database, each entity representation comprising at least two records linked using a first instance of the record matching formula, at least one entity representation comprising a first record comprising the first particular field value and a second record comprising the second particular field value, the first record linked to the second record using a first instance of the record matching formula that comprises the blended field value weight;

calculating, for each of the plurality of particular tokens, an associated revised token weight, each revised token weight comprising a logarithm of a third probability that an arbitrary entity representation in the database comprises a record comprising the associated particular token, wherein each third probability comprises a ratio of records in the database that contain an associated particular token to a total number of records in the database;

calculating a revised field value weight, the revised field value weight comprising a logarithm of a fourth probability that an arbitrary entity representation in the database comprises the first particular field value in the selected field of a record comprising the arbitrary entity representation, wherein the fourth probability comprises a ratio of records in the database that contain the first particular field value to a total number of records in the database;

calculating a revised blended field value weight for the first particular field value and the second particular field value, the revised blended field value weight for the first particular field value and the second particular field value being derived from at least the revised token weights associated with each of the plurality of particular tokens and from the revised field value weight;

linking at least two entity representations in the database based on a second instance of the record matching formula, wherein the second instance of the record matching formula comprises the revised blended field value weight, whereby a number of entity representations in the database is reduced by the linking at least two entity representations relative to a number of entity representations in the database prior to the linking at least two entity representations; and

retrieving information from at least one record in the database.

2. The process of claim 1 further comprising repeating the calculating, for each of the plurality of particular tokens, an associated revised token weight, the calculating a revised field value weight, the calculating a revised blended field value weight, and the linking at least two entity representations at least once.

3. The process of claim 1 wherein the calculating the blended field value weight comprises calculating a sum of token weights associated with tokens that appear in the selected field of both of the first record and the second record, and calculating a sum of token weights associated with tokens that appear in the selected field of exactly one of the first record and the second record.

4. The process of claim 1 wherein the calculating the blended field value weight comprises calculating a maximum between (1) a probability reflecting a likelihood that an arbitrary record in the database comprises, in the selected field of the arbitrary record, the first particular field value, and (2) a probability reflecting a likelihood that an arbitrary record in the database comprises, in the selected field of the arbitrary record, the second particular field value.

5. The process of claim 1 wherein the calculating the blended field value weight comprises calculating a minimum between (1) a probability reflecting a likelihood that an arbitrary record in the database comprises, in the selected field of the arbitrary record, the first particular field value, and (2) a probability reflecting a likelihood that an arbitrary record in the database comprises, in the selected field of the arbitrary record, the second particular field value.

6. The process of claim 1 wherein the calculating the blended field value weight comprises calculating at least one of

7. A computer system for iteratively generating entity representations in a computer implemented database using a record matching formula and for generating parameters for the record matching formula, each entity representation comprising at least one record, the database comprising a plurality of records, each record comprising a plurality of fields, each field capable of containing a field value, each field value comprising at least one token, wherein at least a portion of parameters for the record matching formula are configured for a first particular field value and a non-identical second particular field value, the first particular field value and a second particular field value associated with a selected field, the first particular field value comprising a plurality of particular tokens, wherein the process provides for linking records and entity representations with non-identical field values, the system comprising:

a computer implemented database comprising a plurality of records, each record comprising a plurality of fields, each field capable of containing a field value, each field value comprising at least one token;

a processor programmed to calculate, for each of the plurality of particular tokens, an associated token weight, each token weight comprising a logarithm of a first probability that an arbitrary record in the database comprises the associated particular token in the selected field of the arbitrary record, wherein each first probability comprises a ratio of records in the database that contain an associated particular token to a total number of records in the database;

a processor programmed to calculate a field value weight, the field value weight comprising a logarithm of a second probability that an arbitrary record in the database comprises the first particular field value in the selected field of the arbitrary record, wherein the second probability comprises a ratio of records in the database that contain the particular field value to a total number of records in the database;

a processor programmed to calculate a blended field value weight for the first particular field value and the second particular field value, the blended field value weight for the first particular field value and the second particular field value being derived from at least the token weights associated with each of the plurality of particular tokens and from the field value weight;

a processor programmed to form and store a plurality of entity representations in the database, each entity representation comprising at least two records linked using a first instance of the record matching formula, at least one entity representation comprising a first record comprising the first particular field value and a second record comprising the second particular field value, the first record linked to the second record using a first instance of the record matching formula that comprises the blended field value weight;

a processor programmed to calculate, for each of the plurality of particular tokens, an associated revised token weight, each revised token weight comprising a logarithm of a third probability that an arbitrary entity representation in the database comprises a record comprising the associated particular token, wherein each third probability comprises a ratio of records in the database that contain an associated particular token to a total number of records in the database;

a processor programmed to calculate a revised field value weight, the revised field value weight comprising a logarithm of a fourth probability that an arbitrary entity representation in the database comprises the first particular field value in the selected field of a record comprising the arbitrary entity representation, wherein the fourth probability comprises a ratio of records in the database that contain the first particular field value to a total number of records in the database;

a processor programmed to calculate a revised blended field value weight for the first particular field value and the second particular field value, the revised blended field value weight for the first particular field value and the second particular field value being derived from at least the revised token weights associated with each of the plurality of particular tokens and from the revised field value weight; and

a processor programmed to link and store at least two entity representations in the database based on a second instance of the record matching formula, wherein the second instance of the record matching formula comprises the revised blended field value weight, whereby a number of entity representations in the database is reduced by linking the at least two entity representations relative to a number of entity representations in the database prior to the linking at least two entity representations.

8. The system of claim 7 wherein the processor programmed to calculate a blended field value weight is programmed to calculate a sum of token weights associated with tokens that appear in the selected field of both of the first record and the second record, and calculate a sum of token weights associated with tokens that appear in the selected field of exactly one of the first record and the second record.

9. The system of claim 7 wherein the processor programmed to calculate the blended field value weight is programmed to calculate a maximum between (1) a probability reflecting a likelihood that an arbitrary record in the database comprises, in the selected field of the arbitrary record, the first particular field value, and (2) a probability reflecting a likelihood that an arbitrary record in the database comprises, in the selected field of the arbitrary record, the second particular field value.

10. The system of claim 7 wherein the processor programmed to calculate the blended field value weight is programmed to calculate a minimum between (1) a probability reflecting a likelihood that an arbitrary record in the database comprises, in the selected field of the arbitrary record, the first particular field value, and (2) a probability reflecting a likelihood that an arbitrary record in the database comprises, in the selected field of the arbitrary record, the second particular field value.

11. The system of claim 7 wherein the processor programmed to calculate the blended field value weight is programmed to calculate at least one of