algorithm - una - extraer valores repetidos en excel
¿Cómo detectar datos duplicados? (10)
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 iguales. 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?
Esto puede estar relacionado o no, pero se pueden detectar faltas de ortografía menores mediante una búsqueda de Soundex , por ejemplo, esto le permitirá considerar a Britney Spears, Britanny Spares y Britny Spears como duplicados.
Las contracciones de los apodos, 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á considerando, digamos, usuarios musulmanes, los problemas se vuelven más difíciles (hay demasiados musulmanes, por ejemplo, que se llaman Mohammed / Mohammad).
Me imagino que este problema se comprende bien, pero lo que se me ocurre en la primera lectura es:
- comparar campos individualmente
- cuente los que coincidan (para una definición de coincidencia posiblemente suelta, y posiblemente ponderando los campos de forma diferente)
- presente para la intervención humana en los casos que superan cierto umbral
Use su base de datos existente para obtener una buena primera estimación del umbral y corrija a medida que acumula experiencia.
Es posible que prefiera un sesgo bastante fuerte hacia los falsos positivos, al menos al principio.
No estoy seguro de que funcione bien para el problema de nombres contra apodos, pero el algoritmo más común en este tipo de área sería el algoritmo de distancia de edición / distancia de Levenshtein . Básicamente es un recuento de la cantidad de cambios de carácter, adiciones y eliminaciones necesarias para convertir un elemento en otro.
En cuanto a 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 analizar qué consultas conducen entre sí, a qué se refería con "hacer clic" en los enlaces, etc.
Hay algunas compañías que se especializan en el problema de emparejamiento de nombres (principalmente para aplicaciones de seguridad nacional y fraude). Lo único que recuerdo es que Search Software America parece haber sido comprado por estos tipos http://www.informatica.com/products_services/identity_resolution/Pages/index.aspx , pero sospecho que cualquiera de estos tipos de soluciones estaría lejos. a caro para una aplicación de contactos.
Puedes comparar los nombres con la distancia de Levenshtein . 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.
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 , puede sugerir contactos que ya existen en la nueva pantalla de contacto.
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
Si tiene una base de datos grande con campos de cadena, puede encontrar rápidamente muchos duplicados utilizando el algoritmo simhash .
Entonces, ¿hay algún tipo de algoritmo que pueda dar un porcentaje de qué tan similar es una entrada a otra?
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.
A su tabla de direcciones habitual, agregue versiones raíz de los nombres, p. Ej. Persona (Nombre, Apellido Nombre, Apellido, Nombre raíz ...)
Ahora, crea una tabla de mapeo. FirstNameMappings (Primary KEY Firstname, Rootname)
Complete su tabla de Mapeo de la siguiente manera: Inserte IGNORE (seleccione Nombre, "INDEFINIDO" de Persona) en FirstNameMappings
Esto agregará todos los primeros nombres que tenga en su tabla de personas junto con el RootName de "INDEFINIDO"
Ahora, lamentablemente, tendrá que revisar todos los 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 recientemente 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.
Es posible que también desee buscar una coincidencia probabilística.
FullContact.com tiene API que puede resolver esto por usted, consulte su documentación aquí: http://www.fullcontact.com/developer/docs/?category=name .
Tienen API para Normalización de nombre (Bill into William), Name Deducer (para texto sin formato) y Name Shaped (comparando dos nombres).
Todas las API son gratuitas en este momento, podría ser una buena forma de comenzar.