Automatiser la détection des doublons dans nos bases de données

Les applications complexes actuelles d'extraction de connaissances et de fouille de données utilisent des données hétérogènes et distribuées. Dans ce contexte, la qualité de toute décision dépend de la qualité des données utilisées. En effet, en l'absence de données précises et fiables, de mauvaises décisions peuvent être prises. Afin de fournir une meilleure compréhension de la source des données qui peuvent être utilisées, il est nécessaire, voire indispensable, de nettoyer les données redondantes/très similaires en utilisant leur représentation sémantique. D'autre part, les problèmes de qualité des données se posent souvent avec l'augmentation constante de la quantité de données. La qualité des données stockées dans des bases de données réelles sera assurée par le processus vital de nettoyage des données. Plusieurs domaines de recherche tels que la découverte de connaissances dans les bases de données, l'entreposage de données, l'intégration de systèmes et les services électroniques sont souvent confrontés à des problèmes de nettoyage de données.

Il est nécessaire de nettoyer des données très similaires en utilisant leur représentation sémantique.

La recherche sur l'identification des doublons est présente depuis des décennies et malgré cela, le problème apparaît toujours dans de nombreuses applications. Il s'explique par le fait que chaque base de données a ses propres caractéristiques et son domaine spécifique. La détection des doublons fait partie intégrante du nettoyage des données et est utilisée pour identifier les différentes représentations des mêmes entités du monde réel dans divers ensembles de données qui peuvent être relationnelles. Le nettoyage des données est un processus multivarié qui identifie et corrige divers problèmes pour différents ensembles de données.

Les doublons spécifiés avec des représentations différentes sont parmi les problèmes les plus nuisibles à traiter manuellement. Il s'avère que la détection des doublons pour le traitement de données provenant de sources différentes est un problème qui revient souvent. Par conséquent, cette détection joue un rôle important dans le processus de nettoyage des données. Le problème au sens large a été étudié sous différents noms tels que la résolution d'entités, le couplage d'enregistrements, ou la détection de doublons.

En pratique, la détection des doublons est essentielle pour une meilleure gestion des données. Par exemple, une double inscription dans une demande donnée pour une seule et même personne ou plusieurs enregistrements de personnes se référant à la même personne. Pour ce faire, nous souhaitons attacher aux données leurs types, leurs contraintes, voire leurs empreintes digitales, et des commentaires pour une meilleure interprétation et réutilisation des données (sans doublons et avec une bonne qualité).

L'état de l'art est riche en termes d'algorithmes de déduplication ainsi que des techniques composant ce processus. Depuis l'apparition des premiers tests du principe de détection des doublons, plusieurs approches ont été proposées avec quelques variations au niveau des étapes suivies pour accomplir cette tâche. Plusieurs techniques de déduplication ont été proposées auparavant, parmi lesquelles :

• Des techniques qui trier par attribut et faites glisser une fenêtre pour comparer des enregistrements adjacents dans cette fenêtre
• Les techniques qui se basent sur l'indexation avant de comparer les enregistrements par leurs clés
• Des techniques qui utiliser le blocage pour regrouper des enregistrements potentiellement similaires dans des blocs avant de procéder à la comparaison pour remédier à la grande complexité de la comparaison de tous les enregistrements

Sur le plan de la comparaison, certaines approches comparent toutes les valeurs des attributs de deux enregistrements en une seule chaîne. En revanche, pour d'autres, elles passent par la comparaison de chaque valeur d'attribut entre deux enregistrements.

Après avoir mesuré les similitudes ou les distances entre les enregistrements, comment pouvons-nous juger que deux enregistrements représentent ou non la même entité du monde réel ?

Afin d'atteindre ce but, notre méthodologie consiste à appliquer techniques d'apprentissage automatique et mesures de similarité avec peu de surveillance possible. En effet, nous prévoyons de faire appel à des experts pour annoter des paires d'enregistrements comme étant des doublons ou non. Cela nous permet de valider l'automatisation de notre approche et de fixer des seuils pour juger les paires d'enregistrements.

Méthodologie

Pour toutes les applications de Berger-Levrault ayant un problème de doublons, nous proposons l'approche suivante :

Cette approche est basée sur le prétraitement, l'indexation et le blocage des données pour la comparaison et la classification. On commence par une étape de prétraitement pour comprendre la sémantique des données, ce qui fait défaut dans la plupart des approches de l'état de l'art. Cette étape permet de reconnaître :

1. Types de colonnes (chaîne de caractères, entier, dateetc.) s'ils ne sont pas donnés
2. Leurs concepts (personne, e-mail, genre, adresse, paysetc.)

Il est évident que dans un premier temps nous ne pouvons pas couvrir tous les concepts possibles du monde réel, mais au moins ceux qui apparaissent le plus fréquemment dans nos bases de données. Nous envisageons d'alimenter la liste des concepts, c'est-à-dire que le système sera configurable et s'adaptera en fonction du domaine d'application.

Ces deux phases seront utilisées pour sélectionner les attributs (colonnes) pertinents afin de comparer deux enregistrements, car tous les attributs ne sont pas forcément nécessaires pour différencier deux enregistrements. Par la suite, un choix de mesures adéquates est effectué pour chaque attribut, car l'approche que nous essayons d'atteindre en fin de compte doit être générique et indépendante, avec une adaptation à l'application du domaine..

A titre d'exemple, le tableau ci-dessous montre quelques enregistrements avec les doublons potentiels :

Nom	Prénom	Adresse	Pays	Projet	Année
R. Dukes	Ana	4188 My Drive Garden City, New York 11530	USA	Dedup	2019
P. Becker	Timothy	1148 Columbia Mine Road Charleston, WV 25301	USA	Élire	2019
P. Beker	Timotty	3388 Farland Avenue Marion, TX 78124	USA	F. D	2019
R. Dukes	Anastasia	4188 My Drive Garden City, NY 11530	USA	Élire	2020

Pour suivre les étapes mentionnées précédemment, en prenant l'exemple des données présentes dans le tableau ci-dessus, notre algorithme identifiera les colonnes comme suit chaîne de caractères sauf pour l'année de la colonne qui sera identifiée comme une entierrien n'est magique jusqu'à présent.

Les concepts des colonnes sont clairs dans le tableau car l'algorithme les identifiera. Intuitivement, toutes les colonnes seront considérées sauf le pays puisqu'il contient la même valeur pour tous les enregistrements dans cet exemple. Pour rester simple et ne pas vous emmener trop loin dans le calcul mathématique, nous utilisons ici des mesures prenant en compte les chaînes de caractères (pour Nom, Prénom, Adresse, et Projet) et des mesures spécifiques aux nombres entiers (pour la fonction Année).

Ensuite, nous commençons à générer clés artificielles à partir des valeurs des enregistrements sur les attributs sélectionnés, en fonction de règles spécifiques (nombre de n caractères pour chaque valeur). Par exemple, si nous prenons 2 caractères de chaque valeur d'enregistrement, les clés seront respectivement r.an41de20, p.ti11el20, p.ti33f.20et r.an41el20. Nous donnons ici l'exemple de 4 enregistrements, mais cela sera fait pour tous les enregistrements possibles (puisque le sujet s'applique à des données énormes). La phase de clustering/blocking commence par regrouper les enregistrements similaires par leurs clés dans des clusters. Si deux clés sont similaires selon distance de Levenshtein (qui mesure la différence entre deux chaînes de caractères. Il est égal au nombre minimum de caractères qui doivent être supprimés, insérés ou remplacés pour passer d'une chaîne à l'autre.), leurs enregistrements seront placés dans le même cluster. Pour notre exemple (tableau ci-dessus), quel que soit le seuil de distance que nous devrons utiliser, les enregistrements 1 et 4 seront dans le même cluster.

Pour l'étape suivante, nous pouvons avoir des clusters avec un nombre différent d'enregistrements sans avoir à choisir le nombre de clusters au préalable. Ensuite, une comparaison intra-groupe de deux enregistrements (candidats) est effectuée pour chaque attribut par une mesure spécifique. L'idée d'utiliser le clustering est de réduire le champ de comparaison des enregistrements à ceux qui sont potentiellement similaires et d'en éliminer d'autres qui ne sont proches d'aucun autre.
Au final, les résultats que nous obtenons pour chaque cluster seront transmis à un classificateur supervisé pour renforcer la validation des doublons.

Résultats et performances

Après avoir vu les différentes étapes du processus de détection des doublons, nous devons examiner quelques résultats d'application. Nous prenons comme donnée, l'exemple de BL-Espagne qui contient des doublons de contribuables, puisqu'ils alimentent la nouvelle base à partir de sources différentes. Pour un deuxième exemple, nous prenons une base de données utilisée par les systèmes de pointe de détection des doublons. Elle concerne les restaurants aux Etats-Unis.

Cas d'utilisation 1 : Base de données WinGT

Pour ce premier cas, nous avons exécuté notre programme sur la base de données de l'Espagne. Afin d'obtenir les premiers résultats, nous n'avons pris que 20 000 enregistrements, même si ce jeu de données en contient environ 300 000, en raison du temps de calcul. Comme nous allons limiter les mesures de performance au nombre de doublons détectés uniquement parce qu'à ce stade, nous avons besoin d'annotations manuelles et d'une évaluation par des experts pour cette base de données.

 Comme l'illustre la figure ci-dessus, notre système a pu extraire 39 paires de doublons sur la base des trois attributs jugés pertinents. Ci-dessous, les résultats de différentes méthodes de détection des doublons, basées sur les attributs sélectionnés, avec une comparaison de notre approche.

Vous avez peut-être remarqué qu'il n'y a pas de résultat pour notre approche dans les 4 derniers cas. Cela s'explique par le fait que nous l'avons appliquée uniquement à ces tailles de données. Nous pensons qu'après application sur le reste des tailles de données, il y aura une explosion de doublons.

Cas d'utilisation 2 : Ensemble de données sur les restaurants

Pour ce deuxième cas, nous avons essayé différents tests avant et après la sélection des attributs avec différents choix de mesures et de seuils. La figure ci-dessus présente l'étape de sélection des attributs pertinents qui sont tous pris sauf Type. Ensuite, la phase de détection des doublons est effectuée en regroupant les restaurants potentiellement doublons dans le même cluster.

Les résultats sont présentés dans les deux tableaux suivants (avec traitement de tous les attributs ou seulement des attributs sélectionnés, respectivement).

Le premier tableau présente les résultats de la détection des doublons en utilisant tous les attributs en termes de comparaison de deux enregistrements, avec des mesures différentes à chaque fois (la même mesure utilisée pour tous les attributs). Le nombre moyen de doublons détectés est de 36. Alors que dans le second, après sélection des attributs pertinents, le nombre moyen de doublons détectés est de 69.

Comme le montrent clairement les deux tableaux, les résultats changent généralement en fonction des mesures et du choix des seuils. Nous envisageons de poursuivre ce travail en comparant nos résultats avec des annotations d'experts. Cela nous aidera à automatiser les seuils.