Machine learning techniques for parsing strings?

Question

I have a lot of address strings:

1600 Pennsylvania Ave, Washington, DC 20500 USA

I want to parse them into their components:

street: 1600 Pennsylvania Ave
city: Washington
province: DC
postcode: 20500
country: USA

But of course the data is dirty: it comes from many countries in many languages, written in different ways, contains misspellings, is missing pieces, has extra junk, etc.

Right now our approach is to use rules combined with fuzzy gazetteer matching, but we'd like to explore machine learning techniques. We have labeled training data for supervised learning. The question is, what sort of machine learning problem is this? It doesn't really seem to be clustering, or classification, or regression....

The closest I can come up with would be classifying each token, but then you really want to classify them all simultaneously, satisfying constraints like "there should be at most one country;" and really there are many ways to tokenize a string, and you want to try each one and pick the best.... I know there exists a thing called statistical parsing, but don't know anything about it.

So: what machine learning techniques could I explore for parsing addresses?

Answer 1

This can be seen as a sequence labeling problem, in which you have a sequence of tokens and want to give a classification for each one. You can use hidden Markov models (HMM) or conditional random fields (CRF) to solve the problem. There are good implementations of HMM and CRF in an open-source package called Mallet.

In your example, you should convert the input to the format below. Moreover, you should generate extra-features.

1600 STREET
Pennsylvania STREET
Ave STREET
, OUT
Washington CITY
, OUT
DC PROVINCE
20500 POSTCODE
USA COUNTRY

Answer 2

This sounds like a problem to be solved with bidirectional LSTM classification. You tag each character of the sample as one category for example

street: 1 city: 2 province: 3 postcode: 4 country: 5

1600 Pennsylvania Ave, Washington, DC 20500 USA
111111111111111111111, 2222222222, 33 44444 555

Now, train your classifier based on these labels. Boom!

Answer 3

I had to solve a very similar problem to validate whether an address is valid or invalid.

Typically address have the structure "1600 Pennsylvania Ave, Washington DC, 20500"

A string such as

"I went down 2000 steps and reached Pennsylvania Ave in Washington DC."

is not a valid address.

This can be solved by classification techniques such as SVM, Neural Networks etc.

The idea is to identify a key set of features. Some of these could be:

1) Does the street name start with a valid block number. Most US block numbers are either numbers (e.g. 1200) or a number followed by a single letter (120A) or a number following a single letter (e.g. S200).

2) If the address is well formatted, the street names end in suffixes like Ave for avenue, Dr for Drive, Blvd for Boulevard. It is possible to obtain the US street suffix list from USPS site.

3) The number of words in the street address field can also be an interesting feature. If there are too many words, it is probably not a valid address. E.g. see the example above.

4) How many words occur between the block number and the street suffix in address field ?

These can be used to train a learning algorithm and the resulting model can be used to validate if a given address is valid or not.

Answer 4

This is a bit of a hack that does not require your own solution: reverse geocoding. This can either give you cleaner data or actually do all the work for you.

For example, here's some Stata code with geocode3 from SSC, which uses Google. I guess this is similar to Fuzzy Gazetteer. The first address is pretty messy, the second is clean, and the third is foreign. Other software can handle this is as well.

clear
set obs 3
gen address =""
replace address = "Big Foot Museum in Felton CA" in 1
replace address = "1600 Pennsylvania Ave, Washington, DC 20500 USA" in 2 
replace address = "ул. Ильинка, д. 23 103132, Москва, Россия" in 3
geocode3, address(address)
gen coord = string(g_lat) + "," + string(g_lon)
geocode3, reverse coord(coord)

This works reasonably well:

. list r_addr , clean noobs

                                                                             r_addr  
                                      121 San Lorenzo Avenue, Felton, CA 95018, USA  
    1600 Pennsylvania Avenue Northwest, President's Park, Washington, DC 20500, USA  
                                         ulitsa Ilyinka, 23, Moscow, Russia, 101000  

The Kremlin does have a pretty different format.