Dédupliquer ses données : un vieux fardeau toujours d’actualité

20 mars 2020 Data Science

Migration d’un CRM à un autre, utilisation de plusieurs outils différents, consolidation de plusieurs bases de données suite à une fusion, autant de situations qui peuvent amener à vouloir dédoublonner sa base de données de produits, de clients ou autre. 

Dédupliquer une base de données réfère au fait de détecter les entités (les lignes) similaires présentes dans un même fichier. Une problématique bien connue des métiers et qui pour autant reste encore peu documentée aujourd’hui.

Le but de cet article est de faire un état des lieux des méthodes de déduplication appliquées aujourd’hui sur le marché, et de mettre en exergue les défis qu’une telle problématique, aussi simple soit-elle à formuler, peut soulever.

 

Introduction

 

Utiliser plusieurs outils différents pour gérer ses contacts (ou ses produits), migrer un CRM (ou un PIM) vers un autre, unifier une base de données suite à une fusion entre deux entreprises, unifier une base de données de produits pour avoir une meilleur vision de son catalogue (par exemple, les centrales d’achats), tout autant de cas qui conduisent à la même problématique : des données en doublons.

 

Des données en doublons, c’est gênant. En effet, cela biaise une étude statistique lorsque l’on veut faire une étude sur ses clients ou sur ses produits, les coûts de stockages sont élevés, les clients ne sont pas contents qu’on les contacte plusieurs fois pour la même chose, vous achetez les mêmes produits plusieurs fois, bref, on pourrait en écrire un livre. C’est une problématique bien connue des métiers, qui n’est pas nouvelle et qui a fait l’objet de beaucoup de réunions en interne pour pallier ce phénomène fâcheux. 

Et paradoxalement, les méthodes pour dédupliquer des éléments (des lignes, des contacts, des produits) d’une base de données sont encore peu documentées.

Pour cause, il faut l’avouer, ce n’est pas une problématique très sexy à résoudre, il est clair que les data scientists préfèrent largement mettre au point des architectures de pointe pour analyser des images ou extraire des informations d’un texte libre plutôt que de devoir chercher des informations dupliquées dans un CRM, et c’est bien compréhensible.

 

Un peu de contexte

Dans cette section, nous allons présenter quelques éléments qui vont vous aider à comprendre pourquoi dédupliquer une base de données n’est pas une tâche si simple.

 

Un problème complexe

 

Mettons que nous ayons à notre disposition un fichier de 1000 contacts à dédupliquer. Le but est donc, parmi ces 1000 contacts, d’identifier les lignes qui réfèrent à une même personne. 

 

Une approche exhaustive est de comparer tous les contacts un par un. En d’autres termes, pour un contact donné, on le compare à tous les autres contacts du fichier (excepté lui-même évidemment), et on met de côté les contacts identiques.

Le problème avec cette approche, c’est qu’il est nécessaire d’effectuer 999 comparaison pour chaque contact, donc au total 999 1000 = 999 000 comparaisons, soit presque 1 million de comparaisons à faire, pour un fichier de seulement 1000 contacts. Vous imaginez donc que si vous avez un fichier conséquent (avec plusieurs dizaines de milliers de contacts ou de produit), l’approche exhaustive est à prohiber si le temps de comparaison n’est pas rapide.

 

En algorithmique, on dit que cette problématique, et donc l’approche exhaustive naturelle présentée ci-dessus, admet une complexité quadratique. C’est à dire que si vous avez un fichier de n lignes à dédupliquer, alors le nombre total de comparaisons à effectuer est de l’ordre de n2

Les problèmes quadratiques sont assez courant (par exemple, une multiplication de matrice), mais se gèrent assez bien de nos jours avec une bonne puissance informatique. Néanmoins, dans le cadre de la déduplication, la comparaison n’est pas aussi simple qu’elle peut paraître, et donc le fait que le problème soit quadratique pose problème. Nous détaillons cela dans la prochaine section.

 

L’impact de la qualité de données

 

Comme évoqué précédemment, dédupliquer un fichier revient à comparer chacun de ses éléments avec le reste du fichier. La définition de cette comparaison constitue le fondement des différentes méthodes de déduplication.

 

En effet, la méthode de comparaison la plus simple, c’est de regarder chaque élément de chaque ligne, et de comparer leur exacte adéquation. Par exemple, dans le cas d’un fichier de contact, on sera amené à comparer les deux contacts suivants : 

 

  • Jean Dupont, comptable chez Globex Corp.
  • Jean Dupont, travaillant chez Globex.

 

Dans ce cas bien précis, si l’on effectue une comparaison exacte sur le nom et sur le prénom, alors on peut en déduire qu’il s’agit de la même personne, et donc d’un doublon. Néanmoins, la comparaison exacte échouerait si l’on compare l’entreprise dans laquelle Jean Dupont travaille, et c’est bien dommage parce que les champs se ressemblent fortement !

 

Cela motive donc le fait de ne pas travailler avec des comparaisons exactes, mais avec des similarités. Et le calcul de ces similarités est un enjeu fort pour mesurer une proximité, une distance, entre deux lignes à comparer.

Nous détaillons les similarités dans une section plus bas, un peu de patience !

 

La comparaison par similarité aide également à pallier les problèmes de qualité de données sous-jacents. Par exemple, en reprenant l’exemple énoncé ci-dessus :

 

  • Jean Dupont, comptable chez Globex Corp.
  • Jean Dupond, travaillant chez Globex.

 

La similarité entre Dupont et Dupond sera élevée, ce qui laisse à penser qu’il s’agit de la même personne, et donc d’un doublon, même si la qualité de la donnée n’est pas parfaite.

 

Un autre exemple de problème de qualité de données, plus traître cette fois :

 

  • Marie Durand, née Dupont, ingénieure chez Globex Corp.
  • Marie Dupont, née Durand, ingénieure chez Globex Corp.

 

Dans ce cas là, il s’agit très probablement de la même personne (même s’il n’est toutefois pas à exclure la possibilité que cela corresponde à deux personnes distinctes). Dans le cas où il s’agit de la même personne, cela est causé par le fait que le nom marital et le nom de jeune fille aient été inversés. Et dans ce cas là, même une approche par similarité n’est pas suffisante puisque Durand n’est pas si proche de Dupont. 

Ainsi, cela motive la nécessité d’effectuer des croisements, des recoupements d’informations, parmi les champs d’une même comparaison (ici nom marital et nom de jeune fille), le tout combiné avec des calculs de similarité.

 

Vous l’aurez compris, la qualité de la donnée a un impact direct sur la qualité du dédoublonnage d’un fichier. Des erreurs dans les champs, des champs qui peuvent comporter des valeurs identiques inversés (par exemple, nom de famille et nom marital), des champs erronés, des champs manquants, autant de phénomènes que vous avez déjà croisé, et qui vous compliquent drastiquement la tâche de déduplication.

 

Les mathématiques sous-jacentes

 

Dans cette section, nous allons vous donner une formulation mathématique du problème, bien que nous ne donnerons pas ici un formalisme avancé, ce n’est pas l’objet de cet article.

 

Nous vous donnerons également quelques exemples de fonctions (là encore, dans un formalisme plutôt léger, ce n’est pas le but de l’article) pour calculer des similarités entre les champs d’une base de données.

Contexte

 

On démarre avec un jeu de données D à dédupliquer, disons un fichier de contacts pour rester dans la même typologie d’exemple que présenté précédemment, et supposons également que ce fichier de contact comporte n lignes. Notez que nous parlons en lignes ici, et pas en contacts, car on veut dédupliquer notre fichier, et donc a priori notre fichier comporte plus de lignes que de contacts réels !

 

Prenons donc deux lignes au hasard l1, l2 de notre fichier de contacts. On dira dans notre jargon que ces deux lignes représentent un couple, le couple (l1, l2). Le but de la déduplication, c’est de déterminer si le couple (l1, l2) est oui ou non un doublon. 

ATTENTION, il ne s’agit pas de déterminer ici si l1=l2, mais de déterminer si l1 et l2 réfèrent au même contact ou non. C’est un écueil dans lequel il ne faut pas se prendre. Alors oui, vous me direz que si l1 = l2, alors le couple (l1, l2) est un doublon, ça oui, mais attention, la réciproque est fausse dès lors qu’il y a des imperfections dans les données !

 

On va supposer également que notre fichier de contacts contient m contacts uniques, que l’on note c1,…, cm. Notez bien que si le fichier ne comporte aucun doublon, alors m = n.

Ainsi, pour en revenir à nos moutons, dédoublonner revient  à déterminer si le couple (l1, l2) réfère à un seul et même contact, disons le i-ème contact ci. A noter aussi que m n’est jamais connu ni observé (sauf dans quelques rares cas où le fichier est petit, mais en règle générale non).

 

En d’autres termes, il s’agit ici de construire deux groupes de couples (l1, l2) : un groupe de doublons, et un groupe de non-doublons. La littérature anglo-saxonne nomme ces groupes M(pour match) et U(pour unmatch).

Ainsi, lorsque l’on va dédoublonner notre fichier de contacts D, on va calculer la probabilité que le couple (l1, l2) appartiene à M, c’est à dire la probabilité que les deux lignes du couple réfèrent au même contact. Et on effectue cela pour toutes les lignes du fichier, d’où le fait que le problème ait une complexité quadratique !

 

Plusieurs approches

 

Pour calculer cette probabilité, il existe plusieurs façons de faire. Les approches historiques modélisent cette probabilité en effectuant une hypothèse sur sa distribution sous-jacente (la loi, la façon dont les données et les doublons  sont répartis dans le jeu de données), puis en estimant les paramètres de cette distribution avec les données.

 

Ce genre d’approche est en général très efficace si l’hypothèse structurelle (hypothèse de départ) posée par le statisticien est correcte, ce qui n’est en général pas le cas. Mais malgré l’erreur de modélisation, ce genre d’approche reste relativement rapide et présente des performances correctes, on pourra notamment citer (Culotta & Mccallum, 2005) [1] et (Hall et al., 2008) [2]. Néanmoins, ce genre d’approche présente en général des difficultés lorsque la dimension (le nombre de champs à comparer par exemple, ou encore le nombre de similarités calculées) augmente.

 

Les approches plus récentes, notamment (Sarawagi, Sunita & Bhamidipaty, Anu., 2002) [3], optent pour une approche à base de machine learning, et entraînent un algorithme qui va calculer automatiquement cette probabilité, en se basant sur un ensemble de mesures de similarités entre les champs de la base de données.

Ce genre d’approche présente en général une qualité de prédiction bien supérieure, et fonctionnent assez bien en grande dimension. 

 

Cependant, les approches à base de machine learning requièrent en général un nombre de couples (l1, l2) conséquent pour présenter des résultats convenable, ce qui n’est pas le cas ici puisque l’on ne sait pas d’avance si le couple (l1, l2) est un doublon ou pas ! (ça serait trop facile sinon)

 

Les data scientists comprendront, mais là il faut le dire : on essaye d’entraîner un modèle d’apprentissage supervisé sans target, il n’y a pas comme un paradoxe là ? 

Eh bien justement si ! C’est bien problématique ! On veut entraîner un modèle de prédiction à prédire un phénomène qu’il n’a jamais observé. L’IA n’en est pas encore là malheureusement, vous ne verrez ça que dans Terminator.

 

Plus sérieusement, pour palier le problème d’apprentissage supervisé sans variable cible, il existe une solution plutôt simple : l’active learning. L’active learning consiste à : 

 

  1. taguer quelques exemples à la main, c’est à dire renseigner, pour quelques couples (l1, l2) si le couple en question est bien un doublon ou pas,
  2. entraîner un modèle de prédiction sur ces quelques exemples, 
  3. taguer quelques exemples supplémentaires, basés sur les prédictions du modèle, et ainsi de suite.

 

Ainsi, l’active learning est en général une bonne solution pour qu’un modèle atteigne d’excellentes performances tout en s’affranchissant du fait de devoir taguer un grand nombre de lignes.

 

Calcul des similarités

 

Toutes les méthodes statistiques, qu’elles soient classiques au sens historique du terme (statistique paramétrique) ou à base de machine learning, nécessitent de quantifier l’information présente dans les champs. 

En effet, toute méthode statistique doit prendre à un moment donné des entrées numériques, de sorte à pouvoir estimer les probabilités qui nous intéressent.

 

Dans cette section, nous allons décrire quelques méthodes pour quantifier intelligemment l’information présente dans notre fichier de contacts D.

 

La distance de Levenshtein est probablement la mesure de similarité la plus courante et la plus facile à implémenter. Elle est très pratique pour calculer un écart entre deux chaînes de caractères, et permet de tenir compte des éventuelles fautes d’orthographe.

 

Pour deux champs d’un fichier, disons deux prénoms, la distance de Levenshtein compte le nombre d’opérations élémentaires (ajout, suppression ou remplacement d’une lettre) pour transformer le premier prénom en le second.

 

Ainsi, Pierre et Piere auront une distance de Levenshtein égale à 1, alors que Pierre et Emma auront une distance de 4. Et donc, plus la distance est faible, plus les prénoms sont similaires, et plus il y a de chances qu’il s’agisse d’un doublon !

 

Néanmoins, Léa et Léo ont également une distance de Levenshtein à 1, et donc la méthode présente ses limites, même si on normalise la distance avec les longueurs des prénoms.

 

D’autres distances, comme la distance de Jaro-Winkler, permettent de quantifier l’information un peu différemment. La distance de Jaro-Winkler (JW) fait glisser le long du prénom une petite fenêtre mobile d’une longueur de quelques lettres, et regarde au sein de cette fenêtre si les lettres des deux prénoms sont alignées ou non, et compte les permutations de lettres.

Ainsi, cela permet de détecter des erreurs très locales au sein des prénoms (ou sur d’autres champs que le prénom), et de prendre en compte les permutations de lettres.

La figure 1 ci-dessous illustre le procédé de calcul de la distance de JW. Pour plus de détails sur le calcul de cette distance, nous vous invitons à consulter la page Wikipédia dédiée.

calcul de la distance de JW

Au même titre que la distance de Levenshtein, deux prénoms similaires auront une distance très proche, et deux prénoms très différent seront éloignés.

Et c’est très bien ! Puisque les deux méthodes de calcul sont radicalement différentes, cela permet au modèle d’exploiter une quantité plus riche d’information pour l’aider à décider du fait que (l1, l2) soit un doublon ou non.

 

Il existe toute une panoplie de distances entre chaînes de caractère, et plus on fait, meilleures seront les prédictions. On ne va pas décrire toutes les mesures de similarités ici, car ce n’est pas le but de cet article. Ce qui compte, c’est que vous ayez compris qu’il est important de quantifier intelligemment l’information présente dans les champs pour pallier au mieux aux erreurs rencontrées dans les données, et pour ainsi améliorer les performances du modèle.

Limites des méthodes mathématiques

 

Comme nous l’avons évoqué dans la section précédente, les méthodes de calcul de similarité entre deux champs à comparer permettent de quantifier intelligemment une information qui n’est pas sous forme numérique à l’origine.

 

Les méthodes les plus prometteuses en termes de qualité de prédiction, et donc de qualité de détection des doublons dans fichier, sont les méthodes à base de machine learning. Il est cependant relativement rare d’avoir un fichier partiellement annoté (c’est à dire un fichier avec des exemples de doublons, et des exemples de non-doublons) pour entraîner l’algorithme sans avoir à mettre en place une interface d’active learning. 

Néanmoins, utiliser les travaux manuels de déduplication faits par équipes métiers (si jamais ils sont conservés) est une bonne façon de valoriser le travail des équipes métier, et d’avoir un premier jeu d’entraînement pour l’algorithme. Mais attention, cela ne permet en général pas de s’affranchir de l’étape d’active learning.

 

Par ailleurs, afin de tirer un maximum de performances de la part d’un algorithme de machine learning, il est également important de calculer un nombre assez conséquent de similarités, afin que l’algorithme puisse affiner ses prédictions de doublons. Là encore, ce problème paraît anodin, mais c’est probablement le plus gros problème que vous allez rencontrer.

 

En effet, le calcul d’une dizaine de similarités sur un fichier de contacts prend environ 200 microsecondes (c’est à dire 0,0002 seconde) par couple, et le calcul de la probabilité de doublon pour le couple prend environ 150 microsecondes. C’est rapide vous me direz ! Alors oui, MAIS, n’oubliez pas que la complexité est quadratique ! Cela signifie que vous devez répéter cette opération pour tous les couples de lignes de votre fichier, et donc si vous avez un fichier de 1000 lignes, la déduplication vous prendra 1000 999 0,00035 350 secondes, soit un peu moins de 6 minutes, pour seulement 1000 lignes !

Et attention, la magnitude est quadratique, donc si vous avez 10 000 lignes dans votre fichier de contact, vous n’allez pas multiplier le temps de calcul par 10, mais par 100. Et donc, pour dédupliquer un fichier de 10 000 lignes, il vous faudra presque 10 heures.

 

Ce problème est sans doute celui qui vous donnera le plus d’insomnies, même pour des data scientists aguerris. Il vous faudra non seulement optimiser drastiquement le calcul des similarités, mais également réduire l’espace de recherche des doublons, sans pour autant nuire aux performances du modèle. Certaines méthodes peuvent efficacement réduire l’espace de recherche, comme des méthodes de blocking ou de hashing, mais ce n’est pas l’objet de cet article de les détailler.

 

Conclusion

 

Vous l’aurez compris, la déduplication est un problème bien connu des experts métiers qui travaillent avec leurs données de contacts, de produits, de transaction au quotidien, et c’est une douleur qui se transmet de génération en génération. 

 

La déduplication est une tâche qui est en général faite manuellement, ce qui ne valorise pas le temps des métiers, qui est très compliquée à automatiser de par le caractère quadratique du problème, et où les problèmes dans les données (champ manquant, valeurs bruitées, erronées, etc.) rajoutent une couche de complexité.

 

Par ailleurs, la communauté de recherche en machine learning se concentre très peu sur les problèmes de dédoublonnage, et plus généralement sur les travaux relatifs à la qualité de la donnée sur des fichiers structurés comme des fichiers de contacts. 

 

Il y a donc encore beaucoup à faire, pour redorer le blason de l’étude d’un problème assez vieux (pas comme le monde, mais presque), et particulièrement dans le domaine du machine learning appliqué aux données incomplètes.

 

Si vous souhaitez échanger sur vos problématiques de déduplication, n’hésitez pas à nous contacter. 

 

Références

[1] Culotta, Aron & Mccallum, Andrew. (2005). Joint deduplication of multiple record types in relational data. 257-258. 10.1145/1099554.1099615.

[2] Hall, Robert & Sutton, Charles & Mccallum, Andrew. (2008). Unsupervised deduplication using cross-field dependencies. 310-317. 10.1145/1401890.1401931.

[3] Sarawagi, Sunita & Bhamidipaty, Anu. (2002). Interactive Deduplication using Active Learning. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 10.1145/775047.775087.

Newsletter

Ne manquez pas nos articles ! (1 email/mois)