# Presentation: 673180

## “Record Linking 102”

- Adapting and Implementing the IDB Client Linking Programs
*SAMHSA Integrated Database Project*

**Notes:**
Welcome to the “Record Linking 102” and thank you for coming
This workshop is a product of SAMHSA’s Integrated Database Project
This presentation builds upon the concepts laid out in “Record Linking 101”
It discusses how probabilistic techniques were implemented in the IDB programs
Finally, it describes how to obtain and implement the IDB programs to your specific needs

## 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

- Comparing IDB linking with traditional match-merging
- IDB implementation of probabilistic linking
- Obtaining the IDB programs
- Adapting IDB programs

**Notes:**
While “Record Linking 101” explored the basics of record linking, this presentation discusses the ways IDB programs were set up, and how you can adapt them to your own needs
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 

Here is a quick overview of today’s topics
We will start with a brief discussion of some results we achieved with the IDB linking
And then describe how we implemented probabilistic linking with the IDB programs, and how it all fits together
Finally, we will show you how to obtain the programs and adapt them to your needs

## 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)

## IDB Probabilistic Record Linking

- Linking
- Concatenating Data
- Scaling Factors
- Blocking, Joining, and Comparing
- Initial Links – Deterministic
- Probabilistic Iterations
- Manual review
- Mapping of IDs

**Notes:**
In “Record Linking 101,” we talked about all the pieces, all the tools we’ve used to do probabilistic linking
Along the way, we’ve provided a little insight in how to apply the tools
Now  we’ve come to the time when we show you how to put it all together

These are the basic steps be went through for the IDB
From concatenating all the data
Through mapping the IDs
We’ll talk about each of these in turn
I’d like to touch on each of these, and how the linking tools and concepts we just covered were applied

## Duplicated Client Records

- Accurate linking assumes at least one source of unduplicated data
- Duplication creates ambiguous results

| File 1 |  | File 2 |
| --- | --- | --- |
| John Smith |  | John Smith |
| Jonathan Smith |  | J Smith |
| ... |  | ... |

- ?

**Notes:**
But before we get into probabilistic record linking, I have a tangent for us
In general, we think of linking records across files
But what about linking records within a file?
What if a file contains duplicate records?

If there are duplicate records within a file you will have difficulties, if not actual problems
In the example above, there are duplicate John Smith records on two files
This leaves open the question of which records to link

For example, how do we fix things if “John Smith” and “Jonathan Smith” from File 1 are the same person?
The typical approach is to unduplicate one of the files

## Duplicated Client Records

- Accurate linking assumes at least one source of unduplicated data
- Duplication creates ambiguous results

| File 1 |  | File 2 |
| --- | --- | --- |
| John Smith |  | John Smith |
| Jonathan Smith |  | J Smith |
| ... |  | ... |

- ?

**Notes:**
But before we get into probabilistic record linking, I have a tangent for us
In general, we think of linking records across files
But what about linking records within a file?
What if a file contains duplicate records?

If there are duplicate records within a file you will have difficulties, if not actual problems
In the example above, there are duplicate John Smith records on two files
This leaves open the question of which records to link

For example, how do we fix things if “John Smith” and “Jonathan Smith” from File 1 are the same person?
The typical approach is to unduplicate one of the files

## Linking Data with Duplicate Records

- “Typical” approach
- Unduplicate first file
- Link second file to the unduplicated records from the first file
- Unduplicate any records from the second file not linked to the first file
- Unduplicating is similar to Linking
- Same procedures and evaluation criteria
- Unduplicating a file = Linking a file to itself

**Notes:**
That’s the typical approach
Then it doesn’t matter how many duplicates are found on the second file
Unless there are duplicates on the second file that don’t link to the first file
Really, the typical approach is three steps:
Unduplicate
Link
and then Unduplicate again

I’m not going to talk much about unduplicating because it is essentially the same as linking
It uses the same tools and concepts
Basically, unduplicating is self-linking a file

The process we set up with the IDB combines the upduplicating and linking into one step, instead of the three steps in the typical approach
We have a small example to show how this works

## Unduplicating – Cartesian Product

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

**Notes:**
In the example, there are two files: 1 and 2
Each file has three records
File 1 has the records L, M, and N
File 2 has the records X, Y, and Z

The process we use concatenates the two files and then does a self-join, or Cartesian join
This is a simple example, there is no blocking involved
All the possible record-pairs are created (that’s why the files only have three records each)
So the six records of the two files create a Cartesian table with 36 record-pairs
So there are 36 comparisons to make
Every possible combination is represented

That is actually a little bit overkill
Let’s take a look at the table and divide it into three sections

## Unduplicating – Cartesian Product

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

**Notes:**
First, there is the “identity diagonal” (in yellow) L-L, M-M, down through Z-Z, running diagonally from the upper left to the lower right
These are the record pairs joining records with themselves

We don’t need to join records with themselves, this part of the table is not necessary

## Unduplicating – Cartesian Product

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

**Notes:**
Second, there is the lower left triangle (in pink)
And the upper right triangle (in white)

These triangles are the mirror images of each other
L-M is the same record-pair as M-L
L-Z is the same record pair as Z-L

We don’t need both the upper and lower triangles – we only need one of them

## Unduplicating – Decision Space

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

**Notes:**
So the full Cartesian product is overkill because the resulting decision space is larger than what we need
The record-pairs we do need to link and unduplicate the files – is just the upper-right triangle of the Cartesian table – by the way, the lower-left triangle would work just as well
Instead of the 36 record-pairs from the full Cartesian join, we now have 15 record-pairs, or 15 comparisons to make

Remember we said that the traditional approach is to
Unduplicate File 1
Link the unduplicated File 1 with File 2
Unduplicate anything from File 2 that did not link with File 1
The IDB method combines these steps by concatenating the two files and self-joining that concatenated file
Once we get rid of the superfluous record pairs (the identity diagonal and the lower triangle), the result is equivalent to the traditional method
There are the three record-pairs we would get while unduplicating File 1
L-M, L-N, and M-N
There are the three record-pairs we would get while unduplicating File 2
X-Y, X-Z, and Y-Z
and finally, there are the nine record-pairs we would get from linking files 1 and 2
The yellow text: L-X through N-Z

So while technically, we need to unduplicate files to link them, the process we set up combines these steps
We refer to the combined linking and unduplicating process as linking

## Concatenating Data

- Concatenate all data and unduplicate/link
- Combines steps of unduplicating data and linking files
- Reduces the number of processing steps
- Less set-up time
- Saves review time
- Works with any number of data sources

**Notes:**
With that little explanation out of the way, lets get back to IDB probabilistic linking

In the process we developed, the first step is to concatenating data files
The previous example showed a bit of how, and why, we concatenate files

An obvious benefit from combining unduplicating and linking steps is that we save time
Another benefit is that we can link more than two files in one step

## Scaling Factors

- Recognizes that agreements on uncommon values are more important than agreements on common values
- Associated with specific values of a variable
- One scaling factor for the Last Name “Whalen”
- Separate scaling factor for “Smith”
- Inversely related to a values relative frequency

**Notes:**
The next issue is scaling, specifically the scaling of weights

Weights reflect the overall, or average, importance of a variable’s agreement or disagreement in determining links and non-links
For a variable such as Gender or SSN there isn’t much more that is needed
The distribution of values for these variables is pretty uniform
1⁄2 of all records should be either male or female – at least in the data we used
There should be 1 SSN for each person and each person should have only 1 SSN
So overall weights makes sense for these variables
But other variables have values that are both common and uncommon values
Births are cyclical – the baby-boom years were followed by years with relatively fewer births
Some names are common and some are uncommon – it is helpful to give more weight to agreements on uncommon names
So we make adjustments to certain weights to account for the relative frequency of a variable’s value
Increasing a weight if a value is relatively uncommon
or Decreasing a weight if a value is relatively common

## Scaled Variables

- First Name (NYSIIS phonetic)
- Middle Initial
- Last Name (NYSIIS phonetic)
- Birth Year
- Race
- ZIP Code

**Notes:**
These are the IDB variables where we scaled the weights

We didn’t always use exact values for all these variables
For first and last name, we used the New York Identification Information System phonetic
We also used year of birth rather than the exact date of birth

I mentioned that the scaling is based on relative frequencies for specific values
It is based on the relative frequencies in the concatenated data
So it is specific and unique to the data being linked
In other words, it will vary from source to source and from state to state
The scaling factors we used in Washington differed from the factors we used in Delaware and Oklahoma

## Blocking and Joining

- Creates the decision space for linking
- Subset of Cartesian product of the concatenated data
- “Upper” triangle
- Some evidence for linking the joined pair

**Notes:**
Concatenating data and calculating scaling factors were preliminary step
If you use cooking as an analogy, these steps are the chopping and measuring and setting things up before mixing the ingredients and working at the stove or oven
In case you’re worried, this is the last bad metaphor

The next step is blocking and joining the records – creating the record-pairs that will be compared
This is the step that puts records together and started the process

Here is where we create the decision space
The upper triangle we just spoke of earlier – this is the joining
But only the record-pairs in the upper triangle that have some evidence for linking the records – this is blocking

We only want record-pairs where there is “some” evidence – not overwhelming evidence – that there might be a match
The evidence comes from the blocking done on the data
It is important to remember that even with blocking, the vast majority of the record-pairs are not linked

## Blocking

- SSN agreement
- DOB agreement plus agreement on NYSIIS phonetic of last name
- DOB and gender agreement plus agreement on NYSIIS phonetic of first name
- Gender agreement plus agreement on NYSIIS phonetic of first and last names

**Notes:**
Here are the blocking factors we used with data from one of the IDB states
This is similar to what we used in the other two states

Any record pairs where the SSNs agreed
Record-pairs with different combinations of agreements on birth date or name information

These steps create our decision space

## Comparisons

- On identifying variables
- Made once – at start of the process
- Time consuming / resource intensive
- Results saved for later iterations
- Mixture of dichotomous and continuous comparisons

**Notes:**
We have a decision space that has joined records where there is some evidence of linking
The next step is to compare the two halves of the record-pair
We process each record pair – this can take quite a while
Step-by-step, we go through each of the comparison variables and compare the left and right values
There are different types of comparisons, depending on the variable in question
Some are simple dichotomous comparisons – yes or no
Others are continuous comparisons – which can indicate partial agreements
Most of the comparisons are resource intensive, so we do the comparisons once, at the start of the process
and then use the results multiple times, for each iteration

Here are the comparisons we made

## Comparisons of Names and IDs

- Continuous comparisons
- SSN – approximate string matching
- Medicaid ID – approximate string matching
- First Name – approximate string matching
- Last Name – approximate string matching
- Dichotomous comparisons
- Middle Initial

**Notes:**
Here are the comparisons we made
First the names and IDs
Continuous comparisons using approximate string matching for most
Simple comparison – or dichotomous comparison – for middle initial

## Comparisons of Demographic Data

- Date of Birth – continuous comparison
- If two of the three components agreed(Year, Month, Day)
- Based on the days difference
- Race – dichotomous comparison
- Gender –  dichotomous comparison
- ZIP Code – continuous comparison
- Based on the distance between centroids of the ZIP Codes

**Notes:**
Besides names and IDs, the other comparison variables were demographic information
We did continuous comparisons for the DOB and ZIP Code comparisons
And dichotomous comparisons for the Race and Gender comparisons

For DOB the comparison was made only if there was some agreement in the year, month, or day portions
The numerator was the difference in days between the two dates
The denominator was the number of days from the DOB to the end of the data year
The denominator is larger for older people
Smaller for younger people
This was blatant age-bias since the idea was to penalize for mistakes, but penalize younger people more than older people

The ZIP code measure was based the distance between ZIP Code centroids
The centroid information (longitude and latitude) was obtained from the U.S. Census Bureau
ZIP Code was a proxy for address – which was not present on the data available to us

## Initial Links – Deterministic

- First link / non-link determination
- Used to develop the first set of probabilistic weights and thresholds

**Notes:**
Now that the comparisons have been made, we wanted to calculate weights and find the links
But before we calculate weights we need some idea of which record-pairs are, and are not, links

To do that, we start with a simple deterministic link

## IDB Deterministic Criteria

- SSN agreement, Medicaid ID agreement, DOB agreement, and Gender agreement
- SSN agreement, DOB agreement, Gender agreement and one of the following:
- At least 80% agreement for First Name
- At least 90% agreement for Last Name
- Agreement on Middle Initial
- Medicaid ID agreement, DOB agreement, Gender agreement and one of the following:
- At least 80% agreement for First Name
- At least 90% agreement for Last Name
- Agreement on Middle Initial

**Notes:**
These next two slides show the deterministic criteria we used
There are six in all
Here are the first three

To over-simplify, the deterministic criteria pointed toward a match if
There is agreement on an ID or very strong name agreement and at least two other supporting agreements
We didn’t look at disagreements – that’s a modification you might consider

## More IDB Deterministic Criteria

- At least 80% agreement for first name, At least 90% agreement for last name, DOB agreement, gender agreement and one of the following:
- ZIP Code agreement
- Race agreement
- At least 80% agreement for first name, at least 90% agreement for last name, DOB agreement, and at least 90% agreement for SSN or Medicaid ID
- At least 80% agreement for first name, at least 90% agreement for last name, DOB agreement, and agreement on middle initial

**Notes:**
Here are the second three deterministic criteria

## Probabilistic Iterations

- Classify record-pairs as links or non-links
- First iteration – deterministic criteria
- Following iterations – probabilistic scores and thresholds
- Calculate new weights
- Agreement and disagreement weights
- Compute scores
- Determine thresholds for classifying links, non-links, and uncertain record-pairs

**Notes:**
So the first iteration is a deterministic link
The next step is to calculate weights
Then compute scores for each record-pair
Scores for the links and non-links (from the deterministic linking)
The scores should have a normal distribution
Recall the bimodal distribution
We use these distributions to calculate the upper and lower thresholds

Now we are ready to reclassify the record-pairs – this is the start of a new iteration
Scores above the upper threshold have little chance of being a non-linked record-pair – by default these are definite links
Scores below the lower threshold have little chance of being a linked record-pair – be default these are definite non-links
Scores between the upper and lower thresholds are uncertain record-pairs
For our project, we were very conservative in declaring links
Record-pairs were classified as links only if there was very strong evidence
You may want lass stringent criteria for your projects

We will do a manual review of the uncertains after the last iteration
Until the last iteration, we’ve used the deterministic criteria to classify the uncertain record-pairs and links or non-links
New weights and scores are calculated

You can do as many iterations as you like, but we stopped at one or two

## Manual review

- Review of uncertain record-pairs
- Print from the final iteration
- Uncertain record-pairs
- Link record-pairs that might be twins

**Notes:**
After the last iteration comes the manual review – the fun part
This is the review of 
Uncertain record-pairs
Record-pairs that would be definite links except that there is some suggestion that the records could be twins
If the files contain mostly good information this will be relatively small
If your data has lots of missing or questionable values then this will be relatively large

## Mapping of IDs

- Gathers all record-pairs link
- Automatic links from the iterations
- Links from the manual review
- Assigns synthetic ID for IDB
- Each new ID is associated with one or more IDs from the source data

**Notes:**
Once all the manual review is complete, the links can be transformed into mappings
For our project, we didn’t want any information that could directly identify clients
So we assigned a synthetic ID for our database

## Mapping Links for Data Integration

**Notes:**
The mapping is the stage that makes all the links usable

This is also the stage at which all the links are consolidated.
Remember that the files might contain duplicate records – and probably do contain duplicate records
The resulting links will be between records within a file and also for records across files
The might be a string of links, such as
Records A and B
Records A and C
and Records D and B – but not a link between A and D
The mapping program groups all these associated links so that the result are mappings between records A, B, C, and D

## Conclusion/Discussion

**Notes:**
Supporting materials available to help you with probabilistic linking are available on the CD with this presentation.

Materials include:
The report Linking Client Records from Substance Abuse, Mental Health, and Medicaid State Agencies
A data flow diagram of the linking process
A listing of the programs used for IDB probabilistic linking
A Zip file containing the IDB linking programs