УДК 519.6

МГТУ им. Н.Э. Баумана,

Введение

         Можно выделить три следующих класса систем поддержки принятия решений (СППР): системы, основанные на использовании типовых решений; системы, использующие типовые правила синтеза решений; системы, использующие поиск прецедентов. Корпоративная база знаний представляет собой, как правило, совокупность разного рода слабоструктурированных документов, в которых с той или иной степенью подробности описаны прецеденты – некоторые ситуации и решения, которые были приняты в этих ситуациях. В СППР, которые используют такие базы знаний, поиск решения заключается в поиске в этих базах наиболее подходящих прецедентов и соответствующих им документов [1].

         Эффективность поиска решений в базах знаний прецедентов в значительной мере зависит от используемых методов поиска.

         Современные поисковые системы основаны, преимущественно, на применении полнотекстового поиска – поиска в каждом из документов всех терминов, входящих в запрос. При этом учитывается частота встречаемость терминов в документе и их средняя языковая частотность [2].

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

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

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

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

Модели семантических сетей

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

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

         Пусть  - множество концептов рассматриваемого документа , а  - совокупность бинарных отношений между концептами множества . Общее число концептов и типов отношений  документа  обозначим ,  соответсвенно; , .

         Семантическую сеть  документа  представим в виде взвешенного мультиграфа , аналогичного графу .

         Веса вершин и дуг графов ,  определены ниже.

Метрики графа семантических сетей

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

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

         Тогда в качестве метрик графа  могут быть использованы его «высота», которая определяется на основе ярусно-параллельной формы (ЯПФ) этого графа [9].

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

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

         Наконец, в качестве метрики графа  может быть использована его «реберная плотность», определяемая формулой

,

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

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

Кластеризация семантических сетей

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

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

         Обозначим  совокупность всех концептов семантической сети , включая сам концепт , которые связаны отношением типа  с концептом  в узком смысле. Назовем эту совокупность -локальным кластером концепта  в семантической сети . Число концептов в кластере  равно, очевидно, .

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

.

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

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

         Совокупность всех концептов кластера , включая концепт , которые расположены на расстоянии  от указанного концепта, обозначим . Число таких концептов обозначим , где  - диаметр кластера ; . Очевидно, что .

         Взвешенные мультиграфы, соответствующие кластерам ,  обозначим ,  соответственно.

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

Веса вершин и дуг семантических сетей

         Поставим в соответствие каждому из типов отношений  его вес , . Аналогично поставим в соответствие каждой из вершин  графа  вес , , формализующий «важность» концепта  в семантической сети .

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

.

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

, .

         Аналогично, вес  можно определить на основе суммарной и средней высот :

, ;

, .

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

, ;

, ;

, .

         Аналогично, веса  можно определить на основе максимальной, суммарной и средней реберных плотностей графов , где  - некоторое фиксированное значение из диапазона . Например,

, .

         Наряду с рассмотренными весами  могут быть использованы их нормированные тем или иным образом аналоги, например,

,  

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

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

, .

         Аналогично можно использовать взвешенное число концептов, содержащихся во всех -глобальных кластерах :

, .                                 (1)

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

, , .

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

, ;

, ;

, .

         Аналогично, веса  можно определить на основе максимальной, суммарной и средней реберных плотностей графа , например

, , .

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

Меры важности концептов в семантической сети документа

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

         1). Взвешенное число концептов, содержащихся во всех -локальных кластерах

, .

         2). Взвешенное число концептов, содержащихся во всех -глобальных кластерах

, .

         3). Нормированное взвешенное число концептов, содержащихся во всех -глобальных кластерах

, , .

         4). Взвешенные максимальный, суммарный и средний из диаметров кластеров :

, ;

, ;

, .

         5). Взвешенные максимальная, суммарная и средняя из реберных плотностей кластера , :

, ;

, ;

, .

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

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

Заключение

         В работе под онтологий  понимается, так называемая, «легкая» онтология, определяемая парой вида , где  - множество концептов, а  - множество отношений между ними. В развитии работы планируется применить предложенную в ней методику оценки важности концептов к «тяжелой» онтологии, которая определяется тройкой , где  - множество функций интерпретации, определенных на концептах и/или отношениях онтологии.

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

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

         Работа выполнена при поддержке гранта РФФИ 10-07-00401.

Литература

1.                Норенков И.П. Интеллектуальные технологии на базе онтологий // Информационные технологии, 2010, ╧1, с.17-23.

2.                Толчеев В.О. Методы выявления информационных признаков в задачах классификации текстовых документов // Информационные технологии, 2005, ╧8, с.14-21.

3.                The Dublin Core® Metadata Initiative // (http://dublincore.org/).

4.                Карпенко А.П., Соколов Н.К. Оценка сложности семантической сети в обучающей системе // Наука и образование: электронное научно- техническое издание, 2008, 11, (http://technomag.edu.ru/doc/106658.html).

5.                Карпенко А.П., Соколов Н.К. Расширенная семантическая сеть обучающей системы и оценка ее сложности // Наука и образование: электронное научно- техническое издание, 2008, 12, (http://technomag.edu.ru/doc/111716.html).

6.                Карпенко А.П., Галямова Е.В., Соколов Н.К. Методика контроля понятийных знаний субъекта обучения в обучающей системе // Наука и образование: электронное научно- техническое издание, 2009, 2, (http://technomag.edu.ru/doc/115086.html).

7.                Карпенко А.П., Соколов Н.К. Меры сложности семантической сети в обучающей системе // М.: Вестник МГТУ им. Н.Э. Баумана, серия «Приборостроение», 2009, ╧1(74), с. 50-66.

8.                Галямова Е.В., Карпенко А.П., Соколов Н.К., Ягудаев Г.Г. Контроль понятийных знаний субъекта обучения в обучающей системе // М.: Вестник МАДИ (ГТУ), 2009, ╧2(17), с.82-86.

9.                Федотов И.Е. Некоторые приемы параллельного программирования: Учебное пособие.- М.: Изд-во МГИРЭА (ГУ), 2008.- 188 с.

10.           Евстигнеев В.А. Применение теории графов в программировании. –М.: Наука, 1985.-332 с.

11.           Ларичев О.И. Теория и методы принятия решений, а также Хроника событий в Волшебных странах. – М.: Университетская книга, Логос, 2006. -292 с.