Implementing k-Anonymity for Clinical Datasets

k-Anonymity is the workhorse re-identification control for tabular clinical extracts: a dataset satisfies k-anonymity when every combination of quasi-identifier values — the demographic and temporal fields that are individually non-identifying but jointly narrowing, like birth date, ZIP, and sex — is shared by at least k records, so no single patient can be isolated below a crowd of k. This page is the runnable companion to the clinical data anonymization techniques guide: where that guide surveys the control families, here we build a concrete pandas implementation that measures the minimum equivalence-class size, generalizes and suppresses until the whole frame reaches k, and reports the utility cost so the result can defend an Expert Determination “very small risk” finding.

An equivalence class is the set of rows sharing identical quasi-identifier values after generalization. k-anonymity holds if and only if the smallest equivalence class has at least k records. Anything smaller is a re-identification vector: an adversary with the same quasi-identifiers from an external source (a voter roll, an obituary, an employer record) can link a unique or near-unique row back to a named individual.

Quasi-identifier generalization hierarchies (quick reference)

Generalization is the lever that grows equivalence classes: you replace a precise value with a coarser one so more rows collide into the same class. Each quasi-identifier needs a predefined hierarchy — an ordered ladder from most specific to least — so the algorithm can climb it deterministically. Suppression (dropping a row entirely) is the fallback for outliers that never join a class of size k. Keep this table next to your de-identification config; it is the contract between the risk analyst and the pipeline.

The Safe Harbor method fixes these choices for you (ZIP truncated to 3 digits, all dates but year removed, ages 90+ aggregated) — see Safe Harbor vs Expert Determination for when each pathway applies. k-anonymity is the quantitative tool behind Expert Determination: instead of a fixed recipe you generalize only as far as the data demands to hit a chosen k, preserving more analytic utility.

Implementation pattern

The algorithm is greedy and deterministic: group by the current quasi-identifier levels, find the minimum class size, and if it is below k, climb the generalization hierarchy of the highest-cardinality quasi-identifier (the one splitting the data into the most classes, so collapsing it yields the largest merges). Repeat until either the whole frame satisfies k or every hierarchy is exhausted — at which point residual rows in under-sized classes are suppressed. Suppression is bounded by a budget so the run fails loudly rather than silently gutting the dataset.

First, define the quasi-identifiers and their generalization functions. Each hierarchy is a list of callables applied to the raw column; index 0 is raw, and higher indices are coarser.

"""Greedy k-anonymity for a tabular clinical extract using pandas."""
import pandas as pd

K = 5                      # every equivalence class must hold >= K records
SUPPRESSION_BUDGET = 0.05  # fail if more than 5% of rows must be dropped

def year_band(width):
    """Return a function mapping a year to its lower band edge, e.g. 1974 -> '1970-1974'."""
    def _band(y):
        if pd.isna(y):
            return "NA"
        lo = (int(y) // width) * width
        return f"{lo}-{lo + width - 1}"
    return _band

# Ordered generalization ladders: index = level, callable applied to the RAW column.
HIERARCHIES = {
    "birth_year": [
        lambda s: s,                                   # 0: exact year
        year_band(5),                                  # 1: 5-year band
        year_band(10),                                 # 2: 10-year band
        lambda s: "*",                                 # 3: suppress column
    ],
    "zip": [
        lambda s: s.astype(str).str.zfill(5),          # 0: ZIP5
        lambda s: s.astype(str).str.zfill(5).str[:3],  # 1: ZIP3
        lambda s: "*",                                 # 2: suppress column
    ],
    "sex": [
        lambda s: s,                                   # 0: as-is
        lambda s: "*",                                 # 1: suppress column
    ],
}
QUASI_IDS = list(HIERARCHIES)

Next, the core loop. apply_levels materializes the generalized quasi-identifier columns at the current levels; min_class_size is the k-anonymity measure; and the driver raises the level of the highest-cardinality quasi-identifier each round.

def apply_levels(df, levels):
    """Return a copy with each quasi-identifier generalized to its current level."""
    out = df.copy()
    for col, lvl in levels.items():
        lvl = min(lvl, len(HIERARCHIES[col]) - 1)
        out[col] = HIERARCHIES[col][lvl](df[col])
    return out

def class_sizes(df, cols):
    """Size of the equivalence class each row belongs to (grouped by quasi-identifiers)."""
    return df.groupby(cols, dropna=False)[cols[0]].transform("size")

def anonymize(df, k=K):
    """Generalize greedily, then suppress residual small classes. Returns (frame, report)."""
    levels = {c: 0 for c in QUASI_IDS}
    gen = apply_levels(df, levels)

    while class_sizes(gen, QUASI_IDS).min() < k:
        # Choose the quasi-identifier with the most distinct values (highest cardinality)
        # that still has headroom on its ladder; collapsing it merges the most classes.
        candidates = {c: gen[c].nunique() for c in QUASI_IDS
                      if levels[c] < len(HIERARCHIES[c]) - 1}
        if not candidates:
            break  # ladders exhausted; remaining under-k rows get suppressed below
        target = max(candidates, key=candidates.get)
        levels[target] += 1
        gen = apply_levels(df, levels)

    # Suppress any rows still in classes smaller than k (outliers that never merged).
    sizes = class_sizes(gen, QUASI_IDS)
    keep = sizes >= k
    suppression_rate = float((~keep).mean())
    report = {
        "levels": dict(levels),
        "min_class_size": int(sizes[keep].min()) if keep.any() else 0,
        "suppressed_rows": int((~keep).sum()),
        "suppression_rate": round(suppression_rate, 4),
        "rows_out": int(keep.sum()),
    }
    return gen[keep].reset_index(drop=True), report

Running it on a synthetic frame reports the generalization levels reached, the achieved minimum class size, and the suppression rate — the three numbers a risk analyst signs off on:

df = pd.DataFrame({
    "birth_year": [1974, 1974, 1974, 1981, 1981, 1981, 1990, 1991, 1992],
    "zip":        ["02139", "02139", "02141", "02139", "02138", "02143",
                   "10001", "94103", "60601"],
    "sex":        ["F", "F", "F", "M", "M", "M", "F", "M", "F"],
    "hba1c":      [7.1, 6.8, 8.2, 5.9, 6.1, 7.4, 9.0, 5.5, 6.7],  # sensitive attr
})
clean, report = anonymize(df, k=3)
print(report)
# {'levels': {'birth_year': 1, 'zip': 1, 'sex': 0}, 'min_class_size': 3,
#  'suppressed_rows': 3, 'suppression_rate': 0.3333, 'rows_out': 6}

Note that hba1c is a sensitive attribute, never a quasi-identifier — it is what the dataset exists to study, so it is left untouched. That distinction matters for the next section.

Validation and testing

k-Anonymity has two invariants worth asserting after every run: the minimum surviving class size must meet k, and suppression must stay under budget. Encode both as hard gates so a pathological input (too many outliers, a too-high k) fails the pipeline instead of shipping a mangled or still-risky extract.

def assert_k_anonymous(df_out, report, k=K, budget=SUPPRESSION_BUDGET):
    """Fail loudly unless the output is genuinely k-anonymous within the utility budget."""
    sizes = class_sizes(df_out, QUASI_IDS)
    assert sizes.min() >= k, f"min class {sizes.min()} < k={k}"
    assert report["suppression_rate"] <= budget, (
        f"suppression {report['suppression_rate']:.2%} exceeds {budget:.0%} budget"
    )

def test_k_anonymity_holds():
    out, rep = anonymize(df, k=3)
    sizes = class_sizes(out, QUASI_IDS)
    assert sizes.min() >= 3            # every class satisfies k
    assert rep["min_class_size"] >= 3  # reported measure agrees
    assert (out[QUASI_IDS].value_counts() >= 3).all()  # no residual small class

The independent recomputation of value_counts() in the test guards against an off-by-one in the suppression mask — you never trust the report the algorithm hands you; you re-derive the invariant from the output frame. In CI, run this over a frozen fixture representative of your real quasi-identifier cardinalities so a change to a hierarchy or to k fails the build, not the compliance review.

Gotchas and compliance constraints

• Quasi-identifier combinations drive risk, never single fields. Birth year alone is harmless; birth year + ZIP3 + sex can be unique in a small cohort. Always compute class size over the full quasi-identifier tuple, and be deliberate about which columns you designate — an overlooked field (admission date, provider ZIP, rare procedure) silently re-opens a linkage path the groupby never accounts for.
• Over-generalization destroys utility. Climbing every ladder to the top trivially satisfies any k but yields a dataset where every date is a decade and every ZIP is a region — useless for temporal or geographic analysis. The suppression budget plus a minimal-generalization greedy order is what keeps the result analytically alive; if you cannot hit k under budget without flattening a key variable, the honest answer is that the cohort is too small to release at that granularity.
• Outliers need explicit handling. Ages 90+ and rare diagnoses form singleton classes that never merge — Safe Harbor top-codes age at 90 for exactly this reason. Suppress them, top-code them, or widen their band, but decide before the run; a single 94-year-old with a rare cancer is the textbook re-identification.
• k-anonymity says nothing about the sensitive value — that is where l-diversity begins. If all k records in an equivalence class share the same hba1c band or the same diagnosis, an adversary who locates the class learns the sensitive value without isolating a row (a homogeneity attack). l-diversity is the next guarantee: require at least l well-represented distinct sensitive values within every equivalence class. It layers on top of the same class structure — add a per-class nunique() check on the sensitive column and generalize further where it fails.

Documented together — the quasi-identifier set, the k achieved, the suppression rate, and any l-diversity check — these metrics are exactly the quantitative evidence an expert cites when certifying that the re-identification risk is “very small” under the Expert Determination standard, rather than following the fixed Safe Harbor recipe. When your dataset also carries clinical timestamps that must survive as usable intervals, pair k-anonymity with date-shifting clinical timestamps for de-identification so temporal quasi-identifiers are perturbed consistently per patient rather than merely coarsened.

Related

• Clinical data anonymization techniques — parent guide surveying generalization, suppression, and perturbation controls
• Safe Harbor vs Expert Determination — when k-anonymity’s quantitative pathway beats the fixed 18-identifier recipe
• Date-shifting clinical timestamps for de-identification — perturbing temporal quasi-identifiers while preserving intervals
• HIPAA de-identification and patient matching — the broader de-identification and record-linkage program