The Knowledge Discovery in Database process is detailed in the following phases:

1. Data cleaning (removal of formal and logical errors and outliers)
2. Data integration (combination of different sources)
3. Data selection (extraction of data for analysis from the database)
4. Data transformation (manipulation of data into forms suitable for data mining)
5. Data mining (application of analytical methods to synthesize significant relationships)
6. Relationship evaluation (classification of relationships in terms of utility)
7. Knowledge presentation (visualization and synthesis of useful relationships)

In this sense, it may be useful to define a key operation that is antecedent to Knowledge Discovery that statisticians often find themselves having to face: Record Linkage.
Record Linkage is an operation that allows joining multiple datasets in order to have more information. The objective is to identify records referring to the same individual, but located in different files, through common keys that do not perfectly correspond.

Input: two data sets that observe overlapping groups of units.
Problem: lack of a unique and error-free identification code
Solution: use of a set of variables capable (jointly) of identifying records
Attention: variables can have "problems" (there is no unique one)
Objective: greater number of correct matches, fewer number of incorrect matches

There are mainly 3 types of Record Linkage:

• Merge by matching
• Based on sorting files to be matched according to a common identification key
• It is very efficient
• It is sensitive to errors on the identification key (if it is not unique, better not to use it)
• It is advisable when the files to be matched belong to the same information system
• Deterministic matching
• Based on the concordance of a sufficient number of common variables: Can take into account missing values and errors in matching variables
• Allows to graduate the informative power of variables through scores:
• Same name = 2 points
• Same surname = 7 points
• Same year of birth = 3 points
• Scores can be established through statistical analysis on external data
• All choices on the comparison criterion are external to the treated data
• Probabilistic matching
• As in deterministic matching:
• Work on comparing all possible pairs;
• Use scores based on flexible criteria to establish matches
• But:
• The scores and thresholds used to choose matches depend on the problem under examination
• Disagreement levels in the data are also taken into account

The Phases of Record Linkage

Harmonization
Input file preparation (pre-processing):
1. Harmonization of unit definitions;
2. Harmonization of reference periods;
3. Population completion;
4. Harmonization of variable definitions;
5. Harmonization of classifications;
6. Adjustment of measurement errors (probabilistic only);
7. Adjustment for non-responses (probabilistic only);
8. Construction of derived variables.
Selection of Matching Variables
Selection of common identifying attributes (blocking and matching variables):
Desirable characteristics:
• 1. Universal
• 2. Permanent
• 3. Accurate
• 4. Non-sensitive
Choice of Comparison Function(s)
• Editing and parsing: Methods to handle typos or foreign name pronunciations.
• Sorting and blocking: Operations to:
  • Help computers recognize records faster.
  • Allow statistical operations on data.
Choice of Decision Model
Deterministic: Fixed rules; manual check (clerical review) for errors.
Probabilistic: Statistical model with "optimal" decision rules and error probabilities.
Decisions for Uncertain Matches
When data cannot discriminate a match, use:
1. Alternative linkage techniques.
2. Manual analysis (clerical review).
Data Quality and Analysis
Evaluate the accuracy of the result and determine if standard estimators can be applied directly.
MANUAL REVIEW RESULTS	Matched	Not Matched
Linkage Matched	TP	FP
Linkage Not Matched	TN	FN
FMR = FP / (TP + FP)
FNMR = FP / (TN + FN)
Sensitivity = TP / (TP + TN)
Specificity = FN / (FP + FN)

Python in Practice

Below we demonstrate record linkage techniques using string similarity measures on fake data.

1. String Similarity for Name Matching

from difflib import SequenceMatcher

def string_similarity(s1, s2):
    return SequenceMatcher(None, s1.lower(), s2.lower()).ratio()

# Example pairs
pairs = [
    ("John Smith", "Jon Smith"),      # typo
    ("Maria Garcia", "Maria G."),     # abbreviation
    ("Robert Johnson", "Bob Johnson"), # nickname
    ("Jennifer Williams", "Jenny Williams"),
    ("Michael Brown", "David Wilson"),  # no match
]

for a, b in pairs:
    sim = string_similarity(a, b)
    print(f"  '{a}' vs '{b}' -> {sim:.3f}")

# Output:
#   'John Smith' vs 'Jon Smith' -> 0.947
#   'Maria Garcia' vs 'Maria G.' -> 0.667
#   'Robert Johnson' vs 'Bob Johnson' -> 0.769
#   'Jennifer Williams' vs 'Jenny Williams' -> 0.875
#   'Michael Brown' vs 'David Wilson' -> 0.308

2. Multi-Field Weighted Similarity

def record_similarity(rec_a, rec_b, weights={'name': 0.4, 'dob': 0.4, 'city': 0.2}):
    name_sim = string_similarity(rec_a['name'], rec_b['name'])
    dob_sim = 1.0 if rec_a['dob'] == rec_b['dob'] else 0.0
    city_sim = string_similarity(rec_a['city'], rec_b['city'])
    return weights['name']*name_sim + weights['dob']*dob_sim + weights['city']*city_sim

# Compare all pairs
dataset_a = [{'name': 'John Smith', 'dob': '1985-03-15', 'city': 'New York'}]
dataset_b = [{'name': 'Jon Smith', 'dob': '1985-03-15', 'city': 'New York'},
             {'name': 'David Wilson', 'dob': '1995-04-18', 'city': 'Dallas'}]

for b in dataset_b:
    sim = record_similarity(dataset_a[0], b)
    match = "MATCH" if sim > 0.7 else "NO MATCH"
    print(f"  {dataset_a[0]['name']} vs {b['name']}: {sim:.3f} [{match}]")

# Output:
#   John Smith vs Jon Smith: 0.979 [MATCH]
#   John Smith vs David Wilson: 0.149 [NO MATCH]

3. Blocking Strategy

# Blocking: reduce comparison space by grouping on DOB year
def block_by_year(records):
    blocks = {}
    for i, rec in enumerate(records):
        year = rec['dob'][:4]
        blocks.setdefault(year, []).append(i)
    return blocks

dataset = [
    {'name': 'John', 'dob': '1985-03-15'},
    {'name': 'Maria', 'dob': '1990-07-22'},
    {'name': 'Jon', 'dob': '1985-04-20'},
    {'name': 'Bob', 'dob': '1978-11-30'},
]
blocks = block_by_year(dataset)
total_pairs = len(dataset) * (len(dataset)-1) // 2
blocked_pairs = sum(len(v)*(len(v)-1)//2 for v in blocks.values())
print(f"Total possible pairs: {total_pairs}")
print(f"Pairs after blocking: {blocked_pairs}")
print(f"Reduction: {(1 - blocked_pairs/total_pairs)*100:.0f}%")

# Output:
# Total possible pairs: 6
# Pairs after blocking: 1
# Reduction: 83%

Results