How do I go about building a matching algorithm

Questions

I ve never built an algorithm for matching before and don t really know where to start. So here is my basic set up and why I m doing it. Feel free to correct me if I m not asking the right questions.

I have a database of names and unique identifiers for people. Several generated identifiers (internally generated and some third party), last name, first name, and birth date are the primary ones that I would be using.

Several times throughout the year I receive a list from a third party that needs to be imported and tied to the existing people in my database but the data is never as clean as mine. IDs could change, birth dates could have typos, names could have typos, last names could change, etc.

Each import could have 20,000 records so even if it s 99% accurate that s still 200 records I d have to go in manually and match. I think I m looking for more like 99.9% accuracy when it comes to matching the incoming people to my users.

So, how do I go about making an algorithm that can figure this out?

PS Even if you don t have an exact answer but do know of some materials to reference would also be helpful.

PPS Some examples would be similar to what m3rLinEz wrote:

ID: 9876234 Fname: Jose     LName: Guitierrez       Birthdate:01/20/84   - Original 

ID: 9876234 Fname: Jose     LName: Guitierrez       Birthdate:10/20/84   - Typo in birth date 
ID: 0876234 Fname: Jose     LName: Guitierrez       Birthdate:01/20/84   - Wrong ID 
ID: 9876234 Fname: Jose     LName: Guitierrez-Brown Birthdate:01/20/84   - Hyphenated last name 
ID: 9876234 Fname: Jose, A. LName: Guitierrez       Birthdate:01/20/84   - Added middle initial 
ID: 3453555 Fname: Joseph   LName: Guitierrez       Birthdate:01/20/84   - Probably someone else with same birthdate and same last name 

Answers

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

The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character. It is named after Vladimir Levenshtein, who http://en.wikipedia.org/wiki/Levenshtein_distance http://en.wikipedia.org/wiki/Levenshtein_distance

It is possible to compare every of your fields and computing the total distance. And by trial-and-error you may discover the appropriate threshold to allow records to be interpret as matched. Have not implemented this myself but just thought of the idea :}

  For example:   

• Record A - ID: 4831213321, Name: Jane
• Record B - ID: 431213321, Name: Jann
• Record C - ID: 4831211021, Name: John

The distance between A and B will be lower than A and C / B and C, which indicates better match.

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/2163909/how-do-i-go-about-building-a-matching-algorithm

Related