Dans l’analyse des données textuelles, et principalement dans leur traitement, nous sommes souvent amenés à travailler des processus algorithmiques capables d’identifier une forme de correspondance entre différentes chaînes de caractères. Nous retrouvons très souvent ce cas avec le nettoyage de bases clients. Pour identifier et traiter ces correspondances, nous vous proposons de découvrir la distance de Levenshtein.
Commençons par un exemple concret
Considérons l’exemple suivant :
| ID client | Prénom Nom | Âge | Date 1er achat | |
| 1234 | Jeanne Dupont | 36 | jdupont33@gmail.com | 05/01/2021 |
| 1235 | Jean Dupond | 47 | jean.dupond@hotmail.com | 05/01/2021 |
| 1236 | Jeanne Dupond | 36 | jdupond33@gmail.com | 06/01/2021 |
| 1237 | Marie Blanc | 27 | mblanc99@hotmail.com | 06/01/2021 |
Ce tableau pourrait bien être extrait de la base de données du CRM d’un magasin de vêtements, par exemple. En particulier, il visualise une partie de la base clients.
Ce type de données sont souvent saisies manuellement par un opérateur, dans notre cas le vendeur ou le caissier de notre magasin de vêtements.
Prenons le cas de Jeanne Dupont. Jeanne passe dans notre magasin le 05/01/2021 et, pour la première fois, elle fait un achat. Étant donné que c’est la première fois que Jeanne achète dans le magasin, le caissier lui propose d’adhérer à leur programme de fidélité et lui demande certaines informations : le CRM lui assigne automatiquement un ID client.
Jeanne repasse encore dans notre magasin le lendemain, elle fait un autre achat mais cette fois elle n’est pas servie par le même caissier. Le nouveau caissier n’est pas assez méticuleux et ne demande pas à Jeanne de lui épeler son nom de famille, et il ne vérifie pas s’il y a déjà d’autres Jeanne Dupont ou Dupond contenues dans leur base client : il écrit directement “Jeanne Dupond”, ainsi que l’adresse email “jdupond33@gmail.com”. Par conséquent, le CRM crée une autre fiche client associée à un nouvel ID.
Dans cet exemple nous venons de créer un doublon, c’est à dire une observation qui est un duplicata d’une autre déjà contenue dans notre dataset, mais qui est écrite (dans notre exemple, à cause d’une erreur de saisie) d’une façon différente. Dans le cas où des doublons sont bien présents, notre CRM fournira une information incorrecte sur le nombre de clients fidèles du magasin.
Comment pouvons-nous éviter cela ?
Dans le Traitement Automatique du Langage naturel (TAL) ou Natural Language Processing (NLP) en anglais, nous retrouvons des outils qui nous permettent d’identifier la similarité entre des chaînes de caractères. Un exemple est donné par la distance de Levenshtein.
La distance de Levenshtein est une distance, au sens mathématique du terme, donnant une mesure de la différence entre deux chaînes de caractères. Elle est égale au nombre minimal de caractères qu’il faut supprimer, insérer ou remplacer pour passer d’une chaîne à l’autre.
On appelle distance de Levenshtein entre deux mots M et P le coût minimal pour transformer M en P en effectuant les seules opérations élémentaires suivantes :
substitution d’un caractère de M par un caractère différent de P ;
insertion (ou ajout) dans M d’un caractère de P ;
suppression (ou effacement) d’un caractère de M.
On associe à chacune de ces opérations un coût. Généralement, le coût est égal à 1 pour les trois opérations. On peut montrer que définir une distance au sens mathématique du terme entre les caractères d’un alphabet entraîne que la distance de Levenshtein est aussi une distance au sens mathématique du terme sur l’ensemble des chaînes construites sur l’alphabet.
(source : Wikipedia)
Comment l’appliquer ?
Voici quelques exemples :
- la distance de Levenshtein entre “ville” et “vile” est 1 car il faut ajouter un “l” dans la deuxième chaîne de caractères afin d’avoir une similarité parfaite avec la première ;
- la distance de Levenshtein entre “Paris” et “Parit” est encore 1 car il faut remplacer la “t” par une “s” dans la deuxième chaîne de caractères afin d’avoir une similarité parfaite avec la première ;
- la distance de Levenshtein entre “soleil” et “bonsoir” est 5 car nous avons besoin de faire 5 opérations afin de passer de la deuxième chaîne de caractères à la première, il faudra notamment :
- remplacer le “n” par un “l”,
- remplacer le “s” par un “e”,
- enlever le “o”,
- remplacer le “r” par un “l”.
Si nous reprenons l’exemple de la chaîne de caractères “Jeanne Dupont”, nous voyons qu’elle a une distance de Levenshtein la plus proche avec “Jeanne Dupond”, justement notre doublon :
- distance de Levenshtein entre “Jeanne Dupont” et “Jean Dupond” : 3
- distance de Levenshtein entre “Jeanne Dupont” et “Jeanne Dupond” : 1
- distance de Levenshtein entre “Jeanne Dupont” et “Marie Blanc” : 9.
Nous pourrions ainsi assigner un seuil minimal de distance de Levenshtein (en tenant en compte aussi d’autres variables, comme l’âge et l’adresse email), afin de définir si une observation est bien un duplicata d’autre ou non.
Pour plus d’informations, n’hésitez pas à tester la fonction “levenshteinDist” contenue dans la librairie R “RecordLinkage” : https://rdrr.io/cran/RecordLinkage/man/strcmp.html
