Which type of clustering algorithm to use to identify the "same" item in different data sets?

Question

I'm trying to find a solution for a data quality problem - specifically, identifying which items in different data sets are used to represent the same things.

As an example, assume that we're a retailer and we buy out a couple of other retailers. In the process, we also get their systems and databases. This might lead to some overlap - different systems can represent the same items, customers, etc. in different ways, but with no single unique identifier.

What would the best approach be to determine which rows represent the same thing across data sets in order to come up with a single view of 'unique' entities?

I've done a machine learning course, and I understand the bare minimum. I believe that the solution to this problem requires a clustering algorithm, but what type? I may be dealing with a multitude of features in the data - dimensions, names, dates, contact details - and some of those would probably require a higher 'weight' in matching.

Examples (Items):

A: ABC Notebook, Large, Released: 2018-02-20, 150mm x 100mm.

B: Notebook (ABC), L, Date: 18/02/2018, 150mm x 100mm

I'd expect these to be treated as the same item.

Examples (Customer):

A: Doe, Jane, DOB 1970-06-23, 123 ML Ave, F

B: John Doe, DOB 1971-04-33, 123 ML Avenue, M

C: J. Doe, Born '71

I'd expected B and C to be identified as the same person, but not A.

For this scenario, I don't expect to come up with something with a 100% accuracy, but I would like to be able to come up with a (narrow) list of possible matches that someone can check.

Can some please point me in the right direction? Any case studies that I should look at?

Answer 1

You should focus on methods that fall under the scope of Record Linkage rather than clustering, as Record Linkage methods are specifically targeted to solve this type of problem.

The manuscript 'Automatic Record Linkage Using Seeded Nearest Neighbour and Support Vector Machine Classification' written by Peter Christen, provides a good introduction to using machine learning for Record Linkage link to the pdf.

There is also a RecordLinkage Package available in R, which provides a good starting point to practice with techniques from stochastic record linkage, and supervised and unsupervised machine learning link to manuscript which describes the package

Answer 2

A: ABC Notebook, Large, Released: 2018-02-20, 150mm x 100mm.

B: Notebook (ABC), L, Date: 18/02/2018, 150mm x 100mm

It doesn't seem like a clustering problem. Rather, it's more like a text mining problem. E.g., you extract "ABC" and "Notebook" from the names of both A and B, and then decide they are the same. Besides that, there are also some format detection needed, like mapping date string to datetime format, L to Large.

After you extracted these features and constructed a feature matrix, you can simply determine if two entries are different items/people by their commonly existing features in the matrix (since there will be NAs in your matrix). You don't really need a machine learning clustering algorithm.

A: Doe, Jane, DOB 1970-06-23, 123 ML Ave, F

B: John Doe, DOB 1971-04-33, 123 ML Avenue, M

C: J. Doe, Born '71

E.g., A and B are not the same since there are mismatches in DOB and sex. B and C can be treated as same, as they both have 2 features - name and DOB - show up in your data set, and both 2 features matched.

You might need a bit more complex algorithm, since there might be a D: John Doe, DOB 1971-03-12, F, with which you should leave B, C, D alone. But that's all it need, I guess.