<< Back

Fuzzy Match – recoupement d’adresses

L’outil Fuzzy Match a un côté ‘Magique’. Pour rapprocher les valeurs d’un champ, si ce dernier n’est pas propre, impossible d’utiliser des jointures. C’est ce qui peut arriver avec des valeurs entrées à la main par exemple : noms, adresses, numéro de téléphone… le lundi on a enregistré un Matthieu Dupont et le mercredi un Mathieu Dupond. Cela peut aussi être le cas avec un catalogue de produits, d’offres ou de campagnes identifiées par des libellés, etc.

Si les jointures ne fonctionnent pas, reprendre les valeurs à la main nécessite du temps, trop de temps.

Heureusement, le Fuzzy Match est là ! C’est exactement ce qu’il fait : il cherche des similarités dans les chaînes de caractère, et si elles sont semblables, disons à 80%, il les matche.

Seulement, au premier abord, l’outil peut en décourager quelques-uns. Il faut en effet mettre les mains dans le cambouis et faire un peu de paramétrage. Pas de panique : c’est très simple !

 

Les Données

Nous allons utiliser un petit jeu de données ODbL que vous pouvez trouver sur le site Open Data Paris.

Il s’agit d’une liste des cafés Parisiens proposant le café à 1€ .
Si la lecture de cette ligne vous donne l’irrépressible envie d’aller sur-le-champ prendre un café, il y a également la version carte accessible en ligne, à croiser avec la liste des cafés proposant le Wifi et nous pouvons poursuivre !

Voila à quoi ressemble le fichier .csv

Nous nous intéressons ici uniquement au nom du café, à son adresse, ainsi qu’à la Géolocalisation.

L’idée est de récupérer une adresse à partir des coordonnées, via une API de géolocalisation puis de réaliser le Fuzzy Match sur ces adresses récupérées et celles présentes dans le csv.

 

Géolocalisation

Pour l’API, j’utilise HERE parce que sa précision me convient, mais vous pouvez utiliser Google Map, Bing, la BAN, ou même l’outil Alteryx (si vous avez une license comprenant l’extension Spatial Data avec Geocoder).

Pour les API, il vous faut en général des clefs. Ces clefs sont souvent gratuites jusqu’à un certain volume de requêtes et ne demande qu’une inscription.

Pour Here, ça se passe ici 

Vous aurez besoin de ces identifiants/clefs pour requêter l’API.

 

Première étape : on récupère les coordonnées lat et long dans deux champs distincts comme ci-dessous. Pour cela, j’utilise l’outil Text to Column.

A partir de là j’utilise mes identifiants HERE pour construire la requête.
Via l’aide en ligne, on peut voir quel service appeler, et comment renseigner les paramètres.

Dans mes credentials j’ai entré trois champs :

APPAdress qui contient le lien générique vers le service à appeler, APPID (mon identifiant) et APPCode (ma clefs).

Puis je construis la requête comme ci-dessous :

Vous pouvez la tester directement en entrant la requête dans votre navigateur.

Il faut ensuite utiliser un download tool pour récupérer les réponses de l’API et un JSON parse car elles sont au format JSON (on aurait pu demander un format xml aussi – ça se passe au niveau du champ APPAdress de mes credentials).

L’API me renvoie tout un tas d’informations mais dans ce cas, je ne veux que la rue et le numéro. La ville aussi pour filtrer sur les réponses à Paris: inutile de matcher sinon.

J’utilise un cross-tab pour les disposer en colonne et une petite formule pour reconstruire l’adresse :

Et voilà, j’ai récupéré mes adresses via Here.

 

Fuzzy Matching

        A ce niveau, je fais l’union de mes deux jeux de données : les adresses du fichier – que je flag ‘File’, et les adresses de l’API – que je flag ‘Here’ dans une nouvelle colonne nommée ‘Source’.
Après l’union, je ne garde que trois champs :

Afin d’identifier les lignes j’utilise Record ID.

Petite astuce : il vaut mieux concaténer le nom de la source à cet ID pour identifier les lignes. Une simple formule permet cela. Je crée ainsi une clef unique Key_str

        Et maintenant les choses sérieuses …Comment configurer le Fuzzy Match.

Ici nous sommes en mode ‘Merge’ : nous voulons trouver une ligne similaire à l’adresse du fichier parmi les adresses obtenues via l’API.

Nous précisons ensuite qu’on distingue la provenance de l’adresse grâce au champ Source (File ou Here) ; et que nous identifions les lignes à l’aide du champ Key_str (cf image plus haut, il s’agit de la concaténation entre la source et l’ID de la ligne).

        Enfin, il faut lister les champs sur lesquels on fait le match. Ici il n’y en a qu’un : Adresse.
On aurait pu avoir la liste des cafés à Paris et à Lyon, renseigné via un champ Ville. Nous aurions fait un matching exact sur la ville avant de comparer les adresses, pour être sûr de comparer les cafés parisiens avec les cafés parisiens (il y a certainement une avenue Jean Jaurès à Lyon comme à Paris).

Attention cependant, cela équivaut à une jointure : un peu de nettoyage de donnée ne peut pas faire de mal.

Dans ce cas, j’ai remplacé les ‘-‘ de mes adresses par des espaces

Puis j’ai utilisé un cleansing data pour homogénéiser tout ça : des majuscules partout, pas de tabulation ou de double espaces…

C’est important car cela évite d’avoir un score de matching faible sans raison valable.

 

        Allons maintenant voir comment customiser le match sur Adresse :

Le preprocess est utile si vous n’avez pas bien nettoyé votre champ au préalable. Ici, j’ignore la ponctuation dans mon score de matching.

Comme j’ai des adresses, j’utilise ‘Adress number + Soundex’ et je fais confiance en alteryx pour reconnaître des numéros de rues proches. Attention cependant, il est certainement adapté aux adresses US.

De manière générale, pour comparer des nombres, je recommanderais de les extraire de votre champ (via une RegEx par exemple), de les convertir en numérique et de les comparer. Par exemple en calculant la différence en % de la valeur. De cette façon, vous êtes sûr que 999 sera assimilé à 1000 (avec un filtre à 15 ou 20% … à vous de choisir).

Le Fuzzy Match sera alors fait sur le texte restant uniquement (dans ce cas, vous pouvez utiliser la méthode Soundex par exemple).

Vous trouverez ici plus d’informations sur la manière dont Alteryx construit son Matching (et donc génère ses clefs de matching).

Attention, prenez votre temps, le ‘bon’ matching dépend de votre donnée.

 

        Continuons. Alteryx propose d’affiner un peu le matching en précisant pour quels mots nous ne souhaitons pas générer de clefs :

Ne pas générer de clef pour les mots d’une lettre (D’, L’…) ou les mots tels que ET, AU DE pour ne comparer que les mots pertinents. Inutile de monter le score entre la rue du pot de fer et la rue du cherche midi. Vous pouvez trouver des listes de ce genre de mots (appelés Stop Words) dans la plupart des langues. Il suffit de chercher Stop Words Français dans un navigateur de recherche !

Là aussi, connaître sa donnée est important. Si vous comparez des produits français qui sont tous labellisés FR…, vous pouvez ignorer FR dès le début.

 

        Passons aux algorithmes de matching :

Il en existe plusieurs et vous pouvez chercher ce qui les différencie en ligne, soit directement sur l’aide du Fuzzy Match , soit sur Wikipédia !

Par exemple, Jaro et Levenshtein sont deux distances, qui mesurent les différences entre les mots. La distance est calculée en utilisant les transpositions (pour Jaro) ou les insertions, délétions et substitutions (pour Levenstein). Vous pouvez tester l’une et l’autre ou même choisir de prendre le meilleur des deux scores (Best of …).

Il faut d’abord définir si vous voulez faire un matching sur les mots ou sur les caractères uniquement. Si vous avez des phrases complètes ou des noms, il vaut mieux matcher au niveau du mot. Quitte à choisir l’option also use Character (avec ou sans prendre en compte les espaces).

Là encore, cela dépend de vos données. Est-ce que l’espace est important lorsque vous comparez notre dame des champs et notre dame des landes? Est-ce que ça doit compter comme un match en plus ou non, etc. Autant de questions à vous poser lorsque vous configurez l’outil.

Rien ne vous empêche de tester différentes configurations à partir d’un sous ensemble de données.
D’ailleurs, n’hésitez pas à copier votre outil de matching et à en lancer plusieurs à la fois, avec différentes configurations, afin de comparer directement les outputs.

Enfin les statistiques sur la fréquence des mots sont basées sur la lange anglaise (les adresses et les surnoms communs aux Etats-Unis). Il y a peu de chances que cela fonctionne sur des données françaises. St (abréviation de Street : rue) va être très présent dans les adresses aux US et aura donc un poids moins important. Le St en France n’a pas la même signification.

 

        La longueur maximale de la clef de matching est également importante.
Si vous souhaitez matcher des mots tels que hippopotomonstrosesquipédaliophobique,
ou si vous ne savez pas quoi choisir, vous pouvez laisser le 20 par défaut. Avec 20, il matcherai tous les mots ayant au moins 20 lettres en commun avec hippopotomonstrosesquipédaliophobique (dans ce cas il faudrait mettre 37 pour avoir le mot entier). Avec une clef de taille 20 vous avez déjà peut de chance de rapprocher des mots différents. Si en revanche vous forcez une clef plus petite, par exemple 2 vous aurez un match exact entre FRA et FR mais aussi UFR … Dans certains cas, il peut être intéressant de baisser la taille de la clef. Encore une fois, cela dépend de vos données !

 

        Enfin pour chacun des champs matchés, vous pouvez définir un threshold et un poids :

Si vous n’utilisez qu’un seul champ (ici Adresse) inutile de préciser cela. Sachez tout de même que si vous mettez un Threshold de 50% à ce niveau, mais que vous laissez 80% au global, le Threshold final sera de 80%.

Si en revanche vous matchez deux champs (par exemple ville et Adresse, ou nom et prénom…), vous pouvez donner un poids et un threshold à chacun. Par exemple, le prénom peut compter pour 20% du score avec un threshold de 60% et le nom pour 80% du score final avec un threshold de 70%.

Le score final dans ce cas sera égal à 20% du score du prénom + 80% du score du nom. C’est ce score final qui sera comparé au ‘Match Threshold’ global.

Attention, si le match style est ‘Exact’ il n’y aura pas de Threshold (c’est exact, c’est tout).

 

Output

Voilà pour la customisation du Matching. Pour affiner le résultat, vous pouvez jouer avec l’output.

L’output ‘standard’ est le suivant :

Il y a l’identifiant de la ligne, l’identifiant de la ligne matchée.

NB : c’est l’intérêt de concaténer la source devant les identifiants. Alteryx les sortiras toujours dans le même ordre : ici c’est d’abord les File, puis les Here.
Si vous laissez l’identifiant uniquement, il se peut qu’il échange leur position (ID1 – ID2) ce qui peut rendre les résultats plus difficiles à lire – ou qui nécessite une étape de réordonnancement supplémentaire.

Il y a aussi les scores pour chacun des champs matchés (MatchScore_Adresse, MatchScore_Ville, etc.) puis le score global.

Si vous choisissez d’ajouter comme output les lignes non matchées (Unmatched records), vous verrez des scores nulls. Ces scores peuvent être nuls si l’un des matching ‘Exact’ n’est pas respecté, si l’un des scores de matching est en-dessous du threshold ou si l’alternance des sources n’est pas respectée (ci-dessous, vous voyez qu’il propose un match entre une ligne et… elle-même).

Si vous n’avez que des nulls, je vous conseille de procéder par étape : un champ de matching à la fois, en abaissant le threshold au maximum pour comprendre à quel moment il ne reconnaît plus les similarités.

Afficher les lignes non matchées vous permet notamment de fixer un threshold qui vous donne des résultats acceptables (avec assez de lignes reconnues) mais pas non plus des matchs aberrants. Si vous devez matcher Françoise avec Benoit pour avoir un bon pourcentage de ligne matchées, le Fuzzy match n’est peut-être pas l’outil qu’il vous faut !

Si vous souhaitez uniquement récupérer des ID de groupes vous pouvez choisir l’option ‘Generate Keys Only’ qui vous permettra de reconnaître à quel grand groupe de matching vos lignes appartiennent, via un ID unique de ce groupe

 

Le mode Purge fonctionne également dans notre cas.

Simplement il comparera chaque adresse avec toute les autres (sans chercher une source différente). Ici, il y a de fortes chances que le résultat soit le même  qu’en mode Merge, mais il compare des éléments dans une liste deux fois plus longue (ce qui fait environ quatre fois plus de comparaisons).

 

Formater l’output

Pour finalement avoir un résultat lisible, et récupérer les champs originaux de votre source, vous pouvez utiliser deux outils.

Soit un Find Replace pour remplacera Key_str par l’adresse du fichier File, et un second pour remplacer Key_str2 par l’adresse fournie par Here.

Soit vous utilisez deux Jointures consécutives. La première sur la première clef

Et la seconde sur la seconde…

A bien distinguer les champs ramenés ici, qui correspondent aux résultats fournis par Here (associés à la clef Key_str2, et donc aux valeurs matchées).

 

Enfin, vous avez peut-être remarqué qu’Alteryx ne se limite pas à un match. Il peut matcher la même ligne avec différentes propositions et les scores correspondants. Si vous souhaitez récupérer un unique match, vous pouvez trier les données par match score décroissant, et ne garder qu’une ligne unique par ID à matcher (c’est à dire une ligne par ID du fichier d’origine ou par Key_str).

Voilà un extrait du fichier final.

Les matchs à 100 % ne sont pas palpitants. Mais remarquez les match compris entre 70 et 100, ils sont intéressants: c’est le genre de ligne que nous aurions perdues avec une jointure exacte. En revanche, les match en-dessous de 60% ne correspondent pas, il faudrait ici fixer un threshold aux alentours de 70.

 

La première jointure (sur la clef Key_str) peut aussi vous permettre de récupérer les lignes non matchées (si vous ne cochez pas l’option ‘Output Unmatched Records’). Dans mon cas, c’est la sortie L (left) de la jointure : les Key_str qui sont présent dans le fichier d’origine mais pas dans l’output du Fuzzy Match.

Il y en a 3 ici, je vous laisse deviner pourquoi

 

Vous trouverez ici le workflow Alteryx. Attention, pour qu’il fonctionne vous devez télécharger également les données et vous créer des Id/Clefs pour requêter l’API Here.

J’espère que ce post vous aidera à manipuler le Fuzzy Match. C’est un processus itératif : paramétrer, lancer, regarder les résultats, et recommencer …. Jusqu’à obtenir ce qu’on cherche. De la patiente, et une bonne compréhension des données et des besoins vous aiderons à avancer de façon plus efficace.

Elsa Mullor

Paris

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *