Cálculo de la correlación de texto sensible al contexto

Question

Supongamos que deseo unir registros de direcciones (o nombres de personas o lo que sea) uno contra el otro para fusionar registros que muy probablemente se refieran a la misma dirección. Básicamente, supongo que me gustaría calcular algún tipo de correlación entre los valores de texto y fusionar los registros si este valor supera un determinado umbral.

Ejemplo: "West Lawnmower Drive 54 A" es probablemente lo mismo que "W. Lawn Mower Dr. 54A" pero diferente de "East Lawnmower Drive 54 A".

¿Cómo abordaría este problema? ¿Sería necesario tener algún tipo de diccionario basado en el contexto que sepa, en el caso de la dirección, que "W", "W"? y "Oeste" son lo mismo? ¿Qué hay de los errores ortográficos ("mover" en lugar de "cortacésped", etc.)?

Creo que este es un truco - tal vez hay algunos algoritmos conocidos por ahí?

Answer 1

Un buen línea de base, probablemente, uno práctico en términos de su relativamente alto coste computacional y lo más importante su producción de muchos falsos positivos, sería algoritmos genéricos distancia cadena como

• Edit distance (aka Levenshtein distancia)
• Ratcliff/Obershelp

Dependiendo del nivel de precisión requerido (que, por cierto, debe especificarse tanto en términos de su recall and precision, es decir, en general, expresando si es más importante que se pierda una correlación de identificar falsamente uno), un proceso de cosecha propia en base a [algunos de] los siguientes heurística e ideas podrían hacer el truco:

• tokenize la entrada, es decir, ver la entrada como una matriz de palabras en lugar de una cadena
• tokenización también debe mantener la información de número de línea
• normalizar la entrada con el uso de un diccionario breve de substituions comunes (por ejemplo, "dr" al final de una línea = "unidad", "Jack" = "John", "Bill" = "William" ..., "W." al comienzo de una línea es "Oeste", etc.
• Identificar (un poco como el etiquetado, como en el etiquetado POS) la naturaleza de algunas entidades (por ejemplo, código postal y código postal ampliado, y también ciudad
• Identificar (buscar) algunas de estas entidades (por ejemplo, una tabla de base de datos relativamente corta puede incluir todas las ciudades/población en el área de destino
• Identificar (buscar) algunas entidades relacionadas con el dominio (si todas/muchas de las direcciones tienen que ver con gente de la profesión legal, una búsqueda) de nombres de firmas de abogados o de edificios federales pueden ser de ayuda.
• En general, ponga más peso en los tokens que provienen de la última línea de la dirección
• Ponga más (o menos) peso en tokens con un tipo de entidad particular (por ejemplo: "Drive", "Street", "Court" debe con mucho menos que las fichas que los preceden.
• Considere un SOUNDEX algoritmo modificado para ayudar con la normalización de

con lo anterior en mente, implementar un evaluador basado en reglas. provisionalmente, la las reglas podrían implementarse como visitantes de un árbol/ar estructura de tipo rayo donde la entrada se analiza inicialmente (Visitor design pattern).
La ventaja del marco basado en reglas es que cada heurística tiene su propia función y las reglas se pueden priorizar, es decir, colocar algunas reglas al principio de la cadena, lo que permite abortar la evaluación anticipadamente, con algunas heurísticas fuertes (por ejemplo: diferente Ciudad => Correlación = 0, nivel de confianza = 95%, etc. ...).

Una consideración importante con la búsqueda de correlaciones es la necesidad de a priori comparar cada artículo (en este caso frente) con todos los demás elementos, por lo que requieren un máximo de 1/2 n^2 comparaciones a nivel de artículo. Debido a esto, puede ser útil almacenar los elementos de referencia de una manera en la que estén preprocesados ​​(analizados, normalizados ...) y también para tener un compendio/clave del tipo que pueda usarse como [muy rough] indicador de una posible correlación (por ejemplo, una clave hecha con el código postal de 5 dígitos seguido por el valor SOUNDEX del nombre "principal").

Answer 2

Descargo de responsabilidad: No conozco ningún algoritmo que haga eso, pero realmente estaría interesado en conocer uno, si existe. Esta respuesta es un ingenuo intento de tratar de resolver el problema, sin conocimiento previo alguno. Comentarios bienvenidos, por favor no te rías también.

Si intenta hacerlo a mano, sugiero aplicar algún tipo de "normalización" a sus cadenas: minúsculas, eliminar la puntuación, tal vez reemplazar abreviaturas comunes con las palabras completas (Dr. => unidad, St = > calle, etc ...).

A continuación, puede probar diferentes alineaciones entre las dos cadenas que comparar, y calcular la correlación promediando las diferencias absolutas entre letras correspondientes (por ejemplo, a = 1, b = 2, etc .. y corr(a, b) = |a - b| = 1):

west lawnmover drive 
    w lawnmower street 

Por lo tanto, incluso si algunas letras son diferentes, la correlación sería alta. Luego, simplemente mantenga la correlación máxima que encontró y decida que son iguales si la correlación está por encima de un umbral determinado.

Answer 3

Me gustaría producir una medida de comparación de similitud que, dados dos objetos (cadenas tal vez), devuelve "distancia" entre ellos.

Si cumples con los siguientes criterios entonces ayuda:

1. distancia entre un objeto y sí es cero. (Reflexivo)
2. distancia de A a B es la misma en ambas direcciones (transitivo)
3. distancia de A a C no es más que la distancia de A a B, más distancia de A a C. (Triángulo regla)

Si su métrica obedece a éstos que se puede organizar sus objetos en el espacio métrico que significa que puede funcionar con preguntas como:

• Qué otro objeto más se parece a éste
• Dame los 5 objetos más como este.

Hay un buen libro al respecto here. Una vez que haya configurado la infraestructura para el alojamiento de objetos y la ejecución de consultas, simplemente puede conectar diferentes algoritmos de comparación, comparar su rendimiento y luego ajustarlos.

Hice esto para datos geográficos en la universidad y fue bastante divertido tratar de ajustar los algoritmos de comparación.

Estoy seguro de que podrías encontrar algo más avanzado pero podrías comenzar con algo simple como reducir la línea de dirección a los dígitos y la primera letra de cada palabra y luego comparar el resultado de eso usando una subsecuencia común más larga algoritmo.

Espero que ayude de alguna manera.

Answer 4

Puede usar Levenshtein edit distance para buscar cadenas que difieren en unos pocos caracteres. BK Trees puede ayudar a acelerar el proceso de coincidencia.

Answer 5

Cuando tuve que modificar un programa propietario haciendo esto, a principios de los años 90, tomó muchos miles de líneas de código en múltiples módulos, construidos a lo largo de años de experiencia. Las técnicas modernas de aprendizaje automático deberían facilitarlo, y tal vez no necesite desempeñarse tan bien (era el pan y la mantequilla de mi empleador).

Así que si estás hablando de fusionar listas de direcciones postales reales, lo haría subcontratando si puedo.

El USPS tenía algunas pruebas para medir la calidad de los programas de estandarización de direcciones. No recuerdo nada sobre cómo funcionó, pero es posible que compruebes si todavía lo hacen; tal vez puedas obtener buenos datos de entrenamiento.