Разработка программного комплекса для связывания RDF-наборов из различных источников данных
|
Введение 3
2. Основные модели и технологии разработки программного комплекса 20
2.1 Набор решаемых задач 20
2.2 Архитектура системы 20
2.2.1. Модуль переноса базы данных 22
2.2.2. Модуль корректировки структуры базы данных 22
2.2.3. Модуль добавления записей из Google Scholar 23
2.2.4. Модуль транслитерации поля авторов в базе данных 24
2.2.5. Модуль генерации RDF-набора из локальной базы данных 24
2.2.6. Модуль запуска ё2г-сервера 25
2.2.7. Модуль запуска системы связывания LIMES с настраиваемыми
параметрами 26
2.3 Модель данных 26
2.3.1. Структура внешнего набора данных 26
2.3.2. Структура локальной базы данных 27
2.4. Программная среда разработки 29
2.5. Описание структуры приложения 32
2.5.1. Форма Main Window 33
2.5.1.1. Метод Convert_accdb_to_MySQL 33
2.5.1.2. Метод startLimes 35
2.5.2. Форма SplitDescription 36
2.5.3. Класс AddBooks_googleScholar 37
2.5.4. Класс Transliteration 38
2.5.5. Класс D2R_Job 38
2.5.5.1. Метод d2rqGenerateMapping 38
2.5.5.2. Метод d2rqStartserver 38
2.5.8. Форма Stats 39
2.6. Оценка реализации программной системы 40
3. Эксперименты по связыванию и анализ результатов 41
4. Заключение 43
Список требований для запуска приложения 44
Литература 45
Приложение 1. Таблица правил транслитерации 47
Приложение 2. Метод переноса базы данных в MySQL 49
Приложение 3. Метод добавления записей из Google Scholar
2. Основные модели и технологии разработки программного комплекса 20
2.1 Набор решаемых задач 20
2.2 Архитектура системы 20
2.2.1. Модуль переноса базы данных 22
2.2.2. Модуль корректировки структуры базы данных 22
2.2.3. Модуль добавления записей из Google Scholar 23
2.2.4. Модуль транслитерации поля авторов в базе данных 24
2.2.5. Модуль генерации RDF-набора из локальной базы данных 24
2.2.6. Модуль запуска ё2г-сервера 25
2.2.7. Модуль запуска системы связывания LIMES с настраиваемыми
параметрами 26
2.3 Модель данных 26
2.3.1. Структура внешнего набора данных 26
2.3.2. Структура локальной базы данных 27
2.4. Программная среда разработки 29
2.5. Описание структуры приложения 32
2.5.1. Форма Main Window 33
2.5.1.1. Метод Convert_accdb_to_MySQL 33
2.5.1.2. Метод startLimes 35
2.5.2. Форма SplitDescription 36
2.5.3. Класс AddBooks_googleScholar 37
2.5.4. Класс Transliteration 38
2.5.5. Класс D2R_Job 38
2.5.5.1. Метод d2rqGenerateMapping 38
2.5.5.2. Метод d2rqStartserver 38
2.5.8. Форма Stats 39
2.6. Оценка реализации программной системы 40
3. Эксперименты по связыванию и анализ результатов 41
4. Заключение 43
Список требований для запуска приложения 44
Литература 45
Приложение 1. Таблица правил транслитерации 47
Приложение 2. Метод переноса базы данных в MySQL 49
Приложение 3. Метод добавления записей из Google Scholar
Linked Data [1] - метод представления структурированных данных таким образом, чтобы они могли быть связаны и были более удобными для доступа через семантические запросы. Linked Data построена на стандартах Web- технологий, таких, как URIs, RDF и XML, но ориентирует их не на удобство пользователя, а на автоматическое чтение данных компьютерами. Это позволяет связывать данные с разных источников и обращаться к ним. Модель RDF - это принятый W3C формат данных, используемый для представления отдельных сущностей, представляющих собой самостоятельную единицу знаний. Сущности связаны друг с другом с помощью предикатов по шаблону «субъект - предикат - объект». Данные для открытых хранилищ в основном извлекаются из реляционных баз данных или в частичном виде из веб-страниц и текстовых документов. Ссылки между сущностями образуют глобальный граф данных, используемый поисковыми роботами и браузерами для перемещения по источникам данных. Linked Data состоит из следующих компонентов:
URIs, причем его конкретной разновидности - Dereferencable URIs [2], которая позволяет получить копию или представление ресурса, который она представляет;
HTTP URIs, используемые для удаленного доступа к данным;
Структурированные данные, соответствующие форматам, описанным в Resource Description Framework (“Среда описания ресурса”). Например, RDFa, RDF/XML, N3, Turtle или JSON-LD.
Linked Data Platform, позволяющая RESTful HTTP сервисам получать доступ, создавать, и удалять RDF-ресурсы.
Проект Linked Open Data - одна из самых заметных по результатам реализаций принципов Linked Data. На 2011 год проект насчитывал 31 миллиард RDF-триплетов, с 504 миллиардами RDF-связей.
На темы, близкие к Linked Data, написано достаточное количество статей, но хотелось бы остановиться на некоторых из них. Стоит упомянуть статью под названием «А Survey of Current Link Discovery Frameworks», под авторством четырех сотрудников Лейпцигского университета (Markus Nentwig, Michael Hartung, Axel-Cyrille Ngonga Ngomo, Erhard Rahm). [3]
В ней сообщается о том, что связи между сущностями — это основа структурированности облака Linked Data. Авторы статьи решили рассмотреть проблему недостатка связей между источниками данных, хранящихся в облаке Linked Data. Исследования показывают, что 44% от всех наборов данных в этом облаке вообще не связаны друг с другом. [4,5] Такая проблема существует, потому что создание связей между данными - это очень трудоемкий процесс, если он выполняется вручную. Это особенно заметно на больших наборах данных, к примеру, создание связей между DBPedia (4.5 миллиона записей) и LinkedGeoData (больше 1 миллиона записей), заняло бы несколько десятилетий, если бы проверка связи между двумя отдельно взятыми записями занимала всего 1 миллисекунду.
Авторы сообщают, что на данный момент разработано несколько программных средств и фреймворков, позволяющих находить семантически идентичные объекты в различных наборах данных. Большинство таких решений стараются свести задачу установления связей к задаче установления идентичности. Формально задача описывается в следующем виде: «Пусть даны два набора данных S и Т, задача состоит в автоматическом поиске пар ресурсов в декартовом произведении (S, Т), которые являются связаны друг с другом в соответствии с отношением owksameAs». Когда установление связей производится таким образом, возникают две проблемы: достижение высокой точности и скорости выполнения. Высокая точность требует нахождения почти всех связей между двумя источниками без попадания неверных ссылок. Из этого вытекает проблема скорости выполнения задачи, потому что просто сравнивание каждого элемента из S с каждым элементов из Т дает сложность O(|S| • |Т|).
Разработка алгоритмов и сопутствующие задачи описаны в других книгах и исследованиях, но это исследование концентрируется на изучении уже существующих средств для нахождения связей между наборами данных. При оценке использовался следующий набор критериев:
Эффективность. Средство для связывания данных должно генерировать высококачественные мэппинги и создавать как можно больше связей, чтобы обеспечить целостность структуры. Но при этом связи должны быть образованы только между сущностями, действительно связанными друг с другом. Эта цель может быть достигнута как простыми методами (сравнение строк), так и сложными (с учетом семантической близости ресурсов или с использованием уже доступных ссылок. [6, 7]
Существующие системы связывания данных состоят из нескольких этапов Самые распространенная схема выполнения приведена на Рисунке 1.
Входные данные процесса включают в себя два набора данных, которые должны быть связаны: источник (Source) и цель (Target). Кроме них, системе требуются параметры конфигурации (Configuration parameters). Входные данные могут быть в виде RDF/OWL дампа или получаться через SPARQL-точку доступа. Связывание может быть ограничено по какому-то подмножеству исходного набора, например, объектами одного класса. Конфигурация может быть либо полной спецификацией ссылок или некоторыми из параметров, например, допущение схожести. Обучающие данные - ещё один вид конфигурации, необходимый для связывания, основанного на обучении. Кроме того, средства могут использовать дополнительные источники данных, такие как словари и ранее созданные мэппинги. Выходные данные состоят из набора найденных связей или ссылок, который представляет собой ни что иное, как мэппинг между исходным и целевым источником данных.
Обычно рабочий процесс имеет три основные стадии: предобработка, нахождение связей и постобработка. Предобработка выполняет две важные задачи: завершает спецификацию ссылок и улучшение эффективности работы. Предобработка также может проводить подготовительные шаги по трансформации и чистке входных данных.
Далее в статье приведено описание четырёх основных этапов рабочего процесса: конфигурация системы, оптимизация скорости выполнения, нахождение соответствий и постобработка.
Конфигурация системы. Связывание данных обычно происходит на основе схожести ресурсов по одному или нескольким критериям. Каждый критерий основан на особой мере соответствия или функции соответствия и сравнивает либо определённые поля, либо семантический контекст ресурса. Например, два фильма могут быть связаны друг с другом на основе схожести их названий, годами их выпуска или набора актёров, принимающих участие в них. Определение спецификации ссылок подразумевает определение элементов, которые будут использоваться при сравнении, алгоритмов сравнения и способ вывода комбинированного решения о связывании на основе отдельных сходств. Разные сходства могут быть объединены по одному или комбинации из следующих подходов: численный подход, подход, основанный на правилах и подход, зависящий от рабочего процесса. Численный подход обрабатывает различные сходные значения, например, генерирует числовые параметры из других типов данных и сравнивает эти параметры с учётом некоторого допущения. Подход, основанный на правилах использует так называемые правила совпадения для определения соответствия двух ресурсов. Такие правила определяют комбинацию условий, например, триграммное совпадение по названию > 0.9 и одинаковые годы выпуска. Подход, зависящий от рабочего процесса менее общий и подразумевает итеративное определение решения. Например, на первом шагу система вычисляет сходство строк для выбранного свойства, а затем применяет более дорогую меру сравнения по контексту только для пар ресурсов с высоким уровнем сходства по первому критерию. [9] Ручное указание спецификации ссылок — сложный процесс, который во многих случаях труден даже для специалистов. Адаптивные подходы анализируют характеристики входных данных для достижения частично автоматической установки спецификации для конфигурации системы. Кроме приведённых выше способов существует также подход, основанный на обучении. Обычно такие подходы требуют предварительного указания пар ресурсов, точно состоящих и точно не состоящих в связи, для проведения обучения системы. Этот этап требует участия человека, но некоторые системы используют активное обучение, при котором участие человека требуется только время от времени на парах ресурсов, для которых система не может принять чёткое решение об установке связи. Кроме того, системы с обучением могут работать без участия человека, но для них все равны нужны некоторые параметры.
Оптимизация работы программы. Основной способ оптимизировать работу системы в ходе предобработки - это уменьшение объёмов поиска. Это обычно достигается с помощью двух взаимодополняющих методов: блокировка и фильтрация. Блокировка разбивает наборы данных на несколько блоков так, чтобы поиск ссылок производился только внутри одного блока. Существуют несколько подходов с пересекающимися и непересекающимися подмножествами. Кроме того, могут быть применены множественные ключи блокировки, чтобы разделить входные данные в соответствии с несколькими параметрами, чтобы вероятность нахождения всех ссылок была увеличена. Фильтрация обеспечивает учёт конфигурации ссылок, такие как мера идентичности и допущение идентичности, чтобы отфильтровать пары записей, которые не удовлетворяют условиям идентичности. Например, если использовать меры сравнения, основанные на токенах, то фильтрация позволяет включить в сравнение только строки с одинаковой длины и с одинаковым количеством токенов.
Подходы к сравнению. Основная часть процесса поиска связей применяет спецификацию ссылок и вычисляет указанные меры сравнения на парах ресурсов, представленных методом блокировки и/или фильтрации, которые должны быть определены. Средство для связывания данных обычно имеет библиотеку со встроенными техниками сравнения. Такие техники можно разделить на два типа: элементные, которые производят сравнение по какому-то конкретному полю в объектах, и контекстные, учитывающие контекст объекта. Элементные техники самые распространенные и могут быть основаны на мерах сравнения для строк, чисел или особых типов данных, вроде географических координат. Вычисление схожести может также использовать различные виды сторонних знаний, такие как словари и т.д. Контекстные и структурные техники более сложные и нацелены на поиск схожести между объектами по схожести их контекстов. Существует большой набор техник, зависящих от того, какой контекст имеет выбранный объект. Например, некоторые техники используют так называемые якорные ссылки между похожими объектами, чтобы итеративно найти совпадающие объекты в наборах их близких объектов. Еще одним подходом к установлению соответствий является подход, использующий уже установленные связи для поиска новых связей. Используя свойство транзитивности отношения эквивалентности, можно на основе нескольких ссылок типа owksameAs найти новые ссылки. Открытые репозитории ссылок вроде BioPortal или LinkLion поддерживают публикацию ссылок и также их повторное использование для выявления новых ссылок.
Постобработка. На последней стадии результаты работы модуля по нахождению связей должны быть объединены и из ссылок-кандидатов должны быть выбраны ссылки, удовлетворяющие спецификации ссылок. Результирующие ссылки могут быть упорядочены и перегруппированы, чтобы избежать ошибок, таких как нарушение онтологических или каких- либо других ограничений.
Далее в работе приведено функциональное сравнение одиннадцати систем для связывания данных, основанных на требованиях и основной схеме работы, приведенной на Схеме 1 и подробно описанной ранее. Выбор систем был основан на следующих критериях: участие в OAEI IM (Ontology Alignment Evaluation Initiative Instance Matching) с хорошими результатами либо наличие подхода с обучением и опубликованные результаты вычислений.
Как видно из таблицы, семь систем участвовали в OAEI IM. Оставшиеся четыре системы (Silk, LIMES, KnoFuss и RuleMiner) поддерживают подход, основанный на обучении для определения спецификации ссылок. Следующий критерий показывает, что четыре из семи систем, участвовавших в OAEI IM, кроме стандартного сравнения объектов, имеют еще и поддержку поиска с учетом онтологии. На самом деле, эти системы (RiMOM, AgreementMaker, LogMap и CODI) в начале поддерживали поиск по онтологиям и только потом добавляли поддержку сравнения объектов. Для более подробного сравнения систем использованы основные свойства для вышеупомянутых групп из семи и четырех программ. Поддерживаемые входные форматы. Девять из одиннадцати средств поддерживают входные наборы данных в формате RDF, оставшиеся два (AgreementMaker, SERIMI) могут получать данные на вход только через SPARQL-точку доступа. Хотя такие точки доступа и поддерживают гибкий и динамичный доступ к данным, они могут вызвать проблемы с проблемы с доступом и производительностью. В дополнение к RDF, CODI, LogMap и RiMOM поддерживают входные файлы в формате OWL. Доступ к SPARQL- точкам доступа также есть в основанных на обучении системах Silk, LIMES и KnoFuss. Динамический доступ через SPARQL-точки обычно осуществляется с ограничением по какому-то типу данных (например, книги, поселения), чтобы ограничить объем данных и пространство поиска ссылок. Хотя все средства неспециализированы и могут успешно работать с данными любых тем, некоторые из систем использовались для общих web-данных, например, для поддержки вопросно-ответных задач путем совмещения Linked Data и web-данных.
Удивительно, но большое число рассматриваемых систем не опираются на внешние фоновые знания, такие как словари или уже известные ссылки и мэппинги (кроме использования выбранных ссылок для определения спецификации ссылок). Это является полной противоположностью поиску с учетом онтологий, где все системы используют словари вроде WordNet в качестве фоновых знаний. Системы RiMOM, AgreementMaker и LogMap используют такие словари, но не для связывания сущностей. Возможной причиной является то, что существует недостаточно ресурсов с поддержкой ссылок на уровне объектов. Только Zhishi.links использовала созданный вручную список синонимов, в основном для того, чтобы расшифровывать аббревиатуры, такие как (Corp. - Corporation), (NY - New York).
Silk, LIMES и RuleMiner поддерживают обучение под контролем человека. Silk и LIMES поддерживают генетическое программирование с активным обучением. RuleMiner использует итеративный кластерный подход, который максимизирует функцию схожести, предполагая, что мэппинг ресурсов из источника и цели близок к соответствию 1:1. Генетическое программирование начинается с набора случайных ссылочных спецификаций и использует эволюционные принципы выбора и вариации, чтобы развить эти спецификации пока состояние связности не достигнет какого-то критерия (функция совпадения) или не будет достигнуто определенное количество итераций. Для обучения под контролем система использует заранее известные совпадения в генетическом алгоритме, чтобы найти спецификацию, которая хорошо подходит под обучающие данные. Автоматическое обучение нацелено на уменьшение затрат на предоставление обучающих данных и поэтому применяет интерактивное именование автоматически выбранных ссылок-кандидатов. Такие ссылки-кандидаты выбираются таким образом, чтобы оптимизировать какой-либо критерий, например, корреляцию между именованными и неименованными ссылками. KnoFuss и LIMES также внедряют неконтролируемое обучение спецификации компоновки. Данные подходы также используют генетическое программирование, но стараются многократно оптимизировать меры (степени), которые определяют непрямые критерии качеств, такие как высокие значения схожести и близость к отображению 1:1 (при условии источников данных без дубликатов (копий)). В KnoFuss потенциальные (возможные) спецификации компоновки агрегируют взвешенные значения сходства для нескольких строковых вычислителей и требуют, чтобы агрегированное (общее) значение подобия превышало определенный порог. Таким образом, в этом подходе необходимо выбрать совпадения, определить их вес, статистическую функцию (например, среднюю или максимальную) и порог подобия.
Оптимизация работы программы.
Одной из немногих систем, применяющих полноценную блокировку для уменьшения объемов поиска, является Silk. Они поддерживают ручную спецификацию множественных ключей блокировки, то есть только сущности, имеющие одинаковый ключ из списка ключей блокировки, должны быть сравнены между собой. Для реализации этой стратегии применяется многомерный индекс. Неявная блокировка достигается путем предварительного выбора входной спецификации для выполнения, но это не позволяет быть уверенным в уменьшении объемов поиска, так как объектов одного класса может быть много.
Основным подходом для улучшения работы программы является фильтрация. Эта техника оптимизации обычно специализируется на конкретном свойстве сравниваемых объектов и методе сравнения. Например, основанная на сравнении токенов мера Жаккара подразумевает наличие одинаковых токенов в сравниваемых строках. Поэтому пары, не имеющие общих токенов, могут быть исключены из сравнения. Обратный индекс позволяет быстро определить, какие объекты должны быть сравнены. LIMES применяет идею фильтрации для метрических пространств, используя аксиому треугольника для исключения сущностей из сравнения. Более новые алгоритмы, включенные в LIMES, используют разбиение по пробелам, чтобы улучшить время работы техник, основанных на мерах Минковски.
После рассмотрения всех характеристик систем связывания данных, можно
сделать вывод, что для связывания простых по структуре источников данных лучше всего подходит система LIMES. Можно перечислить причины выбора именно этой системы:
1) Поддержка разнообразных форматов данных (RDF, SPARQL, CSV)
2) Разнообразие поддерживаемых типов ссылок (owksameAs, определенные пользователем)
3) Широкий выбор типов конфигурации (от ручной до автоматической настройки)
4) Наличие консольной версии приложения (удобно для встраивания) Суммируя обзор проекта Linked Open Data и обзор систем для связывания данных, можно поставить вопрос - насколько данные, созданные или обработанные нашим университетом, структурированы и связаны с ними? Ответить на этот вопрос поможет проведение работы по выявлению связей между одной из университетских баз данных и одним из наборов данных Linking Open Data, имеющим сходную тематику.
Чтобы выбрать набор данных, схожий по структуре с университетской базой данных, был произведен анализ статей о структуре Linked Open Data [4,5]. В результате поисков был обнаружен набор данных, содержащий библиографические описания публикаций по компьютерной лингвистике (в университетской базе данных хранятся данные такого же вида) под названием DBLP Computer Science Bibliography.
URIs, причем его конкретной разновидности - Dereferencable URIs [2], которая позволяет получить копию или представление ресурса, который она представляет;
HTTP URIs, используемые для удаленного доступа к данным;
Структурированные данные, соответствующие форматам, описанным в Resource Description Framework (“Среда описания ресурса”). Например, RDFa, RDF/XML, N3, Turtle или JSON-LD.
Linked Data Platform, позволяющая RESTful HTTP сервисам получать доступ, создавать, и удалять RDF-ресурсы.
Проект Linked Open Data - одна из самых заметных по результатам реализаций принципов Linked Data. На 2011 год проект насчитывал 31 миллиард RDF-триплетов, с 504 миллиардами RDF-связей.
На темы, близкие к Linked Data, написано достаточное количество статей, но хотелось бы остановиться на некоторых из них. Стоит упомянуть статью под названием «А Survey of Current Link Discovery Frameworks», под авторством четырех сотрудников Лейпцигского университета (Markus Nentwig, Michael Hartung, Axel-Cyrille Ngonga Ngomo, Erhard Rahm). [3]
В ней сообщается о том, что связи между сущностями — это основа структурированности облака Linked Data. Авторы статьи решили рассмотреть проблему недостатка связей между источниками данных, хранящихся в облаке Linked Data. Исследования показывают, что 44% от всех наборов данных в этом облаке вообще не связаны друг с другом. [4,5] Такая проблема существует, потому что создание связей между данными - это очень трудоемкий процесс, если он выполняется вручную. Это особенно заметно на больших наборах данных, к примеру, создание связей между DBPedia (4.5 миллиона записей) и LinkedGeoData (больше 1 миллиона записей), заняло бы несколько десятилетий, если бы проверка связи между двумя отдельно взятыми записями занимала всего 1 миллисекунду.
Авторы сообщают, что на данный момент разработано несколько программных средств и фреймворков, позволяющих находить семантически идентичные объекты в различных наборах данных. Большинство таких решений стараются свести задачу установления связей к задаче установления идентичности. Формально задача описывается в следующем виде: «Пусть даны два набора данных S и Т, задача состоит в автоматическом поиске пар ресурсов в декартовом произведении (S, Т), которые являются связаны друг с другом в соответствии с отношением owksameAs». Когда установление связей производится таким образом, возникают две проблемы: достижение высокой точности и скорости выполнения. Высокая точность требует нахождения почти всех связей между двумя источниками без попадания неверных ссылок. Из этого вытекает проблема скорости выполнения задачи, потому что просто сравнивание каждого элемента из S с каждым элементов из Т дает сложность O(|S| • |Т|).
Разработка алгоритмов и сопутствующие задачи описаны в других книгах и исследованиях, но это исследование концентрируется на изучении уже существующих средств для нахождения связей между наборами данных. При оценке использовался следующий набор критериев:
Эффективность. Средство для связывания данных должно генерировать высококачественные мэппинги и создавать как можно больше связей, чтобы обеспечить целостность структуры. Но при этом связи должны быть образованы только между сущностями, действительно связанными друг с другом. Эта цель может быть достигнута как простыми методами (сравнение строк), так и сложными (с учетом семантической близости ресурсов или с использованием уже доступных ссылок. [6, 7]
Существующие системы связывания данных состоят из нескольких этапов Самые распространенная схема выполнения приведена на Рисунке 1.
Входные данные процесса включают в себя два набора данных, которые должны быть связаны: источник (Source) и цель (Target). Кроме них, системе требуются параметры конфигурации (Configuration parameters). Входные данные могут быть в виде RDF/OWL дампа или получаться через SPARQL-точку доступа. Связывание может быть ограничено по какому-то подмножеству исходного набора, например, объектами одного класса. Конфигурация может быть либо полной спецификацией ссылок или некоторыми из параметров, например, допущение схожести. Обучающие данные - ещё один вид конфигурации, необходимый для связывания, основанного на обучении. Кроме того, средства могут использовать дополнительные источники данных, такие как словари и ранее созданные мэппинги. Выходные данные состоят из набора найденных связей или ссылок, который представляет собой ни что иное, как мэппинг между исходным и целевым источником данных.
Обычно рабочий процесс имеет три основные стадии: предобработка, нахождение связей и постобработка. Предобработка выполняет две важные задачи: завершает спецификацию ссылок и улучшение эффективности работы. Предобработка также может проводить подготовительные шаги по трансформации и чистке входных данных.
Далее в статье приведено описание четырёх основных этапов рабочего процесса: конфигурация системы, оптимизация скорости выполнения, нахождение соответствий и постобработка.
Конфигурация системы. Связывание данных обычно происходит на основе схожести ресурсов по одному или нескольким критериям. Каждый критерий основан на особой мере соответствия или функции соответствия и сравнивает либо определённые поля, либо семантический контекст ресурса. Например, два фильма могут быть связаны друг с другом на основе схожести их названий, годами их выпуска или набора актёров, принимающих участие в них. Определение спецификации ссылок подразумевает определение элементов, которые будут использоваться при сравнении, алгоритмов сравнения и способ вывода комбинированного решения о связывании на основе отдельных сходств. Разные сходства могут быть объединены по одному или комбинации из следующих подходов: численный подход, подход, основанный на правилах и подход, зависящий от рабочего процесса. Численный подход обрабатывает различные сходные значения, например, генерирует числовые параметры из других типов данных и сравнивает эти параметры с учётом некоторого допущения. Подход, основанный на правилах использует так называемые правила совпадения для определения соответствия двух ресурсов. Такие правила определяют комбинацию условий, например, триграммное совпадение по названию > 0.9 и одинаковые годы выпуска. Подход, зависящий от рабочего процесса менее общий и подразумевает итеративное определение решения. Например, на первом шагу система вычисляет сходство строк для выбранного свойства, а затем применяет более дорогую меру сравнения по контексту только для пар ресурсов с высоким уровнем сходства по первому критерию. [9] Ручное указание спецификации ссылок — сложный процесс, который во многих случаях труден даже для специалистов. Адаптивные подходы анализируют характеристики входных данных для достижения частично автоматической установки спецификации для конфигурации системы. Кроме приведённых выше способов существует также подход, основанный на обучении. Обычно такие подходы требуют предварительного указания пар ресурсов, точно состоящих и точно не состоящих в связи, для проведения обучения системы. Этот этап требует участия человека, но некоторые системы используют активное обучение, при котором участие человека требуется только время от времени на парах ресурсов, для которых система не может принять чёткое решение об установке связи. Кроме того, системы с обучением могут работать без участия человека, но для них все равны нужны некоторые параметры.
Оптимизация работы программы. Основной способ оптимизировать работу системы в ходе предобработки - это уменьшение объёмов поиска. Это обычно достигается с помощью двух взаимодополняющих методов: блокировка и фильтрация. Блокировка разбивает наборы данных на несколько блоков так, чтобы поиск ссылок производился только внутри одного блока. Существуют несколько подходов с пересекающимися и непересекающимися подмножествами. Кроме того, могут быть применены множественные ключи блокировки, чтобы разделить входные данные в соответствии с несколькими параметрами, чтобы вероятность нахождения всех ссылок была увеличена. Фильтрация обеспечивает учёт конфигурации ссылок, такие как мера идентичности и допущение идентичности, чтобы отфильтровать пары записей, которые не удовлетворяют условиям идентичности. Например, если использовать меры сравнения, основанные на токенах, то фильтрация позволяет включить в сравнение только строки с одинаковой длины и с одинаковым количеством токенов.
Подходы к сравнению. Основная часть процесса поиска связей применяет спецификацию ссылок и вычисляет указанные меры сравнения на парах ресурсов, представленных методом блокировки и/или фильтрации, которые должны быть определены. Средство для связывания данных обычно имеет библиотеку со встроенными техниками сравнения. Такие техники можно разделить на два типа: элементные, которые производят сравнение по какому-то конкретному полю в объектах, и контекстные, учитывающие контекст объекта. Элементные техники самые распространенные и могут быть основаны на мерах сравнения для строк, чисел или особых типов данных, вроде географических координат. Вычисление схожести может также использовать различные виды сторонних знаний, такие как словари и т.д. Контекстные и структурные техники более сложные и нацелены на поиск схожести между объектами по схожести их контекстов. Существует большой набор техник, зависящих от того, какой контекст имеет выбранный объект. Например, некоторые техники используют так называемые якорные ссылки между похожими объектами, чтобы итеративно найти совпадающие объекты в наборах их близких объектов. Еще одним подходом к установлению соответствий является подход, использующий уже установленные связи для поиска новых связей. Используя свойство транзитивности отношения эквивалентности, можно на основе нескольких ссылок типа owksameAs найти новые ссылки. Открытые репозитории ссылок вроде BioPortal или LinkLion поддерживают публикацию ссылок и также их повторное использование для выявления новых ссылок.
Постобработка. На последней стадии результаты работы модуля по нахождению связей должны быть объединены и из ссылок-кандидатов должны быть выбраны ссылки, удовлетворяющие спецификации ссылок. Результирующие ссылки могут быть упорядочены и перегруппированы, чтобы избежать ошибок, таких как нарушение онтологических или каких- либо других ограничений.
Далее в работе приведено функциональное сравнение одиннадцати систем для связывания данных, основанных на требованиях и основной схеме работы, приведенной на Схеме 1 и подробно описанной ранее. Выбор систем был основан на следующих критериях: участие в OAEI IM (Ontology Alignment Evaluation Initiative Instance Matching) с хорошими результатами либо наличие подхода с обучением и опубликованные результаты вычислений.
Как видно из таблицы, семь систем участвовали в OAEI IM. Оставшиеся четыре системы (Silk, LIMES, KnoFuss и RuleMiner) поддерживают подход, основанный на обучении для определения спецификации ссылок. Следующий критерий показывает, что четыре из семи систем, участвовавших в OAEI IM, кроме стандартного сравнения объектов, имеют еще и поддержку поиска с учетом онтологии. На самом деле, эти системы (RiMOM, AgreementMaker, LogMap и CODI) в начале поддерживали поиск по онтологиям и только потом добавляли поддержку сравнения объектов. Для более подробного сравнения систем использованы основные свойства для вышеупомянутых групп из семи и четырех программ. Поддерживаемые входные форматы. Девять из одиннадцати средств поддерживают входные наборы данных в формате RDF, оставшиеся два (AgreementMaker, SERIMI) могут получать данные на вход только через SPARQL-точку доступа. Хотя такие точки доступа и поддерживают гибкий и динамичный доступ к данным, они могут вызвать проблемы с проблемы с доступом и производительностью. В дополнение к RDF, CODI, LogMap и RiMOM поддерживают входные файлы в формате OWL. Доступ к SPARQL- точкам доступа также есть в основанных на обучении системах Silk, LIMES и KnoFuss. Динамический доступ через SPARQL-точки обычно осуществляется с ограничением по какому-то типу данных (например, книги, поселения), чтобы ограничить объем данных и пространство поиска ссылок. Хотя все средства неспециализированы и могут успешно работать с данными любых тем, некоторые из систем использовались для общих web-данных, например, для поддержки вопросно-ответных задач путем совмещения Linked Data и web-данных.
Удивительно, но большое число рассматриваемых систем не опираются на внешние фоновые знания, такие как словари или уже известные ссылки и мэппинги (кроме использования выбранных ссылок для определения спецификации ссылок). Это является полной противоположностью поиску с учетом онтологий, где все системы используют словари вроде WordNet в качестве фоновых знаний. Системы RiMOM, AgreementMaker и LogMap используют такие словари, но не для связывания сущностей. Возможной причиной является то, что существует недостаточно ресурсов с поддержкой ссылок на уровне объектов. Только Zhishi.links использовала созданный вручную список синонимов, в основном для того, чтобы расшифровывать аббревиатуры, такие как (Corp. - Corporation), (NY - New York).
Silk, LIMES и RuleMiner поддерживают обучение под контролем человека. Silk и LIMES поддерживают генетическое программирование с активным обучением. RuleMiner использует итеративный кластерный подход, который максимизирует функцию схожести, предполагая, что мэппинг ресурсов из источника и цели близок к соответствию 1:1. Генетическое программирование начинается с набора случайных ссылочных спецификаций и использует эволюционные принципы выбора и вариации, чтобы развить эти спецификации пока состояние связности не достигнет какого-то критерия (функция совпадения) или не будет достигнуто определенное количество итераций. Для обучения под контролем система использует заранее известные совпадения в генетическом алгоритме, чтобы найти спецификацию, которая хорошо подходит под обучающие данные. Автоматическое обучение нацелено на уменьшение затрат на предоставление обучающих данных и поэтому применяет интерактивное именование автоматически выбранных ссылок-кандидатов. Такие ссылки-кандидаты выбираются таким образом, чтобы оптимизировать какой-либо критерий, например, корреляцию между именованными и неименованными ссылками. KnoFuss и LIMES также внедряют неконтролируемое обучение спецификации компоновки. Данные подходы также используют генетическое программирование, но стараются многократно оптимизировать меры (степени), которые определяют непрямые критерии качеств, такие как высокие значения схожести и близость к отображению 1:1 (при условии источников данных без дубликатов (копий)). В KnoFuss потенциальные (возможные) спецификации компоновки агрегируют взвешенные значения сходства для нескольких строковых вычислителей и требуют, чтобы агрегированное (общее) значение подобия превышало определенный порог. Таким образом, в этом подходе необходимо выбрать совпадения, определить их вес, статистическую функцию (например, среднюю или максимальную) и порог подобия.
Оптимизация работы программы.
Одной из немногих систем, применяющих полноценную блокировку для уменьшения объемов поиска, является Silk. Они поддерживают ручную спецификацию множественных ключей блокировки, то есть только сущности, имеющие одинаковый ключ из списка ключей блокировки, должны быть сравнены между собой. Для реализации этой стратегии применяется многомерный индекс. Неявная блокировка достигается путем предварительного выбора входной спецификации для выполнения, но это не позволяет быть уверенным в уменьшении объемов поиска, так как объектов одного класса может быть много.
Основным подходом для улучшения работы программы является фильтрация. Эта техника оптимизации обычно специализируется на конкретном свойстве сравниваемых объектов и методе сравнения. Например, основанная на сравнении токенов мера Жаккара подразумевает наличие одинаковых токенов в сравниваемых строках. Поэтому пары, не имеющие общих токенов, могут быть исключены из сравнения. Обратный индекс позволяет быстро определить, какие объекты должны быть сравнены. LIMES применяет идею фильтрации для метрических пространств, используя аксиому треугольника для исключения сущностей из сравнения. Более новые алгоритмы, включенные в LIMES, используют разбиение по пробелам, чтобы улучшить время работы техник, основанных на мерах Минковски.
После рассмотрения всех характеристик систем связывания данных, можно
сделать вывод, что для связывания простых по структуре источников данных лучше всего подходит система LIMES. Можно перечислить причины выбора именно этой системы:
1) Поддержка разнообразных форматов данных (RDF, SPARQL, CSV)
2) Разнообразие поддерживаемых типов ссылок (owksameAs, определенные пользователем)
3) Широкий выбор типов конфигурации (от ручной до автоматической настройки)
4) Наличие консольной версии приложения (удобно для встраивания) Суммируя обзор проекта Linked Open Data и обзор систем для связывания данных, можно поставить вопрос - насколько данные, созданные или обработанные нашим университетом, структурированы и связаны с ними? Ответить на этот вопрос поможет проведение работы по выявлению связей между одной из университетских баз данных и одним из наборов данных Linking Open Data, имеющим сходную тематику.
Чтобы выбрать набор данных, схожий по структуре с университетской базой данных, был произведен анализ статей о структуре Linked Open Data [4,5]. В результате поисков был обнаружен набор данных, содержащий библиографические описания публикаций по компьютерной лингвистике (в университетской базе данных хранятся данные такого же вида) под названием DBLP Computer Science Bibliography.
В дипломной работе разработана система для удобной настройки и запуска связывания данных, реализующая предварительную подготовку локального набора данных путем корректировки структуры исходной базы данных и внедрение записей из Google Scholar. Также система организует доступ к данным в реляционной БД путем её представления в виде RDF-графа. После подготовки RDF-графа система позволяет произвести его связывание с произвольным набором данных.
Оригинальность работы состоит в том, что в ней реализована возможность в одном приложении выполнить полуавтоматическую настройку процесса связывания и отсутствие необходимости работы пользователя с командной строкой.
В ходе выполнения работы был проведен анализ структуры Linked Open Data Cloud, способ хранения данных в нем. Также были изучены вспомогательные технологии, необходимые для реализации приложения.
После определения основных преимуществ и недостатков реализованного приложения, были проведены эксперименты по проверке работоспособности приложения и улучшению степени связности наборов данных.
Результаты проведенных экспериментов говорят о том, что связанность выбранного набора данных с хранимым в Сети низок, и следует провести работы по публикации этих данных и распространении ссылки на этот источник данных.
С точки зрения развития информационной интегрированности нашего университета в Сеть, использование базы библиографических описаний корпусных данных на данный момент позволяет определить уровень этой интегрированности, и в будущем, опираясь на эти результаты, улучшить её.
Список требований для запуска приложения
Для успешного запуска приложения на персональном компьютере необходим только установленный в стандартном режиме MySQL-сервер. Все остальные программные продукты идут вместе с приложением
Оригинальность работы состоит в том, что в ней реализована возможность в одном приложении выполнить полуавтоматическую настройку процесса связывания и отсутствие необходимости работы пользователя с командной строкой.
В ходе выполнения работы был проведен анализ структуры Linked Open Data Cloud, способ хранения данных в нем. Также были изучены вспомогательные технологии, необходимые для реализации приложения.
После определения основных преимуществ и недостатков реализованного приложения, были проведены эксперименты по проверке работоспособности приложения и улучшению степени связности наборов данных.
Результаты проведенных экспериментов говорят о том, что связанность выбранного набора данных с хранимым в Сети низок, и следует провести работы по публикации этих данных и распространении ссылки на этот источник данных.
С точки зрения развития информационной интегрированности нашего университета в Сеть, использование базы библиографических описаний корпусных данных на данный момент позволяет определить уровень этой интегрированности, и в будущем, опираясь на эти результаты, улучшить её.
Список требований для запуска приложения
Для успешного запуска приложения на персональном компьютере необходим только установленный в стандартном режиме MySQL-сервер. Все остальные программные продукты идут вместе с приложением