Программа курса Урок 54 из 156 · Измеряйте приватность честно
Измеряйте приватность честно

k-анонимность

Почему это важно Организации часто делятся данными после "удаления имён" и называют их анонимными. Вы увидите на синтетических данных, как быстро три обычных факта возвращают имена. Так происходило реальное повторное опознание, и поэтому существует защита из урока 56.

Тест сплетни

Кто-то говорит: "Женщина с нашей улицы, родившаяся 3 марта 1981 года, только что получила диагноз." Имени не названо. Но сколько на одной улице женщин с ровно таким днём рождения? Вероятно, одна. Подробности и были именем.

Квазиидентификатор: факт, который не является именем, но вместе с несколькими другими указывает на одного человека. Почтовый индекс (zip-код), полная дата рождения и пол - классическая тройка.

Повторное опознание: возвращение имён в данные, опубликованные без них, обычно соединением с другим списком, где имена есть.

Известное исследование Латаньи Суини в 2000 году оценило, что около 87% людей в США можно выделить по одним лишь zip-коду, дате рождения и полу. Более позднее исследование с новыми данными переписи (Golle, 2006) дало ближе к 63%: меньше, но всё равно большинство людей, и в этом суть. Мы увидим тот же эффект на вымышленных данных.

Учебные данные

synthetic_people(2000) строит вымышленную медицинскую таблицу: id, name, zip, birth_date, gender, diagnosis. Никто в ней не реален. Мы "анонимизируем" её наивно, удаляя имя. synthetic_public_roll(people) строит вымышленный публичный список, как реестр клуба, с именами, zip-кодом, датой рождения и полом, но без диагноза.

Измерение риска: k

k-анонимность: таблица k-анонимна, когда каждое сочетание значений квазиидентификаторов есть хотя бы у k строк. k = 1 значит, что хотя бы один человек одинок, и его можно найти.

Чтобы найти k: сгруппируйте строки по кортежу квазиидентификаторов, посчитайте каждую группу и возьмите наименьшее число. С одним ["gender"] k большое. С zip-кодом, датой рождения и полом вместе k падает до 1.

Соединение

Для каждого человека из публичного списка постройте его ключ (zip, birth_date, gender) и ищите его в опубликованной таблице. Будьте строги: считайте совпадение, только когда ключ встречается ровно один раз в публикации и ровно один раз в списке. Тогда вы уверены. Если у двух записей один ключ, нельзя сказать, какая чья; если у двух людей в списке один ключ, нельзя сказать, кто есть кто.

reidentify(released, roll)
# {17: 'Mei Patel', 203: 'Omar Novak', ...}   record id -> name

Как только у записи 17 есть имя, у её диагноза тоже. Это вся атака: два безобидных на вид списка, одно соединение.

Распространённое заблуждение

"Удаление имён, почты и телефонов делает данные анонимными." Это убирает очевидные идентификаторы, но оставшиеся столбцы всё равно могут выделить людей. Анонимны ли данные, зависит от того, с чем ещё их можно соединить, поэтому урок 56 меняет сами данные.

Попробуйте Когда пройдёте, измените fraction списка с 0.6 на 0.2 и запустите снова. Число совпадений падает, но доля людей из списка, которых вы опознаёте, почти не меняется. Каждого человека раскрывают его собственные подробности, а не размер списка.

На других языках

JavaScript:

function reidentify(released, roll, cols) {
  const key = r => JSON.stringify(cols.map(c => r[c]));
  const count = list => list.reduce((m, r) => m.set(key(r), (m.get(key(r)) || 0) + 1), new Map());
  const a = count(released), b = count(roll);
  const byKey = new Map(released.map(r => [key(r), r]));
  const found = {};
  for (const p of roll) {
    if (a.get(key(p)) === 1 && b.get(key(p)) === 1) found[byKey.get(key(p)).id] = p.name;
  }
  return found;
}

Мышление в стиле SQL на C# (LINQ):

var matches =
    from r in released
    join p in roll on new { r.Zip, r.BirthDate, r.Gender }
                   equals new { p.Zip, p.BirthDate, p.Gender }
    select new { r.Id, p.Name };
// then keep only keys that occur once on each side

Итоги

  • Квазиидентификаторы (zip-код, дата рождения, пол) могут выделить людей без имени.
  • k - размер наименьшей группы с одинаковыми квазиидентификаторами; k = 1 значит, что кто-то раскрыт.
  • Соединение безымянной таблицы с публичным списком с именами опознаёт людей повторно.
  • Удаление имён - не анонимизация. Здесь только синтетические данные; защита - следующая.
Твоя очередь

Напишите quasi_key(row, columns) (кортеж значений), smallest_group(rows, columns) (размер наименьшей группы строк с одинаковым ключом: это и есть k) и reidentify(released, roll, columns=QUASI), которая возвращает словарь от id опубликованной записи к name из списка для каждого человека из списка, чей ключ встречается ровно один раз в released и ровно один раз в roll.

Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке

Это упражнение откроется скоро

Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.