algorithm - resident - ¿Cómo hago para construir un algoritmo coincidente?

maximum bipartite matching

Question

Nunca he creado un algoritmo para hacer coincidencias antes y realmente no sé por dónde empezar. Así que aquí está mi configuración básica y por qué lo estoy haciendo. Siéntase libre de corregirme si no estoy haciendo las preguntas correctas.

Tengo una base de datos de nombres e identificadores únicos para personas. Varios identificadores generados (generados internamente y algunos terceros), apellido, nombre y fecha de nacimiento son los principales que usaría.

Varias veces a lo largo del año recibo una lista de un tercero que necesita ser importada y vinculada a las personas existentes en mi base de datos, pero los datos nunca son tan limpios como los míos. Las identificaciones pueden cambiar, las fechas de nacimiento pueden tener errores tipográficos, los nombres pueden tener errores tipográficos, los apellidos pueden cambiar, etc.

Cada importación podría tener 20,000 registros, por lo que incluso si es 99% precisa, aún son 200 registros que tendría que ingresar manualmente y coincidir. Creo que estoy buscando más del 99.9% de precisión cuando se trata de hacer coincidir las personas entrantes con mis usuarios.

Entonces, ¿cómo hago para hacer un algoritmo que pueda resolver esto?

PD: incluso si no tiene una respuesta exacta pero si conoce algunos materiales de referencia, también sería útil.

PPS Algunos ejemplos serían similares a lo que m3rLinEz escribió:

ID: 9876234 Fname: Jose     LName: Guitierrez       Birthdate:01/20/84  ''- Original''

ID: 9876234 Fname: Jose     LName: Guitierrez       Birthdate:10/20/84  ''- Typo in birth date''
ID: 0876234 Fname: Jose     LName: Guitierrez       Birthdate:01/20/84  ''- Wrong ID''
ID: 9876234 Fname: Jose     LName: Guitierrez-Brown Birthdate:01/20/84  ''- Hyphenated last name''
ID: 9876234 Fname: Jose, A. LName: Guitierrez       Birthdate:01/20/84  ''- Added middle initial''
ID: 3453555 Fname: Joseph   LName: Guitierrez       Birthdate:01/20/84  ''- Probably someone else with same birthdate and same last name''

Answer 1

Cuando se trata de algo como esto, no reinvente la rueda. La distancia Levehstein es probablemente su mejor apuesta si TIENE QUE hacer esto usted mismo, pero por lo demás, haga una investigación sobre las soluciones existentes que hacen consultas de bases de datos y búsquedas difusas. Lo han estado haciendo más tiempo que tú, probablemente también será mejor ...

¡Buena suerte!

Answer 2

Las expresiones regulares son lo que necesitas, ¿por qué reinventar la rueda?

Answer 3

Si está tratando con conjuntos de datos de este tamaño y diferentes recursos que se importan, es posible que desee buscar en una solución de administración de identidad. En general, estoy familiarizado con Sun Identity Manager, pero puede ser una exageración por lo que estás tratando de hacer. Podría valer la pena mirar.

Answer 4

Si los datos que está obteniendo de terceros son consistentes (el mismo formato cada vez), probablemente crearía una tabla para cada uno de los terceros de los que recibe datos. Luego importe cada nuevo conjunto de datos a la misma tabla cada vez. Sé que hay una manera de unir las dos tablas basadas en columnas comunes en cada una usando una declaración SQL. De esa manera, puede realizar consultas SQL y obtener datos de varias tablas, pero hacer que parezca que proviene de una sola tabla unificada. De manera similar, los registros que se agregaron y que no tienen coincidencias en ambas tablas se pueden encontrar y luego se pueden emparejar manualmente. De esta manera, mantendrá sus datos "limpios" separados de la basura que recibe de terceros. Si desea una verdadera importación, puede utilizar esa tabla unida para crear una tercera tabla que contenga todos sus datos.

Answer 5

Usted podría estar interesado en la distancia Levenshtein .

La distancia de Levenshtein entre dos cadenas se define como el número mínimo de ediciones necesarias para transformar una cadena en otra, con las operaciones de edición permitidas que son la inserción, eliminación o sustitución de un solo carácter. Lleva el nombre de Vladimir Levenshtein, quien consideró esta distancia en 1965. 1

Es posible comparar cada uno de sus campos y calcular la distancia total. Y, por prueba y error, puede descubrir el umbral apropiado para permitir que los registros se interpreten como coincidentes. No lo he implementado yo solo, pero solo pensé en la idea:}

Por ejemplo:

• Registro A - ID: 4831213321, Nombre: Jane
• Registro B - ID: 431213321, Nombre: Jann
• Registro C - ID: 4831211021, Nombre: John

La distancia entre A y B será más baja que A y C / B y C, lo que indica una mejor coincidencia.

Answer 6

Yo empezaría con el 100% fácil de ciertas coincidencias y las manejaría primero, así que ahora tiene una lista de, digamos, 200 que deben solucionarse.

Para las filas restantes puede usar una versión simplificada del Teorema de Bayes .

Para cada fila no coincidente, calcule la probabilidad de que sea una coincidencia para cada fila en su conjunto de datos, suponiendo que los datos contienen ciertos cambios que ocurren con ciertas probabilidades. Por ejemplo, una persona cambia su apellido con probabilidad 0.1% (posiblemente también depende del género), cambia su nombre con probabilidad 0.01%, y tiene un solo error tipográfico con probabilidad 0.2% (use la distancia de Levenshtein para contar el número de errores) ). Otros campos también cambian con ciertas probabilidades. Para cada fila, calcule la probabilidad de que la fila coincida considerando todos los campos que han cambiado. Luego, elija el que tenga la mayor probabilidad de ser una coincidencia.

Por ejemplo, una fila con solo un pequeño error tipográfico en un campo pero igual en todos los demás tendría un 0,2% de probabilidad de una coincidencia, mientras que las filas que difieren en muchos campos podrían tener solo un 0,0000001% de probabilidad. Así que escoges la fila con el pequeño error tipográfico.