Coincidencia difusa de datos estructurados

Question

Tengo un corpus bastante pequeño de registros estructurados en una base de datos.Dada una pequeña fracción de la información contenida en un solo registro, enviada a través de un formulario web (estructurado de la misma manera que el esquema de tabla), (llamémoslo registro de prueba), necesito elaborar rápidamente una lista de los registros que son las coincidencias más probables para el registro de prueba, además de proporcionar una estimación de confianza de qué tan estrechamente coinciden los términos de búsqueda con un registro.El objetivo principal de esta búsqueda es descubrir si alguien está intentando ingresar un registro que esté duplicado en uno del corpus.Existe una posibilidad razonable de que el registro de la prueba sea un engaño, y una posibilidad razonable de que el registro de la prueba no sea un engaño.

Los registros tienen aproximadamente 12.000 bytes de ancho y el recuento total de registros es de aproximadamente 150.000.Hay 110 columnas en el esquema de la tabla y el 95% de las búsquedas se realizarán en el 5% de las columnas más buscadas.

Los datos son cosas como nombres, direcciones, números de teléfono y otros números específicos de la industria.Tanto en el corpus como en el registro de prueba se ingresa a mano y está semiestructurado dentro de un campo individual.Al principio podrías sonrojarte decir "pesar las columnas a mano y hacer coincidir las fichas de palabras dentro de ellas", pero no es tan fácil.Yo también pensé lo mismo:Si obtengo un número de teléfono, pensé que indicaría una combinación perfecta.El problema es que no hay un solo campo en el formulario cuya frecuencia de token no varíe en órdenes de magnitud.Un número de teléfono puede aparecer 100 veces en el corpus o 1 vez en el corpus.Lo mismo ocurre con cualquier otro campo.Esto hace que la ponderación a nivel de campo sea poco práctica.Necesito un enfoque más detallado para lograr una coincidencia decente.

Mi plan inicial era crear un hash de hashes, siendo el nivel superior el nombre del campo.Luego, seleccionaría toda la información del corpus para un campo determinado, intentaría limpiar los datos contenidos en él y tokenizaría los datos desinfectados, aplicando hash a los tokens en el segundo nivel, con los tokens como claves y la frecuencia como valor.

Usaría el recuento de frecuencia como peso:cuanto mayor es la frecuencia de un token en el corpus de referencia, menos peso le doy a ese token si se encuentra en el registro de prueba.

Mi primera pregunta es para los estadísticos presentes en la sala:¿Cómo usaría la frecuencia como peso?¿Existe una relación matemática precisa entre n, el número de registros, f(t), la frecuencia con la que apareció un token t en el corpus, la probabilidad o de que un registro sea original y no un duplicado, y la probabilidad p de que ¿El registro de prueba es realmente un registro x dada la prueba y x contiene la misma t en el mismo campo?¿Qué tal la relación para múltiples coincidencias de tokens en múltiples campos?

Ya que dudo sinceramente que lo haya, ¿hay algo que me acerque pero que sea mejor que un truco completamente arbitrario lleno de factores mágicos?

Aparte de eso, ¿alguien tiene alguna manera de hacer esto?

Me interesan especialmente otras sugerencias que no implican mantener otra tabla en la base de datos, como una tabla de búsqueda de frecuencia de tokens.

Answer 1

Puede probablemente obtener algunas ideas de esta diferente pero similar SO pregunta: sensible de texto correlación cálculo de contexto.?

Más específico para el problema en cuestión, aquí hay algunos pensamientos e ideas:

En primer lugar, reconociendo el uso muy sesgada (sólo 6 a 10 atributos cubren el 95% del uso), se puede / debe aplicar esfuerzo asimétrica en los atributos, es decir, invertir más, tanto en términos de tiempo de programación y en el plazo de en tiempo de ejecución de la CPU asignación, para hacer frente a estos pocos atributos que para los atributos adicionales 100 y pico.

La cantidad relativamente pequeña de datos suministrados como entrada para emparejar posibles duplicados en la base de datos, el conjunto relativamente pequeño de atributos suele utilizar, y la semántica aparentemente comunes de éstos (número de teléfono, dirección, nombre ...) sugieren una mano -crafted solución en lugar de un completamente sobre la base de la máquina de aprendizaje.

Nota: muchas de las sugerencias que a partir de entonces no necesitan ser aplicados a todos los atributos (ya menos de una docena de éstos cubren prácticamente todo el uso, no tiene sentido, al menos en principio invertir mucho con los otros atributos .

• normalizar los datos
  Si no se permite para que usted pueda modificar los valores de los campos originales puede que duplican las columnas correspondientes a un coluumn "norm_xxx" donde xxx es el nombre original.
  ¿Qué, Cómo normalizar puede variar con cada atributo; de "texto libre", como los datos, asegúrese de que no hay espacios iniciales ni de fuga, sólo un espacio entre palabras, sin pestañas y caracteres no imprimibles. Utilice ya sea en mayúsculas o minúsculas (eventhought el texto original / para-pantalla puede incluir una mezcla, su procesamiento irá más rápido al ser capaces de asumir la carcasa uniforme). Más específicamente para las direcciones y / o nombres de empresas, puede convertir los términos comunes a una forma estándar (ST para la calle, ST y ST, etc.) (Asegúrese de mantener esta lista para ello se aplicará a los criterios de búsqueda del usuario así ). Parte de la normalización también puede ser a caer del todo algunas palabras irrelevantes (como decir CO, INC, GMBH a finales de los nombres de empresas)
• Crea unos columnas calculadas
  Por ejemplo, los que tienen el texto, a la inversa, para los atributos que pueden ser buscado con un comodín trailing
• Considere el uso de una conversión Soundex similar para algunos atributos.
• índice de texto completo, de forma individual, toda la columna de texto como
• Crear índices de fricción (SQL) en todas las columnas 6 a 10 más utilizados

Todas las preparaciones, son meros tiempo fuera de línea por encima de los partidos de realizar realmente. Ahora .. el usuario introduce su / su consulta ... aquí están algunas ideas sobre cómo tratar con él

• Normalizar los criterios de búsqueda que lo justifiquen
• Ejecutar varias búsquedas ...
  Esto es un poco complicado; hay varios, en parte contradictorios, objetivos para la realización de estos búsqueda. Queremos reducir, de manera significativa el número de "posibles coincidencias": es efectivamente poco prácticos para hacer un total de uno-a-uno que comparaba de todos los 150.000 registros con los criterios suministrados por el usuario; por ejemplo, parte de la lógica de adaptación puede implicar el cálculo de la distancia de edición entre un campo de un registro dado de la base de datos y un criterio de búsqueda. También queremos asegurarnos de que no excluimos los registros de la lista de "posibles coincidencias" debido a un error tipográfico en el nombre de la compañía digamos ... Finalmente queremos ofrecer la lista de posibles coincidencias de forma igualada.
  La manera de realizar estas búsquedas sigue algunas heurísticas predefinidos (I encontraron que la estrategia funcione patrón de diseño bien para eso, lo que permite flexibilidad en la forma en que la búsqueda se ejecuta, dependiendo de la entrada proporcionada por el usuario). En pocas palabras que buscar las palabras más selectivos en los atributos más selectivos / pertinentes, y con base en el número de "éxitos" descubrimos que sea "O" (unión) o "Y" con otros resultados de la búsqueda, hasta que tengamos unos pocos cientos de registros.
• Calcular un valor de similitud entre cada atributo de los registros de los partidos "potenciales" y los correspondientes criterios de búsqueda. Posiblemente aplicar un coeficiente a este valor (lo que permite poner más pesan decir un nombre de la empresa [parcial] coincida con el de un partido de la ciudad)
• Tally el valor de similitud de eficacia general de un registro completo (frente a los criterios de búsqueda completas)

• Mostrar los registros superior a un umbral particular del valor de similitud con el usuario final, para su revisión

  Finalmente, y llega un proceso parcialmente automatizada, puede modificar algunos de los parámetros basándose en alguna información suministrada por el usuario final. (Esto es muy difícil de hacer, voy a seguir esto por algún otro post ;-))