Automatización de la detección de duplicados en nuestras bases de datos

Las complejas aplicaciones actuales de extracción de conocimientos y minería de datos utilizan datos heterogéneos y distribuidos. En este contexto, la calidad de cualquier decisión depende de la calidad de los datos utilizados. De hecho, con la falta de datos precisos y fiables, se pueden tomar malas decisiones. Por ello, es necesario conocer mejor el origen de los datos que se pueden utilizar, es necesario, o incluso imprescindible, depurar los datos redundantes o muy similares mediante su representación semántica. Por otro lado, los problemas de calidad de los datos surgen a menudo con el aumento constante de la cantidad de datos. La calidad de los datos almacenados en las bases de datos reales estará garantizada por el vital proceso de limpieza de datos. Varios ámbitos de investigación, como el descubrimiento de conocimientos en bases de datos, el almacenamiento de datos, la integración de sistemas y los servicios electrónicos, se enfrentan a menudo a problemas de limpieza de datos.

Es necesario depurar los datos muy similares utilizando su representación semántica

La investigación sobre la identificación de duplicados está presente desde hace décadas y, a pesar de ello, el problema sigue apareciendo en muchas aplicaciones. Se reduce al hecho de que cada base de datos tiene sus propias características y su dominio específico. La detección de duplicados es una parte integral de la limpieza de datos y se utiliza para identificar diferentes representaciones de las mismas entidades del mundo real en varios conjuntos de datos que pueden ser relacionales. La limpieza de datos es un proceso multivariable que identifica y soluciona varios problemas para diferentes conjuntos de datos.

Los duplicados especificados con diferentes representaciones se encuentran entre los problemas más perjudiciales para tratarlos manualmente. Resulta que la detección de duplicados para el tratamiento de los datos procedentes de diferentes fuentes es un problema que se repite a menudo. Por lo tanto, esta detección desempeña un papel importante en el proceso de limpieza de datos. El problema en sentido amplio se ha estudiado con diferentes nombres, como la resolución de entidades, el acoplamiento de registros o la detección de duplicados.

En la práctica, la detección de duplicados es esencial para una mejor gestión de los datos. Por ejemplo, un doble registro en una solicitud determinada para una misma persona o múltiples registros de personas que se refieren a la misma persona. Para ello, nos gustaría adjuntar a los datos sus tipos, restricciones, incluso huellas dactilares, y comentarios para una mejor interpretación y reutilización de los datos (sin duplicados y con buena calidad).

El estado del arte es rico en términos de algoritmos de deduplicación, así como en las técnicas que componen este proceso. Desde la aparición de las primeras pruebas del principio de detección de duplicados, se han propuesto varios enfoques con algunas variaciones a nivel de los pasos dados para realizar esta tarea. Ya se han propuesto varias técnicas de deduplicación, entre ellas

  • Técnicas que clasificación por atributos y arrastrar una ventana para comparar registros adyacentes en esta ventana
  • Las técnicas que se basan en indexación antes de comparar los registros por sus llaves
  • Técnicas que utilizar el bloqueo para agrupar registros potencialmente similares en bloques antes de proceder a la comparación para remediar la alta complejidad de comparar todos los registros

En cuanto al término de comparación, algunos enfoques comparan todos los valores de los atributos de dos registros como una sola cadena. En cambio, otros pasan por la comparación de cada valor de atributo entre dos registros.

Tras medir las similitudes o las distancias entre los registros, ¿cómo podemos juzgar que dos registros representan o no la misma entidad del mundo real?

Para alcanzar este objetivo, nuestra metodología consiste en aplicar técnicas de aprendizaje automático y medidas de similitud con poca supervisión posible. De hecho, tenemos previsto recurrir a expertos para que anoten los pares de registros como duplicados o no. Esto nos permite validar la automatización de nuestro enfoque y establecer umbrales para juzgar los pares de registros.

Metodología

Para todas las aplicaciones Berger-Levrault que tienen el problema de los registros duplicados, proponemos el siguiente enfoque:

Este enfoque se basa en el preprocesamiento, la indexación y el bloqueo de los datos para su comparación y clasificación. Comienza con un paso de preprocesamiento para entender la semántica de los datos, que falta en la mayoría de los enfoques del estado de la técnica. Este paso permite reconocer:

  1. Tipos de columnas (cadena, entero, fechaetc.) si no se dan
  2. Sus conceptos (persona, correo electrónico, género, dirección, paísetc.)

Es evidente que en un primer momento no podemos abarcar todos los conceptos posibles del mundo real, pero al menos los que aparecen con más frecuencia en nuestras bases de datos. Tenemos previsto alimentar la lista de conceptos, es decir, el sistema será configurable y se adaptará en función del ámbito de aplicación.

En estas dos fases se seleccionarán los atributos (columnas) relevantes para comparar dos registros, ya que no todos los atributos pueden ser necesarios para diferenciar dos registros. A continuación, se elige la medida adecuada para cada atributo, ya que el enfoque que intentamos conseguir al final debe ser genérico e independiente con una adaptación a la aplicación del dominio.

Como ejemplo, la siguiente tabla muestra algunos registros con los posibles duplicados:

ApellidoNombreDirecciónPaísProyectoAño
R. DukesAna4188 My Drive Garden City, Nueva York 11530EE.UU.Dedup2019
P. BeckerTimothy1148 Columbia Mine Road Charleston, WV 25301EE.UU.Elige2019
P. BekerTimotty3388 Farland Avenue Marion, TX 78124EE.UU.F. D2019
R. DukesAnastasia4188 My Drive Garden City, NY 11530EE.UU.Elige2020

Siguiendo los pasos que hemos mencionado antes, tomando el ejemplo de los datos presentes en la tabla anterior, nuestro algoritmo identificará las columnas como cadena excepto el año de la columna que se identificará como entero...nada es mágico hasta ahora.

Los conceptos de las columnas están claros en la tabla, ya que el algoritmo los identificará. Intuitivamente, se considerarán todas las columnas excepto el país, ya que contiene el mismo valor para todos los registros de este ejemplo. Para simplificar y no llevarnos demasiado al cálculo matemático, utilizamos aquí medidas teniendo en cuenta las cadenas de caracteres (para Apellido, Nombre, Dirección, y Proyecto) y las medidas propias de los números enteros (para el Año).

Entonces, empezamos a generar llaves artificiales a partir de los valores de los registros en los atributos seleccionados, según reglas específicas (número de n caracteres para cada valor). Por ejemplo, si tomamos 2 caracteres de cada valor del registro, las claves serán respectivamente r.an41de20, p.ti11el20, p.ti33f.20y r.an41el20. Aquí damos el ejemplo de 4 registros, pero esto se hará para todos los registros posibles (ya que el tema se aplica a datos enormes). La fase de agrupación/bloqueo comienza con la agrupación de registros similares por sus claves en clusters. Si dos claves son similares según Distancia Levenshtein (que mide la diferencia entre dos cadenas. Es igual al número mínimo de caracteres que hay que eliminar, insertar o sustituir para pasar de una cadena a la otra), sus registros se pondrán en el mismo clúster. Para nuestro ejemplo (tabla anterior), sea cual sea el umbral de distancia que tengamos que utilizar, los registros 1 y 4 estarán en el mismo clúster.

Para el siguiente paso, podemos tener clusters con un número diferente de registros sin tener que elegir el número de clusters de antemano. A continuación, se realiza una comparación intraclúster de cada dos registros (candidatos) para cada atributo mediante una medida específica. La idea de utilizar el clustering es reducir el campo de comparación de los registros a sólo aquellos que son potencialmente similares y eliminar otros que no están cerca de ningún otro.
Al final, los resultados que obtengamos para cada clúster se pasarán a un clasificador supervisado para reforzar la validación de los duplicados.

Resultados y rendimientos

Después de haber visto las diferentes etapas del proceso de detección de duplicados, debemos ver algunos resultados de la aplicación. Tomamos como datos, el ejemplo de BL-España que contiene duplicados de contribuyentes, ya que alimentan la nueva base desde diferentes fuentes. Para un segundo ejemplo, tomamos una base de datos utilizada por los sistemas más avanzados de detección de duplicados. Se trata de los restaurantes de Estados Unidos.

Caso práctico 1: Base de datos WinGT

Para este primer caso, ejecutamos nuestro programa en la base de datos de España. Para obtener los primeros resultados, tomamos sólo 20.000 registros aunque este conjunto de datos contiene aproximadamente 300.000, debido al tiempo de cálculo. Limitaremos las medidas de rendimiento al número de duplicados detectados, ya que en esta etapa necesitamos anotaciones manuales y la evaluación de expertos para esta base de datos.

 Como se ilustra en la figura anterior, nuestro sistema fue capaz de extraer 39 pares de duplicados basándose en los tres atributos considerados relevantes. A continuación, los resultados de diferentes formas de detectar duplicados, basados en los atributos seleccionados con una comparación de nuestro enfoque.

Habrás notado que no hay resultados para nuestro enfoque en los últimos 4 casos. Esto se debe a que lo hemos aplicado sólo a estos tamaños de datos. Creemos que, después de la aplicación en el resto de los tamaños de datos, explotará con los duplicados.

Caso práctico 2: Conjunto de datos de restaurantes

Para este segundo caso, probamos diferentes pruebas antes y después de la selección de atributos con diferentes elecciones de medidas y umbrales. La figura anterior presenta la etapa de selección de atributos relevantes que se toman todos excepto Tipo. Después, la fase de detección de duplicados se realiza agrupando los restaurantes potencialmente duplicados en el mismo clúster.

Los resultados se muestran en las dos tablas siguientes (con el tratamiento de todos los atributos o sólo de los seleccionados, respectivamente).

MedidaUmbralDuplicados detectados
Levenshtein1/4 de la cadena más corta31
Levenshtein1/6 de la cadena más corta21
Levenshtein1/8 de la cadena más corta15
Jaro-winkler0.667
Jaro-winkler0.840
Media36
MedidaUmbralDuplicados detectados
Levenshtein1/4 de la cadena más corta64
Levenshtein1/6 de la cadena más corta61
Levenshtein1/8 de la cadena más corta38
Jaro-winkler0.697
Jaro-winkler0.886
Media69

La primera tabla presenta los resultados de la detección de duplicados utilizando todos los atributos en términos de comparación de dos registros, con diferentes medidas cada vez (la misma medida utilizada para todos los atributos). El número medio de duplicados detectados es de 36. Mientras que en la segunda, tras la selección de atributos relevantes, el número medio de duplicados detectados es de 69.

Como se ve en las dos tablas, en general los resultados cambian según las medidas y la elección de los umbrales. Tenemos previsto continuar este trabajo comparando nuestros resultados con las anotaciones de los expertos. Esto nos ayudará a automatizar los umbrales.

Más ...

Ir arriba