Пользователь
0,0
рейтинг
16 ноября 2015 в 23:53

Разработка → Семантические технологии просто и доступно на примере родословных tutorial

Программа, способная к логическим выводам в рамках поставленной задачи, может казаться техническим чудом и воплощением Скайнета. Но, как можно убедиться ниже, на сегодняшний день создать такую программу на языке Python не составит труда, если использовать семантические технологии. Мы остановимся на наглядном примере онтологий — родословных — и для любого члена семьи в родословной сможем выводить его родственные отношения произвольной сложности (она ограничена вычислительными ресурсами). К примеру, на фамильном древе семьи Романовых ниже показан внучатый двоюродный племянник (first cousin twice removed) российского императора Петра II.

image

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

О триплетах, RDF и онтологиях можно прочесть в википедии или в других постах. Для описания семейных связей в родословных мы задействуем OWL 2 онтологию Family History Knowledge Base (FHKB). Заметим, что авторы FHKB хотя и признают своё детище хорошим учебным примером, всё же не рекомендуют OWL 2 к использованию в реальных генеалогических приложениях из-за вычислительной сложности для сегодняшних систем рассуждений. Наше же приложение останется учебным: мы ограничимся небольшими генеалогиями до ста членов семей.

Генеалогические данные обычно доступны в текстовом формате GEDCOM (.ged). Некоторые генеалогические порталы и программы по ведению родословных позволяют выгружать графы связей в этом формате. Мы прочитаем GEDCOM при помощи одноимённой библиотеки для языка Python и сгенерируем триплеты индивидуумов (так называемый ABox) для онтологии FHKB. Логика (TBox) для выведения родственных связей у нас уже имеется, и всё, что нам нужно сделать — это задать данные, к которым эта логика будет применяться.

Представим, что у нас есть данные для следующих трёх индивидуумов (абстрактно), на примере вышеупомянутой семьи русских царей:

Александр I *есть-брат* Николая I.
Николай I *есть-отец* Александра II.


и логика FHKB:

Свойство *есть-дядя* является последовательностью свойств *есть-брат* и *есть-отец*.


Тогда система рассуждений в состоянии установить следующий факт:

Александр I *есть-дядя* Александра II.


Эта же информация на RDF-наречии Turtle ниже. Оно компактно и довольно легко читается:

fhkb:i1 a owl:NamedIndividual ;
    fhkb:isBrotherOf fhkb:i2 ;
    rdfs:label "Александр I" .

fhkb:i2 a owl:NamedIndividual ;
    fhkb:isFatherOf fhkb:i3 ;
    rdfs:label "Николай I" .

fhkb:i3 a owl:NamedIndividual ;
    rdfs:label "Александр II" .

fhkb:isFatherOf a owl:ObjectProperty ;
    rdfs:label "есть-отец" .

fhkb:isBrotherOf a owl:ObjectProperty ;
    rdfs:label "есть-брат" .

fhkb:isUncleOf a owl:ObjectProperty ;
    owl:propertyChainAxiom ( fhkb:isBrotherOf fhkb:isFatherOf ) ;
    rdfs:label "есть-дядя" .


(Примечание: здесь опущены некоторые детали для наглядности. В оригинальной FHKB свойства isFatherOf, isBrotherOf и isUncleOf определены несколько иначе для оптимизации логических рассуждений.)

Итак, мы задали индивидуумов i1, i2 и i3, свойства isFatherOf и isBrotherOf, назначили эти свойства индивидуумам и ввели новое свойство isUncleOf. Обратим внимание на префиксы rdfs:, owl: и fhkb: — они показывают задействованные области знаний. Префикс rdfs: указывает на стандартную схему RDF (в примере выше это свойство label). Префикс owl: указывает на стандартные онтологические термины (индивидуум, свойство, последовательность свойств и т.д.). А префикс fhkb: — это используемая нами генеалогическая онтология FHKB, где определена логика родственных связей (isFatherOf, isBrotherOf, isUncleOf, а также другие термины, isGrandfatherOf, isFirstCousinOf и т.д.).

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

image

Итак, логическая база (TBox) доступна в Turtle-файле header.ttl из репозитория для этой статьи. Генеалогия царской семьи Романовых в GEDCOM тоже присутствует, но читателю рекомендуется взять свою для интереса. А вот и скрипт, который сгенерирует индивидуумов для онтологии FHKB из GEDCOM-файла: gedcom2ttl.py. (После клонирования репозитория необходимо установить Python-зависимости при помощи команды pip install -r requirements.txt.) Скопируем FHKB-логику header.ttl в новый файл и дозапишем в него результат работы скрипта:

cp data/header.ttl romanov_family.ttl
./gedcom2ttl.py data/tsars.ged >> romanov_family.ttl


В результате у нас получилась онтология (TBox+ABox) в формате Turtle, которую можно открыть в любом внешнем редакторе (например, Protégé). При необходимости Turtle может быть преобразован в XML-формат OWL с помощью скрипта ttl2owl.py. Теперь выведение родственных связей по этой онтологии — дело техники. Мне известны три современные системы рассуждений для языка Python с открытым исходным кодом: RDFClosure, FuXi и Fact++ с обёрткой owlcpp. На самом деле, их гораздо больше, если «подружить» Python с виртуальной машиной Java (исторически Java лидирует в семантических технологиях и предоставляет гораздо больший набор инструментов). Упомянутые три выстроены по нарастанию сложности и производительности. Первая представляет собой наивный подход «грубой силы», когда все возможные триплеты генерируются методом перебора. Вторая (FuXi) основана на инфиксной Python-нотации для OWL и алгоритме Rete. Третья (Fact++) является низкоуровневой оптимизированной реализацией алгоритма Tableaux. В целом, на сегодня это одна из самых эффективных систем рассуждений с открытым исходным кодом. Для наших задач достаточно первой системы (RDFClosure), тем более, что она написана на чистом Python и устанавливается тривиальной командой pip install. Для рассуждений по генеалогии Романовых tsars.ged (41 член семьи) RDFClosure на ноутбуке с Intel Core i7 1.70GHz требует около десяти секунд.

Как уже говорилось, недостатком OWL 2 применительно к родословным является вычислительная сложность. Я опустил некоторые родственные отношения, упомянутые на иллюстрации выше, и сократил семейное древо Романовых до царственных особ и их ближайших родственников, чтобы демонстрационные рассуждения не загружали ваш компьютер слишком сильно. Если задать все родственные связи с иллюстрации выше и расширить генеалогию хотя бы до нескольких сотен членов семей, RDFClosure становится бесполезной (Fact++, впрочем, продолжает работать).

Запустим рассуждения для полученной выше онтологии:

./infer.py romanov_family.ttl


Пока идут рассуждения, поясню ключевые моменты скрипта infer.py. Его суть умещается в шести строках:

import rdflib
from RDFClosure import DeductiveClosure, OWLRL_Extension
g = rdflib.Graph()
g.parse("romanov_family.ttl", format="turtle")
DeductiveClosure(OWLRL_Extension).expand(g)
print g.serialize(format="turtle")


В первых двух строках мы импортируем систему рассуждений RDFClosure и библиотеку RDFLib, обеспечивающую взаимодействие с онтологиями. В третьей и четвёртой строке — объявляем граф и наполняем его содержимым онтологии romanov_family.ttl. Пятая строка — это запуск рассуждений. В данном случае они являются ничем иным, как циклическим расширением входного графа новыми триплетами по правилам OWL 2. Шестая — печать полученного графа (в том же самом формате Turtle).

Итак, мы получили результат romanov_family.ttl.inferred (по дисковому размеру он в несколько раз больше входного файла). Подготовим его для визуализации. Я написал простое HTML5-приложение (index.html), показывающее граф выведенных родственных отношений в браузере с помощью JavaScript-библиотеки D3.js. Оно доступно в онлайн-ветви репозитория к этой статье. Рёбра графа соответствуют сведениям, взятым из GEDCOM (браки, isFatherOf, isMotherOf), а выведенные родственные отношения подсвечиваются разными цветами при выборе члена семьи. Выбор происходит по наведению курсора или по касанию на сенсорных дисплеях. Граф для этого приложения задаётся в формате JSON с очень простой структурой — список рёбер с указанием вершин (индивидуумов) и типа связи (родственного отношения) между ними. Онтология, полученная на предыдущем шаге, переводится в этот JSON скриптом ttl2json.py:

./ttl2json.py romanov_family.ttl.inferred > romanov_family.json


По умолчанию HTML5-приложение загружает JSON по адресу data/tsars.json. Новый сгенерированный вами JSON можно загрузить в браузер простым нажатием кнопки на веб-странице (используется интерфейс File API без сервера, и визуализация работает оффлайн).

Все вышеописанные команды собраны в Shell-скрипт gedcom2json.sh. С его помощью можно непосредственно переводить GEDCOM-генеалогии в JSON с выведенными родственными связями для визуализации. Добавить выведение и визуализацию других родственных связей относительно просто. Для этого нужно, во-первых, дописать соответствующую логику в TBox FHKB, во-вторых, внести идентификатор новой родственной связи в конвертер Turtle-JSON ttl2json.py, в третьих, задать цвет, название и идентификатор новой родственной связи в коде HTML5-визуализации. Само собой, время генерации JSON из GEDCOM при этом несколько вырастет.

В дополнение, есть идея, что входными данными для любой онтологии (не только генеалогической) могут служить интеллект-карты (mind maps). Разумеется, при рисовании необходимо придерживаться чётких правил, чтобы можно было перевести карту в ABox онтологии, используя, например, Python XMind SDK. Именно так, например, я запускал логические рассуждения для своей родословной, которую исторически вёл в виде интеллект-карты.

Подведём итоги: задав между членами семьи только самые ближайшие родственные связи (братьев и сестёр, браки, отцовство и материнство) и определив логику остальных связей, мы смогли вывести все остальные связи благодаря семантическим технологиям. Таким образом, мы прикоснулись к мощнейшему инструменту, лежащему в основе таких продуктов, как Wolfram Alpha и граф знаний Google. Онтологии и системы рассуждений — зрелые и широко используемые сегодня технологии, но, к сожалению, порог вхождения в эту область отнюдь не низок.

Ссылка на репозиторий к этой статье: github.com/blokhin/genealogical-trees
HTML5-приложение: blokhin.github.io/genealogical-trees/#ru
Общедоступные GEDCOM-файлы можно экспортировать из генеалогических порталов, например, www.wikitree.com

Приятного погружения в семантические технологии, и да не страшен будет нам Скайнет!
Евгений Блохин @jam31
карма
10,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (0)

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