Skip to content
Français

Clustering pairs

  • Lesson 22
  • 35 min
  • Module 7: From pairs to entities

Where we are

Every method so far decides pairs. Larkfield needs customers, not pairs. In this lesson, we join pairs into entities with connected components, and we see how one bad pair can make a giant cluster.

Plays from YouTube. Nothing loads from YouTube until you press play. Privacy

What you will be able to do

Turn pair decisions into customers. Join every chain of “same” pairs into one entity with connected components. Then see the danger: one wrong pair joins two people, and one bad value can join dozens of strangers into one giant “customer”.

NotebookCluster pairs in a notebookColab · Kaggle · GitHub

The notebook writes connected components in 15 lines of Python and runs them on a tiny example. Then it clusters the pairs of the rule “same phone” and you look inside the largest cluster. Its setup cells download the data, so it needs no local setup.

Colab and Kaggle open your own copy. They need a free Google or Kaggle account. Stuck? See the solution notebook.

Before you startWhat to know and to have readyAbout 35 minutes

What you need to know

What you need on your computer

  • The project larkfield-match at the end of Module 6, with its virtual environment active and the model trained (match train). Or use the notebook only.

A librarian sorts old index cards. Each card describes one book. Some books have two or three cards. Her helper reads the cards two at a time. When two cards describe the same book, he staples them together.

He staples card A to card B. Later he staples card B to card C. He never compared A with C. But A, B and C are now one bundle. If A is B and B is C, then A is C.

That rule is useful. It finds the third card without one more comparison. It is also dangerous. One day the helper staples two cards by mistake: a card from one bundle to a card from another bundle. Now two books are one bundle. Every staple that comes later makes the wrong bundle bigger.

Matching has the same rule and the same danger.

Every method in this course so far decides pairs. LightGBM says “same” or “not the same” for each candidate pair. But TermOmarLarkfield’s product manager. He asks the business questions: what a change costs, and what it gives the shop. does not ask about pairs. He asks: how many customers do we have, and which records belong to each one?

A pair decision does not answer that. Imagine three records of one customer:

  • The model says the shop record and the loyalty record are the same.
  • The model says the loyalty record and the garden-centre record are the same.
  • The shop record and the garden-centre record were never a candidate pair. Their postcodes differ, and blocking did not put them together.

Are the three records one customer? The pairs alone do not say. We need a rule that turns pairs into groups.

Draw each record as a dot. Draw a line between two dots when the matcher calls the pair the same. Mathematicians call this picture a graph: the dots are nodes, and the lines are edges. We will say “records” and “links”.

Now follow the lines. Every set of records that you can reach from each other, by any chain of links, is one connected component. Each connected component becomes one entity. This is transitivity: if A = B and B = C, then A = C.

A group of records that a method puts together is a cluster. Joining pairs into clusters is clustering. Connected components is the simplest way to do it.

Six records, A to F. The matcher calls three pairs the same: A–B, B–C and D–E. It never compared A with C.

Six records A to F. Links join A to B, B to C, and D to E. Three steps of union-find: after the link A–B, the groups are {A, B}, {C}, {D}, {E}, {F}; after B–C, {A, B, C}, {D}, {E}, {F}; after D–E, {A, B, C}, {D, E}, {F}. A note says that A and C were never compared, but they end in one entity. The result is three entities.
Connected components on six records (a made-up example). Each link joins two groups. A and C end in one entity without a comparison.
Text description of the diagram

The picture shows six records, A to F, in a row. Three links join A to B, B to C, and D to E. Under the records, three steps show the groups. After the link A–B, A and B are one group, and the other four records are alone. After the link B–C, A, B and C are one group. After the link D–E, D and E are one group. The result is three entities: A, B and C; D and E; and F alone. A note says that A and C were never compared, but they are in one entity.

The method in the picture is union-find. It keeps one “leader” record for each group. For each link, it finds the leaders of the two records. If the leaders differ, it joins the two groups under one leader. It reads every link once. So its work grows with the number of links, not with the number of possible pairs of records.

The project names each cluster after its smallest record ID. So the cluster of A, B and C is “A”.

Connected components needs no new model and no threshold. It is fast and easy to explain. But it trusts every link completely. A link that is wrong is never questioned. And the method has no limit on size. Two families, three families, or forty strangers can end in one entity.

The project has had connected components since the start: every match eval prints “entities after clustering”. Module 7 adds safer clustering, cluster measures and golden records. Copy all the files of this module now.

  1. In your project folder, with the TermVirtual environmentA folder with its own Python and its own packages, for one project. Packages that you install there do not change other projects.Learn more Isolate dependenciesPython for Practical AI Engineering active, copy the files of the snapshot end-of-m07. This module has four lessons, and you copy all their files now. Copy its requirements.txt and README.md too:

    Terminal window
    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 .

    The new commands/cluster.py replaces the old one. It adds the option --method safe for the next lesson.

  2. Install the requirements. The new line is networkx==3.7: NetworkX helps safe clustering cut links in the next lesson.

    Terminal window
    python -m pip install -r requirements.txt

    If you installed PyTorch in Module 6, you have NetworkX 3.7 already: PyTorch needs it too. Then every line starts with Requirement already satisfied. If you did not, pip installs NetworkX and PyTorch now (about 700 MB). To skip PyTorch, install only python -m pip install networkx==3.7.

  3. Run the tests. There are 38 now:

    Terminal window
    python -m pytest -q
    ...................................... [100%]
    38 passed in 95.29s (0:01:35)

We ran these steps on macOS. The Windows commands are not tested.

Cluster the pairs that LightGBM calls the same. --method cc means connected components, the default:

Terminal window
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 entities, against 37,500 true customers. That is close. The largest cluster has 9 records. But no true customer has more than 5 records. So a cluster of 9 records holds at least two people, for sure. We look inside such clusters in the next lesson.

In Module 2, we tried a rule that we did not keep: “same phone, same customer”. Its pairs have precision 0.539 on the test split. Cluster them:

Terminal window
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

One cluster has 40 records. They belong to 40 different people. Not one of them shares a customer with another.

The 8 largest clusters of the rule "same phone", with connected components, in the synthetic records. Measured. No true customer has more than 5 records.
Text description of the chart

A column chart of the 8 largest clusters. The largest has 40 records. The next ones have 9, 8, 7, 7, 7, 7, 7 records. The first column is more than four times higher than the second. No true customer has more than 5 records, so every cluster in the chart joins different people.

Why? Look at the records of the giant cluster. All 40 come from the garden centres, and all have the same phone, 4505550100:

RecordName, as typedPhoneTrue customer
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

The table shows the first 6 of the 40 records.

That is a practice problem we made on purpose, but it happens in real data all the time. When a walk-in customer gave no phone number, the garden-centre staff typed the shop’s own number. So 40 strangers share one phone. The rule links every pair of them, and connected components joins all of them.

A ring of 40 small record circles around one phone number, 450 555 0100. A line joins each record to the phone. Six records are named: LAFRAMBOISE, MARIE CLAUDE; LEBLANC, VALERIE; JOHNSON, NATHAN; WANG, MOHAMMED; LEWIS, EDWARD; JULIE, OUELLET. A label says: 40 records, 40 different people, one cluster. A second panel shows two families of three records each, joined by one wrong link, which makes one cluster of six records.
Two ways one bad link makes a giant cluster. Left: 40 garden-centre records share the shop's own phone number, a practice problem we made on purpose. Right: one wrong pair joins two families (a made-up example).
Text description of the diagram

The picture has two panels. In the left panel, 40 small circles form a ring around one box with the phone number 450 555 0100. A line joins each circle to the box. Six of the circles are named with garden-centre records as typed, for example LAFRAMBOISE, MARIE CLAUDE and LEBLANC, VALERIE. A label under the ring says: 40 records, 40 different people, one cluster. In the right panel, two families of three records each are joined inside each family by right links. One wrong link joins one record of the first family to one record of the second. A box around all six records says: one cluster, two families.

The left panel is the extreme case: a value that many strangers share. The right panel is the common case: one wrong pair between two true groups. Both have the same effect. Connected components cannot tell a strong link from a weak one. Any link joins two whole groups.

A cluster of n records holds n × (n − 1) ÷ 2 pairs. The giant cluster has 40 records, so it holds 780 pairs, and every one of them is wrong. The rule called these pairs the same one by one. But every new link also made the cluster bigger.

This is called chaining: each wrong link adds a whole group, not one record. The more links a method makes, the more likely a chain is. A matcher with high recall makes many links, so it needs more care with clustering, not less.

  • Use connected components as the first step, always. It is fast, and it gives you the entities to inspect. On a precise matcher, it is often good enough: for LightGBM, it makes 38,514 entities.
  • Do not trust it alone. It has no checks. A single wrong link, or a value that strangers share, joins whole groups.
  • Look at the size of the clusters. You know how many records one real customer can have. A cluster far above that is wrong for sure. The next lesson turns this into a check.
  • It costs almost nothing: one pass over the links. The cost is in the errors it can make, and a false merge costs TermLarkfieldA made-up Canadian online shop for home and garden products. It is not a real company. All Nextia courses use its help desk and data as the example.Learn more Meet Larkfield an assumed 150 dollars.

Common mistake

A placeholder value joins strangers

Symptom: after “same phone”, Larkfield has one customer with 40 records. Omar sees a customer who visited every garden centre and changed their name 39 times.

Cause: a placeholder value: a value that people type when they do not have the real one. Here it is the shop’s own phone number. Other common placeholders are 000-000-0000, noemail@example.com, 1900-01-01 and “N/A”. Many strangers share them, so any rule on that field links them all. Connected components then joins them into one entity.

Fix: before you match, count how many records share each value. A phone that 40 records share, in a list where a real customer has at most 5 records, is a placeholder. Treat it as missing. Then add a size check on the clusters, as the next lesson does.

Consequence in AI work: default and placeholder values break more than matching. A model can learn that “phone 450 555 0100” predicts a garden-centre customer. Profile the values before you use them. Profile before changing in SQL and Data Preparation for AI shows how.

Check your understanding

The matcher calls three pairs the same: P–Q, Q–R and S–T. There are six records, P to U. How many entities does connected components make, and which?

Show the answer

Three entities: P, Q and R (P–Q and Q–R form one chain); S and T; and U alone. P and R end in one entity, although the matcher never compared them. The project names the clusters after their smallest record ID: P, S and U.

Check your understanding

The rule "same phone" has pair precision 0.539, but its largest cluster has 40 records of 40 people. Why do the pair measures not show this cluster?

Show the answer

Pair precision counts each wrong pair once. The giant cluster comes from one placeholder phone shared by 40 records. The 780 pairs inside it are spread over all three splits, and only some fall in the test split. In the pair measures, they look like many small errors. Only the cluster shows that one bad value made one false “customer” of 40 people. Lesson 4 measures clusters directly.

Check your understanding

Tomás says: “LightGBM has pair precision 0.918, so its clusters are 92% right.” What is wrong with this?

Show the answer

Clustering adds pairs that the model never called the same. If the model links A–B and B–C, the cluster also contains A–C. When one link is wrong, the cluster contains many wrong pairs that the model never decided. So the clusters can be worse than the pairs. Lesson 4 measures this: inside the connected components of LightGBM, pair precision falls from 0.918 to 0.838.

Recap

  • A matcher decides pairs. Larkfield needs entities: groups of records of one customer.
  • Connected components join every chain of links into one cluster. If A = B and B = C, then A = C. Union-find does it in one pass.
  • For LightGBM, connected components make 38,514 entities (true: 37,500). The largest has 9 records, more than any true customer.
  • One bad link joins two whole groups. The rule “same phone” makes one cluster of 40 records of 40 different people. The cause is a placeholder phone that strangers share: a practice problem we made on purpose.
  • Watch cluster sizes, and treat placeholder values as missing.

Next, we add checks that a cluster must pass, and we cut the weakest link of every cluster that fails.

Next: Safer clustering