What is Entity Resolution?

Combine

The first step is getting all the data and combining it into a common schema. In a perfect world, there would be one global database containing all the data in a single schema. In practice however, there are usually multiple datasets stored in various systems and formats. There might be a relational database to store clients of a shop and a NoSQL for their reviews of products; these could be duplicated between countries or overlap. There could also be a legacy system which is not yet decommissioned and can only return one row at a time in some obscure format. Though cumbersome, centralising the data across multiple sources is essential.

The remaining challenge is deciding on a common schema. Which fields are relevant? Do we need to know in which country is John Doe born? Is it relevant that he’s a foreigner? Is his birthday actually a date type? After answering these questions and combining the data, one can finally continue with the next steps.

Let’s say we have two data sources that store clients of a company across different branches. Each branch has their own database and schema. Notice how, after combination, the source columns have been selected, mapped appropriately and to the right data type. Also observe how the column nationality, deemed irrelevant, was removed from the resulting table.

Clean

The second step is making sure that the data is clean and in the same format. Each data source might require different actions in order to reach a common schema but all data must pass through the same cleaning steps; thus, we perform it after combining.

One of the first things to check is whether the data has the same encoding. Not only do we want to make sure that we don’t see odd ’ characters but also that languages conform to a common translation. A typical choice is converting everything to ASCII. Doing so, Müller and Muller might then become the same. But what about Mueller? Moreover, case isSuES should also be avoided by either uppercasing or lowercasing everything. And what about languages that do not even use the latin alphabet?

Take a look below at the simplistic example for some of these steps, that tackles standardization for characters of the German language using pandas and a dictionary that defines the rules for conversion.

import pandas as pdde_mapping = {'Ü': 'U', 'Ä': 'A', 'Ö': 'O', 'ß': 'SS'}
trans_table = 
''.join(de_mapping.keys()).maketrans(de_mapping)

df = pd.DataFrame({'family_name': ['Muller', 
'Müller', 'Mueller']})
df['cleaned_family_name'] = 
df['family_name'].str.upper()
df['cleaned_family_name'] = 
df['cleaned_family_name'].str.translate(trans_table)

One must also pay attention to whether the cleaning steps should be done in a certain order. For example, the difference between the german words schon (already) and schön (beautiful) would be lost if converting ö to o, and this could be a relevant loss of information in certain situations. Dates can also be tricky — they can not only be stored under different types, e.g. integer or string, but they also have different formats and precision.

Block

Trying to find all possible matches is a computationally expensive process. Computing all the pairs has n² complexity in both time and space, which is very expensive when dealing with millions of records. For example, a dataset of only 1,000 rows would yield 499,500 possible combinations! In order to optimise, we want to only save good potential pairs using a limited number of columns and computations. This is known as blocking. The problem becomes then choosing the right rules such that as many possible matches are found.

Following the same example, let’s try blocking on some simple rules. Creating possible links between people with the same last name correctly omits pairs such as MUELLER and ROSS. However, one might also notice some downsides: MULLER and MUELLER would not be paired. So, let’s add another rule — same birthday. Beware that blocking will be done on the same family name or the same birthday. See below how these rules successfully block our Peter Muller (-like) entries while omitting pairs such as John Dough and Bob Ross. Note how, even though both rules are satisfied in the case of PIETER MULLER/PETER MULLER pair, a single row is produced.

In practice, the rules typically rely on more complex logic. Good blocking requires finding the right balance of relaxed yet effective rules. For example, exact name matches are likely to miss typos or errors in translation. In such cases, one could try fuzzy matching or phonetic algorithms like soundex. We’ll talk about this and more in our next post.

Featurize

This is the step where data scientists and machine learning experts can finally use their creativity in finding the appropriate features to entity resolve. With possible edges created, we now need reliable ways to measure the similarity of the entities. Since we are dealing with string columns, we could use string similarity metrics such as Levenshtein or Jaccard distance.

The example below contains an example of using Jellyfish to calculate the Levenshtein distance between two names. In order to increase interpretability and comparability, the next step converts the distance into a similarity metric. To do that, the distance is divided by the maximum length of the two compared strings, then subtracted from 1.

import pandas as pd
from jellyfish import levenshtein_distance

def normalized_levenshtein(name_left, name_right):
    distance = levenshtein_distance(name_left, name_right)
    return 1 - distance / max(len(name_left), len(name_right))df = pd.DataFrame(
    {'name_left': ['PIETER MUELLER'],
     'name_right': ['PETER MULLER']}
)
df['levenshtein_full_name'] = df.apply(
lambda x: normalized_levenshtein(x.name_left, x.name_right), axis=1)

An interesting example is when dealing with long(er) strings, such as Peter Mueller and Mueller Peter. Simply using a string similarity metric would result in a bad score when they are obviously the same (to us). Here, sorting the words could help. However, the same tactic might not be as useful for addresses. Simply because there are missing parts of the addresses does not mean the records are different; there might still be a lot in common! One could try splitting the address into components and computing the intersection.

Match

Tightly connected to the previously chosen features, you can now either use specific rules and/or leave it to a model to classify the pairs. With sufficiently clean data, rules might correctly label the vast majority of the data. In our example, choosing pairs with the Levenshtein similarity of the first name above 0.9 would only match our first PETER MUELLER/MULLER pair and ignore the other two possible combinations. This would be too restrictive if we would like to also match PETER MUELLER/PIETER MULLER or PIETER/PETER MULLER. Moreover, observe how not using the exact birthday in the matching process would lead our last pair to also be matched, even though they cannot be the same person — they just have the same full name. Rules are easy to create but tricky to perfect. For the purpose of this example, let’s choose a Levensthein similarity >= 0.85 AND exact birthday = 1. Therefore, in the end we will obtain four clusters.

A model could ease the process by implicitly finding the correct rules to match records. Neural networks have shown great potential in NLP tasks in the recent years and are known to do exactly this. However, such a black box model has little explainability and is hard to justify to the business that would like to know why records were matched. One could instead use a supervised model such as Random Forest or even attempt unsupervised techniques such as the Expectation-Maximization algorithm. Good data and model tuning remain furthermore of high importance.

Whichever path is chosen, iterating the model remains a task closely tied to business goals. Some might require that the pipeline has high confidence (low number of false positives), others might require returning every possibility (low number of false negatives); both would be of course ideal. Evaluating the performance can be done in various ways. We have hinted on using the confusion matrix, however this has its limitations. We’ll go over other metrics and their pros and cons in an upcoming blog post.

Conclusion