Cost-sensitive alternating decision trees for record linkage
Record Linkage (RL) is the task of identifying two or more records referring to the same entity (e.g., a person, a company, etc.). RL models can be based on Cost Sensitive Alternating Decision Trees (ADTree), an algorithm that uniquely combines boosting and decision trees algorithms to create shorter and easier-to-interpret linking rules. These models can be naturally trained to operate at industrial precision/recall operating points, and the shorter output rules are so clear that it can effectively explain its decisions to non-technical users via score aggregation or visualization. The models significantly outperform other baselines on the desired industrial operating points, and the improved understanding of the model's decisions led to faster debugging and feature development cycles.
1. A record linkage method comprising:
(a) acquiring data with a computer processing arrangement executing program instructions and connected to an electronic network;
(b) blocking, with the computer processing arrangement, the acquired data to find and block similar data into a blocked database;
(c) applying, with the computer processing arrangement, a feature set with a machine learning model based at least in part on cost-sensitive alternating decision trees to selectively link the blocked acquired data in the blocked database;
(d) storing the selectively-linked data in computer memory; and
(e) enabling users to access and search said selectively-linked data via said electronic network,
wherein the computer processing arrangement trains the cost-sensitive alternating decision trees from a plurality of training examples in a training database; assigns, prior to the training, the plurality of training examples with a plurality of non-uniformly distributed cost factors for the training to quantify the cost of misclassifying, and updates a weight distribution in a biased manner towards training examples with higher costs.
2. A non-transitory storage medium arrangement storing computer program instructions that operate on plural records, said storage medium arrangement storing the following computer program instructions:
(a) blocking instructions that control the computer to block the plural records and store the blocked plural records in a blocked database;
(b) training instructions that control the computer to train a machine learning model based at least in part on cost-sensitive alternating decision trees using a plurality of training examples in a training database; prior to the training, assign the plurality of training examples with a plurality of non-uniformly distributed cost factors for the training to quantify the cost of misclassifying; and update a weight distribution in a biased manner towards training examples with higher costs; and
(c) applying instructions that apply a feature set with the generated machine learned model to selectively link the blocked plural records in the blocked database.
3. The non-transitory storage medium arrangement of claim 2 wherein the storage medium arrangement further stores execution instructions that use said learned model to determine whether to link records.
4. The non-transitory storage medium arrangement of claim 3 wherein the execution instructions use said learned model to link records by classifying a pair of records in a database into match or unmatch.
5. The non-transitory storage medium arrangement of claim 2 wherein the training instructions provide for recall at precisions in excess of 99%.
6. The non-transitory storage medium arrangement of claim 2 wherein the training instructions generate a learned model that is understandable by humans.
7. The non-transitory storage medium arrangement of claim 2 wherein the training instructions assign a cost factor c i ε(0, ∞) to each training example x i ,y i in the training database to quantify the cost of misclassifying x, into a class label other than y i .
8. The non-transitory storage medium arrangement of claim 2 wherein the training instructions provide boosting to derive a classifier from the plurality of training examples in the training database.
9. A method of operating on plural records comprising:
(a) with a computing arrangement, blocking the plural records to provide a blocked database;
(b) training, with the computing arrangement, a plurality of training examples in a training database to generate a machine learned model using a cost-sensitive alternating decision tree, the computing arrangement prior to the training assigning the plurality of training examples with a plurality of non-uniformly distributed costs for the training to quantify the cost of misclassifying, and updating a weight distribution in a biased manner towards training examples with higher costs; and
(c) applying, with the computing arrangement, a feature set with the generated machine learned model to selectively link the blocked plural records in the blocked database.
10. The method of claim 9 further including using said learned model to determine whether to link records in the blocked database.
11. The method of claim 10 further including using said learned model to link records by classifying a pair of records in a database into match or unmatch.
12. The method of claim 9 further including providing for recall at precisions in excess of 99%.
13. The method of claim 9 further including generating a learned model that is understandable by humans.
14. The method of claim 9 further including boosting to derive a classifier from the training database.
15. A system for operating on plural records comprising:
a computer-based blocker that finds similar records and blocks the similar records to provide a blocked database;
a computer-based machine learner that uses at least one processor to train on a plurality of training examples in a training database to generate a machine learned model using an alternating decision tree, the computer-based machine learner prior to the training assigning the plurality of training examples with a plurality of non-uniformly distributed costs for the training to quantify the cost of misclassifying, and updating a weight distribution in a biased manner towards training examples with higher costs;
a computer-based linker that applies a feature set with the generated machine learned model to selectively link the blocked similar records in the blocked database; and
a computer-based execution component connected to the Internet that provides a background check or an identity check on demand at least in part in response to records linked based on said machine-learned model in response to a user search requested over the Internet.