Aller au contenu
English

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.

Lue depuis YouTube. Rien ne se charge depuis YouTube avant que vous appuyiez sur lecture. Confidentialité

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 JupyterColab · Kaggle · GitHub · en anglais

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 mainEnviron 40 minutes

Ce que vous devez savoir

Ce qu’il vous faut sur votre ordinateur

  • Le projet larkfield-match avec 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.

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
La part des vraies paires que chaque clé conserve, sur les 60 108 enregistrements synthétiques. Clé du nom de famille = les 4 premières lettres du nom de famille et les 2 premières du prénom. Cinq clés = les clés par défaut du projet.
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.

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.

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 ».

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.

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.

Les six enregistrements avec leur code postal et leur clé du nom de famille. Clé 1, code postal : le bloc M7K4L8 contient les enregistrements 1, 2, 3 et 5 et produit 6 paires; L0H6T9 contient l'enregistrement 4 et J8Y1L3 l'enregistrement 6, sans paires. 6 paires candidates, 3 vraies paires sur 6 conservées. Clé 2, début du nom de famille : le bloc gree|sa contient les enregistrements 1, 2, 3 et 4 et produit 6 paires; gree|na contient l'enregistrement 5 et beau|ja l'enregistrement 6, sans paires. 6 paires candidates, 6 vraies paires sur 6 conservées. Les deux clés combinées : une paire est candidate quand elle partage la clé 1 ou la clé 2 : 9 paires candidates, 6 vraies paires sur 6 conservées.
Les six enregistrements de la dernière leçon, avec un blocage sur deux clés. Chaque clé produit ses propres blocs. Ensemble, elles produisent 9 paires candidates et conservent les 6 vraies paires.
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.

Le blocage par défaut du projet, keys, combine cinq clés :

  1. le code postal
  2. le courriel
  3. le téléphone
  4. la clé du nom de famille (4 lettres du nom de famille, 2 du prénom)
  5. 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é.

Ajoutez le code de blocage de ce module à votre projet.

  1. 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 fichiers requirements.txt et README.md :

    Fenêtre de terminal
    S=../nextia-learning-labs/C39/snapshots/end-of-m03
    cp $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 .

    blocking.py contient aussi le code MinHash de la prochaine leçon. Le nouveau requirements.txt ajoute un paquet pour ce code : datasketch.

  2. Installez le nouveau paquet :

    Fenêtre de terminal
    python -m pip install -r requirements.txt

    La dernière ligne nomme les nouveaux paquets :

    Successfully installed datasketch-2.0.0 scipy-1.18.1
  3. Exécutez les tests. Il y en a maintenant 21 :

    Fenêtre de terminal
    python -m pytest -q
    ..................... [100%]
    21 passed in 5.05s
  4. Listez les blocages que le projet connaît :

    Fenêtre de terminal
    match block --list
    postcode customers same postcode
    surname customers same first 4 letters of the surname and first 2 of the first name
    surname-wide customers same first 4 letters of the surname and first letter of the first name
    email customers same email
    phone customers same phone
    dob customers same date of birth and first letter of the first name
    postcode+surname customers postcode, or surname start
    keys 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 street
    sorted-name customers sorted neighbourhood on the full name, window 10
    sorted-name-50 customers sorted neighbourhood on the full name, window 50
    keys-wide customers the default keys with the wider surname key
    p-brand products same brand
    p-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 :

Fenêtre de terminal
match block --blocking surname
match block --blocking postcode+surname
match block --blocking keys
surname: 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.999427
postcode+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.999389
keys: 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.999386

Notre 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.

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.

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.

Étape 1 : les six enregistrements triés par nom : 1 jacques beaulieu (G-009906), 2 nathan green (G-002894), 3 samuel green (G-001688), 4 samuel green (G-008438), 5 samuel green (L-011126), 6 samuel green (S-007770). Des encadrés en pointillés montrent des fenêtres de 3, une par ligne de départ. Étape 2 : les paires dans chaque fenêtre : 1-2, 1-3, 2-3, 2-4, 3-4, 3-5, 4-5, 4-6, 5-6; les cinq dernières concernent la même personne. Fenêtre de 3 : chaque enregistrement est apparié aux 2 suivants. 9 paires candidates, 5 vraies paires sur 6 conservées. Perdue : 3-6, la même personne, mais trop éloignée dans la liste.
Voisinage trié avec une fenêtre de 3, sur les mêmes six enregistrements. Les nombres sont ici les positions dans la liste triée. Aucune clé ne doit être égale, mais une vraie paire éloignée après le tri est perdue.
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.

Fenêtre de terminal
match block --blocking sorted-name
match block --blocking sorted-name-50
sorted-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.999701
sorted-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.998370

Le 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.

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.999995

Cause : 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é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.

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.

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.

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