Jak mogę przekształcić nazwy w poufny zestaw danych, aby uczynić go anonimowym, ale zachować niektóre cechy tych nazw?


42

Motywacja

Pracuję z zestawami danych, które zawierają dane osobowe (PII) i czasami muszę udostępniać część zbioru danych stronom trzecim w sposób, który nie naraża PII i nie naraża mojego pracodawcy na odpowiedzialność. Naszym typowym podejściem jest tutaj całkowite wstrzymanie danych lub, w niektórych przypadkach, zmniejszenie rozdzielczości; np. zastąpienie dokładnego adresu ulicy odpowiednim okręgiem lub spisem spisowym.

Oznacza to, że niektóre rodzaje analiz i przetwarzania muszą być wykonywane wewnętrznie, nawet jeśli strona trzecia ma zasoby i wiedzę bardziej dostosowane do tego zadania. Ponieważ dane źródłowe nie są ujawniane, sposób, w jaki podchodzimy do tej analizy i przetwarzania, nie jest przejrzysty. W rezultacie zdolność jakiejkolwiek strony trzeciej do przeprowadzania kontroli jakości / kontroli jakości, dostosowywania parametrów lub wprowadzania udoskonaleń może być bardzo ograniczona.

Anonimizacja poufnych danych

Jedno z zadań obejmuje identyfikację osób według ich nazw, w danych przesłanych przez użytkownika, z uwzględnieniem błędów i niespójności. Osoba prywatna może być zarejestrowana w jednym miejscu jako „Dave”, aw innym jako „David”, podmioty komercyjne mogą mieć wiele różnych skrótów i zawsze są jakieś literówki. Opracowałem skrypty oparte na wielu kryteriach, które określają, kiedy dwa rekordy o nieidentycznych nazwach reprezentują tę samą osobę i przypisują im wspólny identyfikator.

W tym momencie możemy uczynić zestaw danych anonimowym, ukrywając nazwy i zastępując je tym osobistym numerem identyfikacyjnym. Ale to oznacza, że ​​odbiorca prawie nie ma informacji o np. Sile dopasowania. Wolelibyśmy móc przekazywać jak najwięcej informacji bez ujawniania tożsamości.

Co nie działa

Na przykład byłoby wspaniale móc szyfrować ciągi przy zachowaniu odległości edycji. W ten sposób strony trzecie mogą wykonać niektóre z własnej kontroli jakości / kontroli jakości lub zdecydować się na dalsze przetwarzanie samodzielnie, bez uzyskiwania dostępu (lub możliwości potencjalnej inżynierii wstecznej) danych osobowych. Być może dopasowujemy ciągi wewnętrznie z odległością edycji <= 2, a odbiorca chce przyjrzeć się implikacjom zaostrzenia tej tolerancji na odległość edycji <= 1.

Ale jedyną znaną mi metodą, która to robi, jest ROT13 (bardziej ogólnie dowolny szyfr przesuwny ), który prawie nie liczy się jako szyfrowanie; to tak, jakby napisać imiona do góry nogami i powiedzieć: „Obiecujesz, że nie przewrócisz papieru?”

Innym złym rozwiązaniem byłoby skrócenie wszystkiego. „Ellen Roberts” zmienia się w „ER” i tak dalej. Jest to kiepskie rozwiązanie, ponieważ w niektórych przypadkach inicjały w połączeniu z danymi publicznymi ujawnią tożsamość osoby, aw innych przypadkach są zbyt niejednoznaczne; „Benjamin Othello Ames” i „Bank of America” będą miały te same inicjały, ale ich nazwy są inaczej różne. Więc nie robi żadnej z rzeczy, których chcemy.

Nieelegatywną alternatywą jest wprowadzenie dodatkowych pól w celu śledzenia niektórych atrybutów nazwy, np .:

+-----+----+-------------------+-----------+--------+
| 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    |
+-----+----+-------------------+-----------+--------+

Nazywam to „nieelegantem”, ponieważ wymaga przewidywania, które cechy mogą być interesujące i jest stosunkowo gruby. Jeśli nazwy zostaną usunięte, niewiele można rozsądnie wnioskować o sile dopasowania między rzędami 2 i 3 lub o odległości między rzędami 2 i 4 (tj. O tym, jak blisko są dopasowania).

Wniosek

Celem jest transformacja ciągów w taki sposób, aby zachować jak najwięcej użytecznych właściwości oryginalnego ciągu, jednocześnie zasłaniając oryginalny ciąg. Odszyfrowanie powinno być niemożliwe, lub tak niepraktyczne, aby było faktycznie niemożliwe, bez względu na rozmiar zestawu danych. W szczególności bardzo przydatna byłaby metoda, która zachowuje odległość edycji między dowolnymi ciągami.

Znalazłem kilka dokumentów, które mogą być istotne, ale są trochę ponad moją głową:

Odpowiedzi:


19

Jedno z odniesień, o których wspomniałem w OP, doprowadziło mnie do potencjalnego rozwiązania, które wydaje się dość potężne, opisane w „Zachowującym prywatność powiązaniu rekordów za pomocą filtrów Bloom” ( doi: 10.1186 / 1472-6947-9-41 ):

Opracowano nowy protokół służący do zachowania poufności powiązania rekordów z zaszyfrowanymi identyfikatorami, pozwalający na błędy w identyfikatorach. Protokół oparty jest na filtrach Blooma na q-gramach identyfikatorów.

Artykuł szczegółowo opisuje metodę, którą streszczę tutaj najlepiej jak potrafię.

Filtr Blooma to seria bitów o stałej długości, przechowująca wyniki ustalonego zestawu niezależnych funkcji skrótu obliczonych na tej samej wartości wejściowej. Wyjściem każdej funkcji skrótu powinna być wartość indeksu spośród możliwych indeksów w filtrze; tzn. jeśli masz serię 10 bitów z indeksowaniem 0, funkcje skrótu powinny zwracać (lub być odwzorowane na) wartości od 0 do 9.

Filtr rozpoczyna się od każdego bitu ustawionego na 0. Po haszowaniu wartości wejściowej każdej funkcji z zestawu funkcji skrótu, każdy bit odpowiadający wartości indeksu zwracanej przez dowolną funkcję skrótu jest ustawiany na 1. Jeśli ten sam indeks jest zwracany przez więcej niż jedna funkcja skrótu, bit o tym indeksie jest ustawiany tylko raz. Można uznać filtr Blooma za superpozycję zestawu skrótów na stały zakres bitów.

Protokół opisany w powyższym artykule dzieli łańcuchy na n-gram, które są w tym przypadku zestawami znaków. Na przykład "hello"może dać następujący zestaw 2 gramów:

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

Wypełnianie przodu i tyłu spacjami wydaje się być ogólnie opcjonalne przy konstruowaniu n-gramów; przykłady podane w artykule, który proponuje tę metodę, wykorzystują takie wypełnienie.

Każdy n-gram może być mieszany w celu uzyskania filtra Blooma, a ten zestaw filtrów Blooma może zostać nałożony na siebie (bitowa operacja LUB) w celu wytworzenia filtra Blooma dla łańcucha.

Jeśli filtr zawiera o wiele więcej bitów niż funkcji skrótu lub n-gramów, stosunkowo mało prawdopodobne jest, aby arbitralne łańcuchy tworzyły dokładnie ten sam filtr. Jednak im więcej n-gramów mają dwa ciągi, tym więcej bitów ich filtry będą ostatecznie dzielić. Następnie możesz porównać dowolne dwa filtry A, Bza pomocą współczynnika kości:

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

Gdzie hjest liczbą bitów, które są ustawione na 1 w obu filtrów, ato liczba bitów ustawionych na 1 w jedynym filtrem A, i bjest to liczba bitów ustawionych na 1 w jedynym filtrem B. Jeśli ciągi są dokładnie takie same, współczynnik kości wyniesie 1; im bardziej się różnią, tym bliższy będzie współczynnik 0.

Ponieważ funkcje skrótu odwzorowują nieokreśloną liczbę unikatowych danych wejściowych na niewielką liczbę możliwych indeksów bitowych, różne dane wejściowe mogą generować ten sam filtr, więc współczynnik wskazuje tylko prawdopodobieństwo, że ciągi znaków są takie same lub podobne. Liczba różnych funkcji skrótu i ​​liczba bitów w filtrze są ważnymi parametrami do określania prawdopodobieństwa fałszywych trafień - pary danych wejściowych, które są znacznie mniej podobne niż współczynnik kostki wytwarzany tą metodą.

Ten samouczek okazał się bardzo pomocny w zrozumieniu filtra Bloom.

Istnieje pewna elastyczność we wdrażaniu tej metody; zobacz także ten artykuł z 2010 r. (również link na końcu pytania), aby uzyskać pewne wskazówki na temat jego skuteczności w stosunku do innych metod i różnych parametrów.


Oznaczenie tego jako zaakceptowanej odpowiedzi, ponieważ spośród sugerowanych podejść jest to najbardziej obiecujące w moim konkretnym przypadku użycia.
Air

Dziękujemy za wszystkie te szczegóły i tło. Czy natrafiłeś na jakąkolwiek implementację tego podejścia (np. W Pythonie)?
amball

@amball Nie mam.
Air

8

W połowie przeczytania twojego pytania zdałem sobie sprawę, że Levenshtein Distance może być dobrym rozwiązaniem twojego problemu. Dobrze jest zobaczyć, że masz link do artykułu na ten temat, pozwól mi rzucić nieco światła na to, jak wyglądałoby rozwiązanie Levenshtein.

Odległość Levenshteina jest stosowana w wielu branżach do rozwiązywania bytów, dlatego przydatne jest to, że jest to miara różnicy między dwiema sekwencjami. W przypadku porównywania ciągów są to tylko ciągi znaków.

Może to pomóc w rozwiązaniu problemu, umożliwiając podanie jednej liczby określającej stopień podobieństwa tekstu w innym polu.

Oto przykład podstawowego sposobu korzystania z Levenshtein z danymi, które podałeś:

wprowadź opis zdjęcia tutaj

To zapewnia dobre rozwiązanie, odległość 8 zapewnia pewne wskazanie związku i jest bardzo zgodna z PII. Jednak nadal nie jest to bardzo przydatne, zobaczmy, co się stanie, jeśli zrobimy trochę magii tekstowej, aby wziąć tylko pierwszy inicjał imienia i pełne nazwisko, upuszczając cokolwiek na środku:

wprowadź opis zdjęcia tutaj

Jak widać, odległość Levenshteina wynosząca 0 wskazuje raczej na związek. Zwykle dostawcy danych łączą wiązkę permutacji Levenshteina imion i nazwisk z 1, 2 lub wszystkimi znakami, aby nadać pewien wymiar powiązaniom między jednostkami, zachowując jednocześnie anonimowość danych.


1
To, co mnie interesuje w dokumencie, który połączyłem, to to, że twierdzi, że pokazuje metodę wykonywania tego rodzaju obliczeń bez znajomości obu ciągów wejściowych . W artykule każdy aktor ma wiedzę na temat jednego ciągu, co nie jest przydatne do moich celów; Potrzebowałbym jednego aktora, aby móc wykonać obliczenia bez znajomości jednego z ciągów. Wcześniejsze ich obliczenie jest możliwe tylko w przypadku bardzo małych zestawów danych lub bardzo ograniczonych produktów; pełny iloczyn całkowitych odległości całkowitych w moim zestawie danych zajmie ~ 10 PB pamięci.
Air

Właśnie dlatego wpadłem na pomysł szyfru podstawienia (ROT13), ponieważ zachowuje on odległość między łańcuchami; ale nie jest bezpieczny i podejrzewam, że bezpieczne szyfrowanie ciągów przy zachowaniu odległości do edycji może być niemożliwe. (Chciałbym się mylić!)
Air

Racja, po prostu przefiltrowałbym macierz, aby uwzględnić Levenshteiny tylko poniżej pewnego poziomu odcięcia, więc wypełniasz tylko te miejsca, w których istnieje duże prawdopodobieństwo nakładania się. Ponadto, jeśli chodzi o PII, jestem zdania, że ​​jeśli podasz wystarczającą ilość informacji, aby ustalić relację między różnymi podmiotami w swoich zestawach danych, bardzo mało prawdopodobne jest zachowanie anonimowości klientów. Celem anonimizacji danych jest uniknięcie potencjalnych problemów regulacyjnych związanych z PII w tym zakresie (standardy można zawsze zaostrzyć), więc osobiście nie podejmowałbym ryzyka.
neone4373

7

Jeśli to możliwe, połączę powiązane rekordy (np. Dave, David itp.) I zastąpię je numerem sekwencyjnym (1,2,3 itd.) Lub solonym hashem ciągu, który jest używany do reprezentowania wszystkich powiązanych rekordów ( np. David zamiast Dave).

Zakładam, że osoby trzecie nie muszą mieć pojęcia, jakie jest prawdziwe imię, w przeciwnym razie równie dobrze możesz je im podać.

edycja : Musisz zdefiniować i uzasadnić, jakie operacje musi wykonywać osoba trzecia. Na przykład, co jest złego w używaniu inicjałów, po których następuje liczba (np. BOA-1, BOA-2 itd.), Aby ujednoznacznić Bank of America od Benjamina Othello Amesa? Jeśli to zbyt odkrywcze, możesz skasować niektóre litery lub nazwiska; np. [AE] -> 1, [FJ] -> 2 itd., więc BOA zmieni się w 1OA, lub [„Bank”, „Barry”, „Bruce” itp.] -> 1, więc Bank of America ponownie 1OA.

Aby uzyskać więcej informacji, zobacz anonimowość .


Doceń referencję k-anonimowości i sugestię bin - to daje mi kilka nowych rzeczy do przemyślenia.
Air

6

Jedną z opcji (w zależności od wielkości zestawu danych) jest podanie odległości edycji (lub innych miar podobieństwa, których używasz) jako dodatkowego zestawu danych.

Na przykład:

  1. Wygeneruj zestaw unikalnych nazw w zbiorze danych
  2. Dla każdej nazwy oblicz odległość edycji względem siebie
  3. Wygeneruj identyfikator lub nieodwracalny skrót dla każdej nazwy
  4. Zastąp nazwy w oryginalnym zestawie danych tym identyfikatorem
  5. Podaj macierz odległości edycji między numerami ID jako nowy zestaw danych

Chociaż można jeszcze wiele zrobić, aby nawet zdanonimizować dane z tych danych.

Na przykład, jeśli „Tim” jest najpopularniejszym imieniem dla chłopca, liczenie częstotliwości identyfikatorów, które ściśle pasują do znanego odsetka Tims w całej populacji, może to dać. Następnie możesz poszukać nazw z odległością edycji 1 i dojść do wniosku, że te identyfikatory mogą odnosić się do „Toma” lub „Jima” (w połączeniu z innymi informacjami).


5

Nie jestem do końca pewien, ale być może dobrym rozwiązaniem jest mieszanie uwzględniające lokalizację. Robi haszowanie danych wejściowych (w twoim przypadku - nazw), więc oryginalne łańcuchy zostałyby zachowane. Z drugiej strony, główną ideą LSH jest maksymalizacja prawdopodobieństwa skrótów dla podobnych elementów. Istnieje wiele różnych implementacji LSH. Próbowałem skrótu Nilsimsa do porównywania tweetów i działało to całkiem dobrze. Ale nie jestem pewien, jak dobrze będzie działać w przypadku krótkich ciągów (nazw) - ten problem wymaga przetestowania. Próbowałem twoich przykładów, a oto wynik (nazwa A, nazwa B, „odległość” - maksymalna to 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

Jak widać, CHRISTOPH BAUER i CJ BAUER okazali się najbliższą parą. Ale różnica nie jest znacząca. I na przykład - reprezentacja skrótowa tych nazw:

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

3

Oto podejście, o którym nie wspomniałem: podziel proces na dwa etapy: pierwszy krok koncentrował się na kodowaniu nazw, tak aby alternatywne wersje o tej samej nazwie były kodowane tak samo (lub prawie tak samo), a drugi krok koncentrował się na tworzeniu anonimowi.

W pierwszym kroku możesz użyć jednego z algorytmów fonetycznych (Soundex i wariantów) , zastosowanego do imienia, nazwiska i inicjałów w różnych porządkach. (Zobacz także ten artykuł ). Na tym etapie rozwiązujesz podobieństwa i różnice w nazwach w celu zrównoważenia wyników fałszywie dodatnich i fałszywych.

W drugim kroku możesz wybrać dowolną metodę skrótu lub metodę kryptograficzną, bez względu na to, jak ta metoda wpływa na dopasowanie nazw. Daje to swobodę korzystania z metody, która ma najlepsze cechy zarówno pod względem wydajności, niezawodności, jak i anonimowości.


Nie sądzę, aby ta sugestia rozwiązała problem przedstawiony w pytaniu. Gdzie jest elastyczność po szyfrowaniu? Jak zawęzić analizę bez dostępu do oryginalnych danych?
Air

@AirThomas Przepraszam, ale nie rozumiem twoich dwóch pytań. Co rozumiesz przez „elastyczność post-szyfrowania”? Nic takiego nie widziałem w twoim pytaniu / opisie. Co masz na myśli „dopracuj swoją analizę bez dostępu do oryginalnych danych”? Nie widziałem nic o „udoskonalaniu”.
MrMeritology

1
Próbowałem zidentyfikować problem w drugim akapicie sekcji Motywacja . Wyobraź sobie na przykład, że chcesz udostępnić swój zestaw danych różnym badaczom, którzy chcą przeprowadzić modelowanie. Istnieje wiele sprytnych i skutecznych metodologii, które można zastosować, a każdy badacz działa nieco inaczej. Nie możesz ujawnić nazwisk osób prywatnych w swoim zbiorze danych. Jeśli wykonasz tę część analizy przed wydaniem danych, wymusza to wybór metodologii na wszystkich.
Air

Jeśli dodatkowo podajesz skróty nazw, korzyścią jest to, że osoby trzecie mogą odróżnić dokładną tożsamość, ale nie więcej. Pytanie brzmi: w jaki sposób możesz podać więcej informacji o danych, których nie możesz udostępnić? Na przykład, czy istnieje metoda, która zachowuje na wyjściu mieszania / szyfrowania odległość edycji między dowolnymi danymi wejściowymi? Znalazłem przynajmniej jedną metodę, która przynajmniej przybliża tę funkcjonalność (więcej informacji znajdziesz w mojej własnej odpowiedzi). Mam nadzieję, że to wszystko wyjaśni.
Air
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.