Safer clustering
- Lesson 23
- 35 min
- Module 7: From pairs to entities
Where we are
Connected components joined too much. We need checks that stop one weak link from joining two families. In this lesson, we check cluster quality, cut weak links, and add rules such as "no two dates of birth in one entity".
Lesson 23 of 29 · Entity Resolution and Record Matching: Is This the Same Thing?Safer clustering
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
Stop one weak link from joining two people. Give every cluster a few checks that a real customer always passes. When a cluster fails, cut its weakest link and check the parts again. Measure what the checks fix and what they cost.
NotebookMake clusters safe in a notebook
The notebook clusters the pairs of Module 2’s four rules and looks inside a cluster that is too large. You write the date-of-birth check. Then the notebook cuts weak links until every cluster passes, and compares the cluster sizes before and after. 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
- Connected components and the giant cluster, from Clustering pairs.
- The scores of LightGBM’s pairs, from A supervised pair classifier.
What you need on your computer
- The project
larkfield-matchwith the files of Module 7, copied in the previous lesson. Or use the notebook only.
Two birthdays in one folder
Section titled “Two birthdays in one folder”A clinic merges the patient folders of two old offices. A nurse opens one merged folder. The first paper says the patient was born on 12 March 1980. The second paper says 3 July 1985.
One person cannot have two birthdays. So she knows at once: this folder holds two patients. She did not need to compare every paper. One simple rule found the error.
Then she asks a second question: which paper is wrong? She looks at why each paper went into the folder. Two papers share a health-card number: a strong reason. One paper only shares a surname and a street: a weak reason. She takes out the paper with the weakest reason, and checks the folder again.
That is this lesson: simple checks that find a wrong cluster, and a rule that removes the weakest link first.
The problem: clusters that cannot be one person
Section titled “The problem: clusters that cannot be one person”In the previous lesson, connected components joined LightGBM’s pairs into 38,514 entities. Most are right. But 75 clusters have more than 5 records, and no true customer has more than 5. The largest has 9.
Here is one real cluster of LightGBM’s links. It has 4 records:
| Record | Source | Name, as typed | Date of birth (clean) |
|---|---|---|---|
| G-000554 | garden | OUELLET, NATHAOIE | 1950-10-21 |
| G-002354 | garden | OUELLET, NATHALIE | (empty) |
| L-016649 | loyalty | Nathalie Ouellet | 1992-12-06 |
| S-029847 | shop | Nathalie Ouellet | 1950-10-21 |
The cluster holds two dates of birth. Like the nurse, we know it holds at least two people. Connected components cannot see this: it only follows links.
The idea: checks, and cut the weakest link
Section titled “The idea: checks, and cut the weakest link”A check is a rule that every true entity passes. If a cluster fails a check, it is wrong for sure. The project uses three checks. They are our choice, made for 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’s records:
- No two different dates of birth. One person has one date of birth. An empty date is no evidence. A day and a month typed the wrong way round, such as
1975-01-31and1975-31-01, count as the same date. - No more than 6 records. No true customer has more than 5. We allow one more, so that a customer with one extra record is not cut.
- No pair that a person marked “not the same”. When Ivana splits a wrong merge, the project remembers it. A link between two such records is removed first, before the other checks. Lesson 3 shows how.
In the research literature, the third kind of rule is a cannot-link constraint: two records that may never be in one cluster.
What do we do with a cluster that fails? We do not throw it away. Most of its links are right. We remove one link: the weakest link, the pair with the lowest score. Then we check each part again. A part that still fails loses its next weakest link. We stop when every part passes.
A worked example
Section titled “A worked example”Here is the cluster from the table, with its 4 links and LightGBM’s score for each link.
Text description of the diagram
The picture shows 4 record boxes at the corners of a square. Each box gives the record ID, the source, the name as typed and the date of birth. Lines join the records that LightGBM called the same, and each line has its score. Cut 1 removes the link G-000554 to G-002354, with score 0.999736. Cut 2 removes the link G-002354 to S-029847, with score 0.999926. The cut links are dashed and red. After the cuts, the records form 2 groups: G-000554 and S-029847; G-002354 and L-016649. Each group has one date of birth.
Follow the steps:
- Cut 1. The cluster fails ("two dates of birth"). Its weakest link is G-000554 / G-002354, with score 0.999736. Safe clustering removes it.
- Cut 2. The cluster fails ("two dates of birth"). Its weakest link is G-002354 / S-029847, with score 0.999926. Safe clustering removes it.
Why does it take 2 cuts? Because the records were joined by more than one chain. After the first cut, the two people are still connected by another link. Only when no chain joins them does the cluster split. Each part then passes the check: one date of birth each.
The result is right. Our records are synthetic, so we know the truth: these are two different women with the same name, Nathalie Ouellet. One record even has a typing error, “NATHAOIE”. Each part now holds the records of one of them.
Why the weakest link?
Section titled “Why the weakest link?”The model is less sure about a low-score link. So when a cluster is wrong, we remove that link first, and we remove as few links as possible. This rule is easy to explain to Ivana, and each cut goes into a log.
But look at the scores: all of them are above 0.999. The differences are tiny, so the weakest link is only a little weaker than the others. The rule is a good guess, not a proof. We can measure how good it is, because we know the true customers:
- Of the 679 links that safe clustering cuts, 463 join two different customers. Those cuts are right. The other 216 cut a link inside one customer.
- We looked at the 263 failing clusters with 3 to 5 records. In 161 of them, the parts are exactly the true customers.
So the check is reliable: a cluster with two dates of birth is wrong. The choice of where to cut is less reliable. Some tools cut the link whose removal splits the cluster best, or they cluster again with a stricter threshold. In Human review, a person decides the hard cases.
Run it on Larkfield’s records
Section titled “Run it on Larkfield’s records”match cluster has a new option, --method safe. --show-cuts 5 prints the first five links that it cuts:
match cluster --run lgbm --method safe --show-cuts 5lgbm (safe): 60,108 records -> 38,908 entities (true: 37,500)Largest clusters: G-001224 (6 records), G-000994 (6 records), G-002621 (6 records)Links cut: 679 L-000323 / G-000077 score 1.000 (two dates of birth) L-001750 / G-000077 score 1.000 (two dates of birth) L-005021 / G-002529 score 1.000 (two dates of birth) L-001790 / G-000121 score 1.000 (two dates of birth) S-001111 / G-000121 score 1.000 (two dates of birth)Saved to outputs/clusters/lgbm-safe.csvLook at the scores of these first cuts: 1.000, rounded. In those clusters, LightGBM was very sure about every link, and the records still hold two dates of birth. The checks catch errors that the model’s score cannot show.
The largest cluster now has 6 records. Safe clustering cut 679 links. Most cuts had the reason “two dates of birth” (676); some clusters were also too large (74). One cut can have both reasons.
match eval now prints both clusterings, with measures of the clusters. We meet these measures fully in lesson 4. For now, read one of them: B-cubed precision. For each record, it asks: what share of its cluster is the same person? Then it takes the mean over the records. 1.0 means no cluster holds two people.
match eval --run lgbmlgbm on the test split: pair precision 0.918, recall 0.886, F1 0.902 5,375 pairs called the same: 4,932 right, 443 wrong; 632 of 5,564 true pairs missed entities after clustering (all records): 38,514 (true: 37,500) connected components: 38,514 entities, largest 9 records, 75 clusters over 5 records B-cubed precision 0.979, recall 0.967; cluster pairs precision 0.838, recall 0.917; exact clusters precision 0.873, recall 0.913 safe clustering: 38,908 entities, largest 6 records, 11 clusters over 5 records B-cubed precision 0.987, recall 0.965; cluster pairs precision 0.911, recall 0.909; exact clusters precision 0.880, recall 0.923Read the two lines that start with “connected components” and “safe clustering”:
| Clustering | Entities | Largest | B-cubed precision | B-cubed recall |
|---|---|---|---|---|
| connected components | 38,514 | 9 | 0.979 | 0.967 |
| safe clustering | 38,908 | 6 | 0.987 | 0.965 |
B-cubed precision rises from 0.979 to 0.987. Recall falls a little, from 0.967 to 0.965: some cuts split a true customer. The number of entities moves from 38,514 to 38,908, against 37,500 true customers.
Every matcher, before and after
Section titled “Every matcher, before and after”The checks help every matcher. They help most where the matcher makes many wrong links.
- Connected components
- Safe clustering
Text description of the chart
A dot chart with two rows per run: one for connected components and one for safe clustering. exact-norm: 0.981 with connected components, 0.995 with safe clustering. rules: 0.917 with connected components, 0.974 with safe clustering. rule-phone: 0.941 with connected components, 0.969 with safe clustering. weighted: 0.937 with connected components, 0.962 with safe clustering. splink: 0.954 with connected components, 0.975 with safe clustering. lgbm: 0.979 with connected components, 0.987 with safe clustering. Safe clustering is higher on every row. The gain is largest for the rules (0.917 to 0.974) and smallest for exact-norm, which makes few links.
| Run | Largest cluster, connected components | Largest cluster, safe clustering | Links cut |
|---|---|---|---|
| exact-norm | 6 | 4 | 1,262 |
| rules | 14 | 6 | 5,404 |
| rule-phone | 40 | 6 | 4,406 |
| weighted | 12 | 6 | 2,318 |
| splink | 11 | 6 | 1,714 |
| lgbm | 9 | 6 | 679 |
The giant cluster of the last lesson is gone too, but look closely. Only 4 of the 40 garden-centre records of the placeholder phone have a date of birth. Only the size check acts on them, and it cuts them into clusters of at most 6 records. Those smaller clusters are still wrong. The size check limits the damage. It does not remove it. Only the fix of the last lesson does: treat the placeholder phone as missing.
When to use it, and what it costs
Section titled “When to use it, and what it costs”- Use checks that every true entity passes. They must come from facts about the real world: one date of birth per person, one tax number per company, one barcode per product. A check that true entities fail splits them.
- Each check only sees what is in the records. 85% of garden-centre records have no date of birth. The date-of-birth check cannot protect those clusters. The size check still can.
- It costs some recall. LightGBM’s B-cubed recall falls from 0.967 to 0.965. A false merge costs Larkfield an assumed 150 dollars; a missed match, 3 dollars a year. So this trade is good here. With other costs, it may not be.
- It is cheap to run. Only the clusters that fail are cut, and they are small. The project uses NetworkX for the links of those clusters.
- Keep the log. Every cut has a record pair, a score and a reason. Ivana can check the cuts, and you can count them by reason.
Common mistake
A check on raw values splits true customers
Symptom: TermTomásLarkfield’s AI engineer. He often suggests a quick shortcut, and the lesson shows why it fails. writes his own date-of-birth check. He compares the dates as the sources typed them. Valérie Tremblay’s loyalty record says 31/01/1975 and her shop record says 1975-01-31. His check says “two dates of birth” and cuts her entity in two. Thousands of true customers are split the same way.
Cause: the check compared values in different formats. The same date, written two ways, looks like two dates. A check is only as good as the values it compares.
Fix: run checks on the clean values of Module 2, where every date is YYYY-MM-DD. Allow the known harmless difference, a day and a month swapped. Test the check on records that you know are one person before you trust it.
Consequence in AI work: a data-quality rule on raw values gives false alarms. A model monitor, a validation rule or a guardrail can fail the same way. Validation rules in SQL and Data Preparation for AI shows how to write rules on clean values and test them.
Knowledge check
Section titled “Knowledge check”Check your understanding
A cluster has four records with the dates of birth 1980-03-14, (empty), 1980-14-03 and 1980-03-14. Does it fail the date-of-birth check?
Show the answer
No. The empty date is no evidence. 1980-14-03 is 1980-03-14 with the day and the month swapped, and the check counts that as the same date. So the cluster holds one date of birth, and it passes. It would fail only with a really different date, for example 1981-03-14.
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
Safe clustering cuts the link with the lowest score first. Why not cut the link with the highest score, or a random link?
Show the answer
The lowest score is the model’s own best guess at the wrong link. Cutting the highest score removes the link that the model trusts most, and the cluster would probably still fail. A random link ignores the evidence that we have. The guess is not perfect: of LightGBM’s 679 cuts, 463 join two different customers, and the rest cut a link inside one customer.
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
Safe clustering raises LightGBM's B-cubed precision from 0.979 to 0.987, and lowers recall from 0.967 to 0.965. Omar asks: is that a good trade?
Show the answer
At Larkfield’s assumed costs, yes. A false merge costs about 150 dollars: a stranger sees another customer’s orders and address. A missed match costs about 3 dollars a year: a double email or catalogue. Precision protects against the expensive error, and the loss of recall is small. If a missed match were very costly, for example in fraud detection, the answer could change. Then you would keep the cut clusters for review instead.
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 check is a rule that every true entity passes. Larkfield has three: no two dates of birth, no more than 6 records, and no cannot-link pair. A cannot-link pair is a pair that a person marked “not the same”.
- When a cluster fails, cut its weakest link (the lowest score), then check each part again.
- For LightGBM, safe clustering cuts 679 links. The largest cluster falls from 9 to 6 records. B-cubed precision rises from 0.979 to 0.987, and recall falls from 0.967 to 0.965.
- The checks help every matcher, most where it makes many wrong links.
- Run checks on clean values, and keep a log of every cut.
Next, each entity gets one golden record, built field by field from its records.
Next: The golden record