Motivasi

Saya bekerja dengan kumpulan data yang berisi informasi pengenal pribadi (PII) dan kadang-kadang perlu berbagi bagian dari dataset dengan pihak ketiga, dengan cara yang tidak mengekspos PII dan membuat majikan saya bertanggung jawab. Pendekatan kami yang biasa di sini adalah menahan data sepenuhnya, atau dalam beberapa kasus mengurangi resolusinya; misalnya, mengganti alamat jalan yang tepat dengan daerah atau sensus yang sesuai.

Ini berarti bahwa beberapa jenis analisis dan pemrosesan harus dilakukan sendiri, bahkan ketika pihak ketiga memiliki sumber daya dan keahlian yang lebih sesuai dengan tugas tersebut. Karena sumber data tidak diungkapkan, cara kami melakukan analisis dan pemrosesan ini kurang transparan. Akibatnya, kemampuan pihak ketiga mana pun untuk melakukan QA / QC, menyesuaikan parameter atau membuat penyempurnaan mungkin sangat terbatas.

Menganonimkan Data Rahasia

Satu tugas melibatkan mengidentifikasi individu dengan nama mereka, dalam data yang dikirimkan pengguna, sambil memperhitungkan kesalahan dan inkonsistensi akun. Seorang individu pribadi dapat direkam di satu tempat sebagai "Dave" dan di tempat lain sebagai "David," entitas komersial dapat memiliki banyak singkatan yang berbeda, dan selalu ada beberapa kesalahan ketik. Saya telah mengembangkan skrip berdasarkan sejumlah kriteria yang menentukan kapan dua catatan dengan nama yang tidak identik mewakili individu yang sama, dan menetapkannya sebagai ID umum.

Pada titik ini kita dapat membuat dataset anonim dengan menahan nama dan menggantinya dengan nomor ID pribadi ini. Tetapi ini berarti penerima hampir tidak memiliki informasi tentang misalnya kekuatan pertandingan. Kami lebih suka untuk dapat memberikan informasi sebanyak mungkin tanpa mengungkapkan identitas.

Apa yang Tidak Bekerja

Misalnya, akan sangat bagus untuk dapat mengenkripsi string sambil menjaga jarak sunting. Dengan cara ini, pihak ketiga dapat melakukan beberapa QA / QC mereka sendiri, atau memilih untuk melakukan pemrosesan lebih lanjut sendiri, tanpa pernah mengakses (atau secara potensial dapat merekayasa balik) PII. Mungkin kami mencocokkan string di rumah dengan jarak edit <= 2, dan penerima ingin melihat implikasi pengetatan toleransi untuk mengedit jarak <= 1.

Tetapi satu-satunya metode yang saya kenal yang melakukan ini adalah ROT13 (lebih umum, shift cipher ), yang bahkan tidak dianggap sebagai enkripsi; itu seperti menulis nama-nama terbalik dan berkata, "Berjanjilah kamu tidak akan membalik kertas itu?"

Solusi buruk lainnya adalah menyingkat semuanya. "Ellen Roberts" menjadi "ER" dan sebagainya. Ini adalah solusi yang buruk karena dalam beberapa kasus inisial, terkait dengan data publik, akan mengungkapkan identitas seseorang, dan dalam kasus lain itu terlalu ambigu; "Benjamin Othello Ames" dan "Bank of America" ​​akan memiliki inisial yang sama, tetapi nama mereka berbeda. Jadi itu tidak melakukan salah satu hal yang kita inginkan.

Alternatif yang tidak berlaku adalah dengan memperkenalkan bidang tambahan untuk melacak atribut tertentu dari nama, misalnya:

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

Saya menyebutnya "tidak elok" karena memerlukan antisipasi kualitas mana yang mungkin menarik dan relatif kasar. Jika nama dihapus, tidak banyak yang dapat Anda simpulkan tentang kekuatan kecocokan antara baris 2 & 3, atau tentang jarak antara baris 2 & 4 (yaitu, seberapa dekat mereka dengan pencocokan).

Kesimpulan

Tujuannya adalah untuk mengubah string sedemikian rupa sehingga sebanyak mungkin kualitas yang berguna dari string asli dipertahankan sambil mengaburkan string asli. Dekripsi seharusnya tidak mungkin, atau tidak praktis untuk secara efektif tidak mungkin, tidak peduli ukuran set data. Secara khusus, metode yang menjaga jarak sunting antara string arbitrer akan sangat berguna.

Saya telah menemukan beberapa makalah yang mungkin relevan, tetapi mereka sedikit di atas kepala saya:

• Privasi Melestarikan Perbandingan String Berdasarkan Jarak Levenshtein
• Suatu Perbandingan Empiris dari Pendekatan untuk Perkiraan String yang Cocok dalam Hubungan Rekaman Pribadi

Salah satu referensi yang saya sebutkan di OP menuntun saya ke solusi potensial yang tampaknya cukup kuat, dijelaskan dalam "Hubungan catatan pelestarian privasi menggunakan filter Bloom" ( doi: 10.1186 / 1472-6947-9-41 ):

Protokol baru untuk hubungan catatan pelestarian privasi dengan pengidentifikasi terenkripsi memungkinkan untuk kesalahan pengidentifikasi telah dikembangkan. Protokol ini didasarkan pada filter Bloom pada q-gram pengidentifikasi.

Artikel ini menjelaskan secara terperinci tentang metode ini, yang akan saya ringkas di sini sesuai kemampuan saya.

Filter Bloom adalah serangkaian bit dengan panjang tetap yang menyimpan hasil dari serangkaian fungsi hash independen, masing-masing dihitung pada nilai input yang sama. Output dari masing-masing fungsi hash harus berupa nilai indeks dari antara indeks yang mungkin ada dalam filter; yaitu, jika Anda memiliki serangkaian 0-diindeks dari 10 bit, fungsi hash harus mengembalikan (atau dipetakan ke) nilai dari 0 hingga 9.

Filter dimulai dengan setiap bit diatur ke 0. Setelah hashing nilai input dengan setiap fungsi dari set fungsi hash, masing-masing bit yang sesuai dengan nilai indeks dikembalikan oleh fungsi hash diatur ke 1. Jika indeks yang sama dikembalikan oleh lebih dari satu fungsi hash, bit pada indeks itu hanya disetel sekali. Anda bisa menganggap filter Bloom sebagai superposisi dari set hash ke rentang bit yang tetap.

Protokol yang dijelaskan dalam artikel yang ditautkan di atas membagi string menjadi n-gram, yang dalam hal ini adalah kumpulan karakter. Sebagai contoh, "hello"mungkin menghasilkan set 2 gram berikut:

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

Melapisi bagian depan dan belakang dengan spasi tampaknya umumnya opsional saat membuat n-gram; contoh-contoh yang diberikan dalam makalah yang mengusulkan metode ini menggunakan padding tersebut.

Setiap n-gram dapat hash untuk menghasilkan filter Bloom, dan set filter Bloom ini dapat ditumpangkan pada dirinya sendiri (operasi bitwise ATAU) untuk menghasilkan filter Bloom untuk string.

Jika filter mengandung lebih banyak bit daripada fungsi hash atau n-gram, string arbitrer relatif tidak mungkin menghasilkan filter yang persis sama. Namun, semakin banyak n-gram dua string yang sama, semakin banyak bit filter mereka pada akhirnya akan berbagi. Anda kemudian dapat membandingkan dua filter A, Bdengan koefisien Dice mereka:

D _{A, B} = 2j / (a ​​+ b)

Dimana hadalah jumlah bit yang di set ke 1 di kedua filter, aadalah jumlah bit set ke 1 di hanya penyaring A, dan bmerupakan jumlah bit set ke 1 di hanya penyaring B. Jika string yang persis sama, koefisien Dice akan menjadi 1; semakin mereka berbeda, semakin dekat koefisien akan 0.

Karena fungsi hash memetakan sejumlah input unik ke sejumlah kecil indeks bit yang mungkin, input yang berbeda dapat menghasilkan filter yang sama, sehingga koefisien hanya menunjukkan probabilitas bahwa string sama atau mirip. Jumlah fungsi hash yang berbeda dan jumlah bit dalam filter adalah parameter penting untuk menentukan kemungkinan false positive - pasangan input yang jauh lebih mirip daripada koefisien Dice yang dihasilkan oleh metode ini.

Saya menemukan tutorial ini sangat membantu untuk memahami filter Bloom.

Ada beberapa fleksibilitas dalam penerapan metode ini; lihat juga makalah 2010 ini (juga ditautkan pada akhir pertanyaan) untuk beberapa indikasi tentang bagaimana performant dalam kaitannya dengan metode lain, dan dengan berbagai parameter.

Di tengah membaca pertanyaan Anda, saya menyadari Levenshtein Distance bisa menjadi solusi yang bagus untuk masalah Anda. Adalah baik untuk melihat bahwa Anda memiliki tautan ke makalah tentang topik ini, biarkan saya melihat apakah saya dapat menjelaskan seperti apa solusi Levenshtein nantinya.

Jarak Levenshtein digunakan di banyak industri untuk resolusi entitas, yang membuatnya berguna adalah bahwa itu adalah ukuran perbedaan antara dua urutan. Dalam kasus perbandingan string itu hanya urutan karakter.

Ini bisa membantu menyelesaikan masalah Anda dengan memungkinkan Anda memberikan satu nomor yang memberikan ukuran seberapa mirip teks dari bidang lain.

Berikut adalah contoh cara dasar menggunakan Levenshtein dengan data yang Anda berikan:

Ini memberikan solusi ok, jarak 8 memberikan beberapa indikasi hubungan, dan sangat sesuai PII. Namun, itu masih tidak terlalu berguna, mari kita lihat apa yang terjadi jika kita melakukan beberapa keajaiban teks untuk mengambil hanya inisial pertama dari nama depan dan nama belakang lengkap menjatuhkan apa pun di tengah:

Seperti yang Anda lihat, jarak Levenshtein 0 cukup mengindikasikan hubungan. Umumnya penyedia data akan menggabungkan sekelompok permutasi Levenshtein dari nama depan dan belakang dengan 1, 2, atau semua karakter hanya untuk memberikan beberapa dimensi tentang bagaimana entitas terkait sementara tetap mempertahankan anonimitas dalam data.

Jika memungkinkan, saya akan menautkan catatan terkait (misalnya, Dave, David, dll.) Dan menggantinya dengan nomor urut (1,2,3, dll.) Atau hash asin dari string yang digunakan untuk mewakili semua catatan terkait ( misalnya, David bukannya Dave).

Saya berasumsi bahwa pihak ketiga tidak perlu tahu apa nama sebenarnya, jika tidak, Anda bisa memberikannya kepada mereka.

sunting : Anda perlu mendefinisikan dan membenarkan operasi seperti apa yang perlu dilakukan pihak ketiga. Misalnya, apa yang salah dengan menggunakan inisial diikuti oleh angka (misalnya, BOA-1, BOA-2, dll.) Untuk mengacaukan Bank of America dari Benjamin Othello Ames? Jika itu terlalu terbuka, Anda bisa membuang beberapa huruf atau nama; misal, [AE] -> 1, [FJ] -> 2, dll. jadi BOA akan menjadi 1OA, atau ["Bank", "Barry", "Bruce", dll] -> 1 sehingga Bank of America kembali 1OA.

Untuk informasi lebih lanjut lihat k-anonimitas .

Satu opsi (tergantung pada ukuran dataset Anda) adalah hanya memberikan jarak sunting (atau ukuran kesamaan lainnya yang Anda gunakan) sebagai dataset tambahan.

Misalnya:

1. Hasilkan satu set nama unik dalam dataset
2. Untuk setiap nama, hitung jarak edit satu sama nama lainnya
3. Hasilkan ID atau hash yang tidak dapat dikembalikan untuk setiap nama
4. Ganti nama dalam dataset asli dengan ID ini
5. Berikan matriks jarak edit antara nomor ID sebagai dataset baru

Meskipun masih banyak yang bisa dilakukan untuk mendanonimkan data dari data ini.

Misalnya jika "Tim" dikenal sebagai nama yang paling populer untuk anak laki-laki, penghitungan frekuensi ID yang cocok dengan persentase Tim yang diketahui di seluruh populasi mungkin memberikan itu. Dari sana Anda kemudian dapat mencari nama dengan jarak sunting 1, dan menyimpulkan bahwa ID tersebut mungkin merujuk ke "Tom" atau "Jim" (bila digabungkan dengan info lainnya).

Saya tidak yakin, tapi mungkin hashing yang sensitif terhadap lokalitas adalah solusi yang baik. Itu hashing dari input data (dalam kasus Anda - nama), sehingga string asli akan dipertahankan. Di sisi lain, ide utama LSH adalah untuk memaksimalkan kemungkinan hash untuk item serupa. Ada banyak implementasi LSH yang berbeda. Saya mencoba hash Nilsimsa untuk membandingkan teks tweet, dan itu bekerja dengan cukup baik. Tapi saya tidak yakin, seberapa baik itu akan bekerja jika string pendek (nama) - masalah ini memerlukan pengujian. Saya mencoba contoh Anda, dan inilah hasilnya (nama A, nama B, "jarak" - maksimum 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

Seperti yang Anda lihat, CHRISTOPH BAUER dan CJ BAUER muncul menjadi pasangan terdekat. Tetapi perbedaannya tidak signifikan. Dan hanya sebagai contoh - representasi hash dari nama-nama ini:

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

Berikut ini pendekatan yang saya tidak lihat disebutkan: pisahkan proses menjadi dua langkah: langkah pertama difokuskan pada pengkodean nama sehingga versi alternatif dari nama yang sama dikodekan sama (atau hampir sama), dan langkah kedua berfokus pada pembuatan mereka anonim.

Untuk langkah pertama, Anda dapat menggunakan salah satu Algoritma Fonetik (Soundex dan varian) , diterapkan pada nama depan, nama belakang, dan inisial dalam berbagai pesanan. (Lihat artikel ini juga). Itu dalam langkah ini di mana Anda menyelesaikan persamaan vs perbedaan dalam nama untuk menyeimbangkan positif palsu dari negatif palsu.

Untuk langkah kedua, Anda dapat memilih metode hashing atau kriptografi apa pun yang Anda suka, tanpa memperhatikan bagaimana metode itu memengaruhi pencocokan nama. Ini memberi Anda kebebasan untuk menggunakan metode yang memiliki karakteristik terbaik untuk kinerja, ketahanan, dan anonimitas.