Following on from the previous post, here’s my own recipe for a people-matching system. I don’t go into all the gory technical details – the post would be five times the length – but I hope there’s enough here to get the theme across.
We have a large number of Person records (millions?), all from the UK.
We believe that a significant proportion of these records are duplicates or redundant, as they represent the same people; but the details may differ.
The quality of data in each Person record varies, maybe markedly; some records may be customers we have a long-standing relationship with, and are very confident of their details. But other records might come from less trusted or unverified sources, e.g. a survey on the website that promises a voucher in return for answering some questions and entering a few personal details; these details would clearly be less reliable.
, plus a unique PersonID. We might have other data points available, e.g. home telephone number, employment details, bank account number / sort code, and we could absolutely use them for matching. For now, we’ll concentrate on the six above.
Every Person record only has one set of details, that is, just the six pieces of information that we’ll use for matching. This restriction isn’t that realistic – people can have more than one mobile number or email address, and they move house, and occasionally change their names. Taking this into account in a system doesn’t significantly alter the structure of what’s being proposed here.
For each one of these data points, we want to generate and store what is known as the canonical version: that is, the version that is as standard as we can possibly make it. For names, the simplest thing to do is remove spaces, hyphens and apostrophes, which will help us match “Peter O’Toole” against “Peter Otoole”, or “Andrew Lloyd Webber” against “Andrew Lloyd-Webber”. Dates of birth don’t need changing, as long as they’re being stored in a sensible format (so in SQL we should be using DATE, and not VARCHAR). Phone numbers might be accepted in our system as “+442077319333” or “020 7731 9333”, but we need to translate them into one format – I’d go for the former.
Email addresses: As mentioned in the the previous post, email domains can be synonyms of each other, e.g. gmail.com and googlemail.com. Depending on your data, making domains canonical might be too much effort. Also, with some providers (including gmail) the local part of the address (the left-hand side of the @ symbol) can contain labels, so you’ll need to strip those out to make the canonical version.
Addresses: Making canonical versions of bricks-and-mortar addresses can be the biggest headache, which is why you’ll need an address validator: a piece of software that takes an unformatted address, and turns it into a formatted address. Examples of address validators include PCA Predict (formerly Postcode Anywhere) and Experian Data Quality (formerly QAS). The way they work is that if we present, e.g.
If you pay for the extra data, then you can get the UDPRN (Unique Delivery Point Reference Number), which maps every postal address into an 8-digit code. If not, you can make your own loose version of it by hashing the text of the validated address, which you can then use for comparing.
From this point on, I’ll assume (a) that all our data points are canonical, and (b) there are no known ‘test’ people within our data – if there are, we should remove them from any matching process.
Next, we’ll need to consider generating lists of common and/or dummy data. For example, what are the most popular mobile numbers in the data?
with some surprisingly large counts against each. You clearly can’t use these mobile numbers for matching; in fact, you should look at all the associated Person records, to see if it’s worth excluding everyone with obvious dummy numbers like these. But you’ll probably just want to exclude this data point from the match, not exclude the entire Person record.
We’re at the point where our data is as standard (canonical) as we can make it, and we have lists (tables) of data points we know we’re NOT going to be matching.
, i.e. every single piece of information – but that’s the most obvious case, and there are certainly subsets of these details that we’d be happy to accept.
where Set 1 is the best, and Set 7 the ‘least best’. (You, and your data, of course may disagree.) So, every single piece of information in a set has to be identical between person A and person B for us to consider it a match.
Note that no set of details is a subset of any other; the larger set of details would be redundant.
For each Person record, we’ll make (up to) 7 separate hashes, one for each set of details, and store them in a new table. An MD5 hash takes up 16 bytes, so if we had a million records, it’s a maximum of 150MB in space (if we include numeric IDs for the Person and for the set of details).
Finding hard matches between Person records then becomes as simple as finding hashes with more than one PersonID entry in our table – a simple GROUP BY, which if indexed properly, will be lightning quick.
Do nothing. Depending on our requirements, this might be ok; in the grand scheme of things, what’s a handful of duplicate emails / letters / phone calls?
Manual matching. Again, depending on our situation, this might be perfectly feasible. If there’s any human intervention (for example, a phone call) in our end-to-end process, then it could be straightforward to give your customer-facing employees a screen that says “We’ve found these sets of details that might be the same person, do you agree?”, then let them approve or reject the match.
Scoring. Give various amounts of points to each part of the match criteria, depending on the strength of match between data points. If you like, you can consider this a soft match (cf. the hard matching above).
The goal is to come up with a scoring mechanism such that likely matches get more ‘points’ than unlikely ones. Outside of some Very Hard Computer Science (probably involving neural networks), I don’t know of any standard ways of generating scorecards where the outcome is unknown – if the outcome is known, then standard methods apply (Google: Building a scorecard.) However, for this particular application, common sense should get us where we want to go.
For string data like names (first or last), we can make an educated guess at a scoring mechanism, e.g.
I don’t know that the above is optimal, but it feels like a good starting point.
How do we assess how far apart strings are? We need a function that, given two strings, calculates some notion of ‘distance’ between them. Such functions already exist, and the Levenshtein distance (the number of insert/replace edits needed to turn one string into another) is a popular choice.
etc. I’m sure you get the idea: the point is we have lots of options!
Hence, we build up a scorecard that takes two sets of details and returns a single number, a score. We can apply this scoring function to every pair of details in our candidate list, and generate a score for all matches. Inspecting these matches by eye, it becomes fairly obvious what a good threshold for acceptance would be, and what changes to our scorecard are needed. Within a few iterations, we should have a scorecard and threshold that give us the balance we need between matching correct sets of details (where correctness is assessed by eye, by manually checking a sample), and not matching incorrect sets of details.
The scorecards can get as complicated as you like: you can award extra points for an uncommon domain in the email addresses, or for having the same post town, or the same home phone number area code; you can subtract points for too many repeated digits in the mobile numbers, or having 1st January as the date of birth, or having a common name (‘John Smith’). The law of diminishing returns applies in spades – you have to determine whether the extra effort is warranted.
One very important thought: you MUST record exactly how a match between two sets of details was made. Was it a hard match? If so, which one? If the match was via a scorecard, which scorecard was it? (You’ll end up with more than one.) What was the score? What was the threshold that it passed? If you don’t record this information, you can’t hope to reliably improve on the matching process in future.
I’ll come back to these topics soon.
As ever, if you’ve any comments, I’d love to hear them!
You are currently browsing the archives for the people-matching category.