RECORD LINKAGE BASED ON A TRAINED BLOCKING SCHEME

• US 20130212103A1
• Filed: 02/13/2012
• Published: 08/15/2013
• Est. Priority Date: 02/13/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cao, Yunbo, Lin, Chin-Yew, Chen, Zhiyuan, Yue, Pei
• Granted Patent: US 8,843,492 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors

Abstract

Some implementations disclosed herein provide techniques and arrangements to train a blocking scheme using both labeled data and unlabeled data. For example, training the blocking scheme may include iteratively: learning a conjunction, identifying first matches in the labeled data and the unlabeled data that are uncovered by the conjunction, and identifying second matches in the labeled data and the unlabeled data that are covered by the conjunction. The conjunction learned in each iteration may be combined using a disjunction. A search engine may use the search engine when searching for records that match an entity.

Claims

1. A method under control of one or more processors configured with executable instructions, the method comprising:

selecting a set of unlabeled data;

selecting a set of labeled data;

learning one or more conjunctions;

identifying matches in the labeled data and the unlabeled data that are uncovered by each of the one or more conjunctions;

identifying the matches in the labeled data and the unlabeled data that are covered by each of the one or more conjunctions; and

combining the one or more conjunctions to create a blocking scheme.

2. The method of claim 1, wherein the blocking scheme comprises a disjunction of a conjunction of blocking predicates.

3. The method of claim 1, wherein the blocking scheme is trained using at least the unlabeled data and the labeled data.

4. The method of claim 3, wherein the blocking scheme is trained to maximize a number of true matches in a candidate set generated from the labeled data.

5. The method of claim 3, wherein the blocking scheme is trained to minimize a number of candidate matches from the unlabeled data and the labeled data.

6. The method of claim 1, further comprising modifying a precision threshold parameter associated with the blocking scheme to increase a precision of the blocking scheme or to increase a recall of the blocking scheme.

7. The method of claim 1, wherein the blocking scheme is trained using a distribution of blocking attributes over the unlabeled data.

8. Computer-readable media including instructions executable by one or more processors to perform operations comprising:

identifying multiple sets of records;

grouping, based on a blocking scheme, records selected from the multiple sets of records to create blocks of records, the blocking scheme trained using training data that comprises at least a sample of unlabeled data;

comparing the records within each block of the blocks of records; and

identifying matching records that refer to a same entity based on the comparing to create linked records.

9. The computer-readable media of claim 8, wherein the blocking scheme is trained using training data that further comprises labeled data.

10. The computer-readable media of claim 9, wherein the blocking scheme training comprises:

identifying uncovered matches in the labeled data;

learning one or more conjunctions;

identifying matches in the labeled data and the unlabeled data that are uncovered by each of the one or more conjunctions;

identifying the matches in the labeled data and the unlabeled data that are covered by each of the one or more conjunctions; and

combining the one or more conjunctions.

11. The computer-readable media of claim 8, wherein the blocking scheme is trained to increase a number of true matches identified in a candidate set generated from labeled data.

12. The computer-readable media of claim 8, wherein the blocking scheme is trained to decrease a number of candidate matches identified based on the unlabeled data and labeled data.

13. The computer-readable media of claim 8, wherein the blocking scheme is trained using a distribution of blocking attributes over the unlabeled data.

14. A computing device comprising:

one or more processors;

computer-readable media including instructions executable by the one or more processors to perform acts comprising;

learning a blocking scheme from a set of labeled data and unlabeled data, the learning comprising repeatedly performing the following acts until particular criteria are satisfied;

learning a conjunction;

identifying first matches in the labeled data and the unlabeled data that are uncovered by the conjunction;

identifying second matches in the labeled data and the unlabeled data that are covered by the conjunction; and

combining the conjunction learned in each iteration.

17. The computing device of claim 16, wherein:

a first conjunction is learned in a first iteration and a second conjunction is learned in the second iteration that occurs after the first iteration; and

the first conjunction includes one or more predicates.

18. The computing device of claim 17, wherein the second conjunction includes at least one more predicate than the first conjunction.

19. The computing device of claim 17, wherein combining the conjunction learned in each iteration comprises creating a disjunction of the conjunction learned in each iteration.

20. The computing device of claim 16, further comprising performing a search on multiple sets of records to identify records that match an entity based on the blocking scheme.