¿Cómo detectar datos duplicados?

Question

Tengo una base de datos de contactos simple pero estoy teniendo problemas con los usuarios que ingresan datos duplicados. Implementé una comparación de datos simple, pero lamentablemente los datos duplicados que se ingresan no son exactamente los mismos. Por ejemplo, los nombres están incorrectamente deletreados o una persona ingresará 'Bill Smith' y otro colocará 'William Smith' para la misma persona.

Entonces, ¿hay algún tipo de algoritmo que pueda dar un porcentaje de qué tan similar es una entrada a otra?

Answer 1

Si bien no tengo un algoritmo para ti, mi primera acción sería echar un vistazo al proceso involucrado al ingresar a un nuevo contacto. Tal vez los usuarios no tienen una manera fácil de encontrar el contacto que están buscando. Al igual que en el nuevo formulario de preguntas de Stack Overflow, puede sugerir contactos que ya existen en la nueva pantalla de contacto.

Answer 2

me imagino que este problema se entiende bien, pero lo que ocurre a mí en primera lectura es:

• comparar campos individualmente
• cuentan los que coinciden (para una definición posiblemente suelto de partido, y, posiblemente, con un peso los campos de manera diferente)
• presente de intervención humana cualquier caso que pasan algún umbral

Utilice su base de datos existente para conseguir una buena primera aproximación para el umbral, y corrige a medida que acumulas experiencia.

Puede preferir un sesgo bastante fuerte hacia los falsos positivos, al menos al principio.

Answer 3

Puede comparar los nombres con Levenshtein distance. Si los nombres son los mismos, la distancia es 0, sino que viene dada por el número mínimo de operaciones necesarias para transformar una cadena en la otra.

Answer 4

Esto puede o no estar relacionado, pero los errores ortográficos menores pueden detectarse por Soundex search, por ejemplo, esto le permitirá considerar a Britney Spears, Britanny Spares y Britny Spears como duplicados.

Las contracciones de los alias, sin embargo, son difíciles de considerar como duplicados y dudo si es acertado. Seguramente habrá varias personas llamadas Bill Smith y William Smith, y tendrías que repetir eso con Charles-> Chuck, Robert-> Bob, etc.

Además, si estás considerando, digamos, usuarios musulmanes, los problemas se vuelven más difíciles (hay demasiados musulmanes, por ejemplo, que se llaman Mohammed/Mohammad).

Answer 5

Si tiene acceso a SSIS, consulte la agrupación Fuzzy y la transformación de búsqueda difusa.

http://www.sqlteam.com/article/using-fuzzy-lookup-transformations-in-sql-server-integration-services

http://msdn.microsoft.com/en-us/library/ms137786.aspx

Answer 6

no estoy seguro de que va a funcionar bien para los nombres vs problema apodos, pero el algoritmo más común en este tipo de área sería el algoritmo edit distance/Levenshtein distance. Básicamente es un recuento de la cantidad de cambios de carácter, adiciones y eliminaciones necesarias para convertir un elemento en otro.

Para los nombres, no estoy seguro de que vayas a obtener buenos resultados con un enfoque puramente algorítmico: lo que realmente necesitas es una gran cantidad de datos.Tomemos, por ejemplo, las mejores sugerencias de ortografía de Google que las de una aplicación de escritorio normal. Esto se debe a que Google puede procesar miles de millones de consultas web y ver qué consultas se llevan entre sí, qué significa "enlaces realmente cliqueados".

Hay algunas compañías que se especializan en el problema de coincidencia de nombres (principalmente para aplicaciones de seguridad nacional y fraude). Lo que podría recordar, Search Software America parece haber sido comprado por estos chicos http://www.informatica.com/products_services/identity_resolution/Pages/index.aspx, pero sospecho que cualquiera de estos tipos de soluciones sería muy costoso para una aplicación de contactos.

Answer 7

Si tiene una base de datos grande con campos de cadena, puede encontrar muy rápidamente muchos duplicados utilizando el algoritmo simhash.

Answer 8

Entonces, ¿hay algún tipo de algoritmo de que puede dar un porcentaje de cómo similares es una entrada a otro?

Algoritmos como Soundex y distancias de edición (como se sugirió en una publicación anterior) pueden resolver algunos de sus problemas. Sin embargo, si realmente quiere limpiar sus datos, esto no será suficiente. Como otros han declarado "Bill", no suena como "William".

La mejor solución que he encontrado es usar un algoritmo de reducción y una tabla para reducir los nombres a su nombre de raíz.

Para la tabla de dirección regular, agregar-Raíces versiones de los nombres, por ejemplo Persona (Nombre, RootFirstName, Apellido, Rootsurname ....)

Ahora, cree una tabla de asignación. FirstNameMappings (clave principal Nombre, RootName)

pueblan su tabla de asignación por: INSERT IGNORE (SELECT Nombre, "indefinido" de la persona) en FirstNameMappings

Esto agregará todos firstnames que tiene en su mesa persona junto con el RootName de "indefinido"

Ahora, por desgracia, tendrá que pasar por todos los primeros nombres únicos y asignarlos a un RootName. Por ejemplo, "Bill", "Billl" y "Will" deberían traducirse a "William" Esto lleva mucho tiempo, pero si la calidad de los datos es realmente importante para usted, creo que es una de las mejores maneras.

Ahora use la tabla de asignación recién creada para actualizar el campo "Rootfirstname" en su tabla Person. Repita para el apellido y la dirección. Una vez hecho esto, debería poder detectar duplicados sin sufrir errores ortográficos.

Answer 9

Es posible que también quiera buscar una coincidencia probabilística.

Answer 10

FullContact.com tiene API que pueden resolver esto por usted, consulte su documentación aquí: http://www.fullcontact.com/developer/docs/?category=name.

Ellos tienen APIs para Nombre de Normalización (Bill en William), Nombre Deducer (para el texto en bruto), y el nombre de similitud (comparando dos nombres).

Todas las API son gratuitas en este momento, podría ser una buena manera de comenzar.