Разработка алгоритмов и программ для определения сходства семантических сетей на основе их сложности
Семантические сети как модели представления знаний. Основные методы определения сходства графовых моделей систем. Метод решения задач определения сходства семантических сетей на основе их сложности. Разработка алгоритмов и их программная реализация.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 17.12.2011 |
| Размер файла | 1,3 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
2.6 Сравнительный анализ методов определения сходства
Итак, различные методы определения сходства позволяют получить разную информацию о сравниваемых структурах. Как было показано выше, индексы сложности орграфов позволяют оценить сложность структуры одним числом. Индекс сложности позволяет произвести предварительную оценку двух структур и понять степень их сходства. Можно утверждать, что если разница двух индексов сопоставима по величине с индексом сложности одного из орграфов, то эти орграфы обладают различной структурой. Таким образом, индекс сложности - самая простая мера сравнения двух структур, которую можно использовать, чтобы отфильтровать структуры с индексами сложности в заданном диапазоне.
Однако, при этом возникают некоторые проблемы. Индексы сложности могут незначительно отличаться для двух орграфов, если в одном из них много путей меньшей длины и при этом отсутствуют пути большей длины, а другой состоит из одного или несколько путей большей длины. Так, например, в базисе полупутей с максимальной длиной l=6 орграфы G2 и G1 имеют одинаковые индексы сложности 721. В то же время простой путь длины 6 имеет индекс сложности 724.
С другой стороны, различные структуры могут иметь одинаковый индекс сложности и быть лишь отчасти похожими по числу входящих в них фрагментов-полупутей. Так, например, для орграфов G1 и G2 для любого l индексы сложности совпадают, однако, в них имеют структурные отличия. Распознать эти отличия призван полный структурный спектр орграфа.
Вектор полного структурного спектра позволяет описать, сколько каких компонент содержит каждая из структур. Как уже говорилось, если орграфы неизоморфны, то их полные структурные спектры будут различаться. Тем не менее, этот метод не обладает метрикой, позволяющей описывать вклад фрагментов-полупутей и говорить о схожести неизоморфных орграфов.
Метод на основе вектор-индексов сложности призван соединить в себе достоинства обоих методов. С одной стороны, он позволяет описать вклад каждой из компоненты и при необходимости получить индекс сложности орграфа как ||V_ISC (G/HP) ||1. C другой, структурные отличия будут выражены в разнице соответствующих координат вектор-индекса для двух орграфов.
Таким образом, чтобы оценить общую сложность структуры, стоит использовать индекс сложности орграфа. Чтобы выявить точные различия вложенных фрагментов-полупутей, используется полный структурный спектр. Вектор-индексы сложности позволяют провести более детальный анализ как вложений фрагментов-полупутей, так и их вкладов в сложность орграфа.
2.7 Основные результаты и выводы по главе
Семантическую сеть входного текстового документа можно сравнить с семантическими сетями рубрик, что позволяет сделать вывод об отнесении данного текста к определенной тематике, т.е. решать задачу классификации. Для сравнения структур предложена граф-модель, которая предоставляет методы сравнения орграфов на основе их сложности.
Описанная модель позволяет рассматривать орграф как совокупность вложенных фрагментов, каждый из которых имеет собственную сложность. Граф-модель семантической сети позволяет рассчитать несколько величин для сравнения: индекс сложности орграфа, полный структурный спектр и вектор-индекс сложности.
Показано, что индекс сложности орграфа является более слабым показателем по сравнению с полным структурным спектром и вектор-индексом сложности. Все три метода позволяют выявлять различия и сходства орграфов как с точки зрения повторяющихся в них фрагментов, так и с точки зрения веса каждого из этих фрагментов при оценке сложности орграфа.
3. Разработанные алгоритмы и их программная реализация
3.1 Алгоритм вычисления индексов, вектор-индексов и полных структурных спектров в базисе полупутей
Для вычисления полных структурных спектров, индексов и вектор-индексов сложности был разработан алгоритм, использующий известные алгоритмы и структуры данных. По сути, процесс вычисления необходимых значений можно разделить на две части: построение структуры, содержащей индексы сложности для каждого полупути и обход орграфа с подсчетом встречающихся полупутей. В конце выполняется покоординатное умножение вектора индексов сложности на соответствующий вектор частот полупутей.
Итак, для хранения индексов сложности полупутей использовались бинарные деревья, обладающие свойством пирамиды. Пирамида (binary heap) - это структура данных, представляющая собой объект-массив, который можно рассматривать как почти полное бинарное дерево. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, МЦНМО, 2000. Представляющий пирамиду массив patternTree является объектом с атрибутом size [patternTree], содержащим количество элементов массива. В корне дерева находится элемент patternTree [1]. Для каждого из остальных элементов выполняется следующее важное нам свойство пирамиды, а именно: для любого узла с индексом i индекс родительского узла вычисляется как , индекс левого дочернего узла - 2i, индекс правого дочернего узла - 2i+1. Это позволяет за минимальное время "ходить" по пирамиде с помощью битового сдвига числа i на один бит влево или вправо. (Операция 2i+1 выполняется битовым сдвигом влево, а также установкой младшего бита равным 1).
В каждом из узлов дерева хранится индекс сложности (complexity), вектор направлений дуг в порядке их следования на пути от вершины в данный узел (way), а также порядковый номер соответствующего вектору направлений дуг полупути (number), значение которого задается вручную для первых 15 вершин, а для остальных инициализируется нулем.
Рис.3.1 Представление дерева. Указаны наборы значений, которые хранятся в узлах дерева с индексом 1, 2, 3, 5, 10, 14.
Как можно понять из рисунка, переход в левый дочерний узел означает, что к пройденному полупути добавилась дуга ведущая в вершину (IN), из который мы только что пришли. Переход в правый дочерний узел означает, что добавилась дуга ведущая из вершины (OUT). Важно заметить, что все пути хранятся в этом дереве по краям, то есть если идти всегда по OUT, или идти всегда по IN. IN и OUT будем считать значениями, которые может принимать переменная типа DIRECTION.
Найдем все вершины в дереве такие, что длина пути от каждой из них до вершины дерева одна и та же для каждой из этих вершин. Тогда данные вершины являются вершинами одного уровня или находятся на одном уровне. Причем, номер этого уровня есть длина пути до вершины. К примеру, вершины 8, 9, 10, 11, 12, 13, 14, 15 лежат на уровне 3. Важно заметить, что каждый уровень level начинается с вершины с индексом 2level и заканчивается вершиной 2level - 1.
Пусть максимальная длина полупути, для которой будет построен базис, задается в качестве параметра l. Тогда самый нижний уровень дерева есть level = l. Построение недостающих уровней дерева происходит поочередно, то есть пока не завершено построение предыдущего уровня, построение следующего не начинается. Так сделано, потому что индекс сложности вершины на уровне l' зависит только от индексов сложности вершин на уровнях от 1 до l' - 1.
Алгоритм получает на вход 3 параметра:
1) уже описанный параметр l, который является также и высотой дерева;
2) индекс сложности вершины p (в примере на рис.8 p=1);
3) индекс сложности дуги q (в примере q=3). Уровни 0, 1, 2, 3 заполняются уже известными значениями. Остальные вершины заполняются значениями в порядке, определенном порядком их индексов.
Допустим, мы находимся на уровне l'. Пусть все предыдущие вершины уровня обработаны и мы находимся в вершине v. Тогда по индексу v можно определить ее отца и можно определить, является она левым или правым ребенком. Если левым, то мы берем значение way родительской вершины и добавляем в него IN, в противном случае OUT. Очевидно, что число вершин больше числа элементов way на 1. Пусть length [x] означает длину массива х. Можно пронумеровать все вершины полупути с порядком дуг, заданным way, числами от 1 до n, где n-1 = length [way].
Тогда для каждой вершины от 1 до n-1 включительно будем искать все пути в дереве, которые начинаются или заканчиваются в этой вершине и прибавлять их индексы сложности к v.comlexity. При этом мы запоминаем путь coveredWay, который уже прошли, в виде массива из DIRECTION. То есть для каждой вершины от 1 до n-1 делаем следующее:
1. Прибавляем к v.comlexity индекс сложности соответствующий coveredWay в дереве.
2. Смотрим на новое DIRECTION dir в way.
3. Если оно равно последнему добавленному в coveredWay или length [coveredWay] == 0,то добавляем dir в [coveredWay].
4. В противном случае очищаем [coveredWay] и переходим к следующей вершине.
Помимо указанной процедуры можно добавить проверку, которая не позволяет прийти в нашу вершину v и прибавлять ее индекс сложности. Для этого достаточно между строками 1 и 2 вставить проверку того, что length [coveredWay] < length [way].
Проделав все процедуры для каждой из вершин от 1 до n-1 включительно, остается прибавить к v.comlexity индекс сложности, соответствующей одной неисследованной вершине с номером n. Этот индекс, очевидно, равен patternTree [1].complexity:
v.comlexity = v.complexity + patternTree [1].complexity.
В итоге мы получаем дерево фрагментов-полупутей или шаблонов, которое будем использовать для поиска встречаемых в графе полупутей. Однако, это не все. Теперь необходимо пронумеровать каждый из шаблонов. Эту процедуру можно провести отдельно для каждого уровня. Зная что на трех уровнях содержится 9 различных видов полупутей, нумерация шаблонов следующего уровня начнется с 10. В итоге мы можем написать функцию SortNumbersAtLevel, которая получает номер уровня, первый свободный номер freeNumber, раздает номера вершинами и возвращает следующий свободный номер. В силу условий исследования эта функция раздает номера шаблонам в порядке возрастания их индексов сложности. Если же индексы сложности равны, то в произвольном порядке.
Итак, функция SortNumbersAtLevel делает следующее:
1. Извлекает все вершины одного уровня из дерева в массив processed.
2. Сортирует в processed все вершины по возрастанию индекса сложности
3. Дает номера каждой из вершин в порядке возрастания их индексов сложности, что производится функцией giveNumber.
4. Ищет по атрибуту way соответствующую вершине из processed вершину из patternTree и присваивает ей номер данной вершины в processed.
5. возвращает freeNumber.
Все это происходит, потому что половину или почти половину всех вершин дерева patternTree составляют вершины, для полупутей которых можно найти симметричные. Напомним, что симметричность означает, что если этот полупуть перевернуть и каждую дугу поменять на дугу с противоположным направлением, то получим ровно тот же полупуть. Для этого и вызывается процедура giveNumber. Для каждой вершины v уже отсортированного массива вершин processed:
1. Если v. number == 0
2. Присваиваем v. number значение freeNumber.
3. freeNumber = freeNumber + 1.
4. Для каждой из оставшихся вершин v' с индексом сложности, не превосходящим v.complexity и значением number, равным 0:
5. Смотрим, является ли v'. way симметричным v. way
6. Если да,
присваиваем v'. number значение v. number
и переходим к следующей вершине в processed.
Наконец, мы построили дерево шаблонов. Из него можно построить массив, в котором порядковые номера элементов будут соответствовать порядковым номерам number, и каждый элемент будет содержать соответствующий индекс сложности. Очевидно, что его размер равен freeNumber - 1. Мы получили программную реализацию V_ISC (HP).
Для того, чтобы посчитать количество вхождений каждого из фрагментов-полупутей нам потребуется массив размером freeNumber - 1. Числа в массиве будут показывать число вхождений каждого из фрагментов-полупутей. Очевидно, что в результате мы получим полный структурный спектр, то есть FSS (G/HP). Так и обозначим массив.
Обход графа выполняем рекурсивной процедурой DFSsearch, которая получает на вход уже пройденный путь coveredWay, аналогичный описанному выше, а также вершину с индексом currentVertex, которую сейчас будем обрабатывать. Находим номер пути currentVertex. number, заданного последовательностью дуг coveredWay в построенном ранее дереве patternTree. Увеличиваем координату в FSS (G/HP) по индексу currentVertex. number на 1.
Если length [coveredWay] меньше параметра l (максимальная глубина дерева или максимальная длина полупути в базисе), то для каждой из смежных вершин oneMoreVertex смотрим, ходили ли мы по ребрам ведущим к ним (окрашены ли они в цвет GRAY). Если нет, то добавляем направление этого ребра в coveredWay, красим дугу цветом GRAY и вызываем рекурсивную процедуру DFSsearch для coveredWay и OneMoreVertex. Следующей строкой кода перекрашиваем дугу, которую красили до вызова DFSsearch (coveredWay, oneMoreVertex), обратно белым, чтобы вернуть графу нетронутый программистом вид для обхода из следующей вершины.
Таким образом, мы обошли все вершины графа и подсчитали все полупути меньшие или равные заданной длины l, которые из нее выходят. Однако, каждый полупуть был подсчитан дважды: первый раз, когда мы искали все полупути, начиная из данной вершины, и второй раз, когда эта вершина была концом полупути, найденного из других вершин. Это не относится только к полупутям вида "вершина". На основании приведенных доводов разделим все числа массива FSS (G/HP), кроме первого, на 2. Итак, мы получили законченную программную реализацию вычисления FSS (G/HP).
Перемножив покоординатно FSS (G/HP) и V_ISC (HP) получим вектор-индекс сложности V_ISC (G/HP). Вычислив ||V_ISC (G/HP) ||1 найдем ISC (G/HP).
3.2 Среда программирования и основные характеристики программ
Разработка велась в среде Visual Studio 2010 Ultimate в режиме компилятора языка С++. Ultimate - наиболее полное издание Visual Studio, предлагющее множество полезных инструментов для написания, тестирования и отладки программ. Microsoft Visual Studio 2010 поддерживает работу с несколькими языками программирования, в том числе с одним из самых популярных языков программирования С++.
Язык C++ широко используется для разработки программного обеспечения. Благодаря свойствам как низкоуровневого, так и высокоуровневого языка C++ применяется для написания прикладных быстродействующих модулей и приложений, в том числе драйверов, операционных систем, игровых программ.
К неоспоримым достоинствам языка С относятся следующие: Александров Э.Э., Афонин В.В., Программирование на языке C в Microsoft Visual Studio 2010 (курс лекций);
· кроссплатформенность;
· стандартизированность кода;
· высокая скорость работы программ;
· гибкость;
· четкая структурированность.
В процессе разработки мною был создан проект консольного приложения, для которого разработаны 8 отдельных модулей, содержащих реализацию необходимых функций и классов, а также сам код запуска программы. Программа позволяет вычислять полный структурный спектр, индекс сложности и вектор-индекс сложности для графа.
На вход программы подается файл INPUT. txt, содержащий название графа, а также FO-представление графа. В файле Params. txt во второй и последующих строках содержатся задаваемые внешне параметры: максимальная длина полупути в базисе полупутей, индекс сложности вершины, индекс сложности дуги - в порядке перечисления. На выходе программа выдает несколько файлов, а именно:
1) INPUT_FO. txt - файл, который содержит лишь строковое представ-ление графа, заданного в INPUT. txt. Это повышает гибкость программы, поскольку при каких-либо изменениях в формате данных INPUT. txt, имея исходный код, достаточно провести несложный рефакторинг кода.
2) OUTPUT. txt - файл, который содержит полный структурный спектр графа в виде перечисления через пробел координат вектора FSS (G/HP).
3) DESCR. txt - файл, в котором в первой строке перечислены через пробел координаты вектора V_ISC (G/HP) - вектор-индекса сложности графа, во второй строке приведено значение индекса сложности графа ISC (G/HP).
4) BASES_SCHEME. txt - файл, который описывает базис полупутей, рассчитанный программой. В каждой из строк указан порядковый номер фрагмента-полупути, через запятую приведено графическое перечисление дуг данного полупути, представлен индекс сложности данного полупути.
Программа успешно интегрирована с программой "Мастерская граф-моделей", авторами которой являются Кохов В.А., Ткаченко С.В., Незнанов С.В. Данная программа содержит средства редактирования структур, позволяет решать различные задачи и проводить эксперименты на базах структур (от одной до миллионов структур), дает возможность исследовать вычислительную эффективность программных реализаций алгоритмов, работающих со структурами. Кохов В.А., Ткаченко С.В., Незнанов С.В., Мастерская граф-моделей, сайт создателей программы; http: //www.graphmodel.com/ Интеграция произведена посредством библиотеки для внешних приложений CTBench. dll, которая была разработана Незновым А.А.
3.3 Теоретические оценки вычислительной сложности разработанных алгоритмов
Технология, которая применяется в большинстве случаев для оценки вычислительной сложности алгоритмов, есть модель обобщенной однопроцессорной машины с памятью с произвольным доступом. (Random-Access Machine - RAM). Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, МЦНМО, 2000. Программа для RAM-машины представляет собой пронумерованную (начиная с 0) последовательность команд для процессора. Считается, что команды load, read, write, add, jump… выполняются за константное время.
Алгоритм построения дерева шаблонов patternTree состоит из нескольких частей, каждая из которых требует своей оценки вычислительной сложности. Рассмотрим подсчет индекса сложности для вершин уровня l. В худшем случае (если мы походим полный путь длины l) необходимо дважды пройти по ветке дерева длиной l-1 и для остальных вершин в полупути это будет сумма То есть для одной вершины оценка составляет O (l2). Всего таких вершин 2l. Тогда для всех уровней получим , поскольку процедура построения выполняется для каждого уровня, начиная с 4-ого. Воспользовавшись формулой геометрической прогрессии можно получить, что эта оценка равна:
= [] = .
Сортировка и назначение номеров дают меньшую сложность, поэтому данную оценку можно считать оценкой построения всего дерева. Такая оценка вряд ли позволит строить дерево шаблонов с большим l для каждый раз. Однако можно утверждать, что для наших целей сравнения сетей в базисах полупутей максимальной длины, не превышающей 10, проблема построения дерева решена
Алгоритм поиска полупутей в орграфе можно охарактеризовать как алгоритм обхода орграфа, использующий поиск в глубину с заданным параметром глубины. Обозначим через |Adj [v] | число вершин смежных с вершиной v. Кормен, Лейзерсон, Ривест, Штайн показывают Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, МЦНМО, 2000. , что при поиске в глубину , где V - множество ребер, E - множество вершин. Оценка же самого поиска в глубину составляет O (V+E). Мы можем воспользоваться этой оценкой для описания поиска в глубину из одной вершины. Тогда для всех вершин получаем оценку: O (V (V+E)). Поиск фрагмента-полупути в дереве выполняется за O (l). Окончательная оценка сложности для поиска O (C•l·V· (V+E)), где C - константа.
3.4 Экспериментальные оценки вычислительной сложности разработанных алгоритмов
После разработки программы было проведено несколько экспериментов с целью выяснения экспериментальной оценки эффективности ее работы, а также для получения необходимых в исследовании расчетов.
Для 24 ориентированных графов (рис.3.2) без контуров на 4 вершинах были рассчитаны их индексы сложности в базисе полупутей длины 3. На их основе был построен граф попарного сходства обработанных структур, где вершинам соответствуют порядковые номера ориентированных графов, а ребрам - модуль разницы между индексами сложности. Полученная таким образом модель позволяет проводить кластеризацию графов на основе попарных расстояний между ними, роль которых в данном случае играет разница индексов сложности.
G1 G2 G3 G4 G5 G6
G7 G8 G9 G10 G11 G12
G13 G14 G15 G16 G17 G18
G19 G20 G21 G22 G23 G24
Рис.3.2 Набор ориентированных графов без контуров на 4 вершинах.
В результате работы программы было получено 11 различных значений индекса сложности от 0 до 327. При последовательном удалении ребер большого веса постепенно увеличивается число компонент связности графа попарных расстояний.
Рис.3.3 Граф попарного сходства без контуров на 4 вершинах. Удалены все ребра, длина которых превышает 47. Выделено 3 кластера.
На рисунке изображены 3 кластера, полученные в результате последовательного извлечения ребер, превышающих 96 и 47. После удаления всех ребер, веса которых превышают 44 - число кластеров увеличилось на 1. Следующие пороговые числа в порядке уменьшения: 18, 10, 9, 8, 0.
Рис.3.4 Граф попарного сходства без контуров на 4 вершинах. Выделено 5 кластеров.
Рис.3.5 Граф попарного сходства без контуров на 4 вершинах. Выделено 11 кластеров.
В результате было получено 11 кластеров ориентированных графов, каждому из которых соответствует уникальное значение индекса сложности. Вычисления показывают практическую применимость индекса сложности для предварительной обработки множества структур. Стоит отметить, что значения структурного спектра в данном случае были уникальны для каждого из ориентированных графов. Помимо этого были проведены вычисления полного структурного спектра и индекса сложности для базы ориентированных графов на 7 вершинах, сгенерированных с использованием программы "Мастерская граф-моделей". В базу входит более 230 000 графов.
Таблица 3.6 Количество классов, выделенное на основе индекса сложности и полного структурного спектра сложности для длины базиса полупутей от 1 до 7.
|
Classes on complexity index |
Classes on full range of structural |
Half-path basis length |
|
|
16 |
16 |
1 |
|
|
115 |
7910 |
2 |
|
|
4697 |
205946 |
3 |
|
|
18660 |
237226 |
4 |
|
|
37155 |
237317 |
5 |
|
|
47801 |
237317 |
6 |
Рис.3.7 График увеличения числа классов ориентированных графов с ростом длины базиса полупутей.
Расчеты показали, что с увеличением максимальной длины полупути в базисе число классов, выделенных на основе полного структурного спектра, становится равным числу элементов. Количество различных значений индекса сложности также постоянно увеличивается и позволяет выделить число большое число классов, однако значительно уступающее числу классов для полного структурного спектра.
На рисунке приведен график зависимости времени, затраченного на выполнение программы (в минутах), от параметра - длины базиса полупутей. Для каждой длины пути с 1 время составило соответственно: 30, 80, 185, 306, 512, 709 минут.
Рис.3.8 График зависимости времени работы программы от длины базиса полупутей.
Приближение полиномом было выполнено при помощи системы Matlab 7. Звездочками отмечены точки, соответствующие исходным данным. Синяя линия показывает график для оцененных коэффициентов. Можно утверждать, что полученные коэффициенты достаточно точно отражают зависимость: Y = 20.34x2 - 4.89x + 12.3 Таким образом, эксперимент показал квадратичную зависимость от параметра длины базиса полупутей l.
Также были получены экспериментальные оценки вычислительной сложности для ориентированных деревьев с плотностью, равной 3%, и числом вершин 20, 40, 60, 80, 120. Для каждого числа вершин было случайно выбрано 10 графов и измерено время работы программа. Для получения функции приближения было использовано среднее арифметическое полученных значений для каждого вида деревьев в соответствующем базисе полупутей.
На таблицах представлены результаты для базисов полупутей длины 5 и 6. На графиках показаны точки исходных данных, а также звездочками выделены соответствующие значения для оцененных коэффициентов полинома.
Таблица 3.9 Время работы программы для ориентированных деревьев с заданным количеством вершин. Длина базиса полупутей 5.
|
Vertices number |
Elapsed time in milliseconds |
|
|
20 |
38 |
|
|
40 |
358 |
|
|
60 |
7165 |
|
|
80 |
52381 |
|
|
100 |
149278 |
|
|
120 |
553183 |
Рис.3.10 График зависимости времени работы программы от числа вершин ориентированного графа. Длина базиса полупутей 5.
Таблица 3.11 Время работы программы для ориентированных деревьев с заданным количеством вершин. Длина базиса полупутей 6.
|
Vertices number |
Elapsed time in milliseconds |
|
|
20 |
89 |
|
|
40 |
762 |
|
|
60 |
30089 |
|
|
80 |
267773 |
|
|
100 |
1168181 |
|
|
120 |
5980676 |
Рис.3.12 График зависимости времени работы программы от числа вершин ориентированного графа. Длина базиса полупутей 6.
Вычисления также выполнялись в программе Matlab7. Наилучшее приближение дают полиномы 4-ой степени. Для длины базиса 5 получено следующее уравнение:
Y = 0.029x4 - 6.36x3 + 507.55x2 - 16430,45x + 172887,16.
Для длины базиса 6 получено:
Y=0.4x4 - 87.86x3 + 6845,01x2 - 215613,32x+ 2223307,67.
Полученные результаты позволяют говорить о некотором расхождении теоретической оценки с экспериментальной оценкой вычислительной сложности программы.
3.5 Основные результаты и выводы по главе
Таким образом, разработан алгоритм вычисления индексов, вектор-индексов и полных структурных спектров в базисе полупутей. Данный алгоритм позволяет при заданных параметрах максимальной длины полупути в базисе полупутей l, индекса сложности вершины и индекса сложности дуги произвести программную реализацию методов решения задач различения и определения сходства семантических сетей на основе указанных показателей.
Рассчитана теоретическая оценка вычислительной сложности алгоритма. Данная оценка показывает что для небольших значений l возможно построение дерева шаблонов за приемлемое время. Приведена оценка поиска всех фрагментов-полупутей в графе, имеющая квадратичную сложность. Сделан вывод, что при небольших значениях l возможно эффективно производить поиск фрагментов-полупутей в графе. Остается открытым вопрос об улучшении квадратичного времени.
Программа успешно реализована в среде Microsoft Visual Studio 2010 Ultimate на языке программирования С++. С помощью программы проведены исследования разбиения графов на классы эквивалентности на основе равенства полного структурного спектра и индекса сложности в базисах полупутей длины от 1 до 7. Была использована база ориентированных графов на 7 вершинах, сгенерированная с использованием программы "Мастерская граф-моделей", в которой содержится более 230 000 графов. Полученные результаты позволяют утверждать, что с увеличением максимальной длины полупути в базисе число классов становится равным числу элементов, т.е. каждый граф обладает уникальным структурным спектром, отличным от всех остальных.
Определены экспериментальные оценки вычислительной сложности алгоритмов вычисления индексов, вектор-индексов и полупутей. В результате работы программы построена зависимость времени работы от числа вершин, а также зависимость времени работы от длины базиса полупутей.
Заключение
Семантическая технология открывает новые способы представления информации, которые смогут позволить компьютеру распознавать смысл предложений и в соответствии с этим на основе баз знаний с высокой точностью классифицировать полученную информацию и строить собственные на суждения на основе заложенных правил. Потому задача сравнения семантических сетей является одной из важнейших для создания нового типа программ, способных при минимальном участии человека оперировать информацией и выдавать результаты на запросы, которые будут соответствовать смыслу, заложенному в них пользователем. Именно сравнение сетей позволит выявлять сходства контекстов различных по содержанию, но сходных по смыслу языковых конструкций.
В данной работе используется подход к сравнению сетей на основе иерархической модели характеризации структурной сложности систем. Данный подход позволяет решить проблему характеризации сложности структур и определения её меры. Целью этого исследования было разработать алгоритм сравнения семантических сетей на основе индексов сложности, полных структурных спектров и вектор-индексов сложности, а также выполнить его программную реализацию.
В результате исследования был реализован алгоритм позволяющий за разумное время находить все изоморфные вложения фрагментов-полупутей, которые заданы в графе. Данный алгоритм программно реализован на языке программирования С++. Полученная программа была успешно интегрирована с программой "Мастерская граф-моделей".
Данный алгоритм и программа были про тестированы на базах ориентированных графов без контуров, сгенерированных с помощью "Мастерской граф-моделей". Экспериментальные оценки вычислительной сложности отличаются от теоретических выводов. Тем не менее, было показано, что реализованный алгоритм позволяет производить необходимые вычисления за полиномиальное время. Потому полученные результаты доказывают, что с ростом максимальной длины базиса полупутей оценка сложности граф-моделей на основе изученных методов позволяет успешно решать проблему схожести и различения семантических структур.
Таким образом, в обширном исследовании задачи различения и определения сходства семантических сетей сделан еще один шаг в сторону развития данной области. Разработанные алгоритм и программа могут стать полезными инструментами для дальнейшего изучения вопроса сравнения структур.
Список использованных источников
1. Berners-Lee Tim, Hendler James and Lassila Ora, The Semantic Web, 2001; http://www.sciam.com/article. cfm? id=the-semantic-web
2. Borgida Alex, Mylopoulos John, Semantic Networks, 2004; http://www.cs. toronto.edu/~jm/2507S/Notes04/SemanticNets. pdf
3. Manning C. D., Raghavan P., Schutze H., "An Introduction To Information Retrieval", Online Edition (c) 2009 Cambridge UP;
4. Аверкин А.Н., Гаазе-Рапопорт М.Г., Поспелов Д.А., Толковый словарь по искусственному интеллекту;
5. http://raai.org/library/tolk/aivoc.html
6. Александров Э.Э., Афонин В.В., Программирование на языке C в Microsoft Visual Studio 2010 (курс лекций); http://www.intuit.ru/department/pl/prcmsvs2010/
7. Андерсон, Джеймс А., Дискретная математика и комбинаторика: Пер. с англ. - М.: Издательский дом "Вильямс", 2003.
8. Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И., Методы и модели анализа данных: OLAP и Data Mining. - СПб.: БХВ-Петербург, 2004.
9. Гаврилов А.В., Семантические сети. Представление знаний в информационных системах (курс лекций; http://www.insycom.ru/html/metodmat/pz/Lect5_1. pdf
10. Гаврилова Т.А., Хорошевский В.Ф., Базы данных интеллектуальных систем, Издательский дом "Питер"., 2001.
11. Джасим Малатх Рахим Разработка методов и программных средств для решения задач различения и анализа сложности ациклических структур. Автореферат диссертации к. т. н., М. МЭИ. 2010,20 с.
12. Жилякова Л.Ю., Алгебраические свойства отношений в неоднородных семантических сетях.
13. Знаковые графы и орграфы и их применение при моделировании и анализе сложных проблем в экологии, психологии и политике; http://www.allmath.ru/highermath/algebra/diskret-dubna/Ll10_11.html
14. Кальченко Даниил, Интеллектуальные агенты семантического Web'а; http://www.compress.ru/Archive/CP%5C2004%5C10%5C48/
15. Карпенко А.П., Соколов Н.К., Оценка сложности семантической сети в обучающей системе, электронное научно-техническое издание "Науки и образование", # 11, ноябрь 2008; http://technomag.edu.ru/doc/106658.html
16. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, МЦНМО, 2000.
17. Кохов В.А., Граф-модели для анализа сходства структур систем.
18. Кохов В.А. Концептуальные и математические модели сложности графов. М.: Издательство МЭИ, 2002. - 160 с.
19. Кохов В.А., Кохов В.В., Метод решения задачи различения орграфов на основе сложности, БИЗНЕС-ИНФОРМАТИКА №1 (15) - 2011 г.
20. Кохов В.А., Методы анализа сходства графов и сходства расположения цепных фрагментов в графе.
21. Кохов В.А., Незнанов А.А., Ткаченко С.В., Структурная информатика - новый актуальный раздел информатики для изучения в школе и в университете, Совещание "Актуалные проблемы информатики в современном российском образовании", Москва, 2004.
22. Кохов В.А., Ткаченко С.В., Незнанов С.В., Мастерская граф-моделей, сайт создателей программы; http://www.graphmodel.com/
23. Кохов В.А., Ткаченко С.В. Метод иерархического исследования сходства структур систем. // Науч. Сессия МИФИ-2004: Т.З. М: МИФИ, 2004 - с.184-185.
24. Незнанов А.А., Кохов В.А., Программный комплекс для анализа сходства структур систем.
25. Поспелов Д.А., Моделирование рассуждений. Опыт анализа мыслительных актов, - М.: Радио и связь, 1989.
26. Рубашкин В.Ш., Онтологическая инженерия в системах, основанных на знаниях.
27. Стерин А., Цейтлин Д. Возможности использования статистических средств SAS System для решения аналитических задач в области финансов и бизнеса; http://www.sas.com/offices/europe/russia/articles/1998/ss9-10.html
28. Финн В.К., Искусственный интеллект: идейная база и основной продукт, КИИ-2004, Труды конференции в 2 томах, т.1, с.11 - 20.
29. Харламов Александр, Автоматический структурный анализ текстов, "Открытые системы", № 10, 2002;http://www.osp.ru/os/2002/10/182010/
30. Чиковски Эрика, Технологии семантической сети, PC Week/RE №39 (645) 21 - 27 октября 2008; http://www.pcweek.ru/idea/article/detail. php? ID=113351
Приложения
Приложение 1
Пример файла BASES_SCHEME. txt для максимальной длины базиса полупути, равной 5
__________________________________________________________________
1.1
2. < - 3
3. < - < - 9
4. - -> < - 9
5. < - -> 9
6. < - < - < - 31
7. - -> < - < - 22
8. < - -> < - 13
9. < - < - -> 22
10. < - -> < - -> 17
11. - -> < - -> < - 17
12. < - < - -> < - 26
13. < - -> < - < - 26
14. < - -> - -> < - 26
15. < - < - -> - -> 35
16. - -> - -> < - < - 35
17. < - < - < - -> 66
18. - -> < - < - < - 66
19. < - < - < - < - 106
20. < - -> < - -> < - 21
21. < - < - -> < - -> 30
22. < - -> < - < - -> 30
23. - -> < - < - -> < - 30
24. - -> < - -> < - < - 30
25. < - < - -> < - < - 39
26. < - < - -> - -> < - 39
27. < - -> - -> < - < - 39
28. < - < - < - -> < - 70
29. < - -> < - < - < - 70
30. < - -> - -> - -> < - 70
31. < - < - < - -> - -> 79
32. - -> - -> < - < - < - 79
33. < - < - < - < - -> 216
34. - -> < - < - < - < - 216
35. < - < - < - < - < - 362
Приложение 2
Файлы с исходным кодом
__________________________________________________________________
xFile. h
#ifndef XFILE_H
#define XFILE_H
#include <string>
using std:: string;
class xFile // исключение
{
public:
xFile (string _fileName = "undefined"): fileName (_fileName) {}
~xFile () {}
string GetFilename () {return fileName; }
private:
string fileName;
};
class xParams
{
public:
xParams () {}
~xParams () {}
};
#endif
_____________________________________________________________
enums. h
#ifndef ENUMS_H
#define ENUMS_H
enum DIRECTION {OUT = - 1, UNDEFINED, IN};
enum COLOR {WHITE, GRAY, BLACK};
#endif
__________________________________________________________________
txtProcessor. h
#ifndef TXTPROCESSOR_H
#define TXTPROCESSOR_H
#include <iostream>
using std:: cin;
using std:: cout;
using std:: endl;
#include <fstream>
using std:: ifstream;
using std:: ofstream;
#include <vector>
using std:: vector;
#include <string>
using std:: string;
#include "xFile. h"
namespace txtProc {
static vector<int> getParamsFromFile (string params_file) {
ifstream PARAMS (params_file);
if (! PARAMS) {
xFile e (params_file);
throw e;
}
char inputChar;
PARAMS. get (inputChar);
while (inputChar! = '\n')
PARAMS. get (inputChar);
int parameter;
vector<int> params;
while (PARAMS >> parameter && params. size () < 3)
params. push_back (parameter);
return params;
};
static void copyAndClose (ifstream& FROMf, ofstream& TOf, string fullGraphName) {
TOf << fullGraphName << endl;
char nextSymbol;
while (FROMf. get (nextSymbol))
TOf << nextSymbol;
TOf << endl;
FROMf. close ();
};
}
#endif
__________________________________________________________________
patternTree. h
#ifndef PATTERNTREE_H
#define PATTERNTREE_H
#include "enums. h"
#include <vector>
using std:: vector;
struct PatternNode
{
int complexityIndex;
int number;
vector <DIRECTION> theWay;
PatternNode (int _number = 0, int _complexityIndex = 0, vector <DIRECTION> _theWay = vector <DIRECTION> ())
{
complexityIndex = _complexityIndex;
number = _number;
theWay = _theWay;
}
};
class ComparePatterns {
public:
bool operator () (const PatternNode& left, const PatternNode& right)
{
return left.complexityIndex < right.complexityIndex;
}
};
class PatternTree
{
friend class Graph;
public:
PatternTree (int _size = 5, int _vertexWeight = 1, int _edgeWeight = 3);
void buildTree ();
~PatternTree () {}
private:
int sortNumbersAtLevel (int level, int nextCount);
bool reversedWayCompare (vector<DIRECTION> sample, vector<DIRECTION> suspect);
void manualOrderSet ();
void definePattern (vector<DIRECTION> way);
int defineCount ();
void fillHalfPaths ();
int oneMoveDown (int position, DIRECTION direct);
int wholeWayDown (vector<DIRECTION> wholeWay);
void ShowBasesScheme ();
vector <PatternNode> tree;
vector <PatternNode> halfPaths;
vector<int> P;
vector<int> ISC;
int fullSize;
int maxLength;
};
#endif
__________________________________________________________________
patternTree. cpp
#include <iostream>
using std:: cin;
using std:: cout;
using std:: endl;
#include <iomanip>
using std:: setw;
#include <fstream>
using std:: ifstream;
using std:: ofstream;
#include <algorithm>
#include <cmath>
#include "patternTree. h"
PatternTree:: PatternTree (int _size, int _vertexWeight, int _edgeWeight)
: maxLength (_size), fullSize (0)
{
fullSize = pow ( (double) 2, maxLength + 1);
tree. resize (fullSize);
tree. at (1).complexityIndex = _vertexWeight;
tree. at (1). number = 1;
if (maxLength > 0)
{
tree. at (2).complexityIndex = _edgeWeight;
tree. at (2). theWay. push_back (IN);
tree. at (2). number = 2;
tree. at (3).complexityIndex = _edgeWeight;
tree. at (3). theWay. push_back (OUT);
tree. at (3). number = 2;
}
}
int PatternTree:: oneMoveDown (int position, DIRECTION direct)
{
if (direct == IN)
return position * 2;
else if (direct == OUT)
return position * 2 + 1;
}
int PatternTree:: wholeWayDown (vector<DIRECTION> wholeWay)
{
int position = 1;
DIRECTION direct = UNDEFINED;
for (int next = 0; next < wholeWay. size (); ++next)
{
direct = wholeWay. at (next);
position = oneMoveDown (position, direct);
}
return position;
}
void PatternTree:: buildTree ()
{
for (int index = 4; index < tree. size (); ++index) // 4 - с этого индекса начинаются полупути длины 2
{
int parent = index/2;
tree. at (index). theWay = tree. at (parent). theWay;
if (index % 2 == 0)
tree. at (index). theWay. push_back (IN);
else
tree. at (index). theWay. push_back (OUT);
int score = 0;
int currentPosition = 1;
vector<DIRECTION> processed = tree. at (index). theWay;
for (int vertexIndex = 0; vertexIndex < processed. size (); ++vertexIndex)
{
currentPosition = 1;
DIRECTION lastDirInProc, curDirInProc;
lastDirInProc = curDirInProc = UNDEFINED;
for (int nextVertex = vertexIndex; nextVertex - vertexIndex < processed. size (); ++nextVertex)
{
score += tree. at (currentPosition).complexityIndex;
if (nextVertex < processed. size ())
curDirInProc = processed. at (nextVertex);
else
break;
if (lastDirInProc == UNDEFINED || curDirInProc == lastDirInProc)
{
lastDirInProc = curDirInProc;
currentPosition = oneMoveDown (currentPosition, processed. at (nextVertex));
}
else
break;
}
}
int finalScore = score + tree. at (1).complexityIndex; // из последней вершины никуда не пойдем, поэтому просто прибавляем вес вершины.
tree. at (index).complexityIndex = finalScore;
}
int count = defineCount (); // следующий свободный номер базиса полупути
manualOrderSet ();
for (int nextLevel = 4; nextLevel <= maxLength; ++nextLevel)
{
count = sortNumbersAtLevel (nextLevel, count);
}
P. resize (count);
ISC. resize (count);
halfPaths. resize (count);
for (int index = 1; index < tree. size (); ++index)
{
int position = tree. at (index). number;
int weight = tree. at (index).complexityIndex;
ISC. at (position) = weight;
}
fillHalfPaths ();
}
void PatternTree:: fillHalfPaths ()
{
for (int index = 1; index < tree. size (); ++index)
{
int number = tree. at (index). number;
if (halfPaths. at (number).complexityIndex == 0)
{
halfPaths. at (number). theWay = tree. at (index). theWay;
halfPaths. at (number).complexityIndex = tree. at (index).complexityIndex;
}
}
}
void PatternTree:: definePattern (vector<DIRECTION> way)
{
int position = wholeWayDown (way);
int patternPlace = tree. at (position). number;
++P. at (patternPlace);
}
int PatternTree:: sortNumbersAtLevel (int level, int nextCount) // // // // // // /int
{
double powerBase = 2;
int start = pow (powerBase, level);
int finish = pow (powerBase, level + 1);
vector<PatternNode>:: iterator begining = tree. begin () + start;
vector<PatternNode>:: iterator ending = tree. begin () + finish;
vector<PatternNode> processed;
processed. resize (finish-start);
vector<PatternNode>:: iterator destination = processed. begin ();
std:: copy (begining, ending, destination);
std:: stable_sort (processed. begin (), processed. end (), ComparePatterns ()); // отсортировываем по возрастанию индекса сложности с сохранением порядка равных элементов
int currentCount = nextCount;
for (int index = 0; index < processed. size (); ++index)
{
if (processed. at (index). number == 0)
{
processed. at (index). number = currentCount;
vector<DIRECTION> sample = processed. at (index). theWay;
for (int likely = index + 1; likely < processed. size (); ++likely)
{
if (processed. at (likely).complexityIndex > processed. at (index).complexityIndex)
break;
if (processed. at (likely).complexityIndex == processed. at (index).complexityIndex
&& processed. at (likely). number == 0)
{
vector<DIRECTION> suspect = processed. at (likely). theWay;
bool answer = reversedWayCompare (sample, suspect);
if (answer)
{
processed. at (likely). number = currentCount;
int duplicatePosition = wholeWayDown (suspect);
tree. at (duplicatePosition). number = currentCount;
break;
}
}
}
int samplePosition = wholeWayDown (sample);
tree. at (samplePosition). number = currentCount;
++currentCount;
}
}
return currentCount;
}
bool PatternTree:: reversedWayCompare (vector<DIRECTION> sample, vector<DIRECTION> suspect)
{
bool same = true;
std:: reverse (suspect. begin (),suspect. end ());
for (int index = 0; index < sample. size (); ++index)
{
if (sample. at (index) == suspect. at (index))
{
same = false;
break;
}
}
return same;
}
void PatternTree:: manualOrderSet ()
{
if (maxLength > 1) // для уровня 2
{
tree. at (4). number = 3;
tree. at (5). number = 5;
tree. at (6). number = 4;
tree. at (7). number = 3;
}
if (maxLength > 2) // для уровня 3
{
tree. at (8). number = 6;
tree. at (9). number = 9;
tree. at (10). number = 8;
tree. at (11). number = 9;
tree. at (12). number = 7;
tree. at (13). number = 8;
tree. at (14). number = 7;
tree. at (15). number = 6;
}
}
int PatternTree:: defineCount ()
{
int count = 0; // следующий незанятый порядковый номер полупути в базисе и соответственно размер вектор-индекса и ПСС
if (maxLength == 0)
count = 2;
else if (maxLength == 1)
count = 3;
else if (maxLength == 2)
count = 6;
else
count = 10;
return count;
}
void PatternTree:: ShowBasesScheme ()
{
ifstream SCHEME_EXIST ("BASES_SCHEME. TXT");
if (SCHEME_EXIST) {
SCHEME_EXIST. close ();
return;
}
SCHEME_EXIST. close ();
ofstream BASES_SCHEME ("BASES_SCHEME. TXT");
for (int index = 1; index < halfPaths. size (); ++index)
{
BASES_SCHEME << setw (3) << index <<". ";
for (int dir = 0; dir < maxLength; ++dir)
{
if (halfPaths. at (index). theWay. size () > dir)
BASES_SCHEME << setw (3) << (halfPaths. at (index). theWay. at (dir) == - 1?"-->": "<--") << " ";
else
{
BASES_SCHEME. fill (' ');
BASES_SCHEME << " ";
}
}
BASES_SCHEME. width (6);
BASES_SCHEME << "\t" << halfPaths. at (index).complexityIndex << endl;
}
BASES_SCHEME. close ();
}
__________________________________________________________________
graphPath. h
#ifndef GRAPHPATH_H
#define GRAPHPATH_H
#include "enums. h"
#include "patternTree. h"
#include "xFile. h"
#include <fstream>
using std:: ifstream;
using std:: ofstream;
#include <string>
using std:: string;
struct Adjacent
{
int index;
DIRECTION direct;
COLOR visitColor;
Adjacent (int _index = - 1, DIRECTION _direct = UNDEFINED, COLOR _color = WHITE)
{
index = _index;
direct = _direct;
visitColor = _color;
}
};
class Compare
{
public:
bool operator () (const Adjacent& left, const Adjacent& right)
Подобные документы
Средства формализации процесса определения спецификаций. Назначение языка (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
