Record Linkage and Data Matching

Record linkage (also called entity resolution, deduplication, or data matching) identifies records across or within databases that refer to the same real-world entity. When unique identifiers are absent, statistical and probabilistic methods are needed to determine whether two records represent the same entity. This lesson develops the mathematical foundations of record linkage from deterministic rules through the Felleg-Sunter probabilistic framework.

Deterministic vs Probabilistic Linkage

Felleg-Sunter Model

String Distance Metrics

Blocking

EM Algorithm for Linkage

Privacy-Preserving Record Linkage

Evaluation Metrics

Python Implementation

import numpy as np
import pandas as pd
from collections import Counter

np.random.seed(42)

# --- String Distance Metrics ---
def levenshtein_distance(s, t):
    """Compute Levenshtein edit distance via dynamic programming."""
    m, n = len(s), len(t)
    dp = np.zeros((m + 1, n + 1), dtype=int)
    dp[:, 0] = np.arange(m + 1)
    dp[0, :] = np.arange(n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if s[i-1] == t[j-1] else 1
            dp[i, j] = min(dp[i-1, j] + 1, dp[i, j-1] + 1, dp[i-1, j-1] + cost)
    return dp[m, n]

def jaro_winkler(s, t, p=0.1):
    """Compute Jaro-Winkler similarity."""
    if s == t: return 1.0
    len_s, len_t = len(s), len(t)
    match_distance = max(len_s, len_t) // 2 - 1
    s_matches = [False] * len_s
    t_matches = [False] * len_t
    matches = transpositions = 0

    for i in range(len_s):
        start = max(0, i - match_distance)
        end = min(i + match_distance + 1, len_t)
        for j in range(start, end):
            if t_matches[j] or s[i] != t[j]: continue
            s_matches[i] = t_matches[j] = True
            matches += 1
            break

    if matches == 0: return 0.0

    k = 0
    for i in range(len_s):
        if not s_matches[i]: continue
        while not t_matches[k]: k += 1
        if s[i] != t[k]: transpositions += 1
        k += 1

    jaro = (matches/len_s + matches/len_t + (matches - transpositions/2)/matches) / 3

    # Common prefix (max 4 chars)
    prefix = 0
    for i in range(min(4, len_s, len_t)):
        if s[i] == t[i]: prefix += 1
        else: break

    return jaro + prefix * p * (1 - jaro)

# --- Test string distances ---
pairs = [
    ("Smith", "Smyth"), ("Johnson", "Johnsen"),
    ("Washington", "Washngton"), ("Michael", "Micheal"),
    ("New York", "New Yrok"), ("Robert", "Robbert"),
]
print("=== String Distance Metrics ===")
print(f"{'Pair':<30} {'Levenshtein':<14} {'Jaro-Winkler':<14}")
print("-" * 58)
for s, t in pairs:
    lev = levenshtein_distance(s, t)
    jw = jaro_winkler(s, t)
    print(f"({s}, {t}){'':>{26-len(s)-len(t)}} {lev:<14} {jw:<14.4f}")

# --- Felleg-Sunter Model ---
def felleg_sunter_weights(match_probs, non_match_probs, agreement_vector):
    """Compute Felleg-Sunter match weight for a pair."""
    weight = 0.0
    for gamma, m_k, u_k in zip(agreement_vector, match_probs, non_match_probs):
        if gamma == 1:
            weight += np.log(m_k / u_k)
        else:
            weight += np.log((1 - m_k) / (1 - u_k))
    return weight

# Simulated parameters (estimated from field distributions)
# Fields: [first_name, last_name, DOB, city, ZIP]
m_k = np.array([0.95, 0.98, 0.90, 0.85, 0.92])  # match probs
u_k = np.array([0.01, 0.005, 0.02, 0.03, 0.05])  # non-match probs

print("\n=== Felleg-Sunter Match Weights ===")
test_pairs = [
    ("John Smith", "John Smith", [1,1,1,1,1]),
    ("John Smith", "Jon Smith", [0,1,1,1,1]),
    ("John Smith", "John Smyth", [1,0,1,1,1]),
    ("John Smith", "Jane Doe", [0,0,0,0,0]),
]
for name1, name2, gamma in test_pairs:
    w = felleg_sunter_weights(m_k, u_k, gamma)
    agreement = sum(gamma)
    print(f"({name1}, {name2}) agree on {agreement}/5 fields: W = {w:.2f} bits")

# --- EM Algorithm for Linkage ---
np.random.seed(42)
n_pairs = 5000
n_true_matches = 200

# Generate comparison vectors
gamma_true = np.random.binomial(1, m_k, size=(n_true_matches, 5))
gamma_false = np.random.binomial(1, u_k, size=(n_pairs - n_true_matches, 5))
gamma_all = np.vstack([gamma_true, gamma_false])
labels = np.concatenate([np.ones(n_true_matches), np.zeros(n_pairs - n_true_matches)])

# EM algorithm
n_pairs_total = len(gamma_all)
n_fields = gamma_all.shape[1]
pi = n_true_matches / n_pairs_total
m_em = np.random.uniform(0.7, 0.95, n_fields)
u_em = np.random.uniform(0.01, 0.1, n_fields)

for iteration in range(50):
    # E-step
    p_match = pi * np.prod(m_em ** gamma_all * (1 - m_em) ** (1 - gamma_all), axis=1)
    p_nonmatch = (1 - pi) * np.prod(u_em ** gamma_all * (1 - u_em) ** (1 - gamma_all), axis=1)
    w_post = p_match / (p_match + p_nonmatch + 1e-300)

    # M-step
    pi_new = np.mean(w_post)
    m_em_new = np.average(gamma_all, weights=w_post, axis=0)
    u_em_new = np.average(gamma_all, weights=1 - w_post, axis=0)

    if np.max(np.abs(m_em - m_em_new)) < 1e-6:
        print(f"EM converged after {iteration + 1} iterations")
        break
    pi, m_em, u_em = pi_new, m_em_new, u_em_new

print(f"\n=== EM Estimates ===")
print(f"π (match prior): {pi:.4f} (true: {n_true_matches/n_pairs_total:.4f})")
fields = ['First Name', 'Last Name', 'DOB', 'City', 'ZIP']
print(f"{'Field':<15} {'m_k (est)':<12} {'m_k (true)':<12} {'u_k (est)':<12} {'u_k (true)':<12}")
print("-" * 63)
for i, field in enumerate(fields):
    print(f"{field:<15} {m_em[i]:<12.4f} {m_k[i]:<12.4f} {u_em[i]:<12.4f} {u_k[i]:<12.4f}")

# Classification
threshold = 0.5
predicted = (w_post >= threshold).astype(int)
tp = np.sum((predicted == 1) & (labels == 1))
fp = np.sum((predicted == 1) & (labels == 0))
fn = np.sum((predicted == 0) & (labels == 1))
precision = tp / (tp + fp) if (tp + fp) > 0 else 0
recall = tp / (tp + fn) if (tp + fn) > 0 else 0
f1 = 2 * precision * recall / (precision + recall) if (precision + recall) > 0 else 0

print(f"\n=== Linkage Evaluation ===")
print(f"Precision: {precision:.4f}")
print(f"Recall: {recall:.4f}")
print(f"F1: {f1:.4f}")

Summary