ГИБРИДНАЯ ИНТЕЛЛЕКТУАЛЬНАЯ МЕРА ОЦЕНКИ СЕМАНТИЧЕСКОЙ БЛИЗОСТИ

Общая постановка проблемы

Современный мир характеризуется резким ростом объёмов информации, особенно в сети Интернет. Это привело к стремительному развитию Веб-технологий, переходу к концепции Semantic Web, о чем свидетельствует ряд разработанных стандартов WWW, например, стандарт на язык представления знаний (RDF) и язык описания онтологий (OWL) [1], [2]. Онтологии становятся базой для построения систем управления знаниями (СУЗ). В связи с этим в работах [3], [4] был описан онтологический подход к построению СУЗ научно-образовательных организаций, каркасом которого является прикладная онтология в области профессиональной деятельности сотрудников научно-образовательных организаций. Использование современными семантическими технологиями и онтологии позволили перейти на новый уровень обработки данных – семантический, когда появляется возможность поиска и извлечения знаний по заданной теме, а не просто конкретного файла [5].

Ключевым моментом при построении СУЗ является разработка алгоритмов расчета количественных оценок семантической близости (СБ) онтологических термов. Функция F(X, Y), ставящая в соответствие каждой паре термов X и Y некоторый вещественный коэффициент, называется функцией, определяющей семантическую близость между двумя термами.

Для F (X, Y) действительны следующие свойства:

• 0 ≤ F (X, Y) ≤ 1;
• F (X, Y) = 1 ⇔ X = Y (объекты X, Y идентичны);
• F (X, Y) = 0 ⇔ X ≠ Y (объекты X, Y совершенно различны и не имеют схожих характеристик);
• F (X, Y) = F (Y, X), (свойство симметричности функции подобия).

В свою очередь, каждый терм представляет собой некоторое размытое множество, куда попадают и другие подобные термы со значением семантической близости выше заданного порога. Принадлежность к нечеткому множеству задается с помощью значения семантической близости. Подобие сущностей X, Y означает, что F (X, Y)> = t, где t – пороговая величина (уровень подобия, уровень отсечения). В свою очередь, все термы со значением менее некоторого порогового значения t1 считаются различными. Другими словами, функция принадлежности к нечеткому множеству следующая:

Формула 1 – функция принадлежности к нечеткому множеству

где – функция, определяющая семантическую близость между двумя термами, , – пороговые значения.

Таким образом, необходимо разработать способ определения СБ для дальнейшего использования в алгоритмах поиска и классификации.

Обзор существующих методов оценки близости

Мера семантической близости между концептами – это числовая оценка их смысловой связанности. По тематике, посвященной методам оценки СБ терминов написано немало работ. В работе [6] сделан обширный обзор различных методов вычислений мер семантической близости термов внутри онтологий.

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

Другим устоявшимся подходом является подход Тверски, когда через сопоставление одинаковых и различных свойств определяется близость двух объектов. В большинстве мер при вычислении СБ используется нормализованная модель (ratio model), которая является развитием подхода Тверски:

Формула 2 – нормализованная модель Тверски

где A и B – множества свойств этих объектов, f – некоторая функция, α и β – веса общих и различных свойств объектов.

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

Формула 3 – аддитивная свертка гибридных моделей

где Si – i-ая мера близости по определенному критерию, с1,с2 – два концепта, wi – вес i-й меры, n – число мер.

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

Формула 4 – сигмоидальная функция

, где a>0

Веса рассчитываются вручную экспертами или автоматически с помощью интеллектуальных методов – нейронной сети или генетического алгоритма.

Выделяют следующие типы мер семантической близости [6]:

1. таксономические – на основе иерархических (родовидовых, таксономических) связей;
2. реляционные – на основе неиерархических (ассоциативных, проблемно специфических, «горизонтальных») связей между терминами онтологии;
3. атрибутивные.

В свою очередь таксономические подразделяются на:

1. на определении кратчайшего пути;
2. основанные на определении глубины иерархии;
3. учитывающие глубину ближайшего общего родителя (LCS);
4. основанные на понятии общей специфичности двух вершин.

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

Среди методов оценки СБ используются методы, основанные на вычислении подобия определенных характеристик. Среди мер, учитывающих значения атрибутов, известна атрибутивная мера близости, основанная на близости значений общих атрибутов понятий. Пусть A – множество атрибутов; A(i) – множество атрибутов экземпляра i; ACO = A(i1) ∩ A(i2) – множество общих атрибутов экземпляров i1 и i2, S (i1, i2, a) близость двух экземпляров i1 и i2 в отношении одного атрибута а. Тогда атрибутивная мера близости экземпляров i1, i2 с учетом всех атрибутов из Асо=А(i1)A(i2) вычисляется по формуле [6]:

Формула 5 – атрибутивная мера близости

Также существуют и меры, основанные на обработке лексико-семантических ресурсов и основанные на обработке неразмеченных документов.

Традиционно в информационно-поисковых системах близость текстовых документов вычисляется как угол между векторами документов, образуемыми весами ключевых слов документов по схеме TF [7], [8]:

Формула 6 – косинусное сходство

где и – компоненты векторов.

Формула 7 – косинусная мера

Многие подходы, основанные на обработке текстовых документов, используют вычисление сходства между словами. Так, коэффициент подобия Жаккара вычисляет количество уникальных терминов, совместно используемых между двумя текстами, а коэффициент Левенштейна состоит из минимального количества необходимых операций по трансформации одной строки в другую. Семантическое сходство между двумя текстами как максимальное значение, полученное между парами слов, определяется в мерах Леска, Резника и др.

Последнее семейство мер, Дайса и Жаккара, коэффициент Танимото – это простые, нерекурсивные меры близости, которые традиционно применялись в области информационного поиска. Эти меры определяют схожесть двух множеств на основе общих символов и удобно выражаются в множественно-теоретической форме. Несомненным их плюсом является низкая вычислительная сложность.

Пусть Na – количество элементов в первом множестве, Nb – количество элементов во втором множестве, Nc – количество общих элементов в обоих множествах. Тогда коэффициент Танимото принимает значения от 0 до 1 (чем ближе к 1, тем больше сходство между множествами) [9]:

Формула 8 – коэффициент Танимото

Мера Дайса:

Формула 9 – мера Дайса

Коэффициент Жаккара [8]:

Формула 10 – коэффициент Жаккара

Среди примеров простейшей гибридной меры можно привести формулу «мягкого косинуса», который кроме векторных характеристик текста учитывает еще и семантику [8]:

Формула 11 – мягкий косинус

и – компоненты векторов, – матрица семантических связей.

В работе [10] предложен подход, когда гибридная мера близости содержит оценку критериев подобия понятий онтологии, состоящую из трех частей: атрибутивная мера, таксономическая мера и реляционная мера.

Формула 12 – гибридная мера

где St, Sp, Sa – таксономическая, реляционная и атрибутивная составляющие коэффициента близости, соответственно, t, p и a – веса составляющих близости объектов в интервале [0, 1], их сумма равна единице.

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

В работе [11] предложена методика оценки СБ, отличительной особенностью которой является автоматическое определение весовых коэффициентов с использованием метода роя частиц.

Таким образом, при исследовании методов были рассмотрены разные походы: теоретико-множественный подход, базирующийся на определении пересечения одинаковых и различных свойств; информационный подход на базе статистики (частоты встречаемости терминов); структурный подход, основанный на определении различных характеристик онтологий (длина пути, глубина иерархии и др.). Очевидно, что чем полнее учитываются различные характеристики двух сущностей, тем качественнее рассчитываются меры близости и гибридные меры близости, сочетающие несколько подходов и методов, являются наиболее перспективными.

Трехмерный тензор семантических связей на базе RDF-графа онтологии

Современным подходом при построении баз знаний является использование стека семантических технологий. Стандартизованный консорциумом W3C RDF специфицирует архитектуру, синтаксис и семантику, а также базовый словарь RDF Schema (RDFS) для построения моделей предметных областей [1]. В концепции Semantic Web модель данных в виде RDF-графа представляется следующим образом: Subject – Predicate –> Object. Каждая сущность в свою очередь имеет свой универсальный и уникальный идентификатор ресурса – URI (Uniform Resource Identifier).

Для моделирования бинарных отношений на RDF-графе удобно использовать трёхмерный тензор [12]. Наилучшим определением тензора будет цитата Tamara G. Kolda: «A tensor is a multidimensional array» [13]. У тензора бывают верхние, нижние и смешанные индексы. Верхние меняют значение при переходе от одной строки к другой, а нижние при переходе от одного столбца к другому.

В работе [14] авторами было предложено тензорное представление графа знаний в виде тензорного разложения RESCAL.

Для представления многомерных семантических данных авторы работы [15] использовали формализм RDF семантической сети, где отношения моделируются как тройки (субъект, предикат, объект) и где предикат моделирует либо отношения между двумя сущностями, либо между сущностью и значением атрибута. Тензорная запись Sijk ≠ 1 обозначала тот факт, что существует RDF отношение (i-я сущность, j-й субъект, k-й предикат). В противном случае для несуществующих и неизвестных отношений запись устанавливается равной нулю.

В данной работе впервые предлагается использование трехмерного тензора семантических связей, значения которого определяются различным образом для отношений графа знаний и содержат значения в диапазоне [0,1].

Рисунок 1 – Трехмерный тензор семантических связей

Рассмотрим меры СБ, которые были использованы в модели трехмерного тензора семантических связей. Для анализа трехмерного тензора рационально разложить трехмерный куб на отдельные матрицы, представляющие собой матрицы семантических связей для отдельно взятых отношений Rk (рис. 2). Количество полученных матриц соответствует числу используемых в модели мер.

Рисунок 2 – След трехмерного тензора семантических связей Sij¹ при k=1

Элемент матрицы Sij¹ равен числу w, если существует ребро между вершинами Ci и Cj с весом w. Элемент Sij¹ равен нулю, если рёбер между вершинами Ci и Cj не существует.

Меры для оценки СБ по иерархии онтологии

СБ двух термов может быть оценена по положению вершин в иерархической структуре данных – онтологии. Для получения иерархии классов предметной области в виде графа следует выделить скелет (каркас) онтологии. При этом ребра дерева отражают иерархические отношения типа:

1. R1 – таксономические (IS-A, KIND-OF, has, имеет);
2. R2 – партономические (PART-WHOLE, part-of, часть-целое);
3. R3 – родовидные (PARENT-CHIEILD, TOPIC–SUBTOPIC, родитель-ребенок).

Зафиксировав индекс k=1 в трехмерном тензоре семантических связей, мы получили след матрицы Sij¹ – матрицу семантических связей для первого отношения R1. Соответственно при k=2 и k=3 мы получили подобные матрицы для отношений R2 и R3. За расстояние между концептами приняли длину минимального пути между ребрами, так как требуется построить в максимальной степени сбалансированное дерево. При расчете использовали путь от ближайшего общего предка обоих термов и лишь в случае отсутствия идем от корня.

Оценка семантических отношений, выраженных в OWL свойствами концептов

Важным свойством графовых моделей данных является возможность возникновения различных корреляций между множеством взаимосвязанных узлов. Подобные корреляции могут быть вычислены за счёт включения обработки атрибутов, связей и классов связанных сущностей. Мера СБ показывает высокие значения для концептов, которые находятся в семантических отношениях (синоним, гипоним, ассоциативность) и нулевые значения для всех остальных пар.

Свойства OWL типа Data Propery определяют связь между объектами и данными. Выделим отдельно отношение синонимизации ввиду его особой семантической важности. Зафиксировав индекс k=4, мы получим матрицу семантических связей для отношения R4 – синонимизации (эквивалентности, подобия). Если концепты связаны, то СБ=1, иначе 0.

Свойство типа Object Property определяет отношения между индивидуальными объектами. Зафиксировав индекс k=5, мы получим матрицу семантических связей для отношения R5 – Individal. Если два концепта связаны отношением Object Property, то их мера связанности также равна 1.

Между классами и экземплярами различных классов наряду с иерархическими связями могут быть и другие «горизонтальные» семантические связи, представляемые объектными бинарными отношениями, характерными для описываемой предметной области. Зафиксировав индекс k=6, мы получим матрицу семантических связей для отношения R6 – свойства ассоциации (семантических отношений). Поскольку данная матрица не является матрицей смежности, то с помощью эксперта рассчитываются значения всех семантически связанных ячеек, остальные обнуляются.

Рассмотрим процедуру определения СБ на примере фрагмента онтологии “Документ”, которая описывает различные виды документов в деятельности организаций. Часть документов, например, научные статьи, имеют достаточно шаблонную структуру (если соответствуют ГОСТ) и содержат заголовок, аннотацию, список ключевых слов, тему документа, выводы. Эти элементы присутствуют почти во всех документах, несмотря на различные требования к оформлению научных статей. Логично предположить, что наиболее важная информация заключается в заголовке, аннотации и списке ключевых слов и эти термины должны иметь более высокий вес по сравнению с другими понятиями, встречающимися в основном тексте. Соответственно, веса могут быть откорректированы экспертным путем в любой момент времени.

Поскольку в OWL стандарте предусмотрено хранение свойств-атрибутов, то целесообразно будет и вычисление атрибутивной меры близости концептов. Таким образом, зафиксировав индекс k=7, мы получим матрицу семантических связей для отношения R7 – атрибутивную меру сходства.

Меры СБ, основанные на SVM и контекстных множествах

При решении задач поиска используются векторные меры сходства при решении некоторых задач, особенно когда онтология только наполняется данными или не имеет концептов по определённой теме. Сущности графа знаний могут быть эффективно представлены векторами их латентных свойств. Данные свойства называют латентными, т.к. они напрямую не описаны в данных, но могут быть выведены из имеющихся данных в процессе математической обработки. В работе [14] предложена модель, представляющая тройки посредством парного взаимодействия латентных свойств.

Следующей группой мер являются меры, построенные на предположении, что семантически близкие концепты встречаются в тексте в одинаковых контекстах, т.е. обладают похожим набором ключевых (контекстных) слов, который называется контекстным множеством. Для определения меры сходства между двумя документами можно использовать меры на базе косинусного сходства (см. форм. 7). Одна из причин популярности этой меры состоит в том, что она эффективна в качестве оценочной меры, особенно для разреженных векторов, когда необходимо учитывать только ненулевые измерения. Мы использовали «мягкую» косинусную меру сходства между двумя векторами. При расчете «мягкой» косинусной меры используется матрица S сходства между признаками. При отсутствии сходства между признаками (Sij = 0 для i ≠ j), данное уравнение эквивалентно общепринятой формуле косинусного сходства (см. формулу 11).

Следовательно, зафиксировав индекс k=8, мы получим матрицу семантических связей для отношения R8, рассчитанную по векторной мере сходства.

Таким образом, получаем таблицу используемых в гибридной интеллектуальной мере мер СБ.

Генетический алгоритм взвешивания коэффициентов гибридной модели

Тензорное представление графа семантических отношений позволяет эффективным образом вычислить оценки семантической близости между двумя концептами через факторизацию срезов тензора. Выполнив аддитивную свертку тензора Sij^k с вектором коэффициентов значимости для каждого типа отношения Wk получаем:

Формула 13 – аддитивная свертка тензора

где Wk – вес, который определяет относительную важность каждого типа отношения, р – число отношений, R – матрица семантических связей ключевых концептов.

Для оценки весов Wk использовался генетический алгоритм. В результате сформировалось близкое к оптимальному распределение весов для конкретного набора отношений. Существует также возможность экспертного ввода весовых коэффициентов в настройках прикладной программы.

Эксперименты

С целью тестирования разработанных моделей и алгоритмов была разработана программа на языке PHP с использованием целого ряда библиотек и фреймворков. Тестирование проводилось на бюджетном ноутбуке со следующими параметрами: Процессор Intel(R) Core(TM) i3-4010U CPU @ 1.70GHz, 1700 МГц, ядер: 2, логических процессоров: 4, Установленная оперативная память (RAM) 4,00 ГБ. Интерфейс программы приведен на рис. 3.

Рисунок 3 – Интерфейс программного модуля

Программа снабжена целым рядом пользовательских настроек (рис. 4).

Рисунок 4 – Окно настройки параметров обработки файлов

Для определения оптимальных значений некоторых параметров были выполнены дополнительные исследования. Так, результаты выбора способа обработки документа сведены в табл. 2. Видно, что лучшим вариантом по сочетанию двух параметров – скорости обработки (t – время в секундах) и достигнутого результата (n – количество найденных ключевых слов) является разреженная обработка текста.

Результаты экспериментов по определению оптимальной длины контекстного вектора приведены на рис. 5.

Рисунок 5 – Результаты экспериментов по определению оптимальной длины контекстного вектора

В результате обработки документа происходит извлечение полезных знаний и расчет отдельных мер семантической близости к тематическим разделам, а также взвешенной гибридной меры (рис. 6).

Рисунок 6 – Результаты обработки отдельного файла

В качестве базы для проведения экспериментов были использованы электронные документы – материалы конференций факультета за последние 10 лет. На выбор тестового набора повлиял тот факт, что документы в свое время уже были рецензированы и разделены на секции рецензентами-экспертами, то есть набор уже был размечен.

Результаты обработки показали, что использование гибридной взвешенной меры дает существенное преимущество в следующих случаях:

• когда онтология не наполнена терминами;
• когда документ отличается в значительной степени от других;
• когда возникают семантические неоднозначности.

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

Выводы

В результате исследований на базе тензорного представления графа знаний был получен многомерный тензор семантических связей, в котором учитываются различные меры СБ для разных типов отношений. После программной обработки документов оказалось, что для разных документов значения различных мер отличались между собой по значению, но только в отдельных случаях возникали конфликты в рекомендациях по выбору разделов. Наиболее корректные результаты были получены, как и ожидалось, для гибридной меры.

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

Список литературы

РЕЗЮМЕ

Н. К. Андриевская
Гибридная интеллектуальная мера оценки семантической близости

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

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

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

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