Математическое обеспечение систем поиска, основанных на онтологиях

УДК 519.7:007.52

Е.А. Жыжырий, С.С. Щербак

В статье предложен подход к организации поиска на основе онтологий предметных областей и разработано необходимое математическое обеспечение.

1. Введение

Развитие стандартов и широкая поддержка концепции Semantic Web крупными корпорациями определяет тенденции развития будущего Интернет как глобальной базы знаний, в которой программные агенты будут “осмысленно”, т.е. с учетом семантики, оперировать информацией для решения задач поиска и им подобных.

В рамках Semantic Web информация описывается в терминах объектов и свойств предметной области, спецификация которых задается с помощью специального вида словарей, называемых онтологиями предметных областей(ПрО).

Для представления знаний в онтологиях Semantic Web используется свойство-центричная модель. Главной особенностью этой модели является то, что объекты и свойства описываются отдельно. Причем, свойства описываются в терминах объектов, к которым они применимы, т.е. путем указания области применения (domain) и области значений свойства (range).

Для создания эффективных поисковых систем, основанных на онтологиях предметных областей, необходима разработка формальных процедур идентификации объектов ПрО на основе описаний, учитывающих накладываемые пользователем ограничения на значения свойств объектов.

В начало

2. Формальная модель онтологии предметной области

Поиск информации в рамках Semantic Web основывается на использовании знаний из онтологий ПрО. В рамках такого подхода содержимое документа представляется как совокупность экземпляров объектов ПрО, объединенных некоторым контекстом. Тогда поиск информации сводится к идентификации структурно-логических схем объектов ПрО в онтологиях и выводу экземпляров идентифицированного объекта с учетом пользовательских ограничений.

Структура объектов ПрО в онтологии явно задается с помощью структурно-логической схемы — совокупности формальных характеристик моделируемой объектом сущности ПрО.

Для организации поиска на основе онтологий ПрО создадим формальную модель онтологии ПрО и предложим процедуры ее обработки.

Уточним определения основных понятий используемых в работе.

Определение 2.1. Объект ПрО – формальная структура сущности предметной области.

Определение 2.2. Свойство объекта ПрО – логическая характеристика той или иной особенности объекта ПрО.

Определение 2.3. Онтология ПрО – спецификация распределенных по Web объектов ПрО и связей между ними.

Определение 2.4. Экземпляр объекта ПрО – объект ПрО с непустыми значениями свойств, связанный с другим объектом отношением “быть экземпляром” .

Свойство объекта ПрО, согласно определения 2.2, представим как совокупность следующих логических характеристик объекта ПрО:

p = < po, to, vo >, (2.1)

где po – символьное имя свойства p объекта o, to – тип значения свойства,vo – значение свойства.

Объект ПрО, согласно определению 2.1, представим как следующую совокупность логических характеристик моделируемой сущности ПрО:

o = < N, P, S, D, I >, (2.2)

где N – имя объекта, P – множество свойств объекта, причем Структурно-логическая схема онтологии предметной области, S – суперклассы объекта, D – подклассы объекта, I – экземпляры объекта, PU — множество свойств онтологии ПрО.

Множество отношений между объектами онтологии ПрО специфицируем с помощью следующего выражения:

R = < subclass, superclass, instance >, (2.3)

где subclass – отношение «быть подклассом», superclass – отношение «быть суперклассом», instance – отношение «быть экземпляром класса».

Тогда иерархия объектов ПрО может быть представлена следующим образом:

Oi = < O, R > , (2.4)

где O – множество объектов ПрО связанных между собой отношениями из R.

Учитывая вышесказанное, представим онтологию как совокупность структурно-логических схем свойств и объектов ПрО, связанных между собой отношениями R:

Ontology = < Oi, PU > , (2.5)

где О – иерархия объектов ПрО связанных отношениями из R, а PU – множество свойств онтологии.

Структурно-логическая схема онтологии ПрО представлена на рис. 1.

В начало

3. Идентификация объектов предметных областей с учетом пользовательских ограничений

Задача организации поиска на основе онтологий ПрО в контексте Semantic Web приобретает следующий смысл – на основе сформированного пользователем описания строится запрос, в виде возможной структурно-логической схемы объекта ПрО с пользовательскими ограничениями на возможные значения атрибутов искомых объектов ПрО.


Структурно-логическая схема онтологии предметной области

Рисунок 1. Структурно-логическая схема онтологии ПрО

Далее, по сформированной пользователем структурно-логической схеме объекта ПрО идентифицируется объект в онтологии путем сопоставления с существующими объектами онтологии. В случае, если идентификация успешна, т.е. найден объект онтологии соответствующий искомому, проводится вывод экземпляров идентифицированного объекта с учетом пользовательских ограничений на значения свойств.

    Схема процесса идентификации объектов в онтологий ПрО представлена на рис. 2.


Схема процесса идентификации объектов в онтологии предметной области

Рисунок 2. Схема процесса идентификации объектов в онтологии ПрО

Под идентификацией объектов ПрО будем понимать совокупность действий направленных на нахождение экземпляров интересующего пользователя объекта ПрО.

Последовательность идентификации объектов с учетом заданных пользовательских ограничений представлена ниже (рис.3):

  1. Идентификация в онтологии объекта ПрО с структурно-логической схемой соответствующей структурно-логической схеме запроса
  2. Вывод экземпляров объектов с учетом пользовательских ограничений на значения свойств.

Для организации идентификации объектов в онтологии ПрО введем понятие запроса к онтологии, что собственно и будет исходными данными для математической реализации метода идентификации объектов ПрО.

Определим запрос к онтологии как сформированную пользователем структурно-логическую схему объекта ПрО с установленными ограничениями на значения свойств экземпляров объекта таким образом:

Пусть pq – символьное имя свойства, rq – ограничение на значение ra = < ca, va >, тогда запрос Q к онтологии на идентификацию объектов ПрО с заданными пользователем ограничениями можно задать формулой:

Q = < N, < poq, <coq, voq > >,…,< pnq, < cnq, vnq > >, (2.6)
    где co, cn – условия вывода.


    Схема процесса идентификации объектов в онтологии с учетом пользовательских ограничений

    Рисунок 3. Схема процесса идентификации объектов с учетом заданных пользовательских ограничений

Процедура построения запроса к онтологии

    Построение запроса к онтологии состоит из ниже перечисленных действий:

  1. Указание символьного имени объекта ПрО, идентификацию экземпляров которого необходимо провести.
  2. Выбор свойств объекта ПрО, значения которых интересны пользователю в контексте проводимого поиска.
  3. Установка ограничений на значения свойств, т.е. определение критериев вывода экземпляров объектов ПрО.

Идентификация объекта ПрО, структурно-логическая схема которого соответствует пользовательскому запросу, заключается в следующем:

Пусть a = < N, P, O, O, O > структурно-логическая схема объекта ПрО, построенная по запросу Q, идентификацию которого необходимо провести, тогда запрос к онтологии подается на базовый объект онтологии, т.е. на такой объект, у которого нет суперклассов (N которого равно O) и вызывается процедура обработки
o этого объекта.

Процедура o сравнивает структурно-логическую схему запроса объекта, который ее вызвал и в случае полного совпадения прекращает обход объектов онтологии, иначе o передает запрос следующему объекту ПрО. В результате обхода графа онтологии процедура o возвращает реальный объект онтологии с искомой, задаваемой запросом, структурно-логической схемой объекта ПрО.

Для идентификации объекта ПрО, структурно-логическая схема которого соответствует пользовательскому запросу определим набор процедур, реализуемых в каждом объекте ПрО, необходимых для выполнения идентификации объектов в онтологии:

1. Процедура обработки объекта o

2. Процедура сравнения символьного имени объектов ПрО N

3. Процедура обработки пользовательского ограничения с

4. Процедура вывода экземпляров идентифицированного объекта

5. Процедуры передачи запроса на объект o и с соответственно.

Рассмотрим более детально математическую реализацию каждой процедуры.

Процедура обработки объекта ПрО o..

Обработка объекта ПрО подразумевает выполнение ряда действий по сравнению символьных имен объектов ПрО и навигации по иерархии объектов ПрО.

В обязанности этой процедуры входит анализ поступившего запроса и выполнение той или иной процедуры в соответствии с содержимым запроса.>

Процедура обработки объекта ПрО o устанавливает соответствие между символьными именами объектов онтологии и запроса. Если соответствие установлено (), то объект запроса идентифицирован и можно проводить вывод его экземпляров в соответствии с пользовательскими ограничениями на значения свойств; если соответствие не установлено, тогда необходимо проверить пустое ли множество подклассов объекта или нет – если пустое (), то запрос передается следующему объекту ПрО этого уровня; если не пустое (), то запрос передается на первый объект множества подклассов D.

Математическая реализация процедура обработки объекта ПрО o может быть представлена следующей формулой:

, (2.7)

где a = < N, P, O, O, O > — структурно-логическая схема объекта ПрО, построенная по запросу Q, идентификацию которого необходимо провести,

— возврат к объекту с которого был передан запрос () и передача следующему объекту (), – процедура сравнения символьного имени объектов ПрО.

Процедура сравнения символьного имени объектов ПрО отвечает за сравнение символьных имен объекта онтологии и входящего запроса:

, (2.8)

где Naсимвольное имя объекта a, построенного по запросу Q, No— имя объекта ПрО, вызвавшего процедуру .

Процедура обработки пользовательского ограничения предназначена для обработки значений свойств экземпляров объектов на предмет соответствия пользовательским ограничениям, задаваемых в запросе Q.

Математическая реализация процедура обработки объекта ПрО c может быть представлена следующей формулой:

, (2.9)

где po — свойство идентифицированного объекта ПрО, to — тип значения свойства , — значение свойства идентифицированного объекта ПрО, — условие вывода пользовательского ограничения, — граничное значение свойства пользовательского ограничения.

Семантика действий «=» «>» «<» условия вывода определяется типом значения сравниваемого свойства, т.е. каким именно образом

c будет реагировать на символьные имена действий «=» «>» «<» определяется типом значения сравниваемого свойства.

Для целочисленного типа значений свойства действия «=» «>» «<» определим следующим образом:

«=» — сравнение целочисленных значений свойства запроса и анализируемого объекта на “равенство” и если значения равны, то вывод экземпляра в качестве результата;

«>» — вывод экземпляра объекта в качестве результата в случае если целочисленное значение свойства запроса больше целочисленного значения свойства анализируемого объекта;

«<» — вывод экземпляра объекта в качестве результата в случае если значение свойства запроса меньше значения свойства анализируемого объекта.

Для строкового типа значений свойств объекта ПрО под действиями «=» «>» «<» будем подразумевать следующее :

«=» — это сравнение значения свойства запроса и анализируемого объекта на “равенство” и если значения равны, то вывод экземпляра в качестве результата;

«>» — вывод экземпляра объекта в качестве результата в случае если значение свойства запросабольше значения свойства анализируемого объекта , т.е. если является подстрокой и имеет место выражение ;

«<» — вывод экземпляра объекта в качестве результата в случае если значение свойства запросаменьше значения свойства анализируемого объекта , т.е. если является подстрокой и имеет место выражение

Действия «=» «>» «<» для значений свойств имеющих тип float (число с плавающей точкой) имеют такую же семантику как и соответствующие действия с целочисленным типом значений.

Процедура вывода экземпляров объекта

Вывод экземпляров идентифицированного объекта oid осуществляется путем последовательной обработки экземпляров объекта с учетом пользовательских ограничений, т.е. с проверкой соответствия значений свойств экземпляров на соответствие пользовательским ограничениям. В случае, если все значения свойств удовлетворяют пользовательским ограничениям, тогда экземпляр выводится в качестве результата выполнения запроса:

Пусть oid = < N, < po, to,vo >o,…,< pm, tm, vm >m > — структурно-логическая схема идентифицированного объекта oid,

Q = < N, < po, cor, vor > >o,…, < pm, < cou,vor >m > — структурно-логическая схема запроса с установленными пользовательскими ограничениями на значения свойств экземпляров объектов на заданных операциях cr = { <, >, = }.

Тогда подмножество экземпляров oid () с учетом пользовательских ограничений может быть получено последовательной проверкой каждого свойства экземпляра на предмет соответствия пользовательским ограничениям следующим образом:

, (2.10)

где o – объект ПрО, связанный с объектом отношением «быть экземпляром», I – множество экземпляров идентифицированного объекта , — свойство идентифицированного объекта , — тип значения свойства , — множество экземпляров I идентифицированного объекта .

Результатом идентификации объекта ПрО с учетом пользовательских ограничений будет подмножество экземпляров объекта , что собственно и необходимо было получить в контексте решаемой задачи поиска на основе онтологий ПрО.

Замечание. В случае если устанавливается более чем одно пользовательское ограничение (условие вывода на значения свойства) тогда решение о выводе экземпляра объекта как результата принимается как «положительная» конкатенация результатов сравнения отдельных значений свойств с ограничениями пользовательского запроса, т.е. если все значения свойств удовлетворяют пользовательским ограничениям, тогда экземпляр объекта может быть представлен как результат запроса[3].

В начало

4. Алгоритмическое обеспечение

Рассмотрим алгоритм реализации метода идентификации объектов ПрО на следующем примере:

Пусть задана онтология ПрО состоящая из 5 объектов — двух подклассов объекта Thing с экземплярами, как показано на рис 4.


Структурно-логическая схема онтология предметной области

Рисунок 4. Структурно-логическая схема онтология предметной области

Шаг 1. Построим запрос к онтологии Q на идентификацию экземпляров объекта B значения свойств b1, b2 которых равны :

Q = < B, <b1, <=,v2 > >,…,< b2, <=,v2 >>>

Шаг 2. По запросу Q построим структурно-логическую схему объекта a:

a = < B, P, , , >,

где P ={b1,b2}

Шаг 3. Подаем запрос на базовый объект Thing и вызываем этого объекта. Результат сравнения символьных имен объектов Thing и a будет отрицательным. Учитывая то, что множество подклассов D объекта Thing не пусто, то передаем запрос на первый объект множества его подклассов –

объект A.

Шаг 4. Вызываем объекта A. Результат сравнения символьных имен объектов A и a будет отрицательным; учитывая то, что множество D пусто, то передаем запрос следующему объекту — объекту B.

Шаг 5. Вызываем объекта B. Результат сравнения символьных имен объектов B и a будет положительным; учитывая это, далее вызываем этого объекта.

Шаг 6. Согласно выражения 2.10 результатом выполнения запроса будет объект .

В начало

5. Верхняя оценка сложности идентификации объектов ПрО в онтологии с учетом пользовательских ограничений

При идентификации объектов в онтологии ПрО используются следующие элементарные операции:

1. Операция символьного сравнения имен объектов;

2. Операция поиска свойства в списке свойств;

3. Операция сравнения значения свойства с ограничением запроса.

Операция символьного сравнения имен объектов используется при навигации по древовидной иерархии объектов. Верхняя оценка вычислительной сложности (ВОВС) этой операции будет следующая:

, (2.11)

где – число объектов в онтологии, — время затрачиваемое на выполнение операции.

Операция поиска свойств в списке свойств применяется один раз, когда объект идентифицирован и необходимо выбрать из списка свойств те свойства, которые принадлежат этому объекту. ВОВС этой операции следующее:

, (2.12)

где — среднее число свойств в объекте, — число свойств онтологии, — время, затрачиваемое на поиск одного свойства объекта.

Операция сравнения значения свойства с ограничением пользовательского запроса используется при выводе экземпляров идентифицированного объекта ПрО. ВОВС этой операции следующее:

, (2.13)

где — число свойств запроса с указанными пользовательскими ограничениями, — среднее число экземпляров объекта ПрО, — время, затрачиваемое на сравнение одного значения свойства с ограничением.

Учитывая вышесказанное, ВОВС идентификации объектов ПрО в онтологии с учетом пользовательских ограничениях при последовательном выполнении операций будет составлять:

, (2.14)

где — ВОВС операции символьного сравнения имен объектов, — ВОВС операции поиска свойств в списке свойств, — ВОВС операции сравнения значения свойства с ограничением пользовательского запроса.

Анализ выражения 2.14 с учетом 2.11-2.13 показывает, что наибольшее влияние на сложность алгоритма по критерию временных затрат оказывают параметры n и m. Учитывая то, что 2.14 является уравнением 1-го порядка, будем считать сложность полученного алгоритма идентификации линейной.

Проверим экспериментально полученную линейную сложность алгоритма идентификации.

Экспериментальные значения ВОВС идентификации (2.14), проводились на компьютере следующей конфигурации – процессор P4 2,4 ГГц с ОЗУ 512 MB.

Время, затрачиваемое на выполнение операций (2.11-2.13), в мкс (Табл. 2.1).

Табл. 2.1. Время затрачиваемое на выполнения операций

tn
(мкс)
tk (мкс) tq (мкс)
755,876 1203,368 3662,06
133,242 469,28 1272,922
145,812 207,824 1235,212
120,672 227,936 1231,022
120,672 197,768 1223,48
120,672 197,768 1231,022
113,13 191,064 1198,34
110,616 191,064 1251,972
120,672 197,768 1198,34
110,616 197,768 1271,246
110,616 191,064 1211,748
120,672 191,064 1244,43
110,616 204,472 1215,1
110,616 191,064 1244,43
110,616 201,12 1203,368

Средние значения времени, затрачиваемого на выполнение операций:

tn = 137,5661(мкс)

tk = 224,8522 (мкс)

tq = 1258,793 (мкс)

Экспериментальные значения ВОВС идентификации (2.15) в зависимости от параметров n и m представлены в Табл. 2.2.

Табл. 2.2.Экспериментальные значения ВОВС идентификации

N m Vid
10 10 36804,41
20 20 47174,15
30 30 57543,9
40 40 67913,65
50 50 78283,4
60 60 88653,14
70 70 99022,89
80 80 109392,6
90 90 119762,4
100 100 130132,1
110 110 140501,9
120 120 150871,6
130 130 161241,4
140 140 171611,1
150 150 181980,9
160 160 192350,6
170 170 202720,4
180 180 213090,1
190 190 223459,9
200 200 233829,6
210 210 244199,4
220 220 254569,1

График зависимости сложности полученного алгоритма идентификации от параметров n и m представлен на рис. 5.


График зависимости сложности идентификации объектов ПрО от числа объектов и свойств в онтологии

Рис 5. График зависимости сложности идентификации объектов ПрО от числа объектов и свойств в онтологии.

Проведенные эксперименты по вычислению сложности идентификации объектов ПрО подтверждают линейную зависимость между верхней оценкой вычислительной сложности идентификации объектов ПрО от числа объектов и свойств в онтологии.

Выводы

В работе показана специфика поиска на основе онтологий ПрО и предложен подход к решению этой задачи с соответствующим математическим и алгоритмическим обеспечением. Кроме того, в результате проведения экспериментальных исследований была получена верхняя оценка сложности идентификации объектов в онтологии ПрО с учетом пользовательских ограничений и построена зависимость сложности алгоритмического обеспечения метода идентификации от количества свойств и объектов в онтологии ПрО. А также было показано и экспериментально подтверждено то, что сложность алгоритма идентификации объектов ПрО является линейной.

В начало

Литература

  1. http://w3c.org
  2. http://www.ontolib.com

2 Responses to Математическое обеспечение систем поиска, основанных на онтологиях

  1. Shante:

    Сергей, правильно ли я поняла что «объект ПрО» это есть множество экземпляров онтологии или один из контекстов пользовательского запроса? Из вашей статьи следует, что пользователь должен иметь представление об онтологии (хотя бы о ее классах) для того чтобы задать ограничения на запрос. И для того чтобы произвести поиск — в запросе должны явно фигурировать имена классов?

  2. Shcherbak Sergey:

    Правильно.

    Пользователь может иметь представление об онтологии — для этого как раз и некоторое подмножество классов онтологии можно визуализировать. Для поиска имена классов должны быть, но это не обязательно, например имя можно заменить множеством атрибутов которые однозначно идентифицируют ваш класс. Здесь могут быть различные варианты в зависимости от конкретной задачи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *


Ответить с помощью ВКонтакте: