мотивация

Я работаю с наборами данных, которые содержат информацию, позволяющую установить личность (PII), и иногда мне приходится делиться частью набора данных с третьими сторонами таким образом, чтобы не подвергать PII и не подвергать моего работодателя ответственности. Наш обычный подход - полностью скрыть данные или, в некоторых случаях, уменьшить их разрешение; например, замена точного адреса улицы соответствующим округом или районом переписи.

Это означает, что определенные виды анализа и обработки должны выполняться внутри компании, даже если у третьей стороны есть ресурсы и опыт, более подходящие для этой задачи. Поскольку исходные данные не разглашаются, в процессе анализа и обработки отсутствует прозрачность. В результате, способность любой третьей стороны выполнять QA / QC, корректировать параметры или вносить уточнения может быть очень ограниченной.

Анонимизация конфиденциальных данных

Одна из задач заключается в идентификации лиц по их именам в данных, предоставленных пользователями, с учетом ошибок и несоответствий. Частное лицо может быть записано в одном месте как «Дейв», а в другом - как «Дэвид», коммерческие организации могут иметь много разных сокращений, и всегда есть некоторые опечатки. Я разработал сценарии на основе ряда критериев, которые определяют, когда две записи с неидентичными именами представляют одного и того же человека, и присваивают им общий идентификатор.

На этом этапе мы можем сделать набор данных анонимным, удерживая имена и заменяя их этим личным идентификационным номером. Но это означает, что получатель почти не имеет информации, например, о силе матча. Мы бы предпочли иметь возможность передавать как можно больше информации без разглашения личности.

Что не работает

Например, было бы здорово иметь возможность шифровать строки, сохраняя при этом расстояние редактирования. Таким образом, третьи стороны могут выполнить некоторые из своих собственных QA / QC, или выбрать для дальнейшей обработки самостоятельно, никогда не получая доступ (или возможность потенциально перепроектировать) PII. Возможно, мы сопоставляем собственные строки с расстоянием редактирования <= 2, и получатель хочет посмотреть на последствия ужесточения этого допуска для расстояния редактирования <= 1.

Но единственный известный мне метод, который делает это, - это ROT13 (в общем, любой шифр сдвига ), который вряд ли даже считается шифрованием; это все равно что писать имена с ног на голову и говорить: «Обещай, что не перевернешь газету?»

Другим плохим решением было бы сократить все. «Эллен Робертс» становится «ER» и так далее. Это плохое решение, потому что в некоторых случаях инициалы, в сочетании с общедоступными данными, раскрывают личность человека, а в других случаях это слишком неоднозначно; У «Бенджамина Отелло Эймса» и «Банка Америки» будут одинаковые инициалы, но в остальном их имена не совпадают. Так что это не делает ни то, что мы хотим.

Не элегантная альтернатива - ввести дополнительные поля для отслеживания определенных атрибутов имени, например:

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

Я называю это «не элегантным», потому что это требует предвидения того, какие качества могут быть интересными, и это относительно грубо. Если имена удалены, вы не сможете сделать разумный вывод о силе совпадения между строками 2 и 3 или о расстоянии между строками 2 и 4 (т. Е. Насколько близко они совпадают).

Вывод

Цель состоит в том, чтобы преобразовать строки таким образом, чтобы при сохранении исходной строки было сохранено как можно больше полезных качеств исходной строки. Расшифровка должна быть невозможной или настолько непрактичной, что фактически невозможна, независимо от размера набора данных. В частности, метод, который сохраняет расстояние редактирования между произвольными строками, был бы очень полезен.

Я нашел пару документов, которые могут быть актуальны, но они немного над моей головой:

• Конфиденциальность Сравнение строк на основе расстояния Левенштейна
• Эмпирическое сравнение подходов к приближенному сопоставлению строк в привязке личных записей

Одна из ссылок, которые я упомянул в OP, привела меня к потенциальному решению, которое кажется довольно мощным, описанным в «Связывание записей с сохранением конфиденциальности с использованием фильтров Блума» ( doi: 10.1186 / 1472-6947-9-41 ):

Был разработан новый протокол для сохранения конфиденциальности записи с зашифрованными идентификаторами, допускающий ошибки в идентификаторах. Протокол основан на фильтрах Блума на q-граммах идентификаторов.

В статье подробно рассказывается о методе, который я кратко изложу здесь в меру своих возможностей.

Фильтр Блума - это серия битов фиксированной длины, в которой хранятся результаты фиксированного набора независимых хеш-функций, каждая из которых рассчитана на одно и то же входное значение. Выходные данные каждой хэш-функции должны быть значением индекса из числа возможных индексов в фильтре; т. е. если у вас 0-битная серия из 10 битов, хеш-функции должны возвращать (или отображать) значения от 0 до 9.

Фильтр начинается с каждого бита, установленного на 0. После хэширования входного значения с каждой функцией из набора хеш-функций каждый бит, соответствующий значению индекса, возвращаемого любой хеш-функцией, устанавливается в 1. Если тот же индекс возвращается более чем одна хеш-функция, бит с этим индексом устанавливается только один раз. Вы можете рассматривать фильтр Блума как суперпозицию набора хэшей в фиксированном диапазоне битов.

Протокол, описанный в вышеприведенной статье, делит строки на n-граммы, которые в данном случае представляют собой наборы символов. В качестве примера, "hello"может привести следующий набор 2-грамм:

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

Заполнение спереди и сзади пробелами, как правило, необязательно при построении n-граммов; примеры, приведенные в статье, в которой предлагается этот метод, используют такие отступы.

Каждый n-грамм может быть хеширован для создания фильтра Блума, и этот набор фильтров Блума может быть наложен на себя (побитовая операция ИЛИ), чтобы создать фильтр Блума для строки.

Если фильтр содержит намного больше битов, чем хеш-функций или n-грамм, произвольные строки относительно вряд ли произведут точно такой же фильтр. Однако, чем больше у n-граммов двух строк, тем больше битов будут совместно использовать их фильтры. Затем вы можете сравнить любые два фильтра A, Bс помощью их коэффициента кости.

D _{A, B} = 2 ч / (а + б)

Где hчисло битов, которые установлены в 1 в обоих фильтрах, aэто количество битов, установленных в 1 только в фильтре А, и bв количестве бит, установленных в 1 только в фильтре В. Если строки в точности совпадают, коэффициент кости будет 1; чем больше они отличаются, тем ближе будет коэффициент 0.

Поскольку хэш-функции отображают неопределенное количество уникальных входных данных на небольшое количество возможных битовых индексов, разные входные данные могут создавать один и тот же фильтр, поэтому коэффициент указывает только вероятность того, что строки одинаковые или похожие. Количество различных хеш-функций и количество битов в фильтре являются важными параметрами для определения вероятности ложных срабатываний - пар входов, которые намного менее похожи, чем предсказывает коэффициент Кости, полученный этим методом.

Я нашел этот урок очень полезным для понимания фильтра Блума.

Существует некоторая гибкость в реализации этого метода; см. также этот документ 2010 года (также связанный в конце вопроса) для некоторых указаний на то, насколько он эффективен по сравнению с другими методами и с различными параметрами.

На полпути, прочитав ваш вопрос, я понял, что расстояние Левенштейна может стать хорошим решением вашей проблемы. Приятно видеть, что у вас есть ссылка на статью по этой теме. Позвольте мне посмотреть, смогу ли я пролить свет на то, как будет выглядеть решение Левенштейна.

Расстояние Левенштейна используется во многих отраслях для разрешения сущностей, что делает его полезным, поскольку оно является мерой различия между двумя последовательностями. В случае сравнения строк это просто последовательности символов.

Это может помочь решить вашу проблему, позволив вам указать одно число, показывающее, насколько похож текст другого поля.

Вот пример основного способа использования Левенштейна с данными, которые вы предоставили:

Это обеспечивает правильное решение, расстояние 8 обеспечивает некоторую индикацию отношения, и оно очень PII-совместимо. Тем не менее, это все еще не супер полезно, давайте посмотрим, что произойдет, если мы сделаем некоторую текстовую магию, чтобы взять только первый инициал имени и полное имя, выбрасывая что-либо в середине:

Как видите, расстояние Левенштейна, равное 0, довольно показательно для отношений. Обычно поставщики данных объединяют множество перестановок Левенштейна имени и фамилии с 1, 2 или всеми символами, просто чтобы придать некоторую размерность тому, как связаны сущности, при этом сохраняя анонимность в данных.

Если возможно, я бы связал связанные записи (например, Дейв, Дэвид и т. Д.) И заменил их порядковым номером (1,2,3 и т. Д.) Или соленым хешем строки, которая используется для представления всех связанных записей ( например, Дэвид вместо Дейва).

Я предполагаю, что третьи стороны не должны иметь никакого представления о том, каково настоящее имя, иначе вы могли бы также дать его им.

редактировать : вам нужно определить и обосновать, какие операции должна выполнять третья сторона. Например, что не так с использованием инициалов, за которыми следует число (например, BOA-1, BOA-2 и т. Д.) Для устранения неоднозначности Bank of America с Бенджамином Отелло Эймсом? Если это слишком показательно, вы можете скопировать некоторые буквы или имена; например, [AE] -> 1, [FJ] -> 2 и т. д., поэтому BOA станет 1OA, или [«Банк», «Барри», «Брюс» и т. д.] -> 1, так что Bank of America снова 1OA.

Для получения дополнительной информации см. K-анонимность .

Один из вариантов (в зависимости от размера набора данных) состоит в том, чтобы просто указать расстояния редактирования (или другие меры сходства, которые вы используете) в качестве дополнительного набора данных.

Например:

1. Создать набор уникальных имен в наборе данных
2. Для каждого имени вычислите расстояние редактирования для каждого имени
3. Создайте идентификатор или необратимый хеш для каждого имени
4. Замените имена в исходном наборе данных на этот идентификатор
5. Предоставить матрицу редактирования расстояний между идентификационными номерами в качестве нового набора данных

Хотя многое еще можно сделать, чтобы деанонимизировать данные этих событий.

Например, если известно, что «Тим» является самым популярным именем для мальчика, подсчет частот идентификаторов, которые близко соответствуют известному проценту Тимов по всему населению, может дать это. Оттуда вы можете искать имена с расстоянием редактирования 1 и заключить, что эти идентификаторы могут ссылаться на «Том» или «Джим» (в сочетании с другой информацией).

Я не совсем уверен, но, возможно, хеширование с учетом локальных условий является хорошим решением. Он хэширует входные данные (в вашем случае - имена), поэтому оригинальные строки будут сохранены. С другой стороны, основная идея LSH - максимизировать вероятность хеширования для подобных элементов. Есть много разных LSH-реализаций. Я попробовал Nilsimsa-hash для сравнения текстов в твиттере, и это сработало довольно хорошо. Но я не уверен, насколько хорошо это будет работать в случае коротких строк (имен) - этот вопрос требует тестирования. Я попробовал ваши примеры, и вот результат (имя A, имя B, «расстояние» - максимум 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

Как видите, CHRISTOPH BAUER и CJ BAUER оказались ближайшей парой. Но разница не значительна. И просто для примера - хэш-представление этих имен:

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

Вот подход, который я не видел упомянутым: разделить процесс на два этапа: первый этап сфокусирован на кодировании имен, чтобы альтернативные версии с одинаковыми именами кодировались одинаково (или почти одинаково), а второй этап был сосредоточен на создании их анонимно.

Для первого шага вы можете использовать один из фонетических алгоритмов (Soundex и варианты) , применяемый к имени, фамилии и инициалам в различных порядках. (Смотрите также эту статью ). Именно на этом шаге вы разрешаете сходства и различия в именах, чтобы сбалансировать ложные срабатывания и ложные отрицания.

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