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