Разработка алгоритмов и программ для определения сходства семантических сетей на основе их сложности

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

Рубрика Программирование, компьютеры и кибернетика
Вид дипломная работа
Язык русский
Дата добавления 17.12.2011
Размер файла 1,3 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Правительство Российской Федерации

Федеральное государственное автономное образовательное учреждение Высшего профессионального образования

"Национальный исследовательский университет

"Высшая школа экономики"

Факультет Бизнес-информатики

Отделение Прикладной математики и информатики

Кафедра Анализа данных и искусственного интеллекта

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА МАГИСТРА

на тему

"Разработка алгоритмов и программ для определения сходства семантических сетей на основе их сложности"

Выполнил студент группы 2мАИД

Климентовский Алексей Николаевич

Научный руководитель:

кандидат технических наук, доцент

Кохов Виктор Алексеевич

Москва 2011

Оглавление

  • Введение
  • 1. Обзор литературы по методам определения сходства графовых моделей систем
  • 1.2 Семантические сети как модели представления знаний
  • 1.3 Основные классы задач сравнительного анализа структур и методы их решения в структурной информатики
  • 1.4 Задачи определения сложности графовых моделей систем и подходы к их решению
  • 2. Метод решения задач определения сходства семантических сетей на основе их сложности
  • 2.1 Постановка задачи определения сходства семантических сетей
  • 2.2 Формализованная постановка задачи определения сходства семантических сетей на основе их сложности
  • 2.3 Метод решения задач различения и определения сходства семантических сетей на основе индексов сложности
  • 2.4 Метод решения задач различения и определения сходства семантических сетей на основе полных структурных спектров
  • 2.5 Метод решения задач различения и определения сходства семантических сетей на основе вектор-индексов сложности
  • 2.6 Сравнительный анализ методов определения сходства
  • 2.7 Основные результаты и выводы по главе
  • 3. Разработанные алгоритмы и их программная реализация
  • 3.1 Алгоритм вычисления индексов, вектор-индексов и полных структурных спектров в базисе полупутей
  • 3.2 Среда программирования и основные характеристики программ
  • 3.3 Теоретические оценки вычислительной сложности разработанных алгоритмов
  • 3.5 Основные результаты и выводы по главе
  • Заключение
  • Список использованных источников
  • Приложения

Введение

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

В настоящее время большинство браузеров использует язык разметки текста HTML (HyperText Markup Language). Представление текста задается с помощью специальных конструкций, которые называются тэгами. Тэги обрабатываются браузером, и в результате на экране можно увидеть списки, таблицы, гиперссылки и другие элементы. Они же могут быть использованы и для семантической разметки страницы. Результатом такой разметки будет семантическая сеть, отражающая знания, представленные в документе. Сравнение такой сети с фрагментами структур из имеющейся базы знаний позволило бы сделать вывод об отнесении данного документа к конкретной тематике.

Одним из возможных подходов к решению задачи сравнения семантических сетей является представление семантической сети в виде граф-модели, структуру которой можно описать некоторыми числовыми характеристиками. При этом, если представить семантическую сеть как граф, выражающий семантические отношения (дуги) между понятиями (вершины), то можно утверждать, что различные сочетания входящих и исходящих дуг, присутствующих в цепях различной длины в значительной степени влияют на сложность рассматриваемой структуры. Исследования, проведенные в этой области Кохов В.А. Концептуальные и математические модели сложности графов. М.: Издательство МЭИ, 2002. - 160 с.

Незнанов А.А., Кохов В.А., Программный комплекс для анализа сходства структур систем. позволяют предполагать, что сравнение графов на основе подсчета числа изоморфных вложений полупутей даст возможность успешно решать задачи различения и сходства. Таким образом, целью данной работы является создание алгоритмов и программ, позволяющих эффективно определять сходство семантических сетей на основе их сложности. На рис.0.1 приведен пример представления семантической информации в виде семантической сети. Логико-вычислительная семантическая сеть (ЛВС-сеть) имеет ряд преимуществ (табл.0.1) перед другими моделями семантической информации, среди которых ПССШ - пропозициональная семантическая сеть, БСС - Блочная семантическая сеть, ПССЛ - процедурная семантическая сеть Десятая национальная конференция по искусственному интеллекту с международным участием. КИИ-2006: Труды конференции. В 3-х т. М.: Физматлит, 2006.. Выделим, что данный класс сетей является орграфами без контуров с весами на вершинах.

Рис.0.1. Пример ЛВС - сети

"Поставщик осуществил поставку изделий по заказу клиента до 1 июня 2004 года в количестве 1000 штук"

Таблица 0.1. Свойства четырех видов семантических сетей

СВОЙСТВА СЕМАНТИЧЕСКИХ СЕТЕЙ

ПССШ

БСС

ПССЛ

ЛВС-сеть

1

Представление знаний в терминах естественного языка

+

+

+

+

2

Представление декларативных знаний

+

+

+

+

3

Представление процедурных знаний

-

-

+

+

4

Представление логических операций

+

+

-

+

5

Представление кванторов

+

+

-

+

6

Представление интенсионала

+

-

-

+

7

Представление экстенсионала

-

-

-

+

8

Представление нечетких знаний

-

-

-

+

9

Наглядность описания знаний

±

±

+

+

10

Выявление и разрешение противоречий

-

-

-

+

11

Возможность объединения знаний

-

-

-

+

1. Обзор литературы по методам определения сходства графовых моделей систем

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

В работе "Методы анализа сходства графов сходства расположения цепных фрагментов в графе" приведен алгоритм вычисления вкладов цепных фрагментов в общую сложность графа, а также сравнения графов с учетом расположения цепей. Кохов В.А., Методы анализа сходства графов и сходства расположения цепных фрагментов в графе В статье "Программный комплекс для анализа сходства структур систем" Незнанов А.А. и Кохов В.А. описывают архитектуру программного комплекса, реализованного в виде подсистемы АСНИ "Graph Model Workshop", дающего возможность анализировать сходства графовых моделей систем.

Многие основные понятия и области применения графовых моделей даны в статье "Структурная информатика - новый актуальный раздел информатики для изучения в школе и в университете" (Кохов В.А., Незнанов А.А., Ткаченко С. В.). Кохов В.А., Незнанов А.А., Ткаченко С.В., Структурная информатика - новый актуальный раздел

информатики для изучения в школе и в университете, Совещание "Актуалные проблемы информатики в современном российском образовании", Москва, 2004

Многочисленные теоретические выкладки об интеллектуальных системах предложены в работах Финна В.К. В статье "Искусственный интеллект: идейная база и основной продукт" описывается процесс выделения знаний посредством интеллектуальных систем.

В книге "Моделирование рассуждений. Опыт анализа мыслительных актов" Поспелова Д.А. дано научно-популярное толкование интеллектуальных систем и семантических сетей.

1.1 Основные определения

Семантическая сеть является одной из моделей представления знаний. Знания - это закономерности предметной области (принципы, связи, законы), полученные в результате практической деятельности и профессионального опыта, позволяющие специалистам ставить и решать задачи в этой области. Знания основаны на данных, полученных эмпирическим путем. Они представляют собой результат мыслительной деятельности человека, направленной на обобщения его опыта, полученного в результате практической деятельности. Знания - это хорошо структурированные данные, или данные о данных, или метаданные. Гаврилова Т.А., Хорошевский В.Ф., Базы данных интеллектуальных систем, Издательский дом "Питер"., 2001.

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

Сеть можно определить как "пятерку Н = <A, B, P, P1, C>, где А - множество вершин, В - множество имен (весов) вершин; Р - множество дуг, соединяющих пары вершин; Р1 - множество отмеченных входных и выходных дуг; С - множество имен (весов) дуг". Аверкин А.Н., Гаазе-Рапопорт М.Г., Поспелов Д.А., Толковый словарь по искусственному интеллекту; http: //raai.org/library/tolk/aivoc.html Семантическая сеть представляет собой сеть, в вершинах которой находятся информационные единицы, а дуги характеризуют отношения и связи между ними.

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

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

Онтологии разрабатываются и могут быть использованы при решении различных задач, в том числе для совместного применения людьми или программными агентами, для возможности накопления и повторного использования знаний в предметной области, для создания моделей и программ, оперирующих онтологиями, а не жестко заданными структурами данных, для анализа знаний в предметной области. Важно отметить, что формализации понятий есть предмет соглашения (ontological commitments [онтологические обязательства]) использующего их профессионального сообщества. Рубашкин В.Ш., Онтологическая инженерия в системах, основанных на знаниях.

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

Класс "издательство". Атрибуты: название (строка); город (строка).

Класс "книга". Атрибуты: название (строка); автор (строка); число страниц (натуральное число); издательство (экземпляр класса "издатель") и т.д.

Класс "журнал". Атрибуты: название (строка); издательство (экземпляр класса "издатель"); год выпуска (натуральное число - четыре цифры); номер (натуральное число) и т.д.

Поскольку классы "книга" и "журнал" имеют много общих атрибутов (полей), имеет смысл вынести их в отдельный класс под названием "печатная продукция". Кальченко Даниил, Интеллектуальные агенты семантического Web'а; http: //www.compress.ru/Archive/CP%5C2004%5C10%5C48/

Рис.1.1 Фрагмент онтологии издательства с классами и экземплярами классов (орграф без контуров с весами на вершинах).

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

1.2 Семантические сети как модели представления знаний

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

Несмотря на то, что базовые отношения определяются спецификой проблемной области, тем не менее, существует набор универсальных отношений, присутствующих практически во всех задачах. Речь идет об отношениях типа "элемент - множество" (ЭЛ), "подмножество - множество" (ПМ), "часть - целое" и т.д. Именно эти отношения позволяют структурировать знания о проблемной области.

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

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

Можно привести другой более наглядный пример семантической сети.

Рис.2. Семантическая сеть для понятия "автомобиль".

Основные достоинства семантических сетей как метода представления знаний следующие: Гаврилов А.В., Семантические сети. Представление знаний в информационных системах (курс лекций);

http: //www.insycom.ru/html/metodmat/pz/Lect5_1. pdf

· Наглядность и понятность.

· Легкость преобразования в логику предикатов 1-го порядка.

Недостатки:

· Трудно обозревать большую семантическую сеть.

· Не достаточная структурированность.

1.3 Основные классы задач сравнительного анализа структур и методы их решения в структурной информатики

Задачи сравнительного (пространственного) анализа - это задачи выявления закономерностей в некоторых показателях, полученных для различных единиц, а также задачи сравнения показателей конкретной исследуемой структуры с аналогичными показателями соседних структур, со средними данными. Стерин А., Цейтлин Д. Возможности использования статистических средств SAS System для решения аналитических задач в области финансов и бизнеса

Понимание семантической информации семантическим объектом (ЭВМ) определяется в ИСС посредством сравнения предлагаемой семантической информации с эталонной по смыслу. С помощью сравнения выявляются количественные и качественные характеристики объектов, классификация, упорядочение и пр. Сравнить - это значит сопоставить одно с другим, с тем, чтобы выявить их возможные отношения. Сравнение имеет смысл только в совокупности "однородных по сложности" объектов, образующих предметную область. Кохов В.А., Незнанов А.А., Ткаченко С.В., Структурная информатика - новый актуальный раздел информатики для изучения в школе и в университете, Совещание "Актуалные проблемы информатики в современном российском образовании", Москва, 2004.

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

Таким образом, понимание - сравнение (изоморфизм, не изоморфизм, сходство) и принятие решения - можно рассматривать как основную семантическую операцию.

Важным понятием в интеллектуальных семантических системах (ИСС) является понятие структуры, которое используется в двух основных значениях:

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

2. Как атрибут ИСС, необходимый для формального описания ИСС.

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

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

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

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

1.4 Задачи определения сложности графовых моделей систем и подходы к их решению

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

Базовые граф-модели, предложенные в Коховым и Ткаченко Кохов В.А., Ткаченко С.В. Метод иерархического исследования сходства структур систем. // Науч. Сессия МИФИ-2004: Т.З. М: МИФИ, 2004 - с. 184-185. строятся на основе порождающих и являются их инвариантами, характеризующими расположение любых фрагментов в топологии графа на основе использования расширяемых базисов СД. Примеры базисов структурных дескрипторов B=<b1,b2,.,bi,.,bk>: простые связные цепи, деревья, все связные фрагменты, примарные фрагменты и др. Они являются представительным классом инвариантов структур, обладающих свойством наследования значений по отношению вида "часть-целое". Такие инварианты необходимы для сокращения перебора при решении NP-полных задач структурного анализа и синтеза систем.

Центральное место в структурном спектральном анализе занимает иерархическая модель характеризации структурной сложности систем. Эта модель обобщает ранее известные подходы и позволяет стратифицировано по степени точности базиса структурного дескриптора характеризовать структурную спектральную сложность и на ее основе решать задачи различения, упорядочения, анализа сходства и прорисовки диаграмм структур систем, представленных порождающими и базовыми граф-моделями. Можно выделить несколько основных уровней анализа сложности (сходства): Кохов В.А., Незнанов А.А., Ткаченко С.В., Структурная информатика - новый актуальный раздел информатики для изучения в школе и в университете, Совещание "Актуалные проблемы информатики в современном российском образовании", Москва, 2004.

· Сложность на основе индексов сложности.

· Сложность на основе вектор-индексов относительных вкладов классов фрагментов по каждому типу фрагментов.

· Сложность на основе вектор-индексов относительных вкладов фрагментов, с компонентами, упорядоченными по признаку уменьшения значения вклада фрагмента, по каждому типу фрагментов

· Сложность на основе полных структурных спектров в разных базисах структурных дескрипторов.

· Сложность на основе вектор-индексов сложности.

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

расположение фрагментов в структуре системы;

структурную сложность систем с учетом вкладов фрагментов;

структурное сходство систем с учетом вкладов фрагментов;

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

Разнообразие фрагментов систем, фрагментов базиса СД и

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

семантическая сеть модель знание

2. Метод решения задач определения сходства семантических сетей на основе их сложности

2.1 Постановка задачи определения сходства семантических сетей

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

Семантическую сеть можно построить также и на некотором множестве текстов. Тогда сравнение ее фрагментов с соответствующими структурами других текстов может позволить сделать вывод о принадлежности этого текста тематике, описанной данным множеством. Для этого можно выделить так называемое тематическое дерево, которое является минимальным остовным деревом семантической сети. Такое дерево позволяет хранить содержание текста и производить навигацию по нему, т.е. является рефератом или оглавлением. "Исходный текст (множество текстов) вместе с их семантической сетью представляет собой гипертекстовую структуру и является одновременно хранилищем текстов и базой знаний". Харламов Александр, Автоматический структурный анализ текстов, "Открытые системы", № 10, 2002;

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

2.2 Формализованная постановка задачи определения сходства семантических сетей на основе их сложности

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

Определим понятия пути и полупути. Знаковые графы и орграфы и их применение при моделировании и анализе сложных проблем в экологии, психологии и политике;

http: //www.allmath.ru/highermath/algebra/diskret-dubna/Ll10_11.html Под путем в ориентированном графе G = (V, E) понимается последовательность вершин и дуг v1, e1, v2, e2,., vt, et, vt+1, где t ? 0, причем каждая вершина vi О V, а каждая дуга ei О E, и ei всегда является дугой (vi, vi+1). Полупуть в ориентированном графе G = (V, E) есть последовательность вершин и дуг v1, e1, v2, e2,., vt, et, vt+1, где t ? 0, причем каждая вершина vi О V, а каждая дуга eiО E, и ei всегда является либо дугой (vi, vi+1), либо дугой (vi+1, vi). Важно заметить, что каждая дуга может входить в путь или полупуть не более одного раза, т.е. для любого пути или полупути любых v1, a1, v2, a2,., vt, at, vt+1, где t ? 0 и любых i, j таких, что

0 < i, j ? t, справедливо ui ? uj. При этом любая вершина есть путь и полупуть длины 0, а любая дуга также является и путем, и полупутем длины 1.

Пусть L обозначает множество весов для вершин и дуг ориентированного графа без контуров (ОГБК). Под ациклическим орграфом (АОГ) будем понимать орграф G= (V,E,,) без контуров, в котором: (1) V - конечное множество вершин; (2) E VЧV - множество дуг; (3) : V L есть функция соотнесения весов вершинам ОГБК; (4) : E L есть функция соотнесения весов дугам ОГБК. Джасим Малатх Рахим Разработка методов и программных средств для решения задач различения и анализа сложности ациклических структур. Автореферат диссертации к. т. н., М. МЭИ. 2010, 20 с.

Орграф GS= (VS,ES,S,S) будем называть подграфом (порожденным подграфом) G= (V,E,,), то есть GSG, если: (1) VSV; (2) vVS [ (v) =S (v)]; (3) ES=E (VSЧVS); (4) eES [ (e) =S (e)].

Орграф GP= (VP,EP,P,P) будем называть частичным орграфом G= (V,E,,), то есть GPPG, если: (1) VP=V; (2) vVP [ (v) =P (v)]; (3) EPE; (4) eEP [ (e) =P (e)].

Орграф GPS= (VPS,EPS,PS,PS) будем называть частичным подграфом орграфа G= (V,E,,), то есть GPSG, если: (1) VPSV; (2) vVPS [ (v) =PS (v)]; (3) EPSE (VPSЧVPS); (4) eEPS [ (e) = PS (e)].

Под изоморфизмом (GG*) двух взвешенным по вершинам и дугам орграфов G= (V,E,,) и G*= (V*,E*,*,*) будем понимать 1-1 соответствие : VV*, такое, что: (1) vV [ (v) =* ( (v))]; (2) e= (u,w) E e*= ( (u), (w)) E*, такое что [ (e) = (e*)] и e*= (u*,w*) существует дуга e= (1 (u), 1 (w)) E, такая что (e) =* (e*)].

Если : VV* есть изоморфизм между орграфами G и G* и G*SG** (G*PG**, G*PSG**), то будем называть изоморфизмом подграфу (частичному графу, частичному подграфу) орграфа G**. Общий случай, связанный с объединением изоморфизма частичному графу и частичному подграфу будем называть изоморфизмом фрагменту и обозначать f.

Пусть B=<b1, b2,,…,bi,…,bk1> обозначает базис структурных дескрипторов (СД), определяющий точность характеризации ориентированного графа. Тогда под структурным спектром G в базисе СД B=<b1, b2,,…,bi,…,bk1> будем понимать запись следующего вида SS (G/B) 1b1, в2b2, …, вibi, вk1bk1, где вi=1, если фрагмент bi?B изоморфно вкладывается в G и вi=0 в противном случае.

Пусть для орграфа G построен его полный структурный спектр (ПСС) в базисе СД: В= (b1, b2,., bi,., bk1): FSS (G/B) = (w1b1, w2b2,., wibi,., wk1bk1), где bi - фрагмент базиса; wi - число канонических изоморфных вложений фрагмента bi в G; k1 число фрагментов базиса B, относительно которого характеризуется сложность G.

Пусть HP=<HP1, HP2,…, HPi,…HPn> обозначает базис полупутей-фрагментов, где i - порядковый номер полупути. Тогда можно вычислить следующие величины и векторы значений:

SS (G/HP) - вектор значений <ss1,…, ssi>, где ssi = 1, если фрагмент базиса присутствует в графе G, и 0 в противном случае.

FSS (G/HP) - вектор значений <fss1,…, fssi>, где fssi показывает число вхождений фрагмента i-ого базиса полупутей в граф G.

ISC (HPi) - величина, характеризующая сложность полупути HPi или индекс сложности фрагмента-полупути.

Итак, пусть заданы два оргафа без контуров G1= (V1,E1), G2= (V2,E2). Необходимо выяснить, существует ли взаимно однозначное соответствие между множествами V1,V2, которое сохраняет отношение смежности, то есть G*G2, или:

: V1V2 и vi,vjV1 [ (vi,vj) E1 ( (vi), (vj)) E2], где (vi), (vj) V2?

Поскольку данная задача принадлежит к классу NP Андерсон, Джеймс А., Дискретная математика и комбинаторика: Пер. с англ. - М.: Издательский дом "Вильямс", 2003. ,

Обычно полупути, содержащему только одну вершину, сопоставлен порядковый номер базиса полупути i=1, а полупути содержащему одну дугу - порядковый номер i=2. Тогда ISC (HP1) и ISC (HP2) - индексы сложности, соответствующие полупути вида "вершина" и вида "дуга". Они задаются исследователем, и, зная их, можно вычислить все ISC (HPi) для i > 2. Для того, чтобы это сделать необходимо воспользоваться аналогичными характеристиками для индекса сложности в базисе путей-фрагментов. Кохов В.А., Кохов В.В., Метод решения задачи различения орграфов на основе сложности, БИЗНЕС-ИНФОРМАТИКА №1 (15) - 2011 г.

Пусть P=<P0, P1,…, Pi,…, P (p-1) > обозначает базис путей-фрагментов, где Pi - путь с числом дуг i Зададим ISC (P0) и ISC (P1).

Тогда можно выразить ISC (P2) = 3ISC (P0) +2ISC (P1).

Для i > 3 можно рекурсивно вычислить ISC (Pi) по следующей формуле:

ISC (Pi) = 2 * ISC (Pi-1) + 3 * ISC (Pi-2) + 4 * ISC (Pi-3) +. + (n+1) * ISC (Pi-n),

для всех n таких, что i - n ? 0. В целях упрощения программной реализации можно заметить, что

ISC (Pi-1) = 2 * ISC (Pi-2) + 3 * ISC (Pi-3) +. + n * ISC (Pi-n).

Тогда получаем:

ISC (Pi) = 3 * ISC (Pi-1) +

Приведем пример. Пусть задано, что ISC (P0) = 1, ISC (P1) = 3, тогда:

ISC (P2) = 3 * ISC (P0) +2 * ISC (P1) = 9;

ISC (P3) = 2 * ISC (P2) + 3 * ISC (P1) + 4 * ISC (P0) = 2*9 + 3*3 + 4*1 = 31;

или воспользовавшись второй формулой:

ISC (P3) = 3 * ISC (P2) + = 3*9 + 3 + 1 = 31;

также можно вычислить и все другие результаты:

ISC (P4) = 3 * 31 + 9 + 3 + 1 = 106;

ISC (P5) = 3 * 106 + 31 + 9 + 3 + 1 = 362;

Рис.2.1 Вложенность фрагментов-путей в путь длины 4.

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

Рис.2.2 Вычисление индекса сложности полупути на 8 вершинах.

Заметим, что нам неважно направление пути, а важна только его длина. Таким образом, можно задать максимальную длину полупути l и вычислить для всех полупутей длины от 0 до l включительно соответствующие индексы сложности. Стоит сказать, что с ростом l число различных полупутей увеличивается экспоненциально. Если l нечетно, то число неповторяющихся полупутей длины l будет 2l-1. Если же l четно, то это будет число, несколько превосходящее 2l-1, но сравнительно малое по сравнению с этой величиной. (Эксперименты показали, что эта величина составляет 2l/2 - 1) Это происходит из-за того, что для каждого полупути нечетной длины существует симметричный ему полупуть. Симметричность в данном случае означает, что если этот полупуть перевернуть и каждую дугу поменять на дугу с противоположным направлением, то получим ровно тот же полупуть. Однако для l четной длины существует некоторое количество полупутей, симметричные которым представляют собой эти же самые полупути. На основании сделанного предположения о числе "дополнительных" по отношению к количеству 2l-1 полупутей, можно утверждать, что число таких полупутей, для которых симметричные им полупути отсутствуют, составляет величину 2l/2.

Рис.2.3 Базис полупутей длины l=3. Рис.2.4 Базис полупутей длины l=2.

Зная число изоморфных вложений каждого из полупутей в орграфе, можно подсчитать вектор индексов сложности полупутей. То есть количество вхождений каждого из фрагментов в орграф умножить на соответствующий ему индекс сложности в базисе полупутей. Имея вектор частоты вхождений соответствующих фрагментов в орграф FSS и вектор - индекс сложности V_ISC (HP), проведем их покоординатное умножение. Полученный вектор есть вектор индексов сложности полупутей V_ISC (G/HP). Сложив все координаты полученного вектора V_ISC (G/HP), получим ISC (G/HP) - индекс сложности орграфа G.

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

2.3 Метод решения задач различения и определения сходства семантических сетей на основе индексов сложности

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

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

Рис.2.5 Сравнение индексов сложности графов.

Для базисов полупутей различной длины и заданных индексов сложности вершины и дуги мы получаем разные результаты. Пусть, как и раньше индекс сложности вершины ISC (P0) = 1, индекс сложности дуги ISC (P1) = 3. Рассмотрим индексы сложности представленных на рис.2.5 графов в зависимости от выбранной максимальной длины полупути l в базисе полупутей.

l = 3: ISC (G1/HP) = 301; ISC (G2/HP) = 301; ISC (G3/HP) = 319;

l = 4: ISC (G1/HP) = 559; ISC (G2/HP) = 559; ISC (G3/HP) = 649;

l = 5: ISC (G1/HP) = 721; ISC (G2/HP) = 721; ISC (G3/HP) = 883.

Для графов G1 и G2 не выявлено структурных различий. Однако индекс графа G3 превосходит по величине индексы сложности для G1 и G2. Причем, чем больше число l, тем больше это отличие по абсолютной величине.

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

2.4 Метод решения задач различения и определения сходства семантических сетей на основе полных структурных спектров

Полные структурные спектры позволяют подробно изучить вложенность различных фрагментов-полупутей в орграф, задающий семантическую сеть. Как было указано ранее, полный структурный спектр представляется вектором FSS (G/HP) - вектор значений <fss1,…, fssi>, где fssi показывает число вхождений фрагмента i-ого базиса полупутей в орграф G.

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

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

Для каждого из орграфов, изображенных на рис.2.5, можно рассчитать соответствующий ему полный структурный спектр, используя те же значения для индекса сложности вершины и индекса сложности дуги. (базис полупутей для l=3 представлен на рис.2.3, базисы полупутей для l=4 и l=5 не приводятся в целях экономии места).

l = 3:

FSS (G1/HP) =<4 5 2 4 2 0 4 6 2>;

FSS (G2/HP) =<4 5 2 2 4 0 2 6 4>;

FSS (G3/HP) =<4 5 2 3 3 0 4 4 4>;

l = 4:

FSS (G1/HP) =<4 5 2 4 2 0 4 6 2 2 4 2 2 2 0 0 0 0 0>;

FSS (G2/HP) =<4 5 2 2 4 0 2 6 4 4 2 2 2 2 0 0 0 0 0>;

FSS (G3/HP) =<4 5 2 3 3 0 4 4 4 0 0 2 2 6 1 1 0 0 0>;

l = 5:

FSS (G1/HP) =<4 5 2 4 2 0 4 6 2 2 4 2 2 2 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0>;

FSS (G2/HP) =<4 5 2 2 4 0 2 6 4 4 2 2 2 2 0 0 0 0 0 2 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0>;

FSS (G3/HP) =<4 5 2 3 3 0 4 4 4 0 0 2 2 6 1 1 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0>.

Можно увидеть, что по полному структурному спектру орграфы имеют различия, начиная с 4-ой координаты (полупути длины 2 соответствуют координатам вектора с порядковыми номерами 3, 4,5). Сравнивая орграфы по полному структурному спектру, можем заметить, что все они различны, хотя число фрагментов-полупутей одной длины без учета направления дуг для всех одинаково.

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

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

2.5 Метод решения задач различения и определения сходства семантических сетей на основе вектор-индексов сложности

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

V_ISC (G/B) =<w1ISC (b1); w2ISC (b2); …; wiISC (bi); …; wk1ISC (bk1) >,

где за wi обозначен веc i-ой компоненты, который в нашем случае является индексом сложности i-ого полупути ISC (HPi). Вектор-индекс позволяет рассмотреть количественный вклад каждого полупути в индекс сложности орграфа, а также сопоставить соответствующие значения wiISC (HPi) для двух структур.

Снова воспользуемся графами на рис.2.5 и подсчитаем для них вектор-индексы сложности. Положим индекс сложности вершины ISC (P0) = 1, индекс сложности дуги ISC (P1) = 3.

l = 3:

V_ISC (G1/HP) =<4 15 18 36 18 0 88 78 44>;

V_ISC (G2/HP) =<4 15 18 18 36 0 44 78 88>;

V_ISC (G3/HP) =<4 15 18 27 27 0 88 52 88>;

l = 4:

V_ISC (G1/HP) =< 4 15 18 36 18 0 88 78 44 34 68 52 52 52 0 0 0 0 0 >;

V_ISC (G2/HP) =<4 15 18 18 36 0 44 78 88 68 34 52 52 52 0 0 0 0 0>;

V_ISC (G3/HP) =<4 15 18 27 27 0 88 52 88 0 0 52 52 156 35 35 0 0 0>;

l = 5:

V_ISC (G1/HP) =< 4 15 18 36 18 0 88 78 44 34 68 52 52 52 0 0 0 0 0 42 60 60 0 0 0 0 0 0 0 0 0 0 0 0 0 >;

V_ISC (G2/HP) =<4 15 18 18 36 0 44 78 88 68 34 52 52 52 0 0 0 0 0 42 0 0 60 60 0 0 0 0 0 0 0 0 0 0 0>;

V_ISC (G3/HP) =<4 15 18 27 27 0 88 52 88 0 0 52 52 156 35 35 0 0 0 0 0 0 0 0 78 78 78 0 0 0 0 0 0 0 0>.

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

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


Подобные документы

  • Средства формализации процесса определения спецификаций. Назначение языка (PSL) и анализатора определения задач (PSA). Разработка алгоритма решения задачи, критерии оценки его сложности. Локальный и глобальный уровни повышения эффективности алгоритмов.

    контрольная работа [144,9 K], добавлен 26.10.2010

  • Классы и группы моделей представления знаний. Состав продукционной системы. Классификация моделей представления знаний. Программные средства для реализации семантических сетей. Участок сети причинно-следственных связей. Достоинства продукционной модели.

    презентация [380,4 K], добавлен 14.08.2013

  • Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова.

    курсовая работа [1,5 M], добавлен 07.07.2013

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

    реферат [90,6 K], добавлен 27.11.2012

  • Представление знаний в когнитологии, информатике и искусственном интеллекте. Связи и структуры, язык и нотация. Формальные и неформальные модели представления знаний: в виде правил, с использованием фреймов, семантических сетей и нечетких высказываний.

    контрольная работа [29,9 K], добавлен 18.05.2009

  • Принципы разработки алгоритмов и программ на основе процедурного подхода и на основе объектно-ориентированного подхода. Реализация программы Borland Pascal 7.0, ее интерфейс. Разработка простой программы в среде визуального программирования Delphi.

    отчет по практике [934,7 K], добавлен 25.03.2012

  • Решение задачи средствами прикладных программ. Разработка алгоритмов и структур данных. Реализация задачи определения статистических данных по успеваемости на факультете на языке программирования C#. Программа перевода чисел в различные системы счисления.

    курсовая работа [519,9 K], добавлен 03.01.2015

  • Составление и программная реализация в среде Borland Delphi 7.0 алгоритмов итерационного и рекурсивного вариантов решения задачи поиска с возвращением. Исследование асимптотической временной сложности решения в зависимости от количества ячеек на плате.

    курсовая работа [57,5 K], добавлен 25.06.2013

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

    курсовая работа [36,6 K], добавлен 25.06.2013

  • Понятие алгоритма и анализ теоретических оценок временной сложности алгоритмов умножения матриц. Сравнительный анализ оценки временной сложности некоторых классов алгоритмов обычным программированием и программированием с помощью технологии Open MP.

    дипломная работа [1,6 M], добавлен 12.08.2017

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.