<jupyter_start><jupyter_text>Probabilistic Record Linkage Table of Contents- [Introduction](Introduction)- [Setup](Setup)    - [Setup - Imports](Setup---Imports)    - [Setup - Database connection](Setup---Database-connection)    - [Data Definition](Data-Definition)- [String Comparators](String-Comparators)- [Fellegi-Sunter Record Linkage](Fellegi-Sunter-Record-Linkage)    - [Value Comparison](Value-Comparison)    - [Record Comparison](Record-Comparison)- [Appendix - String Comparators](Appendix---String-Comparators)- [References & Further Readings](References-&-Further-Readings)  Introduction- Back to the [Table of Contents](Table-of-Contents)In this lesson we will learn the basic idea behind probabilistic record linkage.We will use two datasets for this example. The first will be a list of people culled from "`ildoc_admit`" and "`ildoc_exit`". The second is a set of wage records from "`il_wage`".Probabilistic record linkage is somewhat different to deterministic record linkage. It takes into account a wieder range of potential identifiers. Identifiers are not unique anymore, which is why this method is also known as fuzzy matching/merging.It is a method that uses properties of variables commom to different datasets to determine the probability that two records refer to the same entity. Examples of the types of data items that might be compared in this method include gender, date of birth, age, and parts of a name.It computes weights for each idenfier used in the linkage based on the estimated ability to correctly identify a match, or a non-match. Then, by using the estimated weights a probability is calculated that two given records are the same entity. The analyst sets the threshold for this probability to determine when a pairing is defined a match.    Fellegi-Sunter ApproachThis is a popular method used in probabilisitc record linkage. Let's walk through an example how it works- Let's assume each person's wage record matches to one person record in the inmate data and we have 100,000 inmates in our inmate data. Then the odds for a match at random are 1:99,999- M, the reliability is the probability that a commom variable agrees on a matched pair. Approx. 1-error rate- U, the discriminating power is the probability that a commom variable agrees on a unmatched pair. Approx. the probability of aggreeing by chance- If first name is the same: m=0.9, u=0.01, ratio: 90:1, this means that the odds for a matchare now: 1:99,999x90:1=1:1,111- If last name is the same: m=0.9, u=0.04, ratio: 22:1, this means that the odds for a matchare now: 1:1,111x22:1=1:51- And you can add as many variables as possible, such as sex, age, date of birth, etc as long as they are in both datasets.  Setup- Back to the [Table of Contents](Table-of-Contents)  Setup - Imports- Back to [Table of Contents](Table-of-Contents)Before we start the Probabilistic Record Linkage example, we need to import the packages we will be using.  Please run the following code cell:<jupyter_code># Importing the modules required in this workbook
import datetime
import jellyfish
import math
import numpy
import pandas
import re
import six
import sqlalchemy
import string

# Database connection packages - one or the other will be imported below:
import psycopg2
import psycopg2.extras

print( "imports loaded at " + str( datetime.datetime.now() ) )<jupyter_output><empty_output><jupyter_text>Setup - Database connection- Back to [Table of Contents](Table-of-Contents)`Pandas` uses a database engine to connect to databases (via the `SQLAlchemy` Python package).  In the code cell below we create a `SQLAlchemy` database engine connected to our class database server for Pandas to use.<jupyter_code># set up database credentials
pandas_db = None
db_host = "10.10.2.10"
db_database = "appliedda"

# Create database connection for pandas.
connection_string = "postgresql://" + db_host + "/" + db_database
pandas_db = sqlalchemy.create_engine( connection_string )

print( "sqlalchemy postgresql database engine created at " + str( datetime.datetime.now() ) )<jupyter_output><empty_output><jupyter_text>Data Definition- Back to the [Table of Contents](Table-of-Contents)Before we begin the task of record linkage, it's important that we understand the variables in our data. In this workbook, we will take a cursory look at some of the values in our data and compute some simple statistics to ensure that the content makes sense. Begin by loading a subset of the data from "`person`" and "`il_wage`" into pandas data frames. After we load the two data sets, we call the `head` method on the first data set to examine the first few reords.<jupyter_code># Load person data
person_df = pandas.read_sql( 'SELECT * FROM person LIMIT 1000;', con = pandas_db )

print( "person data loaded at " + str( datetime.datetime.now() ) )
# Load wage data
il_wage_df = pandas.read_sql( 'SELECT * FROM il_wage WHERE year = 2015 LIMIT 1000;', con = pandas_db )

print( "il_wage data loaded at " + str( datetime.datetime.now() ) )
# Don't forget to close the connection (or "dispose" for a SQLAlchemy engine).
pandas_db.dispose()

print( "pandas database engine dispose()-ed at " + str( datetime.datetime.now() ) )<jupyter_output><empty_output><jupyter_text>Let's perform some quick summaries of the fields in the person data.To get a list of the unique values in a pandas column/Series, call the `.unique()` method on it - like `.value_counts()` from last assignment, only not sorted by frequency of use.<jupyter_code># Get the first few records from the person file.
person_df.head()
# print the distinct values in the birth_year, race, and sex columns
print("Distinct years = ", person_df["birth_year"].unique())
print("Distinct race = ", person_df["race"].unique())
print("Distinct sex = ", person_df["sex"].unique())

# Print the total number of rows and the number of rows with valid SSN,
#     first name, middle name, and last name.
print( "Total rows = ", len( person_df ) )

ssn_hash = person_df[ "ssn_hash" ]
print( "Rows with valid SSN = " + str( len( ssn_hash[ ~ pandas.isnull( ssn_hash ) ] ) ) )

name_first_hash = person_df[ "name_first_hash" ]
print( "Rows with valid name_first_hash = " + str( len( name_first_hash[ ~ pandas.isnull( name_first_hash ) ] ) )  )

name_middle_hash = person_df[ "name_middle_hash" ]
print( "Rows with valid name_middle_hash = " + str( len( name_middle_hash[ ~ pandas.isnull( name_middle_hash ) ] ) ) )

name_last_hash = person_df[ "name_last_hash" ]
print( "Rows with valid name_last_hash = " + str( len( name_last_hash[ ~ pandas.isnull( name_last_hash ) ] ) ) )<jupyter_output><empty_output><jupyter_text>Next we'll take a look at the second data set.<jupyter_code>il_wage_df.head()<jupyter_output><empty_output><jupyter_text>Let's perform some quick summaries of the fields in the wage data.<jupyter_code># Print the total number of rows and the number of rows with valid SSN,
#     first name, middle name, and last name.
print( "Total rows = ", len( il_wage_df ) )

ssn = il_wage_df[ "ssn" ]
print( "Rows with valid SSN = " + str( len( ssn[ ~ pandas.isnull( ssn ) ] ) ) )

name_first = il_wage_df[ "name_first" ]
print( "Rows with valid name_first = " + str( len( name_first[ ~ pandas.isnull( name_first ) ] ) ) )

name_middle = il_wage_df[ "name_middle" ]
print( "Rows with valid name_middle = " + str( len( name_middle[ ~ pandas.isnull( name_middle ) ] ) ) )

name_last = il_wage_df[ "name_last" ]
print( "Rows with valid name_last = " + str( len( name_last[ ~ pandas.isnull( name_last ) ] ) ) )<jupyter_output><empty_output><jupyter_text>Fellegi-Sunter Record Linkage- Back to the [Table of Contents](Table-of-Contents) Fellegi-Sunter Record Linkage is a probabilistic method that uses comparisons of fields that contain the same substantive types of data between records to calculate a weighted probability that records in different data sets refer to the same entity.  Examples of the types of data items that might be compared in this method include gender, date of birth, age, and parts of a name.In this section we will "manually" perform the steps in Fellegi-Sunter record linkage. Our goal is to illustrate the Fellegi-Sunter algorithm by breaking it into bitesize pieces. In our example we will compare first names and last names using Jaro-Winkler distance. In the Fellegi-Sunter algorithm, the result of a field comparison is assumed to follow a multinomial distribution. That means it can only take on finitely many values. Therefore we will define a function that compares two strings and returns the value 2, 1, or 0 to indicate an exact match, a nearly exact match, or anything else.   Value Comparison- Back to the [Table of Contents](Table-of-Contents)In this section, we will implement the value comparison stage of Fellegi-Sunter Record Linkage.  You will implement a function named "`fuzzy-string-comparator`" that accepts two strings and returns one of the following match levels:- 2 - exact match- 1 - close match- 0 - not a matchTo assess whether the two strings passed in match, we could convert both strings to capital letters, decode them into unicode, then calculate the Jaro-Winkler distance between the two strings (Jaro-Winkler distance is a fast-to-compute string distance based on common letters between two words).  We then assign a match level based on where the resulting match score falls in the following ranges:- 2 - exact match - score greater than or equal to ( >= ) 0.92- 1 - close match - score less than 0.92 but greater than or equal to 0.85.- 0 - not a match - score less than 0.85.Finally, we'll return that match score.A function that implements this is below.<jupyter_code># Please complete the following function that tells us how different two input strings are.
# It returns a match level with value 2, 1 or 0 (larger value means higher similarity)
# Calculate Jaro-Winkler distance after converting two strings into capital characters.
# Please use these three criteria, >=0.92, >=0.85, <0.85, to determine match level.

def fuzzy_string_comparator( string_1_IN, string_2_IN ):

    '''
    string_1_IN : input string No.1
    string_2_IN : input string No.2
    '''
    
    # return reference
    match_level_OUT = -1

    # Check if they are all strings
    if ( ( type( string_1_IN ) != str ) or ( type( string_2_IN ) != str ) ):
        
        match_level_OUT = 0
    
    #-- END check to see if strings are actually strings. --#
    
    ### BEGIN SOLUTION

    # declare variables
    cleaned_string_1 = ""
    cleaned_string_2 = ""
    distance = -1
    
    # convert strings to upper case, then to unicode
    
    # string 1
    cleaned_string_1 = string_1_IN.upper()
    cleaned_string_1 = six.text_type( cleaned_string_1 )

    # string 2
    cleaned_string_2 = string_2_IN.upper()
    cleaned_string_2 = six.text_type( cleaned_string_2 )
    
    # Calculate Jaro-Winkler distance after converting two strings into capital characters.
    distance = jellyfish.jaro_winkler( cleaned_string_1, cleaned_string_2 )

    # According to different thresholds, return the match level
    if distance >= 0.92:

        match_level_OUT = 2

    elif distance >= 0.85:
    
        match_level_OUT = 1

    else:
    
        match_level_OUT = 0
        
    #-- END conditional to set match level. --#

    ### END SOLUTION

    return match_level_OUT

#-- END function fuzzy_string_comparator --#

print( "==> Defined function fuzzy_string_comparator() at " + str( datetime.datetime.now() ) + "." )
# Let's see how the fuzzy_string_comparator works
score1 = fuzzy_string_comparator( "joshua", "joshua" )
score2 = fuzzy_string_comparator( "joshua", "joshau" )
score3 = fuzzy_string_comparator( "joshua", "todd" )

print( "Match level for joshua-joshua: " + str( score1 ) )
print( "Match level for joshua-joshau: " + str( score2 ) )
print( "Match level for joshua-todd: " + str( score3 ) )

# tests for our grading program:
assert score1 == 2
assert score2 == 2
assert score3 == 0<jupyter_output><empty_output><jupyter_text>The above function compares *text fields* in a record (other types of data would need different means of comparison). Next, we define a function that compares *records*.  This record comparison function assumes that records will have the form of a tuple: (identifier, first name, last name).  It returns a length 2 tuple that gives the result of applying a string comparator to the first name and to the last name._Note: Since our name values are hashed, we've replaced the fuzzy match call here with a simple equality test, since hash values being close together doesn't indicate that the names from which they were generated are close._<jupyter_code># Comparison_vector compare a pair of records, which consists of first name and last name.
# It returns a tuple with 2 match levels.

def compare_records( record_1_IN, record_2_IN ):

    '''
    record_1_IN : input record No.1
    record_2_IN : input record No.2
    '''
    
    # return reference
    results_OUT = None
    
    # declare variables
    value_1 = None
    value_2 = None
    field_1_match_level = -1
    field_2_match_level = -1
    
    # record_1_IN and record_2_IN have the form (id, first name, last name)
    
    # m, n store the comparing outcomes of first name and last name.
    value_1 = record_1_IN[ 1 ]
    value_2 = record_2_IN[ 1 ]
    if ( ( value_1 is not None ) and ( value_2 is not None ) ):
    
        #field_1_match_level = fuzzy_string_comparator( value_1, value_2 )
        # just check equality since hash.
        if ( value_1 == value_2 ):
            
            field_1_match_level = 2
            
        else:
            
            field_1_match_level = 0
            
        #-- END check to see if equal or not. --#
        
    else:
        
        field_1_match_level = 0
        
    #-- END check to see if empty values. --#
    
    value_1 = record_1_IN[ 2 ]
    value_2 = record_2_IN[ 2 ]
    if ( ( value_1 is not None ) and ( value_2 is not None ) ):
    
        #field_2_match_level = fuzzy_string_comparator( value_1, value_2 )
        # just check equality since hash.
        if ( value_1 == value_2 ):
            
            field_2_match_level = 2
            
        else:
            
            field_2_match_level = 0
            
        #-- END check to see if equal or not. --#
        
    else:
        
        field_2_match_level = 0
        
    #-- END check to see if empty values. --#
   
    results_OUT = ( field_1_match_level, field_2_match_level )

    return results_OUT

#-- END function compare_records() --#

print( "==> Defined function compare_records() at " + str( datetime.datetime.now() ) + "." )
# Try out the compare_records function

print( compare_records( ( 1, "joshua", "tokle" ), ( 2, "joshua", "smith") ) )
print( compare_records( ( 3, "joshua", "tokle" ), ( 4, "josue", "tolke") ) )<jupyter_output><empty_output><jupyter_text>Record Comparison- Back to the [Table of Contents](Table-of-Contents)Next, we'll work on implementing the section of Fellegi-Sunter Record Linkage that calculates a weighted probability that two records from different data sets refer to the same entity.Fellegi-Sunter Record Linkage uses two different sets of probabilities per pair of data items as weights in this step: m-weights and u-weights.For a given pair of data items that represent the same conceptual thing, for each match level:- An **m-weight** is the probability of seeing a particular match level if we assume that we are comparing two records that represent the same individual.- A **u-weight** is the probability of seeing a particular match level if we assume that that we are comparing two records that do *not* represent the same individual.For example, thinking of probabilities when two records are the same (m-weights), if two records represent the same person, the first names and last names should match with high probability - match level 2.  So, the m-weight for first name and last name having a match level of 2 when two records refer to the same person should be large.On the other hand, in the context of probabilities when two records are different (u-weights), suppose we had month of birth in our data set.  The probability that two random individuals will have the same month of birth is about 1/12, so for records that are not the same person, we would assign a u-weight of about 1/12 to the birth year being identical (where for a field like social security number, the u-weight of two different people having the same social security number is 0).Let's assign some preliminary and arbitrary m- and u-weights for first name and last name.- first name    - m-weights:        - match level 0: **_0.01_** (very unlikely the same person will have different first names)        - match level 1: **_0.14_** (also pretty unlikely that first names for a person will be mostly the same)        - match level 2: **_0.85_** (very likely that a person's first names will match exactly)    - u-weights:        - match level 0: **_0.88_** (probability that different people will have different first names)        - match level 1: **_0.10_** (probability that different people's first names will be mostly the same)        - match level 2: **_0.02_** (probability that different people will have same first name)- last name    - m-weights:        - match level 0: **_0.01_** (very unlikely the same person will have different last names)        - match level 1: **_0.09_** (also pretty unlikely that last names for a person will be mostly the same)        - match level 2: **_0.90_** (very likely that a person's last names will match exactly)    - u-weights:        - match level 0: **_0.91_** (probability that different people will have different first names)        - match level 1: **_0.08_** (probability that different people's first names will be mostly the same)        - match level 2: **_0.01_** (probability that different people will have same first name    In practice you would likely start with guesses or very general estimates like these, but then try to better estimate these by trying to fit them to a model or at least tweaking them after seeing preliminary output. In this case, we are just going to run with our initial estimates so we can move efficiently through this process.In the cell below, we create dictionaries that contain the m- and u-weights for our two columns.<jupyter_code># Make dictionaries to hold m_weights and u-weights.  In each dictionary, the weights for
#    a given field are mapped to a string label for that field ("first_name" and "last_name").
# Weights are captured in tuples of length 3, with the index in the tuple matching each of the 
#   match levels that can be returned by the fuzzy string comparator.
# In this tuple, we go from match level 0 (not the same), to match level 2 (identical)
#    as we move from left to right in the tuple, with each position in the tuple holding the
#    corresponding weight for that match level.

m_weights_dict = {}
m_weights_dict[ "first_name" ] = ( 0.01, 0.14, 0.85 )  # m-weights corresponding to first name
m_weights_dict[ "last_name" ] = ( 0.01, 0.09, 0.90 ) # m-weights corresponding to last name

u_weights_dict = {}
u_weights_dict[ "first_name" ] = ( 0.88, 0.10, 0.02 ) # u-weights corresponding to first name
u_weights_dict[ "last_name" ] = ( 0.91, 0.08, 0.01 ) # u-weights corresponding to last name

print( "==> Created m- and u-weight dictionaries at " + str( datetime.datetime.now() ) + "." )<jupyter_output><empty_output><jupyter_text>Now, for exercise 3, we are going to define a function that uses these weights to compare two records and return their record-level match score.In Fellegi-Sunter Record Linkage the match score for a given record is the at calculates a weighted probability that two records from different data sets refer to the same entity.The match_score function starts by comparing the two records passed in and retrieving a match level for the first name and last name.  The function then needs to:- get tuples of m- and u-weights for first name and last name.- retrieve the m- and u-weights for the particular match level calculated for first and last name.- calculate the "log probability" of each of the weights retrieved in the previous step.  The "log probability" of a probability is the log base-n of that probability - so, the result of calling the "`math.log()`" function on a probability (in this case, on each of the weights we retrieved in the step above).- use these log probabilities to calculate a match score for the first name and the second name.  Our algorithm for this match score:    - sum the log probabilities of the records being a match (the log probabilities of the m-weights).    - sum the log probabilities of the records not being a match (the log probabilities of the u-weights).    - subtract the non-match (u-weight) sum from the match (m-weight) sum.    - store your match score value in the variable "`score_OUT`" so that it is returned by the function.<jupyter_code>def match_score( record_1_IN, record_2_IN ):

    '''
    record_1_IN: input record No.1
    record_2_IN: input record No.2
    '''
    
    # return reference
    score_OUT = -1
    
    # declare variables
    match_level_tuple = None
    match_level_first_name = -1
    match_level_last_name = -1
    
    # Calulate the similarity level using compare_records
    match_level_tuple = compare_records( record_1_IN, record_2_IN )
    match_level_first_name = match_level_tuple[ 0 ]
    match_level_last_name = match_level_tuple[ 1 ]
    
    # Use match levels and m- and u-weights to calculate a match score for this record.

    ### BEGIN SOLUTION
    
    # declare variables
    m_weights_list_first_name = None
    m_weights_list_last_name = None
    u_weights_list_first_name = None
    u_weights_list_last_name = None
    first_name_m_weight = -1
    first_name_u_weight = -1
    last_name_m_weight = -1
    last_name_u_weight = -1
    log_prob_given_match = None
    log_prob_given_nonmatch = None
    
    # get lists of m- and u- weights for each field from weights dictionaries defined above.
    m_weights_list_first_name = m_weights_dict[ "first_name" ]
    m_weights_list_last_name = m_weights_dict[ "last_name" ]
    u_weights_list_first_name = u_weights_dict[ "first_name" ]
    u_weights_list_last_name = u_weights_dict[ "last_name" ]
   
    # get weights for match levels returned by compare_records.
    first_name_m_weight = m_weights_list_first_name[ match_level_first_name ]
    first_name_u_weight = u_weights_list_first_name[ match_level_first_name ]
    last_name_m_weight = m_weights_list_last_name[ match_level_last_name ]
    last_name_u_weight = u_weights_list_last_name[ match_level_last_name ]
    
    # calculate log-probabilities for each field assuming a match (m-weight),
    #    and assuming a non-match (u-weight).  Log-probability is the natural
    #    log (math.log() in Python) of the probability of a given match level.
    log_prob_first_name_given_match = math.log( first_name_m_weight )
    log_prob_last_name_given_match = math.log( last_name_m_weight )
    log_prob_first_name_given_no_match = math.log( first_name_u_weight )
    log_prob_last_name_given_no_match = math.log( last_name_u_weight )
    
    # For match and no-match, sum the log-probabilities for each field.
    
    # What's the log-probability of seeing this comparison vector if the records are a match?
    log_prob_given_match = log_prob_first_name_given_match + log_prob_last_name_given_match
    
    # What's the log-probability of seeing this comparison vector if the records are a nonmatch?
    log_prob_given_nonmatch = log_prob_first_name_given_no_match + log_prob_last_name_given_no_match
    
    # match score is the sum of the log probabilities given a match
    #    minus the sum of the log probabilites given no match.
    score_OUT = log_prob_given_match - log_prob_given_nonmatch
    
    ### END SOLUTION
    
    # return match score.
    return score_OUT

#-- END function match_score() --#

print( "==> Defined function match_score() at " + str( datetime.datetime.now() ) + "." )
# Have a rough look at its sample output
print(match_score((1, "joshua", "tokle"), (2, "joshua", "smith")))
print(match_score((1, "joshua", "tokle"), (4, "joshu", "tolke")))
print(match_score((1, "joshua", "tokle"), (7, "christina", "jones")))<jupyter_output><empty_output><jupyter_text>Finally, we can try to link people in our "`person`" table with "`il_wage`" records.We use our "`match_score()`" function to compare each name in the person list with each name in the wage record list, storing only matches whose score exceeds a threshold (0.5, to start) in a separate list of potential matches._Note: This code cell might take quite a few minutes to run._<jupyter_code># This cell takes a few minutes to execute

# configuration
match_score_min = 0.5

# Create an empty list to save the outputs
potential_matches = []

# Loop over uc data frame by row
person_counter = 0
for person_index, person_row in person_df.iterrows():

    # increment counter
    person_counter += 1
    
    # Get ID, FirstName and LastName of uc
    current_person_id = person_row[ "id" ]
    current_person_first_name = person_row[ "name_first_hash" ]
    current_person_last_name = person_row[ "name_last_hash" ]

    # store in tuple for comparison
    current_person_record = ( current_person_id, current_person_first_name, current_person_last_name )
    
    #print( "==> Processing UC person " + str( person_counter ) + ": " + str( current_person_record ) )
    
    # Loop over wage data frame by lines
    wage_counter = 0
    for wage_index, wage_row in il_wage_df.iterrows():    

        # increment counter
        wage_counter += 1

        # Get id, name_first and name_last from NSF row.
        current_wage_id = wage_row[ "id" ] # no person ID, so using id.
        current_wage_first_name = wage_row[ "name_first" ]
        current_wage_last_name = wage_row[ "name_last" ]

        # store in tuple for comparison
        current_wage_record = ( current_wage_id, current_wage_first_name, current_wage_last_name )

        # print( "====> Processing wage person " + str( wage_counter ) + ": " + str( current_wage_record ) )

        # Calculate the match score of each pair of records
        score = match_score( current_person_record, current_wage_record )

        # Save those pairs with score equal to or greater than 0.5
        if score >= match_score_min:
            
            # good enough - add to potential_matches
            potential_matches.append( ( score, current_person_record, current_wage_record ) )
            
        #-- END conditional to see if score is above our threshold --#
        
    #-- END loop over wage data frame rows. --#
    
    # output a little message every 1000 rows.
    if ( person_counter % 1000 == 0 ):
        
        print( "==> Processed " + str( current_wage_record ) + " of " + str( len( person_df ) ) + " person records." )
        
    #-- END check to see if we've processed another thousand rows yet. --#

#-- END loop over UC data frame rows. --#
        
# Sort the output so the best matches appear at the top

# define lambda to retrieve score from each tuple (first item in tuple)
lambda_get_score = lambda x: x[0]

# sort
potential_matches = sorted( potential_matches, key = lambda_get_score, reverse = True )

# output matches:
print( "Matches, in order of descending match score:" )
for current_match in potential_matches:
    
    # print current match.
    print( "==> " + str( current_match ) )

#-- END output loop. --#
    
# How did we do?<jupyter_output><empty_output><jupyter_text>And finally, we assess the potential matches displayed above - how did our algorithm do?  Appendix - String Comparators- Back to the [Table of Contents](Table-of-Contents)In this section we will demonstrate different string comparison algorithms provided by the [jellyfish](https://github.com/sunlightlabs/jellyfish) package ( [https://github.com/sunlightlabs/jellyfish](https://github.com/sunlightlabs/jellyfish) ).For each method we examine, we'll write a function that accepts a name that we want to find matches for and a list of names in which we should look, and that returns a list of the names in that list that are most similar to the name of interest.We will start by creating a `set` of unique first names from the "`il_wage`" data. The `name_first_hash` field is missing some values which are represented as NaN in the data frame. To prevent errors later on, we only include valid character strings (which have type `str`) in our list of unique names.<jupyter_code># If we were starting from scratch, we'd need to import jellyfish
# import jellyfish

# Make a set storing the unique first name with respect to the nsf dataset
unique_first_names = set( name for name in il_wage_df[ "name_first_hash" ] if type( name ) == six.text_type )<jupyter_output><empty_output><jupyter_text>Next, we will define our function "`closest_names`" that:* Accepts a string name we are interested in matching as input argument "`name_IN`".+ Accepts a list of names in which we want to look for "`name_IN`", in argument "`find_name_in_list_IN`".* Accepts an optional number of results we want returned as input argument "`result_count_IN`".* Compares the name in `name_IN` to each name in `unique_first_names` and calculates the "distance" between the two strings using the Levenshtein Distance string comparator from `jellyfish`.* Return a list of size `result_count_IN` of names in `uniq_first_names` that are "closest" to `name_IN`.From wikipedia, the Levenshtein Distance is defined as:> "In information theory and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other. It is named after <NAME>, who considered this distance in 1965."> &mdash; [https://en.wikipedia.org/wiki/Levenshtein_distance](https://en.wikipedia.org/wiki/Levenshtein_distance)_Note that in the comparison we capitalize both names being compared, so that letter case doesn't affect the final distance._<jupyter_code>def closest_names( name_IN, find_name_in_list_IN, result_count_IN = 10 ):

    # return reference
    results_OUT = []
    
    # declare variables
    other_name = ""
    cleaned_name = ""
    cleaned_other_name = ""
    get_distance_lambda = None
    
    # first, standardize the name - convert to upper case and to unicode.
    cleaned_name = name_IN.upper()
    cleaned_name = six.text_type( cleaned_name )
    
    # First create a list of tuples (other_name, distance), where other_name is taken from uniq_first_names
    distances = []

    # loop over unique_first_names to calculate and store distances
    for other_name in find_name_in_list_IN:
        
        # standardize the other name.
        cleaned_other_name = other_name.upper()
        cleaned_other_name = six.text_type( cleaned_other_name )
        
        # get distance from name to other_name (converted to upper case so we are case-insensitive.)
        distance_value = jellyfish.levenshtein_distance( cleaned_name, cleaned_other_name )
        
        # add tuple to distances
        current_tuple = ( other_name, distance_value )
        distances.append( current_tuple )
    
    #-- END loop over unique_first_names --#
    
    # Sort distances by the second element in the tuple.
    
    # define lambda function to retrieve the distance (the second item in the tuple)
    #    and return it.  Lambda functions are little one line functions.  More information:
    #    https://docs.python.org/2/reference/expressions.html#lambda
    get_distance_lambda = lambda distance_tuple_list_IN : distance_tuple_list_IN[ 1 ]
    
    # sort matching names by distance
    results_OUT = sorted( distances, key = get_distance_lambda )
    
    # get the number of results requested using Python's slice notation.
    results_OUT = results_OUT[ : result_count_IN ]
    
    # return results
    return results_OUT
    
    '''
    # For reference, compacted version - you can do this, but please don't.
    
    # First create a list of tuples (other_name, distance), where other_name is taken from uniq_first_names
    distances = [ ( other_name, jellyfish.levenshtein_distance( unicode( name_IN.upper() ), unicode( other_name.upper() ) ) )
        for other_name in unique_first_names ]

    # Sort distances by the second element in the tuple, and return the top n values
    return sorted(distances, key=lambda x: x[1])[:result_count_IN]
    '''

#-- END function closest_names() --#

print( "==> Defined function closest_names() at " + str( datetime.datetime.now() ) + "." )<jupyter_output><empty_output><jupyter_text>Let's try it out on some names.<jupyter_code># Experiment the function with several names.
print( closest_names( "Jennifer", unique_first_names ) )
print( closest_names( "Sonya", unique_first_names ) )
print( closest_names( "<NAME>", unique_first_names ) )<jupyter_output><empty_output><jupyter_text>Recall that Levenshtein distance is a kind of edit distance. Edit distances count the number of edit operations needed to change one word to another, and different edit distances count different edit operations as valid. In the case of Levenshtein distance, the valid edit operations are inserting a letter, deleting a letter, or changing a letter. It would be interesting to compare this output to the output from other string comparators included in the jellyfish package:* **`jellyfish.lenvenshtein_distance`** - _Levenshtein distance_: edit distance where the valid operations are inserting a letter, deleting a letter, or changing a letter* **`jellyfish.damerau_levenshtein_distance`** - _Levenshtein-Damerau distance_: edit distance which includes the same operations as Levenshtein distance but also allows transposing two adjacent letters. This can be useful for finding words with typos.* **`jellyfish.jaro_winkler`** - _Jaro-Winkler distance_: a fast-to-compute string distance based on common letters between two words_Note: For edit distance smaller numbers indicate closer strings, but for Jaro-Winkler distance larger values indicate closer strings._Let's update our `closest_names` function so that we can specify the string comparator we want to use.  Changes from previous function:- add ability to pass in the string distance calculation function you want to use as an argument, named "`string_comparator_function_IN`".    - just pass the name of the function, not in quotation marks, and not followed by parentheses (just like they are shown in the list of functions above).- add ability to reverse sort order for returning "closest" strings to name passed in.  New parameter "`reverse_sort_IN`" defaults to `False` (to match distance scores where a larger number indicates two strings being further apart).  Set it to `True` for distance scores like Jaro-Winkler distance where a larger number indicates two strings are closer together.<jupyter_code>def closest_names_2( string_comparator_function_IN, name_IN, find_name_in_list_IN, reverse_sort_IN = False, result_count_IN = 10 ):

    # return reference
    results_OUT = []
    
    # declare variables
    other_name = ""
    cleaned_name = ""
    cleaned_other_name = ""
    get_distance_lambda = None
    
    # first, standardize the name - convert to upper case and to unicode.
    cleaned_name = name_IN.upper()
    cleaned_name = six.text_type( cleaned_name )
    
    # First create a list of tuples (other_name, distance), where other_name is taken from uniq_first_names
    distances = []

    # loop over unique_first_names to calculate and store distances
    for other_name in find_name_in_list_IN:
        
        # standardize the other name.
        cleaned_other_name = other_name.upper()
        cleaned_other_name = six.text_type( cleaned_other_name )
        
        # get distance from name to other_name (converted to upper case so we are case-insensitive.)
        distance_value = string_comparator_function_IN( cleaned_name, cleaned_other_name )
        
        # add tuple to distances
        current_tuple = ( other_name, distance_value )
        distances.append( current_tuple )
    
    #-- END loop over unique_first_names --#
    
    # Sort distances by the second element in the tuple.
    
    # define lambda function to retrieve the distance (the second item in the tuple)
    #    and return it.  Lambda functions are little one line functions.  More information:
    #    https://docs.python.org/2/reference/expressions.html#lambda
    get_distance_lambda = lambda distance_tuple_list_IN : distance_tuple_list_IN[ 1 ]
    
    # sort matching names by distance
    results_OUT = sorted( distances, key = get_distance_lambda, reverse = reverse_sort_IN )
    
    # get the number of results requested using Python's slice notation.
    results_OUT = results_OUT[ : result_count_IN ]
    
    # return results
    return results_OUT
    
    '''
    # For reference, compacted version - you can do this, but please don't.
    
    # First create a list of tuples (other_name, distance), where other_name is taken from uniq_first_names
    distances = [(other_name, string_comparator(unicode(name.upper()), unicode(other_name.upper())))
                 for other_name in uniq_first_names]
    
    # Sort distances by the second element in the tuple, and return the top n values
    return sorted(distances, key=lambda x: x[1], reverse=reverse_sort)[:n]
    '''

#-- END function closest_names_2() --#

print( "==> Defined function closest_names_2() at " + str( datetime.datetime.now() ) + "." )
# Try it!
print( "Closest names for \"William\" using Levenshtein-Damerau distance:" )
print( closest_names_2( jellyfish.damerau_levenshtein_distance, "William", unique_first_names ) )

print( "\n\nClosest names for \"William\" using Levenshtein-Damerau distance:" )
print( closest_names_2( jellyfish.jaro_winkler, "Wiliam", unique_first_names, reverse_sort_IN = True ) )<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07523535564853556, 'fraction_numerical': 0.00975418410041841, 'mean_word_length': 3.7616735151288756, 'pattern_counts': {'":': 2, '<': 64, '<?xml version=': 0, '>': 81, 'https://': 7, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '15', 'dir': 'jupyter-structured-clean-dedup', 'id': '449861', 'license': 'CC0-1.0', 'n_tokens_mistral': 11212, 'n_tokens_neox': 10721, 'n_words': 4513, 'path': 'notebooks/session_05-record_linkage/probabilistic_record_linkage.ipynb', 'repo_name': 'Coleridge-Initiative/ada-2017-justice', 'size': '38256'}