Protecting privacy with k-anonymity

k-anonymity is a check that nobody in a shared table can be picked out by a few ordinary facts. Removing names does not make a table private, because an age band, an area and a rare course can together point to one person.

A school shares its place applications for research. In this lesson you find the groups too small to share safely, and you widen the table until they are not.

An identifier names someone directly. A quasi-identifier is an ordinary fact, such as an age band or an area. It names nobody alone, but it can single someone out when combined.

Rows that share the same quasi-identifier values form a group. Suppose you know a neighbour is aged 25 to 34 and lives in area P2. If only one row has those facts, you have found their row.

docker exec jupyter python3 -c 'from collections import Counter;r=[("18-24","P1")]*5+[("18-24","P2")]*4+[("25-34","P1")]*6+[("25-34","P2")]*1+[("35-44","P1")]*2+[("35-44","P2")]*3;print(min(Counter(r).values()))'

A table is k-anonymous when every group has at least k rows. Find k by counting the rows in each group and taking the smallest.

In the table above the smallest group is 1, so k is 1: the table gives no cover at all. To aim for k of 3, list every group with fewer than 3 rows. Those are the ones to fix.

# Each row: an age band and an area code.
rows = [["18-24", "P1"]] * 5 + [["18-24", "P2"]] * 4 + [["25-34", "P1"]] * 6
rows = rows + [["25-34", "P2"]] + [["35-44", "P1"]] * 2 + [["35-44", "P2"]] * 3
sizes = {}
for row in rows:
    key = row[0] + " " + row[1]
    if key in sizes:
        sizes[key] = sizes[key] + 1
    else:
        sizes[key] = 1
for key in sizes:
    if sizes[key] < 3:
        print("Too small:", key, sizes[key])
# Change 3 to 6 and run again. Which groups are too small now?

To raise k you have two tools. Generalise means replacing a value with a wider one, such as an age with a ten-year band, or two areas with one. Suppress means removing a row or a value.

Both cost something: less detail for the people who use the data. The table shows what each does to the invented applications.

docker exec jupyter python3 -c 'from collections import Counter;r=[("18-24","P1")]*5+[("18-24","P2")]*4+[("25-34","P1")]*6+[("25-34","P2")]*1+[("35-44","P1")]*2+[("35-44","P2")]*3;print(min(Counter(x[0] for x in r).values()))'

Open hires.csv and group the rows by month and weather. Count the rows in each group and find the smallest.

If each row were one person, would sharing this table keep them private? Write a sentence on which groups you would join first, and what you would lose by doing it.