PyDataNYCSlides.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# The Art and Science of Data Matching\n",
    "\n",
    "## Mike Mull (@kwikstep)\n",
    "\n",
    "#### Notebook at: https://github.com/mikemull/Notebooks/blob/master/PyDataNYCSlides.ipynb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Applications of Matching: Integration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<img src=\"Integrate.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "I'll start with a few applications for data matching.\n",
    "\n",
    "The first is _data integration_.  Here we are starting with multiple data sources with references to the same type of entities.  What we hope to end up with is a combined set of data for those entities that is more accurate and as timely as possible.  We also retain some sort of reference to the original data so that we don't lose any information."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Applications of Matching: Enrichment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<img src=\"Enrich.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The second application is _enrichment_.  There are various ways this term is used, but as a data matching problem it usually means that you have a source of data, often from a client, that needs to be matched to a more complete and accurate set.  All or part of the more complete set is returned to the client as an enriched entity reference."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Applications of Matching: Record Linking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<img src='Merge.png'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The third application is called _record linkage_ or sometimes merging. In this scenario there are two sets of data that have references to the same type of entity, but also related statistics or facts about those entities.  The combined data can then be used to make correlations.  I'll use an application like this throughout this talk, which i'll discuss below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Pairwise Matching\n",
    "\n",
    "If you have two sets of data items, A and B, each with no duplicates then \n",
    "\n",
    "- All possible record pairs are\n",
    "\n",
    "$$\n",
    "A \\times B\n",
    "$$\n",
    "\n",
    "- The pairs can be divided into\n",
    "\n",
    "\n",
    "$$\n",
    "M=\\{ (a,b)| a \\in A, b \\in B, a = b \\}\n",
    "$$\n",
    "\n",
    "$$\n",
    "U=\\{ (a,b)| a \\in A, b \\in B, a \\ne b \\} \\\\\n",
    "$$\n",
    "\n",
    "\n",
    "By definition the union of the two sets M and U is the set of all pairs A and B, or:\n",
    "\n",
    "$$\n",
    "A \\times B = M \\cup U\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "I will use the concept of pairwise matching throughout the code as a model to explain various techniques.  The essential idea is that given two sets of records (say, as two files), matching involves examining every possible record pair to determine if they refer to the same entity.  What we're usually interested in is the _M_ set above.  In practice:\n",
    "\n",
    "- The M set is *much* smaller than the U set\n",
    "- We generally __won't__ look at all of the pairs, which is |A||B| and is often a huge number\n",
    "- We will make two types of errors.  We will put actual matches in U and we will put non-matches in M.\n",
    "- Ideally the set of matches is transitive, but some techniques don't always get that result\n",
    "- In the deduplication case, the M set contains the duplicates.  Finding all of the record pairs that belong to the same entity might require extra clustering.\n",
    "\n",
    "Note that this model does not necessarily match the architecture of matching software.  In other words, we won't usually load the data sets all at once and work through the pairs.  We might, for example, load one set of data, use some properties of those records to query against an existing database that we want to match.\n",
    "\n",
    "There is  an alternative model of matching, which is the _clustering_ model."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Test Case\n",
    "\n",
    "- From [On Wages and Hygiene: Surfacing Bad Management in Public Data](http://blog.enigma.io/bad-management-radiates-a-look-at-hygiene-and-wages/)\n",
    "  - Florida restaurant inspection data\n",
    "  - Federal wage compliance data (from DOL)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/mikemull/anaconda/envs/matching/lib/python3.4/site-packages/IPython/core/interactiveshell.py:2902: DtypeWarning: Columns (8) have mixed types. Specify dtype option on import or set low_memory=False.\n",
      "  interactivity=interactivity, compiler=compiler, result=result)\n"
     ]
    }
   ],
   "source": [
    "from IPython.display import HTML\n",
    "import pandas as pd\n",
    "# Wage data, drop everything but unique name and addresses, and filter to only Florida.\n",
    "df_oge = pd.read_csv('./data/ogesdw.whd.whisard.fl.csv')\n",
    "\n",
    "# Florida restaurant inspection data.  Drop everything but unique name and addresses\n",
    "df_fl = pd.read_csv('./data/fl.restaurant-inspections.csv')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The data sets that i'll use come from a blog post by Enigma.  They used restaurant inspection data from the state of Florida, and wage data from the DOL to do an analysis of whether the wage violations are correllated to bad restaurant hygiene.  They concluded that restaurants with violations for improperly paying employees are much more likely to also have health violations.  One note, they used geocoded addresses to do the matching, whereas i'm primarily going to use street numbers just to illustrate certain ideas.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Profiling\n",
    "\n",
    "- Accuracy\n",
    "- Completeness\n",
    "- Consistency\n",
    "- Timeliness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The first step in matching is usually to explore the data.  In this case we'll use _pandas_, which is often the tool of choice for this type of work in the Python world.  This process is becoming more automated these days, but since it's usually a one-time investment, it's still useful to do manually.  The type of exploration i'll do is an aspect of _data profiling_, although in the matching case we're mostly interested in finding attributes that might be similar between data sources so that we can use them for comparison or linking.  These are sometimes called _natural keys_."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'pandas.core.frame.DataFrame'>\n",
      "Int64Index: 130643 entries, 0 to 130642\n",
      "Data columns (total 83 columns):\n",
      "district                                        130643 non-null object\n",
      "county_number                                   130643 non-null int64\n",
      "county_name                                     130643 non-null object\n",
      "license_type_code                               130643 non-null int64\n",
      "license_number                                  130643 non-null int64\n",
      "dba                                             130613 non-null object\n",
      "location_address                                130643 non-null object\n",
      "location_city                                   130642 non-null object\n",
      "location_zip_code                               130633 non-null object\n",
      "inspection_number                               130643 non-null int64\n",
      "visit_number                                    130643 non-null int64\n",
      "inspection_class                                130643 non-null object\n",
      "inspection_type                                 130643 non-null object\n",
      "inspection_disposition                          130643 non-null object\n",
      "inspection_date                                 130643 non-null object\n",
      "number_of_critical_violations                   4 non-null float64\n",
      "number_of_noncritical_violations                4 non-null float64\n",
      "number_of_total_violations                      130643 non-null int64\n",
      "number_of_high_priority_violations              130619 non-null float64\n",
      "number_of_intermediate_violations               130619 non-null float64\n",
      "number_of_basic_violations                      130619 non-null float64\n",
      "pda_status                                      130643 non-null object\n",
      "approved_source                                 130643 non-null int64\n",
      "original_container                              130643 non-null int64\n",
      "time_and_temperature_control                    130643 non-null int64\n",
      "facilities_to_maintain_ph_tcs                   130643 non-null int64\n",
      "food_and_food_equipment_thermometers            130643 non-null int64\n",
      "ph_tcs_foods_properly_thawed                    130643 non-null int64\n",
      "unwrapped_or_ph_tcs_food_not_re_served          130643 non-null int64\n",
      "food_protection_cross_contamination             130643 non-null int64\n",
      "bare_hand_contact_with_rte_food_aop             130643 non-null int64\n",
      "in_use_food_dispensing_utensils                 130643 non-null int64\n",
      "employee_health_knowledge                       130643 non-null int64\n",
      "hands_washed_and_clean                          130643 non-null int64\n",
      "clean_clothes_hair_restraints                   130643 non-null int64\n",
      "food_contact_and_nonfood_contact                130643 non-null int64\n",
      "violation15                                     130643 non-null int64\n",
      "dishwashing_facilities                          130643 non-null int64\n",
      "violation17                                     130643 non-null int64\n",
      "violation18                                     130643 non-null int64\n",
      "violation19                                     130643 non-null int64\n",
      "violation20                                     130643 non-null int64\n",
      "wiping_cloths_clean_and_soiled_linens           130643 non-null int64\n",
      "food_contact_surfaces_clean                     130643 non-null int64\n",
      "non_food_contact_surfaces_clean                 130643 non-null int64\n",
      "storage_handling_of_clean_equipment             130643 non-null int64\n",
      "single_service_and_single_use_items             130643 non-null int64\n",
      "violation26                                     130643 non-null int64\n",
      "water_source_safe_hot                           130643 non-null int64\n",
      "sewage_and_wastewater                           130643 non-null int64\n",
      "plumbing_installed                              130643 non-null int64\n",
      "violation30                                     130643 non-null int64\n",
      "handwash_sinks                                  130643 non-null int64\n",
      "bathrooms                                       130643 non-null int64\n",
      "garbage_and_refuse                              130643 non-null int64\n",
      "violation34                                     130643 non-null int64\n",
      "no_presence_or_breeding_of_pests                130643 non-null int64\n",
      "floors_walls_ceilings                           130643 non-null int64\n",
      "violation37                                     130643 non-null int64\n",
      "lighting_provided_as_required                   130643 non-null int64\n",
      "violation39                                     130643 non-null int64\n",
      "employee_personal_belongings                    130643 non-null int64\n",
      "chemicals_toxic_substances                      130643 non-null int64\n",
      "cleaning_and_maintenance_equip                  130643 non-null int64\n",
      "complete_separation_from_living_area            130643 non-null int64\n",
      "violation44                                     130643 non-null int64\n",
      "fire_extinguishing_equipment                    130643 non-null int64\n",
      "exits_not_blocked_or_locked                     130643 non-null int64\n",
      "electrical_wiring_outlets_in_good_repair        130643 non-null int64\n",
      "gas_appliances_boiler_certificate               130643 non-null int64\n",
      "flammable_combustible_materials                 130643 non-null int64\n",
      "current_license_properly_displayed              130643 non-null int64\n",
      "other_conditions_sanitary_and_safe_operation    130643 non-null int64\n",
      "misrepresentation_misbranding                   130643 non-null int64\n",
      "food_management_certification_valid             130643 non-null int64\n",
      "florida_clean_indoor_air_act                    130643 non-null int64\n",
      "automatic_gratuity_notice                       130643 non-null int64\n",
      "violation56                                     130643 non-null int64\n",
      "violation57                                     130643 non-null int64\n",
      "violation58                                     130643 non-null int64\n",
      "license_id                                      130643 non-null int64\n",
      "inspection_visit_id                             130643 non-null int64\n",
      "serialid                                        130643 non-null int64\n",
      "dtypes: float64(5), int64(67), object(11)\n",
      "memory usage: 83.7+ MB\n"
     ]
    }
   ],
   "source": [
    "df_fl.info(verbose=True, null_counts=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Here i've used the pandas dataframe method _info()_ to show all of the fields, the field types, and the number of non-null values.  Obviously, this data has a bunch of columns related to the inspection of restaurants.  There also clues here that restaurants will appear in this data more than once (inspection number, inspection date).  What we want for matching is to boil this down to the fields that might help us identify the restaurant and match it to other data sources."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'pandas.core.frame.DataFrame'>\n",
      "Int64Index: 53578 entries, 0 to 130642\n",
      "Data columns (total 6 columns):\n",
      "dba                  53558 non-null object\n",
      "location_address     53578 non-null object\n",
      "location_city        53577 non-null object\n",
      "location_zip_code    53570 non-null object\n",
      "district             53578 non-null object\n",
      "county_number        53578 non-null int64\n",
      "dtypes: int64(1), object(5)\n",
      "memory usage: 2.9+ MB\n"
     ]
    }
   ],
   "source": [
    "fields = ['dba', \n",
    "          'location_address', \n",
    "          'location_city', \n",
    "          'location_zip_code',\n",
    "          'district',\n",
    "          'county_number']\n",
    "df_fl_a = df_fl[fields].drop_duplicates()\n",
    "df_fl_a.info()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "This code basically takes the fields that identify the restaurant and drops the exact duplicates.  We are left with about 54k entities. About 20 of them are missing names, which will make it difficult to match them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'pandas.core.frame.DataFrame'>\n",
      "Int64Index: 16683 entries, 0 to 16702\n",
      "Data columns (total 8 columns):\n",
      "trade_nm                  16683 non-null object\n",
      "legal_name                16593 non-null object\n",
      "street_addr_1_txt         16683 non-null object\n",
      "cty_nm                    16683 non-null object\n",
      "st_cd                     16683 non-null object\n",
      "zip_cd                    16683 non-null float64\n",
      "naic_cd                   16676 non-null object\n",
      "naics_code_description    16676 non-null object\n",
      "dtypes: float64(1), object(7)\n",
      "memory usage: 1.1+ MB\n"
     ]
    }
   ],
   "source": [
    "df_oge_a_fl = df_oge[['trade_nm', \n",
    "                      'legal_name', \n",
    "                      'street_addr_1_txt', \n",
    "                      'cty_nm', \n",
    "                      'st_cd', \n",
    "                      'zip_cd',\n",
    "                      'naic_cd',\n",
    "                      'naics_code_description']].drop_duplicates()\n",
    "df_oge_a_fl.info()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "This is the equivalent operation for the wage data.  We can see that both sources have a name field and various address fields, which are mostly (but not entirely) non-null.  Note here that the zip code field is described as a float, which means that every value in the input data is numeric."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Use `apply()` and `groupby()` To Check Field Patterns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "zip_code_pattern\n",
      "99999         47780\n",
      "99999-9999     1611\n",
      "999999999      4179\n",
      "dtype: int64\n",
      "zip_code_pattern\n",
      "99999.9    16683\n",
      "dtype: int64\n"
     ]
    }
   ],
   "source": [
    "t={ord(x): y for (x, y) in zip('0123456789', '9999999999')}\n",
    "\n",
    "def zip_trans(z): return str(z).translate(t) if pd.notnull(z) else z\n",
    "\n",
    "df_fl_a['zip_code_pattern'] =  df_fl_a.location_zip_code.apply(zip_trans)\n",
    "print(df_fl_a.groupby('zip_code_pattern').size())\n",
    "df_oge_a_fl['zip_code_pattern'] = df_oge_a_fl.zip_cd.apply(zip_trans)\n",
    "print(df_oge_a_fl.groupby('zip_code_pattern').size())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Certain types of identifiers have an expected format, but very often that format is not followed especially when the data was originally entered by hand.  Zip codes for instance have two correct formats (5 digit and zip+4), and obviously numerous potential wrong formats.  Here's a handy trick for looking for formats of fields that are all or mostly numeric (zips, SSN, employer id numbers, phone numbers, etc.)\n",
    "\n",
    "Note here that the zip code pattern for the wage data looks like a decimal number.  That's because pandas defaults to float64 for numeric data.  This really means that the data is consistently a 5 digit integer.  If you know your zip codes, this also tells us that there are no zips with leading zeros, which isn't surprising since these data are filtered to locations in Florida."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Use `apply()` With Regex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "leading_pattern\n",
       "99          37\n",
       "AA        1133\n",
       "Aa       14716\n",
       "OTHER      797\n",
       "dtype: int64"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import re\n",
    "def leading_patt(s):\n",
    "    p = (('^[A-Z][a-z]', 'Aa'), ('^[A-Z][A-Z]', 'AA'), ('^[0-9][0-9]', '99'))\n",
    "    for rx, patt in p:\n",
    "        if re.search(rx, s):\n",
    "            return patt\n",
    "    return 'OTHER'\n",
    "\n",
    "df_oge_a_fl['leading_pattern'] = df_oge_a_fl.trade_nm.apply(leading_patt)\n",
    "df_oge_a_fl.groupby('leading_pattern').size()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Sometimes you'll want to identify more complex patterns like email addresses or dates using regular expressions.  Here's a slightly contrived example where i'm looking at the leading pattern in the names of the businesses in the wage data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Look for Duplicates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table border=\"1\" class=\"dataframe mark_rows\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>dba</th>\n",
       "      <th>location_address</th>\n",
       "      <th>location_city</th>\n",
       "      <th>location_zip_code</th>\n",
       "      <th>district</th>\n",
       "      <th>county_number</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>87996</th>\n",
       "      <td>ATLANTIC VENDORS INC</td>\n",
       "      <td>2411 S ATLANTIC AVE</td>\n",
       "      <td>DAYTONA BCH SHORES</td>\n",
       "      <td>32118</td>\n",
       "      <td>D4</td>\n",
       "      <td>74</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>88045</th>\n",
       "      <td>ATLANTIC VENDORS INC</td>\n",
       "      <td>2209 S ATLANTIC AVE</td>\n",
       "      <td>DAYTONA BCH SHORES</td>\n",
       "      <td>32118</td>\n",
       "      <td>D4</td>\n",
       "      <td>74</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>88061</th>\n",
       "      <td>ATLANTIC VENDORS INC</td>\n",
       "      <td>2125 S ATLANTIC AVE</td>\n",
       "      <td>DAYTONA BCH</td>\n",
       "      <td>32118</td>\n",
       "      <td>D4</td>\n",
       "      <td>74</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>88291</th>\n",
       "      <td>ATLANTIC VENDORS INC</td>\n",
       "      <td>2209 S ATLANTIC AVE</td>\n",
       "      <td>DAYTONA BEACH SHORES</td>\n",
       "      <td>32118</td>\n",
       "      <td>D4</td>\n",
       "      <td>74</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>87993</th>\n",
       "      <td>ATLANTIC VENDORS INC</td>\n",
       "      <td>3111 S ATLANTIC AVE</td>\n",
       "      <td>DAYTONA BEACH SHORES</td>\n",
       "      <td>32118</td>\n",
       "      <td>D4</td>\n",
       "      <td>74</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>88474</th>\n",
       "      <td>ATLANTIC VENDORS INC</td>\n",
       "      <td>1615 S ATLANTIC AVE</td>\n",
       "      <td>DAYTONA BEACH</td>\n",
       "      <td>32118</td>\n",
       "      <td>D4</td>\n",
       "      <td>74</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>88493</th>\n",
       "      <td>ATLANTIC VENDORS INC</td>\n",
       "      <td>2500 N ATLANTIC AVE</td>\n",
       "      <td>DAYTONA BEACH</td>\n",
       "      <td>32118</td>\n",
       "      <td>D4</td>\n",
       "      <td>74</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>88502</th>\n",
       "      <td>ATLANTIC VENDORS INC</td>\n",
       "      <td>103 S OCEAN AVE</td>\n",
       "      <td>DAYTONA BEACH</td>\n",
       "      <td>32118</td>\n",
       "      <td>D4</td>\n",
       "      <td>74</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>87994</th>\n",
       "      <td>ATLANTIC VENDORS INC</td>\n",
       "      <td>2225 S ATLANTIC AVE</td>\n",
       "      <td>DAYTONA BCH SHORES</td>\n",
       "      <td>32118</td>\n",
       "      <td>D4</td>\n",
       "      <td>74</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>87997</th>\n",
       "      <td>ATLANTIC VENDORS INC</td>\n",
       "      <td>3125 S ATLANTIC AVE</td>\n",
       "      <td>DAYTONA BCH SHORES</td>\n",
       "      <td>32118</td>\n",
       "      <td>D4</td>\n",
       "      <td>74</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import HTML, Javascript\n",
    "df=df_fl_a.groupby(['dba','location_zip_code'])\\\n",
    "       .filter(lambda x: len(x['dba']) > 2)\\\n",
    "       .sort_values(by='dba')[['dba',\n",
    "                     'location_address',\n",
    "                     'location_city',\n",
    "                     'location_zip_code',\n",
    "                     'district', \n",
    "                     'county_number']].head(10)\n",
    "HTML(df.to_html(classes='mark_rows'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "We eliminated _exact_ duplicates above, but there might still be duplicate businesses in the data that have slight variations in address or name.  Here's an example, where i group by the name and zip code, and then filter groups with more than 2 items.  The highlighted rows are very likely to be duplicates.  They vary only in the spelling of the city name."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "$('.mark_rows tbody tr').filter(':eq(1)')\n",
       "                                             .css('background-color', '#CCCCCC');\n",
       "              $('.mark_rows tbody tr').filter(':eq(3)')\n",
       "                                             .css('background-color', '#CCCCCC');\n",
       "                   "
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Javascript('''$('.mark_rows tbody tr').filter(':eq(1)')\n",
    "                                             .css('background-color', '#CCCCCC');\n",
    "              $('.mark_rows tbody tr').filter(':eq(3)')\n",
    "                                             .css('background-color', '#CCCCCC');\n",
    "                   ''')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Value Counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "LABIB BALTAGI CPA INC.                 15\n",
       "DCC Lee Enterprises, Inc               12\n",
       "Hospitality Staffing Solutions, LLC    10\n",
       "Executive Details Plus, Inc            10\n",
       "United Subcontractors, Inc.             9\n",
       "Name: legal_name, dtype: int64"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_oge_a_fl.legal_name.value_counts(dropna=True).head(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Dunkin Donuts    28\n",
       "Subway           26\n",
       "Burger King      16\n",
       "Days Inn         12\n",
       "McDonald's       12\n",
       "Name: trade_nm, dtype: int64"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_oge_a_fl.trade_nm.value_counts(dropna=True).head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Often it can be useful to get a count of the most common values for a field.  For example, in the wage data there are two fields, trade_nm and legal_name, that could possibly be used as identifiers and it's not clear which is better.  Looking at the common values though the trade_nm values look much more like restaurant names."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Make a Histogram of String Length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAEACAYAAABcXmojAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAESpJREFUeJzt3X/sXXV9x/HnSysMkUk6Tfmp8EfZqHMTSaib2/g6HCvJ\nBJYYKclIszVmGzqIS5YVs4wvW2Lkjw1JJvyxIL+ydDKZWBKGVOSbuCVYUdBqrUBmDS22OFTQLQwa\n3vvjnn56/e7b9vv73Ns+H8lNz/2ccz7nfb58ua97Pp977jdVhSRJAK/puwBJ0ugwFCRJjaEgSWoM\nBUlSYyhIkhpDQZLUHDYUkpyZ5JEk30ryzSTXdO0rk2xN8mSSh5KcPLTPdUmeSrIzycVD7ecn2d6t\nu3mo/fgkn+7aH03y1qU4UUnSkR3pSuEV4CNV9TbgXcCHkpwLbAK2VtU5wMPdc5KsAa4A1gDrgFuS\npOvrVmBjVa0GVidZ17VvBJ7v2m8Cbly0s5MkzclhQ6Gq9lbVE93yT4FvA6cDlwJ3dpvdCVzeLV8G\nbK6qV6pqF/A0sDbJqcBJVbWt2+6uoX2G+7oXuGihJyVJmp9ZzykkOQs4D/gysKqq9nWr9gGruuXT\ngN1Du+1mECLT2/d07XT/PgNQVfuBF5KsnMtJSJIWx6xCIckbGLyLv7aqfjK8rgbfk+F3ZUjSUWDF\nkTZI8joGgXB3Vd3XNe9LckpV7e2Ghp7r2vcAZw7tfgaDK4Q93fL09gP7vAV4NskK4I1V9cMZ6jB4\nJGmOqipH3uqgI336KMBtwI6q+sTQqi3Ahm55A3DfUPv6JMclORtYDWyrqr3Ai0nWdn1eBXxuhr7e\nz2DiekZVNZaP66+/vvcarL//Oqx/PB/jXP98HOlK4d3AHwDfSPJ413Yd8HHgniQbgV3AB7oX7R1J\n7gF2APuBq+tgZVcDdwAnAA9U1YNd+23A3UmeAp4H1s/rTCRJC3bYUKiqf+fQVxPvPcQ+HwM+NkP7\nV4G3z9D+v3ShIknql3c0L4OJiYm+S1gQ6++X9fdr3Oufq8x33Gm5JalxqVWSRkESao4TzUf89JH6\nc/Bm8OVnAEvHJkNh5PXx4txfGEnql3MKkqTGUJAkNYaCJKkxFCRJjaEgSWoMBUlSYyhIkhpDQZLU\nGAqSpMZQkCQ1hoIkqTEUJEmNoSBJagwFSVJjKEiSGkNBktQYCpKkxlCQJDWGgiSpMRQkSY2hIElq\nDAVJUmMoSJIaQ0GS1BgKkqTGUJAkNYaCJKkxFCRJjaEgSWoMBUlSYyhIkhpDQZLUGAqSpMZQkCQ1\nhoIkqTEUJEmNoSBJagwFSVJjKEiSGkNBktQYCpKkxlCQJDWGgiSpOWIoJPlUkn1Jtg+1TSbZneTx\n7nHJ0LrrkjyVZGeSi4faz0+yvVt381D78Uk+3bU/muSti3mCkqTZm82Vwu3AumltBfx9VZ3XPf4N\nIMka4ApgTbfPLUnS7XMrsLGqVgOrkxzocyPwfNd+E3Djgs5IkjRvRwyFqvoS8KMZVmWGtsuAzVX1\nSlXtAp4G1iY5FTipqrZ1290FXN4tXwrc2S3fC1w0+/IlSYtpIXMKf5bk60luS3Jy13YasHtom93A\n6TO07+na6f59BqCq9gMvJFm5gLokSfO0Yp773Qr8Tbf8t8DfMRgGWlKTk5NteWJigomJiaU+pCSN\njampKaamphbUR6rqyBslZwH3V9XbD7cuySaAqvp4t+5B4Hrge8AjVXVu134l8FtV9afdNpNV9WiS\nFcD3q+rNMxynZlPr0WQwHdPHOYdj7WctHY2SUFUzDfUf0ryGj7o5ggN+HzjwyaQtwPokxyU5G1gN\nbKuqvcCLSdZ2E89XAZ8b2mdDt/x+4OH51CRJWrgjDh8l2QxcCLwpyTMM3vlPJHkHg7ex3wX+GKCq\ndiS5B9gB7AeuHnp7fzVwB3AC8EBVPdi13wbcneQp4Hlg/SKdmyRpjmY1fDQKHD5a1iM7fCQdBZZt\n+EiSdHQyFCRJjaEgSWoMBUlSYyhIkhpDQZLUGAqSpMZQkCQ1hoIkqTEUJEmNoSBJagwFSVJjKEiS\nGkNBktQYCpKkxlCQJDWGgiSpMRQkSY2hIElqDAVJUmMoSJIaQ0GS1BgKkqTGUJAkNYaCJKkxFCRJ\njaEgSWoMBUlSYyhIkhpDQZLUGAqSpGZF3wVoNCXp7dhV1duxpWOdoaBD6OuFub8wkuTwkSRpiKEg\nSWoMBUlSYyhIkhpDQZLUGAqSpMZQkCQ1hoIkqTEUJEmNoSBJagwFSVJjKEiSGkNBktQYCpKk5oih\nkORTSfYl2T7UtjLJ1iRPJnkoyclD665L8lSSnUkuHmo/P8n2bt3NQ+3HJ/l01/5okrcu5glKkmZv\nNlcKtwPrprVtArZW1TnAw91zkqwBrgDWdPvckoN/reVWYGNVrQZWJznQ50bg+a79JuDGBZzPokvS\n20OSltsRQ6GqvgT8aFrzpcCd3fKdwOXd8mXA5qp6pap2AU8Da5OcCpxUVdu67e4a2me4r3uBi+Zx\nHkusenpI0vKa75zCqqra1y3vA1Z1y6cBu4e22w2cPkP7nq6d7t9nAKpqP/BCkpXzrEuStAAL/nOc\nVVVJluVt7eTkZFuemJhgYmJiOQ4rSWNhamqKqampBfUx31DYl+SUqtrbDQ0917XvAc4c2u4MBlcI\ne7rl6e0H9nkL8GySFcAbq+qHMx10OBQkST9r+pvlG264Yc59zHf4aAuwoVveANw31L4+yXFJzgZW\nA9uqai/wYpK13cTzVcDnZujr/QwmriVJPUjV4Ud+kmwGLgTexGD+4K8ZvKDfw+Ad/i7gA1X14277\njwJ/BOwHrq2qz3ft5wN3ACcAD1TVNV378cDdwHnA88D6bpJ6eh11pFqXwiDD+pr07evY/Z5zH/+d\npaNREqpqTh9lPGIojApD4Vg47uDY4/I7KY26+YSCdzRLkhpDQZLUGAqSpMZQkCQ1hoIkqTEUJEmN\noSBJagwFSVJjKEiSGkNBktQYCpKkxlCQJDWGgiSpMRQkSY2hIElqDAVJUmMoSJIaQ0GS1BgKkqTG\nUJAkNYaCJKkxFCRJjaEgSWoMBUlSYyhIkhpDQZLUGAqSpGZF3wVI0yXp7dhV1duxpVFgKGgE9fXC\n3F8YSaPC4SNJUmMoSJIaQ0GS1BgKkqTGUJAkNYaCJKkxFCRJjaEgSWoMBUlSYyhIkhpDQZLUGAqS\npMZQkCQ1hoIkqTEUJEmNoSBJagwFSVJjKEiSmgWFQpJdSb6R5PEk27q2lUm2JnkyyUNJTh7a/rok\nTyXZmeTiofbzk2zv1t28kJokSfO30CuFAiaq6ryquqBr2wRsrapzgIe75yRZA1wBrAHWAbfk4F9o\nvxXYWFWrgdVJ1i2wLknSPCzG8NH0v3Z+KXBnt3wncHm3fBmwuapeqapdwNPA2iSnAidV1bZuu7uG\n9pEkLaPFuFL4QpLHknywa1tVVfu65X3Aqm75NGD30L67gdNnaN/TtUuSltmKBe7/7qr6fpI3A1uT\n7BxeWVWVpBZ4jGZycrItT0xMMDExsVhdS9LYm5qaYmpqakF9pGpxXrOTXA/8FPggg3mGvd3Q0CNV\n9UtJNgFU1ce77R8Erge+121zbtd+JXBhVf3JtP5rsWqdi8G0x/Iftzt6T8c+Fs95cOw+fsekpZKE\nqpo+xH9Y8x4+SvL6JCd1yycCFwPbgS3Ahm6zDcB93fIWYH2S45KcDawGtlXVXuDFJGu7ieerhvaR\nJC2jhQwfrQI+232AaAXwT1X1UJLHgHuSbAR2AR8AqKodSe4BdgD7gauH3vpfDdwBnAA8UFUPLqAu\nSdI8Ldrw0VJz+OhYOG7/xx6X/x+k2VjW4SNJ0tHHUJAkNYaCJKkxFCRJjaEgSWoMBUlSYyhIkhpD\nQZLUGAqSpMZQkCQ1C/3qbI2EOd3FLkmHZCgcLSZHtC9JY8XhI0lSYyhIkhqHj3QISzFP4ddSS6PO\nUNDMJke8P0lLwuEjSVJjKEiSGkNBktQYCpKkxlCQJDWGgiSp8SOp0pCkn++RqvIeDo0GQ0HLaLYv\nuHN5YV7sF9M+Xpz9QkONDkNBy2dyxPuT5JyCJOkgQ0GS1Dh8pDHneLy0mAwFjbfJEe1LGlOGwrKb\n6ztb3wlLWj6GQh8mR7w/SccsJ5olSY2hIElqDAVJUmMoSJKasZpo/vCH/7zvEiTpqDZWofDJT56x\nzEfcvszHk6R+jVUowHJfKXwWuGOZjylJ/XFOQZLUjNmVgrTUluIOcv+AjsaHoSANmxzx/qQl5vCR\nJKkxFCRJjcNHs+I3lWppJf39jlU556GDDIXZmBzRvjQmRvtNRRKDQY2hIC21yUXuazH7O9Cn1BmZ\nOYUk65LsTPJUkr/sux5JOhaNRCgkeS3wD8A6YA1wZZJz+61qEX237wIWyPr7Neb1T01N9V3Cgox7\n/XM1KsNHFwBPV9UugCT/DFwGfHv2XXwRjpuEvLp4Vb36Y3hlEfrZBZy9CP30ZRfW36ddLHn9fUx0\nj8s8xtTUFBMTE32XsWxGJRROB54Zer4bWDu3Lp6FN38FLnxp8aracvzihII08pbyBXqS/z9xMdqT\n78eyUQmFWf1G/vzPv++Q615+eTcv/fBl+I9FPKWXXl68viT9jD4/hjtXN9xww6L1NepXSBmFApO8\nC5isqnXd8+uAV6vqxqFt+i9UksZMVc0pfUclFFYA3wEuAp4FtgFXVtUc5hQkSQs1EsNHVbU/yYeB\nzwOvBW4zECRp+Y3ElYIkaTSMxH0KhzNuN7Ul+VSSfUm2D7WtTLI1yZNJHkpycp81Hk6SM5M8kuRb\nSb6Z5JqufeTPIcnPJflykie62ie79pGvfViS1yZ5PMn93fOxqT/JriTf6Orf1rWNU/0nJ/lMkm8n\n2ZFk7bjUn+QXu5/7gccLSa6Za/0jHQpjelPb7QzqHbYJ2FpV5wAPd89H1SvAR6rqbcC7gA91P/OR\nP4eqegl4T1W9A3gHsC7JWsag9mmuBXZw8FN541R/ARNVdV5VXdC1jVP9NwMPVNW5wK8AOxmT+qvq\nO93P/TzgfOB/GPxN4bnVX1Uj+wB+DXhw6PkmYFPfdc2i7rOA7UPPdwKruuVTgJ191ziHc7kPeO+4\nnQPweuCrDG6MHJvagTOALwDvAe4ft98fBvdf/8K0trGoH3gj8J8ztI9F/dNqvhj40nzqH+krBWa+\nqe30nmpZiFVVta9b3ges6rOY2UpyFnAe8GXG5BySvCbJEwxqfKiqtjEmtXduAv4CGL41f5zqL+AL\nSR5L8sGubVzqPxv4QZLbk3wtyT8mOZHxqX/YemBztzyn+kc9FI66WfAaxPXIn1eSNwD3AtdW1U+G\n143yOVTVqzUYPjoDWJvkl6etH9nak/we8FxVPc4hbvkd5fo7767B8MUlDIYef3N45YjXvwJ4J3BL\nVb0T+G+mDbWMeP0AJDkOeB/wL9PXzab+UQ+FPcCZQ8/PZHC1MG72JTkFIMmpwHM913NYSV7HIBDu\nrqr7uuaxOoeqegF4BPhdxqf2XwcuTfJdBu/yfjvJ3YxP/VTV97t/f8BgPPsCxqf+3cDuqvpK9/wz\nDEJi75jUf8AlwFe7/wYwx5//qIfCY8DqJGd16XcFsKXnmuZjC7ChW97AYJx+JGXw3QO3ATuq6hND\nq0b+HJK86cAnK5KcAPwOgy9VHPnaAarqo1V1ZlWdzeDy/4tVdRVjUn+S1yc5qVs+kcG49nbGpP6q\n2gs8k+Scrum9wLeA+xmD+odcycGhI5jrz7/vCZFZTJhcwuBu56eB6/quZxb1bmZwV/bLDOZD/hBY\nyWDy8EngIeDkvus8TP2/wWA8+wng8e6xbhzOAXg78DXg6wxejP6qax/52mc4lwuBLeNUP4Mx+Se6\nxzcP/P86LvV3tf4q8JXud+hfGUw+j1P9JwL/BZw01Dan+r15TZLUjPrwkSRpGRkKkqTGUJAkNYaC\nJKkxFCRJjaEgSWoMBUlSYyhIkpr/AzN9i33ZKaSiAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10703a2b0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "_ = plt.hist(df_fl_a.dba.apply(lambda x: len(x) if pd.notnull(x) else 0))\n",
    "_ = plt.hist(df_oge_a_fl.trade_nm.apply(lambda x: len(x) if pd.notnull(x) else 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "It's also easy to make plots of aggregated or transformed data.  Here's a simple example where i plot histograms of the lengths of the business names in our matching data.  This might be useful to check that one source is not using a restricted-length field or lots of abbreviations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Comparing Records and Fields"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- What we want:\n",
    "\n",
    "$$\n",
    "IsMatch: A \\times B \\to \\{\\mathrm{true},  \\mathrm{false}\\}\n",
    "$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- In practice we compare against attributes of rA or rB to create a _comparison vector_\n",
    "\n",
    "$$\n",
    "Sim(r_{A}, r_{B}) = Sim(a_{1}, a_{2}..., a_{n}; b_{1}, b_{2}, ..., b_{n}) \\\\\n",
    "= [s_{1}(a_{1}, b_{1}), ..., s_{n}(a_{n}, b_{n})]\n",
    "$$\n",
    "\n",
    "- Then create a decision model to classify comparison as match or non-match"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "What we've seen in profiling the data is that there are certain fields in each data source that we can compare for equality or similarity.  What we really want is a function that will take any record pair and tell us if they are a match.  We could do that by limiting ourselves to cases where the attributes in each record are identical, but that would miss a lot of matches.\n",
    "\n",
    "The usual procedure is that we compare the two records attribute-by-attribute and end up with a _comparison vector_.  The comparison vector is then used in some sort of decision model or rule to decide if the pair is a match.  The next section will be about preprocessing fields to make them more easy to compare, and ways to measure similarity between various types of data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Preprocessing and Transformation\n",
    "\n",
    "- Simple text transformations: lowerize, remove punctuation\n",
    "- More complex:\n",
    "  - Replace patterns ('&' -> 'and')\n",
    "  - Standardize abbreviations, roman numerals, ordinals\n",
    "  - In some situations, remove stop words, use stemming\n",
    "  \n",
    "<span style=\"font-size:14pt;color:blue;\">POMODOROS PIZZA & SUBS & MORE II CORP -> pomodoros pizza and subs and more 2 corporation</span>\n",
    "\n",
    "- Standard length or format (eg, with zip codes)\n",
    "\n",
    "<span style=\"font-size:14pt;color:blue;\">34210-2862 -> 34210</span>\n",
    "\n",
    "- Parsing or tokenization\n",
    "\n",
    "<span style=\"font-size:14pt;color:blue;\">14132 TAMIAMI TRL -> (14132, tamiami trail) </span>\n",
    "\n",
    "- Data editing and imputation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "I won't go into the basic preprocessing operations since you've probably seen them in other contexts.  Here are a few examples of the types of transformations we might need to make before attempting to match."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# Process name and zip code fields\n",
    "name_prep = lambda x:x.lower().translate({None:\"'.,\"}) if pd.notnull(x) else ''\n",
    "df_fl_a['nname'] = df_fl_a.dba.apply(name_prep)\n",
    "df_oge_a_fl['nname'] = df_oge_a_fl.trade_nm.apply(name_prep)\n",
    "\n",
    "# Convert zip codes to 5 digits\n",
    "df_fl_a['nzip'] = df_fl_a.location_zip_code.apply(lambda x:x[0:5] if pd.notnull(x) else x)\n",
    "df_oge_a_fl['nzip'] = df_oge_a_fl.zip_cd.apply(lambda x: str(int(x)))\n",
    "\n",
    "# Split out street number into separate field\n",
    "df_fl_a['snum'] = df_fl_a.location_address.str.split(' ',1).apply(lambda x:x[0])\n",
    "df_oge_a_fl['snum'] = df_oge_a_fl.street_addr_1_txt.str.split(' ',1).apply(lambda x:x[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Here are some basic transformations that we'll apply to our test data, again using pandas apply.  Note the use of the .str property on the dataframe field to split out the street number."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Approximate String Comparison\n",
    "\n",
    "- NLTK\n",
    "  - Edit distance\n",
    "  - Jaccard distance\n",
    "- Difflib\n",
    "  - SequenceMatcher\n",
    "- Jellyfish\n",
    "  - __Levenshtein__ \n",
    "  - Jaro and __Jaro-Winkler__\n",
    "- FuzzyWuzzy\n",
    "\n",
    "- Token-Based\n",
    "  - __Jaccard similarity__\n",
    "  - __SoftTf-Idf__\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "There are dozens of string similarity methods, and several Python libraries that implement versions of them.  The methods shown in bold above are the ones that i'll discuss here.  These have different benefits and applications."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Levenshtein/Edit Distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "from jellyfish import levenshtein_distance\n",
    "print(levenshtein_distance('pydata', 'padata'))    # 1-character change\n",
    "print(levenshtein_distance('pydata', 'pandata'))   # Insert character\n",
    "print(levenshtein_distance('pydata', 'pandasa'))   # 1-character change\n",
    "print(levenshtein_distance('pydata', 'pandas'))    # Character deletion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The Levenshtein distance, or simply edit distance is the number of 1-character edits necessary to transform one string into another.  Despite it's simplicity, this is still in common use, even in sophisticated bioinformatics applications.  In matching applications, this can be useful in cases where manually entered data might have single-character errors or transpositions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Jaro\n",
    "\n",
    "$$\n",
    "Jaro(s_{1}, s_{2}) = w_{1}\\frac{c}{L_{1}} + w_{2}\\frac{c}{L_{2}} + w_{t}\\frac{c-\\tau}{c}\n",
    "$$\n",
    "where:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "& L_{1} \\mbox{ is length of }s_{1} \\\\\n",
    "& L_{2} \\mbox{ is length of }s_{2} \\\\\n",
    "& c \\mbox{ is number of characters in common } \\\\\n",
    "& \\tau \\mbox{ is number of transpositions } \\\\\n",
    "& w_{1}, w_{2}, w_{t} \\mbox{ are weights }\n",
    "\\end{align}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "\n",
    "###  Jaro-Winkler\n",
    "$$\n",
    "JaroWinkler(s_{1}, s_{2}) = Jaro(s_{1}, s_{2}) + 0.1 * i * (1 - Jaro(s_{1}, s_{2}))\n",
    "$$\n",
    "where:\n",
    "$$\n",
    "i = min(4, \\mbox{number of initial characters that match})\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The Jaro and Jaro-Winkler similarities were developed at the census bureau specifically for record-linkage applications. The Jaro-Winkler variant in particular often has the best ability to distinguish between matches and non-matches.  The greater weight on initial patterns has been shown empirically to improve matches.\n",
    "\n",
    "Note however that both of these are not true metrics-- that is they don't obey the triangle inequality, which makes them less appropriate for clustering applications."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Jaccard Similarity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.42857142857142855\n",
      "0.6666666666666666\n"
     ]
    }
   ],
   "source": [
    "def jaccard(s1, s2):\n",
    "    ''' Jaccard similarity score.  (1 - jaccard) is a valid distance metric '''\n",
    "    a = set(s1)\n",
    "    b = set(s2)\n",
    "    if len(a) == 0 and len(b) == 0:\n",
    "        return 0\n",
    "    return len(a & b) / len(a | b)\n",
    "\n",
    "print(jaccard('pydata', 'pandas'))\n",
    "print(jaccard(['bag', 'of', 'words'], ['words', 'bag']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The Jaccard similarity, or just set similarity, is the ratio of the size of the intersection of two sets to the size of the union.  This can be used for direct string comparisons, but it can also be used for other sets, such as tokens."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.1111111111111111\n",
      "0.0\n"
     ]
    }
   ],
   "source": [
    "# N-gram function courtesy of Peter Norvig\n",
    "def ngrams(seq, n):\n",
    "    \"List all the (overlapping) ngrams in a sequence.\"\n",
    "    return [seq[i:i+n] for i in range(1+len(seq)-n)]\n",
    "\n",
    "print(jaccard(ngrams('pydata', 2), ngrams('pandas', 2)))\n",
    "print(jaccard(ngrams('pydata', 3), ngrams('pandas', 3)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Jaccard similarity is also frequently used with character n-grams.  Again, this can be used directly as a string comparison, but there are other applications of this in blocking and clustering."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Comparing Similarity Measures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "outputs": [],
   "source": [
    "import jellyfish\n",
    "\n",
    "df_m = pd.read_csv('./data/matched.csv')\n",
    "df_u = pd.read_csv('./data/unmatched.csv')\n",
    "\n",
    "df_m['jaro'] = df_m[['nname_x','nname_y']].apply(lambda s: jellyfish.jaro_distance(s[0],s[1]),axis=1)\n",
    "df_m['jacc'] = df_m[['nname_x','nname_y']].apply(lambda s: jaccard(ngrams(s[0],2),ngrams(s[1],2)),axis=1)\n",
    "\n",
    "df_u['jaro'] = df_m[['nname_x','nname_y']].apply(lambda s: jellyfish.jaro_distance(s[0],s[1]),axis=1)\n",
    "df_u['jacc'] = df_m[['nname_x','nname_y']].apply(lambda s: jaccard(ngrams(s[0],2),ngrams(s[1],2)),axis=1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAsgAAAEACAYAAACu+IAyAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XuUVeWZ4P/vg4oSjJAKERFQGS9RMjMdW6HpeDumjaIi\navL7GTuO0YRxJRo7EifTYjozlJkZo/y0f609K+nOzWElE6KdtDbaRiG2pWZCJOnWREWCdEQEImoK\niHRQITzzRx2rN1CXU8W5Vn0/a51V++z9nrOffS5PPfXWu98dmYkkSZKkLiMaHYAkSZLUTCyQJUmS\npAILZEmSJKnAAlmSJEkqsECWJEmSCiyQJUmSpIJ+C+SIuCYinoqIpyPimvK6tohYGhGrImJJRIwt\ntL8+Ip6LiJURcWYtg5ckSZKqrc8COSL+LfAfgWnA7wGzIuJIYB6wNDOPAR4q3ycipgIfBqYCM4Ev\nRYS91JIkSWoZ/RWvxwKPZ+brmfk74BHgQ8BsYGG5zULggvLy+cCizNyemWuA1cD0qkctSZIk1Uh/\nBfLTwCnlIRVvA84BJgHjM3Njuc1GYHx5+VBgXeHx64CJVYxXkiRJqql9+9qYmSsj4mZgCfAvwJPA\n73ZrkxHR1/WqvZa1JEmSWkafBTJAZn4D+AZARPwPunqFN0bEIZn5UkRMAF4uN18PTC48fFJ53S76\nKaglqellZjQ6hnoxZ0tqdQPN2ZXMYnFw+edhwAeBbwOLgcvKTS4D7ikvLwYujoiRETEFOBpY3kug\nw+o2f/78hsfgMXvMQ/2YK1Gv/Qw1jX5vm+mzZhzNF0czxGAczRvHYPTbgwx8NyLeCWwHrsrMLRFx\nE3BXRMwB1gAXlRPoioi4C1gB7Ci3H56/TSQ1RF8JZ9h0+UqS9kolQyxO7WFdJ3BGL+1vBG7c+9Ak\nSZKk+nOO4joplUqNDqHuPObhYTgesxqjWT5rxrGrZoijGWIA49hds8QxGNGIERAR4cgLSVUXEf0O\nsahG7okIcpidpGfOltSqBpOzKxmDXDcRw+b3zbDiL1ZJktRKmqpABoupocY/eiRJUqtxDLIkSZJU\nYIEsSZIkFVggS5IkSQUWyEPE29/+dtasWVNR2xEjRvDLX/5ywNskSZKGg6YvkCOi5reBKJVKfP3r\nX6/R0XZZtmwZBx100C4nLF5xxRU9rrvyyisBeO211zjiiCNqGpckSdJw0PQFMnRdOrZWt4EaTFE9\n0GuBn3jiiezcuZN//Md/7F732GOPMXny5D3WnXbaaQOKpVZ27NjR6BAkSZKqoiUK5Ga0efNmZs2a\nxcEHH0xbWxvnnXce69ev795eKpX4/Oc/z0knncTo0aN5/vnn+dGPfsS0adMYO3Ys06dPZ9myZT0+\n93777ceMGTN49NFHAXj55ZfZvn07F1100S7rVq1axamndl0JvDg04vLLL+dTn/oUs2bN4qCDDmLG\njBm9Dpv44Q9/yGGHHdb9vEVvvPEGn/3sZzn88MM55JBDuPLKK3n99dcB6OjoYNKkSSxYsIAJEyYw\nZ86cQb6SkiRJzcUCeZB27tzJnDlzWLt2LWvXrmXUqFFcffXVu7T51re+xde+9jW2bt3K6NGjOffc\nc5k7dy6dnZ1ce+21nHvuuXR2dvb4/Keeemp30froo49y8sknc9JJJ+2ybsqUKRx66KE9Pv7OO++k\nvb2dTZs2cdRRR/Fnf/Zne7R54IEH+MhHPsLf/u3fdhfaRfPmzWP16tX87Gc/Y/Xq1axfv54vfOEL\n3ds3btzIpk2bWLt2LX/9139d2QsnSZLU5CyQB6mtrY0LL7yQAw44gAMPPJDPfe5zPPLII93bI4LL\nL7+c4447jhEjRrBkyRLe/e53c8kllzBixAguvvhijj32WO69994en//UU0/lhz/8IdA1lOLUU0/l\nD//wD/nxj3/cva63a5xHBB/84Ac58cQT2Weffbjkkkt48sknd2lz55138slPfpIHHniAE088cY/n\nyEy++tWv8ud//ueMHTuWAw88kOuvv57vfOc73W1GjBjBDTfcwH777ccBBxwwoNdPkiSpWTXdlfRa\nxbZt25g7dy4PPvggmzZtAmDr1q1kZvcY5cmTJ3e337BhA4cddtguz3H44YezYcMGAA488MDu8c0r\nVqxgxowZbN26laeffprHHnuMT33qU4wePZrJkyd3r7vmmmt6jW/8+PHdy6NGjWLr1q27bL/99tv5\n6Ec/ytSpU3t8/CuvvMJvf/tbTjjhhO51mcnOnTu777/rXe9i5MiRfb5OkiRJrcYe5EHITG655RZW\nrVrF8uXL2bJlC4888sgeJ+MVT+abOHEiL7zwwi7P88ILLzBx4kSgq7h+7bXX+M1vfsOkSZM44IAD\nmDZtGosXL+ZXv/oVxxxzDACnnHIKixcv5uc//3mPwyIq9Td/8zfcfffd3H777T1uHzduHKNGjWLF\nihVs2rSJTZs2sXnzZn7zm9/0eHySJElDhQXyIG3dupVRo0YxZswYOjs7ueGGG/ZoUyyWzznnHFat\nWsWiRYvYsWMHd955JytXrmTWrFm97uPUU0/ltttu46STTuped/LJJ3Pbbbdx6KGHMmXKlB4fV8mM\nGYceeigPPfQQt912G3/1V3+1x/YRI0ZwxRVXMHfuXF555RUA1q9fz5IlS/p9bkmSpFbWb4EcEZ+J\niKcj4qmI+HZE7B8RbRGxNCJWRcSSiBhbaH99RDwXESsj4sxqBBk1vA3GiBEjmDt3Ltu2bWPcuHG8\n733v4+yzz96jR7V4v62tjfvuu49bb72VcePGccstt3DffffR1tbW635OO+00Xn31VU4++eTudSed\ndBKvvPIKp5xySq/76mkqut23Q9cQkIceeoibbrqJb3zjG3u0u/nmmznqqKOYMWMGY8aM4QMf+ACr\nVq3q8TklSZKGiuirtzEiJgKPAcdl5hsRcSdwP/Ae4NXMXBAR1wHvyMx5ETEV+DYwDZgI/AA4JjN3\n7va82dN+I2JA8wU3wgknnMD8+fOZPXt2o0NpCa3wnmroiIg+5zcPKvsPS0X7yRw2fyH2lrMlqRUM\nJmdXMsRiX+BtEbEv8DZgAzAbWFjevhC4oLx8PrAoM7dn5hpgNTB9IAE1s2eeeYZnn32W448/vtGh\nSJIkqUb6LJAzcz1wK7CWrsJ4c2YuBcZn5sZys43AW1MmHAqsKzzFOrp6klveddddx1lnncWCBQt2\nmZ1CkiRJQ0uf07xFxDvo6i0+AtgC/E1E/Idim8zMiOjrf289bmtvb+9eLpVKvc7p2yxuvvlmbr75\n5kaHIakBOjo66OjoaHQYDdVqOVvS8FWNnN3fGOT/FzgrM/9j+f6lwAzg/cDpmflSREwAHs7MYyNi\nHkBm3lRu/wAwPzMf3+15W3YMsgbG91T15Bjk2nAMshqlkpPB/WyqP7UYg/wCMCMiRkXXp/QMYAVw\nL3BZuc1lwD3l5cXAxRExMiKmAEcDywcSkCRJ0luyj5tUK30OscjM5RHxXeCfgB3ln18B3g7cFRFz\ngDXAReX2KyLiLrqK6B3AVXY7SJIkqZX0OcSiZjt1iMWw4XuqenKIRW04xEKNUq/vtIa2Wk3zJkmS\nJA0bFsiSJElSQdMXyG9dNrmWt4EolUp8/etfr9HRSpIkqdH6PEmvabQ3z3MPpqh+a3zUQB8nSZKk\n+mv6HuRmtXnzZmbNmsXBBx9MW1sb5513HuvXr+/eXiqV+PznP89JJ53E6NGjef755/nRj37EtGnT\nGDt2LNOnT2fZsmUNPAJJkiT1xAJ5kHbu3MmcOXNYu3Yta9euZdSoUVx99dW7tPnWt77F1772NbZu\n3cro0aM599xzmTt3Lp2dnVx77bWce+65dHZ2NugIJEmS1BML5EFqa2vjwgsv5IADDuDAAw/kc5/7\nHI888kj39ojg8ssv57jjjmPEiBEsWbKEd7/73VxyySWMGDGCiy++mGOPPZZ77723gUchSZKk3bXG\nGOQmtG3bNubOncuDDz7Ipk2bANi6dSuZ2T3WePLkyd3tN2zYwGGHHbbLcxx++OG7DMuQJElS49mD\nPAiZyS233MKqVatYvnw5W7Zs4ZFHHiEzd5mwvHhS3sSJE3nhhRd2eZ4XXniBSZMm1S1uSZIk9c8C\neZC2bt3KqFGjGDNmDJ2dndxwww17tCkWy+eccw6rVq1i0aJF7NixgzvvvJOVK1cya9aseoYtSZKk\nfrTGEIv2RgewqxEjRjB37lw+8pGPMG7cOCZOnMi1117L4sWLd2lX7EFua2vjvvvu45prruHKK6/k\n6KOP5r777qOtra3e4UuSJKkP0YhrmEdE9rTf8rWy6x7PQJxwwgnMnz+f2bNnNzqUltAK76mGjoig\nr09bQFU+j+XP9bCZ2Ly3nC3VWr2+0xraBpOzHWIxAM888wzPPvssxx9/fKNDkSRJUo1YIFfouuuu\n46yzzmLBggW7zE4hSZKkocUhFqop31PVk0MsasMhFmoUh1ioGhxiIUmSJO2lfgvkiHh3RDxRuG2J\niE9HRFtELI2IVRGxJCLGFh5zfUQ8FxErI+LM2h6CJEmSVD0DGmIRESOA9cB04E+AVzNzQURcB7wj\nM+dFxFTg28A0YCLwA+CYzNxZeB6HWAwTvqeqJ4dY1IZDLNQoDrFQNdRjiMUZwOrMfBGYDSwsr18I\nXFBePh9YlJnbM3MNsJquglqSJElqegMtkC8GFpWXx2fmxvLyRmB8eflQYF3hMevo6kmWJEmSml7F\nV9KLiJHAecB1u2/LzIyIvv7Hsce29vb27uVSqUSpVKo0FPWio6ODSy+9lBdffLHRoUhDSkdHBx0d\nHY0Oo6HM2ZJaRTVydsVjkCPifODKzJxZvr8SKGXmSxExAXg4M4+NiHkAmXlTud0DwPzMfLzwXBWP\nQS5errlWBjJ+qVQqcemllzJnzpwaRjQ4zVggOwZZ9eQY5NpwDLIaxTHIqoZaj0H+Y/51eAXAYuCy\n8vJlwD2F9RdHxMiImAIcDSwfSFB7yhreBiYi6lK092fHjh2NDkGSJGlIqqhAjojRdJ2g97eF1TcB\nH4iIVcD7y/fJzBXAXcAK4PvAVUOx62Hz5s3MmjWLgw8+mLa2Ns477zzWr1/fvb2zs5OPfexjTJw4\nkba2Ni688MLubX/3d3/He9/7XsaMGcNRRx3Fgw8+CMAdd9zB1KlTOeiggzjyyCP5yle+0v2Yjo4O\nJk2axIIFC5gwYQJz5szh9ddf5/LLL6etrY33vOc9/OQnP6nfCyBJkjREVTQGOTP/BRi327pOuorm\nntrfCNy419E1sZ07dzJnzhy++93vsmPHDj7+8Y9z9dVXc/fddwNw6aWXctBBB7FixQpGjx7NsmXL\nAFi+fDmXXXYZ3/ve9/ijP/ojNmzYwGuvvQbA+PHj+fu//3umTJnCo48+ytlnn820adM4/vjjAdi4\ncSObNm1i7dq1/O53v6O9vZ3nn3+eX/7yl2zdupWZM2c2Re+2JElSK2v6S013FXy1jHFgY2RPP/10\nLr30Uj7+8Y/vsv7JJ5/k/e9/P52dnfzqV79i0qRJdHZ2MmbMmF3afeITn+DAAw/k1ltv7XdfF154\nIaeffjqf/vSn6ejo4KyzzuK1115j5MiRABx55JF8+ctf5swzu67F8tWvfpUvfOELjkHWsOUY5Npw\nDLIaxTHIqgYvNV1H27Zt4xOf+ARHHHEEY8aM4bTTTmPLli1kJi+++CJtbW17FMcA69at48gjj+zx\nOb///e8zY8YM3vnOd/KOd7yD+++/n1//+tfd29/1rnd1F8cAGzZsYPLkyd33DzvssCoeoSRJ0vBk\ngTwImcktt9zCqlWrWL58OVu2bOGRRx4hM8lMJk+eTGdnJ1u2bNnjsZMnT2b16tV7rH/jjTf40Ic+\nxJ/+6Z/y8ssvs2nTJs4555xd/jLeffjEhAkTWLt2bff94rIkSZIGxwJ5kLZu3cqoUaMYM2YMnZ2d\n3HDDDd3bJkyYwNlnn81VV13F5s2b2b59O48++igAc+bM4Y477uAf/uEf2LlzJ+vXr+cXv/gFb775\nJm+++Sbjxo1jxIgRfP/732fJkiV9xnDRRRfxxS9+kc2bN7Nu3Tr+8i//sqbHLEmSNBy0SIEcNbwN\n3IgRI5g7dy7btm1j3LhxvO997+Pss8/epYf3m9/8Jvvttx/HHnss48eP5/bbbwdg2rRp3HHHHXzm\nM59h7NixlEol1q5dy9vf/nZuv/12LrroItra2li0aBHnn3/+rq/Cbj3I8+fP5/DDD2fKlCnMnDmT\nj370o56kJ0mStJea/iS9ZnPCCScwf/58Zs+e3ehQWkIrvKcaOjxJrzY8SU+N4kl6qgZP0quxZ555\nhmeffbZ72jVJkiQNPRbIFbruuus466yzWLBgwS4zR0iSJGlocYiFasr3VPXkEIvacIiFGsUhFqqG\nweTsiq6kJ0lDRV8nsvqLVpIEFsiShpv2Aa6XJA07jkGWJEmSCpquB9l5fCVJktRITVUgO/5PkiRJ\njeYQC0mSJKnAAlmSJEkqqKhAjoixEfHdiHg2IlZExB9ERFtELI2IVRGxJCLGFtpfHxHPRcTKiDiz\nduFLkiRJ1VVpD/JtwP2ZeRzw74GVwDxgaWYeAzxUvk9ETAU+DEwFZgJfigh7qiVJktQS+i1cI2IM\ncEpmfgMgM3dk5hZgNrCw3GwhcEF5+XxgUWZuz8w1wGpgerUDlyRJkmqhkp7dKcArEXFHRPxTRHw1\nIkYD4zNzY7nNRmB8eflQYF3h8euAiVWLWJIkSaqhSqZ52xf4feDqzPxJRPwF5eEUb8nMjIi+5mjb\nY1t7e3v3cqlUolQqVRKvJNVdR0cHHR0djQ6joczZklpFNXJ29Df3cEQcAizLzCnl+ycD1wP/Bjg9\nM1+KiAnAw5l5bETMA8jMm8rtHwDmZ+bjhedM5zyWVG0Rsedf48Xt0OelpivNSxFBZg6bqxqZs9Uo\nlXyn/WyqP4PJ2f0OscjMl4AXI+KY8qozgGeAe4HLyusuA+4pLy8GLo6IkRExBTgaWD6QoCRJkqRG\nqfRKen8C/O+IGAn8M/AxYB/groiYA6wBLgLIzBURcRewAtgBXGXXgyRJklpFv0MsarJT/10nqQYc\nYlEb5mw1ikMsVA01GWIhSZIkDScWyJIkSVKBBbIkSZJUYIEsSZIkFVggS5IkSQUWyJIkSVKBBbIk\nSZJUYIEsSZIkFVggS5IkSQUWyJIkSVKBBbIkSZJUYIEsSZIkFVggS5IkSQUWyJIkSVKBBbIkSZJU\nUFGBHBFrIuLnEfFERCwvr2uLiKURsSoilkTE2EL76yPiuYhYGRFn1ip4SZIkqdoq7UFOoJSZx2fm\n9PK6ecDSzDwGeKh8n4iYCnwYmArMBL4UEfZUS5IkqSUMpHCN3e7PBhaWlxcCF5SXzwcWZeb2zFwD\nrAamI0mSJLWAgfQg/yAifhoRV5TXjc/MjeXljcD48vKhwLrCY9cBE/c6UkmSJKkO9q2w3UmZ+auI\neBewNCJWFjdmZkZE9vH4vrZJkiRJTaOiAjkzf1X++UpE3E3XkImNEXFIZr4UEROAl8vN1wOTCw+f\nVF63i/b29u7lUqlEqVQaTPySVHMdHR10dHQ0OoyGMmdLahXVyNmR2XfnbkS8DdgnM1+LiNHAEuAG\n4Azg15l5c0TMA8Zm5rzySXrfpquIngj8ADgqCzuKiOxvv5I0UBHR57+rAqC9l43tUGleiggyc/fz\nMoYsc7YapZLvtJ9N9WcwObuSHuTxwN0R8Vb7/52ZSyLip8BdETEHWANcBJCZKyLiLmAFsAO4yswq\nSZKkVtFvD3JNdmpvhKQasAe5NszZahR7kFUNg8nZzk8sSZIkFVggS5IkSQUWyJIkSVJBpfMgS5Ik\nSXVRnhyiT7Ucf26BLEmSpObTPshtVeAQC0mSJKnAAlmSJEkqsECWJEmSCiyQJUmSpAILZEmSJKnA\nAlmSJEkqsECWJEmSCpwHWZLK+puYvpaT0kuSmocFsiR166sA7v+qTpKkocEhFpIkSVKBPciSaqa/\nIQvgsAVJUvOpqAc5IvaJiCci4t7y/baIWBoRqyJiSUSMLbS9PiKei4iVEXFmrQKX1Bqyj5skSc2o\n0iEW1wAr+NffafOApZl5DPBQ+T4RMRX4MDAVmAl8KSIcxiFJkqSW0W/xGhGTgHOAr/GvZ6nMBhaW\nlxcCF5SXzwcWZeb2zFwDrAamVzNgSZIkqZYq6d39/4H/DOwsrBufmRvLyxuB8eXlQ4F1hXbrgIl7\nG6QkSZJUL30WyBExC3g5M5+glzmOsusMm76GEzrUUJIkSS2jv1ks3gfMjohzgAOAgyLim8DGiDgk\nM1+KiAnAy+X264HJhcdPKq/bQ3t7e/dyqVSiVCoN6gAktba+ZrponhkuOoBd89ZwY86W1Co6Ojro\n6OjYq+eISn8BRcRpwGcz87yIWAD8OjNvjoh5wNjMnFc+Se/bdI07ngj8ADgqd9tJROy+StIQFBH9\nX3qjvZeN7QMvkPd2f/1dKOSteCKCzBw2Vw4xZ6tRKvlO+9kcmiKi93wNA/odMZicPdB5kN+K5Cbg\nroiYA6wBLgLIzBURcRddM17sAK4yq0qSJKmVVFwgZ+YjwCPl5U7gjF7a3QjcWJXoJEmSpDpzjmJJ\nkiSpwAJZkiRJKrBAliRJkgoskCVJkqQCC2RJkiSpwAJZkiRJKrBAliRJkgoskCVJkqQCC2RJkiSp\nwAJZkiRJKrBAliRJkgoskCVJkqQCC2RJkiSpwAJZkiRJKrBAliRJkgoskCVJkqSCPgvkiDggIh6P\niCcj4umIaC+vb4uIpRGxKiKWRMTYwmOuj4jnImJlRJxZ4/glSZI0DEVEn7e90WeBnJmvA6dn5nuB\n9wIzI+IPgHnA0sw8BniofJ+ImAp8GJgKzAS+FBH2UkuSJKnKso/b3um3eM3M35YXRwL7lfc6G1hY\nXr8QuKC8fD6wKDO3Z+YaYDUwfa+jlCRJkuqk3wI5IkZExJPARmBJZi4HxmfmxnKTjcD48vKhwLrC\nw9cBE6sYryRJklRT+/bXIDN3Au+NiDHA3RHxb3fbnhHRV192j9va29u7l0ulEqVSqZJ4JakBOoBd\n89ZwY86W1Do6gL3L2ZFZ+TiNiPgvwG+BK4BSZr4UEROAhzPz2IiYB5CZN5XbPwDMz8zHd3ueHMh+\nJbWmiOhzJFgAtPeysR0Gmif2dn99j1uL7ngigszcuzNAWog5W41SyXfaz+bQFBG952uoec7ubxaL\ncW/NUBERo4APAM8Ci4HLys0uA+4pLy8GLo6IkRExBTgaWD6QgCRJkqRG6m+IxQRgYUTsQ1cxfWdm\n3h8RPwbuiog5wBrgIoDMXBERdwErgB3AVXY7SJIkqZX0WSBn5lPA7/ewvhM4o5fH3AjcWJXoJNVV\nf/NG+veuJGk46PckPUnDTPsA10uSNMR4EQ9JkiSpwAJZkiRJKrBAliRJkgocgyxJkqQe9XfyNgzN\nE7gtkCVJktS79kFua2EOsZAkSZIKLJAlSZKkAgtkSZIkqcACWZIkSSqwQJYkSZIKLJAlSZKkAgtk\nSZIkqcACWZIkSSqwQJYkSZIKLJAlSZKkgn4L5IiYHBEPR8QzEfF0RHy6vL4tIpZGxKqIWBIRYwuP\nuT4inouIlRFxZi0PQJIkSaqmSnqQtwOfycz3ADOAT0XEccA8YGlmHgM8VL5PREwFPgxMBWYCX4oI\ne6olSZLUEvotXDPzpcx8sry8FXgWmAjMBhaWmy0ELigvnw8sysztmbkGWA1Mr3LckiRJUk0MqGc3\nIo4AjgceB8Zn5sbypo3A+PLyocC6wsPW0VVQS5IkSU1v30obRsSBwPeAazLztYjo3paZGRHZx8P3\n2Nbe3t69XCqVKJVKlYYiSXXWAeyat4Ybc7bUWMW6qzeZfZViw0kHsHc5Oyp5MSNiP+A+4PuZ+Rfl\ndSuBUma+FBETgIcz89iImAeQmTeV2z0AzM/MxwvPl76JUvOJCGjvZWP7wJNvROz513Fxe/l5m2V/\nPfwtv8uj34onIsjM/n9bDRHmbDVKJd/p4fLZ7DM/w6ByZqvvt5Y5u5JZLAL4OrDireK4bDFwWXn5\nMuCewvqLI2JkREwBjgaWDyQoSZIkqVEqGWJxEvAfgJ9HxBPlddcDNwF3RcQcYA1wEUBmroiIu4AV\nwA7gKrseJEmS1Cr6LZAz84f03tN8Ri+PuRG4cS/ikiRJkhrC+YklSZKkAgtkSZIkqcACWZIkSSqw\nQJYkSZIKLJAlSZKkAgtkSZIkqcACWZIkSSqo5EIhkirUdeHJ3nnNHEmSmp8FslR1vRXBA7oMvCRJ\nahALZEkVs4dckjQcWCBLGoC+CmB7yCVJQ4Mn6UmSJEkF9iBLLcwhD5JUff3lVjC/DnUWyFLL86RA\nSao2B5QNbxbIqqt693jawypJkgbKAlkNUO8eT3tYJUlS5fo9SS8ivhERGyPiqcK6tohYGhGrImJJ\nRIwtbLs+Ip6LiJURcWatApckSZJqoZJZLO4AZu62bh6wNDOPAR4q3ycipgIfBqaWH/OliHCmDEmS\nJLWMfovXzHwM2LTb6tnAwvLyQuCC8vL5wKLM3J6Za4DVwPTqhCpJklS5iOj3NpQMp2OttcH27o7P\nzI3l5Y3A+PLyocC6Qrt1wMRB7kOSJGkvZR+3oWY4HWtt7fVJepmZEdHXK9/jtvb29u7lUqlEqVTa\n21A0CM7yoGbWPJ/PDmDXvDXcmLMltY4OYO9ydlTyCyYijgDuzcx/V76/Eihl5ksRMQF4ODOPjYh5\nAJl5U7ndA8D8zHx8t+dLC6/m0FWA9D7LQ22mXXN/zbq/iID2Xja208e+et5fRPQ/l2gL7i8iyMxh\n8/9Kc7YapZLvdF+fzb5zZNcz9PT46uy3d4P5PvWZn2FQObNa+61Ffqjm8Q4mZw92iMVi4LLy8mXA\nPYX1F0fEyIiYAhwNLB/kPiRJklqUQx1aWb9DLCJiEXAaMC4iXgT+K3ATcFdEzAHWABcBZOaKiLgL\nWAHsAK6y20GSJEmtpN8COTP/uJdNZ/TS/kbgxr0JSpIkSWoUr6QnSdIwUclUXzUbT9qA/UqDZYEs\nSVIDNG6/24QUAAAIoElEQVSWln5PZR1i+5UGzgJZkqSG6X0WGkmN42WgJUmSpAJ7kCVJkgbISzcP\nbRbITcYTGSSpvsy7GpT2QW4bgprnqqfVY4HclDyRQZLqy7yr4ak6PeFD7/tjgSw1Mf+FJ0mqtaFX\n3u49C2Sp2bUPcpskSRoUC2RpmLFXWpKkvlkgS8OQM69KktQ750GWJEmSCiyQJUmSpAILZEmSJKnA\nAlmSJEkqqMlJehExE/gLYB/ga5l5cy32Iw0FziohwcaNG3nllVf6bDNhwgTe+c531ikiScNZ1Qvk\niNgH+J/AGcB64CcRsTgzn632vmpt2bJltLffwu9+1/P2kSPhm9/8SkUJu6Ojg1KpVN0Am9xwPObB\nau1ZJTqAUoNjUKu7/fa/5NZbv8L++x/c4/bXX9/AJz95KbfddludI9tTs+Q242iuGAB4HpgyuIdW\nt7Okg+bIyx2NDmDQatGDPB1YnZlrACLiO8D5QMsVyOvXr+exx9azbdt/7nH7yJFXsG3btoqeq2m+\nvHU0HI95eOqgORKxWlkmvPHGp3njjc/3uH3//a/mueeeq3NUPWuW3GYczRUDAGsYdIEM1byiXQfN\nkZc7Gh3AoNWiQJ4IvFi4vw74gxrspy72228S27Z9qMdt++57TZ2jkSRJUq3VokDu6w+ghrjhhhv4\n6U9/2uO2Qw45hJdeeqnHbRs2bOCNN9Zz0EHn9bj9t799tWoxSlKr+9jHPsarr/aeF0eOHMmbb77Z\n47Zf/GIV++8P++//eI/b33zzKWBqNcKUpH5FZnXr2YiYAbRn5szy/euBncUT9SKi6YpoSRqIzGyN\nIeJVYM6W1OoGmrNrUSDvC/wC+CNgA7Ac+ONWPElPkiRJw0/Vh1hk5o6IuBp4kK5p3r5ucSxJkqRW\nUfUeZEmSJKmV1fRKehExMyJWRsRzEXFdL21uL2//WUQcX8t46qG/Y46IS8rH+vOI+D8R8e8bEWc1\nVfI+l9tNi4gdEfHBesZXbRV+rksR8UREPB0RHXUOseoq+FyPiYh7I+LJ8jFf3oAwqyYivhERGyPi\nqT7aDKncBRW9z8dGxLKIeD0i/lMD46hLHq0gjvPLcTwRET+JiJPqHUOhXU3zawWvRSkitpRfiyci\nouf5+mocRyGWmubfCl6PzxZei6fK783YBsRRl9xcQRzviIi7y9+XxyPiPTWIobp5OzNrcqNreMVq\n4AhgP+BJ4Ljd2pwD3F9e/gPgx7WKpx63Co/5D4Ex5eWZw+GYC+3+AbgP+FCj467xezwWeAaYVL4/\nrtFx1+GYPwd88a3jBX4N7Nvo2PfimE8Bjgee6mX7kMpdA3if3wWcCPx34D81MI6a59EK4xhdWP53\nwLP1jqHQrmb5tcLXogQsboLPaM3zb6XvS6H9LOAHDXo9ap6bK4zj/wP+S3n53TV6Paqat2vZg9x9\nwZDM3A68dcGQotnAQoDMfBwYGxHjaxhTrfV7zJm5LDO3lO8+Dkyqc4zVVsn7DPAnwHeBvq8l2/wq\nOd6PAN/LzHUAmdnq8wFWcsw7gYPKywcBv87MHXWMsaoy8zFgUx9Nhlrugsry1yuZ+VNge4PjqEce\nrSSOfyncPZCu70FdYyirdX6tNI5az+zSLPm30tejGNOiBsVRj9xcSRzHAQ8DZOYvgCMi4l3VDKLa\nebuWBXJPFwyZWEGbVi4YKznmojnA/TWNqPb6PeaImEjXl+XL5VWtPPC9kvf4aKAtIh6OiJ9GxKV1\ni642Kjnm/wlMjYgNwM+AoX4VnaGWu2Dg+atZ4qhVHq0ojoi4ICKepav39uP1jqFO+bWS1yKB95X/\ndX1/RNRi0upmyb8Vf0Yj4m3AWcD3GhRHPXJzJXH8DPggQERMBw6n/jlzQHm7FhcKeUulX9Ld/+Js\n5eKp4tgj4nS6kmnVx6zVWSXH/BfAvMzMiAhq38tQS5Uc737A79M11eHbgGUR8ePMbI7r5A5cJcc8\nE/inzDw9Io4ElkbE72XmazWOrZGGUu6C5om/WfJoRXFk5j3APRFxCl1DTz5Q5xjqkV8rieOfgMmZ\n+duIOBu4BzimAXHUI/8O5LtyHvDDzNxcxf0PJI565OZK4rgJuC0ingCeAp4AflfFGCpVcd6uZYG8\nHphcuD+Zrmq9rzaTyutaVSXHTPmEkq8CMzOzr38HtIJKjvkE4DtduZtxwNkRsT0zF9cnxKqq5Hhf\nBF7NzG3Atoh4FPg9oFUL5EqO+XLgiwCZ+c8R8Txd48x6voRl6xtquQsqzF/NEkcd8uiAXo/MfCwi\n/k1EtGVmZx1jqEd+7TeOYsGVmd+PiC9V+bWoKA7qk38H8tm4mNoMr6g0jsupfW6u9PPR/R+Wchy/\nrGIMlRhY3q72IOnCYOh9gX+ma9D2SPo/SW8GLX6iS4XHfBhdg9lnNDreeh3zbu3vAD7Y6Lhr/B4f\nC/yArhMX3kbXX8tTGx17jY/5S8D88vJ4upJjW6Nj38vjPoLKTvZo+dxV6ftcaNtO7U7Sa4o8WmEc\nR/Kv06X+PvBio96Tcvua5NcKX4vxhddiOrCmQXHUPP9W+r4AY+g6KW5UAz+jNc/NFcYxBhhZXr4C\n+F81ek2OoEp5u2Y9yNnLBUMi4hPl7X+dmfdHxDkRsRr4F+BjtYqnHio5ZuC/Au8Avlz+i397Zk5v\nVMx7q8JjHjIq/FyvjIgHgJ/TdYLEVzNzReOi3jsVvsf/DfhfEfFzuv6F9adZ3Z6juoqIRcBpwLiI\neBGYT9e/bodk7oLK3ueIOAT4CV0n++yMiGvoKj621jMO6pBHK4zjQ8BHI2I7sA34cANiqLkK4/h/\ngCsjYgfwW7p6TuseRz3y7wDelwuAB7OrN7vqmiU3VxjH1HIcCTxN17kDVVXtvO2FQiRJkqSCml4o\nRJIkSWo1FsiSJElSgQWyJEmSVGCBLEmSJBVYIEuSJEkFFsiSJElSgQWyJEmSVGCBLEmSJBX8X8MN\n67SuIl5XAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1108e1ac8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "f, (ax1, ax2) = plt.subplots(1, 2, sharey=True)\n",
    "f.set_size_inches(12,4)\n",
    "_=ax1.hist(df_m[['jw','jaro', 'jacc']].values, \n",
    "           color=['r', 'g', 'b'], \n",
    "           label=['Jaro-Winkler', 'Jaro', 'Jaccard'],\n",
    "           histtype='bar')\n",
    "_=ax1.legend(loc='upper left')\n",
    "_=ax2.hist(df_u[['jw','jaro', 'jacc']].values, \n",
    "           color=['r', 'g', 'b'], \n",
    "           label=['Jaro-Winkler', 'Jaro', 'Jaccard'],\n",
    "           histtype='bar')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The graph on the left shows similarity scores for names determined to be matched records, while the right graph shows the same metrics on the 1000 non-matches with the greatest similarity.  You can see that the Jaro-Winkler metric has the best ability to distinguish between matches and non-matches."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Further Reading\n",
    "\n",
    "- Term Frequency-Inverse Document Frequency (Tf-Idf)\n",
    "- SoftTfIdf\n",
    "- Adaptive measures and learning parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "There are certain more sophisticated string comparison methods that can be used if you leverage information about the whole set of possible items to compare.  The term frequency-inverse document frequency method is often used in information retrieval applications to cluster and search for larger documents, like web pages or news articles.  It essentially amounts to creating vectors that describe documents and then using cosine similarity on those vectors to find similar documents.  The SoftTf-IDF method uses the same basic idea, except that it only requires the tokens in the document to be similar as defined by some secondary metric (such as Jaro-Winkler)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Human Names\n",
    "\n",
    "|  Name |  Source  |\n",
    "| --- |  --- |\n",
    "| RICHARD ALLAN BREGGER | Finra |\n",
    "| RICHARD A BREGGER | DOL |\n",
    "| BREGGER RICHARD A | DOL |\n",
    "| RICHAPT) A BREGGER | DOL (OCR error) |\n",
    "| RICHARD A BREGGER AXA FINANCIAL | DOL |\n",
    "| RICHARD D BREGGER | DOL |\n",
    "| RICHARDBREGGER | Record Keeper |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<img src='bregger.png'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "There are no human names in my test data, so i'll use an example from some financial advisor data.  The table above has several variations of a particular name that came from actual data sources.  It's fairly certain that these are all references to the same person.  The kicker is that if you search for this person on Google, the top result returned indicates that he actually goes by \"Rick\", not Richard."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Stupid Human (Name) Tricks\n",
    "- Almost always want to parse names into (first, middle or MI, last)\n",
    "   - Do not use regex\n",
    "- Substituting first names is helpful, but build your own database of alternatives\n",
    "- As you match, retain alternatives and do look-ups {'RICHARDBREGGER': 'richard a bregger'}\n",
    "- Sometimes worthwhile to match on a related item first, for example, employer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Depending on the data source, human names will be either a single field, or separate fields for first, middle, and last names; plus maybe titles or suffixes.  For matching purposes it's almost always preferable to parse names given in a single field into the latter form.  It's usually preferable to use a specialized name parser for such a thing, rather than trying to roll your own with regular expressions.\n",
    "\n",
    "One special situation with human names is the use of alternate first names (Rick, Mike, Maggie).  In many applications it's worthwhile to check these variants, however you have to be careful with existing first name alternative databases.  They often have dozens of extremely rare variations, so it's usually better to add the variations that are most likely.\n",
    "\n",
    "Another complication with human names is that they change.  Often with surname changes or other significant name variations, the only way to match is to discover the relationship from other sources, and then keep a look-up table."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### The _nameparser_ library"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<HumanName : [\n",
       "\ttitle: 'DR.' \n",
       "\tfirst: 'RICHARD' \n",
       "\tmiddle: 'ALLAN' \n",
       "\tlast: 'BREGGER' \n",
       "\tsuffix: 'CFP'\n",
       "\tnickname: 'Rick'\n",
       "]>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from nameparser import HumanName\n",
    "\n",
    "HumanName('DR. RICHARD ALLAN \"Rick\" BREGGER, CFP')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The _nameparser_ library is a good tool for parsing names in your own applications.  It does a very good job, even on complicated names provided that the format is not too bogus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<HumanName : [\n",
       "\ttitle: '' \n",
       "\tfirst: 'RICHARD' \n",
       "\tmiddle: 'A' \n",
       "\tlast: 'BREGGER' \n",
       "\tsuffix: ''\n",
       "\tnickname: ''\n",
       "]>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HumanName('BREGGER, RICHARD A')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<HumanName : [\n",
       "\ttitle: '' \n",
       "\tfirst: 'BREGGER' \n",
       "\tmiddle: 'RICHARD' \n",
       "\tlast: 'A' \n",
       "\tsuffix: ''\n",
       "\tnickname: ''\n",
       "]>"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HumanName('BREGGER RICHARD A')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "However, it's not magical.  Since it relies primarily on certain syntactical elements, it won't get some common cases correct.  For instance, here it's relying on the comma to know that this name is in last name, first name order."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Addresses and Geocoding\n",
    "- Addresses are more frequently separated into multiple fields, usually street address, city, state, zip code in the source data.\n",
    "- Zip codes have 3,5, and 9 (Zip+4) variants\n",
    "- Since Zip codes are designed for efficiency of mail delivery, they aren't a consistent indicator of physical proximity.\n",
    "  - Zips are not even areas\n",
    "- The street number can be a useful identifier\n",
    "- Different businesses might have identical addresses (aka, \"the food-court effect\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Addresses are even tricker than human names, but there are two factors that help.  One is that addresses are most often already separated into multiple fields in data sources.  The other is that there's a long history of GIS research.  Zip codes, as in our test data, are often very useful on their own, but you do have to be careful with them since they really only describe mail delivery routes and not bounded geographical areas of any particular size.  Also note that having _identical_ addresses does not mean that two entities refer to the same thing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>dba</th>\n",
       "      <th>location_address</th>\n",
       "      <th>location_city</th>\n",
       "      <th>location_zip_code</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>129483</th>\n",
       "      <td>HOSTED GOURMET</td>\n",
       "      <td>39 S BENEVA RD</td>\n",
       "      <td>SARASOTA</td>\n",
       "      <td>34232</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>129503</th>\n",
       "      <td>STAMPER CHEESE COMPANY</td>\n",
       "      <td>39 S BENEVA RD</td>\n",
       "      <td>SARASOTA</td>\n",
       "      <td>34232</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>129507</th>\n",
       "      <td>MOUTHOLE BBQ</td>\n",
       "      <td>39 S BENEVA RD</td>\n",
       "      <td>SARASOTA</td>\n",
       "      <td>34232</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>129515</th>\n",
       "      <td>PALEO CONNECTION LLC</td>\n",
       "      <td>39 S BENEVA RD</td>\n",
       "      <td>SARASOTA</td>\n",
       "      <td>34232</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>129516</th>\n",
       "      <td>DOLCE VITA LLC</td>\n",
       "      <td>39 S BENEVA RD</td>\n",
       "      <td>SARASOTA</td>\n",
       "      <td>34232</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>129517</th>\n",
       "      <td>BRICKS BBQ</td>\n",
       "      <td>39 S BENEVA RD</td>\n",
       "      <td>SARASOTA</td>\n",
       "      <td>34232</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>129521</th>\n",
       "      <td>WINGS ON WHEELS LLC</td>\n",
       "      <td>39 S BENEVA RD</td>\n",
       "      <td>SARASOTA</td>\n",
       "      <td>34232</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>130612</th>\n",
       "      <td>MOBILE BISTRO</td>\n",
       "      <td>39 S BENEVA RD</td>\n",
       "      <td>SARASOTA</td>\n",
       "      <td>34240</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>130625</th>\n",
       "      <td>RI QUISIMO</td>\n",
       "      <td>39 S BENEVA RD</td>\n",
       "      <td>SARASOTA</td>\n",
       "      <td>34232</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                           dba location_address location_city  \\\n",
       "129483          HOSTED GOURMET   39 S BENEVA RD      SARASOTA   \n",
       "129503  STAMPER CHEESE COMPANY   39 S BENEVA RD      SARASOTA   \n",
       "129507            MOUTHOLE BBQ   39 S BENEVA RD      SARASOTA   \n",
       "129515    PALEO CONNECTION LLC   39 S BENEVA RD      SARASOTA   \n",
       "129516          DOLCE VITA LLC   39 S BENEVA RD      SARASOTA   \n",
       "129517              BRICKS BBQ   39 S BENEVA RD      SARASOTA   \n",
       "129521     WINGS ON WHEELS LLC   39 S BENEVA RD      SARASOTA   \n",
       "130612           MOBILE BISTRO   39 S BENEVA RD      SARASOTA   \n",
       "130625              RI QUISIMO   39 S BENEVA RD      SARASOTA   \n",
       "\n",
       "       location_zip_code  \n",
       "129483             34232  \n",
       "129503             34232  \n",
       "129507             34232  \n",
       "129515             34232  \n",
       "129516             34232  \n",
       "129517             34232  \n",
       "129521             34232  \n",
       "130612             34240  \n",
       "130625             34232  "
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_fl_a[df_fl_a.location_address=='39 S BENEVA RD'][['dba',\n",
    "                     'location_address',\n",
    "                     'location_city',\n",
    "                     'location_zip_code']]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "For example...  Note also that one of these items has a different zip code, which tells us that we can't always rely on zip codes being correct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Geocoders\n",
    "Geocoding is translating an address into latitude and longitude.\n",
    "\n",
    "- Google\n",
    "- OpenStreetMap Nominatim\n",
    "- geocoder.us\n",
    "- TIGER\n",
    "  - Addon for PostGIS\n",
    "  - Uses US Census Bureau TIGER Geodatabases"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Geocoders can be very useful with address data if it is of sufficiently good quality.  Their main purpose is to translate an address in to latitude and longitude (or vice versa); but they have a side-benefit of tokenizing address components.  There are numerous geo-coding services some of which are listed here, however many of them cost money, which can be a problem if you have millions of addresses to handle.  One \"free\" option is the TIGER geocoder, which is part of the PostGIS addon for Postgres."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "```\n",
    "SELECT g.rating, ST_X(g.geomout) As lon, ST_Y(g.geomout) As lat, \n",
    "(addy).address As stno, (addy).streetname As street, \n",
    "(addy).streettypeabbrev As styp, (addy).location As city, (addy).stateabbrev As st,(addy).zip \n",
    "FROM geocode('555 Lake Border Drive, Apopka, FL 32703') As g; \n",
    "\n",
    " rating |        lon        |       lat        | stno |   street    | styp |  city  | st |  zip  \n",
    "--------+-------------------+------------------+------+-------------+------+--------+----+-------\n",
    "      0 | -81.4651538792139 | 28.6714046741846 |  555 | Lake Border | Dr   | Apopka | FL | 32703\n",
    "```\n",
    "\n",
    "| Address | Rating | Street # | Longitude | Latitude |\n",
    "| ------- | ------ | --------- | -------- |\n",
    "| 555 Lake Border Drive, Apopka, FL 32703| <span style=\"color:blue\">0</span> | 555 | -81.4651538792139 | 28.6714046741846 |\n",
    "| 5555 Lake Border Drive, Apopka, FL 32703| <span style=\"color:blue\">10</span> | <span style=\"color:red\">699</span> | -81.4651087639419 | 28.6712609342955 |\n",
    "| Apopka, FL 32703| <span style=\"color:blue\">100</span> || -81.552957384847 | 28.6706870842484 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The top part of this slide shows how you can invoke the TIGER geocoder from psql.  Obviously, you can put a Python wrapper around this fairly trivially, although there are also sophisticated tools like GeoDjango that you can use.\n",
    "\n",
    "Note that geocoders are only as good as the data passed in.  Usually the return value of a geocoder will included an indicator of the quality of the data.  The table here shows three different addresses and their associated ratings.  The first is a correct address that the geocoder can identify precisely.  The second is an incorrect address, and so the geocoder makes a best guess on the intended address.  The third item has only the city and zip, so the geocoder can only return latitude and longitude for some reference position within that zip code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Comparing Locations\n",
    "- To compute actual _distance_ you need to use Vincenty or Great Circle distance\n",
    "- However for comparison, L1 norm will probably work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.003462872373274787, 6.092525294477768)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from geopy.distance import vincenty\n",
    "\n",
    "l0 = (-81.4651538792139,  28.6714046741846)\n",
    "l10 = (-81.4651087639419, 28.6712609342955)\n",
    "l100 = (-81.552957384847,  28.6706870842484)\n",
    "\n",
    "vincenty(l0, l10).miles, vincenty(l0, l100).miles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "If you want to calculate the precise distance between points, you have to use a calculation like the Great Circle distance that takes into account that you're moving along a curved surface.  However, in matching you can often just subtract the component parts and sum them (ie the L1 norm).\n",
    "\n",
    "Here i'm using the geopy library to calculate the distances between the points we found above.  Note that the distance between the correct address and the zip-only address is 6 miles."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Further Reading\n",
    "\n",
    "- Hidden Markov Models\n",
    "- Conditional Random Fields"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "There's been a lot of work on intelligent ways to segment name and address fields using techniques like hidden markov models and conditional random fields."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Blocking/Indexing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table border=\"1\" class=\"dataframe block_rows\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>nname_x</th>\n",
       "      <th>nname_y</th>\n",
       "      <th>sndx</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>gayou's restaurant</td>\n",
       "      <td>gasca, rosendo h. flc</td>\n",
       "      <td>G262</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>gayou's restaurant</td>\n",
       "      <td>geysers international inc</td>\n",
       "      <td>G262</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>gayou's restaurant</td>\n",
       "      <td>geysers international, inc.</td>\n",
       "      <td>G262</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>geiger key marina and fish camp</td>\n",
       "      <td>g.w. sharkeys raw bar &amp; grill</td>\n",
       "      <td>G262</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>geiger key marina and fish camp</td>\n",
       "      <td>gasca, rosendo h. flc</td>\n",
       "      <td>G262</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>geiger key marina and fish camp</td>\n",
       "      <td>geysers international inc</td>\n",
       "      <td>G262</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>geiger key marina and fish camp</td>\n",
       "      <td>geysers international, inc.</td>\n",
       "      <td>G262</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>g w sharkeys raw bar and grill</td>\n",
       "      <td>g.w. sharkeys raw bar &amp; grill</td>\n",
       "      <td>G262</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>g w sharkeys raw bar and grill</td>\n",
       "      <td>gasca, rosendo h. flc</td>\n",
       "      <td>G262</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>g w sharkeys raw bar and grill</td>\n",
       "      <td>geysers international inc</td>\n",
       "      <td>G262</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>g w sharkeys raw bar and grill</td>\n",
       "      <td>geysers international, inc.</td>\n",
       "      <td>G262</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_fl_a['sndx'] = df_fl_a.nname.apply(jellyfish.soundex)\n",
    "df_oge_a_fl['sndx'] = df_oge_a_fl.nname.apply(jellyfish.soundex)\n",
    "df_blocks = df_fl_a[df_fl_a.sndx=='G262'].merge(df_oge_a_fl[df_oge_a_fl.sndx=='G262'], \n",
    "                                    on='sndx')[['nname_x','nname_y','sndx']].ix[5:15]\n",
    "HTML(df_blocks.to_html(classes='block_rows'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Blocking is the process of reducing the number of record pairs that need to be compared.  Our example case has over 800 million record pairs in A x B. That's not huge by today's standards, but you can see that the larger our data sets get, the more we want to eliminate record pairs.  Above is shown a traditional method for blocking, where records in the two data sets are _candidates_ if they have the same soundex value.  Soundex is a code that's supposed to indicate strings that begin with similar sounds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "$('.block_rows tbody tr').filter(':eq(7)')\n",
       "                                             .css('background-color', '#66cd00');                                             \n",
       "                   "
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Javascript('''$('.block_rows tbody tr').filter(':eq(7)')\n",
    "                                             .css('background-color', '#66cd00');                                             \n",
    "                   ''')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Using Key Properties"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAARIAAAEACAYAAAB/KfmzAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAEExJREFUeJzt3X+s3XV9x/HnC0oVhFmJWwulySURIp06lfBDHZEYhp2S\nwl+AmYY4tj9kU6LG0eocNEaCJv5gf2CyiVtHpNrpJPgLW0CYSyZFBQVLLV28Gy229cdw4qa04b0/\nzrfl9NJe2vO5Pefc2+cjObmf8/n+et/mnlc/3+/5fM9JVSFJLY4adQGSZj+DRFIzg0RSM4NEUjOD\nRFIzg0RSs6EGSZJlSTYleTTJNcM8tqTDJ8OaR5LkaOBHwAXANuB+4C1V9chQCpB02AxzRHI2sKWq\nJqtqF/A54OIhHl/SYTLMIFkMPNb3fGvXJ2mWG2aQOBdfmqPmDfFY24Alfc+X0BuV7JXEsJFGpKoy\n6LbDDJLvAKclmQAeBy4D3jJ1pWu7n5t4KZ/nsqEVN7h7gPNHXMOhuIfZVS9Y8zCsatp6aEFSVbuT\n/CXwDeBo4GbfsZHmhmGOSKiqrwNfH+YxJR1+zmxtNjHqAg7RxKgLGMDEqAsYwMSoCxgqg6TZxKgL\nOEQToy5gABOjLmAAE6MuYKgMEknNDBJJzQwSSc0MEknNDBJJzQwSSc0MEknNDBJJzYb2CWkHo3f3\nb++2vZeyicv4/EFtt2rvrX6SBrOq6e5fRySSmo3tiORQvJmv8lXefBgqko4Ujkh4CVtGXYJ0RJsT\nQSJptAwSSc0MEknNhvoJaYfLp3gHK7jhgMtvYMUQq5GOPHMiSJ5iPs/jt6MuQzpieWojqZlBIqmZ\nQSKp2Zy4RgLT329z7ZQv//HeHGlmOSKR1MwgkdTMIJHUzCCR1MwgkdTMIJHUzCCR1GzOzCOZztR5\nI1PnlQziK1zEdzmzeT/SXHBEBMlU3+bc5n28gF9zLt8+rMeQZosjMki+wRub93ERX+FMvnvA5QaJ\njiReI5HUzCCR1MwgkdRsoCBJsiTJN5P8MMnDSd7V9Z+YZH2SzUnWJVnQt83KJI8m2ZTkwpn6BSSN\n3qAjkl3Au6vq94Fzgb9IcgawAlhfVacDd3XPSbIUuAxYCiwDbkriaEiaIwZ6MVfV9qp6sGs/CTwC\nLAaWA6u71VYDl3Tti4E1VbWrqiaBLcDZDXVLGiPNo4IkE8CrgPuAhVW1o1u0A1jYtU8GtvZttpVe\n8EiaA5rmkSQ5HvgicHVV/Sp55qtDq6p63+V7QAdYdk9fe6J7SJpZk91jZgwcJEmOoRcit1TVbV33\njiSLqmp7kpOAnV3/NmBJ3+andH37cf6gJUk6aBPs+5/0vU17G/RdmwA3Axur6pN9i24HrujaVwC3\n9fVfnmR+klOB04ANg5UsadwMOiJ5HfBW4AdJHuj6VgI3AGuTXElv3HQpQFVtTLIW2AjsBq6qqulO\neyTNIgMFSVX9GwcezVxwgG2uB64f5HiSxptzOSQ1M0gkNTNIJDUzSCQ1M0gkNTNIJDUzSCQ1M0gk\nNTNIJDUzSCQ1M0gkNTNIJDUzSCQ1M0gkNTNIJDUzSCQ1M0gkNTNIJDVr+jqKI9kOFrKZ00ddhjQW\nDJIB3c9Z3M9ZB1x+LatYxbVDrEgaHU9tDpPHWMKx/N+oy5CGwhHJYfIZ/hTojUymczNXspVThlGS\ndNg4IpHUzCCR1MwgkdTMIJHUzCCR1MwgkdQsVTXqGvZKUhxhk7jm8xTv4eMA3MCKEVejI9cqqiqD\nbu08khF7ivk8j9+OugypiUEyBm7k6r3tq7kRgJ/xYj7Ln4yqJOmQGCRj4AkW7G0v4AmgN1KRZgsv\ntkpq5sXWMfV77OQdfOpZ/d5RrMOj7WKrQTLL7LkJcDfz+DAfGHE1mjvagqTp1CbJ0UkeSPLl7vmJ\nSdYn2ZxkXZIFfeuuTPJokk1JLmw5rqTx0jQiSfIe4EzghKpanuSjwM+q6qNJrgFeVFUrkiwFbgXO\nAhYDdwKnV9XTU/bniOQgzWM3H+DDz+r31EeDGdGIJMkpwJuATwN7ClgOrO7aq4FLuvbFwJqq2lVV\nk8AW4OxBjy1pvLSc2nwCeB/QP6pYWFU7uvYOYGHXPhnY2rfeVnojE0lzwEBBkuQiYGdVPcAzo5F9\nVO+cabrzpvG5yiupyaAT0l4LLE/yJuD5wO8kuQXYkWRRVW1PchKws1t/G7Ckb/tTur79uKevPdE9\nJM2sye4xMwYakVTV+6tqSVWdClwO3F1VbwNuB67oVrsCuK1r3w5cnmR+klOB04AN+9/7+X2PiUHK\nk/ScJtj3tdZmpqbI7zlNuQFYm+RKenF3KUBVbUyyFtgI7AauqnGawCKpSXOQVNW9wL1d+xfABQdY\n73rg+tbjSRo/3msjqZlBIqmZQSKpmUEiqZlBIqmZQSKpmUEiqZlBIqmZQSKpmZ8iP0s9zVGs49kf\nNHch6/gBr2A7i0ZQlY5UBsks9TRH8e+85ln9H+RDPM7JBomGyiCZYz7EB3kZD/N8fsNZ3D/tut/i\nvCFVpbnOIJmDHuZlALyBu6ddzyDRTPFiq6RmBomkZgaJpGYGiaRmBomkZgaJpGa+/TuHHezXd+75\nYvJD2Ubq54hEUjODRFIzg0RSM4NEUjODRFIzg0RSM4NEUjPnkYiP8d697ffysUNaXwKDRMCTHL+3\nfTxPjrASzVae2khqZpBIamaQSGrmNRLt42Bu2uu/ya9lP5o7HJFIamaQSGpmkEhqNnCQJFmQ5AtJ\nHkmyMck5SU5Msj7J5iTrkizoW39lkkeTbEry7O+alDRrtYxIbgS+VlVnAK8ANgErgPVVdTpwV/ec\nJEuBy4ClwDLgpiSOhqQ5YqAXc5IXAudV1WcAqmp3Vf0SWA6s7lZbDVzStS8G1lTVrqqaBLYAZ7cU\nLml8DDoqOBX4aZJ/SPK9JH+f5AXAwqra0a2zA1jYtU8GtvZtvxVYPOCxJY2ZQYNkHvBq4KaqejXw\na7rTmD2qqoCaZh/TLZM0iww6IW0rsLWq9nzd/ReAlcD2JIuqanuSk4Cd3fJtwJK+7U/p+vbjnr72\nRPeQNLMmu8fMSG/gMMCGyb8Cf1ZVm5NcBxzXLfp5VX0kyQpgQVWt6C623krvushi4E7gJTXl4EkK\nZ0TOCfub/fotzuNu3jCCavTcVlFVGXTrliny7wQ+m2Q+8B/A24GjgbVJrqQXd5cCVNXGJGuBjcBu\n4KqpISJp9hp4RHI4OCKZ+/Y3UrmRq3mCBftZW8PTNiJxLoekZgaJpGYGiaRmBomkZgaJpGYGiaRm\nBomkZgaJpGYGiaRmfoq8huq5Pl1+GXdwDvcd1mNo5jkikdTMIJHUzCCR1MwgkdTMIJHUzCCR1Mwg\nkdTMIJHUzCCR1MwgkdTMIJHUzCCR1MwgkdTMIJHUzCCR1MwgkdTMIJHUzCCR1MwgkdTMIJHUzCCR\n1MwgkdTMIJHUzCCR1MwgkdTMIJHUbOAgSfLuJA8neSjJrUmel+TEJOuTbE6yLsmCvvVXJnk0yaYk\nF85M+ZLGwUBBkmQx8E7gzKp6OXA0cDmwAlhfVacDd3XPSbIUuAxYCiwDbkriaEiaI1pezPOA45LM\nA44DHgeWA6u75auBS7r2xcCaqtpVVZPAFuDshmNLGiMDBUlVbQM+BvwXvQB5oqrWAwurake32g5g\nYdc+Gdjat4utwOKBKpY0duYNslGSF9EbfUwAvwT+Oclb+9epqkpS0+zmAMvu6WtPdA9JM2uye8yM\ngYIEuAD4cVX9HCDJvwCvAbYnWVRV25OcBOzs1t8GLOnb/pSubz/OH7AkSQdvgn3/k763aW+DBsl/\nAucmORb4Db1g2QD8GrgC+Ej387Zu/duBW5N8nN4pzWnd+tI+7mAZd7CsaR/Xsmra5au4tmn/eraB\ngqSqNiT5AvA9YHf38++AE4C1Sa6kN266tFt/Y5K1wMZu/auqarrTHkmzyKAjEqrqOuC6Kd2/oDc6\n2d/61wPXD3o8SePLuRySmhkkkpoZJJKaGSSSmhkkkpoZJJKaGSSSmhkkkpoZJJKaGSSSmhkkkpoZ\nJJKaGSSSmhkkkpoZJJKaGSSSmhkkkpoZJJKaGSSSmhkkkpoZJJKaGSSSmg38dRTSuPo+fzDqEo44\nBonmnNu4ZNQlHHEMEh1xDvSVnn6V5+C8RiKpmUEiqZlBIqmZQSKpmUEiqZlBIqmZQSKpmUEiqZlB\nIqmZQSKp2bRBkuQzSXYkeaiv78Qk65NsTrIuyYK+ZSuTPJpkU5IL+/rPTPJQt+zGw/OrSBqV5xqR\n/AOwbErfCmB9VZ0O3NU9J8lS4DJgabfNTUnSbfMp4MqqOg04LcnUfc5ik6Mu4BBNjrqAAUyOuoAB\nTI66gKGaNkiq6lvAf0/pXg6s7tqrYe+tlhcDa6pqV1VNAluAc5KcBJxQVRu69f6pb5s5YHLUBRyi\nyVEXMIDJURcwgMlRFzBUg1wjWVhVO7r2DmBh1z4Z2Nq33lZg8X76t3X9kuaIpoutVVVAzVAtkmap\nQT6PZEeSRVW1vTtt2dn1bwOW9K13Cr2RyLau3d+/7cC73/9nRYy3e0ddwCGabfXCTNZ84L+wmf7b\nm43/zoMZJEhuB64APtL9vK2v/9YkH6d36nIasKGqKsn/JDkH2AC8Dfjb/e24qrK/fknjbdogSbIG\neD3w4iSPAX8D3ACsTXIlvStKlwJU1cYka4GNwG7gqu7UB+Aq4B+BY4GvVdUdM/+rSBqVPPNal6TB\njM3M1iTLuolsjya5ZtT1wMxNyBtyzUuSfDPJD5M8nORd41x3kucnuS/Jg129141zvVNqPzrJA0m+\nPO41J5lM8oOu3g0zXm9VjfwBHE1v3skEcAzwIHDGGNR1HvAq4KG+vo8Cf9W1rwFu6NpLu7qP6X6P\nLcBRI6h5EfDKrn088CPgjHGuGziu+zkP+DZwzjjX21f3e4DPAreP+98G8GPgxCl9M1bvuIxIzga2\nVNVkVe0CPkdvgttIVfuEvLOHUWe/qtpeVQ927SeBR+hd/B7buqvqf7vmfHp/vMUY1wuQ5BTgTcCn\ngT1vEox1zTxT5x4zVu+4BMli4LG+53sms42jQ52QNzJJJuiNqO5jjOtOclSSB7u61lVvFvTY1tv5\nBPA+4Om+vnGuuYA7k3wnyZ93fTNW77h8r82svOJbVZVkutpH9nslOR74InB1Vf3qmduexq/uqnoa\neGWSFwJfSvKyKcvHqt4kFwE7q+qBJOfvt6Axqxl4XVX9JMnvAuuTbNqnmMZ6x2VEMnUy2xL2TcRx\nsiPJIoCDmJA3zcS7wyfJMfRC5Jaq2jPPZ+zrrqpfAt8E3sh41/taYHmSHwNrgDckuYUxrrmqftL9\n/CnwJXqnKjNW77gEyXfo3RU8kWQ+vbuIbx9xTQeyZ0IePHtC3uVJ5ic5lW5C3rCL6+64vhnYWFWf\n7Fs0lnUnefGedwuSHAv8Eb3rOmNZL0BVvb+qllTVqcDlwN1V9bZxrTnJcUlO6NovAC4EHprRekdx\ntfsAV5X/mN47DFuAlaOup6tpDfA48BS9azhvB04E7gQ2A+uABX3rv7+rfxPwxhHV/If0ztsfBB7o\nHsvGtW7g5cD3gO93f9x/3fWPZb37qf/1PPOuzVjWDJza/T08CDy85/U1k/U6IU1Ss3E5tZE0ixkk\nkpoZJJKaGSSSmhkkkpoZJJKaGSSSmhkkkpr9P32HcP7UQN2XAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10a5c5b00>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "df_fl_a['k'] = 1\n",
    "df_oge_a_fl['k'] = 1\n",
    "df_block = df_fl_a.sort_values(by='nzip').iloc[0:1000].merge(df_oge_a_fl.sort_values(by='nzip').iloc[0:500], \n",
    "                                                             on='k')[['nzip_x', 'nzip_y']]\n",
    "\n",
    "z = (df_block.nzip_x == df_block.nzip_y).values\n",
    "z.shape = (1000, 500)\n",
    "_=plt.imshow(z, aspect=0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Sometimes you can simply use a single property in the data (or part of it) to block. For example, the red section above shows the pairs we would retain if we only used records where the 5-digit zip matches.  However as we've seen there are some wrong zips so this would miss matches.  You could also use the first 3 digits of the zip to throw a wider net."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Using Multiple Keys\n",
    "- Blocking with a single property might defeat the purpose of matching\n",
    "- Using multiple properties (eg, Zip, Street Num) increases the probability of including candidates\n",
    "- This is similar to Locality Sensitive Hashing (LSH)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The idea here is that you sort by the first property and consider pairs where the property matches as we did with zip above, then you sort by the second property and compare any pairs not already considered.  Each new property reduces the probability of dropping a record pair with a match.  In practice you might need to do this in phases."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### N-Gram Based Blocks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'reeeett  ccaaffe', 'sttrreeeett  cca', 'trreeeett  ccaaf'}"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def window(fseq, window_size=8):\n",
    "    for i in range(len(fseq) - window_size + 1):\n",
    "        yield fseq[i:i+window_size]\n",
    "\n",
    "#Find bigrams and then join them into 8-bigram keys\n",
    "n1 = ngrams('mainstreet cafe', 2)\n",
    "n2 = ngrams('the main street cafe inc', 2)\n",
    "# Find the keys shared by these two names\n",
    "set([''.join(x) for x in window(n1)]) & set([''.join(x) for x in window(n2)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<img src=\"ngram_index.jpg\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "This approach works well with messier name data.  For example in this case we have two names that are in fact a match, but they don't have a high similarity score or the same soundex code.  What we do is form bigrams from the names, and then make blocking keys by joining a subset of the bigrams into strings.  You can see here that these two names share 3 blocking keys, so they would end up in the same index lists."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Further Reading\n",
    "\n",
    "- Canopy Clustering\n",
    "- Locality Sensitive Hashing (LSH)\n",
    "  - Minhash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Canopy clustering is a sort of \"pre-clustering\" used to reduce the number of comparisons needed in more complex clustering algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Classifying Matches\n",
    "We can now generate the comparison vectors:\n",
    "\n",
    "$$\n",
    "[s_{1}(a_{1}, b_{1}), ..., s_{n}(a_{n}, b_{n})]\n",
    "$$\n",
    "\n",
    "Options:\n",
    " - Simple Scoring\n",
    " - Rules\n",
    " - Probabilistic matching\n",
    " - Supervised learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "So now we know how to compare fields, and we know how to limit the record pairs that we want to compare, so we can create the comparison vectors.  There are several ways to use that information to classify each record pair as a match or non-match.  The first is just calculating a simple score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Simple Scoring\n",
    "\n",
    "$$\n",
    "Score(r_{a}, r_{b}) = \\sum_{i=1}^{n} w_{i} s_{i}(a_{i}, b_{i})\n",
    "$$\n",
    "\n",
    "$$ \n",
    "Score(r_{a}, r_{b}) > T \\implies r \\in M\n",
    "$$\n",
    "\n",
    "- Sum the individual scores and set a threshold T1.  Anything > T1 is a match\n",
    "- For bonus points, choose a second threshold T2 so that anything < T2 is a non-match\n",
    "- Any sum between T1 and T2 needs review.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The easiest way to classify matches is just to form a score from the components of the comparison vector usually by summing them, possibly with unequal weights.  In fact, this is simple enough that it can usually be calculated directly from the record pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAEACAYAAAC9Gb03AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGCxJREFUeJzt3X2MHPddx/H3x3WskqTJxWp1sZPAmcppah56bRUHUUBL\ncNJQtU4ECFxE8RUUEFEfJATEKVQGIYwV/qDiSUKlbU6CGEJbgoviYAe8hQpq9yGbNr0ax7SGusWX\npoHSECRi8uWPncsM67vbnduH38zc5yWtMrP7292vv7f53uzn5vYUEZiZWXNtSF2AmZmNlwe9mVnD\nedCbmTWcB72ZWcN50JuZNZwHvZlZw/Ud9JJeIenRwuXrkt4habOkY5JOSzoqaapwn3skPSHplKRb\nx/tPMDOz1ajMefSSNgBfBnYCbweeioh7Jd0NXBUR+yTtAO4HbgSuAR4Bro+I50devZmZ9VU2utkF\nnImILwG7gfns+nngjmz7duBQRDwXEWeBM3S/MZiZWQJlB/0e4FC2PR0Ri9n2IjCdbW8FzhXuc47u\nkb2ZmSUw8KCXtAl4E/DnvbdFN/9ZLQPy5yyYmSWyscTaHwQ+FRFfzfYXJV0dEeclbQGezK7/MnBd\n4X7XZte9QJIHv5nZGkSEyt6nTHTzZvLYBuAwsDfb3gs8WLh+j6RNkrYB24GTyxTrSwT79+9PXkNV\nLu6Fe+FerH5Zq4GO6CVdRvcHsXcWrj4IPCDpp4GzwI9mA3xB0gPAAnABuCuGqbDhzp49m7qEynAv\ncu5Fzr0Y3kCDPiL+C3hpz3VP0x3+y60/ABwYujozMxuafzM2sbm5udQlVIZ7kXMvcu7F8Er9wtTI\nnlRymmNmVpIkYsw/jLUxaLfbqUuoDPci517k3IvhedCbmTWcoxszs5pwdGNmZsvyoE/M+WPOvci5\nFzn3Ynge9GZmDeeM3sysJpzRm5nZsjzoE3P+mHMvcu5Fzr0YXpmPKTYzWxek0ulIpTmjNzPr0R30\nVZxRzujNzGwZHvSJOX/MuRc59yLnXgzPg97MrOGc0ZuZ9XBGb2ZmteJBn5jzx5x7kXMvcu7F8Dzo\nzcwazhm9mVkPZ/RmZlYrHvSJOX/MuRc59yLnXgxvoEEvaUrSByV9XtKCpJskbZZ0TNJpSUclTRXW\n3yPpCUmnJN06vvLNzKyfgTJ6SfPARyPi/ZI2ApcBvww8FRH3SrobuCoi9knaAdwP3AhcAzwCXB8R\nzxcezxm9mVXWusvoJV0JfG9EvB8gIi5ExNeB3cB8tmweuCPbvh04FBHPRcRZ4Ayws2xhZmY2GoNE\nN9uAr0r6gKRPS3qvpMuA6YhYzNYsAtPZ9lbgXOH+5+ge2dsynD/m3Iuce5FzL4Y3yOfRbwReA7wt\nIj4h6T3AvuKCiAhJq73Puei2ubk5ZmZmAJiammJ2dpZWqwXkX1jvr6/9JVWpJ+V+p9OpVD0p9zud\nTpLnzy3ttxLst4H7sv0Z1qpvRi/pauAfI2Jbtv89wD3AtwLfHxHnJW0BjkfEDZL2AUTEwWz9w8D+\niDhReExn9GZWWesuo4+I88CXJF2fXbUL+BzwEWBvdt1e4MFs+zCwR9ImSduA7cDJsoWZmdloDHoe\n/duBP5H0GPCdwG8AB4FbJJ0Gbs72iYgF4AFgATgC3OXD95Vd/DZx/XIvcu5Fzr0Y3kB/MzYiHqN7\numSvXSusPwAcGKIuMzMbEX/WjZlZj3WX0ZuZWb150Cfm/DHnXuTci5x7MTwPejOzhnNGb2bWwxm9\nmZnVigd9Ys4fc+5Fzr3IuRfD86A3M2s4Z/RmZj2c0ZuZWa140Cfm/DHnXuTci5x7MTwPejOzhnNG\nb2bWwxm9mZnVigd9Ys4fc+5Fzr3IuRfD86A3M2s4Z/RmZj2c0ZuZWa140Cfm/DHnXuTci5x7MTwP\nejOzhnNGb2bWwxm9mZnVigd9Ys4fc+5Fzr3IuRfDG2jQSzor6TOSHpV0Mrtus6Rjkk5LOippqrD+\nHklPSDol6dZxFW9mZv0NlNFL+iLw2oh4unDdvcBTEXGvpLuBqyJin6QdwP3AjcA1wCPA9RHxfOG+\nzujNrLLWc0bf++C7gflsex64I9u+HTgUEc9FxFngDLCzbGFmZjYagw76AB6R9ElJd2bXTUfEYra9\nCExn21uBc4X7nqN7ZG/LcP6Ycy9y7kXOvRjexgHXvS4i/k3Sy4Bjkk4Vb4yIkLTa+5yLbpubm2Nm\nZgaAqakpZmdnabVaQP6F9f762l9SlXpS7nc6nUrVk3K/0+kkef7c0n4rwX4buC/bn2GtSp9HL2k/\n8AxwJ9CKiPOStgDHI+IGSfsAIuJgtv5hYH9EnCg8hjN6M6usdZfRS7pU0kuy7cuAW4HPAoeBvdmy\nvcCD2fZhYI+kTZK2AduBk2ULMzOz0Rgko58G/l5SBzgB/FVEHAUOArdIOg3cnO0TEQvAA8ACcAS4\ny4fvK7v4beL65V7k3IucezG8vhl9RHwRmF3m+qeBXSvc5wBwYOjqzMxsaP6sGzOzHusuozczs3rz\noE/M+WPOvci5Fzn3Ynge9GZmDeeM3syshzN6MzOrFQ/6xJw/5tyLnHuRcy+G50FvZtZwzujNzHo4\nozczs1rxoE/M+WPOvci5Fzn3Ynge9GZmDeeM3syshzN6MzOrFQ/6xJw/5tyLnHuRcy+G50FvZtZw\nzujNzHo4ozczs1rxoE/M+WPOvci5Fzn3Ynge9GZmDeeM3syshzN6MzOrFQ/6xJw/5tyLnHuRcy+G\nN9Cgl/QiSY9K+ki2v1nSMUmnJR2VNFVYe4+kJySdknTruAo3M7PBDJTRS/p54LXASyJit6R7gaci\n4l5JdwNXRcQ+STuA+4EbgWuAR4DrI+L5nsdzRm9mlbXuMnpJ1wJvAP4IWHqC3cB8tj0P3JFt3w4c\niojnIuIscAbYWbYoMzMbnUGim98GfhEoHpVPR8Ritr0ITGfbW4FzhXXn6B7Z2wqcP+bci5x7kXMv\nhrdxtRslvRF4MiIeldRabk1EhKTV3uMse9vc3BwzMzMATE1NMTs7S6vVfYqlL6z319f+kqrUk3K/\n0+lUqp6U+51OJ8nz55b2Wwn228B92f4Ma7VqRi/pAPAW4ALwYuAK4MN0M/hWRJyXtAU4HhE3SNoH\nEBEHs/s/DOyPiBM9j+uM3swqa11l9BHxroi4LiK2AXuAv42ItwCHgb3Zsr3Ag9n2YWCPpE2StgHb\ngZNlizIzs9Epex790re4g8Atkk4DN2f7RMQC8ACwABwB7vKh++oufpu4frkXufXSC0mVvDTNqhl9\nUUR8FPhotv00sGuFdQeAAyOpzszWgX7Hgm3y/HpSmjXs/Vk3ZpZMlbPwqtblz7oxM7OLeNAntl6y\n2EG4Fzn3oqiduoDa86A3M2s4Z/Rmlowz+rKc0ZuZ2TI86BNzFptzL3LuRVE7dQG150FvZtZwzujN\nLBln9GU5ozczs2V40CfmLDbnXuTci6J26gJqz4PezKzhnNGbWTLO6MtyRm9mZsvwoE/MWWzOvci5\nF0Xt1AXUnge9mVnDOaM3s2Sc0ZfljN7MzJbhQZ+Ys9ice5FzL4raqQuoPQ96M7OGc0ZvZsk4oy/L\nGb2ZmS3Dgz4xZ7E59yLnXhS1UxdQe6sOekkvlnRCUkfS45J+Nbt+s6Rjkk5LOippqnCfeyQ9IemU\npFvHXL+ZmfXRN6OXdGlEPCtpI/Ax4J3ADwNPRcS9ku4GroqIfZJ2APcDNwLXAI8A10fE8z2P6Yze\nzJzRlzamjD4ins02NwGX0P3X7wbms+vngTuy7duBQxHxXEScBc4AO8sWZWZmo9N30EvaIKkDLAJH\nI+IkMB0Ri9mSRWA6294KnCvc/RzdI3tbgbPYnHuRcy+K2qkLqL2N/RZkscuspCuBv5D07T23h6TV\n3uMse9vc3BwzMzMATE1NMTs7S6vVAvIXuffX1/6SqtSTcr/T6VSqnnHu54N8pf1On9vHtU+f2yex\n3wbuy/ZnWKtS59FLejfwLHAn0IqI85K2AMcj4gZJ+wAi4mC2/mFgf0Sc6HkcZ/Rm5oy+tDFk9JJe\nunRGjaRvAm4BPg8cBvZmy/YCD2bbh4E9kjZJ2gZsB06WLcrMzEanX0a/BfhbSY/RHdhHI+Ih4CBw\ni6TTwM3ZPhGxADwALABHgLt86L46Z7E59yLnXhS1UxdQe6tm9BHxWeA1y1z/NLBrhfscAA6MpDoz\nMxuaP+vGzJJxRl+WP+vGzMyW4UGfmLPYnHuRcy+K2qkLqD0PejOzhnNGb2bJOKMvyxm9mZktw4M+\nMWexOfci514UtVMXUHse9GZmDeeM3syScUZfljN6MzNbhgd9Ys5ic+5Fzr0oaqcuoPY86M3MGs4Z\nvdk60M3Cq6qKs6BZGX3fvzBlZk1RzcFl4+foJjFnsTn3IudeFLVTF1B7HvRmZg3njN5sHfD56mVV\nty6fR29mZhfxoE/MWWzOvci5F0Xt1AXUnge9mVnDOaM3Wwec0ZdV3bp8Hn3FlP0lFX/zM7NxcHQz\nZtHncpxqHjek4Fw6514UtVMXUHt9B72k6yQdl/Q5SY9Lekd2/WZJxySdlnRU0lThPvdIekLSKUm3\njvMfYGZmq+ub0Uu6Grg6IjqSLgc+BdwBvBV4KiLulXQ3cFVE7JO0A7gfuBG4BngEuD4ini885rrI\n6CUNfLQuHN3Y+DijL6u6dY3lPPqIOB8RnWz7GeDzdAf4bmA+WzZPd/gD3A4ciojnIuIscAbYWbYw\nMzMbjVIZvaQZ4NXACWA6IhazmxaB6Wx7K3CucLdzdL8x2DLaqQuoEOfSOfeiqJ26gNob+KybLLb5\nEPDOiPhG8YySiAhJq73Puei2ubk5ZmZmAJiammJ2dpZWqwXkL/K67y9Z2mv12X9hfUXqT9avitST\ncr/T6Yytv4O/Iquy30n0/PS5fRL7beC+bH+GtRroPHpJlwB/BRyJiPdk150CWhFxXtIW4HhE3CBp\nH0BEHMzWPQzsj4gThcdzRt+7Fmf0Nj7O6Muqbl1jyejVfYW8D1hYGvKZw8DebHsv8GDh+j2SNkna\nBmwHTpYtzMzMRmOQjP51wE8A3y/p0exyG3AQuEXSaeDmbJ+IWAAeABaAI8Bd6+LwfY3aqQuoEOfS\nOfeiqJ26gNrrm9FHxMdY+RvCrhXucwA4MERdZmY2Iv6smzFyRm9V4Yy+rOrW5c+6qbkyn43jbwpm\nNih/1k1i7cJ2v8/FWbo0lXPpnHtR1E5dQO150JuZNZwz+jEqndGXWbsO+mej44y+rOrW5b8Za2Zm\nF/GgT6yduoAKcS6dcy+K2qkLqD0PejOzhnNGP0bO6K0qnNGXVd26nNGbmdlFPOgTa6cuoEKcS+fc\ni6J26gJqz78ZW8LrXvta/uULXxhs8QZ/DzWzanBGX8LLp6eZf/LJgT7+/2cuv5wjzzzjjN4qwRl9\nWdWty591MwFbgGsHWHepj+jNrCI8jRJrpy6gQpxL59yLonbqAmrPg97MrOGc0Zfw8ulpjj75JC8f\nYO2PXHEFH/rP/3RGb5XgjL6s6tbljH4d8WfXm9mgHN0k1l7j/Zr42fXOpXPuRVE7dQG150FvZtZw\nzuhLqFRGX2ZtDXtto+WMvqzq1uXPujEzs4t40CfWTl1AhTiXzrkXRe3UBdRe30Ev6f2SFiV9tnDd\nZknHJJ2WdFTSVOG2eyQ9IemUpFvHVbgNTlKpi5k1yyBH9B8Abuu5bh9wLCKuB/4m20fSDuDHgB3Z\nff5Akt81rKI1gecY9Ayd1Ilkq9VKXEF1uBdFrdQF1F7fIRwRfw/8e8/Vu4H5bHseuCPbvh04FBHP\nRcRZ4AywczSlmpnZWqz1aHs6Ihaz7UVgOtveCpwrrDsHXLPG51gX2qkLqBDn0jn3oqiduoDaG/o3\nYyMiJK32rn/Z2+bm5piZmQFgamqK2dnZF96uLr3Iq7a/ZGmvtcr+Vy9cKLW+zOMvXdfv8da8n7q/\nFfl6p9zvdDpj6+8YXjFj3u8ken763D6J/TZwX7Y/w1oNdB69pBngIxHxHdn+KaAVEeclbQGOR8QN\nkvYBRMTBbN3DwP6IONHzeD6PvsdYz6MfcO0L62v4tbHV+Tz6sqpb1yTPoz8M7M229wIPFq7fI2mT\npG3AduDkGp/DzMxGYJDTKw8B/wC8QtKXJL0VOAjcIuk0cHO2T0QsAA8AC8AR4K5aHrpPUDt1ARXi\nXDrnXhS1UxdQe30z+oh48wo37Vph/QHgwDBFmZnZ6PizbkpwRm915Yy+rOrW5c+6MTOzi3jQJ9ZO\nXUCFOJfOuRdF7dQF1J4HvZlZwzmjL8EZvdWVM/qyqluXM3ozM7uIB31i7dQFVIhz6Zx7UdROXUDt\nedCbmTWcM/oSnNFbXTmjL6u6dTmjNzOzi3jQJ9ZOXUCFOJfOuRdF7dQF1N7Qn0dvzVPm78Y65vn/\n/Dd3rYo86BNrpS5gGWXy/1Fqzt9JreI3vzp/A2qlLqD2HN2YmTWcB31i7dQFDEnSwJd+nEsXtVMX\nUCHt1AXUnqMbG0qqmMfMBucj+sRaqQuokOZk9KPQSl1AhbRSF1B7HvRmZg3nQZ9YO3UBFVImoy/z\ns4FJXkbYjRE+Vt21UxdQe87obWJGf36+T2M0G4QHfWKt1AVMkH9wW0YrdQEV0kpdQO05ujEza7ix\nDHpJt0k6JekJSXeP4zmaop26gApppy6gUtqpCxiCSlzWst7KGvmgl/Qi4PeA24AdwJslvXLUz9MU\nndQFVMjaelFmSNRpWKylG6McqMP1LQa8DLL2t6nmT2PqZBwZ/U7gTEScBZD0p8DtwOfH8Fy19x+p\nC6iQYi9K/eC2xHPUZcyv9ZVR+m8PlFibqnv+f2R444hurgG+VNg/l11nNmL1GdtNUOYo3aplHEf0\nzf1ab9jAnZdfzmUb+n9//OT//M9AD3l2yJKa5Gxhe7xn6Iz7G8SoHv/XRvQ49XY2dQENMI5B/2Xg\nusL+dXSP6v+fun5u9xdKrh/kXzlfYm2Zx13L2tR1jLsXTVenr3WZtfMvbE3yq92cV9bI/2aspI3A\nPwE/AHwFOAm8OSKc0ZuZJTDyI/qIuCDpbcBfAy8C3uchb2aWzsiP6M3MrFrG9puxkq6TdFzS5yQ9\nLukdy6xpSfq6pEezy6+Mq56UBulFtq6V9eFxSe0JlzkRA74ufqHwmvispAuSplLUO04D9uJKSR+R\n1MnWzCUodewG7MVVkv5C0mOSTkj6thS1jpukF2f/vqWv+a+usO53sl9KfUzSq1d90IgYywW4GpjN\nti+nm9u/smdNCzg8rhqqchmwF1PA54Brs/2Xpq47VS961r8ReCR13QlfF+8CfnPpNQF8DdiYuvZE\nvfgt4N3Z9iua+rrI/n2XZv/dCHwcuKnn9jcAD2XbNwEfX+3xxnZEHxHnI6KTbT9D9xemti6ztDk/\n2l7BgL34ceBDEXEuW/fUZKucjBKviyU/DhyaRG2TNmAvngeuyLavAL4WERcmV+VkDNiLVwLHszX/\nBMxIetlEC52QiHg229wEXEL3dVC0m+xkpIg4AUxJml7p8SbyoWaSZoBXAyd6bgrgu7O3Hg9J2jGJ\nelJapRfbgc3Z29dPSnrLpGubtFV6sXT7pcDrgQ9Nrqo0VunF7wE7JH0FeAx452Qrm7xVevEY8EPZ\nmp3AtwDXTrK2SZG0QVIHWASORsQnepYs94upK/Zi7INe0uXAB4F3Zt+piz4NXBcRrwJ+F3hw3PWk\n1KcXlwCvofuW7PXAuyVtn3CJE9OnF0veBHwsIhr9W/B9enEb8OmI2ArMAr8v6SWTrnFS+vTiIN0j\n10eBtwGPAv874RInIiKej4hZusP7phV+HtGbhqx4Zs1YB72kS+gejf1xRFw0xCPiG0tvUSLiCHCJ\npM3jrCmVfr2g+935aET8d0R8Dfg74FWTrHFSBujFkj00NLZZMkAv5oAPA0TEPwNfpJtPN86A8+Kn\nIuLVEfGTwMso/zuMtRIRX6cbV93Wc1PvL6Zem123rHGedSPgfcBCRLxnhTXT2bqlt2KKiKfHVVMq\ng/QC+EvgeyS9KIssbgIWJlXjpAzYCyRdCXwf3b400oC9+FdgV7Z+mu6Qb9xwG3BeXClpU7Z9J/DR\nVd4N1pakly6dZSbpm4BbuPhDIQ8DP5mt+S7gPyJicaXHHOdfmHod8BPAZ7K3WtA9g+CbASLiD4Ef\nAX5O0gXgWbpHcE3UtxcRcUrSw8Bn6P7g5b0R0bhBz2CvC4A7gL+OiP+efIkTM0gvfh24T9Jn6L5V\n/6UmHgwxWC920O1FAI8DP52i0AnYAsyr+5HvG4A/i4iHJP0svDAvHpL0BklngP8C3rraA/oXpszM\nGs5/StDMrOE86M3MGs6D3sys4TzozcwazoPezKzhPOjNzBrOg97MrOE86M3MGu7/AOZwjv4DsbFF\nAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x108f55fd0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def match_score(r_a, r_b):\n",
    "    return (jellyfish.jaro_winkler(r_a[0], r_b[0]) + \n",
    "            (1.0 if r_a[1] == r_b[1] else 0) + \n",
    "            (1.0 if r_a[2] == r_b[2] else 0))\n",
    "\n",
    "_=df_m[['nname_x','snum_x', 'nzip', \n",
    "        'nname_y', 'snum_y', 'nzip']].apply(\n",
    "       lambda r: match_score(r[0:3], r[3:]), axis=1).hist(bins=20)\n",
    "_=df_u[['nname_x','snum_x', 'nzip', \n",
    "        'nname_y', 'snum_y', 'nzip']].apply(\n",
    "       lambda r: match_score(r[0:3], r[3:]), axis=1).hist(bins=20,color='r')\n",
    "_=plt.xlim([2.5,3.0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "This approach actually works reasonably well on our example even using a super-simple score.  This graph shows the scores of the true matches (in blue) and the scores of the top 1000 non-matches.  They are fairly well separated except for some outliers down at the bottom that were manually set.  However, there's a range between 2.7 and 2.9 where there are numerous matches and non-matches."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Rules\n",
    "$$\n",
    "(JaroWinkler(Name_{A}, Name_{B}) > 0.9) \\land (Zip_{A} = Zip_{B}) \\implies M\n",
    "$$\n",
    "\n",
    "$$\n",
    "(JaroWinkler(Name_{A}, Name_{B}) < 0.7) \\lor (Zip_{A} \\neq Zip_{B}) \\implies U\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Using rules is another common approach. Basically we're just applying various conditions to the elements of the comparison vector.  The rules are usually just implemented with standard Python conditionals, but you could also use something like PyRules for complicated situations.  Rules give us an added level of complexity over scoring.  For example, we could have one rule that says we have a match if the Jaro-Winkler score is 0.8 and the zip and street number match, and another rule that says we have a match if the names are identical and the street number matches.  The biggest problem with rules is that they are harder to learn, so you often need experience with the data or the problem domain before you can get them right."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Probabilistic Matching (Fellegi-Sunter)\n",
    "Suppose our comparison vector is:\n",
    "\n",
    "$$\n",
    "  \\gamma(r_{A}, r_{B}) = [JaroWinkler(Name_{A}, Name_{B}) > 0.9, (Zip_{A} = Zip_{B}), Levenshtein(StreetNum_{A}, StreetNum_{B}) < 2]\n",
    "$$\n",
    "\n",
    "We'll call this type of comparison vector an _agreement pattern_.  The are 8 separate patterns (2^3) in this case\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>name</th>\n",
       "      <th>zip</th>\n",
       "      <th>street num</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>match</td>\n",
       "      <td>match</td>\n",
       "      <td>match</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>match</td>\n",
       "      <td>match</td>\n",
       "      <td>unmatch</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>match</td>\n",
       "      <td>unmatch</td>\n",
       "      <td>match</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>match</td>\n",
       "      <td>unmatch</td>\n",
       "      <td>unmatch</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>unmatch</td>\n",
       "      <td>match</td>\n",
       "      <td>match</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>unmatch</td>\n",
       "      <td>match</td>\n",
       "      <td>unmatch</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>unmatch</td>\n",
       "      <td>unmatch</td>\n",
       "      <td>match</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>unmatch</td>\n",
       "      <td>unmatch</td>\n",
       "      <td>unmatch</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      name      zip street num\n",
       "0    match    match      match\n",
       "1    match    match    unmatch\n",
       "2    match  unmatch      match\n",
       "3    match  unmatch    unmatch\n",
       "4  unmatch    match      match\n",
       "5  unmatch    match    unmatch\n",
       "6  unmatch  unmatch      match\n",
       "7  unmatch  unmatch    unmatch"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import itertools\n",
    "pd.DataFrame(data=list(itertools.product(['match','unmatch'], repeat=3)),\n",
    "             columns=['name', 'zip', 'street num'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Probabilistic matching methods, which are mostly identified with the method of Fellegi and Sunter, were the first attempts to find an optimal approach to matching.  The starting point is a comparison vector that is a set of predicates, or an _agreement pattern_, here called gamma.  Fellegi and Sunter treat gamma as a random variable, so that each pattern has a certain probability of occuring in the set of pairs, and of course the probability of all the patterns sums to one.  Certain patterns will obviously be much more associated with matches, and others will be much more associated with non-matches."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The method then defines the following two conditonal probabilities:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "m(\\gamma) = P[\\gamma(r_{A}, r_{B})| (r_{A}, r_{B}) \\in M] \\\\\n",
    "\\end{align}\n",
    "$$\n",
    "and\n",
    "$$\n",
    "\\begin{align}\n",
    "u(\\gamma) = P[\\gamma(r_{A}, r_{B})| (r_{A}, r_{B}) \\in U] \\\\\n",
    "\\end{align}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "To capture this idea, they first define two conditional probabilities: m, the probability that a certain pattern will occur in the set of matches, and u the probability that a pattern will appear in the set of non-matches."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The Fellegi-Sunter method results in a _linkage rule_:\n",
    "\n",
    "$$\n",
    "\t\\begin{array}{ll}\n",
    "\t\t\\frac{m}{u} > T_{\\mu}  & \\mbox{match}  \\\\\n",
    "        T_{\\mu} < \\frac{m}{u} < T_{\\lambda}  & \\mbox{potential match}  \\\\\n",
    "\t\t\\frac{m}{u} < T_{\\lambda}  & \\mbox{non-match}  \\\\\n",
    "\t\\end{array}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Using ratios of m and u, the method defines a _linkage rule_, which uses two thresholds to define matches, possible matches, and non-matches.  The insight of Fellegi and Sunter was that if you sort the m/u ratios from largest to smallest you can define a linkage rule that will give you the best possible match set given the data and the level of error that you're willing to accept.  Obviously, you want to mimimize the \"potential match\" range so that the process is as automatic as possible, but you have to do so while not introducing false positives or missing true matches."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Simplifications\n",
    "\n",
    "- Conditional Independence\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "& P(\\textit{name matches}, \\textit{zip matches}, \\textit{street matches}|M) = \\\\\n",
    "& P(\\textit{name matches}|M) P(\\textit{zip matches}|M) P(\\textit{street matches}|M) \\\\\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "- So\n",
    "\n",
    "$$\n",
    "m(\\textit{name matches}) = \\frac{P(\\textit{name matches}|M)}{P(\\textit{name matches}|U)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Two simplifications are usually introduced for the method.  The first is to assume conditional independence between the properties, so that the probabilities of each pattern conditional on M can be written as the product of the probabilities for the individual attributes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Convert m/u ratios to weights:\n",
    "\n",
    "$$\n",
    "w_{i} = \n",
    "\\left\\{\n",
    "\t\\begin{array}{ll}\n",
    "\t\tlog_{2}(\\frac{m_{i}}{u_{i}})  & \\mbox{if agreement on field i}  \\\\\n",
    "\t\tlog_{2}(\\frac{1-m_{i}}{1-u_{i}}) & \\mbox{if otherwise}\n",
    "\t\\end{array}\n",
    "\\right.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Once conditional independence is assumed you can also convert the ratios to a log form and then score each record with a sum rather than a product."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### But Wait!\n",
    "\n",
    "- By definition we don't know which records are in M and which are in U\n",
    "- In some cases __m/u__ can be estimated, and then progressively refined.\n",
    "- Most general method is __Expectation-Maximization__ algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "Obviously the conditional probabilities we defined above require knowing which records are in M and which are in U, but we could only know that for sure by actually determining the matches.  Fortunately there is a well-known way to estimate the parameters given our data that's based on the idea of maximum likelihood estimation, which is a way to find the values of distribution parameters that are the most likely given the data that we have.  The data that we do have is the comparison vectors and agreement patterns.  The data that we don't have is whether each record is in M or in U.  That's where the Expectation-Maximization algorithm comes in."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Assume distribution of patterns is a mixture of distributions, with parameters:\n",
    "\n",
    "$$\n",
    "\\Phi = ((m_{1}\\dots m_{k}), (u_{1}\\dots u_{k}), p)\n",
    "$$\n",
    "\n",
    "- Also assume there is a _latent variable_ __g__ that determines whether a record pair is in __M__ or __U__.\n",
    "- Then simply find parameters that maximizes this simple (;-)) likelihood function for the data we have:\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "\n",
    "$$\n",
    "f(g,\\gamma; \\Phi) = \\prod_{j=1}({pP(\\gamma_{j}|r_{j} \\in M))^g((1-p)P(\\gamma_{j}|r_{j} \\in U)})^{(1-g)}\n",
    "$$\n",
    "\n",
    "where the product is over the _j_ records in the data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The E-M algorithm is a sort of unsupervised classification or clustering.  We start by assuming that the overall distribution of our data is a _mixture_ of two distributions, given by the m and u values, and an additional parameter p that describes the probability that a record is a match.  This is also sometimes called the _mixing parameter_.  This is the same method used in Scikit-learn's Gaussian Mixture Models, except here the distributions we're mixing are not gaussian.\n",
    "\n",
    "The next detail of the E-M approach is the assumption of a latent variable, g, that says whether or not the record is in the match set or not.  Of course we don't know this, which is why it is hidden or latent.  The hairy-looking function above is the _likelihood function_ for our data including the latent variable.  We can't easily maximize this directly, so the E-M algorithm takes an iterative approach.\n",
    "\n",
    "The E-M algorithm starts with initial estimates of the m, u, and p parameters; along with the agreement patterns.  It first calculates the expected value of g for each record.  Then it uses those values to calculate new values for m, u, and p.  This is repeated until the parameters don't change, within some threshold."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "outputs": [],
   "source": [
    "import operator\n",
    "import numpy as np\n",
    "from functools import reduce\n",
    "\n",
    "mh = np.array([ 0.08910887,  0.98090761,  0.88638131])\n",
    "uh = np.array([ 0.00019569,  0.00198455,  0.0003152 ])\n",
    "\n",
    "def mp(gamma, mh, uh):\n",
    "    return reduce(operator.mul, (mh[i] ** g * (1 - mh[i]) ** (1 - g) for i,g in enumerate(gamma)))\n",
    "\n",
    "def up(gamma, mh, uh):\n",
    "    return reduce(operator.mul, (uh[i] ** g * (1 - uh[i]) ** (1 - g) for i,g in enumerate(gamma)))\n",
    "\n",
    "def log_score(gamma, mh, uh):\n",
    "    return sum([np.log2(mh[i]/uh[i]) if g==1 else np.log2((1-mh[i])/(1-uh[i])) for i,g in enumerate(gamma)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table border=\"1\" class=\"dataframe potential\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>name</th>\n",
       "      <th>zip</th>\n",
       "      <th>street num</th>\n",
       "      <th>m</th>\n",
       "      <th>u</th>\n",
       "      <th>mu</th>\n",
       "      <th>w</th>\n",
       "      <th>cu</th>\n",
       "      <th>cm</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0.077476</td>\n",
       "      <td>1.224100e-10</td>\n",
       "      <td>6.329257e+08</td>\n",
       "      <td>29.237461</td>\n",
       "      <td>1.224100e-10</td>\n",
       "      <td>0.077476</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0.791982</td>\n",
       "      <td>6.254078e-07</td>\n",
       "      <td>1.266345e+06</td>\n",
       "      <td>20.272239</td>\n",
       "      <td>6.255302e-07</td>\n",
       "      <td>0.869458</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0.009931</td>\n",
       "      <td>3.882342e-07</td>\n",
       "      <td>2.558027e+04</td>\n",
       "      <td>14.642744</td>\n",
       "      <td>1.013764e-06</td>\n",
       "      <td>0.879389</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0.001508</td>\n",
       "      <td>6.155908e-08</td>\n",
       "      <td>2.449682e+04</td>\n",
       "      <td>14.580307</td>\n",
       "      <td>1.075323e-06</td>\n",
       "      <td>0.880897</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0.101518</td>\n",
       "      <td>1.983536e-03</td>\n",
       "      <td>5.118046e+01</td>\n",
       "      <td>5.677521</td>\n",
       "      <td>1.984612e-03</td>\n",
       "      <td>0.982416</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0.015415</td>\n",
       "      <td>3.145129e-04</td>\n",
       "      <td>4.901273e+01</td>\n",
       "      <td>5.615085</td>\n",
       "      <td>2.299124e-03</td>\n",
       "      <td>0.997831</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0.000193</td>\n",
       "      <td>1.952401e-04</td>\n",
       "      <td>9.900612e-01</td>\n",
       "      <td>-0.014410</td>\n",
       "      <td>2.494365e-03</td>\n",
       "      <td>0.998024</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0.001976</td>\n",
       "      <td>9.975056e-01</td>\n",
       "      <td>1.980894e-03</td>\n",
       "      <td>-8.979633</td>\n",
       "      <td>1.000000e+00</td>\n",
       "      <td>1.000000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_scores = pd.DataFrame(data=list(itertools.product([1,0], repeat=3)),\n",
    "             columns=['name', 'zip', 'street num'])\n",
    "df_scores['m'] = df_scores[['name', 'zip', 'street num']].apply(lambda p: mp(p,mh,uh), axis=1)\n",
    "df_scores['u'] = df_scores[['name', 'zip', 'street num']].apply(lambda p: up(p,mh,uh), axis=1)\n",
    "df_scores['mu'] = df_scores.m/df_scores.u\n",
    "df_scores['w'] = df_scores[['name', 'zip', 'street num']].apply(lambda p: log_score(p,mh,uh), axis=1)\n",
    "df_scores.sort_values(by='mu', ascending=False, inplace=True)\n",
    "df_scores['cu'] = df_scores.u.cumsum()\n",
    "df_scores['cm'] = df_scores.m.cumsum()\n",
    "HTML(df_scores.to_html(classes='potential'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "The data above shows m and u data calculated for our test set, using only name, zip, and street number for comparison.  These are sorted by m/u ratio.  This doesn't give us great results.  Only the first ratio is really safe in terms of automatically declaring a match.  The last 4 are also pretty safe in terms of determining a non-match.  However the three patterns show in yellow probably need some review.  It might not seem like it at first-- note that for the second pattern the u value is only about 1 in a million, but also recall that we're thinking in terms of 900 million pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "$('.potential tbody tr').filter(':eq(1)')\n",
       "                                             .css('background-color', '#ffff99');\n",
       "              $('.potential tbody tr').filter(':eq(2)')\n",
       "                                             .css('background-color', '#ffff99');\n",
       "              $('.potential tbody tr').filter(':eq(3)')\n",
       "                                             .css('background-color', '#ffff99');\n",
       "              $('.potential tbody tr').filter(':eq(4)')\n",
       "                                             .css('background-color', '#ffff99');\n",
       "                   "
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Javascript('''$('.potential tbody tr').filter(':eq(1)')\n",
    "                                             .css('background-color', '#ffff99');\n",
    "              $('.potential tbody tr').filter(':eq(2)')\n",
    "                                             .css('background-color', '#ffff99');\n",
    "              $('.potential tbody tr').filter(':eq(3)')\n",
    "                                             .css('background-color', '#ffff99');\n",
    "              $('.potential tbody tr').filter(':eq(4)')\n",
    "                                             .css('background-color', '#ffff99');\n",
    "                   ''')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Supervised Learning\n",
    "- Requires training data where matches/non-matches are already known\n",
    "- Always imbalanced since there are many more non-matches than matches\n",
    "- Harder to apply in production situations\n",
    "- Comparison vector is feature vector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "If you have some data that already has matches defined, that can be used to train the standard classifiers in scikit-learn.  This might seem unlikely, but it's not unusual to use one of the techniques above in conjunction with a team of reviewers to determine the likely matches.  \n",
    "\n",
    "In this case our comparison vector will correspond to a feature vector.  Note that the classes will always be unbalanced, that is we'll always have way more non-matches than matches.  Balancing classes can be even trickier here than it usually is.  If you sample from the non-matched set, it's too easy.  If you use non-matches that higher matching scores, the classifier will focus too much on 1 property."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from sklearn.cross_validation import KFold\n",
    "from sklearn.ensemble import RandomForestClassifier\n",
    "\n",
    "df_train = pd.concat([\n",
    "        df_m[['nname_x', 'nname_y', 'snum_x', 'snum_y','cty_nm', 'location_city', 'match']],\n",
    "        df_u[['nname_x', 'nname_y', 'snum_x', 'snum_y','cty_nm', 'location_city', 'match']]\n",
    "    ])\n",
    "\n",
    "#Make some new features\n",
    "df_train['jw_dist'] = df_train[['nname_x', 'nname_y']].apply(\n",
    "                            lambda s: jellyfish.jaro_winkler(str(s[0]), str(s[1])),\n",
    "                            axis=1)\n",
    "df_train['snum_dist'] = df_train[['snum_x', 'snum_y']].apply(\n",
    "                            lambda s: levenshtein_distance(str(s[0]), str(s[1])),\n",
    "                            axis=1)\n",
    "df_train['city_sim'] = df_train[['cty_nm', 'location_city']].apply(\n",
    "                            lambda c: jaccard( ngrams(c[0].lower(),2),\n",
    "                                               ngrams(c[1].lower(),2)),\n",
    "                                               axis=1)\n",
    "df_train['nzip_x'] = 1\n",
    "df_train['nzip_y'] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.937368642287\n"
     ]
    }
   ],
   "source": [
    "# Do a 5-fold cross-validation\n",
    "y = df_train.match.values\n",
    "X = df_train[['jw_dist', 'snum_dist', 'city_sim']].as_matrix()\n",
    "\n",
    "kf = KFold(len(y),n_folds=5,shuffle=True)\n",
    "y_pred = y.copy()\n",
    "\n",
    "clf = RandomForestClassifier()\n",
    "\n",
    "# Iterate through folds\n",
    "for train_index, test_index in kf:\n",
    "    X_train, X_test = X[train_index], X[test_index]\n",
    "    y_train = y[train_index]\n",
    "\n",
    "    clf.fit(X_train,y_train)\n",
    "    y_pred[test_index] = clf.predict(X_test)\n",
    "\n",
    "print(np.mean(y == y_pred))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "As an example, here's a case where i've built a balanced data set by choosing the best non-matches, then i do a 5-fold cross-validation using a Random Forest Classifier.  The predicted value is correct here about 94% of the time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/mikemull/anaconda/envs/matching/lib/python3.4/site-packages/matplotlib/collections.py:590: FutureWarning: elementwise comparison failed; returning scalar instead, but in the future will perform elementwise comparison\n",
      "  if self._edgecolors == str('face'):\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXYAAAEACAYAAACnJV25AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X10XPV95/H3V0+2HNmIsRMjh2dB9nRzmiC2Tcgxu4hG\nYznZrlvDnn1IaOUkTdg9SU2w2DgbQ3FS6bDJrl2WkywhDwVv2yXtgTg1FDSYFm0WTuLWCcYYnCZO\nuklYAhsgDzjIix199497ZY1mRvOk353RXH1e59xz7tz56TdfjTTf+5vv/d17zd0REZH0aGt2ACIi\nEpYSu4hIyiixi4ikjBK7iEjKKLGLiKSMEruISMpUTOxmttzMDpjZITM7YmY7S7R5t5k9YWaHzewx\nM3tTItGKiEhFHZUauPsJM7vS3V8xsw7gUTN70N0P5DX7HvDP3P1nZrYR+BxwWUIxi4hIGRUTO4C7\nvxKvdgGdwHTB81/Le3gAODtIdCIiUrOqauxm1mZmh4DngYfc/e/KNH8f8ECI4EREpHbVjtingUvM\n7Axgr5m90d2fKmxnZlcC7wXWhw1TRESqVVVinxHX0B8BNgJzEnt8wPTzwEZ3/0nhz5qZLkojIlIH\nd7da2lczK2aNmfXG691AFjha0OZc4MvANe5+rExwLbvcfPPNTY9hKcau+Ju/KP7mLvWoZsTeB+wx\ns3aiHcGfu/sDZnZtnKzvAP4AOBO43cwATrr7W+qKSEREFqSa6Y5PApeW2H5H3vrvAb8XNjQREamH\nzjyt0uDgYLNDqFsrxw6Kv9kUf+uxems4Nb+QmTfqtURE0sLM8NAHT0VEpLUosYuIpIwSu4hIyiix\ni4ikjBK7iEjKKLGLiKSMEruISMoosYuIpIwSu4hIyiixi4ikjBK7iEjKKLGLiKSMEruISMoosYuI\npIwSu4hIyiixi4ikjBK7iEjKKLGLiKSMEruISMoosYuIpIwSu4hIypRN7Ga23MwOmNkhMztiZjvn\naXebmX3HzJ4ws4FEIhURkaqUTezufgK40t0vAS4BNprZW/PbmNk7gYvc/WLgA8DtSQUr0lJyOdiw\nIVpyuWZHU7tWj99s7rKEdFRq4O6vxKtdQCcwXdBkE7AnbnvAzHrNbK27Px80UpFWksvB5s0wNRU9\nfvRR2LsXhoebG1e1Wj3+UoncDNwbH0sTVKyxm1mbmR0Cngcecve/K2jyeuCHeY+fAc4OF6JIC9q1\nazYpQrS+a1fz4qlVq8e/xFUzYp8GLjGzM4C9ZvZGd3+qoFnh7rHkbnHnzp2n1wcHBxkcHKwpWBGR\ntJucnGRycnJBfZjX8NXEzG4CXnH3XXnbPgtMuvuX4sffAq4oLMWYmdfyWiItrbCU0d3dWqWMVo9/\nvpp6C+YgM8PdazpIUGlWzBoz643Xu4EscLSg2T7gd+M2lwE/VX1dlrzh4SgRZrPR0kpJEVo//iWu\n7IjdzH6V6MBoO9FO4M/dfczMrgVw9zvidp8GNgK/AN7j7t8s0ZdG7CLSGEt8xF5TKWYhlNhlycnl\nZg84jo5qxNtISuxK7CLB5XKwaRO8+mr0uKsL9u1Tcm8UJXYldpHgLr0UHn987raBAfhmUZVSkrDE\nE7uuFSOShO9/v7ptIglQYhdJwnnnVbdNJAFK7CJJuOWWqK4+o6sr2ibSAKqxiyRFs2KaZ4nX2JXY\nRSR9lnhiVylGRCRllNilbrlcjg0brmbDhqvJteL1upOW9PXMW73/LVugszNatmwJ3v04sJpeVtPL\nePDeFzl3b8gSvZQ00sTEhGezV3k2e5VPTEwE77ur67UOdznc5V1drw3+GkWvOTbm2cx5ns2c5xNj\nYwvvL8H3xycm3Lu63KMv/9H6PK8xMTTkWVZ5llU+MTRUff/d3bP9d3fP239NMWez0TI2Vjn+/Pa1\nvvbIyGzfM8vISH1xj4y4d3RES9zHGDisOv3/Cat8rEVzUJw7a8u3tf5AvYsSe2lJJZeJiQnv7l57\n+h+7u3tt0P4HBq6I+575XN7lAwNXBOu/0MTYmHfnfVC7WbWg5J70++MDA8WJa2CgOI6hoeLfa57k\nPtbX5xl6PUOvj3V2FvefzdYfb+GOwqx8/AvdsZTqPzoOVzo88Cw9nqXHJ/JzSakdxNCQZ+h1uNqh\nP16u9gy9tb8vi4ASe4tJMrlks1c5rHd4Xbys92z2qiB9u7tnMv0Oow5XxcuoZzL9wfovlM2cV7Qj\nyWbOq7+/7FXF/QV8fzyTKU44mUxxHKeTel4crCpqN9bXV3oEGiqxZ7PF8ZaLv1T7Wl5/vtcoYQKK\nd34zbdvbS/aznGVF79dyltX//jRRPYldNfYm2rXrc0xNXUN05eN9TE1dw65dn6upj/nq3Ee+8Rjw\nJPCpeHky3hbGmWcuI7q97bPxcnu8LZz83+2FV6cq/0Cl/rZsYUPnajZ0ruaFI4cCRFjGshLvRalt\nVdr9oyngNmAkXm5jN72zDbq7oymVSTrzzKDd5YAN9LCBHspV8HfRw1Te7z7FbeyiB8bH4Ze/LPkz\nRjfwfmY+W/D+eNsSUeueoN4FjdiLDAysj0cVl8XLKh8YWF/1z5cb8beTKRoJtlM8YqxXf9+FDmvy\nRkRrvL/vwnnjrLXcVPi7dXWs9i5W1F2KmRgZyRv1jbrR68YZ8beOhZd2ivT0FI8ke3qK46qyFBOV\nFub+PTP01l/jLgqksaWYsqPwAll6SnyrKfH+5i09vKbo/7OH1yzsPWoSVIppLbUkx1LKlRM6SiT2\njoCJPdPx2qL+Mx2vLWpXb7kp+t3mlnoG+i+p++BptmPm/ZhwmI2njVU+wPIoqZSogdetylKMe3UH\nT0uWYvr6wsXrPvdgaKljBIWllgUcPJ03WZcKa76dwHxLV5f301P0/9M/T/+LnRJ7i6k2Oc6nXGIf\nGRoqSgQj1c64qMLAynVFrz2wcl1NMZbtf2C9wwqHs+NlRU3fZoriOJ3Y8+MZiXesZ/pImcRbl7Gx\n4oSzwG8Ecw6ehk7qhSYm5o7azRb+rSBPtkTinS+xu5c4eFpqxzmzc56Y8AGWFw2aBlgeLP5GUmJv\nMdUmx/lUGg0P9fc7ZBwyPtQf9sDmxNiYd+XtOLrmKWXUm9j7Mmc5dMYfzjUOnd6XOav+eE+XYi6L\n4xkp3vGFTOzuUSLPZKIlZJmnEYaGipNmwIHBgqcjVthxDtDjhbNiBjRiV2JvhGqTY9k+5qlfh+i7\nmvgrlUbqLcVESX3uBx86FxbvyIgPtL3G21gV7yzmfvA72qv/tlTV6yU5Tz5pNcxaqUctpZh5ldlx\n9pf4/+lf4P9Psyixt6DQJ93MiL4NFIxYavg2EFI9CQ7OLPrgw5lh4hkbc1gel3pmDlyvcLMVQfp3\nj3doeSdwdTfgBK6gWiGxl7GyxMHmlZrHrsTe6pbbiqIRy/KAics9uZ2Su3tbicTeFiCxT4yMxPX2\nnrhMNVuD7Wg7I0DkkWyJE7iyoU/gWsiZn5UknNhrmRUz+0PV/746QUmJPZWSnu44MTbmHSzzmYOb\nHSwLmtxHBgaKdkwjC5y1MnfK42VF70/IWUPRCVVzE8tCTqgqksQlBfIlnNgdig+Iluu/xt93qEQN\nf6hFc5ASu5y2sn1NUeJa2b4mWP/9y8/wwoOb/cvDjXjdwx/8nZ0Z4z53dkz0/vR3rQ4QdWSkxPTE\nkZAzWRZ65mcltSbeOvqvacdR4+8777z/FlRPYu9o0HlQ0mDbr/nn3Lhna96WrWy/ZnOw/r974hWg\nG/gvp/uPtoWRy+V47NnjwG4AHnt2O7lcjuFgN6v4AHDN6UcdbOUz57w2UN9w3/FOZs8Undn2B8H6\n53vfq25bnXJmbPaV8Rmf8Chb2Wsvo1uFtIhyWR84B3gEeAo4Amwt0eYM4D7gUNxmyzx9NWTvJrNG\nhoa8g4x3kAk6h93d45H03HnIhCxlJHAtl7mlmLu8ixU+kD8iDTjija6lUzBiDHktnZUri0ewK1cG\n677aa9jUra2tOP62tvnb11iKWepXd6w0Yj8JXO/uh8ysB/iGme1396N5bT4IHHH3f2Fma4C/N7M/\ndfdTwfY+UrNcLsdfPPYkp+IR7188tp1/G3DEa3YK9z3MjthvwGxx/8mH77qLvcCuP9sGPs2on2B4\nejp6MvC1VrZtew833jj3G9O2bR8J1j+dndVtq1f3cii8PE/38nD9X3ABfPe7xdvmMzwMe/dWfavB\nHQD8nN18GIBt/DzetkTUshcAvgK8vWDbR4HPxOsXAt+e52cT3avJXKVOyQ959cK+vjcUjej6+t4Q\nrP/EL6sbvUhys0rcfWxszDOZfs9k+n0s9AlKCZzZmi/0ZZKLX2Aiun76TOwdHa118LeBSPLgKXA+\n8H2gp2B7D1G55lngZeAd8/x8A96C1pPUSSwDfRd60QXGargOTSWJX/bWW/wEn6QlnRh9dmpotiPj\nE/XeBKPsC7TudM1GqiexV3Uz67gMMwmMuftXCp77l8Db3H3UzPqB/cCb3f3lgnZ+8803n348ODjI\n4OBgld8r0imXy7Fp0+/w6qv/GYCurv/Avn1/EqRcclF7D9+dzj+4eQP9bVMc++XxBfcNUey/+ZtX\nc+pUdCnXjo6fcP/99wY8uCllbdgA+/fP3ZbNwkMPhek/l4PNm2Eqrsd0d0elkFb5+7bwzawnJyeZ\nnJw8/fjjH/84XuPNrKsZqXcSXTr5w/M8fz+wPu/xXwO/VqJdonu1VpTkXYgyJeaxZwIe3BwbGys+\nOBX6kgUasc8v6emOSffvrhF7lQhdigEM+O/AH5Vp89+Am+P1tcAzRNMjlNgrSHLmxECJGvhAwBp4\n0rM+GlJjb2VJn6CUdGJv9ROsGiiJxH45ME00lfHxeHkHcC1wbdymLx7RHya6Zc+75umrUe9Dy4gu\nTVtwadEFXJo238TEhHe1n3m67672M4MmxqQTeyNq+C0vyRFvDTfjrksDTrBayom97HRHd38Uyt8+\nz91/BDpvoR633HITmzb9G1599bMAdHWd4pZbbgrS9/DwMPv+6u7Tt9obHb07aP078el8QDROuDpe\nLzMVbqkaHm6dmrc0Vq17gnoXWnRvmbREp8QlLMnYG1HDT1zC0ykTpVLMokGS0x0XuiixF0u6jtzK\nBx+TnoefuKQTV9IacfA0yRuRKLErsTdLknXkVj/4mOTxh4ZoRGJMUtI7pqT77+wsfv87l86NNsrW\nz6UR7gMuipf7gvW6a9fnmJr6JNFFqEaYmvrk6Xp7a+ggin1fvIzE22RGbnycDavPZ8Pq88mNj4ft\nfHgYduyATCZaduwIW8/ftWt2jjxE6zOXCwjh5MnqtqWUEnsF4+PjrF59EatXX8R44A/PunUric7n\nuile9sfbBE4BdwKb4uXOeFuLGB0l19XFBnrYQA+5rq6g16LJjY+z+cZPsf+lj7P/pY+z+cZPhU3u\nuRx84hPw0kvR8olPRNukNdQ6xK93oQVLMdEBvLm3Twt5AC+aMji3jhxqymAjSjFJ1vD7+y8pKlP1\n918S9DWSPLiZ9K3xoht5FJTxQt7IY2CguJSxwBudzDEyUtx/yMsWqMauxD6f7u41Pvf2aRnv7g53\ns4qenr6iOnJPT7ibMSSZeJPecWRWnluUuDIrzw3Wf9I13qTn4WdXrivuP+Q9bRO+LLD39BT33xPu\nnqc+NFTcf+BLVzdKPYldRcsypqZOAbeSf7OEqakPB+t/7dq1HD/+4Tn9r117a7D+h4eHE7t2y9wa\n/kyJ9HPBXu88P8FLbMvbso3zPOC/63w13haZFz76um4efXnr6SvrdrOV0deFu1EI0WCs8rZ6nThR\n3bZ67d8fXTvn4Yejx0NDxdfWSTHV2MtqA64DVsfLdYR8yy688MKqti1FV69sB04An42XE/G2QF54\nobptdRod/QDd3duBPcAeuru3Mzr6gWD9D194IXv5OVk+RJYPsZefMxzyf+fiixkHVtPLanoZj7cF\ns2pVddsWYv/+2fH6EkrqgEox5QBO3g2bo/Vwv8fExIS3tS3zmfuGtrUtC1rOSPIOSkmXYhIvNSRd\nQ/aEzyNI+JT/saEhLzpBLOT/UNKlnhRBpZjQlgOvAjP38jwZbwvj7rvvZnp6GTOX1p2e3srdd4c5\n9X9LNsueh/8W4ntW7nl4K2Sz3BVo5DI8PMzevXvyLlmwJ2zZJ+k7BK1ZU922BUiyFJa03Y8covCe\nrbsfuSHcXYiS/vsudbXuCepdaMkRe1uJEXuZ+zLWqKPjdUWzYjo6Xhem7xKX7e0IeNnepDXkDj46\nM3ReSV/2Oek7QKUJGrGH1gksA8bix1vLtK3d9PT/I6rBzt4MY3p66ZxEUc7wjh3R/Ul33wzA6LaP\nMLwj4F0ra7yH5lKzrW8ZN/6o4CJvfa8J9wIzf8vdu+MX3Da7TRau1j1BvQstOWJfWTSihnB1wCTv\nGzpSokYaus4uTdSAU/7H2to8Q69n6PWxtrbW+kaTItQxYq/q1nghmJk36rVCMXsNUV39jHjLz4BO\n3H8RpP8NG65m//5NzNYx95DN7uOhh+4N0v+WbJY/e/ibALx76NJg9XVZJHK5ZL9xJN2/VMXM8Bpv\njafEXoZZF1E55k3xlsPASdxfDdJ/Lpdj8+aReD44dHdvZ+/ewAchRaSlKbEHZtZNNCumN97yU6AL\n96n5f6hG4+Pj7N59JxDdvGKH6owikkeJPTCzdqIR+8wZfT8mGrH/Mkj/GrGLSCVK7IFFI/YTQCbe\n8hKwPNiIPekau4i0vnoSu6Y7lnUCyD+NfeY095B0X08RCUvXiimrjWge+xviZRkh37IrrrgUuB14\nNl5uj7eJiNRPib2sFUSXE/h2vLwSbwvj3nsfJLpEwb+Ll+XxNhGR+qkUU9ZxokT+hvjx4XhbGMeO\n/QDYTf71OI4duylY/yKyNJUdsZvZOWb2iJk9ZWZHzKzkOfVmNmhmj8dtJhOJtCm6icovMyPqZfG2\nME6dKr7VW6ltIiK1qDRiPwlc7+6HzKwH+IaZ7Xf3ozMNzKwX+Aww7O7PmFnYS+Q1VSfwG8Afxo9/\ng+gepWG0twPckLflBtrbdYU7EVmYsond3Z8DnovXj5vZUWAdcDSv2buAe939mbhduLsVNN0UUSK/\nLX68Nd4WxsUXv4HHH/81YF+8ZYSLLz4YrH8RWZqqnsduZucD/xN4o7sfz9v+R0RD2zcCK4H/6u5/\nUuLnW3Ae+8wZpzNTHqMTk9x/GqT/XC7HO995FdPT0Tz5traXeOCBL+sEJRE5LbF57HEZ5h7guvyk\nHusELgXeTnSk8Wtm9nV3/05hPzt37jy9Pjg4yODgYC2xNkF00a/Zi4C9TFSdCuPgwYNMT3cwc1ng\n6emtHDx4UIldZAmbnJxkcnJyQX1UHLGbWSdwP/CguxfdadnMtgPd7r4zfvwFYMLd7ylo14Ij9i6i\ng6VzSzGhLgK2evVFvPTSTeSfeZrJ/CEvvngsSP8i0vrqGbFXmhVjwBeBp0sl9dhfApebWbuZrQDe\nCjxdSxCLVw+ztwcbidd7mhqRiEgllUox64FrgMNm9ni87WPAuQDufoe7f8vMJogmeU8Dn3f3lCT2\n6Sq31Wfbtvdw440Fd6nZ9pFg/YvI0qSLgJURHVroJv/WdVEpJtxJSrpsr4iUo6s7BmaWAd4L/EO8\n5QLgj3F/qXlBiciSosQeWHSIYRVzD57+nFb7PUSkdSmxJyBK7rPXY2/F30FEWpeux54AJXIRaTW6\nbK+ISMoosYuIpIwSu4hIyiixi4ikjBK7iEjKKLGLiKSMEruISMoosYuIpIwSu4hIyiixi4ikjBK7\niEjKKLGLiKSMEruISMoosYuIpIwSu4hIyiixi4ikjBK7iEjKKLGLiKSMEruISMqUTexmdo6ZPWJm\nT5nZETPbWqbtr5vZKTO7KnyYIiJSrUo3sz4JXO/uh8ysB/iGme1396P5jcysHfgkMAHUdDdtEREJ\nq+yI3d2fc/dD8fpx4CiwrkTT3wfuAX4cPEIREalJ1TV2MzsfGAAOFGx/PfBbwO3xJg8Um4iI1KFS\nKQaAuAxzD3BdPHLPdyvwUXd3MzPKlGJ27tx5en1wcJDBwcFa4xURSbXJyUkmJycX1Ie5lx9gm1kn\ncD/woLvfWuL57zGbzNcArwDvd/d9Be280muJiMhcZoa713Tssmxij0fge4AX3f36KgK4E7jP3b9c\n4jkldhGRGtWT2CuVYtYD1wCHzezxeNvHgHMB3P2OmqMUEZFEVSzFBHshjdhFRGpWz4hdZ56KiKSM\nEruISMoosYuIpIwSu4hIyiixi4ikjBK7iEjKKLGLiKSMEruISMoosYuIpIwSu4hIyiixi4ikjBK7\niEjKKLGLiKSMEruISMoosYuIpIwSu4hIyiixi4ikjBK7iEjKKLGLiKSMEruISMoosYuIpIwSu4hI\nyiixi4ikTMXEbmbnmNkjZvaUmR0xs60l2rzbzJ4ws8Nm9piZvSmZcEVEpBJz9/INzM4CznL3Q2bW\nA3wD+G13P5rX5m3A0+7+MzPbCOx098sK+vFKryUiInOZGe5utfxMR6UG7v4c8Fy8ftzMjgLrgKN5\nbb6W9yMHgLNrCUJERMKpqcZuZucDA0TJez7vAx6oPyQREVmIiiP2GXEZ5h7gOnc/Pk+bK4H3AutL\nPb9z587T64ODgwwODtYQqohI+k1OTjI5ObmgPirW2AHMrBO4H3jQ3W+dp82bgC8DG939WInnVWMX\nEalRPTX2ag6eGrAHeNHdr5+nzbnA3wDXuPvX52mjxC4iUqOkEvvlwFeBw8BM448B5wK4+x1m9gVg\nM/CD+PmT7v6Wgn6U2EVEapRIYg9FiV1EpHb1JHadeSoikjJK7CIiKaPELiKSMkrsIiIpo8QuIpIy\nSuwiIimjxC4ikjJK7CIiKaPELiKSMkrsIiIpo8QuIpIySuwiIimjxC4ikjJK7CIiKaPELiKSMkrs\nIiIpo8QuIpIySuwiIimjxC4ikjJK7CIiKaPELiKSMkrsIiIpo8QuIpIyZRO7mZ1jZo+Y2VNmdsTM\nts7T7jYz+46ZPWFmA8mEKiIi1ag0Yj8JXO/ubwQuAz5oZr+S38DM3glc5O4XAx8Abk8kUhGRWoyP\nw+rV0TI+3uxoGqqj3JPu/hzwXLx+3MyOAuuAo3nNNgF74jYHzKzXzNa6+/MJxSwiUt74ONx44+zj\nmfUdO5oTT4NVXWM3s/OBAeBAwVOvB36Y9/gZ4OyFBiYiUrfdu6vbllJlR+wzzKwHuAe4zt2Pl2pS\n8NhL9bNz587T64ODgwwODlYVpIjIUjE5Ocnk5OSC+jD3kjl4toFZJ3A/8KC731ri+c8Ck+7+pfjx\nt4ArCksxZuaVXktEJIjCUgzA2FhLlmLMDHcvHDyXVXbEbmYGfBF4ulRSj+0DPgR8ycwuA36q+rqI\nNNVMAp8pv2zb1pJJvV5lR+xmdjnwVeAws+WVjwHnArj7HXG7TwMbgV8A73H3b5boSyN2EZEa1TNi\nr1iKCUWJXUSkdvUkdp15KiKSMkrsIiIpo8QuIpIySuwiIimjxC4ikjJK7CIiKaPELiKSMkrsIiIp\no8QuIpIySuwiIimjxC4ikjJK7CIiKaPELiKSMkrsIpJOuRxs2BAtuVyzo2koXbZXRNInl4PNm2Fq\nKnrc3Q1798LwcHPjqoMu2ysiArBr12xSh2h9167mxdNgSuwiIimjxC4i6TM6GpVfZnR3R9uWCNXY\nRSSdcrnZ8svoaEvW10H3PBURSR0dPBURESV2EZG0qZjYzeyPzex5M3tynufPMLP7zOyQmR0xsy3B\noxQRkapVM2K/E9hY5vkPAkfc/RJgENhlZh0BYltUJicnmx1C3Vo5dlD8zab4W0/FxO7u/wv4SZkm\n08CqeH0V8KK7nwoQ26LSyv8crRw7KP5mU/ytJ8TI+tPAfWb2LLAS+FcB+hQRkTqFOHi6Efimu68D\nLgE+Y2YrA/QrIiJ1qGoeu5mdD9zn7r9a4rn7gVvc/bH48V8D2939YEE7TWIXEalDrfPYQ5RifgAM\nAY+Z2VrgHwHfW2hgIiJSn4ojdjO7G7gCWAM8D9wMdAK4+x1m1gfcBfQBRjR6/x8JxiwiImU07JIC\nIiLSGImdeWpmGTPbb2bfNrOHzKy3RJtzzOwRM3sqPrlpa1LxVMPMNprZt8zsO2a2fZ42t8XPP2Fm\nA42OsZxK8ZvZu+O4D5vZY2b2pmbEOZ9q3v+43a+b2Skzu6qR8VVS5f/PoJk9Hv+/TzY4xLKq+P9Z\ntCcjVjqRMm6zmD+7lU4Ere2z6+6JLMCngI/E69uB/1SizVnAJfF6D/D3wK8kFVOFeNuBY8D5RKWm\nQ4WxAO8EHojX3wp8vRmxLiD+twFnxOsbWy3+vHZ/A9wPXN3suGt8/3uBp4Cz48drmh13jfF/jKjU\nClFp9kWgo9mxx/H8U2AAeHKe5xftZ7fK+Gv67CZ5rZhNwJ54fQ/w24UN3P05dz8Urx8HjgLrEoyp\nnLcAx9z9f7v7SeBLwG8VtDn9O7n7AaA3PmC8GFSM392/5u4/ix8eAM5ucIzlVPP+A/w+cA/w40YG\nV4Vq4n8XcK+7PwPg7i80OMZyqol/0Z6M6JVPpFzMn92K8df62U0ysa919+fj9eeBsm9iPKVygCjo\nZng98MO8x8/E2yq1WSzJsZr4870PeCDRiGpTMX4zez1Rsrk93rSYDhBV8/5fDGTi8uNBM/udhkVX\nWTXxfxr4x/HJiE8A1zUothAW82e3VhU/uwua7mhm+4nKKYV25D9wdy83j93MeohGYdfFI/dmqDZJ\nFE7bXCzJpeo4zOxK4L3A+uTCqVk18d8KfDT+fzKK/xbNVE38ncClwNuBFcDXzOzr7v6dRCOrTjXx\nz5yMeKWZ9QP7zezN7v5ywrGFslg/u1Wr9rO7oMTu7tkyATxvZme5+3PxlMj/O0+7TuBe4E/d/SsL\niWeB/g9wTt7jc4j26uXanB1vWwyqiZ/4oMvngY3uXu6ra6NVE/8/Ab4U5XTWAO8ws5Puvq8xIZZV\nTfw/BF5w9ylgysy+CrwZWAyJvZr4twC3ALj7d83sH4jOWznI4reYP7tVqeWzm2QpZh8wEq+PAEVJ\nOx51fRG0liq+AAABKklEQVR42t1vTTCWahwELjaz882sC/jXRL9Dvn3A7wKY2WXAT/PKTc1WMX4z\nOxf4MnCNux9rQozlVIzf3S909wvc/QKib3j/fpEkdaju/+cvgcvNrN3MVhAdxHu6wXHOp5r4Z05G\npNzJiIvUYv7sVlTzZzfBo7wZ4GHg28BDQG+8fR3wV/H65UQHZA4Bj8fLxiYemX4H0cycY8B/jLdd\nC1yb1+bT8fNPAJc2K9Z64ge+QDSTYea9/ttmx1zr+5/X9k7gqmbHXMf/zw1EM2OeBLY2O+Ya/3/6\ngBxwOI7/Xc2OOS/2u4FngVeJvhm9t8U+u2Xjr/WzqxOURERSRrfGExFJGSV2EZGUUWIXEUkZJXYR\nkZRRYhcRSRkldhGRlFFiFxFJGSV2EZGU+f+zoeMmHTZHSAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x110b85b38>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "yy=df_train[['nname_x','snum_x', 'nzip_x', \n",
    "        'nname_y', 'snum_y', 'nzip_y']].apply(\n",
    "       lambda r: match_score(r[0:3], r[3:]), axis=1).values\n",
    "xx =          clf.predict_proba(X)\n",
    "pp = xx[:,1]\n",
    "_=plt.scatter(pp[df_train.match.values==1],yy[df_train.match.values==1], color='r')\n",
    "_=plt.scatter(pp[df_train.match.values==0],yy[df_train.match.values==0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  9.89445520e-01,   3.43909157e-04,   1.02105711e-02])"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "clf.feature_importances_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Further Reading\n",
    "\n",
    "- Frequency based match weights\n",
    "- Active learning (dedupe)\n",
    "- FEBRL\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}