Practical Mergic

Saturday May 30, 2015

A talk for the Open Data Science Conference in Boston on Saturday May 30, 2015. Including some material originally given in a talk for the New York Open Statistical Programming Meetup on Wednesday May 20, 2015 and a lightning talk at the May meeting (registration) of the PyData NYC meetup group.



I've also done a longer version and a shorter version of this talk, and those are also on the blog. So if you find yourself wanting more you can get more, and if you want less I can also give you less.

This is probably the cheekiest of the three versions.

Open Data Science Conference title slide for Practical Mergic with Aaron Schumacher

Here's an official cover slide.


I teach at Metis, and I'm really happy that we're helping sponsor the Open Data Science Conference. Metis is a data science bootcamp, currently just in New York (sorry Boston). We get the best people, we have a lot of fun, and at the end out come data scientists that you could hire.

I could just talk about Metis, but instead I thought it'd be a good idea to talk about un-sexy everyday problems.


In general it's just one problem, and if you work with data you have this problem.

your data sucks

Data is awful! You do not want to swim in a data lake. It's a mess out there!

Of course these days we have open data, which is a huge improvement.

our data sucks

So maybe we release some data sets, put them on a nice Socrata open data portal...

   dbn grade year category num_tested
01M019     3 2010   Female         16
01M019     3 2010     Male         20
01M019     3 2010     Male          2

Here's an example of open data released by the New York City Department of Education.

The dbn is a school identifier, and grade and year make sense. This file has the number of students tested in three categories: “Female”, “Male”, and “Male”.

What does that mean?

There are fourteen hundred extra “Male” rows like this!

You can look more deeply into this and conclude with some confidence that you can probably drop these extra “Male” rows. It's clearly a mistake of some kind.

Original image from Magnolia via Indie Outlook.

This is a scene from a movie called Magnolia where it's raining frogs. One of the things they say in that movie is that strange things happen, and if you've worked with any variety of data sets, you've probably encountered very strange things indeed. You need to check everything—including things that you shouldn’t have to check.

I would also like to offer, before I get to what I'm really going to talk about, that it is a serious problem that I can't easily contribute a fix to that DOE data set. We should expect collaborative checking and editing of data sets to be part of the benefit of open data.

I don't know of any system currently in existence that does this well. We need something in between Wikipedia and GitHub. The dat project isn't doing it, at least not yet. I like the architecture of Datomic, but it's not quite right either. Wikidata might be moving in the right direction, but I'm not sure yet.

problems when names are the same

How is this relevant to merging? Well, lots of things can go wrong when you have exact duplicates that you aren't expecting.










$ convert -rotate 180 left_join.png right_join.png

You're welcome.


And an outer join gives you everything. Great!



Ready? Here's a test.



Take about three minutes and then come back.

three minutes pass



> nrow(first)
## [1] 3
> nrow(second)
## [1] 3
> result <- merge(first, second)
> nrow(result)
## [1] 3

This code is runnable in count_trouble.R.


This does an inner join, which is the default for merge in R. (I'm using R here as a personal favor to Jared Lander.)

Think about it.

 x    y1        x   y2        x    y1   y2
 1 looks        1 good        1 looks good
 2    oh        2  boy        2    oh  boy
 3  well        2   no        2    oh   no

There is no peace while you don't have unique IDs.


problems when names are the same


problems when names aren't the same




let's play tennis

I downloaded the Tennis Major Tournament Match Statistics Data Set from the University of California, Irvine Machine Learning Repository.

Do you know the process for getting a data set up up on the UCI ML repository?

The process is this: You fill in a form on their web site, and then maybe they put up your data set.

## Serena Williams,Ashleigh Barty,1,1,2,0,5

## S Williams,V Azarenka,7,1,2,1,57,44,43,2

There are eight files like this. You can see that the player names are not perfectly consistent.

Some good people up-state New York contributed this data set, and I got in touch with them. I was curious about where the data came from; it was scraped from some web sites. Did they use it in any of their classes? Yes, it was used for some activities. Did they use it for teaching any particular data cleaning techniques? I haven't heard back since then.

$ wc -l names.txt
## 1886

$ sort names.txt | uniq | wc -l
## 669

So we'll take the tennis player names as our example data set. We have a file with 1,886 names, 669 of which are unique.


$ sort names.txt | uniq -c | sort -nr | head -5
##  21 Rafael Nadal
##  17 Stanislas Wawrinka
##  17 Novak Djokovic
##  17 David Ferrer
##  15 Roger Federer


single field deduplication


Lukas Lacko             F Pennetta
Leonardo Mayer          S Williams
Marcos Baghdatis        C Wozniacki
Santiago Giraldo        E Bouchard
Juan Monaco             N.Djokovic
Dmitry Tursunov         S.Giraldo
Dudi Sela               Y-H.Lu
Fabio Fognini           T.Robredo
...                     ...


Do you see the match here? (It's Santiago!)


Open Refine is quite good.


Open Refine is quite good, but there are several things I wish it did differently.

For one, although it has an internal record of changes, the interface Open Refine exposes changes your data in place. That's not okay.

Cluster ID,name
1,Lukas Lacko
2,Leonardo Mayer
3,Marcos Baghdatis

One way to keep output from a deduplication process is a merge table like this. The csvdedupe interface on the Python dedupe project from DataMade in Chicago will give you this kind of output. It's much better than no accessible record of the transformation, but it's also not a format I want to look at, as a human.

    "Ann's group": [
    "Bob's group": [

Here's a format that I propose could be usable for describing deduplication. It's as readable by humans as any JSON, and it can be easily produced and consumed by anything that speaks JSON, which is everything.

Ann's group,Ann
Bob's group,Bob
Bob's group,Robert

You can still produce a merge table from the JSON representation, and it will have whatever new keys you specify, possibly human-readable ones.

mergic is a tool that supports doing deduplication with these conventions.

The goals of mergic are to be:

the tool disappears

Good tools disappear.



any distance function


really reproducible


A quick disclaimer!

This is John Langford's slide, about what big data is. He says that small data is data for which \( O(n^2) \) algorithms are feasible. Currently mergic is strictly for this kind of "artisanal" data, where we want to ensure that our matching is correct but want to reduce the amount of human work to ensure that. And we are about to get very \( O(n^2) \).

Santiago Giraldo,Leonardo Mayer
Santiago Giraldo,Dudi Sela
Santiago Giraldo,Juan Monaco
Santiago Giraldo,S Williams
Santiago Giraldo,C Wozniacki
Santiago Giraldo,S.Giraldo
Santiago Giraldo,Marcos Baghdatis
Santiago Giraldo,Y-H.Lu

So we make all possible pairs of identifiers!




Karolina Pliskova,K Pliskova



Kristyna Pliskova,K Pliskova


sets > pairs


workflow support for reproducible deduplication and merging


demo: mergic tennis


$ pew new odsc

I'll start by making a new virtual environment using pew.

$ pip install mergic

mergic is very new (version 0.0.6) and it currently installs with no extra dependencies.

$ mergic -h



positional arguments:
    calc                calculate all partitions of data
    make                make a JSON partition from data
    check               check validity of JSON partition
    diff                diff two JSON partitions
    apply               apply a patch to a JSON partition
    table               make merge table from JSON partition

optional arguments:
  -h, --help            show this help message and exit



#!/usr/bin/env python

import re
import Levenshtein
import mergic

def first_initial_last(name):

def distance(x, y):
    x = first_initial_last(x)
    y = first_initial_last(y)
    return Levenshtein.distance(x, y)




Now can be used just like the standard mergic script.

$ ./ calc names.txt
## num groups, max group, num pairs, cutoff
##        669,         1,         0, -1
##        358,         5,       384, 0
##        348,         6,       414, 1
##        332,         6,       470, 2
##        262,        85,      5117, 3
##        165,       324,     52611, 4
##         86,       496,    122899, 5
##         46,       584,    170287, 6
##         24,       624,    194407, 7
##         16,       641,    205138, 8
##         10,       650,    210940, 9
##          4,       663,    219459, 10
##          2,       668,    222778, 11
##          1,       669,    223446, 12


$ ./ make names.txt 2 > groups.json



$ head -5 groups.json
## {
##     "Yen-Hsun Lu": [
##         "Di Wu",
##         "Yen-Hsun Lu",
##         "Y-H.Lu",


$ head -8 edited.json
## {
##     "Yen-Hsun Lu": [
##         "Yen-Hsun Lu",
##         "Y-H.Lu"
##     ],
##     "Di Wu": [
##         "Di Wu"
##     ],



$ mergic check edited.json
## 669 items in 354 groups


$ mergic diff groups.json edited.json > diff.json



$ mergic apply groups.json diff.json > rebuilt.json


$ mergic diff edited.json rebuilt.json
## {}


$ mergic table edited.json > merge.csv



##  24 Novak Djokovic
##  22 Rafael Nadal
##  21 Serena Williams
##  21 David Ferrer
##  20 Na Li
##  19 Victoria Azarenka
##  19 Agnieszka Radwanska
##  18 Stanislas Wawrinka
##  17 Tommy Robredo
##  17 Sloane Stephens


##  21 Rafael Nadal
##  17 Stanislas Wawrinka
##  17 Novak Djokovic
##  17 David Ferrer
##  15 Roger Federer
##  14 Tommy Robredo
##  13 Richard Gasquet
##  11 Victoria Azarenka
##  11 Tomas Berdych
##  11 Serena Williams


distance matters



See also: Adaptive Duplicate Detection Using Learnable String Similarity Measures

extension to multiple fields

We've been talking about single field deduplication.


This means that we have one field, say name.

name, name
Bob, Bobby
Bob, Robert
Bobby, Robert



name,    hometown
Bob,     New York
Rob,     NYC
Robert,  "NY, NY"






The Python dedupe project and the R RecordLinkage package do this.

The csvdedupe interface using dedupe even asks us to clarify things, doing a live training phase. The hope is that it will learn what matters.

You can also build this kind of behavior into your own systems; there is an example.

real clustering?




dog, doge, kitten, kitteh


       dog doge kitten kitteh
   dog   0    1      6      6
  doge   1    0      5      5
kitten   6    5      0      1
kitteh   6    5      1      0



from sklearn.manifold import MDS
mds = MDS(dissimilarity='precomputed')
coords = mds.fit_transform(distances)

Here's all the code it takes.






This is the Open Data Science Conference, right?

This mergic project is something I think could be a good direction for particular kinds of data problems. Of course it's on GitHub and of course I'd love help in making it something that might actually help people.

Our community is bigger than any one problem or any one solution, and I want to hear about what problems are real for you and what solutions you're excited about.


Thanks for listening—let's talk!


This is just me again.