Skip to content
Français

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".

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

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 notebookColab · Kaggle · GitHub

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 readyAbout 35 minutes

What you need to know

What you need on your computer

  • The project larkfield-match with the files of Module 7, copied in the previous lesson. Or use the notebook only.

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:

RecordSourceName, as typedDate of birth (clean)
G-000554gardenOUELLET, NATHAOIE1950-10-21
G-002354gardenOUELLET, NATHALIE(empty)
L-016649loyaltyNathalie Ouellet1992-12-06
S-029847shopNathalie Ouellet1950-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.

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:

  1. 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-31 and 1975-31-01, count as the same date.
  2. 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.
  3. 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.

Here is the cluster from the table, with its 4 links and LightGBM’s score for each link.

4 records of one LightGBM cluster: G-000554, OUELLET, NATHAOIE, born 1950-10-21; G-002354, OUELLET, NATHALIE, born empty; L-016649, Nathalie Ouellet, born 1992-12-06; S-029847, Nathalie Ouellet, born 1950-10-21. Links with their scores: G-000554 to S-029847 0.999999; G-002354 to L-016649 0.999938; G-002354 to S-029847 0.999926; G-000554 to G-002354 0.999736. Safe clustering cuts cut 1: G-000554 to G-002354, score 0.999736; cut 2: G-002354 to S-029847, score 0.999926. After the cuts: G-000554 and S-029847; G-002354 and L-016649.
One real cluster of LightGBM's links in the synthetic records. Safe clustering cuts the weakest link until no part holds two dates of birth.
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.

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.

match cluster has a new option, --method safe. --show-cuts 5 prints the first five links that it cuts:

Terminal window
match cluster --run lgbm --method safe --show-cuts 5
lgbm (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.csv

Look 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.

Terminal window
match eval --run lgbm
lgbm 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.923

Read 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.

The checks help every matcher. They help most where the matcher makes many wrong links.

  • Connected components
  • Safe clustering
B-cubed precision of six runs, with connected components and with safe clustering, on the test split of the synthetic records. Measured.
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.

RunLargest cluster, connected componentsLargest cluster, safe clusteringLinks cut
exact-norm641,262
rules1465,404
rule-phone4064,406
weighted1262,318
splink1161,714
lgbm96679

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.

  • 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.

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.

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.

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.

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