=Paper=
{{Paper
|id=None
|storemode=property
|title=Автоматическое связывание документов
(Automatic Document Linking)
|pdfUrl=https://ceur-ws.org/Vol-934/paper46.pdf
|volume=Vol-934
|dblpUrl=https://dblp.org/rec/conf/rcdl/KnyazevaTK12
}}
==Автоматическое связывание документов
(Automatic Document Linking)
==
https://ceur-ws.org/Vol-934/paper46.pdf
Автоматическое связывание документов
c А.А. Князева
⃝ c И.Ю. Турчановский
⃝ c О.С. Колобов
⃝
Томский филиал Институт сильноточной
Института вычислительных технологий СО РАН электроники СО РАН
Томск Томск
aknjazeva@ict.nsc.ru tur@hcei.tsc.ru okolobov@hcei.tsc.ru
Аннотация В более общей формулировке задача связы-
вания может быть поставлена для документов
В работе рассматривается задача ав- разных типов, имеющих различную структуру.
томатического связывания документов, В то же время, задача связывания документов
относящихся к одному и тому же одного типа, то есть выявления дублирующихся
объекту реального мира. Предлагается документов в одном или нескольких источниках
алгоритм, основанный на классификации является частным случаем рассматриваемой за-
с использованием расстояния Махалан- дачи. Разумеется, при этом речь идет о нечетких
обиса. Работа алгоритма иллюстрируется дубликатах, поскольку нередки ситуации, когда
на примере связывания библиографиче- дублирующиеся документы имеют различные
ских записей и авторитетных записей значения в одном или нескольких полях [4].
имен авторов в формате машиночитаемой Причинами такого несоответствия могут быть
каталогизационной записи (MARC). опечатки, перестановки слов и символов, про-
пуски данных, а также привычки и традиции
каталогизаторов.
1 Введение Безусловно, самым простым подходом к
задаче связывания является принятие решения
В рамках работы рассматривается задача восста- о соответствии записей на основе некоторых
новления отсутствующих или утраченных связей правил. Эти правила могут быть относительно
между документами в контексте библиотечных простыми или достаточно сложными, в зависи-
данных. В качестве документа может выступать мости от конкретной системы. Такой подход к
как запись из электронного каталога библиотеки, установлению связей можно назвать детермини-
так и полнотекстовый документ с внедренными стическим. Однако на практике далеко не всегда
метаданными. Главное требование к документу - есть возможность выработать исчерпывающий
он должен содержать информацию о свойствах набор правил, особенно в условиях, когда часть
объекта в виде набора атрибутов с определенной информации отсутствует.
структурой. В качестве примера работы алго-
ритма в данной работе приводятся результаты
2 Связанные работы
эксперимента по связыванию библиографических
записей и авторитетных записей имен авторов. Впервые задача автоматического связывания
Тем не менее, подход является достаточно общим без применения фиксированных правил была
и может быть перенесен на связывание полнотек- сформулирована Ньюкомби [14] в контексте
стовых документов с авторитетными записями. сопоставления записей о рождениях с запися-
Под связыванием документов в рамках работы ми о регистрации брака. Суть предложенного
понимают сравнение информации из различных решения заключается в подсчете количества сов-
источников данных с целью определения, какие павших полей. Если это количество превышает
пары документов представляют один и тот же некоторый заданный заранее порог, то записи
объект реального мира [4, 17]. Таким объектом признаются соответствующими, в противном слу-
может быть, например, некоторый документ, чае - несоответствующими. В дальнейшем для
автор или организация. Эта задача также идей Ньюкомби была разработана формальная
известна под названием связывания записей, математическая модель, получившая название
идентификации сущностей и т.п. вероятностной модели связывания Fellegi-Sunter
(FS) [5], на которой в настоящее время осно-
Труды 14-й Всероссийской научной конференции
«Электронные библиотеки: перспективные методы и
вано целое семейство вероятностных моделей,
технологии, электронные коллекции» — RCDL-2012, например, модели основанные на штрафах или
Переславль-Залесский, Россия, 15–18 октября 2012 г. использующие EM-алгоритм [4]. Описанный
299
подход основан на явной оценке условных веро- решаемой задачи можно отнести то, что они не
ятностей соответствия записей, он предполагает поддерживают данные сложной структуры, тре-
знание распределения признаков соответствия буют установления правил связывания в явном
или их взаимную независимость [1]. виде или принятия предположений о функции
Альтернативой является более прямой под- распределения признаков и их взаимной неза-
ход, основанный на методиках машинного висимости, которые часто не выполняются на
обучения [2]. Это может быть обучение с учите- практике.
лем или без него. Основная идея заключается в Группу систем, работающих с библиогра-
том, чтобы относить пару документов к классу фическими данными, в свою очередь можно
соответствующих или несоответствующих пар на разделить на две части: системы для «просто-
основании ее схожести с остальными парами го» формата библиографической ссылки (такого
класса. Применение такого подхода не требу- как BiBTEX или неструктурированная библио-
ет независимости признаков, что существенно графическая запись) и системы для работы
расширяет область применения. с «профессиональными» форматами (семейство
Диапазон существующих систем связывания MARC-форматов). Первая группа систем вынуж-
документов достаточно широк: техники для дена больше внимания уделять такой частной
установления RDF-ссылок в Веб, базы данных задаче, как автоматическая разметка неразме-
с адресами клиентов и организаций, системы ченного текста (чтобы выделять из текстовой
для связывания демографической и медицинской строки элементы библиографического описания).
информации о персонах и др. Во второй группе такая необходимость отпадает
В отдельную группу можно выделить методы, благодаря сложной структуре формата, но в то
предназначенные для связывания данных в же время появляется необходимость учета этой
Веб с помощью установления RDF-ссылок, структуры, в которой одна и та же информация
реализованные, напримерм в системе Silk [8]. может быть внесена по-разному, в зависимости
Хотя в основе таких методик лежат те же от предпочтений каталогизаторов. К первой
общие предположения, что и во всех системах группе можно отнести системы DIFWICS [7] и
связывания, специфичность области применения MARLIN [2], а ко второй проект VIAF [16].
не позволяет непосредственно использовать Однако, хотя в проекте VIAF и реализована
данные системы для решения рассматриваемой работа с данными в MARC-формате, он не пред-
задачи. лагает механизма для автоматической оценки
Наиболее многочисленной является группа весов признаков, поскольку основан на использо-
систем, настроенная на поиск дубликатов в вании эмпирических правил. Кроме того, проект
одном или нескольких текстовых файлах (либо нацелен на поск дублирующихся записей, а не
в реляционых БД), содержащих сведения об связывание записей различных типов. Таким
именах, почтовых адресах, телефонах, номерах образом, несмотря на некоторое сходство, не
страховки и т.п. Чаще всего, для принятия представляется возможным заимствовать подход,
решения о соответствии записей используется использованный в проекте VIAF для решения
набор правил или классическая вероятностная поставленной задачи.
модель F-S. В первом случае система предо-
ставляет пользователю возможность определения
того, насколько важно совпадение по тому
3 Модель системы связывания
или иному признаку. На практике это может
Для процедуры связывания необходимо опреде-
быть достаточно трудно сделать, поскольку не
лить несколько основных моментов.
всегда в распоряжении пользователя есть такая
Так, необходимо задать правила для опре-
информация. Во втором случае вес того или
деления того, достаточно ли информации для
иного признака вычисляется автоматически, на
связывания содержится в записи. Кроме того,
основании функции правдоподобия (например,
необходимо определить правила для нормализа-
система AutoMatch [10]). При этом принима-
ции данных, которые бы позволили стандартизи-
ется предположение о функции распределения
ровать значения (например, с помощью словаря
признаков, а также их взаимной независимости.
допустимых значений).
Также, многие системы предлагают использова-
Далее следует предусмотреть варианты сокра-
ние одного из описанных механизмов на выбор
щения перебора при поиске записей-кандидатов
пользователя (Febrl [3], FRIL [11] и другие).
для связывания, поскольку в крупных хра-
Системы этой группы отличаются друг от
нилищах затраты на подробный анализ всех
друга гибкостью настройки, инструментами для
возможных пар записей могут быть неприемлимо
нормализации данных и сравнения отдельных
большими.
полей, возможностями визуалицации и т.п. К
Еще одним важным моментом является выбор
недостаткам систем этой группы с точки зрения
способа для сравнения значений на уровне
300
полей. Даже при проведении нормализации, возникающих из-за сокращений, перестановки
использование строгого сравнения может быть слов и т.п.
необоснованным. Зачастую необходимо оценить Существует множество подходов к нормали-
степень соответствия полей записей, чтобы зации данных. Это может быть использование
учесть и частичное соответствие информации. конечного словаря для значений поля, автомати-
Когда оценивается степень подобия между ческая разметка текста на естественном языке
записями, состоящими из множества полей, для определения о каком объекте идет речь и
возникает необходимость комбинировать оценки т.п.
подобия для отдельных полей. Поскольку В данной работе рассматриваются записи
соответствие между общим подобием записей в формате RUSMARC, созданные профессио-
и подобием в отдельных полям может сильно нальными каталогизаторами, поэтому в блоке
варьироваться, то необходимо взвешивать поля нормализации производится только проверка
и каким-либо образом оценивать вклад каждого записи на соответствие профилю.
из них в соответствие на уровне записи [2].
Перечисленные задачи, реализованные в 3.2 Составление пар
большинстве систем связывания [4], можно
рассматривать как этапы процедуры связывания: Сравнение входящего документа с каждым
из авторитетных документов, может оказаться
1. Нормализация; необоснованно трудоемким процессом. В частно-
2. Составление пар; сти, при работе «на лету» может потребоваться
сократить количество авторитетных документов,
3. Сравнение отдельных полей в парах которые будут сопоставляться с входящим. Су-
записей; ществует множество способов ограничить круг
4. Вынесение решения о соответствии. записей для сопоставления. Приведем некоторые
из них.
Кроме данных четырех этапов, непосредственно
участвующих в процедуре связывания, необхо- 1. Метод стандартных блоков выделяет записи
димо наличие еще двух: настройка системы в один блок в том случае, если они
и проверка качества связывания. Последние содержат идентичный блочный ключ [9].
два включаются в работу периодически при Блочные ключи формируются на основе
расширении базы данных. Принцип работы у атрибутов записей, например, первые 4
них общий: для записи, относительно которой символа фамилии. Кроме того, блочный
уже известно правильное решение (с какой ключ может быть и составным, например,
из авторитетных записей ее нужно связать) атрибут «индекс» может сочетаться с
проводится процедура связывания и в первом атрибутом «возраст». Ключи должны быть
случае уточняются параметры системы, а во выбраны таким образом, чтобы блоки не
втором оценивается, насколько успешно система были ни слишком большими, ни слишком
справилась с задачей. мелкими.
Рассмотрим подробнее описанные выше эта-
пы. 2. Метод ближайших соседей [6] сортирует
записи на основе сортирующего ключа
и затем двигает окно фиксированного
3.1 Нормализация
размера ω последовательно по всем запи-
Блок нормализации решает две задачи: проверка сям. Записи внутри окна составляют пары
записи на соответствие профилю и анализ ее друг с другом и включаются в список
отдельных полей. Проверка на соответствие пар-кандидатов. Использование окна огра-
профилю позволяет определить достаточно ли ничивает число возможных сравнений для
информации, содержащейся в записи, для свя- каждой записи до 2ω − 1. Метод может
зывания. Анализ отдельных полей предназначен некорректно работать в том случае, если
для очистки и нормализации данных. количество записей с одним значением
На практике большинство коллекций данных ключа превышает размер окна, поскольку в
содержат засоренную, неполную, неправильно такой ситуации будут сравниваться не все
форматированную информацию. Очистка данных нужные записи.
и их нормализация - необходимые этапы 3. Метод Bigram-индексирования [3] предна-
подготовки данных перед их загрузкой в значен для нечеткого разбиения на блоки.
хранилище и использованием для дальнейшего Основная идея заключается в том, что
анализа. Особенно важно решение этих задач значения блочных ключей конвертируются
в распределенных системах. Цель нормализации в лист биграм (подстрок, состоящих из
данных - избавиться от вариаций в написании, двух символов) и затем из этих биграм
301
формируются списки на основе заданного различно записанные слова, символьные меры
порога (например, выбираются все записи, предпочтительнее, поскольку они могут оценить
в которых встречается 80% биграм). разницу между строками более детально [2].
Далее методы можно классифицировать по
В рамках данной работы принят метод поиска тому, как вычисляются их параметры, например
по составному ключу, состоящему из двух «стоимость» операции редактирования или вес
значений: фамилия и инициалы автора. Значение токена. Параметры могут быть фиксированными,
ключа определяется по входящему документу, а вручную подобранными исследователем (кон-
поиск производится в авторитетной базе данных. текстно-независимые методы), вычисленными на
При этом используется точное сопоставление. основе характеристик БД или полученными
Такой механизм позволяет существенно сни- в результате обучения с учителем (контекст-
зить трудоемкость без использования сложных но-зависимые). В случае, если используются
вычислений. контекстно-зависимые методы, включающие обу-
Одной из важных черт предлагаемого подхода, чение с учителем, необходимо определить
является использование расширенного автори- обучающую выборку.
тетного документа для сравнения с входящим Результаты сопоставления строк также могут
документом, аналогичный подход используется в варьироваться от одного метода к другому,
проекте VIAF [16]. Расширенная авторитетная они могут быть записаны в виде бинарных,
запись кроме самой найденной авторитетной категориальных, порядковых или непрерывных
записи включает информацию из библиографи- величин.
ческих записей, уже хранящахся в системе Например, классический метод Левенштей-
и связанных с ней. Такой подход позволяет на [12], определяющий расстояние как мини-
увеличить объем информации, задействованной мальное число вставок, удалений или замен,
в анализе, и получать более точные результаты. необходимых для перевода одной строки в
другую, относится к символьным методам с
3.3 Сравнение отдельных полей в парах фиксированными параметрами (следовательно,
записей контекстно-независимый) и непрерывной пере-
менной результата.
Цель блока сравнения отдельных полей за- В рамках настоящей работы использовалась
ключается в оценке того, насколько записи комбинация точного сравнения и сравнения с
совпадают по различным параметрам. Результа- выделением основы слова по методу Snowball [15]
том работы блока является вектор, составленный для русского языка. Такой выбор был обусловлен
из оценок близости двух строк, которые яв- тем, что механизм стеммирования уже был
ляются значениями соответствующих полей. реализован на момент разработки алгоритма.
Существует огромное разнообразие методов со-
поставления строк, учитывающих различные
3.4 Вынесение решения для каждой из пар
аспекты сходства. Множество методов можно
классифицировать в соответствии с тем, на чем Соответствие на уровне записей необязательно
они базируются, как определяются их параметры означает однозначное соответствие на уровне
и в каком виде представляются результаты полей.
сопоставления. Блок вынесения решения призван провести
В основе метода сопоставления строк могут анализ сравнительного вектора, полученного для
быть символы (как отдельные символы, так и пары документов (авторитетного и библиографи-
q-граммы, наборы подстрок длины q) или токены. ческого) и принять одно из двух возможных
В качестве примеров методов, базирующихся на решений: соответствуют или не соответствуют
токенах, можно привести Метрику Джаккарда эти записи друг другу.
или косинусную меру сходства в векторном Методы, используемые для решения задачи
пространстве. Методы, работающие с набором связывания документов разделяются на две об-
подстрок определенной длины позволяют срав- ширные категории. Детерминистические методы
нивать не целые слова, а комбинации в них, в которых устанавливаются часто очень сложные
что может быть полезно при наличии орфогра- правила и вероятностные методы, в которых
фических ошибок. Символьные метрики, такие для классификации пар документов использу-
как расстояние Левенштейна и его различные ются статистические модели [3]. Вероятностные
варианты, вычисляют подобие между строками, методы могут быть в свою очередь разделе-
оценивая минимальное количество изменений, ны на методы, основанные на классической
которые достаточны для перевода одной строки вероятностной теории связывания [5], и бо-
в другую. В случае, когда данные представле- лее поздние подходы, использующие различные
ны относительно короткими строками, которые техники машинного обучения [2].
содержат одинаковые, хотя и орфографически
302
Основное отличие классической модели от коррелированность признаков и инвариантно к
методик машинного обучения заключается в масштабу. Учет коррелированности позволяет
том, что она основана на предположении того, отказаться от предположения о взаимной незави-
что сравнительный вектор является случайным симости переменных, которое часто принимается
вектором, чья функция плотности различается при классификации, и работать с зависимыми
для каждого из двух классов (совпадающих признаками. В рамках решаемой задачи это яв-
и несовпадающих пар документов). При этом ляется важным моментом, поскольку некоторые
предполагается, что классы этих плотностей из- переменные достаточно сильно коррелированны.
вестны заранее и их параметры можно оценить. Квадрат расстояния Махаланобиса между
Затем, задача сводится к вычислению вероятно- двумя точками X и Y, определенными в
сти принадлежности сравнительного вектора к p-мерном пространстве можно записать в виде:
каждому из классов при условии его конкретной
реализации и выбора наиболее вероятного клас-
са. Использование этого подход осложняется D2 (X, Y ) = (X − Y )C −1 (X − Y )T , (1)
тем, что на практике, как правило, классы
плотностей заранее неизвестны. где X и Y - векторы координат размерности
Альтернативный подход заключается в ис- p;
пользовании методик машинного обучения, поз- C −1 - матрица, обратная ковариационной
воляющих не делать предположений о функциях матрице.
плотности соответствующих и несоответствую- Заменив один или оба вектора в формуле (1)
щих пар, а классифицировать пару документов на вектор координат центроида первого класса
на основе ее подобия одному из классов. µ1 или второго µ2 , получим расстояние от точки
Такой подход возможен, например, если выбрать до класса или расстояние между классами.
некоторый центроид класса, а затем вычислить На практике оценить расстояние Махаланобиса
расстояние до центроидов обоих классов и можно подставив соответствующие оценки сред-
выбрать наименьшее. них значений и матрицы ковариации. В качестве
Рассмотрим три подхода к построению оценки матрицы ковариации в формуле (1)
решающей функции [4]. будем использовать внутригрупповую матрицу
ковариации W, элементы которой находится по
1. Индукционная модель связывания записей: формуле:
в основе лежит машинное обучение с
учителем, предполагаем, что есть обуча- g nk
1 XX
ющая выборка, в которой для каждого Wij = (Xikm − Xik. )(Xjkm − Xjk. ),
n. − 2
образца точно известен класс. Эта выборка k=1 m=1
используется для построения классифика- (2)
тора, приванного относить любой новый где
образец к определенному классу. g - число классов;
nk - число наблюдений в k-м классе;
2. Кластерная модель связывания записей —
n. - общее число наблюдений по всем
это модель обучения без учителя, она
классам;
не требует обучающей выборки. Принцип
Xikm - величина переменной i для m-го
таков: разбиваем все пары на три кла-
наблюдения в k-м классе;
стера с помощью некоторого алгоритма
Xik. - средняя величина переменной i в k-м
кластеризации, затем определяем какой
классе.
кластер относится к какому статусу: со-
Воспользовавшись расстоянием Махалоноби-
ответствие, несоответствие или возможное
са можно произвести отбор наиболее ин-
соответствие.
формативных признаков (то есть признаков,
3. Гибридная модель. На первом шаге ис- позволяющих наиболее четко разделить классы),
пользуя кластерную модель для анализа а также спрогнозировать принадлежность к клас-
некоторого количества пар, затем эти па- су для новых наблюдений (вычислив расстояния
ры становятся обучающей выборкой для до обоих классов и выбрав наиболее близкий
применения обучения с учителем. класс).
В рамках данной работы используется
индукционная модель. Классификация пары до- 4 Описание эксперимента
кументов к классу соответствующих, либо к
классу несоответствующих пар производится с При проведении эксперимента ставилась цель
помощью расстояния Махалонибиса [13], вы- проанализировать пригодность предлагаемого ал-
бранного благодаря тому, что оно учитывает горитма для решения задачи автоматического
303
связывания библиографических записей с ав- 00161/Н340-682478
700 1$a Шилов $b Б. В.$gБорис
торитетными записями имен авторов. Данные
Владимирович$cцитолог$f19710323
для эксперимента были предоставлены НП
$3AShilov\_BoriB2003100663480700
МедАрт [18]. 701 1 $aИванов$bВ. В. $gВладимир
Эксперимент проводился на системе, включа- Владимирович $cбиохимик $f19530130
ющей: $3AIvanovVladV2004042963480700
$pкафедра биохимии и молекулярной
1. Библиографическую базу данных (ББД), биологии СГМУ
около 300 000 записей в формате 701 1 $aКазанский $bВ. Е.
RUSMARC; 71202 $aСибирский медицинский
университет $cТомск
2. Авторитетный файл имен авторов (АФА),
около 10 000 записей в формате RUSMARC
AUTHORITY. Рис. 2: Фрагмент библиографической записи
На основе АФА был составлен список
фамилий с инициалами, соответствующих сразу 4.1 Факторы
двум и более авторитетным записям (42 фамилии
Рассмотрим подробнее переменные, по которым
с инициалами). Для каждой из фамилий были
осуществляется связывание записей (таблица 1).
составлены пары из авторитетной записи (АЗ) и
Результирующая переменная out отвечает
библиографической записи (БЗ), всего 1215 пар.
за принадлежность библиографической записи
Полученное множество было случайным образом
данному автору (другими словами за принад-
разделено на обучающую и тестовую выборки.
лежность наблюдения к одной из двух групп).
Кроме наличия однофамильцев к авто-
Остальные переменные в нашем эксперименте
ритетным записям предъявлялось требование
являются факторными и указывают на степень
полноты: наличие информации о дате рождения,
соответствия информации о годах жизни автора,
географических и профессиональных дополне-
ний, аннотации (наличие полей 001, 200 ($a,
$b, $c, $f, $y), 830$a).
В рамках эксперимента намеренно игнориро- Таблица 1: Основная группа переменных
валась информация о расшифровке инициалов
(200 $g) для увеличения области совпаде- Переменная Сравнение АЗ БЗ
ния авторитетных и библиографических записей out точное 001 701$3
и, следовательно, объема обучающей выборки. (соответствие) совпадение
Разумеется, рабочий алгоритм не будет игнори- birth совпадение
ровать эту информацию, что позволит повысить (дата с точностью 200$f 701$f
его точность. рождения) до года
В свою очередь, библиографическая запись death совпадение
обязательно должна была содержать указание (дата с точностью 200$f 701$f
на авторитетную запись (наличие поля 701$3) смерти) до года
для того, чтобы можно было ответить на вопрос addition совпадение 200$c 701$c
о ее принадлежности. В рамках эксперимента (профес- усеченных
требование полноты к БЗ не предъявлялось, сиональное форм
хотя очевидно, отсутствие информации сразу по дополнение)
нескольким переменным существенно повышает place1 совпадение 200$y 712$c
вероятность ошибки. (географи- усеченных
ческое) форм
001 AIvanovVladV2004042963480700 place2 вхождение 200$y 712$a
200 1$a Иванов $b В. В. $c биохимия (географи- усеченных
$f 19530130 $g Владимир Владимирович $y Томск ческое) форм
830 $a Образование: в 1975 г. окончил work 1 совпадение 830$a 701$p
Томский университет, биолого-почвенный (место усеченных
факультет, аспирантуру в Томском медицинском работы) форм
институте. work2 вхождение 830$a 712$a
$a Ученая степень: в 1975 г. защитил (место усеченных
кандидатскую диссертацию. Кандидат
работы
биологических наук.
коллектива) форм
Рис. 1: Фрагмент авторитетной записи
304
переменные нельзя назвать независимыми. В
Таблица 2: Расширенная группа: соавторы по случае, когда не указаны соавторы, например,
фамилии все три переменные coauthor1, coauthor2 и
coauthor3 будут равны 2. Выбор наиболее
Переменная Поля для
значимых переменных обсуждается ниже.
сравнения БЗ
Вычисляя значения перечисленных перемен-
и расширен-
ных для записей, приведенных в примере, а
ной АЗ
затем проделав аналогичное сравнение для всех
coauthor1
пар из обучающей выборки, получим исход-
(количество найденных
ные данные эксперимента, фрагмент которых
фамилий соавторов)
приведен в таблице 3.
coauthor2
(доля найденных 701$a,
фамилий соавторов) 702$a Таблица 3: Фрагмент исходных данных
coauthor3
(макс. число out Факторные переменные
общих БЗ среди addition birth death place1 ...
указанных фамилий) 2 3 3 2 1 ...
2 1 3 2 2 ...
1 1 1 2 2 ...
профессиональной деятельности, географическом
положении и т.п. Факторные переменные можно Введение переменной place2 было основано
разделить на две группы. Значения перемен- на том факте, что в библиографических записях
ных основной группы вычисляются на основе при заполнении поля 712$a иногда в скобках
непосредственного сравнения библиографической указывают место расположения организации,
записи с авторитетной. Расширенная группа кроме того, в названиях некоторых органи-
использует расширенную авторитетную запись, заций содержится указание на географическое
которая строится следующим образом: находятся положение (например, можно найти подстроку
все библиографические записи, уже связанные «Томск» в названии «Томский государственный
с авторитетной записью и оценивается степень университет»). Переменная work1 отвечает за
их подобия рассматриваемой библиографической указание места работы автора в аннотации. В
записи. Такой подход позволяет существенно данном случае 701$p = «кафедра биохимии
расширить объем библиографических записей, и молекулярной биологии СГМУ», тогда как
которые можно связать с соответствующими 830$a содержит подстроку «кафедры биохимии
авторитетными, поскольку информация по пере- и молекулярной биологии Сибирского медицин-
менным основной группы часто отсутствует в ского университета». Сопоставить эти строки
библиографических записях. С другой стороны, можно, если использовать словари. Если словарь
подход не дает никакого выигрыша в случае, сокращений не привлекать, то получим значение
когда с авторитетной записью не связано ни work1 равное 1, хотя очевидно, что налицо
одной библиографической. совпадение информации. В то же время пара
В расширенной группе переменных анализи- записей относится к классу соответствующих и
руется информация по соавторам и предметным переменная out принимает значение 2.
рубрикам, указанным в библиографической за-
писи. При этом разделение на авторов и
соавторов условное: автором будем называть 4.2 Предварительный анализ
персону, указанную в авторитетной записи (для Факторные переменные, используемые в работе,
которой производится связывание), а соавторами не подчиняются нормальному распределению,
все остальные персоны, независимо от того, как что исключает применение параметрических
они указаны в библиографических записях. критериев. Для проверки гипотезы значимости
В таблице 2 приведены три переменные, различия двух групп использовался ранговый
расчитываемые для соавторов по фамилии, коэффициент корреляции τ Кендалла [19].
аналогично обрабатываются соавторы по кодам Переменные, для которых принималась гипотеза
(группа переменных coauthorId поля 701$3, об отсутствии различий (при уровне значимости
702$3), предметные рубрики по наименованиям 0,01), исключались из работы.
(переменные subject поле 606$a), предметные Как видно из таблицы 4, переменную place2,
рубрики по кодам (переменные subjectId поле уровень значимости для которой больше 0,01,
606$3). Всего в расширенной группе вычисляется можно исключить из рассмотрения.
12 переменных. Следует отметить, что эти
305
Таблица 4: Анализ переменных Таблица 5: Первый этап ранжирования фактор-
ных переменных
Переменная τ p-value Корреляция
Шаг Переменная Расстояние
addition 0,428 <2,2*10−16 значима отбора между
birth 0,868 <2,2*10−16 значима классами
death 0,296 <2,2*10−16 значима D2 (µ1 |µ2 )
place1 0,257 <2,2*10−16 значима шаг 1 addition 19,63
place2 0,041 0,149 незначима (выбрана coauthor1 20,77
work1 0,094 1,1*10−3 мало значима birth) coauthor2 * 21,39
work2 0,137 1,4*10−6 мало значима coauthor3 20,27
coauthor1 0,587 <2,2*10−16 значима coauthorId1 20,06
coauthor2 0,595 <2,2*10−16 значима coauthorId2 20,85
coauthor3 0,588 <2,2*10−16 значима coauthorId3 19,77
coauthorId1 0,513 <2,2*10−16 значима death 19,44
coauthorId2 0,513 <2,2*10−16 значима place1 19,31
subject1 20,51
coauthorId3 0,508 <2,2*10−16 значима
subject2 20,58
subject1 0,408 <2,2*10−16 значима
subject3 19,63
subject2 0,489 <2,2*10−16 значима
subjectId1 20,57
subject3 0,417 <2,2*10−16 значима
subjectId2 20,47
subjectId1 0,405 <2,2*10−16 значима
subjectId3 19,51
subjectId2 0,41 <2,2*10−16 значима
work1 19,32
subjectId3 0,405 <2,2*10−16 значима
work2 19,35
4.3 Отбор факторных переменных Таблица 6: Результат ранжирования переменных
Воспользовавшись расстоянием Махалонобиса
Место Переменная Место Переменная
можно произвести отбор наиболее информатив-
ных признаков. Для этого на каждом шаге 1 birth 10 place1
отбираем по одной переменной, дающей наи- 2 coauthor2 11 coauthor1
большее расстояние между центроидами классов 3 subjectId1 12 coauthorId1
в сочетании с уже выбранными (таблица 5). 4 coauthorId2 13 coauthorId3
В качестве первой включаемой переменной 5 death 14 subject2
выберем birth, дающую наибольший коэффици- 6 addition 15 coauthor3
ент корреляции с результирующей переменной 7 subjectId2 16 work2
out. Так, на первом шаге в дополнение к birth 8 work1 17 subject3
будет выбрана переменная coauthor2 (отмечена 9 subject1 18 subjectId3
*), а на втором переменные birth, coauthor2,
subjectId1, и так далее. Чем раньше включаются
переменные - тем больше информации в них
вана с уже включенными переменными.
содержится.
В результате процедуры отбора был получен
список факторных переменных в порядке их 4.4 Проверка качества дискриминации
значимости для дискриминации, приведенной в С помощью расстояния Махаланобиса можно
таблице 6. Пользуясь этой информацией можно прогнозировать принадлежность наблюдения к
исключить наименее информативные переменные одной из групп. Для этого достаточно рассчитать
и сократить время работы алгоритма. расстояния до центроидов обоих классов, подста-
Следует отметить, что ранжирование учиты- вив в формулу (1) координаты этого наблюдения,
вает не только вклад отдельной переменной, но координаты центроида класса и матрицу внутри-
и ее взаимодействие с остальными, это дости- групповой ковариации, рассчитанную по формуле
гается за счет учета корреляции в расстоянии (2). После чего следует выбрать в качестве
Махаланобиса. Таким образом, на каждом этапе прогноза тот класс, расстояние до которого
включение менее информативной, но при этом наименьшее.
менее коррелированной переменной может ока- Проведя расчеты для тестовой выборки,
заться полезнее включения более информативной наблюдения которой не использовались при
переменной, если она слишком тесно коррелиро- вычислении параметров алгоритма, получим так
306
называемую матрицу классификации, на основе библиографических записей. На практике это
которой можно рассчитать долю правильно клас- приводит к попытке найти соответствующую
сифицированных объектов и оценить точность авторитетную запись даже и для той биб-
прогноза. лиографической, которая содержит недостаточно
Поскольку количество ошибок в тестовой информации. Поэтому к алгоритму предъявляет-
выборке зависит от того, какие именно пары ся требование возможности работы в условиях
попали в нее, было проведено 100 прогонов с частично пропущенных данных. Требования
разными выборками. Средний процент ошибок полноты библиографической записи можно ва-
составил 2,36%. рьировать в зависимости от степени надежности
принятия решения, которой требуется достичь.
В целом можно утверждать, что предлагаемый
5 Заключение алгоритм способен улучшить качество данных
библиотеки за счет установления недостающих
В данной статье представлен алгоритм автома-
связей между библиографическими записями,
тического авторитетного контроля, позволяющий
полнотекстовыми документами и авторитетными
делать заключение о связи библиографической
документами. При дальнейшей разработке алго-
и авторитетной записей без участия человека;
ритма планируется подключить дополнительные
а также процедура статистического анализа
методы сопоставления строк, улучшить анализ
признаков и отбора наиболее информативных из
соответствия по предметным рубрикам, а также
них. Подход, описанный в работе, является до-
дополнить блок нормализации специальными
статочно общим и не накладывает ограничений
словарями, отсутствующими на данный момент
на используемые переменные и информацию,
в библиотечной системе.
которую они отражают.
Важной особенностью предлагаемого подхода
является возможность обучения на конкретных Список литературы
данных. С одной стороны, это является
ограничением, поскольку такие данные не всегда [1] Belin T. R., and Rubin D. B. (1995), "A
доступны. С другой стороны, возможность method for Calibrating False-Match Rates
обучения позволяет настроить алгоритм на in Record Linkage Journal of the American
работу с базой данных и, тем самым, учесть ее Statistical Association, 90, 694-707.
особенности.
[2] Bilenko M. Learning to Combine Trained
Информацию, на основе которой производится
Distance Metrics for Duplicate Detection in
связывание, можно разделить на основную (годы
Databases / M. Bilenko, R. Mooney.
жизни, профессиональное дополнение, место ра-
Technical Report AI-02-296, Artificial
боты) и косвенную (наименование коллективного
Intelligence Lab, University of Texas
автора, географическая отметка, информация о
at Austin, 2002.
соавторах и тематических рубриках). При этом
не требуется взаимной независимости признаков, [3] Christen P., Churches T. Febrl: Freely
по которым производится сравнение, а также до- extensible biomedical record linkage
пускается возможность отсутствия информации Manual, release 0.2.2 edition, November
в части полей. Еще одна особенность подхо- 2003.
да заключается в использовании расширенных [4] Elfeky M. G., Elmagarmid A. K.,
авторитетных записей, позволяющих увеличить Verykios V. S. "TAILOR: A Record
объем информации для сравнения. Конечно, Linkage Tool Box". In Proceedings of
информация, привлеченная из библиографиче- the 18th International Conference on Data
ских записей, уже связанных с расматриваемой Engineering (ICDE 02). IEEE Computer
авторитетной, является косвенной и потому Society, Washington, DC, USA, 17 - 28,
необходимо тщательно анализировать ее с точки 2002.
зрения достаточности для принятия решений.
[5] Fellegi I. P., Sunter A. B. A theory for
Однако с другой стороны, «основная» информа-
record linkage. Journal of the American
ция, такая как годы жизни, профессиональное
Statistical Association, 64: 1183-1210, 1969.
дополнение и место работы автора, часто
отсутствует в библиографической записи. В ре- [6] Hernandez M. A., Stolfo S. J. Real-world
зультате необходимо делать выбор: использовать data is dirty: data cleansing and the
косвенную информацию или отказываться от merge/purge problem. Journal of Data
связывания вовсе. Mining and Knowledge Discovery, 1(2),
Как уже упоминалось, к авторитетным запи- 1998.
сям в рамках работы предъявляются достаточно [7] Hylton J. A. Identifying and merging
жесткие требования полноты, в отличие от related bibliographic records. M. S. thesis,
307
MIT, 1996. Published as MIT Laboratory Library of Congress Name Authority Files
for Computer Science Technical Report 678. / Bennett, Rick, Christal Hengel-Dittrich,
[8] Isele R., Jentzsch A., Bizer C., & Volz J. Edward T. O’Neill, and Barbara Tillett //
(2010). Silk - A Link Discovery Framework International Cataloging and Bibliographic
for the Web of Data, User manual and link Control. 2007. V.36,1. P. 12-19.
language specification 2.0. Language. [17] Winkler W. E. Overview of Record
[9] Jaro M. A. Advances in Record Linkage Linkage and Current Research Directions.
Methodology as Applied to Matching the Research Report Series, RRS: Statistics
1985 Census of Tampa, Florida. Journal of #2006-2. http://www.census.gov/
the American Statistical Society, 84(406): srd/papers/pdf/rrs2006-02.pdf.
414-420, 1989. [18] Мешечак Н. А. Web-справочник «Медики
[10] Jaro M. A. Probabilistic linkage of large России» [Электронный ресурс] / Н. А.
public health data files // Statistics in Мешечак, О. С. Колобов, Ф. Е. Татарский
Medicine 1995; 14: P. 491-498. // Информационные технологии, компью-
терные системы и издательская продукция
[11] Jurczyk P., Lu J., Xiong L., Cragan для библиотек: материалы конф. LIBCOM-
J., Adolfo Correa, FRIL: A Tool for 2007. - Электрон. текстовые дан. - М.
Comparative Record Linkage, American : ГПНТБ России, 2007. – 1 электрон.
Medical Informatics associations (AMIA) опт. диск (CD-ROM). – Загл. с этикетки
2008 annual Symposium. диска. – ISBN 978-5-85638-120-6. - гос.
[12] Levenshtein V. I. Binary codes capable of регистрации 0320702219.
correcting insertions and reversals. Soviet [19] Закс Л. Статистическое оценивание. Пер.
Physics Doclady, 10(8): 707-710, Feb. 1966. с нем. В.Н. Варыгина. Под ред. Ю.П.
[13] Mahalanobis P. C. (1936). «On Адлера, В.Г. Горского. М.: Статистика,
the generalised distance in statistics». 1976. – 599 с.: ил.
Proceedings of the National Institute of
Sciences of India 2 (1): 49-55. Automatic document linking
Anna Knyazeva, Igor Turchanovsky, Oleg Kolobov
[14] Newcombe H. B., Kennedy J. M., Axford
S. J., and James A. P. Automatic linkage of The problem of automatic linking of documents
vital records. Science, 130:954-959, 1959. relating to the same real world object is
[15] Сайт: Russian stemming algorithm considered. An algorithm based on classification
http://snowball.tartarus.org/ using the Mahalanobis distance is proposed.
algorithms/russian/stemmer.html The algorithm is illustrated by linking between
bibliographic and authority records of author
[16] VIAF (Virtual International Authority File):
names in Machine-Readable Cataloging format
Linking the Deutsche Nationalbibliothek and
(MARC).
308