Алгоритмы и структуры данных 2 2017/2018/Clustering - История изменений

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

2017-10-13T11:30:35Z

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

← Предыдущая версия		Версия от 11:30, 13 октября 2017
Строка 9:		Строка 9:
	Для удобства реализации и визуализации мы будем работать с точками на плоскости.		Для удобства реализации и визуализации мы будем работать с точками на плоскости.

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

	[https://www.dropbox.com/s/xuds26z1lf0qaqw/cluster.cpp?dl=0 Заготовка с кодом]		[https://www.dropbox.com/s/xuds26z1lf0qaqw/cluster.cpp?dl=0 Заготовка с кодом]

Aumnov в 12:13, 10 октября 2017

2017-10-10T12:13:41Z

← Предыдущая версия		Версия от 12:13, 10 октября 2017
Строка 1:		Строка 1:
	== Кластеризация объектов ==		== Кластеризация объектов ==

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

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

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

2017-10-10T12:13:00Z

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

← Предыдущая версия		Версия от 12:13, 10 октября 2017
Строка 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 нужно установить). При желании можно изучить ее параметры и запускать ее по-другому (например, с записью результата в файл), или использовать онлайн-версии.
	* gnuplot и ~~картинки~~		* В алгоритме на основе минимального остовного дерева используется полный граф на всех вершинах, где вес ребра между двумя точками равен расстоянию между ними на плоскости.
	* ~~MST и pairwise distance~~		* Заготовкой пользоваться не обязательно, программировать можно как на Python, так и на C++ (но заготовки для Python нет).
	* ~~TODO~~ Заготовкой пользоваться не обязательно, программировать можно как на Python, так и на C++ (но заготовки для ~~C++~~ нет).

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

2017-10-10T11:41:56Z

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

← Предыдущая версия		Версия от 11:41, 10 октября 2017
Строка 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++ нет).

Aumnov в 11:37, 10 октября 2017

2017-10-10T11:37:26Z

← Предыдущая версия		Версия от 11:37, 10 октября 2017
Строка 8:		Строка 8:

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

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

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

2017-10-10T11:33:34Z

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

← Предыдущая версия		Версия от 11:33, 10 октября 2017
Строка 5:		Строка 5:
	1) Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние;		1) Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние;

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

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

Aumnov: Новая страница: «== Кластеризация объектов == В этом задании мы рассмотрим задачу кластеризации объектов.…»

2017-10-10T11:29:57Z

Новая страница: «== Кластеризация объектов == В этом задании мы рассмотрим задачу кластеризации объектов.…»

Новая страница

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

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

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

2) Кластеризация алгоритмом k-means, минимизирующая среднее расстояние от центра кластера.

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