Участник:Maria Zaitseva/PAM (Partitioning Around Medoids) - История изменений

ASA в 13:28, 19 декабря 2016

2016-12-19T13:28:55Z

← Предыдущая версия		Версия от 13:28, 19 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|~~Преподаватель 1~~\|Dexter}}		{{Assignment\|ASA\|Dexter}}
	~~{{Assignment\|ASA}}~~
	~~{{Assignment}}~~


	{{algorithm		{{algorithm

Dexter в 15:55, 17 декабря 2016

2016-12-17T15:55:27Z

← Предыдущая версия		Версия от 15:55, 17 декабря 2016
Строка 1:		Строка 1:
			{{Assignment\|Преподаватель 1\|Dexter}}
	{{Assignment\|ASA}}		{{Assignment\|ASA}}
	{{Assignment}}		{{Assignment}}

Maria Zaitseva в 13:41, 10 декабря 2016

2016-12-10T13:41:30Z

← Предыдущая версия		Версия от 13:41, 10 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|ASA}}		{{Assignment\|ASA}}
			{{Assignment}}

Maria Zaitseva в 13:38, 10 декабря 2016

2016-12-10T13:38:39Z

← Предыдущая версия		Версия от 13:38, 10 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|ASA}}		{{Assignment\|ASA}}


	{{algorithm		{{algorithm
Строка 6:		Строка 7:
	\| input_data = <math>\frac{n (n - 1)}{2}</math>		\| input_data = <math>\frac{n (n - 1)}{2}</math>
	\| output_data = <math>k</math>		\| output_data = <math>k</math>
			\| pf_height = <math>O(Tkn)</math>
			\| pf_width = <math>O(k(n-k))</math>
	}}		}}

Maria Zaitseva: /* Масштабируемость алгоритма и его реализации */

2016-12-10T13:32:11Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 13:32, 10 декабря 2016
Строка 260:		Строка 260:
	Для оценки производительности алгоритма осуществлялся расчет числа операций с плавающей запятой в секунду (FLOPs или GFLOPs). Для этого при каждом запуске рассчитывалось время работы алгоритма, число итераций шага ''SWAP'', по данным значениям можно получить точное число операций сложения, вычитания и сравнения вещественных чисел (оно равно последовательной сложности алгоритма), поделив его на время работы можно получить оценку числа FLOP в секунду. График изменения производительности в зависимости от числа процессоров и числа кластеризуемых элементов представлен ниже. Интерактивный график доступен по [https://plot.ly/~kovalexal/7/ ссылке].		Для оценки производительности алгоритма осуществлялся расчет числа операций с плавающей запятой в секунду (FLOPs или GFLOPs). Для этого при каждом запуске рассчитывалось время работы алгоритма, число итераций шага ''SWAP'', по данным значениям можно получить точное число операций сложения, вычитания и сравнения вещественных чисел (оно равно последовательной сложности алгоритма), поделив его на время работы можно получить оценку числа FLOP в секунду. График изменения производительности в зависимости от числа процессоров и числа кластеризуемых элементов представлен ниже. Интерактивный график доступен по [https://plot.ly/~kovalexal/7/ ссылке].

	[[file:~~perf~~.png\|thumb\|center\|553px\|Рис.4. Изменение производительности в зависимости от числа процессоров и числа кластеризуемых элементов]]		[[file:PAM_perf.png\|thumb\|center\|553px\|Рис.4. Изменение производительности в зависимости от числа процессоров и числа кластеризуемых элементов]]

	Масштабируемость алгоритма была получена путем деления реальной производительности на пиковую произвдительность <math>s</math> задействованных ядер (пиковая производительность одного ядра "Ломоносова" составляет ''5.686'' GFLOPs). График изменения эффективности в зависимости от числа процессоров и числа кластеризуемых элементов представлен ниже. Интерактивный график доступен по [https://plot.ly/~kovalexal/9/ ссылке].		Масштабируемость алгоритма была получена путем деления реальной производительности на пиковую произвдительность <math>s</math> задействованных ядер (пиковая производительность одного ядра "Ломоносова" составляет ''5.686'' GFLOPs). График изменения эффективности в зависимости от числа процессоров и числа кластеризуемых элементов представлен ниже. Интерактивный график доступен по [https://plot.ly/~kovalexal/9/ ссылке].

	[[file:~~eff~~.png\|thumb\|center\|553px\|Рис.5. Изменение эффективности в зависимости от числа процессоров и числа кластеризуемых элементов]]		[[file:PAM_eff.png\|thumb\|center\|553px\|Рис.5. Изменение эффективности в зависимости от числа процессоров и числа кластеризуемых элементов]]

Maria Zaitseva: /* Информационный граф шага SWAP */

2016-12-10T13:27:43Z

Информационный граф шага SWAP

← Предыдущая версия		Версия от 13:27, 10 декабря 2016
Строка 178:		Строка 178:
	На рис.2 показана информационная структура шага SWAP алгоритма PAM на некотором шаге.		На рис.2 показана информационная структура шага SWAP алгоритма PAM на некотором шаге.

	[[file:~~Pam_swap~~.png\|thumb\|center\|553px\|Рис.2. Информационная структура шага SWAP алгоритма PAM на шаге <math>t</math>]]		[[file:Pam_swap_new.png\|thumb\|center\|553px\|Рис.2. Информационная структура шага SWAP алгоритма PAM на шаге <math>t</math>]]

	''Операции'':		''Операции'':

Maria Zaitseva: /* Математическое описание алгоритма */

2016-12-10T13:13:37Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 13:13, 10 декабря 2016
Строка 46:		Строка 46:
	''Выходные данные'':		''Выходные данные'':

	* <math>m = \{m_1,\dots,m_k\}\subset o</math> –– множество индексов объектов, принятых в качестве медоидов		* <math>m = \{m_1,\dots,m_k\}\subset o</math> –– множество индексов объектов, принятых в качестве медоидов; <math> M </math>--множество медоидов.

	Принадлежность объекта к определенному кластеру определяется как индекс ближайшего к нему медоида:		Принадлежность объекта к определенному кластеру определяется как индекс ближайшего к нему медоида:

ASA в 11:03, 18 ноября 2016

2016-11-18T11:03:32Z

← Предыдущая версия		Версия от 11:03, 18 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|ASA}}

	{{algorithm		{{algorithm

Maria Zaitseva в 11:20, 17 ноября 2016

2016-11-17T11:20:15Z

← Предыдущая версия		Версия от 11:20, 17 ноября 2016
Строка 1:		Строка 1:
			{{Assignment}}

	{{algorithm		{{algorithm
	\| name = Partitioning Around Medoids		\| name = Partitioning Around Medoids

Kovalexal: /* Масштабируемость алгоритма и его реализации */

2016-11-17T10:11:10Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 10:11, 17 ноября 2016
Строка 241:		Строка 241:
	== Масштабируемость алгоритма и его реализации ==		== Масштабируемость алгоритма и его реализации ==

	Для изучения масштабируемости алгоритма была выполнена его [https://gitlab.com/kovalexal/pam-lomonosov реализация] с использованием механизма MPI на языке программирования C++. Данная реализация использует библиотеку [http://www.boost.org Boost] (модуль MPI для удобного взаимодействия C++ и MPI и модуль uBLAS для работы с матрицами). Исследование масштабируемости описанной реализации производилось на суперкомпьютере [https://parallel.ru/cluster/lomonosov.html "Ломоносов"].		Для изучения масштабируемости алгоритма была выполнена его [https://gitlab.com/kovalexal/pam-lomonosov реализация] с использованием механизма MPI на языке программирования C++. Данная реализация использует библиотеку [http://www.boost.org Boost] (модуль MPI для удобного взаимодействия C++ и MPI и модуль uBLAS для работы с матрицами). Исследование масштабируемости описанной реализации производилось на суперкомпьютере [https://parallel.ru/cluster/lomonosov.html "Ломоносов"]. Для сборки программы использовался компилятор gcc версии 5.2.0 с опциями "-std=c++11 -O3" совместно с OpenMPI версии 1.8.4.

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