Введение
Задача поиска записей в наборе данных, относящихся к одной и той же сущности из разных источников. Связывание записей (также известное как сопоставление данных, объединение данных, разрешение сущностей и множество других терминов) – это задача выявления записей в наборе данных, которые описывают одну и ту же сущность, полученные из различных источников данных (например, файлов данных, книг, веб-сайтов и баз данных). Связывание записей необходимо при объединении различных наборов данных на основе сущностей, которые могут как иметь, так и не иметь общий идентификатор (например, ключ базы данных, URI, национальный идентификационный номер). Это может быть обусловлено различиями в структуре записей, месте их хранения или стилем и предпочтениями ответственных за данные. Набор данных, прошедший согласование с использованием связывания записей, может называться перекрестно связанным.
Record linkage (also known as data matching, data linkage, entity resolution, and many other terms) is the task of finding records in a data set that refer to the same entity across different data sources (e. g., data files, books, websites, and databases). Record linkage is necessary when joining different data sets based on entities that may or may not share a common identifier (e. g., database key, URI, National identification number), which may be due to differences in record shape, storage location, or curator style or preference. A data set that has undergone RL oriented reconciliation may be referred to as being cross linked.
Конвенции о наименовании
"Связь записей" – это термин, используемый статистиками, эпидемиологами и историками, в частности, для описания процесса объединения записей из разных источников данных, относящихся к одной и той же сущности. Однако для этого процесса существует множество других терминов. К сожалению, это разнообразие терминологии привело к небольшому количеству перекрестных ссылок между этими исследовательскими сообществами. Специалисты в области компьютерных наук часто называют это "сопоставлением данных" или "проблемой идентификации объектов". В коммерческих почтовых и базах данных это известно как "слияние/очистка" или "очистка списков". Другие названия, используемые для описания одной и той же концепции, включают: "разрешение корреференции/сущности/идентичности/имени/записи", "деамбигуация/связывание сущностей", "нечеткое сопоставление", "выявление дубликатов", "дедупликация", "сопоставление записей", "(ссылочное) согласование", "идентификация объектов", "интеграция данных/информации" и "конфляция". Несмотря на схожесть названий, связь записей и связанные данные – это два различных подхода к обработке и структурированию данных. Хотя оба подхода включают в себя идентификацию совпадающих сущностей в разных наборах данных, связь записей обычно отождествляет "сущности" с конкретными людьми, в то время как связанные данные основаны на возможности взаимосвязи любых веб-ресурсов в разных наборах данных, используя более широкое понятие идентификатора – URI.
История
Первоначальная идея связывания записей восходит к Хальберту Л. Данну в его статье 1946 года под названием «Связь записей», опубликованной в Американском журнале общественного здравоохранения. Говард Борден Ньюкомб затем заложил вероятностные основы современной теории связывания записей в статье 1959 года в журнале Science. Эти основы были формализованы в 1969 году Иваном Феллеги и Аланом Сунтером в их новаторской работе «Теория связывания записей», где они доказали, что вероятностное правило принятия решений, которое они описали, было оптимальным, когда атрибуты сравнения были условно независимы. В своей работе они отметили растущий интерес к применению достижений в области вычислительной техники и автоматизации к большим массивам административных данных, и теория Феллеги — Сунтера остаётся математической основой для многих приложений связывания записей. С конца 1990-х годов были разработаны различные методы машинного обучения, которые при благоприятных условиях могут использоваться для оценки условных вероятностей, необходимых для теории Феллеги — Сунтера. Ряд исследователей сообщили, что предположение об условной независимости алгоритма Феллеги — Сунтера часто нарушается на практике; однако опубликованные попытки явного моделирования условных зависимостей между атрибутами сравнения не привели к улучшению качества связывания записей. С другой стороны, алгоритмы машинного обучения или нейронных сетей, которые не опираются на эти предположения, часто обеспечивают значительно более высокую точность, при наличии достаточного количества размеченных обучающих данных. Связывание записей может быть выполнено полностью без использования компьютера, но основными причинами, по которым компьютеры часто используются для выполнения связывания записей, являются снижение или исключение ручной проверки и повышение воспроизводимости результатов. Компьютерное сопоставление имеет преимущества, такие как централизованный контроль обработки, улучшенный контроль качества, скорость, согласованность и лучшая воспроизводимость результатов.
Предварительная обработка данных
Связывание записей крайне чувствительно к качеству связываемых данных, поэтому все рассматриваемые наборы данных (особенно их ключевые поля-идентификаторы) в идеале должны пройти оценку качества данных перед связыванием записей. Многие ключевые идентификаторы для одной и той же сущности могут быть представлены совершенно по-разному между (и даже внутри) наборов данных, что может значительно усложнить связывание записей, если это не учитывать заранее. Например, ключевые идентификаторы человека по имени Уильям Дж. Смит могут выглядеть в трех различных наборах данных следующим образом:
Data set Name Date of birth City of residence Data set 1 William J. Smith 1/2/73 Berkeley, California Data set 2 Smith, W. J. 1973.1.2 Berkeley, CA Data set 3 Bill Smith Jan 2, 1973 Berkeley, Calif. In this example, the different formatting styles lead to records that look different but in fact all refer to the same entity with the same logical identifier values. Most, if not all, record linkage strategies would result in more accurate linkage if these values were first normalized or standardized into a consistent format (e. g., all names are "Surname, Given name", and all dates are "YYYY/MM/DD"). Standardization can be accomplished through simple rule based data transformations or more complex procedures such as lexicon based tokenization and probabilistic hidden Markov models. Several of the packages listed in the Software Implementations section provide some of these features to simplify the process of data standardization.
Набор данных Имя Дата рождения Город проживания
Набор данных 1 William J. Smith 1/2/73 Berkeley, California
Набор данных 2 Smith, W. J. 1973.1.2 Berkeley, CA
Набор данных 3 Bill Smith Jan 2, 1973 Berkeley, Calif.
Data set Name Date of birth City of residence Data set 1 William J. Smith 1/2/73 Berkeley, California Data set 2 Smith, W. J. 1973.1.2 Berkeley, CA Data set 3 Bill Smith Jan 2, 1973 Berkeley, Calif. In this example, the different formatting styles lead to records that look different but in fact all refer to the same entity with the same logical identifier values. Most, if not all, record linkage strategies would result in more accurate linkage if these values were first normalized or standardized into a consistent format (e. g., all names are "Surname, Given name", and all dates are "YYYY/MM/DD"). Standardization can be accomplished through simple rule based data transformations or more complex procedures such as lexicon based tokenization and probabilistic hidden Markov models. Several of the packages listed in the Software Implementations section provide some of these features to simplify the process of data standardization.
В этом примере различные стили форматирования приводят к тому, что записи выглядят по-разному, хотя на самом деле все они относятся к одному и тому же объекту с одинаковыми логическими значениями идентификаторов. Большинство, если не все, стратегии связывания записей дадут более точные результаты, если эти значения предварительно нормализовать или стандартизировать в единый формат (например, все имена в формате "Фамилия, Имя", а все даты – "YYYY/MM/DD"). Стандартизация может быть выполнена с помощью простых преобразований данных на основе правил или более сложных процедур, таких как токенизация на основе словарей и вероятностные скрытые модели Маркова. Некоторые из пакетов, перечисленных в разделе "Программные реализации", предоставляют некоторые из этих функций для упрощения процесса стандартизации данных.
Data set Name Date of birth City of residence Data set 1 William J. Smith 1/2/73 Berkeley, California Data set 2 Smith, W. J. 1973.1.2 Berkeley, CA Data set 3 Bill Smith Jan 2, 1973 Berkeley, Calif. In this example, the different formatting styles lead to records that look different but in fact all refer to the same entity with the same logical identifier values. Most, if not all, record linkage strategies would result in more accurate linkage if these values were first normalized or standardized into a consistent format (e. g., all names are "Surname, Given name", and all dates are "YYYY/MM/DD"). Standardization can be accomplished through simple rule based data transformations or more complex procedures such as lexicon based tokenization and probabilistic hidden Markov models. Several of the packages listed in the Software Implementations section provide some of these features to simplify the process of data standardization.
Резолюция организаций
Резолюция сущностей – это операционный процесс аналитики, обычно поддерживаемый движком разрешения сущностей или промежуточным программным обеспечением, посредством которого организации могут связывать разрозненные источники данных с целью выявления возможных совпадений сущностей и неочевидных связей между различными хранилищами данных. Он анализирует всю информацию, относящуюся к физическим лицам и/или организациям из множества источников данных, а затем применяет оценку вероятности и правдоподобия для определения, какие идентификаторы соответствуют друг другу и какие, если таковые имеются, неочевидные связи существуют между этими идентификаторами. Движки разрешения сущностей обычно используются для выявления рисков, мошенничества и конфликтов интересов, но также являются полезными инструментами для интеграции данных о клиентах (CDI) и управления основными данными (MDM). Типичные области применения движков разрешения сущностей включают проверку по спискам террористов, выявление страхового мошенничества, соблюдение требований Закона США о патриотизме, выявление организованных преступных групп в сфере розничной торговли и проверку кандидатов. Например: в различных хранилищах данных – записи о сотрудниках, данные о поставщиках, списки наблюдения и т.д. – организация может иметь несколько вариантов представления сущности под названием ABC, которые могут относиться к одному и тому же лицу, а могут и не относиться. Эти записи могут фактически отображаться как ABC1, ABC2 или ABC3 в этих источниках данных. Сравнивая сходства между базовыми атрибутами, такими как адрес, дата рождения или номер социального страхования, пользователь может исключить некоторые возможные совпадения и подтвердить другие как весьма вероятные. Затем движки разрешения сущностей применяют правила, основанные на здравом смысле, для выявления скрытых связей в данных. В приведенном выше примере, возможно, ABC1 и ABC2 – это не один и тот же человек, а два разных человека, имеющих общие атрибуты, такие как адрес или номер телефона.
Гибридная связь человека и машины
Для высококачественного сопоставления записей часто требуется гибридная система, объединяющая возможности человека и машины, чтобы безопасно управлять неопределенностью в непрерывно меняющихся и хаотичных потоках больших данных. Учитывая, что ошибки сопоставления распространяются на сопоставленные данные и их анализ, были предложены интерактивные системы сопоставления записей. Интерактивное сопоставление записей определяется как итеративная корректировка результатов, полученных автоматизированными методами, человеком, а также управление неопределенностью и ее распространением на последующий анализ. Основная задача интерактивных систем сопоставления записей – ручное разрешение неоднозначных сопоставлений и проверка результатов до достижения приемлемого уровня точности для конкретного применения. Также были предложены варианты интерактивного сопоставления записей, обеспечивающие повышенную конфиденциальность на этапах взаимодействия с человеком.
Соединение записей для сохранения конфиденциальности
Все чаще возникает необходимость в сопоставлении записей между базами данных, принадлежащими разным организациям, где взаимодополняющие данные, хранящиеся в этих организациях, могут, например, помочь выявить пациентов, склонных к определенным нежелательным реакциям на лекарства (сопоставление баз данных больниц, врачей, аптек). Однако во многих подобных случаях базы данных, подлежащие сопоставлению, содержат конфиденциальную информацию о людях, которую нельзя передавать между организациями. Методы сопоставления записей с сохранением конфиденциальности (PPRL) были разработаны для сопоставления баз данных без необходимости обмена исходными конфиденциальными данными между организациями, участвующими в сопоставлении. В PPRL значения атрибутов записей, подлежащих сравнению, обычно кодируются или шифруются. Одним из популярных методов кодирования является фильтр Блума, который позволяет вычислять приблизительное сходство между закодированными значениями без необходимости обмена соответствующими конфиденциальными исходными данными. В конце процесса PPRL организациям, участвующим в сопоставлении, раскрывается только ограниченная информация о парах записей, классифицированных как совпадения. Методы, используемые в PPRL