Lehrplan Lektion 54 von 156 · Miss dich ehrlich.
Miss dich ehrlich.

k-Anonymität

Warum das wichtig istOrganisationen teilen oft Daten nach dem "Entfernen von Namen" und nennen sie anonym. Du wirst auf synthetischen Daten sehen, wie schnell drei gewöhnliche Fakten die Namen wieder herstellen. So ist eine echte Re-Identifizierung passiert, und deshalb gibt es die Verteidigung in Lektion 56.

Der Gossip-Test

Jemand sagt: "Eine Frau in unserer Straße, geboren am 3. März 1981, hat gerade eine Diagnose erhalten." Kein Name wurde genannt. Aber in einer Straße, wie viele Frauen teilen genau diesen Geburtstag? Wahrscheinlich eine. Die Details waren der Name.

Quasi-identifier: eine Tatsache, die kein Name ist, aber in Kombination mit einigen anderen auf eine Person hinweist. Postleitzahl, vollständiges Geburtsdatum und Geschlecht sind die klassischen drei.

Re-identification: Namen wieder auf Daten setzen, die ohne Namen veröffentlicht wurden, meist durch Zusammenführung mit einer anderen Liste, die Namen hat.

Eine berühmte Studie von Latanya Sweeney im Jahr 2000 schätzte, dass etwa 87% der Menschen in den Vereinigten Staaten allein durch Postleitzahl, Geburtsdatum und Geschlecht identifiziert werden konnten. Eine spätere Studie mit neueren Zensusdaten (Golle, 2006) lag näher bei 63%: niedriger, aber immer noch die meisten Menschen, was der Punkt ist. Wir werden den gleichen Effekt bei erfundenen Daten sehen.

Die Übungsdaten

synthetic_people(2000) erstellt eine erfundene Gesundheitstabelle: id, name, zip, birth_date, gender, diagnosis. Niemand darin ist echt. Wir anonymisieren sie auf die naive Weise, indem wir den Namen löschen. synthetic_public_roll(people) erstellt eine erfundene öffentliche Liste, wie ein Vereinsregister, mit Namen, Postleitzahl, Geburtsdatum und Geschlecht, aber ohne Diagnose.

Das Risiko messen: k

k-anonymity: eine Tabelle ist k-anonym, wenn jede Kombination von quasi-identifier Werten von mindestens k Zeilen geteilt wird. k = 1 bedeutet, dass mindestens eine Person allein ist und gefunden werden kann.

Um k zu finden: Gruppiere Zeilen nach ihrem Quasi-Identifier-Tupel, zähle jede Gruppe und nimm den kleinsten Zähler. Mit ["gender"] allein ist k groß. Mit zip, Geburtsdatum und Geschlecht zusammen sinkt k auf 1.

Der join

Für jede Person auf der öffentlichen Liste erstelle ihren Schlüssel (zip, birth_date, gender) und suche danach in der veröffentlichten Tabelle. Sei streng: Zähle eine Übereinstimmung nur, wenn der Schlüssel genau einmal in der Veröffentlichung und genau einmal auf der Liste erscheint. Dann bist du sicher. Wenn zwei Datensätze denselben Schlüssel teilen, kannst du nicht sagen, welcher welcher ist; wenn zwei Personen auf der Liste ihn teilen, kannst du nicht sagen, wer wer ist.

reidentify(released, roll)
# {17: 'Mei Patel', 203: 'Omar Novak', ...}   record id -> name

Sobald Record 17 einen Namen hat, hat seine Diagnose auch einen. Das ist der ganze Angriff: zwei harmlos aussehende Listen, ein Join.

Ein häufiges Missverständnis

"Das Entfernen von Namen, E-Mails und Telefonnummern macht Daten anonym." Es entfernt die offensichtlichen Identifikatoren, aber die verbleibenden Spalten können Personen immer noch identifizieren. Ob Daten anonym sind, hängt davon ab, was sonst noch da ist, um sie zu verknüpfen, weshalb Lektion 56 die Daten selbst ändert.

Probier es aus Wenn du bestehst, ändere die fraction der roll von 0.6 auf 0.2 und führe es erneut aus. Die Anzahl der Übereinstimmungen sinkt, aber der Anteil der roll Personen, die du re-identifizierst, ändert sich kaum. Jede Person wird durch ihre eigenen Details enttarnt, nicht durch die Größe der list.

In anderen Sprachen

JavaScript:

function reidentify(released, roll, cols) {
  const key = r => JSON.stringify(cols.map(c => r[c]));
  const count = list => list.reduce((m, r) => m.set(key(r), (m.get(key(r)) || 0) + 1), new Map());
  const a = count(released), b = count(roll);
  const byKey = new Map(released.map(r => [key(r), r]));
  const found = {};
  for (const p of roll) {
    if (a.get(key(p)) === 1 && b.get(key(p)) === 1) found[byKey.get(key(p)).id] = p.name;
  }
  return found;
}

SQL-artiges Denken in C# (LINQ):

var matches =
    from r in released
    join p in roll on new { r.Zip, r.BirthDate, r.Gender }
                   equals new { p.Zip, p.BirthDate, p.Gender }
    select new { r.Id, p.Name };
// then keep only keys that occur once on each side

Zusammenfassung

  • Quasi-Identifikatoren (Postleitzahl, Geburtsdatum, Geschlecht) können Einzelpersonen ohne einen Namen identifizieren.
  • k ist die Größe der kleinsten Gruppe, die die gleichen Quasi-Identifikatoren teilt; k = 1 bedeutet, dass jemand exponiert ist.
  • Das Zusammenführen einer anonymen Tabelle mit einer öffentlichen Liste mit Namen identifiziert Personen erneut.
  • Namen zu entfernen ist keine Anonymisierung. Nur synthetische Daten hier; die Verteidigung kommt als Nächstes.
Du bist dran

Schreibe quasi_key(row, columns) (Tupel der Werte), smallest_group(rows, columns) (die Größe der kleinsten Gruppe von Zeilen, die einen Schlüssel teilen: das ist k) und reidentify(released, roll, columns=QUASI) und gib ein Dictionary von freigegebenem Datensatz id zu Roll name für jede Roll Person zurück, deren Schlüssel genau einmal in released und genau einmal in roll erscheint.

Ein Problem in dieser Lektion entdeckt? Melde es · Frage zu dieser Lektion

Diese Übung öffnet bald

Beende die vorherige Lektion, damit diese freigeschaltet wird. Der ganze Kurs ist kostenlos, kein Konto erforderlich, und du kannst diese Lektion jetzt direkt lesen.