Участник:Sergey Lavrushkin/EM-алгоритм кластеризации - История изменений

ASA в 12:49, 28 ноября 2016

2016-11-28T12:49:20Z

← Предыдущая версия		Версия от 12:49, 28 ноября 2016
Строка 1:		Строка 1:
	{{Assignment\|~~Преподаватель 1~~\|Dexter}}		{{Assignment\|Algoman\|Dexter}}
	{{algorithm		{{algorithm
	\| name = EM-алгоритм кластеризации (1 итерация)		\| name = EM-алгоритм кластеризации (1 итерация)

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

2016-11-16T23:08:40Z

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

← Предыдущая версия		Версия от 23:08, 16 ноября 2016
Строка 285:		Строка 285:
	Для каждого набора параметров было проведено по 3 запуска для избежания выбросов. Для каждого запуска измерялось среднее время выполнения одной итерации алгоритма. На следующем рисунке приведен график производительности данной реализации EM-алгоритма кластеризации в зависимости от изменяемых параметров запуска.		Для каждого набора параметров было проведено по 3 запуска для избежания выбросов. Для каждого запуска измерялось среднее время выполнения одной итерации алгоритма. На следующем рисунке приведен график производительности данной реализации EM-алгоритма кластеризации в зависимости от изменяемых параметров запуска.

	[[Файл:Em-performance-Lavrushkin.png\|thumb\|1650px\|center\|Рисунок 8. Параллельная реализация EM-алгоритма кластеризации. Изменение производительности в зависимости от числа процессов и числа элементов выборки.]]		[[Файл:Em-performance-avg-Lavrushkin.png\|thumb\|1650px\|center\|Рисунок 8. Параллельная реализация EM-алгоритма кластеризации. Изменение производительности в зависимости от числа процессов и числа элементов выборки.]]

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

Sergey Lavrushkin: /* Программная реализация алгоритма */

2016-11-16T23:03:54Z

Программная реализация алгоритма

← Предыдущая версия		Версия от 23:03, 16 ноября 2016
Строка 253:		Строка 253:

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

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

	~~==== Масштабируемость алгоритма ====~~

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

	Для исследования масштабируемости EM-алгоритм кластеризации был реализован с помощью технологии MPI. Была реализована версия алгоритма с диагональными матрицами ковариации. В качестве критерия останова было выбрано достижение максимального числа итераций (соответственно, вычисление логарифмического правдоподобия на каждой итерации не проводится).		Для исследования масштабируемости EM-алгоритм кластеризации был реализован с помощью технологии MPI. Была реализована версия алгоритма с диагональными матрицами ковариации. В качестве критерия останова было выбрано достижение максимального числа итераций (соответственно, вычисление логарифмического правдоподобия на каждой итерации не проводится).
Строка 271:		Строка 265:
	### Каждый процесс вычисляет суммы <math>\sum_{i = 1}^{n\_proc_i}y_{ij}x_i</math> для каждого кластера <math>j = \overline{1, k}</math> по своему набору элементов выборки и отправляет полученные суммы процессу 0. Процесс 0 вычисляет суммы <math>\sum_{i = 1}^{n}y_{ij}x_i</math> для каждого кластера <math>j = \overline{1, k}</math> по всем элементам выборки и отправляет их остальным процессам. С помощью полученных сумм каждый процесс вычисляет значения математических ожиданий <math>\mu_j</math>.		### Каждый процесс вычисляет суммы <math>\sum_{i = 1}^{n\_proc_i}y_{ij}x_i</math> для каждого кластера <math>j = \overline{1, k}</math> по своему набору элементов выборки и отправляет полученные суммы процессу 0. Процесс 0 вычисляет суммы <math>\sum_{i = 1}^{n}y_{ij}x_i</math> для каждого кластера <math>j = \overline{1, k}</math> по всем элементам выборки и отправляет их остальным процессам. С помощью полученных сумм каждый процесс вычисляет значения математических ожиданий <math>\mu_j</math>.
	### Каждый процесс вычисляет суммы <math>sum_l = \sum_{i = 1}^{n\_proc_i}y_{ij}(x_{il} - \mu_{jl}^{new})^2 \, (l = \overline{1, q})</math> для каждого кластера <math>j = \overline{1, k}</math> по своему набору элементов выборки и отправляет полученные суммы процессу 0. Процесс 0 вычисляет суммы <math>sum_l = \sum_{i = 1}^{n}y_{ij}(x_{il} - \mu_{jl}^{new})^2 \, (l = \overline{1, q})</math> для каждого кластера <math>j = \overline{1, k}</math> по всем элементам выборки и отправляет их остальным процессам. С помощью полученных сумм каждый процесс вычисляет значения диагональных элементов матриц ковариации <math>\Sigma_j</math>.		### Каждый процесс вычисляет суммы <math>sum_l = \sum_{i = 1}^{n\_proc_i}y_{ij}(x_{il} - \mu_{jl}^{new})^2 \, (l = \overline{1, q})</math> для каждого кластера <math>j = \overline{1, k}</math> по своему набору элементов выборки и отправляет полученные суммы процессу 0. Процесс 0 вычисляет суммы <math>sum_l = \sum_{i = 1}^{n}y_{ij}(x_{il} - \mu_{jl}^{new})^2 \, (l = \overline{1, q})</math> для каждого кластера <math>j = \overline{1, k}</math> по всем элементам выборки и отправляет их остальным процессам. С помощью полученных сумм каждый процесс вычисляет значения диагональных элементов матриц ковариации <math>\Sigma_j</math>.

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

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

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

	Распараллеливание было проведено по числу элементов выборки, поэтому и исследование масштабируемости было проведено для числа элементов выборки. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].		Распараллеливание было проведено по числу элементов выборки, поэтому и исследование масштабируемости было проведено для числа элементов выборки. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].
Строка 281:		Строка 281:
	* число итераций 50.		* число итераций 50.

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

			Для каждого набора параметров было проведено по 3 запуска для избежания выбросов. Для каждого запуска измерялось среднее время выполнения одной итерации алгоритма. На следующем рисунке приведен график производительности данной реализации EM-алгоритма кластеризации в зависимости от изменяемых параметров запуска.

	[[Файл:Em-performance-Lavrushkin.png\|thumb\|1650px\|center\|Рисунок 8. Параллельная реализация EM-алгоритма кластеризации. Изменение производительности в зависимости от числа процессов и числа элементов выборки.]]		[[Файл:Em-performance-Lavrushkin.png\|thumb\|1650px\|center\|Рисунок 8. Параллельная реализация EM-алгоритма кластеризации. Изменение производительности в зависимости от числа процессов и числа элементов выборки.]]

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

	[https://github.com/HighVoltageRocknRoll/EM-clusterization_scalability Исследованная параллельная MPI-реализация на языке C]		[https://github.com/HighVoltageRocknRoll/EM-clusterization_scalability Исследованная параллельная MPI-реализация на языке C]

Dexter в 18:31, 16 ноября 2016

2016-11-16T18:31:07Z

← Предыдущая версия		Версия от 18:31, 16 ноября 2016
Строка 1:		Строка 1:
			{{Assignment\|Преподаватель 1\|Dexter}}
	{{algorithm		{{algorithm
	\| name = EM-алгоритм кластеризации (1 итерация)		\| name = EM-алгоритм кластеризации (1 итерация)

Algoman в 13:04, 16 ноября 2016

2016-11-16T13:04:54Z

← Предыдущая версия		Версия от 13:04, 16 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~
	~~{{Assignment\|Algoman}}~~

	{{algorithm		{{algorithm
	\| name = EM-алгоритм кластеризации (1 итерация)		\| name = EM-алгоритм кластеризации (1 итерация)

Sergey Lavrushkin в 22:41, 11 ноября 2016

2016-11-11T22:41:24Z

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

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

2016-11-11T22:38:34Z

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

← Предыдущая версия		Версия от 22:38, 11 ноября 2016
Строка 270:		Строка 270:
	## M-шаг.		## M-шаг.
	### Каждый процесс вычисляет суммы значений скрытых переменных <math>\sum_{i = 1}^{n\_proc_i}y_{ij}</math> для каждого кластера <math>j = \overline{1, k}</math> по своему набору элементов выборки и отправляет полученные суммы процессу 0. Процесс 0 вычисляет значения <math>n_j</math> по полученным суммам и отправляет их остальным процессам. Каждый процесс обновляет значения <math>w_j</math> по полученным значениям <math>n_j</math>.		### Каждый процесс вычисляет суммы значений скрытых переменных <math>\sum_{i = 1}^{n\_proc_i}y_{ij}</math> для каждого кластера <math>j = \overline{1, k}</math> по своему набору элементов выборки и отправляет полученные суммы процессу 0. Процесс 0 вычисляет значения <math>n_j</math> по полученным суммам и отправляет их остальным процессам. Каждый процесс обновляет значения <math>w_j</math> по полученным значениям <math>n_j</math>.
	### Каждый процесс вычисляет суммы <math>\sum_{i = 1}^{n\_proc_i}y_{ij}x_i</math> для каждого кластера <math>j = \overline{1, k}</math> по своему набору элементов выборки и отправляет полученные суммы процессу 0. Процесс 0 вычисляет суммы <math>>\sum_{i = 1}^{n}y_{ij}x_i</math> для каждого кластера <math>j = \overline{1, k}</math> по всем элементам выборки и отправляет их остальным процессам. С помощью полученных сумм каждый процесс вычисляет значения математических ожиданий <math>\mu_j</math>.		### Каждый процесс вычисляет суммы <math>\sum_{i = 1}^{n\_proc_i}y_{ij}x_i</math> для каждого кластера <math>j = \overline{1, k}</math> по своему набору элементов выборки и отправляет полученные суммы процессу 0. Процесс 0 вычисляет суммы <math>\sum_{i = 1}^{n}y_{ij}x_i</math> для каждого кластера <math>j = \overline{1, k}</math> по всем элементам выборки и отправляет их остальным процессам. С помощью полученных сумм каждый процесс вычисляет значения математических ожиданий <math>\mu_j</math>.
	### Каждый процесс вычисляет суммы <math>sum_l = \sum_{i = 1}^{n\_proc_i}y_{ij}(x_{il} - \mu_{jl}^{new})^2 \, (l = \overline{1, q})</math> для каждого кластера <math>j = \overline{1, k}</math> по своему набору элементов выборки и отправляет полученные суммы процессу 0. Процесс 0 вычисляет суммы <math>sum_l = \sum_{i = 1}^{n}y_{ij}(x_{il} - \mu_{jl}^{new})^2 \, (l = \overline{1, q})</math> для каждого кластера <math>j = \overline{1, k}</math> по всем элементам выборки и отправляет их остальным процессам. С помощью полученных сумм каждый процесс вычисляет значения диагональных элементов матриц ковариации <math>\Sigma_j</math>.		### Каждый процесс вычисляет суммы <math>sum_l = \sum_{i = 1}^{n\_proc_i}y_{ij}(x_{il} - \mu_{jl}^{new})^2 \, (l = \overline{1, q})</math> для каждого кластера <math>j = \overline{1, k}</math> по своему набору элементов выборки и отправляет полученные суммы процессу 0. Процесс 0 вычисляет суммы <math>sum_l = \sum_{i = 1}^{n}y_{ij}(x_{il} - \mu_{jl}^{new})^2 \, (l = \overline{1, q})</math> для каждого кластера <math>j = \overline{1, k}</math> по всем элементам выборки и отправляет их остальным процессам. С помощью полученных сумм каждый процесс вычисляет значения диагональных элементов матриц ковариации <math>\Sigma_j</math>.

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

2016-11-11T22:35:52Z

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

← Предыдущая версия		Версия от 22:35, 11 ноября 2016
Строка 284:		Строка 284:
	Для каждого набора параметров измерялось среднее время выполнения одной итерации алгоритма. На следующем рисунке приведен график производительности данной реализации EM-алгоритма кластеризации в зависимости от изменяемых параметров запуска.		Для каждого набора параметров измерялось среднее время выполнения одной итерации алгоритма. На следующем рисунке приведен график производительности данной реализации EM-алгоритма кластеризации в зависимости от изменяемых параметров запуска.

	[[Файл:Em-performance-Lavrushkin.png\|thumb\|~~1700px~~\|center\|Рисунок 8. Параллельная реализация EM-алгоритма кластеризации. Изменение производительности в зависимости от числа процессов и числа элементов выборки.]]		[[Файл:Em-performance-Lavrushkin.png\|thumb\|1650px\|center\|Рисунок 8. Параллельная реализация EM-алгоритма кластеризации. Изменение производительности в зависимости от числа процессов и числа элементов выборки.]]

	[https://github.com/HighVoltageRocknRoll/EM-clusterization_scalability Исследованная параллельная MPI-реализация на языке C]		[https://github.com/HighVoltageRocknRoll/EM-clusterization_scalability Исследованная параллельная MPI-реализация на языке C]

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

2016-11-11T22:35:29Z

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

← Предыдущая версия		Версия от 22:35, 11 ноября 2016
Строка 284:		Строка 284:
	Для каждого набора параметров измерялось среднее время выполнения одной итерации алгоритма. На следующем рисунке приведен график производительности данной реализации EM-алгоритма кластеризации в зависимости от изменяемых параметров запуска.		Для каждого набора параметров измерялось среднее время выполнения одной итерации алгоритма. На следующем рисунке приведен график производительности данной реализации EM-алгоритма кластеризации в зависимости от изменяемых параметров запуска.

	[[Файл:Em-performance-Lavrushkin.png\|thumb\|~~1800px~~\|center\|Рисунок 8. Параллельная реализация EM-алгоритма кластеризации. Изменение производительности в зависимости от числа процессов и числа элементов выборки.]]		[[Файл:Em-performance-Lavrushkin.png\|thumb\|1700px\|center\|Рисунок 8. Параллельная реализация EM-алгоритма кластеризации. Изменение производительности в зависимости от числа процессов и числа элементов выборки.]]

	[https://github.com/HighVoltageRocknRoll/EM-clusterization_scalability Исследованная параллельная MPI-реализация на языке C]		[https://github.com/HighVoltageRocknRoll/EM-clusterization_scalability Исследованная параллельная MPI-реализация на языке C]

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

2016-11-11T22:35:07Z

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

← Предыдущая версия		Версия от 22:35, 11 ноября 2016
Строка 284:		Строка 284:
	Для каждого набора параметров измерялось среднее время выполнения одной итерации алгоритма. На следующем рисунке приведен график производительности данной реализации EM-алгоритма кластеризации в зависимости от изменяемых параметров запуска.		Для каждого набора параметров измерялось среднее время выполнения одной итерации алгоритма. На следующем рисунке приведен график производительности данной реализации EM-алгоритма кластеризации в зависимости от изменяемых параметров запуска.

	[[Файл:Em-performance-Lavrushkin.png\|thumb\|~~2000px~~\|center\|Рисунок 8. Параллельная реализация EM-алгоритма кластеризации. Изменение производительности в зависимости от числа процессов и числа элементов выборки.]]		[[Файл:Em-performance-Lavrushkin.png\|thumb\|1800px\|center\|Рисунок 8. Параллельная реализация EM-алгоритма кластеризации. Изменение производительности в зависимости от числа процессов и числа элементов выборки.]]

	[https://github.com/HighVoltageRocknRoll/EM-clusterization_scalability Исследованная параллельная MPI-реализация на языке C]		[https://github.com/HighVoltageRocknRoll/EM-clusterization_scalability Исследованная параллельная MPI-реализация на языке C]