Patient matching with Unsupervised Learning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exploring patient matching with unsupervised learning : Expectation-Maximisation and K-means\n",
    "This notebook introduces key concepts of patient matching while demonstrating those concepts using python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***********************************************"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook follows  step by step the record linkage process , providing minimum exaplanation and assuming  knowledge of the process. For more detailed information, please consult the reference section\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Record linkage process (deduplication)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import display\n",
    "import warnings\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import recordlinkage \n",
    "from recordlinkage.index import Block\n",
    "from recordlinkage.preprocessing import phonetic\n",
    "warnings.filterwarnings('ignore')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Get version information"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pandas version: 0.25.0 \n",
      "\n",
      "Python Record Linkage version: 0.14 \n",
      "\n",
      "Numpy version: 1.16.3 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Get Version information\n",
    "print(\"Pandas version: {0}\".format(pd.__version__),'\\n')\n",
    "print(\"Python Record Linkage version: {0}\".format(recordlinkage._version.get_versions()['version']),'\\n')\n",
    "print(\"Numpy version: {0}\".format(np.__version__),'\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# file to deduplicate\n",
    "IMPORT_FILE_TO_DEDUPLICATE = './data/dataset_febrl3.csv'\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook we use  synthetic dataset from The Python Record Linkage Toolkit (PRLT). The PRLT contains several open public synthetic datasets. The package is distributed with a  four synthetic datasets. For this project we will use The Freely Extensible Biomedical Record Linkage (Febrl) dataset 3 . Dataset 3 (FEBRL3) contains 5000 records (2000 originals and 3000 duplicates).\n",
    "\n",
    "For more info : [Synthetic datasets](./https://recordlinkage.readthedocs.io/en/latest/ref-datasets.html \"Title\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of records : 5000\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>given_name</th>\n",
       "      <th>surname</th>\n",
       "      <th>address_1</th>\n",
       "      <th>address_2</th>\n",
       "      <th>suburb</th>\n",
       "      <th>postcode</th>\n",
       "      <th>state</th>\n",
       "      <th>date_of_birth</th>\n",
       "      <th>soc_sec_id</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rec_id</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>rec-1496-org</th>\n",
       "      <td>mitchell</td>\n",
       "      <td>green</td>\n",
       "      <td>wallaby place</td>\n",
       "      <td>delmar</td>\n",
       "      <td>cleveland</td>\n",
       "      <td>2119</td>\n",
       "      <td>sa</td>\n",
       "      <td>19560409.0</td>\n",
       "      <td>1804974</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rec-552-dup-3</th>\n",
       "      <td>harley</td>\n",
       "      <td>mccarthy</td>\n",
       "      <td>pridhamstreet</td>\n",
       "      <td>milton</td>\n",
       "      <td>marsden</td>\n",
       "      <td>3165</td>\n",
       "      <td>nsw</td>\n",
       "      <td>19080419.0</td>\n",
       "      <td>6089216</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rec-988-dup-1</th>\n",
       "      <td>madeline</td>\n",
       "      <td>mason</td>\n",
       "      <td>hoseason street</td>\n",
       "      <td>lakefront retrmnt vlge</td>\n",
       "      <td>granville</td>\n",
       "      <td>4881</td>\n",
       "      <td>nsw</td>\n",
       "      <td>19081128.0</td>\n",
       "      <td>2185997</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rec-1716-dup-1</th>\n",
       "      <td>isabelle</td>\n",
       "      <td>NaN</td>\n",
       "      <td>gundulu place</td>\n",
       "      <td>currin ga</td>\n",
       "      <td>utakarra</td>\n",
       "      <td>2193</td>\n",
       "      <td>wa</td>\n",
       "      <td>19921119.0</td>\n",
       "      <td>4314184</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rec-1213-org</th>\n",
       "      <td>taylor</td>\n",
       "      <td>hathaway</td>\n",
       "      <td>yuranigh court</td>\n",
       "      <td>brentwood vlge</td>\n",
       "      <td>NaN</td>\n",
       "      <td>4220</td>\n",
       "      <td>nsw</td>\n",
       "      <td>19991207.0</td>\n",
       "      <td>9144092</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "               given_name   surname        address_1               address_2  \\\n",
       "rec_id                                                                         \n",
       "rec-1496-org     mitchell     green    wallaby place                  delmar   \n",
       "rec-552-dup-3      harley  mccarthy    pridhamstreet                  milton   \n",
       "rec-988-dup-1    madeline     mason  hoseason street  lakefront retrmnt vlge   \n",
       "rec-1716-dup-1   isabelle       NaN    gundulu place               currin ga   \n",
       "rec-1213-org       taylor  hathaway   yuranigh court          brentwood vlge   \n",
       "\n",
       "                   suburb  postcode state  date_of_birth  soc_sec_id  \n",
       "rec_id                                                                \n",
       "rec-1496-org    cleveland      2119    sa     19560409.0     1804974  \n",
       "rec-552-dup-3     marsden      3165   nsw     19080419.0     6089216  \n",
       "rec-988-dup-1   granville      4881   nsw     19081128.0     2185997  \n",
       "rec-1716-dup-1   utakarra      2193    wa     19921119.0     4314184  \n",
       "rec-1213-org          NaN      4220   nsw     19991207.0     9144092  "
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## add columns\n",
    "df_a = pd.read_csv(IMPORT_FILE_TO_DEDUPLICATE)\n",
    "df_a = df_a.set_index('rec_id')\n",
    "print('Number of records :', len(df_a))\n",
    "df_a.head()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pre-processing and standardization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the first step of the Record linkage process. The main task of **data cleaning and standardization** is the conversion of the raw input data into well defined, consistent forms, as well as the resolution of inconsistencies in the way information is represented and encoded. (source:)\n",
    "\n",
    "We have split the date of birth in 3 columns for more easy comparison, also we have calculated the metaphone of the given name and surname respectively.\n",
    "\n",
    "**Metaphone** is a phonetic encoding algorithm used to encode the way words an syllable are pronounces to help **reduce minor typographical error**.The output of a phonetic algorithm is an intentionally approximate phonetic representation of the word. With application still limited to English words Metaphone is an improvement on the Soundex algorihtm .\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# convert date of birth as string\n",
    "df_a['date_of_birth'] = pd.to_datetime(df_a['date_of_birth'],format='%Y%m%d', errors='coerce')\n",
    "df_a['YearB'] = df_a['date_of_birth'].dt.year.astype('Int64') \n",
    "df_a['MonthB'] = df_a['date_of_birth'].dt.month.astype('Int64') \n",
    "df_a['DayB'] = df_a['date_of_birth'].dt.day.astype('Int64') \n",
    "\n",
    "df_a['metaphone_given_name'] = phonetic(df_a['given_name'], method='metaphone')\n",
    "df_a['metaphone_surname'] = phonetic(df_a['surname'], method='metaphone')\n",
    "#df_a.sort_values(['given_name'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Blocking and Indexing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The second step of the process called ***blocking or indexing** try to reduce the number of records we need to compare. The idea is instead of comparing all records of the dataset between themselves we want to compare only the records that are most likely to be matched. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As example you can decide to compare only patiend with the same : first name, last name and date of birth. This combination of fields is called a **  blocking key**. Using  a blocking key provide a reduce set of record pairs. In this notebook we use multiple blocking keys and consider the  ** union  ** of all the results set of candidate record pairs to evaluate for matching in the next steps."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Please note the use of the **metaphone** algorithm here instead of the exact value.This takes into account typrographic errors in the names and provide a wider range of candidiate record pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of record pairs : 12833\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>rec_id_1</th>\n",
       "      <th>rec_id_2</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>rec-0-org</td>\n",
       "      <td>rec-1023-org</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>rec-0-org</td>\n",
       "      <td>rec-1540-dup-1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>rec-1-org</td>\n",
       "      <td>rec-1643-org</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>rec-1-org</td>\n",
       "      <td>rec-1986-org</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>rec-1-org</td>\n",
       "      <td>rec-41-org</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    rec_id_1        rec_id_2\n",
       "0  rec-0-org    rec-1023-org\n",
       "1  rec-0-org  rec-1540-dup-1\n",
       "2  rec-1-org    rec-1643-org\n",
       "3  rec-1-org    rec-1986-org\n",
       "4  rec-1-org      rec-41-org"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "indexer = recordlinkage.Index()\n",
    "        \n",
    "# soundex firstname, methapone surname, exact date of birth\n",
    "indexer.add(Block(['metaphone_given_name','metaphone_surname','date_of_birth']))\n",
    "# soundex firstname , day of birth\n",
    "indexer.add(Block(['metaphone_given_name','DayB']))\n",
    "#soundex firstname , month of birth\n",
    "indexer.add(Block(['metaphone_given_name','MonthB']))\n",
    "# metaphone surname, year of birth \n",
    "indexer.add(Block(['metaphone_surname','YearB']))\n",
    "# ssn\n",
    "indexer.add(Block(['soc_sec_id']))\n",
    "\n",
    "candidate_record_pairs = indexer.index(df_a)\n",
    "\n",
    "print(\"Number of record pairs :\",len(candidate_record_pairs))\n",
    "candidate_record_pairs.to_frame(index=False).head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In PRLT Phonetic encoding possible options are “soundex”, “nysiis”, “metaphone” or “match_rating”.**Other phonetic algorithm not included in PRLT : double-metaphne, phonix , phonex, OCNA, Fuzzy soundex (Christen 2012)**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparison"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Identifying the similarity between records pairs to create a comparison vectors. \n",
    "\n",
    "The previous step provided us a list of record pairs. In this step we compare the corresponding fields of each record pair using string distance algorithm.\n",
    "Jarowinkler and Levenshtein generate a **score between 0 and 1** that is binarized based on the threshold. In our case if the **score >0.85** we say there's agreeement (1) if not there's disagreement (0)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output of the comparison is the **comparison vector** that will be used for classification."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th>given_name</th>\n",
       "      <th>surname</th>\n",
       "      <th>date_of_birth</th>\n",
       "      <th>soc_sec_id</th>\n",
       "      <th>address_1</th>\n",
       "      <th>address_2</th>\n",
       "      <th>suburb</th>\n",
       "      <th>postcode</th>\n",
       "      <th>state</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rec_id_1</th>\n",
       "      <th>rec_id_2</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th rowspan=\"2\" valign=\"top\">rec-0-org</th>\n",
       "      <th>rec-1023-org</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rec-1540-dup-1</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th rowspan=\"3\" valign=\"top\">rec-1-org</th>\n",
       "      <th>rec-1643-org</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rec-1986-org</th>\n",
       "      <td>1.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rec-41-org</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                          given_name  surname  date_of_birth  soc_sec_id  \\\n",
       "rec_id_1  rec_id_2                                                         \n",
       "rec-0-org rec-1023-org           0.0      0.0              0           0   \n",
       "          rec-1540-dup-1         0.0      0.0              0           0   \n",
       "rec-1-org rec-1643-org           0.0      0.0              0           0   \n",
       "          rec-1986-org           1.0      0.0              0           0   \n",
       "          rec-41-org             0.0      0.0              0           0   \n",
       "\n",
       "                          address_1  address_2  suburb  postcode  state  \n",
       "rec_id_1  rec_id_2                                                       \n",
       "rec-0-org rec-1023-org          0.0        0.0     0.0         0      0  \n",
       "          rec-1540-dup-1        0.0        0.0     0.0         0      1  \n",
       "rec-1-org rec-1643-org          0.0        0.0     0.0         0      0  \n",
       "          rec-1986-org          0.0        0.0     0.0         0      0  \n",
       "          rec-41-org            0.0        0.0     0.0         0      0  "
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "compare_cl = recordlinkage.Compare()\n",
    "compare_cl.string('given_name', 'given_name', method='jarowinkler', threshold = 0.85, label='given_name')\n",
    "compare_cl.string('surname', 'surname', method='jarowinkler',threshold = 0.85, label='surname')\n",
    "compare_cl.exact('date_of_birth', 'date_of_birth', label='date_of_birth')\n",
    "compare_cl.exact('soc_sec_id', 'soc_sec_id', label='soc_sec_id')\n",
    "compare_cl.string('address_1', 'address_1', method ='levenshtein' ,threshold = 0.85, label='address_1')\n",
    "compare_cl.string('address_2', 'address_2', method ='levenshtein' ,threshold = 0.85, label='address_2')\n",
    "compare_cl.string('suburb', 'suburb', method ='levenshtein' ,threshold = 0.85, label='suburb')\n",
    "compare_cl.exact('postcode', 'postcode', label='postcode')\n",
    "compare_cl.exact('state', 'state', label='state')\n",
    "\n",
    "features = compare_cl.compute(candidate_record_pairs, df_a)\n",
    "features.head()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on comparison results, this step uses a classification algorithm to classify candidate records pairs in: matches, non-matches or potential matches.\n",
    "\n",
    "Probabilistic matching is based on a probability model that designates record pairs as matches, possible matches, or non-matches based on calculation of linkage scores and application of decision rules about these scores to define true matches. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ECM Classifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** EM-Algorithm ** :\n",
    "This Expectation-Maximisation (EM) algorithm is an unsupervised probabilistic algorithm which **automatically estimate a threshold for the likelihood score to decide a match and non-match**. This do not need training data.\n",
    "\n",
    "References :\n",
    "* Herzog, Thomas N, Fritz J Scheuren and William E Winkler. 2007. Data quality and record linkage techniques. Vol. 1 Springer.\n",
    "* Fellegi, Ivan P and Alan B Sunter. 1969. “A theory for record linkage.” Journal of the American Statistical Association 64(328):1183–1210."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of matched record pairs : 6276\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>rec_id_1</th>\n",
       "      <th>rec_id_2</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>rec-10-dup-0</td>\n",
       "      <td>rec-10-dup-2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>rec-10-dup-1</td>\n",
       "      <td>rec-10-dup-0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>rec-10-dup-1</td>\n",
       "      <td>rec-10-dup-2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>rec-10-org</td>\n",
       "      <td>rec-10-dup-0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>rec-10-org</td>\n",
       "      <td>rec-10-dup-1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       rec_id_1      rec_id_2\n",
       "0  rec-10-dup-0  rec-10-dup-2\n",
       "1  rec-10-dup-1  rec-10-dup-0\n",
       "2  rec-10-dup-1  rec-10-dup-2\n",
       "3    rec-10-org  rec-10-dup-0\n",
       "4    rec-10-org  rec-10-dup-1"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ecm = recordlinkage.ECMClassifier()\n",
    "matches = ecm.fit_predict(features)\n",
    "print(\"Number of matched record pairs :\",len(matches))\n",
    "matches.to_frame(index=False).head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### K-means classifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of matched record pairs : 6228\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>rec_id_1</th>\n",
       "      <th>rec_id_2</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>rec-10-dup-0</td>\n",
       "      <td>rec-10-dup-2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>rec-10-dup-1</td>\n",
       "      <td>rec-10-dup-0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>rec-10-dup-1</td>\n",
       "      <td>rec-10-dup-2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>rec-10-org</td>\n",
       "      <td>rec-10-dup-0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>rec-10-org</td>\n",
       "      <td>rec-10-dup-1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       rec_id_1      rec_id_2\n",
       "0  rec-10-dup-0  rec-10-dup-2\n",
       "1  rec-10-dup-1  rec-10-dup-0\n",
       "2  rec-10-dup-1  rec-10-dup-2\n",
       "3    rec-10-org  rec-10-dup-0\n",
       "4    rec-10-org  rec-10-dup-1"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kmeans = recordlinkage.KMeansClassifier()\n",
    "matches_kmeans = kmeans.fit_predict(features)\n",
    "\n",
    "# The predicted number of matches\n",
    "type(matches_kmeans)\n",
    "print(\"Number of matched record pairs :\",len(matches_kmeans))\n",
    "matches_kmeans.to_frame(index=False).head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evaluation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comparing match results with the known ground truth or gold standard to mesaure the performance of the matching process.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Gold standard \n",
    "The main objective of evaluation techniques is to achieve **high matching quality** in order to assess  the quality of the matched  data for a certain project ground-truth data also known as gold standard is required.\n",
    "\n",
    "There are several approches of how ground-thruth data can be generated. In this notebook the gold standard data was generated as part of the synthetic data used for matching."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# gold_ standard or known truth\n",
    "IMPORT_FILE_GOLD_STANDARD = './data/dataset_febrl3_true_links.csv'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rec_id_1</th>\n",
       "      <th>rec_id_2</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>rec-552-dup-1</th>\n",
       "      <th>rec-552-dup-3</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th rowspan=\"2\" valign=\"top\">rec-552-dup-0</th>\n",
       "      <th>rec-552-dup-3</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rec-552-dup-1</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th rowspan=\"2\" valign=\"top\">rec-552-org</th>\n",
       "      <th>rec-552-dup-3</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>rec-552-dup-1</th>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "Empty DataFrame\n",
       "Columns: []\n",
       "Index: [(rec-552-dup-1, rec-552-dup-3), (rec-552-dup-0, rec-552-dup-3), (rec-552-dup-0, rec-552-dup-1), (rec-552-org, rec-552-dup-3), (rec-552-org, rec-552-dup-1)]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_true_links = pd.read_csv(IMPORT_FILE_GOLD_STANDARD)\n",
    "df_true_links.columns=['rec_id_1','rec_id_2']\n",
    "df_true_links.set_index(['rec_id_1','rec_id_2'],inplace=True)\n",
    "df_true_links.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def metrics(links_true,links_pred,pairs):\n",
    "    if len(links_pred) > 0 :\n",
    "        matrix  = recordlinkage.confusion_matrix(links_true, links_pred, len(pairs))\n",
    "            \n",
    "        # precision\n",
    "        precision  = recordlinkage.precision(links_true, links_pred)\n",
    "\n",
    "         #precision\n",
    "        recall  = recordlinkage.recall(links_true, links_pred)\n",
    "\n",
    "        # The F-score for this classification is\n",
    "        fscore = recordlinkage.fscore(links_true,links_pred)\n",
    "        \n",
    "        return {'precision':precision, 'recall':recall,'fscore':fscore}\n",
    "    else :\n",
    "        return {'precision':0, 'recall':0,'fscore':0}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Create Function to Print Results\n",
    "def get_results(metrics):\n",
    "    print(\"\\n{0:20}    {1:6}    {2:6}    {3:6}\".format('Matching ','Precision','Recall','Fscore'))\n",
    "    print('------------------------------------------------------')\n",
    "    for i in metrics.keys():\n",
    "        print(\"{0:20}    {1:<6.4}      {2:<6.4f}      {3:<6.4f}\".format(i,metrics[i]['precision'],\n",
    "                                                                      metrics[i]['recall'],\n",
    "                                                                      float(metrics[i]['fscore'])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "results_score = {}\n",
    "\n",
    "results_score['ECM'] =  metrics(df_true_links,matches,features)\n",
    "results_score['K-means'] = metrics(df_true_links,matches_kmeans,features)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Matching                Precision    Recall    Fscore\n",
      "------------------------------------------------------\n",
      "ECM                     1.0         0.9599      0.9796\n",
      "K-means                 1.0         0.9526      0.9757\n"
     ]
    }
   ],
   "source": [
    "get_results(results_score)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* de Bruin, Jonathan. 2017. “Record Linkage. Python library. Version 0.8.1.” https://recordlinkage.readthedocs.io/.\n",
    "\n",
    "* Herzog, Thomas N, Fritz J Scheuren and William E Winkler. 2007. Data quality and record linkage techniques. Vol. 1 Springer.\n",
    "\n",
    "* Fellegi, Ivan P and Alan B Sunter. 1969. “A theory for record linkage.” Journal of the American Statistical Association 64(328):1183–1210.\n",
    "\n",
    "* Christen, Peter. 2012. Data matching: concepts and techniques for record linkage, entity resolution, and duplicate detection. Springer Science & Business Media."
   ]
  }
 ],
 "metadata": {
  "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.6.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "335px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}