¿Cómo hacer direcciones postales coincidencia difusa?

14

Me gustaría saber cómo hacer coincidir las direcciones postales cuando su formato difiere o cuando uno de ellos está mal escrito.

Hasta ahora he encontrado diferentes soluciones, pero creo que son bastante antiguas y poco eficientes. Estoy seguro de que existen algunos métodos mejores, por lo que si tiene referencias para que yo lea, estoy seguro de que es un tema que puede interesar a varias personas.

La solución que encontré (los ejemplos están en R):

  • Distancia de Levenshtein, que equivale al número de caracteres que tiene que insertar, eliminar o cambiar para transformar una palabra en otra.

    agrep("acusait", c("accusait", "abusait"), max = 2, value = TRUE) ## [1] "accusait" "abusait"

  • La comparación de fonemas

    library(RecordLinkage) soundex(x<-c('accusait','acusait','abusait')) ## [1] "A223" "A223" "A123"

  • El uso de un corrector ortográfico (eventualmente uno bayesiano como el de Peter Norvig) , pero supongo que no es muy eficiente en la dirección.

  • Pensé en usar las sugerencias de Google Sugiere, pero del mismo modo, no es muy eficiente en las direcciones postales personales.

  • Puede imaginarse utilizando un enfoque supervisado de aprendizaje automático, pero debe haber almacenado las solicitudes mal escritas de los usuarios para hacerlo, lo cual no es una opción para mí.

Stéphanie C
fuente
Sugeriría usar una base de datos real que admita la coincidencia de cadenas difusas: posgres . Será eficiente
Emre
¿Solo EE. UU., Canadá, Reino Unido, Francia, Japón, varios países ...? Presumiblemente para cada uno, primero determina / adivina qué idioma y país es, luego aplica un clasificador específico del país. ¿Tiene un conjunto de capacitación y, de ser así, cuál es su distribución de países?
smci
¿Dónde terminaste con esto? La solución que diseñamos fue restregar y enriquecer las direcciones y los nombres de lugares, presionar la geocodificación de Google y colocar las API web y luego hacer algunos cálculos aproximados para determinar el resultado correcto en comparación con los datos sin procesar. Es un poco torpe pero funciona, pero debe haber una forma más elegante de normalizar direcciones y lugares / ubicaciones.
Chris Smith

Respuestas:

9

Como está utilizando R, es posible que desee consultar el paquete stringdist y la métrica de distancia Jaro-Winkler que se puede usar en los cálculos. Esto fue desarrollado en la Oficina del Censo de los Estados Unidos para la vinculación.

Consulte para obtener más información sobre la distancia de Jaro y Jaro-Winkler en este diario .

Para una comparación de diferentes técnicas de emparejamiento, lea este documento

phiver
fuente
4

Hay muchas formas inteligentes de extender la distancia de Levenshtein para obtener una imagen más completa. Una breve introducción a un módulo bastante útil (para Python) llamado ' Fuzzy Wuzzy ' está aquí por el equipo de SeatGeek.

Un par de cosas que puede hacer es la similitud parcial de cadenas (si tiene cadenas de longitud diferente, digamos m & n con m <n), entonces solo coincide con m caracteres. También puede separar la cadena en tokens (palabras individuales) y ver cómo los conjuntos de tokens coinciden u organizarlos alfabéticamente y ordenarlos.

dmb
fuente
4

Otra técnica popular para detectar coincidencias parciales de cadenas (aunque generalmente en el nivel de documento) es el shingling . En esencia, es un enfoque de ventana móvil que extrae un conjunto de n-gramos para la palabra / documento objetivo y los compara con los conjuntos de n-gramos para otras palabras / documentos a través del coeficiente Jaccard . Manning y colegas (2008) discuten casi duplicados y herpes zóster en el contexto de la recuperación de información.

Brandon Loudermilk
fuente
4

He escrito un matizador difuso probabalístico genérico en Python que hará un trabajo razonable al hacer coincidir cualquier tipo de datos:

https://github.com/robinl/fuzzymatcher

Está en la memoria, por lo que probablemente no desee usarlo para hacer coincidir conjuntos de datos que están por encima de aproximadamente 100k filas.

También he escrito un proyecto similar específico para las direcciones del Reino Unido, pero esto supone que tiene acceso a Addressbase Premium. Este no está en la memoria, por lo que se ha utilizado contra los 100m más o menos direcciones del Reino Unido. Mira aquí:

https://github.com/RobinL/AddressMatcher

Si desea que esto funcione rápidamente, recomendaría usar libpostal para normalizar sus direcciones y luego alimentarlas en mi fuzzymatcher genérico ( pip install fuzzymatcher).

Puede encontrar ejemplos de uso aquí .

RobinL
fuente
Hola Robin, estoy interesado en tu biblioteca AddressMatcher. ¿Tienes alguna documentación sobre cómo usarlo? Tengo este problema exacto: necesito hacer coincidir 1 conjunto de direcciones (desordenado) con otro (direcciones postales oficiales). Gracias
SCool
1
lamentablemente con el comparador de direcciones no es nada trivial y no tengo buena documentación. Lo principal que necesita es cargar addressbase premium, un producto comercial, en postgresql.
RobinL
Ok, gracias por responderme. Estoy trabajando con supongo que la versión irlandesa de Addressbase premium llamada Eircode que será incompatible. ¿Crees que fuzzy matcher estaría a la altura en la coincidencia de direcciones del entorno de producción? Solo quiero agregar códigos postales a las direcciones en mis datos que no los tienen, por ejemplo, buscar en la base de datos Eircode '1 Main Street, Some Town, County'y, si encuentro una coincidencia, recuperar el código postal.
SCool
1
fuzzy matcher: sí, definitivamente creo que vale la pena intentarlo. debería funcionar razonablemente bien para que una pequeña lista de direcciones se encuentre dentro de una gran lista de direcciones autorizadas (es decir, eircode) en una máquina robusta. Otra opción es el paquete fastlink en R
RobinL