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

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

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

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

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

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

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

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

Омск – XXX

Реферат

Отчёт 14с., 1ч., 12рис., 0табл., 3источника, 0прил.

ГРАФ, КЛАСТЕР, МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО.

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

Цель работы – разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера.

В ходе работы был разработан алгоритм кластеризации.

В результате работы было написан алгоритм, решающий данные задачи.

Введение

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

Теория графов получила широкое применение на практике. Она применяется в гражданском строительстве, электротехнике, социологии и экономике и в других областях.

Одной из задач теории графов является кластеризация и построение минимального остовного дерева. Эти задачи часто возникают на практике: при группировке результатов поиска, проектировании компьютерных систем, соединении городов, составлении электрических цепей.

Целью данной работы является разработка алгоритма, выполняющего данные задачи.

Отчет содержит четыре раздела:

- постановка задачи курсового проектирования – это раздел, в котором описывается задача курсового проекта;

- схемы алгоритмов – это раздел, в котором описывается алгоритм и его схема;

- теоретический анализ – теория, необходимая для выполнения поставленной задачи;

- результаты тестирования – это раздел, в котором описываются результаты тестирований на правильность работы разработанного алгоритма.

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

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

2 Теоретический анализ

Граф G - это математический объект, состоящий из множества вершин X = {x ₁ , x ₂ ,..., x _n } и множества ребер A = {a ₁ , a ₂ ,..., a _k }.

Связный граф — такой граф, в котором между любой парой вершин существует по крайней мере один путь.

Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некоторое значение (вес ребра).

Вес ребра — значение, поставленное в соответствие данному ребру взвешенного графа. Обычно вес — вещественное число и его можно интерпретировать как «длину» ребра.

Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным. Ребра ориентированного графа называются дугами. Если направления ребер не указываются, то граф называется неориентированным (или просто графом).

Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер.

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n ) — это квадратная матрица A размера n , в которой значение элемента a_{i j} равно числу ребёр из i -й вершины графа в j -ю вершину.

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

Кластерный анализ — задача разбиения заданной выборки объектов (ситуаций) на подмножества, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались.

Кластер — группа элементов, характеризуемых общим свойством.

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

Лес — неориентированный граф без циклов. Компонентами связности леса являются деревья.

Дерево — это связный граф, не содержащий циклов.

Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном, взвешенном, неориентированном графе — это остовное дерево, имеющее минимальный возможный вес. Вес дерева — сумма весов входящих в него рёбер.

В данном курсовом проекте для построения минимального остовного дерева используется алгоритм Краскала. Рёбра графа упорядочиваются в порядке не убывания их весов и последовательно добавляются к графу. Если добавление нового ребра приведёт к образованию цикла, то это ребро пропускается. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным лесом минимального веса.

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

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

Шаг 1. Заполнение матрицы весов T .

Шаг 2. Создание матрицы смежности С .

Шаг 2а. Если расстояние между двумя точками s > d , то в матрицу заносится 0, иначе 1.

Шаг 2б. Повторение шага 2 N раз;

Шаг 3. Создание матрицы минимального ос

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать