7
$\begingroup$

I have a large dataset (2M entries) of people, but many people have multiple entries in the database with slightly (or significantly) different identifying information. For example, I may have J. Doe and John Doe, or I may have John Doe with an accompanying email address and John Doe without an accompanying email address.

I've been looking at different clustering algorithms but nothing seems well-suited to what I'm doing, which is to aggregate the entries based on rules like the following:

  • guess first and last names based on whether one of the names is written in all capitals
  • aggregate "J. Doe" and "J. Doe" if email addresses match
  • aggregate "J. Doe" into "John Doe" if no other people have first name starting with "J" and last name "Doe"

With a smaller dataset this would be a relatively straightforward task to do just with some simple rules, but with the number of entries I have the aggregation tasks can get really slow and the logic gets pretty convoluted. My current solution (based around using the fulltext search function within my database to find similar entries, adding hashes based on those results, and then aggregating based on a mix of hashes and types of ambiguity) works, but every time I try to run it or update it it just screams that it's the kind of problem somebody else has already solved. But I haven't been able to find a solution.

Are there algorithms that will do what I want based on rules like this? Or specific packages or software that might be helpful? Or am I approaching this problem completely wrong?

Thanks!

(Please note though that I am well aware that there are many different ways to incorrectly aggregate identities (e.g. that J. Doe could mean John Doe or James Doe), so I don't need warnings against trying to aggregate things.)

$\endgroup$
  • $\begingroup$ After posting this question, did you try anything or come up with a plan in any sort? What language do you prefer? I have some ideas in my mind. Python dictionary will be your best friend to have a key, value matching in your case. $\endgroup$ – i.n.n.m Aug 25 '17 at 21:11
  • 2
    $\begingroup$ This is called en.wikipedia.org/wiki/Record_linkage $\endgroup$ – Emre Aug 26 '17 at 8:21
  • $\begingroup$ Clustering will be the wrong thing here. By statistical analysis you will merge "Jan" and "Jane" because they differ by only one letter. So at most, these should be used interactively as e.g. in OpenRefine. Look for record linkage research instead. $\endgroup$ – Has QUIT--Anony-Mousse Aug 28 '17 at 6:09
7
$\begingroup$

I haven't yet successfully solved my record linkage problem, but I wanted to share some of the stuff I've found in the process in case it's of use to anyone else. This is a work in progress based here on GitHub.


Record Linkage Resources

(also known as deduplication, data matching, entity resolution)

Background

Documents

Talks

Books

Free software

(last updated, github stars as of Nov 2017)

Python

Java

R

Other

Commercial software and solutions

For SAS

Data Cleaning

Name Parsers

Python JavaScript

Papers

Organizations

Misc

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.