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

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

2016-11-28T12:47:56Z

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

	{{algorithm		{{algorithm

Dexter в 08:28, 24 ноября 2016

2016-11-24T08:28:04Z

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

Dexter в 08:27, 24 ноября 2016

2016-11-24T08:27:03Z

← Предыдущая версия		Версия от 08:27, 24 ноября 2016
Строка 1:		Строка 1:
			{Assignment\|Преподаватель 1\|Dexter}}
	{{Assignment\|Zhum}}		{{Assignment\|Zhum}}

Zhum в 12:01, 23 ноября 2016

2016-11-23T12:01:02Z

← Предыдущая версия		Версия от 12:01, 23 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|Zhum}}

	{{algorithm		{{algorithm

Avasilenko: /* Свойства и структура алгоритма */

2016-11-17T05:34:08Z

Свойства и структура алгоритма

← Предыдущая версия		Версия от 05:34, 17 ноября 2016
Строка 45:		Строка 45:
	На каждой итерации алгоритма выбирается пара (медоид, не-медоид) такая, что замена медоида <math>x_{m_l}</math> на не-медоид <math>x_{o_h}</math> дает лучшую кластеризацию из возможных. Оценка кластеризации выполняется с помощью целевой функции, вычисляемой как сумма расстояний от каждого объекта до ближайшего медоида:		На каждой итерации алгоритма выбирается пара (медоид, не-медоид) такая, что замена медоида <math>x_{m_l}</math> на не-медоид <math>x_{o_h}</math> дает лучшую кластеризацию из возможных. Оценка кластеризации выполняется с помощью целевой функции, вычисляемой как сумма расстояний от каждого объекта до ближайшего медоида:

	:<math>E = \sum_{j = 1}^n \min_{1 \leq l \leq k} \rho ( x_{m_l},x_{~~o_h~~} )</math>		:<math>E = \sum_{j = 1}^n \min_{1 \leq l \leq k} \rho ( x_{m_l},x_{o_j} )</math>

	Процедура изменения множества медоидов повторяется, пока есть возможность улучшения значения целевой функции.		Процедура изменения множества медоидов повторяется, пока есть возможность улучшения значения целевой функции.
Строка 599:		Строка 599:

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


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

Anastasia в 12:29, 16 ноября 2016

2016-11-16T12:29:23Z

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

	{{algorithm		{{algorithm

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

2016-11-16T12:24:09Z

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

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


	[https://github.com/phonexicum/pam-mpi-cmc Исследованная параллельная реализация на языке C++]		[https://github.com/phonexicum/pam-mpi-cmc Исследованная параллельная реализация на языке C++] (реализация написана самостоятельно)

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===

Zhum в 08:28, 16 ноября 2016

2016-11-16T08:28:45Z

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

	{{algorithm		{{algorithm

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

2016-11-14T16:42:56Z

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

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

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

	~~''Сдача этого параграфа перенесена на 15-е ноября.''~~

	~~''Параграф пока ещё в разработке.''~~


	Структура графа алгоритма (см. 1.7 [[#Информационный граф\| Информационный граф алгоритма]]) такова, что позволяет надеяться на получение хорошей масштабируемости.		Структура графа алгоритма (см. 1.7 [[#Информационный граф\| Информационный граф алгоритма]]) такова, что позволяет надеяться на получение хорошей масштабируемости.

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

2016-11-14T16:41:40Z

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

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


	На рисунке 5б, видно, что пики организованы в прямые. Это обусловлено инвариантностью величины <math>a</math> в соответствии с описанной в [[#Вычислительное ядро алгоритма \| вычислительном ядре фазы SWAP]] оптимизацией. На рисунке 3 для [[#Информационный граф фазы SWAP\| информационного графа фазы SWAP]] наглядно видно, что при построчном распределении вычислений <math>\overline{b}_{x_{m_s, o_h}}</math> возможно возникновение ~~3-х типов~~ ситуаций:		На рисунке 5б, видно, что пики организованы в прямые. Это обусловлено инвариантностью величины <math>a</math> в соответствии с описанной в [[#Вычислительное ядро алгоритма \| вычислительном ядре фазы SWAP]] оптимизацией. На рисунке 3 для [[#Информационный граф фазы SWAP\| информационного графа фазы SWAP]] наглядно видно, что при построчном распределении вычислений <math>\overline{b}_{x_{m_s, o_h}}</math> возможно возникновение следующих ситуаций (далее при '' '''k * (n-k) mod p == 0''' '' обозначим '' '''r = k * (n-k) / p''' ''):
	* при '' '''k * (n-k) mod p == 0''' '' обозначим '' '''r = k * (n-k) / p''' ''		# при '' '''r < (n-k)''' '', если '' '''(n-k) mod r == 0''' '', то каждому процессу необходимо вычислить ровно одну величину <math>\overline{a}_{x_{m_s}};</math>
	*# при '' '''r < (n-k)''' '', если '' '''(n-k) mod r == 0''' '', то каждому процессу необходимо вычислить ровно одну величину <math>\overline{a}_{x_{m_s}};</math>		# при '' '''r ≥ (n-k)''' '', если '' '''k mod p == 0''' '', то каждому процессу необходимо вычислить несколько соответствующих ему величин <math>\overline{a}_{x_{m_s}},</math> при этом каждая величина будет вычислена ровно в одном процессе;
	*# при '' '''r ≥ (n-k)''' '', если '' '''k mod p == 0''' '', то каждому процессу необходимо вычислить несколько соответствующих ему величин <math>\overline{a}_{x_{m_s}},</math> при этом каждая величина будет вычислена ровно в одном процессе;		# в остальных случаях вычисления величин <math>\overline{b}_{x_{m_s, o_h}}</math> распределяются между процессами таким образом, что часть процессов обрабатывает больше величин <math>\overline{a}_{x_{m_s}}</math> нежели остальные (ситуация возникает при обработке процессом последних элементов одной строки и первых элементов следующей). Подобная ситуация приводит к дополнительным вычислениям на некоторых процессах и, как следствие, к простою остальных, в связи с чем происходит падение производительности.
	~~<ol><li value="3">~~в остальных случаях вычисления величин <math>\overline{b}_{x_{m_s, o_h}}</math> распределяются между процессами таким образом, что часть процессов обрабатывает больше величин <math>\overline{a}_{x_{m_s}}</math> нежели остальные (ситуация возникает при обработке процессом последних элементов одной строки и первых элементов следующей). Подобная ситуация приводит к дополнительным вычислениям на некоторых процессах и, как следствие, к простою остальных, в связи с чем происходит падение производительности.~~</li></ol>~~