Aller au contenu
English

Regrouper les paires

  • Leçon 22
  • 35 min
  • Module 7 : Des paires aux entités

Où nous en sommes

Toutes les méthodes vues jusqu'ici décident pour chaque paire. Larkfield a besoin de clients, pas de paires. Dans cette leçon, nous réunissons les paires en entités avec les composantes connexes. Nous voyons aussi comment une mauvaise paire peut créer un groupe géant.

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

Ce que vous saurez faire

Transformez les décisions par paire en clients. Réunissez chaque chaîne de paires « identiques » en une entité avec les composantes connexes. Observez ensuite le danger : une mauvaise paire réunit deux personnes. Une mauvaise valeur peut réunir des dizaines d’inconnus en un seul « client » géant.

Carnet JupyterRegrouper les paires dans un carnetColab · Kaggle · GitHub · en anglais

Le carnet (notebook) Jupyter crée des composantes connexes en 15 lignes de Python et les applique à un petit exemple. Il regroupe ensuite les paires de la règle « même téléphone », puis vous examinez le plus grand groupe. Ses cellules de préparation téléchargent les données. Il ne nécessite donc aucune configuration 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 35 minutes

Ce que vous devez savoir

Ce qu’il vous faut sur votre ordinateur

  • Le projet larkfield-match à la fin du module 6, avec son environnement virtuel actif et le modèle entraîné (match train). Ou utilisez seulement le carnet.

Une bibliothécaire trie de vieilles fiches. Chaque fiche décrit un livre. Certains livres ont deux ou trois fiches. Son assistant lit les fiches deux à la fois. Quand deux fiches décrivent le même livre, il les agrafe ensemble.

Il agrafe la fiche A à la fiche B. Plus tard, il agrafe la fiche B à la fiche C. Il n’a jamais comparé A et C. Mais A, B et C forment maintenant un seul paquet. Si A est B et B est C, alors A est C.

Cette règle est utile. Elle trouve la troisième fiche sans comparaison supplémentaire. Elle est aussi dangereuse. Un jour, l’assistant agrafe deux fiches par erreur : une fiche d’un paquet à une fiche d’un autre paquet. Maintenant, deux livres forment un seul paquet. Chaque agrafe ajoutée ensuite agrandit ce mauvais paquet.

L’appariement suit la même règle et présente le même danger.

Toutes les méthodes de ce cours vues jusqu’ici décident pour chaque paire. LightGBM dit « identiques » ou « différents » pour chaque paire candidate. Mais TermeOmarLe gestionnaire de produit de Larkfield. Il pose les questions d’affaires : ce qu’un changement coûte et ce qu’il apporte à la boutique. ne pose pas de questions sur les paires. Il demande : combien avons-nous de clients, et quels enregistrements appartiennent à chacun?

Une décision par paire ne répond pas à cette question. Imaginez trois enregistrements d’un même client :

  • Le modèle dit que l’enregistrement du magasin et celui du programme de fidélité correspondent.
  • Le modèle dit que l’enregistrement du programme de fidélité et celui de la jardinerie correspondent.
  • L’enregistrement du magasin et celui de la jardinerie n’ont jamais formé une paire candidate. Leurs codes postaux diffèrent, et le blocage ne les a pas réunis.

Les trois enregistrements représentent-ils un seul client? Les paires seules ne le disent pas. Il nous faut une règle qui transforme les paires en groupes.

Représentez chaque enregistrement par un point. Tracez une ligne entre deux points quand l’apparieur juge que la paire correspond. Les mathématiciens appellent ce dessin un graphe : les points sont des nœuds, et les lignes sont des arêtes. Nous dirons « enregistrements » et « liens ».

Suivez maintenant les lignes. Chaque ensemble d’enregistrements reliés entre eux par une chaîne de liens forme une composante connexe. Chaque composante connexe devient une entité. C’est la transitivité : si A = B et B = C, alors A = C.

Un ensemble d’enregistrements qu’une méthode réunit est un groupe. Réunir des paires en groupes s’appelle le regroupement. Les composantes connexes sont la façon la plus simple de le faire.

Six enregistrements, de A à F. L’apparieur juge que trois paires correspondent : A–B, B–C et D–E. Il n’a jamais comparé A et C.

Six enregistrements de A à F. Des liens relient A à B, B à C et D à E. Trois étapes d'union-find : après le lien A–B, les groupes sont {A, B}, {C}, {D}, {E}, {F}; après B–C, {A, B, C}, {D}, {E}, {F}; après D–E, {A, B, C}, {D, E}, {F}. Une note indique que A et C n'ont jamais été comparés, mais aboutissent dans une seule entité. Le résultat est trois entités.
Composantes connexes sur six enregistrements (un exemple inventé). Chaque lien réunit deux groupes. A et C aboutissent dans une seule entité sans comparaison.
Description textuelle du diagramme

L’image montre six enregistrements, de A à F, sur une rangée. Trois liens relient A à B, B à C et D à E. Sous les enregistrements, trois étapes montrent les groupes. Après le lien A–B, A et B forment un groupe, et les quatre autres enregistrements restent seuls. Après le lien B–C, A, B et C forment un groupe. Après le lien D–E, D et E forment un groupe. Le résultat est trois entités : A, B et C; D et E; et F seul. Une note indique que A et C n’ont jamais été comparés, mais se trouvent dans une seule entité.

La méthode illustrée est union-find (structure union-recherche). Elle garde un enregistrement « représentant » pour chaque groupe. Pour chaque lien, elle trouve les représentants des deux enregistrements. Si les représentants diffèrent, elle réunit les deux groupes sous un seul représentant. Elle lit chaque lien une fois. Son travail augmente donc avec le nombre de liens, pas avec le nombre de paires d’enregistrements possibles.

Le projet nomme chaque groupe d’après son plus petit identifiant d’enregistrement. Le groupe de A, B et C s’appelle donc « A ».

Les composantes connexes ne nécessitent ni nouveau modèle ni seuil. La méthode est rapide et facile à expliquer. Mais elle fait entièrement confiance à chaque lien. Elle ne remet jamais un mauvais lien en question. Et elle n’impose aucune limite de taille. Deux familles, trois familles ou quarante inconnus peuvent aboutir dans une seule entité.

Exécuter la méthode sur les enregistrements de Larkfield

Section intitulée « Exécuter la méthode sur les enregistrements de Larkfield »

Le projet utilise les composantes connexes depuis le début : chaque match eval affiche « entities after clustering » (entités après regroupement). Le module 7 ajoute un regroupement plus sûr, des mesures de groupes et des fiches de référence. Copiez maintenant tous les fichiers de ce module.

  1. Dans votre dossier de 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 l’instantané end-of-m07. Ce module comprend quatre leçons, et vous copiez maintenant tous leurs fichiers. Copiez aussi ses fichiers requirements.txt et README.md :

    Fenêtre de terminal
    S=../nextia-learning-labs/C39/snapshots/end-of-m07
    cp $S/larkfield_match/safecluster.py $S/larkfield_match/clustermeasures.py $S/larkfield_match/golden.py larkfield_match/
    cp $S/larkfield_match/commands/cluster.py $S/larkfield_match/commands/golden.py $S/larkfield_match/commands/undo.py larkfield_match/commands/
    cp $S/tests/test_entities.py tests/
    cp $S/requirements.txt $S/README.md .

    Le nouveau commands/cluster.py remplace l’ancien. Il ajoute l’option --method safe pour la prochaine leçon.

  2. Installez les dépendances. La nouvelle ligne est networkx==3.7 : NetworkX aide le regroupement plus sûr à couper des liens dans la prochaine leçon.

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

    Si vous avez installé PyTorch au module 6, vous avez déjà NetworkX 3.7 : PyTorch en a aussi besoin. Chaque ligne commence alors par Requirement already satisfied (dépendance déjà satisfaite). Sinon, pip installe maintenant NetworkX et PyTorch (environ 700 Mo). Pour éviter PyTorch, installez seulement python -m pip install networkx==3.7.

  3. Exécutez les tests. Il y en a maintenant 38 :

    Fenêtre de terminal
    python -m pytest -q
    ...................................... [100%]
    38 passed in 95.29s (0:01:35)

Nous avons exécuté ces étapes sur macOS. Les commandes Windows n’ont pas été testées.

Regroupez les paires que LightGBM juge correspondantes. --method cc signifie composantes connexes, la méthode par défaut :

Fenêtre de terminal
match cluster --run lgbm
lgbm (cc): 60,108 records -> 38,514 entities (true: 37,500)
Largest clusters: G-005393 (9 records), G-010491 (8 records), G-005908 (8 records)
Saved to outputs/clusters/lgbm-cc.csv

38 514 entités, contre 37 500 vrais clients. C’est proche. Le plus grand groupe contient 9 enregistrements. Mais aucun vrai client n’a plus de 5 enregistrements. Un groupe de 9 enregistrements contient donc au moins deux personnes, sans aucun doute. Nous examinons ces groupes dans la prochaine leçon.

Au module 2, nous avons essayé une règle que nous n’avons pas gardée : « même téléphone, même client ». Ses paires ont une précision de 0,539 sur le jeu de test. Regroupez-les :

Fenêtre de terminal
match cluster --run rule-phone
rule-phone (cc): 60,108 records -> 45,230 entities (true: 37,500)
Largest clusters: G-000544 (40 records), G-007655 (9 records), G-002757 (8 records)
Saved to outputs/clusters/rule-phone-cc.csv

Un groupe contient 40 enregistrements. Ils appartiennent à 40 personnes différentes. Aucun ne représente le même client qu’un autre.

Les 8 plus grands groupes de la règle « même téléphone », avec les composantes connexes, dans les enregistrements synthétiques. Mesuré. Aucun vrai client n'a plus de 5 enregistrements.
Description textuelle du graphique

Un diagramme à colonnes des 8 plus grands groupes. Le plus grand contient 40 enregistrements. Les suivants contiennent 9, 8, 7, 7, 7, 7, 7 enregistrements. La première colonne est plus de quatre fois plus haute que la deuxième. Aucun vrai client n’a plus de 5 enregistrements. Chaque groupe du diagramme réunit donc des personnes différentes.

Pourquoi? Regardez les enregistrements du groupe géant. Les 40 proviennent tous des jardineries et ont le même téléphone, 4505550100 :

EnregistrementNom, tel que saisiTéléphoneVrai client
G-000544LAFRAMBOISE, MARIE CLAUDE4505550100E-29426
G-000737LEBLANC, VALERIE4505550100E-34152
G-000754JOHNSON, NATHAN4505550100E-34584
G-000938WANG, MOHAMMED4505550100E-24630
G-001017LEWIS, EDWARD4505550100E-09937
G-001083JULIE, OUELLET4505550100E-10654

Le tableau montre les 6 premiers des 40 enregistrements.

Nous avons créé ce problème exprès pour l’exercice, mais il survient souvent dans les données réelles. Quand un client de passage ne donnait pas de numéro de téléphone, le personnel de la jardinerie saisissait celui du magasin. Ainsi, 40 inconnus partagent un téléphone. La règle relie chaque paire, et les composantes connexes les réunissent tous.

Un anneau de 40 petits cercles d'enregistrements autour d'un numéro de téléphone, 450 555 0100. Une ligne relie chaque enregistrement au téléphone. Six enregistrements sont nommés : LAFRAMBOISE, MARIE CLAUDE; LEBLANC, VALERIE; JOHNSON, NATHAN; WANG, MOHAMMED; LEWIS, EDWARD; JULIE, OUELLET. Une étiquette indique : 40 enregistrements, 40 personnes différentes, un groupe. Un second panneau montre deux familles de trois enregistrements chacune, reliées par un seul mauvais lien, ce qui crée un groupe de six enregistrements.
Deux façons dont un mauvais lien crée un groupe géant. À gauche : 40 enregistrements des jardineries partagent le numéro de téléphone du magasin, un problème d'exercice que nous avons créé exprès. À droite : une mauvaise paire réunit deux familles (un exemple inventé).
Description textuelle du diagramme

L’image comporte deux panneaux. Dans le panneau gauche, 40 petits cercles forment un anneau autour d’un encadré contenant le numéro de téléphone 450 555 0100. Une ligne relie chaque cercle à l’encadré. Six cercles portent les noms d’enregistrements des jardineries tels que saisis, par exemple LAFRAMBOISE, MARIE CLAUDE et LEBLANC, VALERIE. Une étiquette sous l’anneau indique : 40 enregistrements, 40 personnes différentes, un groupe. Dans le panneau droit, deux familles de trois enregistrements sont reliées, chacune par des liens corrects. Un mauvais lien relie un enregistrement de la première famille à un enregistrement de la deuxième. Un encadré autour des six enregistrements indique : un groupe, deux familles.

Le panneau gauche montre le cas extrême : une valeur que de nombreux inconnus partagent. Le panneau droit montre le cas courant : une mauvaise paire entre deux vrais groupes. Les deux ont le même effet. Les composantes connexes ne distinguent pas un lien fort d’un lien faible. Tout lien réunit deux groupes entiers.

Un groupe de n enregistrements contient n × (n − 1) ÷ 2 paires. Le groupe géant contient 40 enregistrements, donc 780 paires, et elles sont toutes erronées. La règle a jugé ces paires correspondantes une à une. Mais chaque nouveau lien a aussi agrandi le groupe.

C’est ce qu’on appelle l’enchaînement : chaque mauvais lien ajoute un groupe entier, pas un seul enregistrement. Plus une méthode crée de liens, plus une chaîne est probable. Un apparieur au rappel élevé crée beaucoup de liens. Son regroupement exige donc plus de prudence, pas moins.

  • Utilisez toujours les composantes connexes comme première étape. La méthode est rapide et vous donne les entités à inspecter. Avec un apparieur précis, elle suffit souvent : pour LightGBM, elle crée 38 514 entités.
  • Ne vous fiez pas à cette méthode seule. Elle n’effectue aucune vérification. Un seul mauvais lien, ou une valeur que des inconnus partagent, réunit des groupes entiers.
  • Examinez la taille des groupes. Vous savez combien d’enregistrements un vrai client peut avoir. Un groupe bien plus grand est forcément erroné. La prochaine leçon transforme ce constat en vérification.
  • Le coût est presque nul : un passage sur les liens. Le coût vient des erreurs possibles. Selon notre hypothèse, une fusion erronée coûte 150 $ à 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.

Erreur courante

Une valeur de remplacement réunit des inconnus

Symptôme : après « même téléphone », Larkfield a un client avec 40 enregistrements. Omar voit un client qui a visité toutes les jardineries et changé de nom 39 fois.

Cause : une valeur de remplacement : une valeur que les gens saisissent quand ils n’ont pas la vraie. Ici, c’est le numéro de téléphone du magasin. D’autres valeurs de remplacement courantes sont 000-000-0000, noemail@example.com, 1900-01-01 et « N/A ». De nombreux inconnus les partagent. Toute règle portant sur ce champ les relie donc tous. Les composantes connexes les réunissent ensuite en une seule entité.

Correction : avant l’appariement, comptez combien d’enregistrements partagent chaque valeur. Un téléphone partagé par 40 enregistrements est une valeur de remplacement si un vrai client a au maximum 5 enregistrements. Traitez cette valeur comme manquante. Ajoutez ensuite une vérification de la taille des groupes, comme dans la prochaine leçon.

Conséquence pour le travail en IA : les valeurs par défaut et de remplacement nuisent à bien plus que l’appariement. Un modèle peut apprendre que « téléphone 450 555 0100 » prédit un client de jardinerie. Profilez les valeurs avant de les utiliser. Profiler avant de modifier, dans SQL et préparation des données pour l’IA, montre comment faire.

Vérifiez votre compréhension

L'apparieur juge que trois paires correspondent : P–Q, Q–R et S–T. Il y a six enregistrements, de P à U. Combien d'entités les composantes connexes créent-elles, et lesquelles?

Afficher la réponse

Trois entités : P, Q et R (P–Q et Q–R forment une chaîne); S et T; et U seul. P et R aboutissent dans une seule entité, même si l’apparieur ne les a jamais comparés. Le projet nomme les groupes d’après leur plus petit identifiant d’enregistrement : P, S et U.

Vérifiez votre compréhension

La règle « même téléphone » a une précision par paire de 0,539, mais son plus grand groupe contient 40 enregistrements de 40 personnes. Pourquoi les mesures par paire ne montrent-elles pas ce groupe?

Afficher la réponse

La précision par paire compte chaque mauvaise paire une fois. Le groupe géant vient d’un téléphone de remplacement partagé par 40 enregistrements. Ses 780 paires sont réparties entre les trois partitions, et seules certaines se trouvent dans le jeu de test. Dans les mesures par paire, elles ressemblent à de nombreuses petites erreurs. Seul le groupe montre qu’une mauvaise valeur a créé un faux « client » de 40 personnes. La leçon 4 mesure directement les groupes.

Vérifiez votre compréhension

Tomás dit : « LightGBM a une précision par paire de 0,918, donc ses groupes sont corrects à 92 %. » Qu'est-ce qui ne va pas dans cette affirmation?

Afficher la réponse

Le regroupement ajoute des paires que le modèle n’a jamais jugées correspondantes. Si le modèle relie A–B et B–C, le groupe contient aussi A–C. Quand un lien est erroné, le groupe contient de nombreuses mauvaises paires sur lesquelles le modèle n’a jamais décidé. Les groupes peuvent donc être moins bons que les paires. La leçon 4 mesure cet effet : dans les composantes connexes de LightGBM, la précision par paire passe de 0,918 à 0,838.

Récapitulatif

  • Un apparieur décide pour chaque paire. Larkfield a besoin d’entités : des groupes d’enregistrements d’un même client.
  • Les composantes connexes réunissent chaque chaîne de liens en un groupe. Si A = B et B = C, alors A = C. Union-find le fait en un passage.
  • Pour LightGBM, les composantes connexes créent 38 514 entités (nombre réel : 37 500). La plus grande contient 9 enregistrements, plus que tout vrai client.
  • Un mauvais lien réunit deux groupes entiers. La règle « même téléphone » crée un groupe de 40 enregistrements de 40 personnes différentes. La cause est un téléphone de remplacement que des inconnus partagent : un problème créé exprès pour l’exercice.
  • Surveillez la taille des groupes et traitez les valeurs de remplacement comme manquantes.

Ensuite, nous ajoutons des vérifications que chaque groupe doit réussir. Nous coupons le lien le plus faible de chaque groupe qui échoue.

Leçon suivante : Un regroupement plus sûr