Fuzzy data matching for personal demographic information

Question

Lets say I have a database filled with people with the following data elements:

• PersonID (meaningless surrogate autonumber)
• FirstName
• MiddleInitial
• LastName
• NameSuffix
• DateOfBirth
• AlternateID (like an SSN, Militarty ID, etc)

I get lots of data feeds in from all kinds of formats with every reasonable variation on these pieces of information you could think of. Some examples are:

• FullName, DOB
• FullName, Last 4 SSN
• First, Last, DOB

When this data comes in, I need to write something to match it up. I don't need, or expect, to get more than an 80% match rate. After the automated match, I'll present the uncertain matches on a web page for someone to manually match.

Some of the complexities are:

1. Some data matches are better than others and I would like to assign weight to those. For example, if the SSN matches exactly but the name is off because someone goes by their middle name, I would like to assign a much higher confidence value to that match than if the names match exactly but the SSNs are off.
2. The name matching has some difficulties. John Doe Jr is the same as John Doe II, but not the same as John Doe Sr. and if I get John Doe and no other information, I need to be sure the system doesn't pick one because there's no way to determine who to pick.
3. First name matching is really hard. You have Bob/Robert, John/Jon/Jonathon, Tom/Thomas, etc.
4. Just because I have a feed with FullName+DOB doesn't mean the DOB field is filled for every record. I don't want to miss a linkage just because the unmatched DOB kills the matching score. If a field is missing, I want to exclude it from the elements available for matching.
5. If someone manually matches, I want their match to affect all future matches. So, if we ever get the same exact data again, there's no reason not to automatically match it up next time.

I've seen that SSIS has fuzzy matching, but we don't use SSIS currently, and I find it pretty cludgy and nearly impossible to version control so it's not my first choice of tool. But if it's the best there is, tell me. Otherwise, are there any (preferably free, preferably .NET or T-SQL based) tools/libraries/utilities/techniques out there that you've used for this type of problem?

Answer 1

Take a look at the Levenshtein Algoritm, which allows you to get 'the distance between two strings,' which can then be divided into the length of the string to get a percentage match.

http://en.wikipedia.org/wiki/Levenshtein_distance

I have previously implemented this to great success. It was a provider portal for a healthcare company, and providers registered themselves on the site. The matching was to take their portal registration and find the corresponding record in the main healthcare system. The processors who attended to this were presented with the most likely matches, ordered by percentage descending, and could easily choose the right account.

Answer 2

There are a number of ways that you can go about this, but having done this type of thing before i will go ahead and put out here that you run a lot of risk in having "incorrect" matches between people.

Your input data is very sparse, and given what you have it isn't the most unique, IF not all values are there.

For example with your First Name, Last Name, DOB situation, if you have all three parts for ALL records, then the matching gets a LOT easier for you to work with. If not though you expose yourself to a lot of potential for issue.

One approach you might take, on the more "crude" side of things is to simply create a process using a series of queries that simply identifies and classifies matching entries.

For example first check on an exact match on name and SSN, if that is there flag it, note it as 100% and move on to the next set. Then you can explicitly define where you are fuzzy so you know the potential ramification of your matching.

In the end you would have a list with flags indicating the match type, if any for that record.

Answer 3

If the false positives don't bug you and your languages is primarily English you can try algorithms like soundex. MS SQL server has it as a built in function. Soundex isn't the best, but it does do a fuzzy matching and is popular. Another alternative is metaphone