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.
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
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
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 Jupyter
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 main
Ce que vous devez savoir
- Les vraies paires, la précision par paire et le rappel par paire, présentés dans Fusions erronées et correspondances manquées et Mesurer un apparieur.
- Les valeurs nettoyées de chaque enregistrement (nom, courriel, téléphone, code postal, date de naissance), présentées dans Normaliser.
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.
Les classeurs de la clinique
Section intitulée « Les classeurs de la clinique »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.
Compter toutes les paires
Section intitulée « Compter toutes les paires »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.
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.
Les paires de Larkfield
Section intitulée « Les paires de Larkfield »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.
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.
Combien de temps faudrait-il?
Section intitulée « Combien de temps faudrait-il? »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.
-
Assurez-vous d’avoir les fichiers du cours les plus récents. Dans le dossier contenant
nextia-learning-labsetlarkfield-match, exécutez :Fenêtre de terminal git -C nextia-learning-labs pullSi vous avez utilisé le fichier ZIP, téléchargez-le de nouveau.
-
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-matchcp ../nextia-learning-labs/C39/snapshots/end-of-m03/larkfield_match/commands/allpairs.py larkfield_match/commands/Fenêtre de terminal cd larkfield-matchCopy-Item ..\nextia-learning-labs\C39\snapshots\end-of-m03\larkfield_match\commands\allpairs.py larkfield_match\commands\La commande
matchtrouve ses sous-commandes grâce à leurs fichiers. La nouvelle commande fonctionne donc immédiatement. -
Exécutez-la :
Fenêtre de terminal match allpairs60,108 records -> 1,806,455,778 pairsTimed 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 namesOnly 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.
Ce que les nombres veulent dire
Section intitulée « Ce que les nombres veulent dire »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.
L’idée : les paires candidates
Section intitulée « L’idée : les paires candidates »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é.
Le petit exemple, avec blocage
Section intitulée « Le petit exemple, avec blocage »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.
Deux nombres pour un blocage
Section intitulée « Deux nombres pour un blocage »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.
Bloquer Larkfield selon le code postal
Section intitulée « Bloquer Larkfield selon le code postal »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.
La même idée en recherche
Section intitulée « La même idée en recherche »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.
Quand bloquer, et ce que cela coûte
Section intitulée « Quand bloquer, et ce que cela coûte »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érification des connaissances
Section intitulée « Vérification des connaissances »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.
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
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 ».
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
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.
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
- 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 allpairsestime 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é