Wie kann ich Namen in einen vertraulichen Datensatz umwandeln, um ihn anonym zu machen, aber einige der Eigenschaften der Namen beibehalten?

42

Motivation

Ich arbeite mit Datensätzen, die personenbezogene Daten (PII) enthalten, und muss manchmal einen Teil eines Datensatzes mit Dritten auf eine Weise teilen, die PII nicht gefährdet und meinem Arbeitgeber eine Haftung auferlegt. Unser üblicher Ansatz besteht darin, Daten vollständig zurückzuhalten oder in einigen Fällen ihre Auflösung zu verringern. B. Ersetzen einer genauen Straße durch den entsprechenden Landkreis oder Zensusabschnitt.

Dies bedeutet, dass bestimmte Arten der Analyse und Verarbeitung intern durchgeführt werden müssen, auch wenn ein Dritter über Ressourcen und Fachwissen verfügt, die für die jeweilige Aufgabe besser geeignet sind. Da die Quelldaten nicht offen gelegt werden, mangelt es uns an Transparenz bei der Analyse und Verarbeitung. Infolgedessen kann die Fähigkeit Dritter, QA / QC durchzuführen, Parameter anzupassen oder Verfeinerungen vorzunehmen, sehr eingeschränkt sein.

Anonymisierung vertraulicher Daten

Eine Aufgabe besteht darin, Personen anhand ihres Namens in von Benutzern übermittelten Daten zu identifizieren und dabei Fehler und Inkonsistenzen zu berücksichtigen. Eine Privatperson kann an einer Stelle als "Dave" und an einer anderen als "David" aufgezeichnet werden. Kommerzielle Einheiten können viele verschiedene Abkürzungen haben, und es gibt immer einige Tippfehler. Ich habe Skripts basierend auf einer Reihe von Kriterien entwickelt, die bestimmen, wann zwei Datensätze mit nicht identischen Namen dieselbe Person darstellen, und ihnen eine gemeinsame ID zuweisen.

Zu diesem Zeitpunkt können wir den Datensatz anonymisieren, indem wir die Namen zurückhalten und durch diese persönliche ID-Nummer ersetzen. Dies bedeutet jedoch, dass der Empfänger fast keine Informationen über z. B. die Stärke des Spiels hat. Wir möchten möglichst viele Informationen weitergeben können, ohne Identität preiszugeben.

Was geht nicht

Zum Beispiel wäre es großartig, Zeichenfolgen verschlüsseln zu können, während der Bearbeitungsabstand beibehalten wird. Auf diese Weise können Dritte eine eigene QA / QC durchführen oder die weitere Verarbeitung selbst vornehmen, ohne jemals auf die PII zuzugreifen (oder sie möglicherweise rückentwickeln zu können). Vielleicht ordnen wir die Zeichenfolgen intern dem Bearbeitungsabstand <= 2 zu, und der Empfänger möchte die Auswirkungen einer Verschärfung dieser Toleranz auf den Bearbeitungsabstand <= 1 untersuchen.

Aber die einzige Methode, mit der ich vertraut bin, ist ROT13 (allgemeiner jede Verschiebungsverschlüsselung ), die kaum als Verschlüsselung gilt. Es ist, als würde man die Namen verkehrt herum schreiben und sagen: "Versprichst du, dass du das Papier nicht umdrehen wirst?"

Eine andere schlechte Lösung wäre, alles abzukürzen. Aus "Ellen Roberts" wird "ER" und so weiter. Dies ist eine schlechte Lösung, da in einigen Fällen die Initialen in Verbindung mit öffentlichen Daten die Identität einer Person offenbaren, in anderen Fällen ist sie zu mehrdeutig. "Benjamin Othello Ames" und "Bank of America" ​​haben die gleichen Initialen, aber ihre Namen sind ansonsten unterschiedlich. Also tut es auch nichts, was wir wollen.

Eine unelegante Alternative besteht darin, zusätzliche Felder einzufügen, um bestimmte Attribute des Namens zu verfolgen, z.

+-----+----+-------------------+-----------+--------+
| Row | ID | Name              | WordChars | Origin |
+-----+----+-------------------+-----------+--------+
| 1   | 17 | "AMELIA BEDELIA"  | (6, 7)    | Eng    |
+-----+----+-------------------+-----------+--------+
| 2   | 18 | "CHRISTOPH BAUER" | (9, 5)    | Ger    |
+-----+----+-------------------+-----------+--------+
| 3   | 18 | "C J BAUER"       | (1, 1, 5) | Ger    |
+-----+----+-------------------+-----------+--------+
| 4   | 19 | "FRANZ HELLER"    | (5, 6)    | Ger    |
+-----+----+-------------------+-----------+--------+

Ich nenne das "unelegant", weil man vorhersehen muss, welche Eigenschaften interessant sein könnten und es relativ grob ist. Wenn die Namen entfernt werden, können Sie nicht viel über die Stärke der Übereinstimmung zwischen den Zeilen 2 und 3 oder über den Abstand zwischen den Zeilen 2 und 4 (dh wie nahe sie der Übereinstimmung sind) schließen.

Fazit

Ziel ist es, die Zeichenfolgen so zu transformieren, dass möglichst viele nützliche Eigenschaften der ursprünglichen Zeichenfolge erhalten bleiben, während die ursprüngliche Zeichenfolge verdeckt wird. Die Entschlüsselung sollte unabhängig von der Größe des Datensatzes unmöglich oder praktisch unmöglich sein. Insbesondere wäre eine Methode, die den Bearbeitungsabstand zwischen beliebigen Zeichenfolgen beibehält, sehr nützlich.

Ich habe ein paar Artikel gefunden, die vielleicht relevant sind, aber ein bisschen über meinem Kopf liegen:

Luft
quelle

Antworten:

19

Eine der Referenzen, die ich im OP erwähnte, führte mich zu einer potenziellen Lösung, die ziemlich leistungsfähig zu sein scheint, beschrieben in "Verknüpfung von Datensätzen mit Bloom-Filtern unter Wahrung der Privatsphäre" ( doi: 10.1186 / 1472-6947-9-41 ):

Es wurde ein neues Protokoll für die datenschutzschonende Verknüpfung von Datensätzen mit verschlüsselten Bezeichnern entwickelt, das Fehler in Bezeichnern zulässt. Das Protokoll basiert auf Bloom-Filtern für Q-Gramm-Identifikatoren.

Der Artikel geht detailliert auf die Methode ein, die ich hier nach besten Kräften zusammenfassen werde.

Ein Bloom-Filter ist eine Reihe von Bits fester Länge, in denen die Ergebnisse einer festen Menge unabhängiger Hash-Funktionen gespeichert sind, die jeweils mit demselben Eingabewert berechnet werden. Die Ausgabe jeder Hash-Funktion sollte ein Indexwert aus den möglichen Indizes im Filter sein. Wenn Sie also eine mit 0 indizierte Serie von 10 Bits haben, sollten Hash-Funktionen Werte von 0 bis 9 zurückgeben (oder auf diese abgebildet werden).

Der Filter beginnt mit jedem Bit, das auf 0 gesetzt ist. Nachdem der Eingabewert mit jeder Funktion aus der Menge der Hash-Funktionen gehasht wurde, wird jedes Bit, das einem von einer Hash-Funktion zurückgegebenen Indexwert entspricht, auf 1 gesetzt. Wenn derselbe Index von mehr zurückgegeben wird als eine Hash-Funktion wird das Bit an diesem Index nur einmal gesetzt. Sie können den Bloom-Filter als Überlagerung der Hash-Menge mit dem festgelegten Bitbereich betrachten.

Das in dem oben verlinkten Artikel beschriebene Protokoll unterteilt Zeichenfolgen in n-Gramme, die in diesem Fall Zeichensätze sind. Als Beispiel "hello"könnte der folgende Satz von 2 Gramm ergeben:

["_h", "he", "el", "ll", "lo", "o_"]

Das Auffüllen der Vorder- und Rückseite mit Leerzeichen scheint bei der Konstruktion von n-Gramm generell optional zu sein. Die Beispiele in dem Artikel, der diese Methode vorschlägt, verwenden eine solche Polsterung.

Jedes n-Gramm kann gehasht werden, um einen Bloom-Filter zu erzeugen, und dieser Satz von Bloom-Filtern kann sich selbst überlagert werden (bitweise ODER-Verknüpfung), um den Bloom-Filter für den String zu erzeugen.

Wenn der Filter viel mehr Bits als Hash-Funktionen oder n-Gramm enthält, ist es relativ unwahrscheinlich, dass beliebige Zeichenfolgen genau denselben Filter erzeugen. Je mehr n-Gramm zwei Strings gemeinsam haben, desto mehr Bits teilen sich letztendlich ihre Filter. Sie können dann zwei beliebige Filter A, Banhand ihres Würfelkoeffizienten vergleichen:

DA , B = 2h / (a ​​+ b)

Wobei hdie Anzahl der Bits, die in beiden Filtern auf 1 gesetzt sind, adie Anzahl der Bits, die nur in Filter A auf 1 gesetzt sind , und bdie Anzahl der Bits, die nur in Filter B auf 1 gesetzt sind. der Würfelkoeffizient ist 1; je mehr sie sich unterscheiden, desto näher wird der Koeffizient sein 0.

Da die Hash-Funktionen eine unbestimmte Anzahl eindeutiger Eingaben auf eine kleine Anzahl möglicher Bitindizes abbilden, können verschiedene Eingaben denselben Filter erzeugen, sodass der Koeffizient nur eine Wahrscheinlichkeit angibt, dass die Zeichenfolgen gleich oder ähnlich sind. Die Anzahl der verschiedenen Hash-Funktionen und die Anzahl der Bits im Filter sind wichtige Parameter, um die Wahrscheinlichkeit von Fehlalarmen zu bestimmen - Eingangspaare, die viel weniger ähnlich sind als der mit dieser Methode berechnete Würfelkoeffizient.

Ich fand dieses Tutorial sehr hilfreich für das Verständnis des Bloom-Filters.

Bei der Implementierung dieser Methode besteht eine gewisse Flexibilität. In diesem Artikel aus dem Jahr 2010 (der auch am Ende der Frage verlinkt ist) finden Sie einige Hinweise darauf, wie leistungsfähig er in Bezug auf andere Methoden und mit verschiedenen Parametern ist.

Luft
quelle
Wenn Sie dies als akzeptierte Antwort markieren, ist dies die vielversprechendste Antwort für meinen speziellen Anwendungsfall.
Air
Vielen Dank für all diese Details und Hintergründe. Sind Sie auf eine Implementierung (zB in Python) dieses Ansatzes gestoßen?
Amball
@amball habe ich nicht.
Air
8

Auf halbem Weg durch das Lesen Ihrer Frage erkannte ich, dass Levenshtein Distance eine gute Lösung für Ihr Problem sein könnte. Es ist gut zu sehen, dass Sie einen Link zu einem Artikel zu diesem Thema haben. Lassen Sie mich sehen, ob ich etwas Licht in die Frage bringen kann, wie eine Levenshtein-Lösung aussehen würde.

Der Levenshtein-Abstand wird in vielen Branchen für die Auflösung von Entitäten verwendet. Was ihn nützlich macht, ist, dass er ein Maß für den Unterschied zwischen zwei Folgen ist. Im Falle eines Zeichenkettenvergleichs handelt es sich nur um Sequenzzeichen.

Dies könnte Ihr Problem lösen, indem Sie eine Zahl eingeben, die angibt, wie ähnlich der Text eines anderen Feldes ist.

Hier ist ein Beispiel für eine grundlegende Verwendung von Levenshtein mit den von Ihnen angegebenen Daten:

Bildbeschreibung hier eingeben

Dies bietet eine gute Lösung, der Abstand von 8 gibt einen Hinweis auf eine Beziehung und ist sehr PII-konform. Es ist jedoch immer noch nicht besonders nützlich. Sehen wir uns an, was passiert, wenn wir Textmagie anwenden, um nur die erste Initiale des Vornamens und den vollständigen Nachnamen zu verwenden und etwas in der Mitte abzulegen:

Bildbeschreibung hier eingeben

Wie Sie sehen können, ist der Levenshtein-Abstand von 0 ziemlich bezeichnend für eine Beziehung. Üblicherweise kombinieren Datenanbieter eine Reihe von Levenshtein-Permutationen des Vor- und Nachnamens mit 1, 2 oder allen Zeichen, um eine gewisse Dimension in Bezug auf die Beziehung von Entitäten zu erhalten, während die Anonymität in den Daten erhalten bleibt.

neone4373
quelle
1
Was mich an dem Artikel interessiert, den ich verlinkt habe, ist, dass er behauptet, eine Methode zum Durchführen dieser Art von Berechnung ohne Kenntnis beider Eingabezeichenfolgen zu zeigen . In der Zeitung kennt jeder Schauspieler eine Zeichenfolge, was für meine Zwecke nicht nützlich ist. Ich würde einen Schauspieler brauchen, um die Berechnung ohne Kenntnis einer der beiden Zeichenfolgen durchführen zu können. Eine Vorausberechnung ist nur für sehr kleine Datensätze oder sehr begrenzte Produkte möglich; Ein vollständiges Kreuzprodukt aus ganzzahligen Abständen in meinem Datensatz würde etwa 10 PB Speicherplatz beanspruchen.
Air
Aus diesem Grund habe ich die Idee einer Substitutions-Chiffre (ROT13) aufgegriffen, da sie den Abstand zwischen den Zeichenfolgen beibehält. Es ist jedoch nicht sicher, und ich vermute, dass es unmöglich ist, die Zeichenfolgen sicher zu verschlüsseln, während der Bearbeitungsabstand beibehalten wird. (Würde gerne falsch liegen!)
Air
Richtig, ich würde die Matrix nur so filtern, dass Levenshteins nur unterhalb eines bestimmten Grenzwerts enthalten sind, sodass Sie nur dort auffüllen, wo eine hohe Wahrscheinlichkeit von Überlappungen besteht. Darüber hinaus ist es sehr unwahrscheinlich, dass Sie die Anonymität Ihrer Kunden wahren, wenn Sie genügend Informationen angeben, um eine Beziehung zwischen unterschiedlichen Entitäten in Ihren Datensätzen zu bestimmen. Der Zweck der Anonymisierung der Daten besteht darin, potenzielle Probleme mit personenbezogenen Daten zu vermeiden (Standards können jederzeit verschärft werden), sodass ich persönlich das Risiko nicht eingehen würde.
Neone4373
7

Nach Möglichkeit verknüpfe ich verknüpfte Datensätze (z. B. Dave, David usw.) und ersetze sie durch eine Sequenznummer (1,2,3 usw.) oder einen gesalzenen Hash der Zeichenfolge , die zur Darstellung aller verknüpften Datensätze verwendet wird ( zB David statt Dave).

Ich gehe davon aus, dass Dritte keine Ahnung haben müssen, wie der wirkliche Name lautet, ansonsten können Sie ihn ihnen auch geben.

Bearbeiten : Sie müssen definieren und begründen, welche Art von Operationen der Dritte ausführen kann. Was ist beispielsweise falsch daran, Initialen gefolgt von einer Zahl (z. B. BOA-1, BOA-2 usw.) zu verwenden, um die Bank of America von Benjamin Othello Ames zu unterscheiden? Wenn das zu aufschlussreich ist, können Sie einige Buchstaben oder Namen wegwerfen. Beispiel: [AE] -> 1, [FJ] -> 2 usw., damit aus BOA 1OA wird, oder ["Bank", "Barry", "Bruce" usw.] -> 1, damit die Bank of America wieder wird 1OA.

Weitere Informationen finden Sie unter k-anonymity .

Emre
quelle
Schätzen Sie die k-Anonymitätsreferenz und den Bin-Vorschlag - das gibt mir einige neue Denkanstöße.
Air
6

Eine Möglichkeit (abhängig von der Größe Ihres Datasets) besteht darin, lediglich Bearbeitungsabstände (oder andere von Ihnen verwendete Ähnlichkeitsmaße) als zusätzliches Dataset anzugeben.

Z.B:

  1. Generieren Sie eine Reihe eindeutiger Namen im Dataset
  2. Berechnen Sie für jeden Namen den Bearbeitungsabstand zwischen den Namen
  3. Generieren Sie für jeden Namen eine ID oder einen irreversiblen Hash
  4. Ersetzen Sie die Namen im ursprünglichen Datensatz durch diese ID
  5. Stellen Sie eine Matrix mit Bearbeitungsabständen zwischen ID-Nummern als neuen Datensatz bereit

Es gibt jedoch noch viel zu tun, um die Daten aus diesen sogar zu entschlüsseln.

Wenn beispielsweise bekannt ist, dass "Tim" der beliebteste Name für einen Jungen ist, kann dies durch die Häufigkeitszählung von IDs, die dem bekannten Prozentsatz von Tims in der Bevölkerung entsprechen, verraten werden. Von dort aus können Sie dann nach Namen mit einem Bearbeitungsabstand von 1 suchen und daraus schließen, dass sich diese IDs möglicherweise auf "Tom" oder "Jim" beziehen (wenn sie mit anderen Informationen kombiniert werden).

Dave Challis
quelle
5

Ich bin mir nicht ganz sicher, aber vielleicht ist ortsabhängiges Hashing eine gute Lösung. Es werden keine Eingabedaten (in Ihrem Fall Namen) verarbeitet, sodass die ursprünglichen Zeichenfolgen erhalten bleiben. Auf der anderen Seite besteht die Hauptidee von LSH darin, die Wahrscheinlichkeit von Hashes für ähnliche Elemente zu maximieren. Es gibt viele verschiedene LSH-Implementierungen. Ich habe versucht, Nilsimsa-Hash zum Vergleichen von Tweet-Texten, und es hat ganz gut funktioniert. Aber ich bin nicht sicher, wie gut es bei kurzen Zeichenfolgen (Namen) funktioniert - dieses Problem muss getestet werden. Ich habe Ihre Beispiele ausprobiert und hier ist das Ergebnis (Name A, Name B, "Entfernung" - maximal 120):

1. AMELIA BEDELIA  - CHRISTOPH BAUER - 107
2. AMELIA BEDELIA  - C J BAUER       - 82
3. AMELIA BEDELIA  - FRANZ HELLER    - 91
4. CHRISTOPH BAUER - C J BAUER       - 81
5. CHRISTOPH BAUER - FRANZ HELLER    - 98
6. C J BAUER       - FRANZ HELLER    - 83

Wie Sie sehen, waren CHRISTOPH BAUER und CJ BAUER das engste Paar. Der Unterschied ist jedoch nicht signifikant. Und nur zum Beispiel - Hash-Darstellung dieser Namen:

AMELIA BEDELIA  6b208299602b5000c3005a048122a43a828020889042240005011c1880864502
CHRISTOPH BAUER 22226448000ab10102e2860b52062487ff0000928e0822ee106028016cc01237
C J BAUER       2282204100961060048050004400240006032400148000802000a80130402002
FRANZ HELLER    58002002400880080b49172044020008030002442631e004009195020ad01158
Sobach
quelle
3

Hier ist ein Ansatz, den ich nicht erwähnt habe: Teilen Sie den Prozess in zwei Schritte auf: Der erste Schritt konzentrierte sich auf das Codieren von Namen, sodass alternative Versionen desselben Namens gleich (oder fast gleich) codiert werden, und der zweite Schritt konzentrierte sich auf das Erstellen sie anonym.

Für den ersten Schritt können Sie einen der phonetischen Algorithmen (Soundex und Varianten) verwenden , die auf Vorname, Nachname und Initialen in verschiedenen Reihenfolgen angewendet werden. (Siehe auch diesen Artikel ). In diesem Schritt lösen Sie Ähnlichkeiten und Unterschiede in den Namen auf, um falsch-positive von falsch-negativen zu trennen.

Im zweiten Schritt können Sie eine beliebige Hashing- oder Kryptografiemethode auswählen, ohne sich Gedanken darüber zu machen, wie sich diese Methode auf die Namenszuordnung auswirkt. Dies gibt Ihnen die Freiheit, eine Methode zu verwenden, die die besten Eigenschaften hinsichtlich Leistung, Robustheit und Anonymität aufweist.

MrMeritology
quelle
Ich glaube nicht, dass dieser Vorschlag das Problem angeht, wie es in der Frage dargestellt wird. Wo ist die Flexibilität nach der Verschlüsselung? Wie verfeinere ich Ihre Analyse ohne Zugriff auf die Originaldaten?
Air
@AirThomas Es tut mir leid, aber ich verstehe Ihre beiden Fragen nicht. Was meinen Sie mit "Flexibilität nach der Verschlüsselung"? Ich habe in Ihrer Frage / Beschreibung so etwas nicht gesehen. Was meinen Sie mit "Verfeinern Sie Ihre Analyse ohne Zugriff auf die Originaldaten"? Ich habe nichts von "Verfeinern" gesehen.
MrMeritology
1
Ich habe versucht, das Problem im zweiten Absatz des Abschnitts Motivation zu identifizieren . Stellen Sie sich zum Beispiel vor, Sie möchten Ihren Datensatz für verschiedene Forscher freigeben, die Modellierungen durchführen möchten. Es gibt eine beliebige Anzahl von cleveren und effektiven Methoden, die angewendet werden können, und jeder Forscher arbeitet ein wenig anders. Sie können die Namen von Privatpersonen in Ihrem Datensatz nicht offenlegen. Wenn Sie diesen Teil der Analyse durchführen, bevor Sie die Daten freigeben, müssen Sie die Methode für jeden auswählen.
Air
Wenn Sie zusätzlich Hashes der Namen bereitstellen, besteht der Vorteil darin, dass Dritte die genaue Identität erkennen können, jedoch nicht mehr. Die Frage ist also, wie Sie weitere Informationen zu den Daten bereitstellen können, die Sie nicht freigeben können. Gibt es zum Beispiel eine Methode, die die Bearbeitungsentfernung zwischen beliebigen Eingaben in der Hashing- / Verschlüsselungsausgabe beibehält? Ich habe mindestens eine Methode gefunden, die diese Funktionalität mindestens annähert (weitere Informationen finden Sie in meiner eigenen Antwort). Ich hoffe, das macht die Dinge klarer.
Air