Курсовая работа: Двумерная кластеризая по предельному расстоянию. Дискретная математика
Федеральное агентство по образованию
ГОУ ВПО "ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ"
Кафедра «Автоматизированные системы обработки информации и управления»
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
К КУРСОВОМУ ПРОЕКТУ
по дисциплине «Дискретная математика»
ДВУМЕРНАЯ КЛАСТЕРИЗАЦИЯ ПО ПРЕДЕЛЬНОМУ РАССТОЯНИЮ
Омск – 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 .
Лес — неориентированный граф без циклов. Компонентами связности леса являются деревья.
Дерево — это связный граф, не содержащий циклов.
--> ЧИТАТЬ ПОЛНОСТЬЮ <--