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

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

2016-11-28T12:48:45Z

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

	{{algorithm		{{algorithm

Dexter в 19:28, 27 ноября 2016

2016-11-27T19:28:51Z

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

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

2016-11-23T12:04:38Z

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

	{{algorithm		{{algorithm

Denemmy: /* Свойства алгоритма */

2016-11-18T07:26:11Z

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

← Предыдущая версия		Версия от 07:26, 18 ноября 2016
Строка 215:		Строка 215:
	=== Свойства алгоритма ===		=== Свойства алгоритма ===
	<p><b>[[глоссарий#Вычислительная мощность\|''Вычислительная мощность'']]</b></p>		<p><b>[[глоссарий#Вычислительная мощность\|''Вычислительная мощность'']]</b></p>
	Суммарный объем входных данных равен <math> O(N^2) </math> , число операций алгоритма '''PAM''' равно <math> O(KN^2\Tau) </math>, где <math>K</math> – число кластеров, <math>\Tau</math> – число итераций алгоритма, <math> N </math> - число точек. Тогда вычислительная мощность алгоритма '''PAM''' равна <math>K*\Tau </math>.		Суммарный объем входных данных равен <math> O(N^2) </math> , число операций алгоритма '''PAM''' равно <math> O(KN^2\Tau) </math>, где <math>K</math> – число кластеров, <math>\Tau</math> – число итераций алгоритма, <math> N </math> - число точек. Тогда вычислительная мощность алгоритма '''PAM''' равна <math>O(K*\Tau)</math>.

	<p><b>[[глоссарий#Детерминированность \|''Детерминированность'']] и [[глоссарий#Устойчивость \|''Устойчивость'']] </b></p>		<p><b>[[глоссарий#Детерминированность \|''Детерминированность'']] и [[глоссарий#Устойчивость \|''Устойчивость'']] </b></p>

Denemmy в 07:25, 18 ноября 2016

2016-11-18T07:25:40Z

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

	{{algorithm		{{algorithm

Denemmy: /* Свойства алгоритма */

2016-11-18T07:24:09Z

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

← Предыдущая версия		Версия от 07:24, 18 ноября 2016
Строка 214:		Строка 214:
	=== Свойства алгоритма ===		=== Свойства алгоритма ===
	<p><b>[[глоссарий#Вычислительная мощность\|''Вычислительная мощность'']]</b></p>		<p><b>[[глоссарий#Вычислительная мощность\|''Вычислительная мощность'']]</b></p>
	~~Вычислительная мощность алгоритма~~ <i>~~k means~~</i> ~~равна~~ <math>~~\frac{~~KN^2\Tau~~}{N^2} = K*\Tau~~ </math>, где <math>K</math> – число кластеров, <math>\Tau</math> – число итераций алгоритма.		Суммарный объем входных данных равен <math> O(N^2) </math> , число операций алгоритма '''PAM''' равно <math> O(KN^2\Tau) </math>, где <math>K</math> – число кластеров, <math>\Tau</math> – число итераций алгоритма, <math> N </math> - число точек. Тогда вычислительная мощность алгоритма '''PAM''' равна <math>K*\Tau </math>.

	<p><b>[[глоссарий#Детерминированность \|''Детерминированность'']] и [[глоссарий#Устойчивость \|''Устойчивость'']] </b></p>		<p><b>[[глоссарий#Детерминированность \|''Детерминированность'']] и [[глоссарий#Устойчивость \|''Устойчивость'']] </b></p>

Denemmy: /* Макроструктура алгоритма */

2016-11-18T07:14:44Z

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

← Предыдущая версия		Версия от 07:14, 18 ноября 2016
Строка 131:		Строка 131:
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:		Если на вход алгоритма была подана не матрица расстояний, а матрица объектов с их координатами в пространстве <math>R^P</math>, то операция вычисления расстояния между объектами <math>a</math> и <math>b</math> размерности <math>P</math> будет являться макрооперацией. В качестве меры расстояния может быть использована евклидова метрика:
	<math> d(a,b) ~~= \sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\dots+(a_P-b_P)^2}~~ = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>		<math> d(a,b) = \sqrt{\sum_{i=1}^P (a_i-b_i)^2}</math>

	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===

Denemmy в 07:14, 18 ноября 2016

2016-11-18T07:14:13Z

← Предыдущая версия		Версия от 07:14, 18 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~
	{{algorithm		{{algorithm
	\| name = Partitioning Around Medoids		\| name = Partitioning Around Medoids

Denemmy в 11:38, 16 ноября 2016

2016-11-16T11:38:46Z

← Предыдущая версия		Версия от 11:38, 16 ноября 2016
Строка 1:		Строка 1:
			{{Assignment}}
	{{algorithm		{{algorithm
	\| name = Partitioning Around Medoids		\| name = Partitioning Around Medoids

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

2016-11-16T11:38:20Z

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

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

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

	Данные были сгенерированы в '''Matlab'е''' случайным образом. Количество кластеров равно '''16''', каждый кластер был промоделирован нормальным распределением с некоторыми случайными значениями среднего и среднеквадратического отклонения. Размерность данных равна '''2''', а число точек на каждый кластер было достаточно большим для проведения экспериментов с различными значениями размерности матрицы расстояний. Пример сгенерированных данных показан на рисунке 3.		Данные были сгенерированы в '''Matlab'е''' случайным образом. Количество кластеров равно '''16''', каждый кластер был промоделирован нормальным распределением с некоторыми случайными значениями среднего и среднеквадратического отклонения. Размерность данных равна '''2''', а число точек на каждый кластер было достаточно большим для проведения экспериментов с различными значениями размерности матрицы расстояний. Пример сгенерированных данных показан на рисунке 3.