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:

• Vergleiche von datenschutzbewahrenden Zeichenfolgen basierend auf der Levenshtein-Entfernung
• Ein empirischer Vergleich der Ansätze für die ungefähre Übereinstimmung von Zeichenfolgen bei der Verknüpfung privater Datensätze

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.

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:

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:

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.

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 .

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).

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

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.