Алгоритмы и структуры данных 2 2017/2018/Clustering — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Кластеризация объектов)
Строка 10: Строка 10:
  
 
Вам дается код с заготовкой на C++, в котором реализована генерация случайных наборов точек, запись результата в скрипт для отображения с помощью утилиты gnuplot, а также некоторый набор полезных функций и классов. Необходимо реализовать функции кластеризации и проверить их работу на примерах нескольких наборов точек.
 
Вам дается код с заготовкой на C++, в котором реализована генерация случайных наборов точек, запись результата в скрипт для отображения с помощью утилиты gnuplot, а также некоторый набор полезных функций и классов. Необходимо реализовать функции кластеризации и проверить их работу на примерах нескольких наборов точек.
 +
 +
[https://www.dropbox.com/s/xuds26z1lf0qaqw/cluster.cpp?dl=0 Заготовка с кодом]
 +
 +
Пояснения по коду:
 +
* Для работы кода необходимо создать папки 'plot_base', 'plot_mst', 'plot_mdc', в которые код записывает данные для визуализации для исходных данных, результата алгоритма 1 и алгоритма 2 соответственно.
 +
* gnuplot -p
 +
* gnuplot и картинки
 +
* MST и pairwise distance
 +
* TODO Заготовкой пользоваться не обязательно, программировать можно как на Python, так и на C++ (но заготовки для C++ нет).

Версия 14:41, 10 октября 2017

Кластеризация объектов

В этом задании мы рассмотрим задачу кластеризации объектов. Вам необходимо реализовать два алгоритма кластеризации:

1) Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние;

2) Кластеризация жадным алгоритмом, приближенно минимизирующая максимальное внутрикластерное расстояние.

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

Вам дается код с заготовкой на C++, в котором реализована генерация случайных наборов точек, запись результата в скрипт для отображения с помощью утилиты gnuplot, а также некоторый набор полезных функций и классов. Необходимо реализовать функции кластеризации и проверить их работу на примерах нескольких наборов точек.

Заготовка с кодом

Пояснения по коду:

  • Для работы кода необходимо создать папки 'plot_base', 'plot_mst', 'plot_mdc', в которые код записывает данные для визуализации для исходных данных, результата алгоритма 1 и алгоритма 2 соответственно.
  • gnuplot -p
  • gnuplot и картинки
  • MST и pairwise distance
  • TODO Заготовкой пользоваться не обязательно, программировать можно как на Python, так и на C++ (но заготовки для C++ нет).