# Presentation: 304123

## “Record Linking 101”

- Combining Files without a Common Identifier
*SAMHSA Integrated Database Project*

**Notes:**
Welcome to the “Record Linking 101” and thank you for coming
This workshop is a product of SAMHSA’s Integrated Database Project

## SAMHSA Integrated Data Project

- Center for Mental Health Services
- Center for Substance Abuse Services
- Contractors
- The MEDSTAT Group, Inc.
- National Association of State Mental Health Program Directors Research Institute (NASMHPD)
- National Association of State Alcohol and Drug Abuse Directors, Inc. (NASADAD)

**Notes:**
The Integrated Database Project is a contract jointly funded by SAMHSA’s
Center for Substance Abuse Treatment
Center for Mental Health Services
One goal of this project is providing technical assistance to states for integrating and using MH, SA, and Medicaid data
Contractors on this project include
The Medstat Group
NASMHPD
NASADAD
Medstat is the principal contractor for this project

## Agenda

- Probabilistic linking vs. match-merging
- Comparisons
- Benefits
- Match-merge linking
- Probabilistic and deterministic linking
- Identifying variables
- Comparisons
- Weights & scores

**Notes:**
This workshop explores the basics of record linking. Much of the workshop is based on a paper we wrote for SAMHSA, which is included with the supplemental materials.
The paper is based on our experiences in trying to explain probabilistic record linking to others 
So we do not jump right into probabilistic record linking
We’ll start with smaller pieces and then (like magic) put everything together at the end

Here is a quick overview of today’s topics
We will start with a brief linking comparison and discussion of some benefits from probabilistic linking
A short review of match-merging will follow
The remainder of our time will be spent exploring different concepts and techniques used with probabilistic linking
Finally, we will provide an understanding of how it all fits together.

## General Comparison of Linking

- Based on analysis of two states
- Relative to overlap from Probabilistic Population Estimate (Pandiani & Banks)
- Links found
- Probabilistic linking: 80-86%
- Match merge: 51-72%
- Deterministic links: 59-76%

**Notes:**
Let’s start with a comparison of how probabilistic record linking compares with other techniques
These numbers reflect our experience in constructing integrated MH-SA-Medicaid databases

This comparison looks at the number of links found compared with the potential number of links that could be found.
We used Probabilistic Population Estimation to estimate the potential overlap between data sources, we then determined how many of the potential links each method found

Probabilistic linking consistently found more links than other methods
The more sophisticated the deterministic linking, the better the results
Deterministic linking that uses blocking were the most effective of the deterministic linking methods

## Accuracy of Methods

| (1) | (2) | (3) | (4) | (5) | (6) |
| --- | --- | --- | --- | --- | --- |
| 

State | 
Probabilistic Linking Total | Links Not Found with Match Merge | 
Common Links | False Links from Match Merge | 
Match Merge Total |
| Delaware | 5,612 | 1,488 | 4,124 | 523 | 4,647 |
| Oklahoma | 38,683 | 18,655 | 20,028 | 6,809 | 26,837 |
| WashingtonAOD-Medicaid | 14,836 | 4,766 | 10,070                                                | 588 | 10,658 |
| WashingtonMH-Medicaid | 56,990 | 35,135 | 21,855 | 995 | 22,850 |
| WashingtonAOD-MH | 7,830 | 6,562 | 1,268 | 2,412 | 3,680 |

**Notes:**
Not all found links are the same – match merging can create erroneous results
Here we compare specific linking results from probabilistic linking and match merging
Here, the match merge was on SSN

Column 2 shows the number of links found with probabilistic linking
Column 6 shows the number of links found with match merging
Column 4 shows the number of links in common between these two methods

Column 3 shows links that were not identified using match merging – “false negatives” from the perspective of match-merge
Low of 27% (Delaware)
High of 84% (Washington AOD-MH)
Column 5 shows “false positives” – match-merge linked clients that should not have been linked
Low of 4% (Washington MH-Medicaid – very few MH records contained SSN)
High of 66% (Washington AOD-MH)

## Match-Merge Methods

- Familiar concept in data processing
- Uses keys (identical variables) on each file
- Records are combined (merged) when the respective keys on each file are the same (match)
- Records are not combined when the keys are different
- Keys can be simple or complex

**Notes:**
The first topic is Match-Merging
This is familiar – most of you have done this a few thousand times
Files are combined using keys
Keys can be simple, a single variable such as an ID or SSN
Keys might be complex, consisting of several variables, such as State, Provider, and Date

## Match-Merging Related Files

- Match-merging files from a single authority is usually very accurate
- Agency specific identifiers are often used as file keys
- Identifiers from a single authority are generally reliable – errors are rare

**Notes:**
Match-merging files from an agency (or company or some other single entity) is usually error free – particularly when the key or keys are specific to the agency
This is because agency specific identifiers are usually quite accurate
There is a positive feedback loop involved with agency identifiers – all parties have a vested interest
Patients need valid IDs to receive services
Providers must supply valid IDs to receive payments for services
Claims processors require valid IDs to pay claims

## Problems with Match-Merge Methods

- Problems when keys are incorrect
- May occur because of omissions and errors
- Two outcomes:
- Records do not match when they should
- Records match when they should not

**Notes:**
However, nothing is perfect – there can be problems with match-merging
Match-merging relies on keys and if there are problems with the keys there will be problems with the match-merge
Incorrect information may be due to either omissions or errors
Patients may not want to provide information such as a SSN, or they may be unable to supply information
Patients may supply correct information which is then recorded incorrectly
The main point is that “key” errors result in match-merge errors

## Match-Merging Unrelated Files

- There are often problems merging files from separate agencies – even with a common identifier (i.e., SSN)
- Omissions and errors are more prevalent with identifiers that are not specific to an agency
- Manual review of SSN match-merges reveal many errors
- records that should be linked but are not
- incorrect links

**Notes:**
Merging files from different agencies isn’t as simple
A common strategy for linking people across different agencies is to use SSN
Using SSN Merging Medicaid data with MH data using SSN are prone to errors. 
Medicaid and MH/AOD agencies usually collect SSN – but not always
But generally they don’t require a SSN
It’s problematic – they aren’t able to issue SSN – what do they do if someone doesn’t have a SSN?
If they are not required, what can happen? Errors are common
Omissions
Incorrectly reported
No verification

## A Linking Tangent – Background

| File A |  |
| --- | --- |
| ID | Var1 |
| 1 | E |
| 2 | F |
| 3 | G |

| File B |  |
| --- | --- |
| ID | Var2 |
| 1 | X |
| 3 | Y |
| 4 | Z |

- Two simple files:
- File A
- File B
- Both with a variable “ID” as their key

**Notes:**
There’s a little detour before we go on
I want to take a few minutes to demonstrate different ways of linking data
So lets consider two simple files
Each with a variable “ID” as their key
File A has a variable Var1
File B has a variable Var2

## A Match-Merge

- Match-merge on ID

| Match-merge Results |  |  |
| --- | --- | --- |
| ID | Var1 | Var2 |
| 1 | E | X |
| 3 | G | Y |

**Notes:**
Match-merging files A and B is simple, easy
Both files have records with IDs 1 and 3 and that what the resulting file has

## Probabilistic and Deterministic Linking

- Related techniques – overcome limitations of match merging
- Makes linking possible, even with
- Missing information
- Errors in data
- Uses multiple criteria
- More work than match-merging

**Notes:**
Deterministic linking is often used to overcome the limitations of match-merging
It combines data using identifying information such as name and DOB and SSN
The message I have about SSN isn’t that it’s bad, but that it isn’t enough
With deterministic linking, comparisons are made using identifying information
If you remember what a phone book is, it is much like looking for someone in a phone book
Each agreement or disagreement adds information

## Terminology

***Record-pair*** – a combination of records from two files such that one half of each pair is derived from the first file and the remainder is from the second file

**Notes:**
We will review some terminology as we go along
The first concept is “record-pair” ...

## A Conceptual Linking Example

| File A |  |
| --- | --- |
| ID | Var1 |
| 1 | E |
| 2 | F |
| 3 | G |

| File B |  |
| --- | --- |
| ID | Var2 |
| 1 | X |
| 3 | Y |
| 4 | Z |

- Two simple files:
- File A
- File B
- Both with a variable “ID” as their key

**Notes:**
There’s a little detour before we go on to demonstrate different ways of linking data
Consider the same two simple files we used for a match-merge
Each with a variable “ID” as their key
File A has a variable Var1
File B has a variable Var2

Here is an alternative linking process – this isn’t something you would probably do, but it is a good introduction to the linking discussions we will have in a few minutes.

## More Terminology

***Links*** – record-pairs that represent the same person or entity (a.k.a. linked). In match merging, the "matched" records are links
***Non-links*** – record-pairs that do not represent the same person or entity

**Notes:**
More terminology...

## More Terminology

***Joined Records*** – a collection of record-pairs: all the joined records (the sum of all links and non-links)
***Decision Space*** – the complete set of record-pairs that are evaluated to determine links

**Notes:**
More terminology...

## More Terminology

***Cartesian Product*** – a set of joined records constructed from two files such that each record from the first file is paired with every record from the second file, as depicted below

| Record |  | File 2 |  |  |
| --- | --- | --- | --- | --- |
|  |  | X | Y | Z |
| File 1 | L | L-X | L-Y | L-Z |
|  | M | M-X | M-Y | M-Z |
|  | N | N-X | N-Y | N-Z |

**Notes:**
Cartesian product
And this is a simple Cartesian table from two 3-record files
L-X represents the record-pair of the “L” record from file 1 and the “X” record from file 2
The joined records are the 9 record-pairs – this is the decision space

For our project, we used SQL to create Cartesian tables

## Record-Pairing

- An alternate method to link files
**Cartesian product**

| Combined Files |  |  |  |
| --- | --- | --- | --- |
| A.ID | B.ID | Var1 | Var2 |
| 1 | 1 | E | X |
| 1 | 3 | E | Y |
| 1 | 4 | E | Z |
| 2 | 1 | F | X |
| 2 | 3 | F | Y |
| 2 | 4 | F | Z |
| 3 | 1 | G | X |
| 3 | 3 | G | Y |
| 3 | 4 | G | Z |

**Notes:**
Now think about a simple match-merge in a different light
Instead of a simple match-merge, link the files by creating the cartesian product of the two files, joining each record from file A with each of the records from file B
Each input file has 3 records, the result is 9 record-pairs
You would probably never a match-merge this way, but it helps put some context around the things we will be talking about

## Record-Pairing

- An alternate method to link files
- Cartesian product
**Evaluate keys:****A.ID = B.ID **

| Combined Files |  |  |  |
| --- | --- | --- | --- |
| A.ID | B.ID | Var1 | Var2 |
| 1 | 1 | E | X |
| 1 | 3 | E | Y |
| 1 | 4 | E | Z |
| 2 | 1 | F | X |
| 2 | 3 | F | Y |
| 2 | 4 | F | Z |
| 3 | 1 | G | X |
| 3 | 3 | G | Y |
| 3 | 4 | G | Z |

**Notes:**
Next, look for record-pairs where the value for ID in file A is equal to the value for ID in file B
That is the 1st and 8th row

## Record-Pairing

- An alternate method to link files
- Cartesian product
- Evaluate keys:A.ID = B.ID
**Keep pairs where the IDs are the same**

| Combined Files |  |  |  |
| --- | --- | --- | --- |
| A.ID | B.ID | Var1 | Var2 |
| 1 | 1 | E | X |
| 3 | 3 | G | Y |

**Notes:**
Which we keep – throwing out all the other record-pairs – the record pairs where the IDs were not equal
The results are the same as the simple match-merge
Basically a lot of extra work for the same results

## Extending the Conceptual Example

- Decision rule: a function of A.ID and B.ID
- Keep (or true or 1) if A.ID=B.ID
- Remove (or false or 0) if A.IDB.ID
- With “match-merging,” ID is a single variable
- Extend concept for deterministic and probabilistic linking
- ID is a collection of variables

**Notes:**
In the example we just walked through, there was a simple decision rule used to decide linking
True if file A’s ID equaled file B’s ID
False when they are not equal
One variable (ID) from each of the two files
Probabilistic and deterministic linking can be thought of with that same framework
but instead of a single variable, ID is a collection of variables
And instead of a simple equals/not-equals decision rule, we have something more complex

## Identifying Variables

- Information that _can_ identify a person
- Directly
- Indirectly
- Linking requires identifying variables
- Used in “decision rules” to determine links

**Notes:**
Think of examples of identifying variables available with your data
Last name?
SSN?

What else? Make a list, we’ll use it in a moment

## More Terminology

***Identifying Variables*** – information that can be used to identify a person. This includes direct identifiers such as name and indirect identifiers such as date of birth and race

**Notes:**
More terminology...

## Examples of Identifiers

- ID numbers (i.e., SSN)
- Name
- Gender
- Address
- Finger print
- DOB
- Race
- Telephone number

**Notes:**
Here are some examples

## Weak and Strong Identifiers

- Some identifiers are “weak”
- By themselves, they do not directly identify a person
- They must be used with other information to work as an identifier
- Other identifiers are “strong”
- They can be used to directly identify a person

**Notes:**
Look at your list of identifying variables and classify them as “weak” or “strong”

## Examples of Identifiers

|  ID numbers (i.e., SSN) | Strong |
| --- | --- |
|  Name | Strong |
|  Gender | Very weak |
|  Address | In between |
|  Finger print | Very strong |
|  DOB | Weak |
|  Race | Very weak |
|  Telephone number | In between |

**Notes:**
Examples of identifying variables are
Name
SSN
Finger print
DOB
Gender
Race
Telephone number

## Useful identifiers

- As a general rule, strong identifiers are better than weak ones
- But strong is not the same as good or useful
- A useful identifier is available on all files
- An identifier found on a single file cannot be used for comparisons

## Comparing Identifiers

- Record-pairs are evaluated with comparisons
- Compare each and every set of identifying variables
- Look for
- Agreement
- Disagreement

**Notes:**
Comparisons are the tool we use to evaluate the record-pairs in our decision space
Think of the two records in a record-pair as LEFT and RIGHT
If you’re a programmer or familiar with SQL, then this should be a useful way to think about things
For each record-pair, we compare the identifying variables – when they are available
The left SSN with the right SSN
The left first name with the right first name
And so-on, until we have cone comparisons for all the identifying variables
From the comparisons, we look for either agreement or disagreement

## More Terminology

***Comparison Variables*** – identifying variables used in comparing the two halves of a record-pair
***Comparisons*** – the result of equating comparison variables from a record-pair. Record-pairs typically contain a mixture of comparisons in both agreement and disagreement. Comparisons are part of the process of evaluating record-pairs to determine links

**Notes:**
All comparison variables are identifying variables,

So if we had 3 comparison variables we would make three comparisons

But not all identifying variables are comparison variables
A comparison variable must be available on both files
An identifying variable might be available only on one file

## Types of Comparisons

- Comparisons can be dichotomous or continuous
- Dichotomous – true or false
- No gray areas, unforgiving of errors and mistakes
- Example: gender – either the same or different
- Continuous – a continuum
- Indicates the degree of agreement
- Forgiving of mistakes/errors

**Notes:**
There are two types of comparison results: dichotomous and continuous
Dichotomous comparisons
true/false or 1/0
There is no grey with dichotomous comparisons, there is either agreement or there isn’t
Works well for comparisons of gender
Continuous – some range along a continuum from agreement to disagreement
There are degrees of agreement, rather than the absolutes of dichotomous agreements
Continuous comparisons can overcome spelling mistakes and transpositions of numbers
Useful for names and IDs
You can use a dichotomous comparison for any variable, but often at the cost of losing some information
A misspelling with a name will generate a dichotomous disagreement even if the difference is minor
So continuous comparisons are usually preferable, but
They are sometimes difficult to define
They are more complex to code

## More Terminology

***Dichotomous Comparisons*** – comparisons which evaluate as either true or false – agreement or disagreement
***Continuous Comparisons*** – comparisons resulting in a numeric score that reflects partial agreement ranging from complete disagreement to complete agreement.

**Notes:**
Dichotomous – there are no gray areas here

Continuous – grey area big time
Many web searches use this type of measure – telling you that a page matches some percent to your query

## Comparing Names

- Misspellings often occur with names
- Anderson and Andersen
- Whalen and Whelan
- Phonetic equivalents sometimes used to account for differences in spelling
- Russell Soundex
- New York State Identification Information System (NYSIIS)

**Notes:**
Another short side-trip to talk about names and phonetic equivalents
Names are often misspelled
And people have devised many ways to accommodate those misspellings
One method are phonetic equivalents like
Russell Soundex
	and
New York State Identification Information System  or NYSIIS
Phonetics can overcome some misspellings, but at the cost of hiding differences that may be important

## Phonetic Names

| Name | Soundex | NYSIIS |
| --- | --- | --- |
| Whalen | W45 | WALAN |
| Whelan | W45 | WALAN |
| Graber | G616 | GRABAR |
| Gerber | G616 | GARBAR |
| Aijian | A25 | AJAN |
| Askam | A25 | ASCAN |
| Haskens | H252 | HASCAN |
| Haskant | H253 | HASCAN |

**equal**

**equal**

**equal**

**equal**

**equal**

**Notes:**
Here are a few examples of Soundex and NYSIIS phonetics
The first name on the list is mine, and the second is another spelling that is often used – the Soundex and NYSIIS are the same for each
The other six names I pulled from a phone book to show that very different names may generate identical phonetics
This doesn’t demonstrate that Soundex is better or worse than NYSIIS
This shows that they create different results
Phonetics can overcome some misspellings, but at the cost of hiding differences that may be important

Look at the four name pairs, if we compare each of the pairs – simple dichotomous comparisons – we get four disagreements
With these four name pairs
Three agreements with Soundex (1, 2, and 3)
Two agreements with NYSIIS (1 & 4)

Dichotomous comparisons such as these don’t always make intuitive sense
The first name pair seems “pretty close,” so the Soundex and NYSIIS agreement makes sense
But the third pair: AIJIAN and ASKAM seem very different
The main similarity is the common first letter
So the Soundex agreement seems wrong to me

## Approximate String Matching

- A continuous comparison
- Calculates degree of agreement
- Additions/Deletions/Changes
- Percentage based on name lengths
- WHALEN & WHELAN2 changes  66.7% agreement
- AIJIAN & ASKAM3 changes + 1 addition (or deletion)
-  26.7% agreement

**Notes:**
An alternative to the dichotomous comparisons are continuous comparisons -- something that can quantify the degree of agreement
There are a number of methods to do this
Bigrams are the simplest
The U.S. Census Bureau is the most complex I’ve seen
We have used Approximate String Matching or ASM
ASM calculates the degree of agreement as a function of the number of changes necessary to make two strings agree and the length of the strings
ASM examples – two of the name pairs from the previous slide
First WHALEN and WHELAN
Both names are 6 letters in length
It takes 2 changes to make the two names agree
33.3% disagreement -> 66.7% agreement 
In the second example, AIJIAN and ASKAM
The lengths are 6 and 5 letters respectively
AIJIAN needs 3 changes and 1 deletion for 20% agreement
ASKAM needs 3 changes and 1 addition for 33% agreement
The average is 26.7% agreement

## Weights

- A comparison variable’s overall importance in determining links is quantified as a *comparison weight*
- Weights signify the relative importance of variables
- Higher points for more important information
- Lower points for less important information
- Links made for records pairs with a point total over a predefined threshold

**Notes:**
With probabilistic and deterministic linking, comparisons are made using identifying information
A variable’s importance – the discriminating power of the variable – is expressed as a weight

Not all comparison variables are of equal importance in determining links
Weights signify the importance of a variable to determining links
Weights QUANTIFY the importance of that comparison – think of weights as points
Each agreement adds a certain number of points
Each disagreement subtracts a different number of points
All the points are totaled
Only records with a point total over some predefined threshold are linked

## More Terminology

***Weights*** – numeric values that indicate the overall importance of a comparison relative to other comparisons. The discriminating power of each comparison variable – its importance in determining links – is expressed as a weight.

**Notes:**
More terminology...

## Types of weights

- Deterministic weights
- Arbitrarily determined before the linking process
- Probabilistic weights
- Calculated from the relative probabilities of agreement (or disagreement)
*Weight = log**2** [ Pr(agree | link) / Pr(agree | non-link) ]*
- Agreement and disagreement weights
- For each comparison variable
- Not symmetrical

**Notes:**
Deterministic weights are set beforehand and do not change

Probabilistic weights are determined through the process and are unique to each set of data
Calculated from the log of the relative probabilities of agreement or disagreement
Both agreements and disagreements are useful
The usual focus is on agreements, but disagreements are important
Agreement and disagreement weights are not symmetrical
If the agreement weight is 5, the disagreement weight is not necessarily -5, or -1/5
Take gender as an example – for non-links the probability for gender agreement  - or disagreement – should be 50% just from chance
The probability of gender agreement for links should approach 100% and the agreement weight should approach 1 – as the link probability approaches 100%
And gender disagreement with links should approach 0%, with the disagreement weight approaching negative infinity

For both probabilistic and deterministic linking, weights should represent the relative importance of an agreement	

## Points for Deterministic Agreements

- Points for “agreements” should reflect the relative importance of that agreement
- Higher points for more important information(i.e., SSN)
- Lower points for less important information(i.e., gender)
- Negative points for disagreements are also possible, but not often employed

**Notes:**
Most of us would think that SSN is more important than Gender for linking
Your SSN should be unique to you
But you share by gender with approximately 1⁄2 the population
So it makes sense to us that agreement points for SSN should be larger than the points for Gender agreement

## A Deterministic Linking Example

- Comparison Points
- 20 points for a complete SSN agreement, or10 points for agreement on the last four digits of the SSNs
- 15 points for an agreement on last name
- 8 points for an agreement on first name
- 5 points for a date of birth agreement
- 1 point for a gender agreement, or
- 		10 points if gender does not agree
- Linking Threshold: 25 or more points

**Notes:**
Here are points for a hypothetical deterministic linking example
Point values were arbitrarily – similar to many examples used by states
Included negative points for gender disagreements
There could be negative points for all the comparisons
There is a threshold of 25 points in this example – another arbitrary number 

So what are the problems here?

## More Terminology

***Score*** & ***Scoring*** – the sum of the products of all the comparisons with the associated weights. The score is used to evaluate record-pairs and determine links and non-links. When weights are applied and summed into scores, the scores for record-pairs that should be linked are generally higher than scores for the record-pairs that should not be linked.

**Notes:**
More terminology...

## Deterministic Linking Problems

- Setting Points and Thresholds
- Appropriate points for agreement
- Effective point thresholds
- How should it be done?
- Trial and Error?
- Intuition?
*Recall: point values should reflect the relative importance of an agreement (or disagreement)*

**Notes:**
Nothing is perfect
The big problem with deterministic linking – or perhaps “issues” is a better description – is setting agreement points and linking thresholds
How do you set the values? 
In the previous example they were made up
Earlier we stated that SSN is more important than Gender – and in the example SSN points were higher than Gender points – SSN agreements generated the highest number of points
SSN points are also higher than DOB
That makes intuitive sense, but look at SSN and DOB again
SSN points are 4 time as large as DOB points
Does that represent the relative importance of SSN and DOB?
Should the ratio be 3? ...or 5? ...or something else?
The answer, which we hope we show a little later, depends upon the populations of the data

## Deterministic Linking (continued)

- A clear improvement over match merging
- Record linkage is possible even with errors, or missing information
- When SSN is not available
- Errors in SSN do not necessarily cause incorrect links

**Notes:**
With deterministic linking, an agreement (or lack of agreement) on any one piece of information is not sufficient evidence determining a link or non-link
Because of that point, it is an improvement over match-merging of files without a common ID
Although there are still problems that we can address with other tools and techniques

## Probabilistic Linking

- Similar to deterministic linking
- Multiple criteria/comparisons
- Scores to determine links
- Differences from deterministic linking
- Points and scoring not known beforehand
- Commonly uses disagreements as well as agreements
- More complex

**Notes:**
This brings us to probabilistic record linking
It’s similar to deterministic linking
Both use multiple pieces of identifying information
The main differences have to do with points and scoring
With deterministic linking, the points were determined before the linking was started
With probabilistic linking, Points – which we will start referring to as “weights” – are determined by the data and can differ over time
Probabilistic linking is more flexible – it overcomes the main difficulty with deterministic linking, which was setting the points and thresholds
It’s also common with probabilistic linking to use disagreements and negative points – this is more of a style difference since you could do use disagreements with deterministic linking as well
Finally, probabilistic linking is more complex to set up

## Determining Probabilistic Weights

- Which comes first, weights or links?
- Weights needed to divide record-pairs into links and non-links
- Link/non-link division necessary to calculate weights
- Solutions
- Sample files
- Iterative process

**Notes:**
Weights are unique for each combination of joined files – each set of new files requires recalculation
There is some circular logic in these explanations
We need weights to decide what is and isn’t a link
But we need that division before we can calculate the weights
There are a couple of solutions

The first is to calculate weights, before the process – using a sample file
Links between the sample files are determined by hand
These links are used to calculate weights which are applied to the complete data files
There are some problems with this method
Sampling and manual reviews are time consuming
Larger samples produce better weights but take more time to review

An alternative method is an iterative process
Start with some automatic linking (i.e., deterministic linking) to classify the links and non-links
Calculate weights based on these groupings
Reclassify links and non-links using the weights
In building the IDB we used the original deterministic linking criteria to make decisions about the uncertain record-pairs
Then, you can go through another iteration
Recalculate weights and do the link/non-links again
For the final iteration, a manual review can be used to decide the uncertain record-pairs
If the process is correctly set up and good data are available, the number of uncertain record-pairs should be of a manageable size for human (non-automated) review.

## More Terminology

***Scaling*** – adjusting the weight for a comparison variable to reflect the relative frequency of a specific value.

**Notes:**
More terminology...

## Scaling Weights

- Some weights are _scaled_ – adjusted up or down for specific values
- Scaling factors inversely related to the relative frequency of the identifier’s value
- Not an issue for evenly distributed identifiers (i.e., SSN and gender)
- Used for identifiers not evenly distributed (i.e., last-name and race)

**Notes:**
In the IDB linking, we scale some weights where a variable’s values are not uniformly distributed
Determining the relative importance of a variable’s value
If the values for a variable are uniformly distributed, then scaling is not necessary
All the values are equally likely
SSN should be uniformly distributed – one SSN per person – so it is not scaled
Gender is another example – 1⁄2 of the overall population is male and the other 1⁄2 is female
If you’re working with a specific subset of the population where this isn’t true, then you might think about scaling Gender
But names are not uniformly distributed, some names are more common than others
Agreement on an uncommon name should contribute more linking information than agreement on a common name
The same is true with birth dates – there is some cyclical pattern in births
Race and geographic location are other examples

## Other Linking Issues

- File size
- Blocking
- Scores

**Notes:**
Here are a few important issues we encounter in actual record linking
We will look at each of these issues in a moment

## File Size Issues

- Recall that the initial decision space for linking two files is the Cartesian product of those two files
- As file size increases
- The decision space increases exponentially
- The proportion of potential links decreases

|  |  |  | Potential Links |  |
| --- | --- | --- | --- | --- |
| File A | File B | Decision Space | Number | Proportion |
| 100 | 100 | 10,000 | 100 | 1.000% |
| 1,000 | 1,000 |  |  |  |
| 10,000 | 10,000 |  |  |  |
| 100,000 | 100,000 |  |  |  |

- 1,000,000

*1,000*

*0.100%*

- 100,000,000

*10,000*

*0.010%*

- 10,000,000,000

*100,000*

*0.001%*

**Notes:**
Go back to the definition of decision space
The decision space is “the complete set of record-pairs that are evaluated to determine links”
Theoretically, the decision space is the Cartesian product of the files
And the Cartesian Product  is “a set of joined records constructed from two files such that each record from the first file is paired with every record from the second file, as depicted below”
For the simple example we walked through a few minutes ago, size wasn’t much of an issue
There were 3 records in each file
The decision space was 9 record pairs
However, as files get larger size becomes a big problem (pardon the pun)

In these examples, the two files are the same size – for files of roughly equal size, as the size of the file size increases
The number of potential links – the potential can be no larger than the smallest file – the number of potential links increases linearly with the file size
But the size of the decision space increases exponentially
So the proportion of potential links in the decision space decreases

## Blocking

- Blocking is the process of creating record-pairs only when there is some evidence for linking the two records
- Blocking decreases the decision space, reducing the number of comparisons necessary
- Eliminates record-pairs with no linking evidence
- Results in more efficient search for links
- The importance of blocking increases as the size of files increase

**Notes:**
To lessen the problems that come with larger files, we use blocking
Blocking is an efficiency tool
Blocking creates record-pairs only when there is some evidence for linking the two records
The idea is to eliminate record-pairs that lack evidence for a link
For example there is no real point in looking at record-pairs where none of the identifying information is in agreement, i.e.,
Different names & IDs
Different DOBs
And
Different genders
The result is a smaller decision space and a more efficient link search
Because the files we use tend to be large, blocking becomes an important issue and tool
Here is an important point – blocking doesn’t eliminate the number of record-pairs that are not links, it’s a tool that tries to keep the number of non-link record-pairs to a manageable level

Here are the numbers from our linking of the Washington data
DASA, MH, and Medicaid data
The potential decision space was nearly 185 Billion record-pairs
Because of blocking it was much smaller – around 7 million record-pairs

## More Terminology

***Blocking*** – a technique to limit the decision space to a manageable size without eliminating potential links

**Notes:**
More terminology...

## Linking Scores

- Scores are the sum of all comparisons
- Agreements
- Disagreements
- Combines comparisons, weights, and scaling factors
- For each comparison variable, calculated as
- Agreement | disagreement weight
- Multiplied by the comparison result
- Plus any scaling factor for the variable’s value

**Notes:**
Scoring pulls together
Comparisons results – agreements and disagreements
Weights – the importance of comparison variables in determining links
	and
Scaling factors - the relative importance of specific variable values

Each variable’s contribution to the score is
The comparison result:0 or 1 (dichotomous) – or – a decimal (continuous)
Multiplied by the variable agreement (or disagreement) weight
Plus the scaling factor for the variable and value

The score is then calculated by summing each variable’s contribution

## Record-Pair Scores

- Scores for record-pairs will vary
- Scores for links are generally higher than scores fornon-links

**Notes:**
Each record-pair is scored
If the decision space is 10,000 record pairs, there will be 10,000 scores
The scores will vary – there will be low scores and high scores and scores in between
And in the decision space, there will be record-pairs that should be linked and record pairs that should not be linked
Scores for each group will vary, each will have both low and high scores
The scores should be normally distributed
	and
Scores for record-pairs that should be linked are generally higher, or larger, than scores for record-pairs that should not be linked
The chart on the right tries to show these points
Both the linked and non-linked record-pairs have normal distributions
There are many more non-linked record-pairs than linked record-pairs

## More Terminology (continued)

***Decision Groups*** – the division of the decision space into groups based on scores for the purpose of deciding which records should be linked. Record-pairs can be classified as links, non-links, and uncertain pairs.
***Uncertain pairs***– record-pairs for which a link or non-link determination cannot be made.

**Notes:**
More terminology...

## More Record-Pairs and Scores

**Notes:**
The problem is that prior to the actual linking, it is not known which record-pairs should be linked and which should not
There is only one group of record-pairs, combining record-pairs that should be linked and record-pairs that should not be linked
Overall, these scores will have a bimodal distribution
But the scores for both groups vary
Low scores tend to be non-links
High scores tend to be links
Scores in the middle are uncertain – these are usually reviewed by hand
We set thresholds to divide the decision space into
Non-links
Uncertains
Links
The goal is to set the thresholds so that
Links do not appear with non-links
Non-links do not appear with links
The number of uncertain pairs is as small as possible
In the next presentation, Record Linking 102, we’ll talk about how we approached these goals when building the IDB

## Conclusion/Discussion

**Notes:**
The next presentation, “Record Linking 102,” demonstrates how the IDB record liking programs work