Algorithms for aggregating duplicate identities based on non-numerical data? 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.)
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


Wikipedia pages on Record Linkage and Data Deduplication
Overview slideshttps://www.umiacs.umd.edu/~getoor/Tutorials/ER_VLDB2012.pdf
[Dedupe]'s explanation of how their software works: https://dedupe.io/developers/library/en/latest/How-it-works.html


Talks


Peter Christen, Record Linkage lectures at ADRC-Scotland: 1 2 3 4 (2015)
Mike Mull, The Art and Science of Data Matching: https://www.youtube.com/watch?v=Y-nYEOgq3YE (2015)
Rhydwyn Mcguire, Join for real life: https://www.youtube.com/watch?v=cEcVIjyHfiQ (2013)
Andrew Rowe, Big Data Deduplication and Data Matching using Python: https://www.youtube.com/watch?v=Z6mlvrYEYnk (2013)


Books


Peter Christen, Data Matching: http://www.springer.com/us/book/9783642311635
Thomas N. Herzog, Fritz J. Scheuren and William E. Winkler, Data Quality and Record Linkage Techniques: http://www.springer.com/us/book/9780387695020


Free software

(last updated, github stars as of Nov 2017)

Python


Dedupe: https://github.com/dedupeio/dedupe (2017, 1,413)
RLTK: https://github.com/usc-isi-i2/rltk/ (2017, 13)
Febrl: https://sourceforge.net/projects/febrl/ (2013)


Java


Duke: https://github.com/larsga/Duke (2016, 469)
JedAI: https://github.com/scify/JedAIToolkit (2017, 12)
LSHDB: https://github.com/dimkar121/LSHDB (2017, 9)
FRIL: http://fril.sourceforge.net/ (2011) (Windows binary available)


R


RecordLinkage: https://r-forge.r-project.org/projects/recordlinkage/ https://cran.r-project.org/web/packages/RecordLinkage/index.html
fastLink: https://github.com/kosukeimai/fastLink


Other


OpenRecLink: http://reclink.sourceforge.net/ (2016)


C++ with GUI

Registry Plus™ Link Plus: https://www.cdc.gov/cancer/npcr/tools/registryplus/lp_tech_info.htm (2007)


Commercial software and solutions


Data Ladder DataMatch: https://dataladder.com/
Dedupe: https://dedupe.io/ (freemium frontend for Dedupe Python library)
LinkageWiz: http://www.linkagewiz.net/
WinPure Clean and Match: http://www.winpure.com/cleanmatch.html
Reifier: http://nubetech.co/


For SAS


(free but requires SAS) The Link King: http://www.the-link-king.com/


Data Cleaning

Name Parsers

Python


probablepeople: https://github.com/datamade/probablepeople (2017, 204)
Name Parser: https://github.com/derek73/python-nameparser (2017, 232)


JavaScript


parse-full-name: https://github.com/dschnelldavis/parse-full-name (2017, 18)


Papers


US Census Bureau Data Linkage research: https://www.census.gov/srd/csrm/RecordLinkage.html
Learnable Similarity Functions and their Application to Record Linkage and Clustering (via)
[https://www.microsoft.com/en-us/research/publication/improving-entity-resolution-with-global-constraints/ (via)
https://arxiv.org/abs/1312.4645 (via)
http://people.cs.umass.edu/~mwick/MikeWeb/Publications_files/wick09entity.pdf (via)
http://homes.cs.washington.edu/~pedrod/papers/mrdm04.pdf (via)
https://www.researchgate.net/publication/318874102_Clink_-_A_Novel_Record_Linkage_Methodology_based_on_Graph_Interactions


Organizations


US Census Burea - Center for Statistical Research and Methodolgy - Record Linkage: https://www.census.gov/srd/csrm/RecordLinkage.html
Stanford Entity Resolution Framework: http://infolab.stanford.edu/serf/
ANU Data Mining and Matching Group https://dmm.anu.edu.au/ https://web.archive.org/web/20160515215747/datamining.anu.edu.au/projects/linkage.html (Archive.org link)


Misc


DuDe (framework for comparing record linkage results): https://hpi.de/naumann/projects/data-quality-and-cleansing/dude-duplicate-detection.html
Datasets to use for evaluating deduplication software: https://hpi.de/naumann/projects/repeatability/datasets.html
https://www2.vrdc.cornell.edu/news/3/20050420-Record%20Linkage%20Software.pdf