What algorithm could be used to fuzzy merge multiple datasets?

Question

Problem Description

I have several tables that are related but do not share any unique key. I've come across this problem several times with customer data in separate source systems that needs to be compared together.

Lets say my data is multiple tables, Table A through Z.

There may be columns where I'm 100% certain on a match. For example table A and B have the column tax ID which is a certain match joining A to B. Both A and B alone cannot match to C, but using columns from A and B can make a certain match to C.

There are columns that are likely matches like matching first name, last name, birthday, etc "John Smith", but may result in false positives. Additional fuzzy matches may increase likelihood of match at different magnitudes.

I would like to feed an ML engine a set of tables that have been verified to be related to the same person, and see what rules it can come up with for matching the tables. I may get only a subset of tables at a time, and I want to be able to match what is possible and await more data. What algorithm could be used?

Thoughts

• I know decision trees are great for this type of problem but probably many of the fuzzy checks I could make could better be expressed by some certainty magnitude. I've also never used a decision tree across a set of datasets where I could only be dealing with a subset.
• I know Naive Bayes is often used for fuzzy matching but I also want to combine logic for 100% matches
• Since this is a case where there can be limited full information via manually tracking down data, evolutionary algorithms could potentially work

Answer 1

The first thing is to define a distance metric to say how close potential keys are. If the data is text, Levenshtein distance is a common distance metric. If the data is numeric, then Euclidean or Manhattan distance could work. If the data is geographic, then Haversine is a good choice.

After defining a distance, a threshold needs to be set to for merging. The threshold could be picked by a person or learned by a machine learning algorithm. Typically, there is not enough data to train a machine learning algorithm. It is often good enough to just pick a threshold based on domain knowledge.

If you can use R, there is the fuzzyjoin package.

Given that you have to search the cartesian product of the space, evolutionary algorithms will take too much time.