# Presentation: 472857

## Issues in Deterministic and Probabilistic Record Linkage 

- Scott DuVall
- Salt Lake City
- VHA MC

## information

- the age of

**information**

## information

**informatician**

- information =

- information =

## Linkage Adds Information

**Notes:**
Linkage is a good thing! 

My interest in informatics is focused on providing complete information to those who need it at the point of decision.  Regional Health Information Organizations and Health Record Banks are examples of sources that can benefit from duplicate record detection. 

Record linkage adds information in the form of ROWS or COLUMNS.
Adding COLUMNS gives us more information about each person – the linkage between the EDW and UPDB adds GENEALOGY data to MEDICAL DATA
Adding ROWS gives us information about more people – A birth certificate record ADDS a person to the UPDB

## Linkage Corrects Errors

**Notes:**
By having multiple copies of the same data collected from different sources, the existing data can be verified and errors can be identified (and hopefully corrected)

## Missing information
affects patient care1

- Missing information
- affects patient care1

- 1 Stiell et al.  Prevalence of information gaps in the emergency department
- and the effect on patient outcomes. Cmaj 2003;169(10):1023-8.

- 2 Coleman et al. Lost in transition: challenges and opportunities for improving
- the quality of transitional care. Ann Intern Med 2004;141(7):533-6.

- Transitions in care
- cause breakdown in communication2

## Resolving duplicates can cost $60 per case.1

- Resolving duplicates can cost $60 per case.1

- 1Thornton SN, Hood SK. Reducing Duplicate Patient Creation Using a Probabilistic Matching
- Algorithm in an Open-access Community Data Sharing Environment. Proc AMIA Symp 2005:1135.

## “between $0.30 and $0.40 of every dollar spent on health care is wasted on overuse, under use, misuse, duplication, system failures, unnecessary repetition, poor communications and inefficiency.”1

- “between $0.30 and $0.40 of every dollar spent on health care is wasted on overuse, under use, misuse, duplication, system failures, unnecessary repetition, poor communications and inefficiency.”1

- 1Reid PP, Compton WD, Grossman JH, Fanjiang G. Building a Better Delivery System: A New Engineering/
- Health Care Partnership. National Academies Press, 2005:99.

## Key element of health care information exchange and interoperability, estimated to be able to reduce costs $77.8 billion annually.1

- Key element of health care information exchange and interoperability, estimated to be able to reduce costs $77.8 billion annually.1

- 1Walker J, Pan E, Johnston D, Adler-Milstein J, Bates DW, Middleton B. The value of health care
- information exchange and interoperability. Health Aff (Millwood). 2005 Jan-Jun;Suppl Web Exclusives:
- W5-10-W5-18.

## Record Matching

- Many systems have record matching software.
- Errors still exist
- 50% missed in CDC Survey1
- 5% missed in 1.5 million records = 75,0002

- 1 User Manual for the CDC Deduplication Evaluation Toolkit
- 2 Snow LA, DuVall SL. Clinical Data Exchange Through A Looking Glass:
- A Gray-Box Approach To Record Linkage. NLM 2005.

## Old Technology

**Notes:**
Those were all the good reasons to get involved in the a linking project.

Now here are some of the challenges facing linkage that are found even in our institution.

The linkage model most widely used today is the “probabilistic model”.  It was introduced by Howard Newcombe in the 1950s and formalized by Ivan Fellegi and Alan Sunter in 1969.  Because their model is based on probability theory, the use constitutes probabilistic linkage. 

It’s OLD!  Newcombe wrote the seminal paper published in 1959 in Science about computerized record linkage.  

No offense, many good things came from the 50s – like my parents!

Just because it’s OLD, doesn’t mean it’s not GOOD.  While there have been many papers on rule-based linkage (called deterministic linkage), other methods have not gained popularity – Neural Nets, Bayesian Networks, Markov Chain Monte Carlo methods – none have taken over.  Most work done in record linkage in the last 20 years has been to improve the use of the probabilistic model.

## Misunderstood Technology

**Notes:**
Some researchers have gone as far as stating that “probabilistic patient identification provides a powerful tool because its linkage decision criteria are developed to emulate human judgment and skill in evaluating discrepancies—that is, the expertise of an experienced clerk.”

SOME PEOPLE THINK IT IS better than it really is!

ASSUMPTIONS OF CONDITIONAL INDEPENDENCE.
Conditional independence of the fields.  This assumption allows the transformation of the formulas into log(m/u).  It is thought that a little dependence between the variables is okay (such as name and year of birth, or name and sex).  The dependence in reality creates differences in the estimated and actual sensitivity and specificity rates at a given threshold.  Research done at Regenstrief has shown that the difference between estimated and observed sensitivity and specificity have ranged an average from less than 1% up to 3%. 

THE U PROBABILITY
The conditional probability that you observe agreement in field i given the record pair is not a match is noted as ui.  Because there are so many more non-matches than there are matches when searching for duplicate records, most make the assumption that U is random chance.  This takes into account both pairs that match and those that do not match.  

THE M PROBABILITY
The whole assumption is that there are duplicates that are EXACT COPIES, otherwise they would be trivial to find.  Since there is no way of determining which records DO match, the M probability is not “the conditional probability that you observe agreement in field i given the record pair is truly a match is noted as mi.”, but rather a guess at the reliability and discrimination of the field. 

As the assumption is that errors in M and U will wash out in the noise, often initial estimates are set casually.

## Misunderstood Technology

**Notes:**
In actuality, the Fellegi-Sunter theory defines an optimal linkage rule for pre-determined levels of false positives and false negatives. “Optimal linkage” is defined as minimizing the number of pairs of records that cannot be determined as matches or not by the algorithm.  The final score, does not tell you how strong a match is, but how strongly that match is from being undetermined.  In other words, it clusters to minimize the GREEN BUCKET, not to appropriately fill the RED or BLACK.

Model is quite loose.
Choose which fields to block on 
====================
When searching for duplicate records in a data set, each record is compared against every other record.  For large data sets with relatively few duplicates, most of the record pairs will not match.  Blocking is an initial step used in probabilistic linkage where records that match exactly on a small number of fields are grouped together.  The combination of fields that match exactly is called the blocking criteria.  Only records within the same group – or “block” – are compared with each other.  Records that do not end up in the same block are not compared and are considered non-matches.  To minimize the number of duplicate records that don’t end up in blocks, several blocking criteria are employed.  The best blocking criteria use fields thought to be most reliable and those that have the most number of values.  Despite this, most blocking is done empirically and done 40 to 60 times per linkage.
Although blocking should eliminate pairs that will not score high enough to match, it is usually done first, instead of being based on the scoring strategy.

Choose which fields to score
==================
As fields used in blocking partition the data into groups, they do not give additional discriminating information within the groups and are not used in the scoring strategy.  In addition, some fields are highly correlated and are not used in the same scoring strategy.  IHC swears by home phone number.  UPDB does not contain phone numbers and thus does not use any phone number information in the EDW.

Choose which similarity metric to use for each field
=================================
Similarity metrics are algorithms that compare field values between records and determine whether values are close enough to be considered a match. Although the field type limits the number of metrics that can be used, there are MANY to choose from.  Examples of metrics for names include phonetic compression and edit distance.  Metrics for dates include upper and lower limits of how many days, months, or years apart values can be and still match.

Choose a fuzzy comparison threshold
========================
The result of a field comparison ends up as 0 or 1.  As many metrics give a real number between 0 and 1, a threshold has to be set above which all pairs will be considered as matching.  In the software used at the UPDB for matching the instructions read as follows:
“setting the threshold at 500 for records that rarely link
600 for records that probably link
700 for records that usually link”

Determine a score cutoff for accepting matches
====================================

## Score Is Not Probability

- score

- probability

**Notes:**
Scores do not translate very well into probabilities.

This is especially true when relative frequency of values in a field is taken into account.  For example, 
James Johnson could match with another James Johnson and get a score of 20
Xavier Krazinsky could match with another Xavier Krazinsky and get a score of 45 – just because the name is less common.

## Information is not Used

**Notes:**
A lot of information is available in both the UPDB and the EDW that is not used in the matching algorithms.
Last Name Changes, Other names that have been used by the person, Address History, Family Relationships – all are not used until manual review.

Linkage weight is not kept.  When Alun and Lisa and all others use the EDW / UPDB resource, it is assumed that the links made were all correct and all at the same level of certainty.

## MPI

- Name +
- Date of Birth +
- Social Security Number

## MPI

## Deterministic Linkage

- IF r1.social_security_number = r2.social_security_number
- 			THEN match.
- 2) IF SoundexCompare(r1.last_name, r2.last_name) AND
- 	SoundexCompare(r1.first_name, r2.first_name) AND
- 	EditDistance(r1.birth_place, r2.place)<2 AND
- 	r1.birth_date = r2.birth_date AND
- 	r1.multiplicity = r2.multiplicity AND
- 	r1.birth_order = r2.birth_order
- 			THEN match.

## IF contains(0..9)

- 		THEN NUMBER
- IF contains(North, South, East, West)
- 		THEN DIRECTION
- IF contains(Street, Road, Lane, Drive, ...)
- 		THEN STREET_TYPE
- ELSE	STREET_NAME
- IF (NUMBER = NUMBER) AND (DIRECTION = DIRECTION) AND (STREET = STREET) AND (STREET_TYPE = STREET_TYPE)
- 		THEN MATCH

## Probabilistic Linkage 

- Each field given AGREEMENT and DISAGREEMENT weight
- Weight proportional to the field’s DISCRIMINATION and RELIABILITY
- Many more parameters, possibility of better matching

## Record Matching

- Understand your Data
- +
- Understand Mistakes in your Data
- Good Strategy for Linkage

**MANUAL REVIEW**

## Understanding the Data

- Compare characteristics of records in the duplicate subset with records in the full enterprise data warehouse
- Describe instances where records in the duplicate subset are not typical of the database at large
- Provide considerations for others looking at duplicate records in master patient indexes

## Slide 23

|  | 

UUHSC | 

Friedman |
| --- | --- | --- |
| Extra names and titles | 34.3% | 36.9% |
| Nicknames, spelling variations | 21.8% | 13.9% |
| One letter substitutions | 13.6% | 13.7% |
| One letter added or deleted | 7.6% | 12.9% |
| Punctuation or spaces | 1.9% | 11.8% |
| Different last names for females | 12.9% | 7.8% |
| Permuted parts of names | 3.2% | 1.4% |
| Different first names | 2.8% | 1.4% |
| One letter transposed | 1.9% | 0.8% |

| Nicknames, spelling variations | 21.8% | 13.9% |
| --- | --- | --- |

| Punctuation or spaces | 1.9% | 11.8% |
| --- | --- | --- |

**Notes:**
F&s – errors in names

## Slide 24

|  | UUHSC | Grannis |
| --- | --- | --- |
| Missing SSN | 52.4% | 35% |
|  |  |  |
| Typographical errors | 62.7% | 35.5% |
| Spouse (family) collisions | 14.8% | 47.5% |
| Unexplained collisions | 9.9% | 17% |
| Invalid SSN | 12.6% | 0% |

| Missing SSN | 52.4% | 35% |
| --- | --- | --- |

| Typographical Errors | 62.7% | 35.5% |
| --- | --- | --- |

| All Collisions | 24.7% | 64.5% |
| --- | --- | --- |

| Invalid SSN | 12.6% | 0% |
| --- | --- | --- |

**Notes:**
Grannis – errors in SSN

## Extension of the Probabilistic Model for Approximate Field Comparators

## Probabilistic Model

- Field in Record A = Field in Record B
- Agreement Weight
- Field in Record A ≠ Field in Record B
- Disagreement Weight

## M – probability that field matches in      

- 	dup pair
*U* – probability that field matches in
- 	non-dup pair

## Agreement Weight

- LOG(M/U)
- Disagreement Weight
- LOG(1-M/1-U)

## Field in Record A ≈ Field in Record B

- ?

## Approximate Comparator

- Edit Distance
- ED( Johnathan, Jonathan ) = 1

**Notes:**
To use approximate comparator, you have to use a cutoff or switch to rule based linking method.
Cutoff loses information (how close the field matches)
Rule-based loses probabilistic basis.

## Slide 31

## Slide 32

## LOG(Mδ /Uδ)

- LOG(Mδ /Uδ)

## Mδ – probability that field approximately 	matches by δ in  dup pair

*U*δ – probability that field 	approximately 	matches by δ in non-dup pair

## Dups

- Non-Dups

- Load and randomize
- training set

- Classify with estimated parameters

- Estimate Dups and Non-Dups

- Update Parameters

- Initial Parameters

## Dups

- Non-Dups

- Load and randomize
- training set

- Classify with updated parameters

- Re-estimate Dups and Non-Dups

- Update Parameters

- Updated Parameters

## Dups

- Non-Dups

- Load and randomize
- validation set

- Classify with training set parameters

- Classified Dups and Non-Dups

- Training Set Parameters

## Slide 38

## Slide 39

## Slide 40

## Slide 41

## Slide 42

## questions?

**questions?**