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

Размещено на

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

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

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

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

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

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

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

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

на тему

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

Выполнил студент группы 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	Возможность объединения знаний	-	-	-	+ Другие файлы: Разработка алгоритмов и программ Принципы разработки алгоритмов и программ на основе процедурного подхода и на основе объектно-ориентированного подхода. Реализация программы Borland P... Построение аналитических моделей алгоритмов и оценка их сложности Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Ть... Алгоритмизация задач Средства формализации процесса определения спецификаций. Назначение языка (PSL) и анализатора определения задач (PSA). Разработка алгоритма решения за... Разработка алгоритмов и программ решения алгебраических задач численными методами Создание схем алгоритмов и составление программы на языке Pascal для вычисления значений заданных функций. Сущность и порядок нахождения значения опре... Расчет показателей и построение основных элементов защищенных вычислительных сетей. Разработка программной реализации криптографических алгоритмов Описание компонентов сети конфиденциальной связи. Система распределения ключей на основе линейных преобразований. Описание разработанных программ. Кри...