Clés de blocage et voisinage trié
- Leçon 9
- 40 min
- Module 3 : Le blocage : ne pas tout comparer
Où nous en sommes
Nous ne pouvons pas comparer toutes les paires. Nous devons donc choisir des paires candidates. Le moyen le plus simple est une clé commune. Dans cette leçon, nous bloquons sur des clés comme le code postal ou le début du nom de famille. Nous combinons des clés et faisons glisser une fenêtre sur des enregistrements triés.
Leçon 9 sur 29 · Résolution d'entités et appariement d'enregistrements : est-ce la même chose?Clés de blocage et voisinage trié
1. Le problème de l'appariement
2. Nettoyer d'abord, puis apparier exactement
3. Le blocage : ne pas tout comparer
4. Comparer les enregistrements : les mesures de similarité
5. L'appariement probabiliste
6. L'appariement appris : classificateurs, plongements et modèles de langage
7. Des paires aux entités
8. L'appariement en production
Ce que vous saurez faire
Créez des paires candidates avec des clés de blocage. Construisez des clés à partir de plusieurs champs, mesurez chacune et combinez-les. Ainsi, une clé trouve ce qu’une autre manque. Essayez ensuite une deuxième méthode qui ne demande aucune clé exacte : une fenêtre glissante sur des noms triés.
Carnet JupyterConstruire et mesurer des clés dans un carnet Jupyter
Le carnet (notebook) Jupyter construit les cinq clés du projet avec pandas. Vous mesurez chaque clé, les combinez et écrivez vous-même un blocage par voisinage trié. Ses cellules de préparation téléchargent les données. Il ne demande donc aucune préparation locale.
Le carnet est en anglais. Colab et Kaggle ouvrent votre propre copie. Il faut un compte Google ou Kaggle gratuit. Vous êtes bloqué ? Consultez le carnet de solution.
Avant de commencerCe qu’il faut savoir et avoir sous la main
Ce que vous devez savoir
- Les paires candidates, les clés de blocage, l’exhaustivité des paires (pair completeness) et le taux de réduction, vus dans Pourquoi comparer toutes les paires est impossible.
- Le nom, le courriel, le téléphone, le code postal et la date de naissance nettoyés de chaque enregistrement, vus dans Normaliser et Découper en parties.
Ce qu’il vous faut sur votre ordinateur
- Le projet
larkfield-matchavec la commande de la dernière leçon. Ou utilisez seulement le carnet.
Testé sur macOS avec Python 3.12.13. Les commandes Windows (PowerShell) ne sont pas testées.
Deux façons de trouver un livre
Section intitulée « Deux façons de trouver un livre »Une bibliothèque possède un catalogue sur fiches. Chaque livre a une fiche dans les tiroirs auteur, triée par nom de famille de l’auteur. Il a une deuxième fiche dans les tiroirs titre.
Pourquoi deux? Un lecteur peut se rappeler l’auteur, mais pas le titre. Un autre se rappelle le titre, mais écrit mal le nom de l’auteur. Avec un seul ensemble de tiroirs, le deuxième lecteur ne trouve rien. Avec deux, l’un ou l’autre souvenir suffit.
Les clés de blocage fonctionnent de la même façon. Une clé correspond à un ensemble de tiroirs. Deux enregistrements d’un même client doivent partager une clé pour se retrouver ensemble. Ils n’ont pas besoin de toutes les partager.
Le problème : une seule clé manque toujours quelqu’un
Section intitulée « Le problème : une seule clé manque toujours quelqu’un »La dernière leçon utilisait un blocage sur le code postal. Elle perdait 4 289 vraies paires : 15,5 % de toutes les vraies paires. Lesquelles? Dans chacune, les deux enregistrements ont des codes postaux différents. La plupart concernent des clients qui ont déménagé. Un enregistrement porte l’ancien code postal, l’autre le nouveau. Dans nos données synthétiques, environ 28 % des personnes ont déménagé.
Essayez plutôt une autre clé unique. Chaque clé perd un groupe différent de clients :
- Une clé
- Plusieurs clés combinées
Description textuelle du graphique
Un graphique à points avec sept lignes, un point par blocage, sur un axe de 0 à 1. Une clé : code postal 0,845, nom de famille 0,849, téléphone 0,494, courriel 0,451, date de naissance (avec la première lettre du prénom) 0,235. Plusieurs clés : code postal ou nom de famille 0,976; les cinq clés combinées 0,994.
- Le courriel ne conserve que 0,451 des vraies paires. Les jardineries laissent le courriel vide dans la plupart des enregistrements. Certains clients utilisent un courriel familial dans une liste et leur propre courriel dans une autre.
- Le téléphone en conserve 0,494. Le magasin laisse le téléphone vide dans 30 % des enregistrements.
- La date de naissance en conserve 0,235. La plupart des enregistrements des jardineries et du magasin n’ont pas de date de naissance.
- La clé du nom de famille en conserve 0,849. Elle perd les clients dont les premières lettres du nom contiennent une faute de frappe. Elle perd aussi ceux dont le prénom est remplacé par un surnom.
Aucune clé seule ne suffit. Mais regardez les deux dernières lignes : les clés combinées en conservent beaucoup plus.
Construire une clé
Section intitulée « Construire une clé »Une clé est un court texte construit à partir des valeurs nettoyées d’un enregistrement. Elle doit être identique pour deux enregistrements d’un même client, et différente pour la plupart des autres enregistrements.
Le code postal est déjà une clé. La clé du nom de famille demande plus de travail. Le projet la construit en deux parties :
clé du nom de famille = les 4 premières lettres du nom de famille + « | » + les 2 premières lettres du prénom
Pour Samuel Green, cela donne gree|sa. Pour Jacques Beaulieu, beau|ja. Le | sépare simplement les parties.
Clés étroites et clés larges
Section intitulée « Clés étroites et clés larges »Pourquoi 4 lettres, et pourquoi ajouter le prénom? À cause de la taille des blocs. Un bloc de k enregistrements produit k × (k − 1) / 2 paires. Un seul gros bloc peut produire plus de paires que tous les petits blocs réunis.
Nous avons compté les paires que chaque clé produirait sur les enregistrements de TermeLarkfieldUne boutique en ligne canadienne inventée, qui vend des articles pour la maison et le jardin. Ce n’est pas une vraie entreprise. Tous les cours Nextia utilisent son service d’assistance et ses données comme exemple.En savoir plus Découvrez Larkfield. Nous les avons comptées à partir des tailles des blocs, sans les construire :
| Clé | Valeurs différentes | Plus gros bloc | Paires |
|---|---|---|---|
| La liste source (magasin, fidélité, jardinerie) | 3 | 31 128 | 700 893 447 |
| La première lettre du nom de famille | 23 | 5 780 | 120 104 444 |
| Les 4 premières lettres du nom de famille | 1 027 | 2 381 | 24 624 225 |
| 4 lettres du nom de famille + 2 du prénom | 7 499 | 316 | 1 035 498 |
| Le code postal | 22 727 | 16 | 89 630 |
Une clé large a peu de valeurs et de gros blocs. Elle conserve beaucoup de vraies paires, mais produit trop de paires candidates. Une clé étroite a beaucoup de valeurs et de petits blocs. Elle produit peu de paires, mais une petite différence place deux enregistrements dans des blocs différents. Les deux lettres du prénom produisent environ 24 fois moins de paires. Le plus gros bloc est maintenant trem|ma : 316 enregistrements dont le nom de famille commence par « trem » et le prénom par « ma ».
Les clés ont besoin de valeurs nettoyées
Section intitulée « Les clés ont besoin de valeurs nettoyées »Une clé compare des valeurs exactes. Construisez-la donc à partir des valeurs nettoyées du module 2, et non des valeurs saisies. TREMBLAY, VAL et Valérie Tremblay donnent la même clé seulement après normalisation : sans majuscules ni accents, avec le nom de famille séparé du prénom. Ici, un prénom court reste utile : « val » et « valérie » commencent tous deux par va.
Plusieurs clés combinées
Section intitulée « Plusieurs clés combinées »Combinez maintenant les clés, comme la bibliothèque combine ses tiroirs. Une paire est candidate quand les deux enregistrements partagent au moins une des clés. Dans le langage des ensembles, les paires candidates sont l’union des paires de chaque clé.
Le diagramme le montre sur les six enregistrements de la dernière leçon.
Description textuelle du diagramme
Les six enregistrements à nouveau : les quatre de Samuel Green (1 à 4), son frère Nathan (5) et Jacques Beaulieu (6). Le code postal place les enregistrements 1, 2, 3 et 5 dans un bloc : 6 paires, dont 3 vraies. L’enregistrement 4, l’ancien enregistrement de Samuel, est seul. La clé du nom de famille place les quatre enregistrements de Samuel dans le bloc gree|sa : 6 paires, toutes vraies. Nathan est seul dans gree|na, car son prénom commence par « na ». Ensemble, les deux clés produisent 9 paires candidates : les 6 paires entre les enregistrements de Samuel et 3 paires de Nathan avec Samuel. Les 6 vraies paires sont conservées.
Dans cet exemple, la clé du nom de famille conserve déjà toutes les vraies paires à elle seule. Sur les données complètes, ce n’est pas le cas. Chaque clé trouve des vraies paires que l’autre perd. Le code postal seul conserve 0,845 des vraies paires. La clé du nom de famille seule en conserve 0,849. Ensemble, elles en conservent 0,976.
Le coût est faible, car la plupart des paires produites par les deux clés sont différentes. Ensemble, elles produisent 1 103 620 paires candidates : seulement 68 122 de plus que la clé du nom de famille seule.
Les cinq clés du projet
Section intitulée « Les cinq clés du projet »Le blocage par défaut du projet, keys, combine cinq clés :
- le code postal
- le courriel
- le téléphone
- la clé du nom de famille (4 lettres du nom de famille, 2 du prénom)
- la date de naissance avec la première lettre du prénom
Chaque clé seule conserve entre 0,235 et 0,849 des vraies paires. Ensemble, elles en conservent 0,9937, avec 1 108 591 paires candidates. La date de naissance reçoit la première lettre du prénom, car beaucoup de personnes partagent une date d’anniversaire. La lettre garde les blocs petits.
C’est la même idée qu’un index inversé en recherche : pour chaque valeur de clé, une liste des enregistrements qui la possèdent. Recherche et classement : trouver la meilleure correspondance en construit un dans L’index inversé.
Exécuter le blocage dans le projet
Section intitulée « Exécuter le blocage dans le projet »Ajoutez le code de blocage de ce module à votre projet.
-
Dans le dossier de votre projet, avec l’TermeEnvironnement virtuelUn dossier avec son propre Python et ses propres paquets, pour un seul projet. Les paquets installés là ne changent pas les autres projets.En savoir plus Isoler les dépendancesPython pour l'ingénierie de l'IA en pratique actif, copiez les fichiers de blocage de l’instantané
end-of-m03. Copiez aussi ses fichiersrequirements.txtetREADME.md:Fenêtre de terminal S=../nextia-learning-labs/C39/snapshots/end-of-m03cp $S/larkfield_match/blocking.py larkfield_match/cp $S/larkfield_match/commands/block.py larkfield_match/commands/cp $S/tests/test_blocking.py tests/cp $S/requirements.txt $S/README.md .Fenêtre de terminal $S = "..\nextia-learning-labs\C39\snapshots\end-of-m03"Copy-Item $S\larkfield_match\blocking.py larkfield_match\Copy-Item $S\larkfield_match\commands\block.py larkfield_match\commands\Copy-Item $S\tests\test_blocking.py tests\Copy-Item $S\requirements.txt, $S\README.md .blocking.pycontient aussi le code MinHash de la prochaine leçon. Le nouveaurequirements.txtajoute un paquet pour ce code :datasketch. -
Installez le nouveau paquet :
Fenêtre de terminal python -m pip install -r requirements.txtLa dernière ligne nomme les nouveaux paquets :
Successfully installed datasketch-2.0.0 scipy-1.18.1 -
Exécutez les tests. Il y en a maintenant 21 :
Fenêtre de terminal python -m pytest -q..................... [100%]21 passed in 5.05s -
Listez les blocages que le projet connaît :
Fenêtre de terminal match block --listpostcode customers same postcodesurname customers same first 4 letters of the surname and first 2 of the first namesurname-wide customers same first 4 letters of the surname and first letter of the first nameemail customers same emailphone customers same phonedob customers same date of birth and first letter of the first namepostcode+surname customers postcode, or surname startkeys customers postcode, email, phone, surname start or date of birth (the default)keys+street customers the default keys and the street number with the start of the streetsorted-name customers sorted neighbourhood on the full name, window 10sorted-name-50 customers sorted neighbourhood on the full name, window 50keys-wide customers the default keys with the wider surname keyp-brand products same brandp-minhash products MinHash LSH on title shingles (threshold 0.5)p-minhash-0.3 products MinHash LSH on title shingles (threshold 0.3)p-minhash+gtin products MinHash LSH (0.5) or the same barcode
Créez maintenant les paires candidates d’une clé, puis de deux clés, puis de cinq :
match block --blocking surnamematch block --blocking postcode+surnamematch block --blocking keyssurname: 1,035,498 candidate pairs out of 1,806,455,778 possible pairs (4.91 s) pair completeness 0.849 (23,489 of 27,677 true pairs kept); reduction ratio 0.999427postcode+surname: 1,103,620 candidate pairs out of 1,806,455,778 possible pairs (4.29 s) pair completeness 0.976 (27,019 of 27,677 true pairs kept); reduction ratio 0.999389keys: 1,108,591 candidate pairs out of 1,806,455,778 possible pairs (6.0 s) pair completeness 0.994 (27,503 of 27,677 true pairs kept); reduction ratio 0.999386Notre ordinateur portable était occupé pendant cette exécution, donc les durées sont longues. Sur un ordinateur portable peu occupé, keys prenait 0,24 seconde. Vos durées seront différentes; les décomptes ne changeront pas. Chaque exécution sauvegarde ses paires dans outputs/candidates/, pour les modules suivants.
Comment le code produit les paires
Section intitulée « Comment le code produit les paires »Ouvrez larkfield_match/blocking.py. La fonction key_pairs produit les paires de chaque colonne de clé et réunit les listes :
def key_pairs(keys, cols): parts = [same_value_pairs(keys, c) for c in cols] return pd.concat(parts).drop_duplicates(["record_id_l", "record_id_r"]).reset_index(drop=True)same_value_pairs joint la table des clés à elle-même sur une colonne. Elle conserve chaque paire une seule fois, avec le plus petit identifiant d’enregistrement en premier. Une paire trouvée par deux clés n’est conservée qu’une fois : c’est ce que fait drop_duplicates.
Voisinage trié : aucune clé exacte nécessaire
Section intitulée « Voisinage trié : aucune clé exacte nécessaire »Une clé demande une correspondance exacte. « gagnon » et « gagnoj » donnent des blocs différents. Peut-on apparier des enregistrements qui sont seulement proches?
Pensez encore aux tiroirs d’auteurs de la bibliothèque. Un lecteur cherche « Gagnon ». La fiche indique « Gagnoj » par erreur. Elle n’est pas sous « Gagnon », mais juste à côté. Un lecteur qui regarde les quelques fiches autour de cet endroit la trouve quand même.
Le voisinage trié fait cela. Triez tous les enregistrements selon une valeur, comme le nom complet. Faites ensuite glisser une fenêtre de w enregistrements le long de la liste triée. Appariez chaque enregistrement aux w − 1 enregistrements qui le suivent.
Description textuelle du diagramme
Les six enregistrements triés par nom : Jacques Beaulieu d’abord, puis Nathan Green, puis les quatre enregistrements de Samuel Green, dans l’ordre de leurs identifiants. Une fenêtre de 3 enregistrements glisse le long de la liste. Chaque enregistrement est apparié aux deux suivants. Cela produit 9 paires candidates : 1–2, 1–3, 2–3, 2–4, 3–4, 3–5, 4–5, 4–6 et 5–6. Cinq d’entre elles apparient Samuel à lui-même. Une vraie paire est perdue : les positions 3 et 6, les enregistrements G-001688 et S-007770 de Samuel, sont séparées de trois places.
Une fenêtre de w produit environ n × (w − 1) paires. Ce nombre augmente avec le nombre d’enregistrements, et non avec son carré. Avec une fenêtre de 10, les 60 108 enregistrements de Larkfield donnent 540 927 paires.
Voisinage trié sur les noms de Larkfield
Section intitulée « Voisinage trié sur les noms de Larkfield »match block --blocking sorted-namematch block --blocking sorted-name-50sorted-name: 540,927 candidate pairs out of 1,806,455,778 possible pairs (1.4 s) pair completeness 0.543 (15,023 of 27,677 true pairs kept); reduction ratio 0.999701sorted-name-50: 2,944,067 candidate pairs out of 1,806,455,778 possible pairs (7.85 s) pair completeness 0.800 (22,144 of 27,677 true pairs kept); reduction ratio 0.998370Le résultat est mauvais. Une fenêtre de 10 ne conserve que 0,543 des vraies paires. Une fenêtre de 50 en conserve 0,800, avec 2,9 millions de paires. C’est plus de paires que les cinq clés, et beaucoup moins de vraies paires.
Pourquoi? Regardez l’ordre de tri. Le nom complet commence par le prénom : samuel green. La liste est donc triée d’abord par prénom. « Samuel Green » et « Sam Green » sont éloignés : tous les « Samuel » avec un autre nom de famille les séparent. Les noms courants produisent de longues séquences de valeurs égales. Dans une longue séquence, les enregistrements d’une vraie paire sont souvent séparés de plus de w places.
Le voisinage trié fonctionne mieux quand :
- les erreurs de la valeur de tri se trouvent près de la fin, pas au début (une faute de frappe dans « Gagnon » à la dernière lettre, pas à la première);
- les valeurs sont rares, donc les valeurs égales produisent de courtes séquences;
- vous ne pouvez pas construire une bonne clé exacte.
Une correction courante consiste à faire plusieurs passages, chacun trié selon une autre valeur : nom de famille, puis code postal, puis téléphone. L’union des passages forme le blocage, comme avec les clés.
Quand utiliser chaque méthode
Section intitulée « Quand utiliser chaque méthode »| Méthode | Utilisez-la quand | Ce qu’elle coûte |
|---|---|---|
| Une clé | un champ est fiable et vous voulez un premier essai rapide | elle perd toute vraie paire dont le champ diffère ou est vide |
| Plusieurs clés combinées | le choix par défaut pour les enregistrements de clients | plus de paires candidates; chaque clé doit être mesurée |
| Voisinage trié | aucune clé exacte ne fonctionne et les erreurs sont à la fin d’une valeur | les vraies paires dans de longues séquences de valeurs courantes sont perdues |
La taille de la fenêtre et la largeur de la clé jouent le même rôle. Elles font un compromis entre paires candidates et vraies paires. Choisissez-les par la mesure, et non par intuition.
Erreur courante
Une clé sur un champ souvent vide
Symptôme : TermeTomásL’ingénieur en IA de Larkfield. Il propose souvent un raccourci rapide, et la leçon montre pourquoi il échoue. bloque sur la date de naissance : « Une personne a une seule date d’anniversaire, donc cette clé ne peut pas se tromper. » Il obtient seulement 8 757 paires candidates, et l’apparieur trouve très peu de clients.
dob: 8,757 candidate pairs out of 1,806,455,778 possible pairs (1.77 s) pair completeness 0.235 (6,495 of 27,677 true pairs kept); reduction ratio 0.999995Cause : la clé est correcte lorsqu’elle existe, mais elle est souvent vide. Les jardineries n’ont pas de date de naissance dans 84,7 % de leurs enregistrements, et le magasin dans 54,6 %. Un enregistrement dont la clé est vide n’appartient à aucun bloc. Il n’est donc jamais comparé. L’exhaustivité des paires est de 0,235 : 77 % des vraies paires sont perdues avant toute comparaison.
Correction : ne bloquez jamais sur un seul champ. Utilisez la date de naissance comme une clé parmi plusieurs, comme le fait keys dans le projet. Avant de choisir une clé, vérifiez aussi à quelle fréquence son champ est vide dans chaque source. C’est ce que montre Découvrir les enregistrements.
Conséquence dans le travail en IA : une valeur vide n’est pas un désaccord, mais ce n’est pas non plus un accord. Une clé qui ignore les valeurs vides retire silencieusement des groupes entiers d’enregistrements. Ici, elle retire la plupart des clients des jardineries.
Vérification des connaissances
Section intitulée « Vérification des connaissances »Vérifiez votre compréhension
Le code postal conserve 0,845 des vraies paires et la clé de nom de famille, 0,849. Ensemble, elles en conservent 0,976. Pourquoi ce résultat dépasse-t-il autant celui de chaque clé seule? Pourquoi ne coûte-t-il que 68 122 paires candidates de plus que la clé de nom de famille?
Afficher la réponse
Les deux clés perdent des vraies paires différentes. Le code postal perd les clients qui ont déménagé. La plupart gardent leur nom de famille et leur prénom, donc la clé de nom de famille les retrouve. La clé de nom de famille perd les noms dont les premières lettres contiennent une erreur. La plupart de ces clients gardent leur code postal. Une paire est candidate quand ses enregistrements partagent l’une ou l’autre des clés. Elle n’est donc perdue que si les deux clés échouent. Le coût est faible parce que les clés trouvent beaucoup de paires identiques. Deux enregistrements d’un même ménage partagent souvent le code postal et le nom de famille. Chaque paire compte une seule fois.
Votre réponse contient-elle les points principaux de la nôtre ?
Connectez-vous et inscrivez-vous au cours pour enregistrer vos réponses. Chaque vérification compte pour le certificat.
Vérifiez votre compréhension
La première lettre du nom de famille produit 120 104 444 paires. Les 4 premières lettres, plus 2 lettres du prénom, en produisent 1 035 498. Pourquoi la première clé est-elle tellement moins bonne, malgré une exhaustivité des paires plus élevée?
Afficher la réponse
La première lettre n’a que 23 valeurs, donc les blocs sont grands : le plus grand contient 5 780 enregistrements. Un bloc de k enregistrements produit k × (k − 1) / 2 paires. Les grands blocs produisent donc un nombre énorme de paires. Comparer 120 millions de paires et les garder en mémoire n’est pas possible. La clé plus précise a 7 499 valeurs, et son plus grand bloc contient 316 enregistrements. Elle perd un peu plus de vraies paires, mais produit 116 fois moins de paires candidates. Les autres clés retrouvent la plupart des paires qu’elle perd.
Votre réponse contient-elle les points principaux de la nôtre ?
Connectez-vous et inscrivez-vous au cours pour enregistrer vos réponses. Chaque vérification compte pour le certificat.
Vérifiez votre compréhension
Un collègue veut remplacer la clé de courriel par un voisinage trié sur le courriel, avec une fenêtre de 5. Nommez une vraie paire que cette méthode retrouverait, mais que la clé manquerait, et une paire que les deux manqueraient.
Afficher la réponse
Elle retrouve un courriel avec une faute de frappe vers la fin, par exemple mariepaquette@… et mariepaqquette@…. Dans le tri par courriel, les deux se retrouvent proches. La clé exacte de courriel les manque. Les deux méthodes manquent une cliente qui utilise le courriel familial thebouchards@example.org dans une liste et son propre courriel cbouchard@post.example dans une autre. Les deux courriels sont éloignés dans le tri et ne sont pas identiques. Les deux méthodes manquent aussi tous les enregistrements dont le courriel est vide.
Votre réponse contient-elle les points principaux de la nôtre ?
Connectez-vous et inscrivez-vous au cours pour enregistrer vos réponses. Chaque vérification compte pour le certificat.
Récapitulatif
- Une clé de blocage est une valeur courte créée à partir de champs nettoyés. La clé de nom de famille combine les 4 premières lettres du nom de famille et les 2 premières du prénom.
- Les clés larges produisent d’énormes blocs : un bloc de k enregistrements produit k × (k − 1) / 2 paires. Les clés précises perdent des vraies paires à cause de petites différences.
- Les clés ensemble retrouvent ce qu’une seule clé manque. Les cinq clés du projet conservent 0,9937 des vraies paires avec 1 108 591 candidats. Le code postal seul en conserve 0,845; avec la clé de nom de famille, 0,976.
- Le voisinage trié apparie chaque enregistrement avec les w − 1 suivants dans une liste triée. Sur les noms de Larkfield, il ne conserve que 0,543 (fenêtre de 10) et 0,800 (fenêtre de 50).
- Une clé sur un champ souvent vide, comme la date de naissance, perd la plupart des vraies paires.
Les clés fonctionnent pour les noms et les codes postaux. Mais deux titres de produits décrivant un même boyau partagent rarement une valeur exacte. Ensuite, MinHash et LSH trouvent des titres semblables sans comparer toutes les paires.
Leçon suivante : MinHash et LSH