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

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

2016-11-28T12:50:11Z

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

	{{algorithm		{{algorithm

Dexter в 14:51, 18 ноября 2016

2016-11-18T14:51:25Z

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

Антон Тодуа: /* Макроструктура алгоритма */

2016-11-17T12:49:12Z

Макроструктура алгоритма

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


	Значение <math>T_{ijh}</math> представляет собой число, которое добавляется к значению <math>D_{j}</math> в результате выполнения операции ''обмена'' <math>i</math>-го медоида и <math>h</math>-го объекта. Для вычисления <math>C_{ij}</math> следует рассмотреть два случая. В первом случае, когда <math>D_{j} = d_{ij}</math> (<math>i</math>-й объект является медоидом <math>j</math>-го объекта) может быть два варианта: <math>E_{j} <= d_{jh}</math> (медоидом <math>j</math>-го объекта станет второго ближайший к нему медоид), тогда справедливо равенство <math>T_{ijh} = E_{j} - D_{j}</math> и <math>E_{j} > d_{jh}</math> (медоидом <math>j</math>-го объекта станет <math>h</math>-й объект), тогда справедливо равенство <math>T_{ijh} = d_{jh} - D_{j}</math>. Во втором случае, когда <math>D_{j} != d_{ij}</math> (<math>i</math>-й объект НЕ является медоидом <math>j</math>-го объекта) также может быть два варианта: <math>D_{j} <= d_{jh}</math> (медоид <math>j</math>-го объекта не изменится), тогда справедливо равенство <math>T_{ijh} = 0</math> и <math>D_{j} > d_{jh}</math> (медоидом <math>j</math>-го объекта станет <math>h</math>-й объект), тогда справедливо равенство <math>T_{ijh} = d_{jh} - D_{j}</math>. Таким образом, в первом случае (<math>i</math>-й объект является медоидом <math>j</math>-го объекта) значение <math>T_{ijh}</math> может быть вычислено по формуле <math>T_{ijh} = min(E_{j}, d_{jh}) - D_{j}</math>, а во втором (<math>i</math>-й объект НЕ является медоидом <math>j</math>-го объекта) – по формуле <math>T_{ijh} = min(d_{jh} - D_{j}, 0)</math>.		Значение <math>T_{ijh}</math> представляет собой число, которое добавляется к значению <math>D_{j}</math> в результате выполнения операции ''обмена'' <math>i</math>-го медоида и <math>h</math>-го объекта. Для вычисления <math>C_{ij}</math> следует рассмотреть два случая. В первом случае, когда <math>D_{j} = d_{ij}</math> (<math>i</math>-й объект является медоидом <math>j</math>-го объекта) может быть два варианта: <math>E_{j} <= d_{jh}</math> (медоидом <math>j</math>-го объекта станет второго ближайший к нему медоид), тогда справедливо равенство <math>T_{ijh} = E_{j} - D_{j}</math> и <math>E_{j} > d_{jh}</math> (медоидом <math>j</math>-го объекта станет <math>h</math>-й объект), тогда справедливо равенство <math>T_{ijh} = d_{jh} - D_{j}</math>. Во втором случае, когда <math>D_{j} != d_{ij}</math> (<math>i</math>-й объект НЕ является медоидом <math>j</math>-го объекта) также может быть два варианта: <math>D_{j} <= d_{jh}</math> (медоид <math>j</math>-го объекта не изменится), тогда справедливо равенство <math>T_{ijh} = 0</math> и <math>D_{j} > d_{jh}</math> (медоидом <math>j</math>-го объекта станет <math>h</math>-й объект), тогда справедливо равенство <math>T_{ijh} = d_{jh} - D_{j}</math>. Таким образом, в первом случае (<math>i</math>-й объект является медоидом <math>j</math>-го объекта) значение <math>T_{ijh}</math> может быть вычислено по формуле <math>T_{ijh} = min(E_{j}, d_{jh}) - D_{j}</math>, а во втором (<math>i</math>-й объект НЕ является медоидом <math>j</math>-го объекта) – по формуле <math>T_{ijh} = min(d_{jh} - D_{j}, 0)</math>. В формулах выше <math>min(x, y)</math> – это операция получения минимального из двух значений <math>x</math> и <math>y</math>.
	[[file:PAM_Tijh.png\|thumb\|center\|550px\|Вычисление значения <math>T_{ijh}</math>]]		[[file:PAM_Tijh.png\|thumb\|center\|550px\|Вычисление значения <math>T_{ijh}</math>]]

Zhum в 10:38, 14 ноября 2016

2016-11-14T10:38:20Z

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

	{{algorithm		{{algorithm

Антон Тодуа в 21:25, 13 ноября 2016

2016-11-13T21:25:36Z

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

	{{algorithm		{{algorithm
	\| name = Partitioning Around Medoids		\| name = Partitioning Around Medoids
Строка 8:		Строка 9:
	\| pf_width = <math>O(K * (N - K))</math>		\| pf_width = <math>O(K * (N - K))</math>
	}}		}}

	'''Авторы''':		'''Авторы''':
	* [[Участник:Антон Тодуа \| Тодуа А.Р.]] (оценки и реализация)		* [[Участник:Антон Тодуа \| Тодуа А.Р.]] (оценки и реализация)

Антон Тодуа в 21:25, 13 ноября 2016

2016-11-13T21:25:26Z

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

	{{algorithm		{{algorithm
	\| name = Partitioning Around Medoids		\| name = Partitioning Around Medoids
Строка 9:		Строка 8:
	\| pf_width = <math>O(K * (N - K))</math>		\| pf_width = <math>O(K * (N - K))</math>
	}}		}}

	'''Авторы''':		'''Авторы''':
	* [[Участник:Антон Тодуа \| Тодуа А.Р.]] (оценки и реализация)		* [[Участник:Антон Тодуа \| Тодуа А.Р.]] (оценки и реализация)

Антон Тодуа в 21:25, 13 ноября 2016

2016-11-13T21:25:16Z

← Предыдущая версия		Версия от 21:25, 13 ноября 2016
Строка 1:		Строка 1:
	{{~~assigment~~}}		{{Assignment}}

	{{algorithm		{{algorithm

Антон Тодуа в 21:24, 13 ноября 2016

2016-11-13T21:24:50Z

← Предыдущая версия		Версия от 21:24, 13 ноября 2016
Строка 1:		Строка 1:
			{{assigment}}

	{{algorithm		{{algorithm

Антон Тодуа в 21:23, 13 ноября 2016

2016-11-13T21:23:28Z

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


			{{algorithm
			\| name = Partitioning Around Medoids
			\| serial_complexity = <math>O(Q * K * N^2)</math>
			\| input_data = <math>\frac{N (N - 1)}{2}</math>
			\| output_data = <math>K</math> медоидов или <math>N</math> кластеров объектов
			\| pf_height = <math>O(Q * K * N)</math>
			\| pf_width = <math>O(K * (N - K))</math>
			}}

	'''Авторы''':		'''Авторы''':
	* [[Участник:Антон Тодуа \| Тодуа А.Р.]] (оценки и реализация)		* [[Участник:Антон Тодуа \| Тодуа А.Р.]] (оценки и реализация)

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

2016-11-13T21:18:28Z

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

← Предыдущая версия		Версия от 21:18, 13 ноября 2016
Строка 312:		Строка 312:
	* При увеличении числа процессов общая эффективность программы уменьшается, т.к. время чтения и подготовки исходных данных остаётся неизменным и начинает преобладать над временем работы алгоритма ''PAM''.		* При увеличении числа процессов общая эффективность программы уменьшается, т.к. время чтения и подготовки исходных данных остаётся неизменным и начинает преобладать над временем работы алгоритма ''PAM''.
	* При увеличении числа объектов кластеризации общая эффективность программы постепенно увеличивается, т.к. время чтения и подготовки исходных данных растёт медленнее, чем время работы алгоритма ''PAM''.		* При увеличении числа объектов кластеризации общая эффективность программы постепенно увеличивается, т.к. время чтения и подготовки исходных данных растёт медленнее, чем время работы алгоритма ''PAM''.
	* ~~Общая оценка масштабируемости: .~~ При одновременном увеличении как числа процессов, так и числа объектов кластеризации общая эффективность программы уменьшается.		* При одновременном увеличении как числа процессов, так и числа объектов кластеризации общая эффективность программы уменьшается.

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