Aller au contenu
English

Pourquoi comparer toutes les paires est impossible

  • Leçon 8
  • 30 min
  • Module 3 : Le blocage : ne pas tout comparer

Où nous en sommes

Nous avons mesuré les règles exactes sur tous nos enregistrements. Un apparieur approximatif doit comparer des enregistrements différents, et les paires sont très nombreuses. Dans cette leçon, nous comptons les paires, chronométrons leur comparaison sur un portable et découvrons les paires candidates.

Lue depuis YouTube. Rien ne se charge depuis YouTube avant que vous appuyiez sur lecture. Confidentialité
Leçon 8 sur 29 · Résolution d'entités et appariement d'enregistrements : est-ce la même chose?Pourquoi comparer toutes les paires est impossible

Ce que vous saurez faire

Voyez pourquoi un apparieur ne peut pas comparer chaque enregistrement avec tous les autres. Comptez les paires et chronométrez leur comparaison sur votre portable. Découvrez l’idée sur laquelle repose le reste de ce module : les paires candidates.

Carnet JupyterCompter, chronométrer et bloquer dans un carnet JupyterColab · Kaggle · GitHub · en anglais

Le carnet (notebook) Jupyter compte les paires d’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 et chronomètre une petite comparaison. Ensuite, vous créez votre première clé de blocage et mesurez ce qu’elle conserve. Ses cellules de préparation téléchargent les données, donc aucune configuration locale n’est nécessaire.

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 30 minutes

Ce que vous devez savoir

Ce qu’il vous faut sur votre ordinateur

  • Le projet larkfield-match à la fin du module 2, comme dans Découvrir les enregistrements, avec son environnement virtuel activé. Ou utilisez seulement le carnet.

Testé sur macOS avec Python 3.12.13. Les commandes Windows (PowerShell) s’écrivent de la même façon, mais nous ne les avons pas testées.

Reprenons la clinique. La nouvelle commis doit trouver chaque patient qui a deux fiches. Elle a 600 fiches. Elle pourrait comparer la fiche 1 avec chacune des 599 autres fiches. Puis la fiche 2 avec les 598 fiches suivantes. Et ainsi de suite, jusqu’à la fin.

Cela fait 179 700 comparaisons. À une comparaison par seconde, il lui faut environ 50 heures.

Elle ne fait pas cela. Elle répartit les fiches dans des tiroirs selon les premières lettres du nom de famille. Puis elle compare seulement les fiches d’un même tiroir. Elle ne compare jamais « Gagnon » avec « Smith ». Cela lui prend un après-midi.

Elle peut manquer un patient. Supposons qu’une fiche indique « Gagnon » et que l’autre contient une faute de frappe dans la première lettre. Les deux fiches se retrouvent dans des tiroirs différents. Elle accepte ce risque, car l’autre méthode n’en finit pas.

Un apparieur a le même problème et utilise la même idée.

Un apparieur décide « identique ou non » pour une paire d’enregistrements. Pour trouver chaque client ayant deux enregistrements, il doit examiner chaque paire pouvant représenter un seul client.

Combien de paires n enregistrements donnent-ils? L’enregistrement 1 forme une paire avec chacun des n − 1 autres. L’enregistrement 2 forme une paire avec chacun des n − 2 suivants. Additionnez ces nombres et vous obtenez :

paires = n × (n − 1) / 2

Regardez d’abord un tout petit exemple. Six enregistrements des données synthétiques de Larkfield : quatre de Samuel Green, un de son frère Nathan et un de Jacques Beaulieu. Vous avez rencontré Samuel et Nathan dans Découvrir les enregistrements.

Six enregistrements à gauche : 1 G-001688 samuel green M7K4L8, 2 L-011126 samuel green M7K4L8, 3 S-007770 samuel green M7K4L8, 4 G-008438 samuel green L0H6T9, 5 G-002894 nathan green M7K4L8, 6 G-009906 jacques beaulieu J8Y1L3. Les enregistrements 1 à 4 représentent Samuel, l'enregistrement 5 représente son frère Nathan et l'enregistrement 6 représente Jacques. Une grille triangulaire contient une case pour chacune des 15 paires. Six cases indiquent la même personne : 1-2, 1-3 et 2-3 ont une bordure épaisse, car les deux enregistrements partagent un code postal; 1-4, 2-4 et 3-4 ont une bordure pointillée, car l'enregistrement 4 a un autre code postal. Les cases 1-5, 2-5 et 3-5 sont bleu pâle : deux personnes ayant le même code postal. Les six autres cases sont blanches. En dessous : 6 enregistrements donnent 15 paires, dont 6 vraies paires; le même code postal donne 6 paires candidates et conserve 3 des 6 vraies paires.
Six enregistrements donnent 15 paires. Comparer seulement les enregistrements ayant le même code postal laisse 6 paires et conserve 3 des 6 vraies paires. Les valeurs sont les valeurs nettoyées du module 2 (enregistrements synthétiques).
Description textuelle du diagramme

Six enregistrements à gauche : quatre de Samuel Green (enregistrements 1 à 4), un de son frère Nathan (enregistrement 5) et un de Jacques Beaulieu (enregistrement 6). L’enregistrement 4 est l’ancien enregistrement de Samuel, avec le code postal L0H6T9; les autres enregistrements Green ont M7K4L8. La grille triangulaire contient une case par paire : 15 cases. Six cases sont de vraies paires, celles parmi les quatre enregistrements de Samuel. Trois ont une bordure épaisse : les deux enregistrements ont le code postal M7K4L8. Trois ont une bordure pointillée : elles incluent l’enregistrement 4, avec son ancien code postal. Trois cases bleu pâle associent Nathan à un enregistrement de Samuel : deux personnes ayant le même code postal. Les six autres cases sont blanches : des personnes différentes et des codes postaux différents.

Six enregistrements donnent 6 × 5 / 2 = 15 paires. Seulement 6 sont de vraies paires. Cela représente déjà 40 % des paires, parce que nous avons choisi cet exemple. Dans les vraies données, les vraies paires sont très rares.

Utilisons maintenant les nombres de Larkfield. Il y a 60 108 enregistrements de clients :

60 108 × 60 107 / 2 = 1 806 455 778 paires, soit environ 1,8 milliard.

Seulement 27 677 de ces paires sont de vraies paires. Cela représente environ 1 paire sur 65 000. Presque toutes les paires que l’apparieur compare représentent deux personnes différentes.

Le nombre de paires augmente avec le carré du nombre d’enregistrements. Dix fois plus d’enregistrements donnent environ cent fois plus de paires. Le graphique montre cette courbe.

Le nombre de paires est n × (n − 1) / 2 : il augmente avec le carré du nombre d'enregistrements. Cette courbe est calculée à partir de la formule, et non mesurée.
Description textuelle du graphique

Un graphique en courbe. L’axe horizontal indique le nombre d’enregistrements, de 0 à 100 000. L’axe vertical indique le nombre de paires, de 0 à 5 milliards. La courbe est plate au début, puis monte fortement. À 10 000 enregistrements, elle atteint 0,05 milliard de paires; à 60 108 enregistrements, les données de Larkfield, 1,8 milliard; à 100 000 enregistrements, 5 milliards.

Doubler les enregistrements de Larkfield ne doublerait pas le travail. Cela le multiplierait par environ quatre.

Un décompte ne vous indique pas le temps nécessaire. Mesurez-le donc. Le projet contient une commande pour cela dans le module 3. Elle chronomètre une toute petite comparaison sur 200 000 paires aléatoires, puis multiplie le résultat.

  1. Assurez-vous d’avoir les fichiers du cours les plus récents. Dans le dossier contenant nextia-learning-labs et larkfield-match, exécutez :

    Fenêtre de terminal
    git -C nextia-learning-labs pull

    Si vous avez utilisé le fichier ZIP, téléchargez-le de nouveau.

  2. Allez 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 activé. Copiez le fichier de commande de cette leçon depuis l’instantané end-of-m03 :

    Fenêtre de terminal
    cd larkfield-match
    cp ../nextia-learning-labs/C39/snapshots/end-of-m03/larkfield_match/commands/allpairs.py larkfield_match/commands/

    La commande match trouve ses sous-commandes grâce à leurs fichiers. La nouvelle commande fonctionne donc immédiatement.

  3. Exécutez-la :

    Fenêtre de terminal
    match allpairs
    60,108 records -> 1,806,455,778 pairs
    Timed 200,000 random pairs: 7.06 microseconds per pair (one CPU core)
    All pairs would take about 3.5 hours for one simple comparison of the names
    Only to store the pairs as two 4-byte numbers each: 14.5 GB of memory

Votre temps sera différent. Nous l’avons exécutée sur un portable occupé par d’autres tâches. Sur le même portable sans autre tâche, la commande affichait 2,04 microsecondes par paire et « environ 1,0 heure ». Une microseconde est un millionième de seconde.

La comparaison dans match allpairs est minuscule. Elle vérifie seulement combien de lettres deux noms ont en commun. Un véritable apparieur compare cinq champs ou plus, et chaque comparaison est plus lente. Le temps réel est donc de nombreuses heures, et non une seule.

Une bibliothèque rapide aide, mais pas assez. Nous avons chronométré la similarité de Jaro–Winkler de la bibliothèque rapidfuzz, que vous découvrirez dans le module 4. Elle nécessite 0,34 microseconde par paire. Comparer toutes les paires prendrait encore 0,17 heure, pour un seul champ. Et il faut comparer les paires de nouveau après chaque modification de l’apparieur.

La dernière ligne est pire. Simplement conserver les paires, chacune sous forme de deux numéros d’enregistrement, nécessite 14,5 Go de mémoire. Le portable du cours a 16 Go au total. Un apparieur qui construit toutes les paires remplit la mémoire avant de comparer quoi que ce soit. L’ordinateur devient alors très lent, ou le programme s’arrête.

Et Larkfield est une petite entreprise. Une entreprise ayant 1 million d’enregistrements a environ 500 milliards de paires.

La plupart des paires ne méritent pas d’être examinées. Prenez un client de Montréal et un client de l’Ontario sans nom, courriel, téléphone ni code postal en commun. Aucun apparieur raisonnable ne dirait qu’il s’agit d’une seule personne. Ne les comparez donc pas.

Une paire candidate est une paire qui pourrait représenter un seul client. Un apparieur compare seulement les paires candidates. Il considère toutes les autres paires comme « différentes » sans les examiner.

Le blocage est l’étape qui choisit les paires candidates. Le nom vient des tiroirs de la clinique : les enregistrements vont dans des blocs. Seuls les enregistrements d’un même bloc sont comparés. Dans les étapes d’un apparieur, le blocage vient après la normalisation et avant la comparaison.

La façon la plus simple de créer des blocs est une clé de blocage. C’est une valeur que les enregistrements d’un même client partagent habituellement. Par exemple, le code postal. Deux enregistrements deviennent une paire candidate quand ils ont la même clé.

Regardez de nouveau les six enregistrements. Bloquez-les selon le code postal :

Bloc (code postal) Enregistrements Paires candidates
M7K4L8 1, 2, 3, 5 6
L0H6T9 4 0
J8Y1L3 6 0

Le blocage laisse 6 paires candidates sur 15. Trois sont de vraies paires (les cases à bordure épaisse dans l’image). Trois associent Nathan à son frère : l’étape de comparaison doit les déclarer « différentes ». Et trois vraies paires sont perdues. L’enregistrement 4 contient l’ancien code postal de Samuel, donc il ne rencontre jamais ses autres enregistrements.

Le blocage a toujours ces deux côtés. Il élimine la plupart des paires, et l’apparieur devient rapide. Mais une vraie paire éliminée par le blocage est perdue pour de bon. Aucune étape suivante ne peut la trouver, car aucune ne la voit.

Nous mesurons donc chaque blocage avec deux nombres :

  • Exhaustivité des paires (pair completeness) : la proportion de vraies paires qui sont candidates. C’est le rappel du blocage. Dans l’exemple : 3 sur 6 = 0,5.
  • Taux de réduction : la proportion de toutes les paires que le blocage élimine. Dans l’exemple : 1 − 6/15 = 0,6.

Un bon blocage a ces deux valeurs proches de 1 : il élimine presque toutes les paires et conserve presque toutes les vraies paires.

Passons aux vraies données. Le projet fait cela dans la prochaine leçon, mais vous pouvez déjà voir le résultat. Sur les 60 108 enregistrements, le code postal crée 89 630 paires candidates. Il conserve 23 388 des 27 677 vraies paires :

  • exhaustivité des paires = 23 388 / 27 677 = 0,845
  • taux de réduction = 1 − 89 630 / 1 806 455 778 = 0,99995

Lisez attentivement le deuxième nombre. Le code postal élimine 99,995 % des paires. L’apparieur compare maintenant 89 630 paires, et non 1,8 milliard. Dans nos exécutions, créer ces paires candidates a pris entre 0,06 et 2,3 secondes.

Mais le premier nombre indique que 15,5 % des vraies paires sont perdues. Les prochaines leçons trouvent de meilleures clés. Le blocage par défaut du projet, keys, utilise cinq clés ensemble. Il crée 1 108 591 paires candidates, conserve 0,9937 des vraies paires et élimine encore 99,939 % de toutes les paires.

Vous connaissez peut-être cette idée grâce à la recherche. Un moteur de recherche n’attribue pas un score à chaque document pour une requête. Il récupère d’abord un petit ensemble de candidats dans un index, puis classe seulement ceux-ci. Recherche et classement : trouver la meilleure correspondance enseigne cela dans Classement en deux étapes. Le blocage est la première étape d’un apparieur.

Utilisez le blocage dès que vous avez plus de quelques milliers d’enregistrements. À 1 000 enregistrements, il y a 499 500 paires : un portable les compare toutes en quelques secondes. À 10 000 enregistrements, il y a environ 50 millions de paires : c’est lent, mais possible une fois. À 60 000 enregistrements et plus, le blocage est indispensable.

Vous pouvez l’omettre pour une vérification ponctuelle d’une petite liste, ou pour apparier quelques nouveaux enregistrements à une liste. Un nouvel enregistrement comparé à 60 108 enregistrements connus donne seulement 60 108 paires.

Ce que cela coûte : le blocage perd les vraies paires dont les enregistrements ne partagent pas de clé. Vous devez mesurer cette perte avec l’exhaustivité des paires chaque fois que vous changez les clés. La dernière leçon de ce module, Ce que le blocage fait perdre, le fait en détail.

Erreur courante

Une clé que tous les enregistrements partagent

Symptôme : dans le carnet, vous essayez la liste source comme clé de blocage : "shop", "loyalty" ou "garden". La cellule s’arrête avec une erreur :

ValueError: This key makes 700,893,447 pairs: too many to hold in memory. Use a narrower key.

Sans le garde-fou, le portable devient très lent, et le carnet s’arrête après quelques minutes.

Cause : une clé ayant peu de valeurs crée d’énormes blocs. Le bloc de la boutique contient 31 128 enregistrements, qui donnent à eux seuls 484 millions de paires. Les trois blocs ensemble donnent 700 893 447 paires : 39 % de toutes les paires. Une clé ayant une seule valeur pour tous les enregistrements crée la totalité des 1,8 milliard de paires. La fonction utilitaire du carnet compte d’abord les paires à partir des tailles des blocs. Elle refuse une clé qui en crée plus de 20 millions.

Solution : utilisez une clé ayant beaucoup de valeurs et de petits blocs : un code postal, un téléphone, le début d’un nom de famille. Comptez les paires d’une clé avant de les construire. Un bloc de taille k donne k × (k − 1) / 2 paires. Additionnez les résultats de tous les blocs.

Conséquence dans le travail en IA : une autojointure (une table jointe à elle-même sur une colonne) présente le même risque en SQL et dans pandas. Une valeur commune, comme une chaîne vide ou « unknown » (inconnu), peut créer un bloc de milliers d’enregistrements. SQL et préparation des données pour l’IA montre comment une jointure peut multiplier les lignes dans Joindre des tables. Comptez toujours avant de faire une jointure.

Vérifiez votre compréhension

Larkfield achète une deuxième chaîne de jardineries, et sa liste passe de 60 108 à 120 216 enregistrements. Combien de paires a-t-elle maintenant, environ? Combien de fois plus de temps prend la comparaison de toutes les paires?

Afficher la réponse

120 216 × 120 215 / 2 = 7 225 883 220 paires : environ 7,2 milliards. C’est quatre fois 1,8 milliard, et non deux fois. Le nombre de paires augmente avec le carré du nombre d’enregistrements. La comparaison de toutes les paires prend donc environ quatre fois plus de temps. Leur stockage nécessite environ quatre fois plus de mémoire : environ 58 Go.

Vérifiez votre compréhension

Dans le petit exemple, le code postal crée 6 paires candidates à partir des 6 enregistrements. Quelles vraies paires sont perdues, et pourquoi aucune étape suivante ne peut-elle les trouver?

Afficher la réponse

Les paires perdues sont 1–4, 2–4 et 3–4. L’enregistrement 4 (G-008438) est l’ancien enregistrement de Samuel Green, avec le code postal L0H6T9. Ses autres enregistrements ont M7K4L8. L’enregistrement 4 est seul dans son bloc, donc il ne forme jamais de paire avec eux. Les étapes suivantes (comparer, attribuer un score, regrouper) voient seulement les paires candidates. Une paire qui n’est pas candidate n’est jamais comparée. Elle est donc toujours déclarée « différente ».

Vérifiez votre compréhension

Tomás dit : « Le blocage par code postal a un taux de réduction de 0,99995. C'est presque parfait. » Que manque-t-il dans son jugement?

Afficher la réponse

Le taux de réduction indique seulement combien de paires le blocage élimine. Il ne dit rien sur les vraies paires qu’il élimine. Le code postal conserve seulement 23 388 des 27 677 vraies paires : son exhaustivité des paires est de 0,845. Donc, 15,5 % des vraies paires sont perdues avant toute comparaison. Il faut juger un blocage sur les deux nombres. Une clé qui élimine toutes les paires a un taux de réduction de 1 et ne sert à rien.

Récapitulatif

  • n enregistrements donnent n × (n − 1) / 2 paires. Les 60 108 enregistrements de Larkfield donnent 1 806 455 778 paires, dont seulement 27 677 sont de vraies paires.
  • Les paires augmentent avec le carré du nombre d’enregistrements. match allpairs estime environ une heure pour une toute petite comparaison sur un portable sans autre tâche. Il faut aussi 14,5 Go simplement pour conserver les paires.
  • Un apparieur compare seulement les paires candidates. Le blocage les choisit, par exemple avec une clé de blocage comme le code postal.
  • L’exhaustivité des paires est la proportion de vraies paires que le blocage conserve. Le taux de réduction est la proportion de toutes les paires qu’il élimine. Le code postal seul : 0,845 et 0,99995.
  • Une vraie paire éliminée par le blocage est perdue pour de bon.

Le code postal perd les clients qui ont déménagé. Ensuite, vous construirez des clés à partir d’autres champs et utiliserez plusieurs clés ensemble. Vous essaierez aussi une fenêtre glissante sur les noms triés.

Leçon suivante : Clés de blocage et voisinage trié