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ą:
źródło
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ś:
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:
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.
źródło
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ść .
źródło
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:
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).
źródło
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):
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:
źródło
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.
źródło