<jupyter_start><jupyter_text>Learning String Similarity for Address Resolution <NAME>, Phronesis LLC, 2015-12-15  ProblemIn this notebook, we'll try to learn a custom string metric for address resolution.Generally, when we're doing this kind of thing, we use something like Levenshtein distance or Jaro-Winkler distance to measure the distance between two strings.  This generally makes sense for measuring distances between first names:     Hilary    Hillary    Hillry    are plausibly the same name with various typos.However, this is clearly not the best method for measuring distances between addresses:    123 Fake Street    123 Fake St    124 Fake StreetFrom writing conventions, it's obvious that the first two addresses are the same and the third is different, despite the fact that the first and third have the smallest Levenshtein distance.  So we see that these kind of metrics are degraded when applied to addresses due to     different characters have different importance    abbreviations are commonly used ApproachWe could try to write down a set of weights for different characters and a mapping from words to abbreviations, but that would be tedious and may be brittle.  It also would require separate hand-written rules for each datatype.  We could spend time developing a set of rules for addresses, then realize that we need to do the same thing for corporation names, etc... So ideally we want to be able to learn the string similarity metric from data.(Note, in this document, we'll say two addresses are "equivalent" if they refer to the same physical location.)But what kind of training data can we use for this task?  It turns out that it is not impossible to use publicly available datasets to construct a reasonably high fidelity set of pairs of non-equivalent addresses and pairs of equivalent addresses.  The first set of pairs could be constructed by finding a high-quality list of unique addresses in a region and thus any pair of addresses is non-equivalent.  The second set is a little trickier, but could be constructed by taking a messy dataset and joining addresses on some less messy attribute (i.e. phone number).  This kind of dataset may be publicly available in the form of campaign finance records, government contracting records, etc...From these two sets of paired addresses, we can construct a training dataset consisting of triplets of addresses:    (anchor, positive, negative)where    - anchor and positive are equivalent    - anchor and negative are not equivalentWe'll use this data to learn a function `F` that maps address strings to N-dimensional space while minimizing the function    max(0, distance(F(anchor), F(positive)) - distance(F(anchor), F(negative)) + margin)    over the training data, with    distance(x, y) = 1 - cosine_similarity(x, y)The model we use is a LSTM neural network with this triplet loss function implemented in the `Keras` `python` module.  Code First we load some libraries, set some parameters and initialize some helpers.<jupyter_code>import keras
import pandas as pd
from fuzzywuzzy import fuzz
from matplotlib import pyplot as plt

import sys
sys.path.append('/Users/BenJohnson/projects/what-is-this/wit/')
from wit import *

# --
# Setting parameters
num_features = 75  # Dimension of character embedding (more than enough)
max_len      = 350 # Max length of input string in characters
formatter    = KerasFormatter(num_features, max_len)<jupyter_output>Using Theano backend.<jupyter_text>Next, we load the data and construct a training set in the format we described above.(Note: At the moment, we won't actually create the negative training pairs using a high-quality list of unique addresses in a region.  Rather, we'll use randomly drawn pairs of addresses under the assumption that the number of addresses is sufficiently high as to make collisions relatively uncommon. We plan to re-run these analyses with higher quality negative training pairs in the near future.)<jupyter_code># --
# Construct training set

# Load set of matching addresses
df         = pd.read_csv('real_address.csv')
df['id']   = 0

# Make training set
train      = make_triplet_train(df.head(60000), N = 20)

# Format training set for input into `wit`
trn, levs  = formatter.format(train, ['obj'], 'hash')<jupyter_output><empty_output><jupyter_text>Now we can use the `wit` TripletClassifier model to learn the string embedding we described above.<jupyter_code>classifier = TripletClassifier(trn, levs)
classifier.fit(batch_size = 250, nb_epoch = 3)<jupyter_output><empty_output><jupyter_text>And finally, we can compare the behavior of the learned similarity metric to Levenshtein distance.  We expect Levenshtein distance to perform adequately on addresses that have different street names, but expect it to fare much worse on addresses with different (but similar) street numbers or different levels of abbreviation.<jupyter_code>def compare(a, b):
    # Similarity metric learned by `wit`
    pred    = model.predict(formatter._format_x([a, b], False))
    wit_sim = np.round(np.dot(pred, pred.T)[0, 1], 3)

    # Fuzzywuzzy.fuzz.ratio Levenshtein similarity
    fuzz_sim = int(np.round(fuzz.ratio(a, b)))
    
    print '\nwit_sim : %f\nlev_sim : %d\n' %(wit_sim, fuzz_sim)

print "\n--\nCase 1, different street names : ('101 fake street', '101 elm street')"
compare('101 fake street', '101 elm street')

print "\n--\nCase 2, different abbrevations : ('101 fake street', '101 fake st')"
compare('101 fake street', '101 fake st')

print "\n--\nCase 3, different house numbers : ('101 fake street', '102 fake street')"
compare('101 fake street', '102 fake street')<jupyter_output>--
Case 1, different street names : ('101 fake street', '101 elm street')

wit_sim : 0.790000
lev_sim : 83


--
Case 2, different abbrevations : ('101 fake street', '101 fake st')

wit_sim : 0.959000
lev_sim : 85


--
Case 3, different house numbers : ('101 fake street', '102 fake street')

wit_sim : 0.861000
lev_sim : 93
{'fraction_non_alphanumeric': 0.06763770299681902, 'fraction_numerical': 0.02109492717227524, 'mean_word_length': 4.552044609665428, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '612201', 'license': 'Apache-2.0', 'n_tokens_mistral': 1703, 'n_tokens_neox': 1543, 'n_words': 800, 'path': 'wit/notebooks/address-matching.ipynb', 'repo_name': 'benjibonji/wit', 'size': '5978'}