Técnicas de aprendizado de máquina para analisar seqüências de caracteres?

Eu tenho muitas sequências de endereços:

1600 Pennsylvania Ave, Washington, DC 20500 USA

Eu quero analisá-los em seus componentes:

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

Mas é claro que os dados estão sujos: vêm de muitos países em vários idiomas, escritos de maneiras diferentes, contêm erros de ortografia, faltam peças, têm lixo extra, etc.

No momento, nossa abordagem é usar regras combinadas com a correspondência difusa de gazetas, mas gostaríamos de explorar técnicas de aprendizado de máquina. Marcamos dados de treinamento para aprendizado supervisionado. A questão é: que tipo de problema de aprendizado de máquina é esse? Realmente não parece ser agrupamento, classificação ou regressão ...

O mais próximo que posso chegar seria classificando cada token, mas você realmente deseja classificá-los todos simultaneamente, satisfazendo restrições como "deve haver no máximo um país"; e realmente existem muitas maneiras de tokenizar uma string, e você quer tentar cada uma delas e escolher a melhor .... Eu sei que existe uma coisa chamada análise estatística, mas não sei nada sobre ela.

Então: quais técnicas de aprendizado de máquina eu poderia explorar para analisar endereços?

Isso pode ser visto como um problema de rotulagem de sequência , no qual você tem uma sequência de tokens e deseja dar uma classificação para cada um. Você pode usar modelos de Markov ocultos (HMM) ou campos aleatórios condicionais (CRF) para resolver o problema. Existem boas implementações de HMM e CRF em um pacote de código aberto chamado Mallet .

No seu exemplo, você deve converter a entrada para o formato abaixo. Além disso, você deve gerar recursos extras.

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

Eu tive que resolver um problema muito semelhante para validar se um endereço é válido ou inválido.

Normalmente, o endereço tem a estrutura "1600 Pennsylvania Ave, Washington DC, 20500"

Uma sequência como

"Desci 2000 degraus e cheguei à Pennsylvania Avenue em Washington DC."

não é um endereço válido.

Isso pode ser resolvido por técnicas de classificação como SVM, Redes Neurais, etc.

A idéia é identificar um conjunto importante de recursos. Alguns destes podem ser:

1) O nome da rua começa com um número de bloco válido. A maioria dos números de bloco dos EUA são números (por exemplo, 1200) ou um número seguido por uma única letra (120A) ou um número após uma única letra (por exemplo, S200).

2) Se o endereço estiver bem formatado, os nomes das ruas terminarão em sufixos como Ave for Avenue, Dr for Drive, Blvd for Boulevard. É possível obter a lista de sufixos de rua nos EUA no site USPS.

3) O número de palavras no campo de endereço também pode ser uma característica interessante. Se houver muitas palavras, provavelmente não é um endereço válido. Por exemplo, veja o exemplo acima.

4) Quantas palavras ocorrem entre o número do bloco e o sufixo da rua no campo de endereço?

Eles podem ser usados ​​para treinar um algoritmo de aprendizado e o modelo resultante pode ser usado para validar se um determinado endereço é válido ou não.

Isso é meio que um hack que não requer sua própria solução: geocodificação reversa. Isso pode fornecer dados mais limpos ou realmente fazer todo o trabalho para você.

Por exemplo, aqui está um código Stata geocode3do SSC, que usa o Google. Eu acho que isso é semelhante ao Fuzzy Gazetteer . O primeiro endereço é bastante confuso, o segundo é limpo e o terceiro é estrangeiro. Outro software pode lidar com isso também.

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)

Isso funciona razoavelmente bem:

. 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  

O Kremlin tem um formato bem diferente.

Isso soa como um problema a ser resolvido com a classificação bidirecional LSTM. Você marca cada caractere da amostra como uma categoria, por exemplo

rua: 1 cidade: 2 província: 3 CEP: 4 país: 5

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

Agora, treine seu classificador com base nesses rótulos. Estrondo!