I have a huge dataset of addresses. I have another data stream that contains addresses that I need to match against those in the original dataset. As all the addresses are user-provided, matching them is not trivial. For example, 10 John Smith Square could be represented as 10 J.S. Square, J. Smith Sq 10, possibly even as only John Smith (which obviously misses the number and on top of that can collide with John Smith Street).

I am wondering if there are some known ways to reducing this ambiguity. My intuition is that some clustering should be possible, allowing me to match incoming addresses from the second dataset to the clusters of the first. I want to get to clusters that separate different street numbers, rather than put all addresses on a single street together.

I'm recently considering employing some sort of (possibly sparse) autoencoders, but was not able to find any literature to suggest that anyone else has tried a similar approach. So my question is, how can I employ autoencoders to cluster street address labels if anyone has tried anything of the sort? Otherwise, what alternative approaches would you suggest.

I've already have a dictionary to reduce the vocabulary by trivial substitutions (e.g. Square to Sq), but it remains to be tested whether this actually improves results or not, depending on what further analysis is applied after that. My current representation of the address strings is with bag-of-words, as I don't think word order changes much.

Handling the ambiguity of short strings requires a carefully supervised approach. Don't expect unsupervised approaches to "magically" do what you want them to do...

Anything unsupervised will cause undesired merges. For example, the words "fog" and "dog" are highly similar on an unsupervised way, but humans will consider them to be very different. So "Fog Road" and "Dog Road" will not be likely confused. But as you noted, "John Smith Square" and "John Smith Street" may end up being confused, but for an unsupervised approach like Levenshtein distance they would be very dissimilar - much more than Dog vs. Fog that differ only by a single letter.

• This seems to be assuming that we are defining a character-level similarity function, as the mentioned Levenshtein distance. How about a partial mapping/metric that is more at the word-level? I agree this depends on predefined dataset/dependencies, but this is exactly an example of what you called a supervised approach, which however is independent (in a way a kernel of) of the clustering. – mapto Jul 10 '18 at 10:03
• For example, the vocabulary of geographical objects (Street, Hill, Square, Walk,...) is generally limited, street numbers as well. This gives us three categories: name, number and geographical object type that can provide certain level of semantics in the general case. Have you seen any work done in such a direction? – mapto Jul 10 '18 at 10:10
• If you do that, all the work is done, there is nothing left to apply statistical analysis (e.g., clustering) on. Yes, if you have an ideal supervised mapping dictionary, then the problem is easier. But then, either two things are the same, or not. For clustering, you need all the inbetween. – Has QUIT--Anony-Mousse Jul 10 '18 at 21:20
• Thanks! You are right. A complete string metric would be needed for clustering. A partial dictionary would not address all three of the address components as I was considering them (number, name and object) – mapto Jul 11 '18 at 9:58

My instinct would say to start with a standard dataset and map all addresses ‒ both from your first and second datasets ‒ to that. In the standard dataset, each physical location would have a unique address.

The obvious source for the standard dataset is OpenStreetMap. You can query and dowload data from it using the Overpass API. Its query language, just like the whole OSM project, is well documented in my experience. Overpass Turbo is the user-friendly way with a graphical user interface to get started with the querying. Once you have developed a query, you can download data using e.g. wget, you just have to convert the query into the right URL at the Overpass API Convert Form by entering it into the window Overpass API Convert Form and selecting compact Overpass QL.

wget --timeout=0 http://overpass-api.de/api/interpreter?data=[your query in compact Overpass QL form] -O filename

In OSM, some addresses are associated with buildings, which are ways (closed polygons), and some are nodes inside the buildings' outlines, so that's a bit of complication.

This all sounds doable. However, the OSM is not complete, so it very much depends on your area of interest whether it's worthwhile to use OpenStreetMap.

• We've been using Google as mapping. It's more complete than OSM, but our data extraction is driven by our dataset, thus limited. One problem that we've encountered is a partial mismatch between our locations and what Google considers an address. I believe this corresponds to the ambiguity of buildings in OSM. This is a sort of contextual interpretation to what an address represents, and thus somewhat varies in our case, in Google Maps and in OSM. – mapto Jul 10 '18 at 8:47