Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Двумерная кластеризая по предельному расстоянию. Дискретная математика

Название: Двумерная кластеризая по предельному расстоянию. Дискретная математика
Раздел: Рефераты по математике
Тип: курсовая работа Добавлен 22:11:49 22 ноября 2010 Похожие работы
Просмотров: 172 Комментариев: 2 Оценило: 1 человек Средний балл: 4 Оценка: неизвестно     Скачать

Федеральное агентство по образованию

ГОУ ВПО "ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ"

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

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К КУРСОВОМУ ПРОЕКТУ

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

ДВУМЕРНАЯ КЛАСТЕРИЗАЦИЯ ПО ПРЕДЕЛЬНОМУ РАССТОЯНИЮ

Омск – 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 , в которой значение элемента 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а. Первоначально в матрице на главной диагонали все нули, значит

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с.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:06:10 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
08:53:37 29 ноября 2015

Работы, похожие на Курсовая работа: Двумерная кластеризая по предельному расстоянию. Дискретная математика

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(151259)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru