Enforcing l-Diversity on POI Categories Within Grid Cells

Q: Should I use natural log or log base 2?

Either, consistently. Natural log with e^{H} gives the effective count directly, which is why it is used here. Base 2 gives bits, which is convenient when comparing against mix-zone entropy.

Measure the effective number of POI categories per published cell as $e^{H}$ over distinct people, and route a failing cell to attribute coarsening before you consider suppressing it. Coarsening clears most failures at a fraction of the coverage cost, and it is the remedy teams reach for last.

Core Calculation permalink

For a cell $c$ whose visits fall into categories with person-counts $n_1, \dots, n_m$ , the entropy is

H(c) = -\sum_{i} \frac{n_i}{n_c} \ln \frac{n_i}{n_c}, \qquad n_c = \sum_i n_i

and the effective category count is $L(c) = e^{H(c)}$ . The cell satisfies entropy $l$ -diversity when $L(c) \ge l$ .

Reporting $L$ rather than $H$ is the practical choice: a reviewer can compare “1.4 effective categories against a floor of 3” without translating nats. It is also directly comparable to the distinct-category count, which makes the gap between them — the skew — visible at a glance.

Worked numeric example permalink

Three cells at 500 m resolution, categories drawn from a nine-value taxonomy, $l = 3$ :

Cell	Distinct categories	Person-counts	$H$ (nats)	$L = e^{H}$	Verdict
c-41	1	clinic 34	0.00	1.00	fail
c-58	4	clinic 41, pharmacy 3, retail 2, café 2	0.53	1.70	fail
c-72	4	retail 18, café 15, gym 11, clinic 9	1.35	3.86	pass

Cell c-58 is the case that matters. Distinct l-diversity scores it 4 and passes it; entropy scores it 1.7 and fails it, correctly — 82% of its visits are to one clinic, so learning that a target is in c-58 raises the posterior on “visited a clinic” from a baseline of perhaps 8% to 82%.

Now coarsen the taxonomy: map clinic, pharmacy and dentist to health, and retail, café and gym to everyday. Cell c-58 becomes health 44, everyday 4, which is worse — coarsening helps only when it merges a dominant value with a genuinely different one. Coarsening clinic into a broader outpatient services alongside categories that co-locate with it is what actually clears the cell.

Plotting the two counts against each other is the fastest way to find out whether a release has a skew problem at all — and the cluster below the line is the work list.

Python Implementation permalink

from __future__ import annotations

import numpy as np
import pandas as pd

def enforce_l_diversity(
    visits: pd.DataFrame,
    l_min: float,
    coarse_map: dict[str, str] | None = None,
    cell_col: str = "cell_id",
    cat_col: str = "poi_category",
    person_col: str = "person_id",
) -> pd.DataFrame:
    """Score entropy l-diversity per cell and choose a remedy for each failure.

    Counts are over distinct individuals: a frequent visitor to one category
    inflates row-level diversity while the person-level mix stays homogeneous.

    Args:
        visits: one row per observed visit.
        l_min: required effective category count, e.g. 3.
        coarse_map: optional finer-to-coarser category mapping, applied only to
            cells that fail at the fine taxonomy.

    Returns:
        One row per cell with the fine and coarse effective counts and the remedy.
    """

    def effective(counts: np.ndarray) -> float:
        p = counts[counts > 0] / counts.sum()
        return float(np.exp(-(p * np.log(p)).sum()))

    fine = (visits.groupby([cell_col, cat_col])[person_col]
                  .nunique().rename("n").reset_index())

    rows = []
    for cell, grp in fine.groupby(cell_col):
        l_fine = effective(grp["n"].to_numpy(dtype=float))
        l_coarse = np.nan
        if l_fine < l_min and coarse_map:
            coarse = (grp.assign(_c=grp[cat_col].map(coarse_map).fillna(grp[cat_col]))
                         .groupby("_c")["n"].sum())
            l_coarse = effective(coarse.to_numpy(dtype=float))

        if l_fine >= l_min:
            remedy = "publish"
        elif np.isfinite(l_coarse) and l_coarse >= l_min:
            remedy = "publish_coarsened"      # cheapest fix; try before suppressing
        else:
            remedy = "merge_or_suppress"

        rows.append({
            cell_col: cell,
            "distinct_categories": int((grp["n"] > 0).sum()),
            "effective_fine": round(l_fine, 2),
            "effective_coarse": None if np.isnan(l_coarse) else round(l_coarse, 2),
            "persons": int(grp["n"].sum()),
            "remedy": remedy,
        })
    return pd.DataFrame(rows).sort_values("effective_fine").reset_index(drop=True)

Verification permalink

The parameter is a proxy; the property is how far an adversary’s belief moves. Measure that directly.

def posterior_shift(cell_counts: np.ndarray, global_counts: np.ndarray) -> dict:
    """Largest change in any category's probability caused by learning the cell."""
    p = cell_counts / cell_counts.sum()
    q = global_counts / global_counts.sum()
    delta = np.abs(p - q)
    return {
        "max_shift": float(delta.max()),
        "argmax_index": int(delta.argmax()),
        "cell_top_prob": float(p.max()),
        "baseline_top_prob": float(q[p.argmax()]),
    }

A cell whose max_shift is 0.7 has told the reader almost everything, whatever its effective count says. Gate on the shift and use $l$ as the cheap screen that decides which cells need the expensive check.

Re-run the whole pass counting rows instead of people and compare. A large divergence means the release’s apparent diversity is an artefact of visit frequency, and the person-level figures are the ones to publish.

The two middle options are usually available and usually skipped, because the failing test names a cell rather than naming a remedy. Returning the remedy from the scoring pass is what puts them in front of the operator.

Edge Cases & Adjustments permalink

Unknown or missing categories. Treat them as their own value rather than dropping them, and default them toward the sensitive tier when scoring — the reasoning in scoring POI sensitivity for location datasets.
Coarsening that merges like with like. Mapping three health categories into one health value can lower diversity rather than raise it. Design the coarse taxonomy so each coarse value spans activities that genuinely co-locate.
Cells with very few people. Entropy is unstable below about ten individuals; a cell of four with four categories scores an effective count of 4.0 and means nothing. Apply the k floor first and score diversity only on cells that already pass it.
Ordered categories. If the attribute has an order — severity, income band — entropy ignores it. Move to a t-closeness test using the Earth Mover’s Distance, as set out on the l-diversity and t-closeness topic page.
Correlated second attributes. A cell diverse in category and homogeneous in facility identifier discloses through the identifier. Score every column an adversary might treat as sensitive, not only the declared one.

Running the same pass both ways is a two-line change and the fastest way to find out whether a release's apparent diversity is real.

Choosing the Coarse Taxonomy permalink

The coarse mapping is the parameter that does most of the work, and designing it badly is the reason attribute coarsening gets a reputation for not helping.

A coarse value should span activities that genuinely co-locate. Merging clinic, pharmacy and dentist into health looks tidy and usually makes things worse, because those three cluster in the same places: a cell dominated by one of them becomes a cell dominated by health. Merging clinic into a broader appointment-based services alongside salon, legal and accountancy clears the cell, because those categories are spread across the same commercial streets and dilute each other.

A coarse value should also be one a reader can act on. A taxonomy that collapses everything into services and other protects perfectly and answers no question. The test is whether the map still supports the analysis it was built for; if it does not, merging cells is the better remedy even though it costs spatial detail.

Finally, the mapping should be versioned with the release. Two releases that use different coarse taxonomies are not comparable, and a reader who assumes they are will read a taxonomy change as a change in behaviour. Ship the mapping alongside the data, not in the pipeline configuration.

FAQ permalink

Why $e^{H}$ rather than $H$ ?

Because it has units a reviewer already understands — categories — and because it is directly comparable to the distinct count, which makes the skew visible. The threshold is identical; only the presentation changes.

Should I use natural log or log base 2?

Either, consistently. Natural log with $e^{H}$ gives the effective count directly, which is why it is used here. Base 2 gives bits, which is convenient when comparing against mix-zone entropy.

What if coarsening loses the finding the map exists for?

Then merge cells or accept the suppression, and record the choice. But check first: many maps present a fine taxonomy for display and answer a question that only needs the coarse one.

Does this replace a k check?

No. It runs after one, on cells that already clear the count floor. Diversity on a cell of three people is a statement about three people.

l-Diversity & t-Closeness for Spatial Attributes — the definitions and the closeness test
k-Anonymity Grouping for Location Traces — the count floor this runs on top of
Scoring POI Sensitivity for Location Datasets — deciding which categories are sensitive
Small-Cell Suppression & Complementary Suppression Rules — the count-disclosure counterpart

← Back to l-Diversity & t-Closeness for Spatial Attributes

Enforcing l-Diversity on POI Categories Within Grid Cells

Core Calculation # permalink

Worked numeric example # permalink

Python Implementation # permalink

Verification # permalink

Edge Cases & Adjustments # permalink

Choosing the Coarse Taxonomy # permalink

FAQ # permalink

Related # permalink