Behavior based record linkage

• US 9,514,167 B2
• Filed: 08/01/2011
• Issued: 12/06/2016
• Est. Priority Date: 08/01/2011
• Status: Active Grant

• Current Assignee: Qatar Foundation
• Original Assignee: Qatar Foundation
• Inventors: Yakout, Mohamed, Elmagarmid, Ahmed K., Elmeleegy, Hazem, Ouzzani, Mourad, Qi, Yuan
• Primary Examiner(s): Shmatov, Alexey
• Assistant Examiner(s): Mueller, Kurt
• Application Number:
  US13/195,319
• Publication Number:
  US 20130036119A1
• Time in Patent Office: 1,954 Days
• Field of Search: 707/737
• US Class Current: 1/1
• 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/24558 Binary matching operations

Abstract

A computer implemented method for matching data records from multiple entities comprising providing respective transaction logs for the entities representing actions performed by or in respect of the entities, determining a matching score using the transaction logs for respective pairs of the entities and for predetermined combinations of merged entities by generating a measure representing a gain in behavior recognition for the entities before and after merging, and using the gain as a matching score.

Claims

1. A computer implemented method, with at least one step executed by a computer, the method for matching data records from multiple entities to identify if the multiple entities are the same entity, comprising:

providing respective transaction logs for the multiple entities representing actions performed by or in respect of the multiple entities;

extracting behavior data for the multiple entities from the transaction logs;

determining candidate entity matches between pairs of entities using the behavior data of each entity of the pair by generating pairs of entity matches and using those pairs not discarded by a coarse matching function as candidate entity matches;

merging the behavior data of each pair of candidate entity matches to generate a merged behavior matrix for each pair;

calculating a behavior recognition score for the merged behavior matrix and for each entity of the pair of candidate entity matches;

determining a gain from the behavior recognition score for each entity of the pair of candidate entity matches to the recognition score for the merged behavior matrix of the respective pair of candidate entity matches;

determining a matching score for each pair of candidate entity matches using the gain in behavior recognition score, wherein the gain in behavior recognition score is indicative of the two entities in the pair of candidate entity matches being the same entity;

identifying which entities represent the same entity among the multiple entities if the matching score is above a predetermined threshold; and

associating the identified matching entities of the multiple entities as the same entity.

2. A method as claimed in claim 1, further comprising converting the transaction logs to a predetermined format to provide a processed log including data from the transaction logs and a set of identifiers representing combinations of features for respective actions.

3. A method as claimed in claim 2, further comprising generating a behavior matrix for an entity using the identifiers.

4. A method as claimed in claim 3, further comprising generating a first element of a discrete Fourier transform for a binarised behavior matrix in which non zero values are replaced with the value “

1”

to provide a complex number representing an action in the behavior matrix.

5. A method as claimed in claim 4, wherein the inverse of the magnitude of the complex number represents a recognition score for an action of an entity.

6. A method as claimed in claim 1, wherein determining a matching score includes determining if a merged entity exhibits a consistent behavior compared to a behavior pattern of actions for the individual entities.

7. A method as claimed in claim 1, wherein determining a matching score includes determining the behavior recognition score for a behavior of an entity representing consistency of the entities behavior over multiple components.

8. A method as claimed in claim 7, wherein the multiple components include a measure representing consistency in repeating actions, a measure representing stability in features describing actions, and a measure representing association between actions.

9. A method as claimed in claim 1, further comprising generating a statistical model for the behavior of an entity using the transaction log for that entity, wherein parameters of the model are used to determine a measure for repeated patterns in a sequence corresponding to action occurrences for an entity.

10. A method as claimed in claim 1, comprising using the transaction logs of the entities to generate the measure representing the gain in the behavior recognition score, wherein the behavior recognition score represents the similarity in behaviors between the entities.

11. A computer program embedded on a non-transitory tangible computer readable storage medium, the computer program including machine readable instructions that, when executed by a processor, implement a method for matching data records from multiple entities to identify if the multiple entities are the same entity, comprising:

providing respective transaction logs for the multiple entities representing actions performed by or in respect of the multiple entities;

extracting behavior data for the multiple entities from the transaction logs;

determining candidate entity matches between pairs of entities using the behavior data of each entity of the pair by generating pairs of entity matches and using those pairs not discarded by a coarse matching function as candidate entity matches;

merging the behavior data of each pair of candidate entity matches to generate a merged behavior matrix for each pair;

calculating a behavior recognition score for the merged behavior matrix and for each entity of the pair of candidate entity matches;

determining a gain from the behavior recognition score for each entity of the pair of candidate entity matches to the recognition score for the merged behavior matrix of the respective pair of candidate entity matches;

determining a matching score for each pair of candidate entity matches using the gain in behavior recognition score, wherein the gain in behavior recognition score is indicative of the two entities in the pair of candidate entity matches being the same entity;

identifying which entities represent the same entity among the multiple entities if the matching score is above a predetermined threshold; and

associating the identified matching entities of the multiple entities as the same entity.

12. A computer program embedded on a non-transitory tangible computer readable storage medium as claimed in claim 11, the computer program including machine readable instructions that, when executed by a processor, implement a method for matching data records from multiple entities further comprising converting the transaction logs to a predetermined format to provide a processed log including data from the transaction logs and a set of identifiers representing combinations of features for respective actions.

13. A computer program embedded on a non-transitory tangible computer readable storage medium as claimed in claim 12, the computer program including machine readable instructions that, when executed by a processor, implement a method for matching data records from multiple entities further comprising generating a behavior matrix for an entity using the identifiers.

14. A computer program embedded on a non-transitory tangible computer readable storage medium as claimed in claim 13, the computer program including machine readable instructions that, when executed by a processor, implement a method for matching data records from multiple entities further comprising generating a first element of a discrete Fourier transform for a binarised behavior matrix in which non zero values are replaced with the value “

1”

to provide a complex number representing an action in the behavior matrix.

15. A computer program embedded on a non-transitory tangible computer readable storage medium as claimed in claim 14, the computer program including machine readable instructions that, when executed by a processor, implement a method for matching data records from multiple entities, wherein the inverse of the magnitude of the complex number represents a recognition score for an action of an entity.

16. A computer program embedded on a non-transitory tangible computer readable storage medium as claimed in claim 11, the computer program including machine readable instructions that, when executed by a processor, implement a method for matching data records from multiple entities wherein determining a matching score includes determining if a merged entity exhibits a consistent behavior compared to a behavior pattern of actions for the individual entities.

17. A computer program embedded on a non-transitory tangible computer readable storage medium as claimed in claim 11, the computer program including machine readable instructions that, when executed by a processor, implement a method for matching data records from multiple entities wherein determining a matching score includes determining the behavior recognition score for a behavior of an entity representing consistency of the entities behavior over multiple components.

18. A computer program embedded on a non-transitory tangible computer readable storage medium as claimed in claim 17, the computer program including machine readable instructions that, when executed by a processor, implement a method for matching data records from multiple entities wherein the multiple components include a measure representing consistency in repeating actions, a measure representing stability in features describing actions, and a measure representing association between actions.

19. A computer program embedded on a non-transitory tangible computer readable storage medium as claimed in claim 11, the computer program including machine readable instructions that, when executed by a processor, implement a method for matching data records from multiple entities further comprising generating a statistical model for the behavior of an entity using the transaction log for that entity, wherein parameters of the model are used to determine a measure for repeated patterns in a sequence corresponding to action occurrences for an entity.