Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Некоторые методы огрубления графов при оценке релевантности документов

# 07, июль 2012
DOI: 10.7463/0712.0432649
Файл статьи: Карпенко_P.pdf (659.04Кб)
авторы: Вершинин В. Д., профессор, д.ф.-м.н. Карпенко А. П., Плякин Д. А.

УДК 519.6

Россия, МГТУ им. Н.Э. Баумана

vlad.vershinin@gmail.com

apkarpenko@mail.ru

 

Введение

Системы поддержки принятия решений (СППР) представляют собой обширный класс интеллектуальных систем, призванных помочь лицу, принимающему решения (ЛПР), в решении слабоструктурированных проблем [1]. Различные варианты классификации СППР представлены, например, в работе [2]. Целям нашей работы соответствует следующая классификация:

          ‑ системы, основанные на использовании типовых решений,

          ‑ системы, использующие типовые правила синтеза решений,

          ‑ системы на основе поиска прецедентов (Case-BasedReasoningsystem, CBR-system).

          Работа посвящена актуальной задаче в области искусственного интеллекта ‑ задаче поиска решений в корпоративных базах знаний на основе прецедентов [3]. Работу можно считать продолжением работы [4].

          Известны три способа извлечения прецедента или набора прецедентов из базы знаний [3]:

          ‑ поиск по прямым указателям в индексе на требуемые признаки,

          ‑ поиск по структуре индекса,

          ‑ поиск в модели онтологии предметной области.

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

Обычно в CBR-системах, построенных на основе семантической сети, в качестве метода извлечения прецедентов используют метод k-средних. Однако этот метод неэффективен в тех случаях, когда прецеденты содержат множество несущественных признаков [3]. В работе [4] для извлечения прецедентов из семантической базы знаний предложен метод, основанный на огрублении графа соответствующей семантической сети. Данная работа посвящена оценка эффективности этого метода. 

Отметим, что качество решений, полученных с помощью CBR-системы, сильно зависит от качества накопленной информации, объёма накопленных данных, объёма знаний о предметной области, а также от способа извлечения прецедентов [3]. Поэтому с самой общей точки зрения целью данной работы является повышение качества решений CBR-систем.

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

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

 

1. Постановка задачи

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

Обозначим ,  веса узлов графа . Пусть также  - -вектор весов ребра ,   этого графа. Здесь , если концепты  не связаны между собой отношением типа ;  - в противном случае;  - вес отношений типа  в онтологии . Алгоритмы определения весов ,  рассмотрены в работе [4].

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

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

Задача 1 (задача определения топологии графа ) - по каким правилам связывать узлы графа  ребрами?

Задача 2 (задача определения весов узлов и атрибутов ребер графа ) - исходя из каких соображений, назначать веса  узлов графа , а также значения атрибутов ,  его ребер?

Рассматриваем методы решения первой из указанных задач, основанные на огрублении соответствующего графа. Метод решения второй задачи предложен в работе [4] 

 

2. Алгоритмы огрубления графа

Суть рассматриваемого подхода к задаче огрубления графа состоит в итерационном стягивании смежных узлов графа  в узлы графа , где  - номер итерации,  [5]. Специфика нашего случая состоит в том, что запрещено стягивание в один узел тех узлов графа , которые принадлежат графу .

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

Рассматриваем три алгоритма построения насыщенных паросочетаний [6]:

‑ алгоритм случайных паросочетаний ,

‑ алгоритм паросочетаний из тяжелых ребер ,

‑ алгоритм паросочетаний из тяжелых клик .

Алгоритм . Схема алгоритма для итерации  имеет следующий вид:

1)         все узлы  текущего графа  объявляем немаркированными;

2)         случайным образом выбираем немаркированный узел, еще не включенный в паросочетание (пусть это будет узел );

3)         из числа немаркированных узлов, смежных узлу , случайным образом выбираем узел (пусть это будет узел ), также еще не включенный в паросочетание;

4)         если оба узла или один из узлов пары  не принадлежат графу , то включаем ребро  в паросочетание и узлы  маркируем;

5)         если ни одного немаркированного узла, смежного узлу , не существует, то узел  маркируем и оставляем свободным (чтобы затем перенести его в граф );

6)         если в графе  имеются еще немаркированные узлы, то переходим к шагу 2.

Алгоритм . Схема алгоритма отличается от рассмотренной выше схемы шагом 3, который в данном случае формулируется следующим образом:

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

Алгоритм . В данном случае также меняется только шаг 3 рассмотренной схемы формирования случайного паросочетания:

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

Указанную реберную плотность определяем по формуле

,

где  ‑ суммарные веса ребер, стянутых на предыдущих итерациях в узлы  соответственно;  ‑ суммарный вес ребра ;  ‑ суммарные веса узлов  соответственно.

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

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

Таким образом, схема алгоритма , например, имеет следующий вид:

1) все узлы  текущего графа  объявляем немаркированными;

2) случайным образом выбираем немаркированный узел, который содержит в себе один из узлов графа  и еще не включен в паросочетание (пусть это будет узел );

3) из числа немаркированных узлов, смежных узлу  и не содержащих в себе узел графа , случайным образом выбираем узел (пусть это будет узел ), также еще не включенный в паросочетание;

4) включаем ребро  в паросочетание и узлы  маркируем;

5) если ни одного немаркированного узла, смежного узлу , не существует, то узел  маркируем и оставляем свободным (чтобы затем перенести его в граф );

6) если в графе  имеются еще немаркированные узлы, то переходим к шагу 2.

 

3. Методика исследования

Назовем вершину графа , совпадающую с одной из вершин графа , терминальной вершиной.

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

Рассмотрены две группы тестовых графов , параметры которых представлены в таблице 1. Здесь  - номер графа; ,  ‑ реберные плотности графа и его -го кластера соответственно; min - минимальная реберная плотность, при которой еще не утрачена связность графа; .

 

Таблица 1 – Параметры тестовых графов

 

Группа

 

 

 

1

1

min

 

 

 

0,2

 

 

 

0,3

 

 

 

0,5

 

 

 

0,7

 

 

 

0,8

2

0,3

3

0,5

4

0,7

5

0,9

 

2

6

0,3

 

0,1

 

0,3

 

0,5

 

0,7

 

0,9

7

0,5

8

0,7

 

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

‑ время решения задачи , измеренное в CLOCK_TICKс помощью стандартного инструментария языка C,

‑ реберная плотность  результирующего графа,

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

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

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

 

4. Вычислительный эксперимент

          Интегральные результаты исследования эффективности алгоритмов  и алгоритмов  по критерию  представлены на рисунках 1, 2 соответственно. Как и следовало ожидать, рисунки показывают сильную зависимость времени решения задачи от реберной плотности графа . Для данной реберной плотности время решения задачи различными алгоритмами отличатся не более чем на 10%, что лежит в пределах статистической погрешности эксперимента. Другими словами, рисунки показывают близкую эффективность рассматриваемых алгоритмов по критерию .

 

Рисунок 1 – Эффективность алгоритмов  по критерию

         

Значительно более яркими являются результаты сравнительного исследования эффективности алгоритмов  и алгоритмов  (рисунок 3).

 

Рисунок 2 – Эффективность алгоритмов  по критерию

 

 

а) алгоритмы

 

 

б) алгоритмы

 

 

в) алгоритмы

 

Рисунок 3 – Сравнительная эффективность алгоритмов по критерию

 

Рисунки 3а – 3в показывают превосходство модифицированных алгоритмов  над исходными алгоритмами  по критерию  от ~100 до ~300%.

Аналогичные результаты исследования по критерию реберной плотности  результирующего графа представлены на рисунках 4 – 6. Как и в случае критерия , рисунки 4, 5 показывают близкую эффективность исходных и модифицированных алгоритмов между собой для всех рассматриваемых классов графов.

 

Рисунок 4 – Эффективность алгоритмов  по критерию

 

Рисунок 5 – Эффективность алгоритмов  по критерию

 

а) алгоритм

 

б) алгоритмы

 

в) алгоритмы

 

Рисунок 6 – Сравнительная эффективность алгоритмов по критерию

 

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

Эффективность исходных алгоритмов  и модифицированных алгоритмов  по критерию  иллюстрируют рисунки 7, 8.

Рисунок 7 – Эффективность алгоритмов  по критерию 

 

Рисунок 8 – Эффективность алгоритмов  по критерию 

 

Рисунки 7, 8 показывают близость соответствующих алгоритмов этих групп между собой по критерию  для всех рассматриваемых классов графов и их плотностей.

Сравнительную эффективность исходных и модифицированных алгоритмов по критерию  иллюстрируют рисунки 9а – 9в.

 

а) алгоритмы

 

б) алгоритмы

 

в) алгоритмы

 

Рисунок 9 – Сравнительная эффективность алгоритмов по критерию

 

Рисунки 9а – 9в показывают, что кроме случая слабосвязанных кластеров, модифицированные алгоритмы лучше сохраняют начальную принадлежность вершин кластеру по сравнению с исходными алгоритмами, и это превосходство может достигать 20%.

 

Заключение

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

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

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

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

 

Литература

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

2.          Гайдрик К.В. Системы поддержки принятия решений: эволюция, концепции и некоторые перспективы

(http://www.masters.donntu.edu.ua/2010/fknt/sheptulia/library/article05.htm).

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

4.         Карпенко А.П. Методика оценки релевантности документов онтологической базы знаний // Информационные технологии, 2011, №4, с. 13-23

5.         Bui T.N., Chaudhuri S., Leighton F.T., Sipser M. Graph bisection algorithms with good average case behavior // Combinatorica, 1987, N7, pp. 171.191.

6.         Бувайло Д.П., Толок В.А. Быстрый высокопроизводительный алгоритм для разделения нерегулярных графов // Вісник Запорізького державного університету, 2002, № 2, с. 1 – 10.

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2024 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)