Федеральноеагентство по образованию
ГОУ ВПО«ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Кафедра«Автоматизированные системы обработки информации и управления»
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
К КУРСОВОМУ ПРОЕКТУ
по дисциплине «Дискретная математика»
ДВУМЕРНАЯ КЛАСТЕРИЗАЦИЯ ПО ПРЕДЕЛЬНОМУРАССТОЯНИЮ
Омск – XXX
/>/>/>
Реферат
Отчёт 14с., 1ч., 12рис., 0табл., 3источника,0прил.
ГРАФ, КЛАСТЕР, МИНИМАЛЬНОЕ ОСТОВНОЕДЕРЕВО.
Предметом курсового проекта являетсякластеризация.
Цель работы – разработка алгоритмакластеризации по предельному расстоянию и построение минимального остовногодерева каждого кластера.
В ходе работы был разработан алгоритмкластеризации.
В результате работы было написаналгоритм, решающийданные задачи.
Введение
Часто бывает полезно и наглядноизображать некоторую ситуацию в виде рисунка, состоящего из точек (вершин) илиний (рёбер), соединяющих некоторые вершины. Такие изображения получилиназвания графа.
Теория графов получила широкоеприменение на практике. Она применяется в гражданском строительстве,электротехнике, социологии и экономике и в других областях.
Одной из задач теории графов являетсякластеризация и построение минимального остовного дерева. Эти задачи частовозникают на практике: при группировке результатов поиска, проектированиикомпьютерных систем, соединении городов, составлении электрических цепей.
Целью данной работы являетсяразработка алгоритма, выполняющего данные задачи.
Отчет содержит четыре раздела:
— постановка задачи курсовогопроектирования – это раздел, в котором описывается задача курсового проекта;
— схемы алгоритмов – это раздел, вкотором описывается алгоритм и его схема;
— теоретический анализ – теория,необходимая для выполнения поставленной задачи;
— результаты тестирования – этораздел, в котором описываются результаты тестирований на правильность работыразработанного алгоритма.
1 Постановка задачи курсовогопроектирования
Реализовать алгоритм кластеризациизаданного набора точек по предельному расстоянию d. После кластеризации граф каждого кластера редуцировать доминимального остовного дерева.
2 Теоретический анализ
Граф G — этоматематический объект, состоящий из множества вершин X = {x1,x2,...,xn} и множества ребер A = {a1,a2,..., ak}.
Связный граф — такой граф, в котором между любой парой вершин существуетпо крайней мере один путь.
Взвешенный граф — граф, каждому ребру которого поставлено в соответствиенекоторое значение (вес ребра).
Вес ребра — значение, поставленное в соответствие данному ребру взвешенногографа. Обычно вес — вещественное число и его можно интерпретировать как «длину»ребра.
Если ребрам графа приданы направления от одной вершинык другой, то такой граф называется ориентированным. Ребра ориентированногографа называются дугами. Если направления ребер не указываются, то графназывается неориентированным (или просто графом).
Подграф исходного графа — граф, содержащий некое подмножество вершинданного графа и некое подмножество инцидентных им рёбер.
Матрицасмежности графа G с конечным числом вершин n (пронумерованныхчислами от 1 до n) — это квадратная матрица A размера n, вкоторой значение элемента ai j равно числу ребёр из i-йвершины графа в j-ю вершину.
Матрицасмежности простого графа является бинарной матрицей и содержит нули на главнойдиагонали.
Кластерный анализ — задача разбиения заданной выборки объектов (ситуаций) на подмножества,так, чтобы каждый кластер состоял из схожих объектов, а объекты разныхкластеров существенно отличались.
Кластер — группа элементов, характеризуемых общимсвойством.
В данном случае в кластеры объединяются точки,находящиеся на расстоянии меньше предельного d.
Лес — неориентированный граф без циклов. Компонентами связности лесаявляются деревья.
Дерево — это связный граф, не содержащий циклов.
Минимальное остовное дерево (или минимальное покрывающее дерево)в связанном, взвешенном, неориентированном графе — это остовное дерево, имеющееминимальный возможный вес. Вес дерева — сумма весов входящих в него рёбер.
В данномкурсовом проекте для построения минимального остовного дерева используетсяалгоритм Краскала. Рёбра графа упорядочиваются в порядке не убывания их весов ипоследовательно добавляются к графу. Если добавление нового ребра приведёт кобразованию цикла, то это ребро пропускается. Подграф данного графа, содержащий все его вершины инайденное множество рёбер, является его остовным лесом минимального веса.
3 Схемы основных алгоритмов
3.1 Пошаговый алгоритм
Шаг 1. Заполнение матрицы весов T.
Шаг 2. Создание матрицы смежности С.
Шаг 2а. Если расстояние между двумя точками s> d, то в матрицу заносится 0, иначе 1.
Шаг 2б. Повторение шага 2 N раз;
Шаг 3. Создание матрицы минимального остовного дерева ТТ;
Шаг 3а. Если ttii= 0, ttjj = 0, то ttij = tij, ttii = k, ttjj = k,k = k +1, где tij – минимальный положительный элемент матрицы T;
Шаг 3б. Если ttii= 0, ttjj ≠ 0, то ttij = tij, ttii = ttjj;
Шаг 3д. Если ttii≠ 0, ttjj = 0, то ttij = tij, ttjj = ttii;
Шаг 3е. Если ttii≠ 0, ttjj≠ 0, ttii≠ ttjj,то ttij = tij, ttii=l, ttjj = l, где l –наименьшее из ttiiиttjj;
Шаг 3ж. Если ttii≠ 0, ttjj≠ 0, ttii= ttjj, то tij = -1;
Шаг 4. Проверка диагональных элементов матрицы ТT;
Шаг 4б. Если ttzz= 1, то повторить шаг 4. Иначе m= 0;
Шаг 5. Повторять алгоритм с шага 3 до тех пор, пока m≠ 1;
3.2 Схема алгоритма.
Решение данной задачи состоит из нескольких этапов:кластеризации и построения минимального остовного дерева. Схемы этихалгоритмов, изображены на рисунках 2 – 4. Общая схема алгоритма изображена нарисунке 1.
/>
Рисунок 1 – Схема основного алгоритма
/>
Рисунок 2 – Алгоритм кластеризации
/>
Рисунок 3 – Алгоритм построения минимального остовногодерева
/>
Рисунок 4 – Алгоритм построения минимального остовногодерева (продолжение)
4 Результаты тестирования
Было проведено 3 различных эксперимента.
4.1 Тест первый.
Пусть граф содержит 8 вершин, координаты которых заданы случайнымобразом, а взвешенная матрица Т представлена на рисунке 5. Предельноерасстояние d = 5;
/>
Рисунок 5 – Тест первый (часть 1)
Шаг 1. Обнуление матрицы дерева ТТ.
Шаг 2. Составляем матрицу смежности С.
Шаг 2а. Если расстояние между двумя точками s> d, то в матрицу заносится 0, иначе 1.
Шаг 2б. Повторение шага 2 8 раз. Полученная в результатематрица смежности представлена на рисунке 6.
/>
Рисунок 6 – Тест первый (часть 2)
Шаг 3. Составляем матрицу дерева ТТ.
Шаг 3а. Первоначально в матрице на главной диагоналивсе нули, значит
tt11 = tt22 =… = tt88 = 0, k = 1;
Шаг 3б. Находим минимальный элемент матрицы Т — t12= 0,5. Включаем данное ребро в матрицу ТТ и увеличиваем значениесчётчика k = k + 1 = 2;
Шаг 3г. Находим следующий минимальный элемент и повторяемвсе действия из шага 3б. Таким образом перебираем всю матрицу.
Шаг 4. На главной диагонали матрицы ТТнаходятся все 1. Полученная матрица представлена на рисунке 7.
/>
Рисунок 7 – Тест первый (часть 3)
4.1 Тест второй.
Результат выполнения алгоритма с 20-ю вершинами,заданными случайными координатами и предельным расстоянием равным 2,5 представленна рисунке 8.
/>
Рисунок 8 – Тест второй (часть 1)
На данном рисунке видно, что граф был разбит на 8кластеров. Увеличим предельное расстояние до 3. Из рисунка 9 видно, чтоколичество кластеров сократилось до 4.
/>
Рисунок 9 – Тест первый (часть 2)
Продолжая постепенно увеличивать предельноерасстояние, увидим, что в итоге граф будет представлять собой один кластер.Минимальное остовное дерево этого кластера представлено на рисунке 10.
/>
Рисунок 10 – Тест первый (часть 3)
Из этого теста видно, что с увеличением предельногорасстояния количество кластеров уменьшается. Минимальное остовное деревостроится верно. Значит, в данном тесте программа работает верно.
4.3 Тест третий
Составим граф из 7 вершин, координаты которых ипредельное расстояние представлены на рисунке 11.
/>
Рисунок 11 – Тест второй (часть 1)
Построим данный граф. Остовное дерево данного графа, атак же матрицы смежности, расстояний и остовного дерева представлены на рисунке12.
/>
Рисунок 12 – Тест второй (часть 2)
Заключение
При рассмотрении данной задачи был изучен один изразделов теории графов кластеризация и построение минимального остовного деревапо алгоритму Краскала.
Результатом курсового проекта является алгоритм,выполняющий необходимые задачи.
Список использованных источников
1 Канева О.Н. Дискретная математика. –Омск: ОмГТУ, 2009. -87с.
2 Кристофидес Н. Теория графов.Алгоритмический подход.- М.: Мир, 1978.-433с.
3 Новиков Ф.А. Дискретная математикадля программистов. – СПб: Питер, 2000. -304с.