Алгоритмы и структуры данных 2 2017/2018/Clustering — различия между версиями
Aumnov (обсуждение | вклад) (→Кластеризация объектов) |
Aumnov (обсуждение | вклад) (→Кластеризация объектов) |
||
| Строка 15: | Строка 15: | ||
Пояснения по коду: | Пояснения по коду: | ||
* Для работы кода необходимо создать папки 'plot_base', 'plot_mst', 'plot_mdc', в которые код записывает данные для визуализации для исходных данных, результата алгоритма 1 и алгоритма 2 соответственно. | * Для работы кода необходимо создать папки 'plot_base', 'plot_mst', 'plot_mdc', в которые код записывает данные для визуализации для исходных данных, результата алгоритма 1 и алгоритма 2 соответственно. | ||
| − | * gnuplot -p | + | * Для того, чтобы визуализировать результат, нужно перейти в одну из папок, и запустить из нее команду "gnuplot script.txt -p" (утилиту gnuplot нужно установить). При желании можно изучить ее параметры и запускать ее по-другому (например, с записью результата в файл), или использовать онлайн-версии. |
| − | + | * В алгоритме на основе минимального остовного дерева используется полный граф на всех вершинах, где вес ребра между двумя точками равен расстоянию между ними на плоскости. | |
| − | * | + | * Заготовкой пользоваться не обязательно, программировать можно как на Python, так и на C++ (но заготовки для Python нет). |
| − | * | + | |
Версия 15:13, 10 октября 2017
Кластеризация объектов
В этом задании мы рассмотрим задачу кластеризации объектов. Вам необходимо реализовать два алгоритма кластеризации:
1) Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние;
2) Кластеризация жадным алгоритмом, приближенно минимизирующая максимальное внутрикластерное расстояние.
Для удобства реализации и визуализации мы будем работать с точками на плоскости.
Вам дается код с заготовкой на C++, в котором реализована генерация случайных наборов точек, запись результата в скрипт для отображения с помощью утилиты gnuplot, а также некоторый набор полезных функций и классов. Необходимо реализовать функции кластеризации и проверить их работу на примерах нескольких наборов точек.
Пояснения по коду:
- Для работы кода необходимо создать папки 'plot_base', 'plot_mst', 'plot_mdc', в которые код записывает данные для визуализации для исходных данных, результата алгоритма 1 и алгоритма 2 соответственно.
- Для того, чтобы визуализировать результат, нужно перейти в одну из папок, и запустить из нее команду "gnuplot script.txt -p" (утилиту gnuplot нужно установить). При желании можно изучить ее параметры и запускать ее по-другому (например, с записью результата в файл), или использовать онлайн-версии.
- В алгоритме на основе минимального остовного дерева используется полный граф на всех вершинах, где вес ребра между двумя точками равен расстоянию между ними на плоскости.
- Заготовкой пользоваться не обязательно, программировать можно как на Python, так и на C++ (но заготовки для Python нет).
