Другие журналы
|
научное издание МГТУ им. Н.Э. БауманаНАУКА и ОБРАЗОВАНИЕИздатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408
Меры важности концептов в семантической сети онтологической базы знаний
# 07, июль 2010 DOI: 10.7463/0710.0151142
Файл статьи:
01.pdf
(582.19Кб)
УДК 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 с.
Публикации с ключевыми словами: семантическая сеть, база знаний, онтология, система поддержки принятия решений Публикации со словами: семантическая сеть, база знаний, онтология, система поддержки принятия решений Смотри также: Тематические рубрики: Поделиться:
|
|
||||||||||||||||||||||||||||||||
|