Введение
Некоторое время назад я стал участником проекта по разработке программного продукта, предназначенного для анализа поступающих из медицинских организаций записей о пациентах и данных об их состоянии здоровья с целью формирования единой медицинской карты. Долгое время команда не могла выработать подход к объединению данных пациентов. Отправной точкой послужило изучение исходных кодов решения Open EMPI (Open Enterprise Master Patient Index), которые подтолкнули нас к алгоритмам анализа похожести строк. С этого момента началось более глубокое изучение материалов, позволившее создать сначала макет, а потом и рабочее решение.
До сих пор, на разного рода презентациях приходится слышать много вопросов о логике работы подобных продуктов, из чего я делаю вывод, что обзор методов связывания текстовых записей будет интересен широкому кругу читателей.
Материал представляет собой перевод статьи wikipedia «Record linkage» с авторскими правками и дополнениями.
Что такое «связывание текстовых записей»?
Термин «связывание текстовых записей» (record linkage) описывает процесс присоединения текстовых записей из одного источника данных к записям из другого, при условии что они описывают один и тот же объект. В информатике это называется «сопоставлением данных» или «проблемой идентичности объекта». Иногда используются альтернативные определения, такие как «идентификация», «привязка, «обнаружение дубликатов», «дедупликация», «сопоставление записей», «идентификация объекта», которые описывают одно и тоже понятие. Это терминологическое изобилие привело к разделению подходов обработки и структурирования информации — связыванию записей и связыванию данных. Хотя они оба определяют идентификацию совпадающих объектов по различным наборам параметров, термин «связывание текстовых записей» принято использовать, когда речь идет о «сущности» человек, в то время как под «связыванием данных» понимают возможность связывания любого веб-ресурса между наборами данных, используя, соответственно, более широкую концепцию идентификатора, а именно URI.
Зачем это нужно?
При разработке программных продуктов для построения автоматизированных систем, применяемых в различных областях, связанных с обработкой персональных данных человека (здравоохранение, история, статистика, образование и т.д.), встает задача идентификации данных о субъектах учета, поступающих из различных источников.
Однако, при сборе описаний из большого числа источников, возникают проблемы, затрудняющие их однозначную идентификацию. К таким проблемам можно отнести:
- опечатки;
- перестановки полей (например, в имени-отчестве);
- использование сокращений и аббревиатур;
- применение разного формата идентификаторов (даты, номера документов и т.д).
- фонетические искажения;
- и.т.д.
Качество первичных данных напрямую влияет на результат процесса связывания. Из-за названных проблем, часто в обработку передаются наборы данных, которые хоть и описывают один и тот же объект, но внешне эти записи выглядят по-разному. Поэтому с одной стороны, все переданные идентификаторы записей оцениваются на применимость к использованию в процессе идентификации, а с другой стороны, сами записи нормализуются или стандартизуются с целью приведения к их единому формату.
Экскурс в историю
Первоначальную идею о связывании записей высказал Гилберт Данн (Halbert L. Dunn), опубликовав в 1946 году в журнале «American Journal of Public Health» статью под названием «Record Linkage».
Позже, в 1959 году, статьей «Automatic Linkage of Vital Records» в журнале Science, Говард Ньюкомб (Howard B. Newcombe) заложил вероятностные основы современной теории связывания строк, которые в 1969 году были развиты и закреплены Иваном Феллеги (Ivan Fellegi) и Аланом Сантером (Alan Sunter). Их работа «A Theory For Record Linkage» до сих пор является математическим обоснованием для многих алгоритмов связывания.
Основное развитие алгоритмы получили в 90-х годах прошлого столетия. Тогда из различных областей (статистика, архивное дело, эпидемиология, история и другие) к нам пришли часто используемые сейчас в программных продуктах алгоритмы, такие как сходство (расстояние) Джаро-Винклера (Jaro-Winkler distance) и расстояние Левенштейна (Levenshtein distance), однако, некоторые решения, например, фонетический алгоритм Soundex, появился гораздо раньше — в 20-е годы прошлого века.
Алгоритмы сравнения текстовых записей
Различают детерминированные и вероятностные алгоритмы сравнения текстовых записей. Детермированные (deterministic) алгоритмы основаны на полном совпадении атрибутов записей. Вероятноятностные (probabilistic) алгоритмы позволяют вычислить степень соответствия атрибутов записей и на основании этого принять решение о возможности их связи.
Детерминированные алгоритмы
Самый простой способ сравнения строк основан на четких правилах, когда ссылки между объектами генерируются на основании количества совпадений атрибутов наборов данных. Т.е две записи соответствуют друг другу через детерминированный алгоритм если все или некоторые их атрибуты идентичны. Детерминированные алгоритмы подходят для сравнения субъектов, описанных набором данных, которые идентифицируются общим идентификатором (например, Страховым номером индивидуального лицевого счета в Пенсионном фонде — СНИЛС) или имеют несколько репрезентативных идентификаторов (дата рождения, пол и т.д.), которым можно доверять.
Детерминированные алгоритмы возможно применять тогда, когда в обработку передаются четко структурированные (стандартизированные) наборы данных.
Например, имеет следующий набор текстовых записей:
| № | СНИЛС | Имя | Дата рождения | Пол |
|---|---|---|---|---|
| A1 | 163-648-564 96 | Жванецкий Михаил | 06.03.1934 | М |
| A2 | 163-648-564 96 | Жванецкий Михаил | 06.03.1934 | М |
| A3 | 126-029-036 24 | Ильченко Виктор | 02.01.1937 | М |
| A4 | Новикова Клара | 12.26.1946 | Ж |
| № | СНИЛС | Имя | Дата рождения | Пол |
|---|---|---|---|---|
| Б1 | 126-029-036 24 | Ильиченко Виктор | 02.01.1937 | М |
| Б2 | Живанецкий Михаил | 06.03.1934 | М | |
| Б3 | Зерчанинова Клара | 12.26.1946 | 2 |
Ранее было сказано, что самый простой детерминированный алгоритм — это использование уникального идентификатора, который, как предполагается, однозначно идентифицирует персону. Например, будем считать, что все записи, имеющие одинаковое значение идентификатора (СНИЛС), описывают один и тот же субъект, в противном случае — это разные субъекты. Детерминированная связь в таком случае породит следующие пары: A1 и А2, А3 и Б1. Б2 не будет связан с А1 и А2, так как не имеет значение идентификатора, хотя и совпадает по содержанию с указанными записями.
Указанные исключения приводят к необходимости дополнения детерминированного алгоритма новыми правилами. Например, в случае отсутствия уникального идентификатора, можно воспользоваться другими атрибутами — таким как имя, дата рождения и пол. В приведенном примере это дополнительное правило опять не даст соответствия Б2 и А1/А2, потому что теперь отличаются имена — имеет место фонетическое искажение фамилии.
Решить эту проблему можно с использованием методов фонетического анализа, но при изменении фамилии (например, в случае брака) потребуется прибегнуть к применению нового правила, например, сравнению даты рождения или допустить различия в имеющихся атрибутах записи (например, пол).
Пример наглядно иллюстрирует, что детерминированный алгоритм очень чувствителен к качеству данных, а увеличение количества атрибутов записей может привести к существенному увеличению количества применяемых правил, что значительно усложняет использование детерминированных алгоритмов.
Более того, применение детерминированных алгоритмов возможно, в случае наличия выверенного набора данных (мастер-справочника) с которым производится сравнение поступающей информации. Однако в случае постоянного пополнения самого мастер-справочника может потребоваться полная перестройка существующих связей, что делает использование детерминированных алгоритмов трудоемким или попросту невозможным.
Вероятностные алгоритмы
Вероятностные алгоритмы связывания строковых записей используют более широкий набор атрибутов, нежели детерминированные, причем для каждого атрибута вычисляется весовой коэффициент, определяющий способность влиять на связь при итоговой оценке вероятности соответствия оцениваемых записей. Записи, набравшие итоговый вес выше определенного порога считаются связанными, записи набравшие итоговый вес ниже порога — считаются не связанными. Пары, набравшие значение итогового веса из середины диапазона считаются кандидатами на связывание и могут быть рассмотрены позже (например, оператором), который примет решение об их объединении (связи) либо оставит несвязанными. Таким образом, в отличие от детерминированных алгоритмов, которые представляют собой набор большого количества четких (запрограммированных) правил, вероятностные алгоритмы могут быть адаптированы к качеству данных подбором пороговых значений и не требуют перепрограммирования.
Итак, вероятностные алгоритмы назначают весовые коэффициенты (u и m) атрибутам записи, с помощью которых будет определяться их соответствие или несоответствие друг другу.
Коэффициент u определяет вероятность того, что идентификаторы двух независимых записей совпали случайно. Например, u-вероятность месяца рождения (когда имеется двенадцать равномерно распределенных значений) составит 1\12 = 0.083. Идентификаторы со значениями, которые распределены неравномерно будут иметь разные вероятности для разных значений (иногда, включая пропущенные значения).
Коэффициент m — это вероятность того, что идентификаторы в сравниваемых парах соответствуют друг другу или достаточно похожи — например, в случае высокой вероятности по алгоритму Джаро-Винклера или низкой по алгоритму Левенштейна. В случае полного соответствия атрибутов записей это значение должно иметь значение 1.0, но учитывая низкую вероятность этого, коэффициент должен быть оценен иначе. Эта оценка может быть произведена на основе предварительного анализа набора данных, например, путем ручного «обучения» вероятностного алгоритма при идентификации большого числа совпадающих и несовпадающих пар или путем итеративного запуска алгоритма с целью подбора наиболее подходящего значения m-коэффициента.
Если m-вероятность определить как 0.95, то коэффициенты соответствия\несоответствия для месяца рождения будут выглядеть так:
| Метрика | Доля ссылок | Доля значений, не ссылок | Частота | Вес |
|---|---|---|---|---|
| Соответствие | m=0.95 | u=0.083 | m\u = 11.4 | ln(m/u)/ln(2) ≈ 3.51 |
| Несоответствие | 1-m = 0.05 | 1-u = 0.917 | (1-m)/(1-u) ≈ 0.0545 | ln((1-m)/(1-u))/ln(2) ≈ -4.20 |
Подобные расчеты должны быть произведены для других идентификаторов записей с целью определения их коэффициентов соответствия и несоответствия. Затем, каждый идентификатор одной записи сравнивается с соответствующим идентификатором другой записи для определения общего веса пары: вес соответствующей пары добавляется к общему результату с нарастающим итогом, в то время как вес несоответствующей пары вычитается из общего результата. Полученная сумма сравнивается с выявленными пороговыми значениями чтобы определить следует ли связать или не связать анализируемую пару автоматически или передать ее на рассмотрение оператору.
Блокирование
Определение порогов соответствия\несоответствия является балансом между получением приемлемой чувствительности (доли связанных записей, выявляемых алгоритмом) и прогностической ценностью получаемого результата (т.е. точности, как меры действительно соответствующих друг другу записей, связанных алгоритмом). Поскольку определение порогов может быть очень сложной задачей, особенно для больших наборов данных, для повышения эффективности вычислений часто применяется метод, известный как блокирование. Блокируются попытки выполнить сравнение между записями, для которых выявлено значительное расхождение (дискриминация) в значениях базовых атрибутов. Это приводит к увеличению точности за счет уменьшения чувствительности.
Например, блокировка на основе фонетического кодирования фамилии позволяет сократить общее количество необходимых сравнений и повышает вероятность того, что связи между записями будут верными, так как два атрибута уже согласованы, но потенциально, может пропустить записи, относящиеся к одному и тому же лицу, чья фамилия изменена (например, в результате замужества). Блокировка по месяцу рождения более стабильный показатель, который может быть скорректирован только в случае наличия ошибки в исходных данных, но обеспечивает более скромную выгоду в положительной прогностической ценности и потери чувствительности, так как создает двенадцать различных групп крайне больших наборов данных и не приводит к увеличению скорости вычислений.
Таким образом, наиболее эффективные системы связывания текстовых записей часто используют несколько блокирующих проходов для группировки данных различными способами для того, чтобы подготовить группы записей, которые впоследствии должны быть переданы на анализ.
Машинное обучение
В последнее время стали применяться различные методы машинного обучения для связывания текстовых записей. В своей работе, опубликованной в 2011 году, Рэндалл Вилсон (Randall Wilson) показал, что классический алгоритм вероятностного связывания текстовых записей эквивалентен наивному байесовскому алгоритму (naive Bayes algorithm) и испытывает те же проблемы от предположения о независимости признаков классификации. Для повышения точности анализа автор предлагает использовать базовую модель нейросети под названием однослойный персептрон (single-layer perceptron), применение которого позволяет существенно превзойти результаты, получаемые с применением традиционных вероятностных алгоритмов.
Фонетическое кодирование
Фонетические алгоритмы сопоставляют двум схожим по произношению словам одинаковые коды, что позволяет осуществлять сравнение таких слов на основе их фонетического сходства.
Большинство фонетических алгоритмов разработаны для анализа слов английского языка, хотя в последнее время некоторые алгоритмы были модифицированы под использование с другими языками, либо изначально созданы как национальные решения (например, Caverphone).
Soundex
Классическим алгоритмом сравнения двух строк по их звучанию является Soundex (сокращение от Sound index). Он устанавливает одинаковый код для строк, имеющих схожее звучание в английском языке. Изначально Soundex был использован Национальным управлением архивами США в 1930-х годах для ретроспективного анализа переписей населения за период с 1890 по 1920 годов.
Авторами алгоритмами являются Роберт Рассел (Robert C. Russel) и Маргарет Кинг Оделл (Margaret King Odell), которые запатентовали его в 20-х годах прошлого столетия. Сам алгоритм приобрел популярность во второй половине прошлого века когда стал темой нескольких статей в научно-популярных журналах США и был опубликован в монографии Д.Кнута «Искусство программирования».
Daitch-Mokotoff Soundex
Так как Soundex подходит только для английского языка, некоторые исследователи делали попытки модифицировать его. В 1985 году Гари Мокотофф (Gary Mokotoff) и Рэнди Дэйч (Randy Daitch) предложили вариант алгоритма Soundex, предназначенный сопоставления восточно-европейских (в том числе русских) фамилий с достаточно высоким качеством.
Metaphone
В 90-х годах Лоуренс Филипс (Lawrence Philips) предложил альтернативный вариант алгоритма Soundex, который получил название Metaphone. Новый алгоритм использовал больший набор правил английского произношения за счет чего был более точен. Позднее алгоритм был модифицирован с целью использования в других языках на основании транскрипции с помощью букв латинского алфавита.
Русский Metaphone
В 2002 году в 8-ом выпуске журнала «Программист» была опубликована статья Петра Каньковски, рассказывающая о его адаптации английской версии алгоритма Metaphone. Эта версия алгоритма преобразует исходные слова в соответствии с правилами и нормами русского языка, учитывая фонетическое звучание безударных гласных и возможные «слияния» согласных при произношении.
Вместо заключения
В результате нескольких итераций командой проекта по разработке программного продукта, о котором говорилось во введении, было выработано архитектурное решение, схема которого представлена на рисунке.
Текстовые описания пациентов принимаются через REST- сервис и сохраняются в хранилище (БД карточек) без каких-либо изменений. Так как наша система работает с медицинскими данными, то для обмена информацией был выбран стандарт FHIR (Fast Healthcare Interoperability Resources). Информация о поступившей карточке пациента передается в очередь сообщений для дальнейшего анализа и принятия решения об установлении связи.
Первым карточку обрабатывает «Быстрый анализатор» работающий по детерминированному алгоритму. Если все правила детерминированного алгоритма отработали, то он создает в отдельном хранилище (БД связей) запись со ссылкой на обрабатываемую карточку. Запись содержит кроме идентификатора проанализированной карточки, дату установления связи и условный идентификатор, определяющий глобально-идентифицированного пациента. На указанный глобальный идентификатор в дальнейшем ссылаются и другие карточки, формируя тем самым массив, описывающий конкретное физическое лицо.
Если детерминированный алгоритм не нашел соответствия, то информация о карточке через очередь сообщений передается «Полному анализатору».
Полный анализатор реализует смешанный алгоритм сравнения (вероятностный и детермиированный). Работа полного анализатора состоит ряда последовательных этапов. В некотором упрощении этапы можно представить так:
Этап 1. Подбор карточек-кандидатов
На этом этапе с помощью фонетических алгоритмов из БД карточек отбираются те, в которых обнаружены сходные по звучанию имена. Массив отобранных карточек после нормализации передается на обработку этапа 2.
Этап 2. Анализ имен
С помощью алгоритма Джаро-Винклера определяется вероятность указания в сравниваемых карточках имен, относящихся к одному и тому же физическому лицу (пациенту).
Этап 3. Анализ идентификаторов
Далее анализируется совпадение других атрибутов записи о пациенте, таких как номера паспорта, полиса ОМС (обязательного медицинского страхования) и СНИЛС, а также пол и дата рождения.
Этап 4. Итоговая оценка схожести
На заключительном шаге суммируются баллы, полученные в ходе анализа на каждом из этапов. Итоговое значение сравнивается с полученными эмпирическим путем граничными значениями. Если сумма баллов оказалась выше границы связывания, то в хранилище связей создается запись, аналогично логике работы быстрого анализатора. Если сумма баллов оказалась ниже границы связывания, но выше границы, однозначно определяющей различие карточек, то анализируемая карточка передается на визуальную оценку оператору системы.
