Двовимірна кластеризуючих за граничним відстані Дискретна математика

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Федеральне агентство з освіти

ГОУ ВПО "Омськ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ"

Кафедра «Автоматизовані системи обробки інформації та управління»

ПОЯСНЮВАЛЬНА ЗАПИСКА

До курсового проекту

з дисципліни «Дискретна математика»

Двовимірні Кластеризація ПО Глибина

Омськ - XXX

Реферат

Звіт 14с., 1ч., 12ріс., 0табл., 3істочніка, 0пріл.

ГРАФ, КЛАСТЕР, МІНІМАЛЬНЕ остовне дерево.

Предметом курсового проекту є кластеризація.

Мета роботи - розробка алгоритму кластеризації за граничним відстані і побудова мінімального остовного дерева кожного кластера.

В ході роботи був розроблений алгоритм кластеризації.

В результаті роботи було написано алгоритм, вирішальний дані завдання.

Введення

Часто буває корисно і наочно зображувати деяку ситуацію в вигляді малюнка, що складається з точок (вершин) і ліній (ребер), що з'єднують деякі вершини. Такі зображення отримали назви графа.

Теорія графів одержала широке застосування на практиці. Вона застосовується в цивільному будівництві, електротехніці, соціології та економіці і в інших областях.

Одним із завдань теорії графів є кластеризація і побудова мінімального остовного дерева. Ці завдання часто виникають на практиці: при угрупованню результатів пошуку, проектуванні комп'ютерних систем, з'єднанні міст, складанні електричних ланцюгів.

Метою даної роботи є розробка алгоритму, що виконує ці завдання.

Звіт містить чотири розділи:

- Постановка завдання курсового проектування - це розділ, в якому описується завдання курсового проекту;

- Схеми алгоритмів - це розділ, в якому описується алгоритм і його схема;

- Теоретичний аналіз - теорія, необхідна для виконання поставленого завдання;

- Результати тестування - це розділ, в якому описуються результати тестувань на правильність роботи розробленого алгоритму.

1 Постановка завдання курсового проектування

Реалізувати алгоритм кластеризації заданого набору точок щодо граничного відстані d. Після кластеризації граф кожного кластера редукувати до мінімального остовного дерева.

2 Теоретичні аналіз

Граф G - це математичний об'єкт, що складається з безлічі вершин X = {x 1, x 2 ,..., x n} і безлічі ребер A = {a 1, a 2 ,..., a k}.

Зв'язний граф - такий граф, в якому між будь-якою парою вершин існує принаймні один шлях.

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

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

Якщо ребрам графа додані напрямку від однієї вершини до іншої, то такий граф називається орієнтованим. Ребра орієнтованого графа називаються дугами. Якщо напрями ребер не вказуються, то граф називається неорієнтованим (або просто графом).

Подграф вихідного графа - граф, що містить якесь підмножина вершин даного графа і якесь підмножина інцидентних їм ребер.

Матриця суміжності графа G з кінцевим числом вершин n (пронумерованих числами від 1 до n) - це квадратна матриця A розміру n, в якій значення елемента a ij дорівнює числу ребер з i-й вершини графа в j-ю вершину.

Матриця суміжності простого графа є бінарною матрицею і містить нулі на головній діагоналі.

Кластерний аналіз - завдання розбиття заданої вибірки об'єктів (ситуацій) на підмножини, так, щоб кожен кластер складався з схожих об'єктів, а об'єкти різних кластерів істотно відрізнялися.

Кластер - група елементів, якi характеризуються загальною властивістю.

В даному випадку в кластери об'єднуються точки, що знаходяться на відстані менше граничного d.

Ліс - неорієнтований граф без циклів. Компонентами зв'язності лісу є дерева.

Дерево - це зв'язний граф, який не містить циклів.

Мінімальна остовне дерево (або мінімальне покриває дерево) у зв'язаному, зваженому, неориентированном графі - це остовне дерево, що має мінімальний можливий вагу. Вага дерева - сума ваг входять до нього ребер.

В даному курсовому проекті для побудови мінімального остовного дерева використовується алгоритм Краскала. Ребра графа впорядковуються в порядку не спадання їх ваг і послідовно додаються до графа. Якщо додавання нового ребра призведе до утворення циклу, то це ребро пропускається. Подграф даного графа, що містить всі його вершини і знайдене безліч ребер, є його Остовним лісом мінімальної ваги.

3 схеми основних алгоритмів

3.1 Покроковий алгоритм

Крок 1. Заповнення матриці ваг T.

Крок 2. Створення матриці суміжності С.

Крок 2а. Якщо відстань між двома точками s > D, то в матрицю заноситься 0, інакше 1.

Крок 2б. Повторення кроку 2 N разів;

Крок 3. Створення матриці мінімального остовного дерева ТТ;

Крок 3а. Якщо tt ii = 0, tt jj = 0, то tt ij = t ij, tt ii = k, tt jj = k, k = k +1, де t ij - мінімальний позитивний елемент матриці T;

Крок 3б. Якщо tt ii = 0, tt jj ≠ 0, то tt ij = t ij, tt ii = tt jj;

Крок 3д. Якщо tt ii ≠ 0, tt jj = 0, то tt ij = t ij, tt jj = tt ii;

Крок 3Е. Якщо tt ii ≠ 0, tt jj ≠ 0, tt ii tt jj , То tt ij = t ij, tt ii = l, tt jj = l, де l - найменше з tt ii і tt jj;

Крок 3ж. Якщо tt ii ≠ 0, tt jj ≠ 0, tt ii = Tt jj, то t ij = 1;

Крок 4. Перевірка діагональних елементів матриці Т T;

Крок 4б. Якщо tt zz = 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а. Спочатку в матриці на головній діагоналі всі нулі, значить

tt 11 = tt 22 = ... = Tt 88 = 0, k = 1;

Крок 3б. Знаходимо мінімальний елемент матриці Т - t 12 = 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с.

Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Курсова
29кб. | скачати


Схожі роботи:
Дискретна математика
Двовимірна графіка системи Maple
Передача електроенергії на відстані та її використання
Трансформатор Передача електроенергії на великі відстані
Ознаки ушкодження при пострілах з різного відстані
Визначення фокусної відстані збиральної і розсіює лінз
Розрахунок пройденої відстані і часу при пасивному та активному гальмуванні судна
Алгоритми на графах Найкоротші відстані на графах
Математика
© Усі права захищені
написати до нас