Distance measure calculation addresses for record linking

Question

At the moment we use different methods for record linking locations in different datasets.

Theoretically given two locations we can give a prediction on how well they match (are the same). This is not just based on address data (street, house number, zip, city, country, latitude, longitude) but also based on the name, type of establishment and other properties like phonenumber. Since most features are prone to fuzzy errors (different spellings, writing styles, formatting, human entry error, null-values (absent)) this means we cannot do strict comparisons.

Using many business rules, basic distance calculations, etc. we can clean & reformat the data so we can have a pretty good comparison and high accuracy on matches.

eg.

Datlinq BV, Roer 266, 2908MC, Capelle aan den IJssel

is the same as

datlinq, 266 Roer, capelle a/d yssel

but not as

Ferro BV, Roer 266, 2908MC, Capelle aan den IJssel

Our problem is many a scaling issue:

We need smart ways to reduce the dataset so we don't compare every location in dataset A to every location dataset B.

At this moment we do some pre-filtering (boxing) on latitude / longitude (if present)

However I was wondering if we could somehow generate a vector for each data location and us a basic distance calculation to find matches (or match candidates) in other datasets.

Or maybe another way to find very similar locations across huge datasets.

I'd love to use a machine learning model for this, but I am stumped how to generate numerical features out of a string address, location type & telephone number, without applying to many business rules.

So the actual question is:

• Are there smart ways to do (parallel) record linking across big datasets (using Spark or so)
• Is the approach of converting locations to vectors using a ml model and then using a distance calculation to find nearby points a good approach?
• Is there terminology I should use to find more information about this problem? Are there papers / experiments?

-- Update 20170829 151213

So we are working on prefiltering datasets based on nearby locations, but unfortunately for many datasets we don't have reliable lat/longs. So I'm looking for a more general approach.

So based on the fact that we cannot positively resolve a nearby location without comparing textual addresses. A smart heuristic is something I'm looking for, but I want to incorporate weights to certain (fuzzy) features, eg. zipcodes should match more closely towards the beginning then towards the end, phonenumbers other way around. Streets and cities maybe spelled very differently including abbreviations.

Sure I can extract all these features and create business rules with arbitrary weights, but I'd rather have an unsupervised ML model learn the most important features based on positive and negative test/trainingsets of address matches. I would also guess that weights will vary differently by country/language so maintaining these by hands seems a suboptimal solution.

Answer 1

Is the problem that you can resolve a new address B to a location reliably, but, don't know if it's the same address as an existing address A? then it seems straightforward to perform the expensive check for near-matches on only addresses that also resolve to a nearby location, and consider them in order of distance. The simple distance calculation shouldn't be expensive.

Or are you saying that you can't resolve B to a location by itself, and have to resolve it by finding a fuzzy match with some A, but you don't know where A might be? Then you need some cheap heuristic match to compute over all records. What about simply the distribution of characters/digits in every string? easy to compute, small, and easy to compare. Presumably near-matches have nearly the same letters and digits, so might correlate well with actual fuzzy matches.

Edited to add:

You could try to build a classifier that can tell when two different strings represent the same address. That's not your ultimate goal, I know. But along the way you might be able to learn a useful intermediate vector representation of the strings that is relevant for determining same/not same. And then use that intermediate representation.

In theory that's what a neural network could do. Inputs are two strings; they share weights/layers that transform to an intermediate rep; then the top of the network learns same/not same.

"Simple as that" but in practice you might find that learning this way takes such a huge network to do well that it's infeasible.

Maybe someone knows an equivalent idea that doesn't need the brute force of deep learning.