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.
Lesson 22 of 29 · Entity Resolution and Record Matching: Is This the Same Thing?Clustering pairs
1. The matching problem
2. Clean first, then match exactly
3. Blocking: do not compare everything
4. Compare records: similarity measures
5. Probabilistic linkage
6. Learned matching: classifiers, embeddings and language models
7. From pairs to entities
8. Run matching in production
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 notebook
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 ready
What you need to know
- Pair decisions, from A supervised pair classifier.
- Pair precision and recall, and “entities after clustering”, from Measure a matcher.
What you need on your computer
- The project
larkfield-matchat the end of Module 6, with its virtual environment active and the model trained (match train). Or use the notebook only.
Stapled cards
Section titled “Stapled cards”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.
The problem: pairs are not customers
Section titled “The problem: pairs are not customers”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.
The idea: follow every chain of links
Section titled “The idea: follow every chain of links”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.
A tiny example
Section titled “A tiny example”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.
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”.
What it costs
Section titled “What it costs”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.
Run it on Larkfield’s records
Section titled “Run it on Larkfield’s records”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.
Add the files of Module 7
Section titled “Add the files of Module 7”-
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 itsrequirements.txtandREADME.mdtoo:Terminal window S=../nextia-learning-labs/C39/snapshots/end-of-m07cp $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 .Terminal window $S = "..\nextia-learning-labs\C39\snapshots\end-of-m07"Copy-Item $S\larkfield_match\safecluster.py, $S\larkfield_match\clustermeasures.py, $S\larkfield_match\golden.py larkfield_match\Copy-Item $S\larkfield_match\commands\cluster.py, $S\larkfield_match\commands\golden.py, $S\larkfield_match\commands\undo.py larkfield_match\commands\Copy-Item $S\tests\test_entities.py tests\Copy-Item $S\requirements.txt, $S\README.md .The new
commands/cluster.pyreplaces the old one. It adds the option--method safefor the next lesson. -
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.txtIf 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 onlypython -m pip install networkx==3.7. -
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 of the best model
Section titled “Cluster the pairs of the best model”Cluster the pairs that LightGBM calls the same. --method cc means connected components, the default:
match cluster --run lgbmlgbm (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.csv38,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.
One bad value, one giant cluster
Section titled “One bad value, one giant cluster”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:
match cluster --run rule-phonerule-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.csvOne cluster has 40 records. They belong to 40 different people. Not one of them shares a customer with another.
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:
| Record | Name, as typed | Phone | True customer |
|---|---|---|---|
| G-000544 | LAFRAMBOISE, MARIE CLAUDE | 4505550100 | E-29426 |
| G-000737 | LEBLANC, VALERIE | 4505550100 | E-34152 |
| G-000754 | JOHNSON, NATHAN | 4505550100 | E-34584 |
| G-000938 | WANG, MOHAMMED | 4505550100 | E-24630 |
| G-001017 | LEWIS, EDWARD | 4505550100 | E-09937 |
| G-001083 | JULIE, OUELLET | 4505550100 | E-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.
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.
How big can it get?
Section titled “How big can it get?”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.
When to use it, and what it costs
Section titled “When to use it, and what it costs”- 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.
Knowledge check
Section titled “Knowledge check”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.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
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.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
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.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
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