Участник:IanaV/Алгоритм k means - История изменений

ASA в 14:16, 19 декабря 2016

2016-12-19T14:16:33Z

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

Konshin в 14:30, 9 декабря 2016

2016-12-09T14:30:28Z

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


	{{level-a}}		{{level-a}}

IanaV: /* Общее описание алгоритма */

2016-12-08T21:37:59Z

Общее описание алгоритма

← Предыдущая версия		Версия от 21:37, 8 декабря 2016
Строка 19:		Строка 19:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	<p>Алгоритм <i>k-means</i> (<i>k средних</i>) - один из наиболее популярных алгоритмов кластеризации. Наиболее простой, но в то же время достаточно неточный метод кластеризации в классической реализации.</p>		<p>Алгоритм <i>k-means</i> (<i>k средних</i>) - один из наиболее популярных алгоритмов кластеризации. Наиболее простой, но в то же время достаточно неточный метод кластеризации в классической реализации.</p>
	<p>Алгоритм был разработан в 1956 году математиком Гуго Штейнгаузом <ref>[http://www.laurent-duval.eu/Documents/Steinhaus_H_1956_j-bull-acad-polon-sci_division_cmp-k-means.pdf Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.]</ref>, и почти одновременно его изобрел Стюарт Ллойд <ref>[http://www-evasion.imag.fr/people/Franck.Hetroy/Teaching/ProjetsImage/2007/Bib/lloyd-1982.pdf Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper. ~~Опубликован~~ позже в IEEE Transactions on Information Theory 28 (1982): 129-137.]</ref>. Особую популярность алгоритм снискал после работы Джеймса Маккуина <ref>[https://pdfs.semanticscholar.org/a718/b85520bea702533ca9a5954c33576fd162b0.pdf MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.]</ref></p>		<p>Алгоритм был разработан в 1956 году математиком Гуго Штейнгаузом <ref>[http://www.laurent-duval.eu/Documents/Steinhaus_H_1956_j-bull-acad-polon-sci_division_cmp-k-means.pdf Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801—804.]</ref>, и почти одновременно его изобрел Стюарт Ллойд <ref>[http://www-evasion.imag.fr/people/Franck.Hetroy/Teaching/ProjetsImage/2007/Bib/lloyd-1982.pdf Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper. Опубликовано позже в IEEE Transactions on Information Theory 28 (1982): 129-137.]</ref>. Особую популярность алгоритм снискал после работы Джеймса Маккуина <ref>[https://pdfs.semanticscholar.org/a718/b85520bea702533ca9a5954c33576fd162b0.pdf MacQueen J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability, pages 281—297.]</ref></p>
	<p>Алгоритм кластеризации <i>k-means</i> решает задачу распределения <math>N</math> наблюдений (элементов векторного пространства) на заранее известное число кластеров <math>K</math>. Действие алгоритма таково, что он стремится минимизировать среднеквадратичное отклонение на точках каждого кластера.</p>		<p>Алгоритм кластеризации <i>k-means</i> решает задачу распределения <math>N</math> наблюдений (элементов векторного пространства) на заранее известное число кластеров <math>K</math>. Действие алгоритма таково, что он стремится минимизировать среднеквадратичное отклонение на точках каждого кластера.</p>
	<p>Алгоритм k-means является итерационным алгоритмом кластеризации. На каждой итерации происходит пересчет центра масс для каждого кластера, полученного на предыдущем шаге, затем исходные векторы заново распределяются по кластерам в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров.</p>		<p>Алгоритм k-means является итерационным алгоритмом кластеризации. На каждой итерации происходит пересчет центра масс для каждого кластера, полученного на предыдущем шаге, затем исходные векторы заново распределяются по кластерам в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров.</p>

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

2016-12-08T21:18:29Z

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

← Предыдущая версия		Версия от 21:18, 8 декабря 2016
Строка 223:		Строка 223:
	По рис. 5 можно отметить практически полное отсутствие роста производительности с увеличением числа процессов от 256 до 512 при минимальном размере задачи. Это связано с быстрым ростом накладных расходов по отношению к крайне низкому объёму вычислений. При росте размера задачи данный эффект пропадает, и при одновременном пропорциональном увеличении числа кластеров и числа процессов рост производительности становится близким к линейному.		По рис. 5 можно отметить практически полное отсутствие роста производительности с увеличением числа процессов от 256 до 512 при минимальном размере задачи. Это связано с быстрым ростом накладных расходов по отношению к крайне низкому объёму вычислений. При росте размера задачи данный эффект пропадает, и при одновременном пропорциональном увеличении числа кластеров и числа процессов рост производительности становится близким к линейному.
	[[file:kmeans_efficiency.jpg\|thumb\|center\|720px\|Рисунок 6. График зависимости эффективности параллельной реализации алгоритма от числа кластеров и числа процессов. ]]		[[file:kmeans_efficiency.jpg\|thumb\|center\|720px\|Рисунок 6. График зависимости эффективности параллельной реализации алгоритма от числа кластеров и числа процессов. ]]
	Исследовалась [https://github.com/like-a-bauss/kmeans параллельная реализация алгоритма k means].		Исследовалась [https://github.com/like-a-bauss/kmeans параллельная реализация алгоритма k means на MPI].
	<p>Были получены следующие оценки масштабируемости реализации алгоритма k means:</p>		<p>Были получены следующие оценки масштабируемости реализации алгоритма k means:</p>
	*<i>По числу процессов:</i> <math>-0.02209</math>. Следовательно, с ростом числа процессов эффективность уменьшается. На рис. 6 можно наблюдать плавное и равномерное снижение производительности по мере увеличения числа процессов при неизменном числе кластеров, что свидетельствует об относительно невысоком росте накладных расходов на передачу данных между процессами и преобладании объёма вычислений над объёмом пересылок данных по сети.		*<i>По числу процессов:</i> <math>-0.02209</math>. Следовательно, с ростом числа процессов эффективность уменьшается. На рис. 6 можно наблюдать плавное и равномерное снижение производительности по мере увеличения числа процессов при неизменном числе кластеров, что свидетельствует об относительно невысоком росте накладных расходов на передачу данных между процессами и преобладании объёма вычислений над объёмом пересылок данных по сети.

IanaV: /* Вычислительное ядро алгоритма */

2016-12-08T21:09:32Z

Вычислительное ядро алгоритма

← Предыдущая версия		Версия от 21:09, 8 декабря 2016
Строка 63:		Строка 63:
	# пересчет центров масс кластеров.		# пересчет центров масс кластеров.

	<i>Распределение векторов по кластерам</i> заключается в следующем: для каждого вектора <math>x_i \in X, i = 1, ..., n</math> необходимо посчитать расстояние между этим вектором и центром масс кластера <math>\mu_j^t, j = 1, ..., k</math>. Следовательно, на каждой итерации необходимо выполнить <math>~~n * k~~</math> операций вычисления расстояния между векторами.		<i>Распределение векторов по кластерам</i> заключается в следующем: для каждого вектора <math>x_i \in X, i = 1, ..., n</math> необходимо посчитать расстояние между этим вектором и центром масс кластера <math>\mu_j^t, j = 1, ..., k</math>. Следовательно, на каждой итерации необходимо выполнить <math>nk</math> операций вычисления расстояния между векторами.

	<i>Пересчет центров масс кластеров</i> заключается в следующем: для каждого кластера <math>S_i^t \in S, i = 1, ..., k</math> необходимо пересчитать кластер по формуле, приведенной в пункте выше. Следовательно, на каждой итерации необходимо выполнить <math>k</math> операций пересчета центров масс кластеров.		<i>Пересчет центров масс кластеров</i> заключается в следующем: для каждого кластера <math>S_i^t \in S, i = 1, ..., k</math> необходимо пересчитать кластер по формуле, приведенной в пункте выше. Следовательно, на каждой итерации необходимо выполнить <math>k</math> операций пересчета центров масс кластеров.

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

2016-12-08T21:06:21Z

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

← Предыдущая версия		Версия от 21:06, 8 декабря 2016
Строка 226:		Строка 226:
	<p>Были получены следующие оценки масштабируемости реализации алгоритма k means:</p>		<p>Были получены следующие оценки масштабируемости реализации алгоритма k means:</p>
	*<i>По числу процессов:</i> <math>-0.02209</math>. Следовательно, с ростом числа процессов эффективность уменьшается. На рис. 6 можно наблюдать плавное и равномерное снижение производительности по мере увеличения числа процессов при неизменном числе кластеров, что свидетельствует об относительно невысоком росте накладных расходов на передачу данных между процессами и преобладании объёма вычислений над объёмом пересылок данных по сети.		*<i>По числу процессов:</i> <math>-0.02209</math>. Следовательно, с ростом числа процессов эффективность уменьшается. На рис. 6 можно наблюдать плавное и равномерное снижение производительности по мере увеличения числа процессов при неизменном числе кластеров, что свидетельствует об относительно невысоком росте накладных расходов на передачу данных между процессами и преобладании объёма вычислений над объёмом пересылок данных по сети.
	<i>По размеру задачи:</i> <math>0.01252</math>. Следовательно, с ростом размера задачи (числа кластеров) эффективность увеличивается. При этом объём пересылок данных по сети пропорционален <math>(n + k) p</math> (где <math>k</math> - число кластеров, <math>n</math> - число входных векторов, <math>p</math> - число процессов) таким образом, поскольку <math>k << n</math>, рост накладных расходов с ростом числа кластеров при неизменном числе процессов и входных векторов представляет собой незначительную величину.		*<i>По размеру задачи:</i> <math>0.01252</math>. Следовательно, с ростом размера задачи (числа кластеров) эффективность увеличивается. При этом объём пересылок данных по сети пропорционален <math>(n + k) \cdot p</math> (где <math>k</math> - число кластеров, <math>n</math> - число входных векторов, <math>p</math> - число процессов) таким образом, поскольку <math>k << n</math>, рост накладных расходов с ростом числа кластеров при неизменном числе процессов и входных векторов представляет собой незначительную величину.
	<i>Общая оценка:</i> <math>-0.00081</math>. Таким образом, с ростом и размера задачи, и числа процессов эффективность уменьшается. Это связано с тем, что отношение объёма вычислений к объёму передаваемых данных изменяется пропорционально <math>{~~n k~~ \over (n + k) * p} \thicksim {k \over p}</math>, что ~~преставляет~~ собой невысокий коэффициент, но при этом позволяет параллельной реализации не деградировать до нулевой эффективности при значительном увеличении числа процессов.		*<i>Общая оценка:</i> <math>-0.00081</math>. Таким образом, с ростом и размера задачи, и числа процессов эффективность уменьшается. Это связано с тем, что отношение объёма вычислений к объёму передаваемых данных изменяется пропорционально <math>{kn \over (n + k) \cdot p} \thicksim {k \over p}</math>, что представляет собой невысокий коэффициент, но при этом позволяет параллельной реализации не деградировать до нулевой эффективности при значительном увеличении числа процессов.

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

IanaV в 21:05, 8 декабря 2016

2016-12-08T21:05:08Z

← Предыдущая версия		Версия от 21:05, 8 декабря 2016
Строка 6:		Строка 6:
	\| name = Алгоритм k средних (k means)		\| name = Алгоритм k средних (k means)
	\| serial_complexity = <math>O(iknd)</math>		\| serial_complexity = <math>O(iknd)</math>
	\| input_data = <math> dn </math>		\| input_data = <math> nd </math>
	\| output_data = <math> n </math>		\| output_data = <math> n </math>
	}}		}}

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

2016-12-08T21:04:50Z

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

← Предыдущая версия		Версия от 21:04, 8 декабря 2016
Строка 192:		Строка 192:
	;[[глоссарий#Устойчивость\|''Устойчивость'']]: Алгоритм является устойчивым к погрешностям во входных данных, так как при вычислении центров кластеров расстояния между объектами усредняются, что приводит к уменьшению ошибки. Алгоритм также является устойчивым к погрешностям, допускаемых при вычислениях, так как операция сложения на каждой новой итерации выполняется над входными данными.		;[[глоссарий#Устойчивость\|''Устойчивость'']]: Алгоритм является устойчивым к погрешностям во входных данных, так как при вычислении центров кластеров расстояния между объектами усредняются, что приводит к уменьшению ошибки. Алгоритм также является устойчивым к погрешностям, допускаемых при вычислениях, так как операция сложения на каждой новой итерации выполняется над входными данными.

	;Сбалансированность: <p>Множество входных векторов можно равномерно разделить между параллельными вычислителями. Центры всех кластеров можно распространить на все вычислители (так как их заведомо меньше, чем число входных векторов). В таком случае на каждой итерации определение для каждого объекта ближайшего кластера представляет собой вычисление расстояния от каждого входного вектора, находящегося на вычислителе, до каждого кластера, и является сбалансированной операцией. После данного этапа происходит пересчёт центров кластеров. Данная операция является несбалансированной в случаях, когда число объектов в одном из кластеров значительно больше числа объектов в других кластерах, из-за чего один кластер занимает большое число вычислителей, а остальные занимают по одному или несколько вычислителей. В таком случае для данного кластера потребуется вычислить центр [[Нахождение_частных_сумм_элементов_массива_сдваиванием \| алгоритмом нахождения частичной суммы элементов массива путем сдваивания]]. Данная операция представляет несбалансированность порядка <math>O(\log (~~k*n~~))</math>. После данного шага происходит сбалансированная операция рассылки центров кластеров на все вычислители.</p><p>В идеальном случае параллелизации алгоритм не является сбалансированным, однако в реальных задачах, когда <math>n >> p</math>, где <math>p</math> - количество вычислителей, эта несбалансированность сглаживается наличием объектов из каждого кластера на каждом вычислителе</p>		;Сбалансированность: <p>Множество входных векторов можно равномерно разделить между параллельными вычислителями. Центры всех кластеров можно распространить на все вычислители (так как их заведомо меньше, чем число входных векторов). В таком случае на каждой итерации определение для каждого объекта ближайшего кластера представляет собой вычисление расстояния от каждого входного вектора, находящегося на вычислителе, до каждого кластера, и является сбалансированной операцией. После данного этапа происходит пересчёт центров кластеров. Данная операция является несбалансированной в случаях, когда число объектов в одном из кластеров значительно больше числа объектов в других кластерах, из-за чего один кластер занимает большое число вычислителей, а остальные занимают по одному или несколько вычислителей. В таком случае для данного кластера потребуется вычислить центр [[Нахождение_частных_сумм_элементов_массива_сдваиванием \| алгоритмом нахождения частичной суммы элементов массива путем сдваивания]]. Данная операция представляет несбалансированность порядка <math>O(\log (kn))</math>. После данного шага происходит сбалансированная операция рассылки центров кластеров на все вычислители.</p><p>В идеальном случае параллелизации алгоритм не является сбалансированным, однако в реальных задачах, когда <math>n >> p</math>, где <math>p</math> - количество вычислителей, эта несбалансированность сглаживается наличием объектов из каждого кластера на каждом вычислителе</p>

	;Соотношение последовательной и параллельной сложности: <math>{O(~~ndki~~) \over O(\log(~~ndk~~)i)} \thicksim O \bigg( {~~ndk~~ \over \log(~~ndk~~)} \bigg)</math>		;Соотношение последовательной и параллельной сложности: <math>{O(iknd) \over O(i \cdot \log(knd))} \thicksim O \bigg( {knd \over \log(knd)} \bigg)</math>

	;[[глоссарий#Вычислительная мощность\|''Вычислительная мощность'']]: <p>Последовательный алгоритм: <math>{O(~~ndki~~) \over ~~nd~~+n+1} \thicksim {O(~~dki~~) \over d+1} \thicksim O(~~ki~~)</math>, где <math>n</math> - число входных векторов, <math>d</math> - размерность векторов, <math>k</math> - число кластеров, <math>i</math> - число итераций, требуемое для сходимости</p><p>Параллельный алгоритм: <math>O(\log(~~ndk~~)i) \over ~~n*d~~+n+1</math></p>		;[[глоссарий#Вычислительная мощность\|''Вычислительная мощность'']]: <p>Последовательный алгоритм: <math>{O(iknd) \over nd+n+1} \thicksim {O(ikd) \over d+1} \thicksim O(ik)</math>, где <math>n</math> - число входных векторов, <math>d</math> - размерность векторов, <math>k</math> - число кластеров, <math>i</math> - число итераций, требуемое для сходимости</p><p>Параллельный алгоритм: <math>O(i \cdot \log(knd)) \over nd+n+1</math></p>

	;[[глоссарий#Детерминированность\|''Детерминированность'']]: Алгоритм является недетерминированным, так как результат зависит от выбора исходных центров кластеров, а их оптимальный выбор неизвестен.		;[[глоссарий#Детерминированность\|''Детерминированность'']]: Алгоритм является недетерминированным, так как результат зависит от выбора исходных центров кластеров, а их оптимальный выбор неизвестен.

IanaV: /* Входные и выходные данные алгоритма */

2016-12-08T21:01:48Z

Входные и выходные данные алгоритма

← Предыдущая версия		Версия от 21:01, 8 декабря 2016
Строка 170:		Строка 170:

	<i>Объем входных данных</i>:		<i>Объем входных данных</i>:
	<math>~~n * d~~</math> действительных чисел, 1 целое положительное число		<math>nd</math> действительных чисел, 1 целое положительное число

	<i>Выходные данные</i>:		<i>Выходные данные</i>:

IanaV: /* Информационный граф */

2016-12-08T21:01:18Z

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

← Предыдущая версия		Версия от 21:01, 8 декабря 2016
Строка 126:		Строка 126:
	Рассмотрим информационный граф алгоритма k-means.		Рассмотрим информационный граф алгоритма k-means.
	На <i>рисунке 1</i> представлена общая схема алгоритма k-means, согласно разделу [[#Схема реализации последовательного алгоритма\|"Схема реализации последовательного алгоритма"]].		На <i>рисунке 1</i> представлена общая схема алгоритма k-means, согласно разделу [[#Схема реализации последовательного алгоритма\|"Схема реализации последовательного алгоритма"]].
	Вершина <i>Init</i> - этап инициализации.		Вершина <math>\rm Init</math> - этап инициализации.
	Вершина <i>Distribute</i> - этап распределения векторов по кластерам.		Вершина <math>\rm Distribute</math> - этап распределения векторов по кластерам.
	Вершина <i>Update</i> - этап пересчета центров масс кластеров.		Вершина <math>\rm Update</math> - этап пересчета центров масс кластеров.
	[[file:k-means-all.PNG\|800px\|thumb\|center\|Рисунок 1. Общая схема алгоритма k-means]]		[[file:k-means-all.PNG\|800px\|thumb\|center\|Рисунок 1. Общая схема алгоритма k-means]]


	На <i>рисунке 2</i> представлен информационный граф этапа распределения векторов по кластерам. На вход данному этапу подают множество векторов <math>x_1, x_2, ..., x_n</math> из входных данных и множество центров масс кластеров <math>\mu^t_1, ..., \mu^t_k</math>, полученных с шага инициализации или с предыдущей итерации. Для каждой пары векторов <math>x_i, \mu^t_j, i = 1, ..., n; j = 1,..., k</math> считается расстояние между ними (вершина <i>dist</i>). Информационный граф вычисления расстояния между двумя векторами рассмотрен ниже (<i>рисунок 3</i>). Затем выполняется операция нахождения минимума (вершина <i>min</i>), в результате которой каждому вектору <math>x_i, i = 1, ..., n</math> приписывается метка <math>l^t_i</math>, равная порядковому номеру кластера <math>S^t_j, j = 1 ..., k</math>, которому принадлежит данный вектор: <math>x_i \in S^t_j</math>.		На <i>рисунке 2</i> представлен информационный граф этапа распределения векторов по кластерам. На вход данному этапу подают множество векторов <math>x_1, x_2, ..., x_n</math> из входных данных и множество центров масс кластеров <math>\mu^t_1, ..., \mu^t_k</math>, полученных с шага инициализации или с предыдущей итерации. Для каждой пары векторов <math>x_i, \mu^t_j, i = 1, ..., n; j = 1,..., k</math> считается расстояние между ними (вершина <math>\rm dist</math>). Информационный граф вычисления расстояния между двумя векторами рассмотрен ниже (<i>рисунок 3</i>). Затем выполняется операция нахождения минимума (вершина <math>\rm min</math>), в результате которой каждому вектору <math>x_i, i = 1, ..., n</math> приписывается метка <math>l^t_i</math>, равная порядковому номеру кластера <math>S^t_j, j = 1 ..., k</math>, которому принадлежит данный вектор: <math>x_i \in S^t_j</math>.
	[[file:k-means-distribute.PNG\|800px\|thumb\|center\|Рисунок 2. Схема этапа распределения векторов по кластерам]]		[[file:k-means-distribute.PNG\|800px\|thumb\|center\|Рисунок 2. Схема этапа распределения векторов по кластерам]]


	На <i>рисунке 3</i> представлен информационный граф вычисления расстояния между двумя векторами <math>x_i = (x_{i1}, ..., x_{id}), i = 1, ..., n</math> и <math>\mu^t_j = (\mu^t_{j1}, ..., \mu^t_{jd}) , j = 1, ..., k</math>. Выполняется операция поэлементного вычитания двух векторов (вершины <i>-</i>), затем возведение в квадрат (вершины <i>sqr</i>), затем суммирование полученных результатов (вершина <i>+</i>). На выходе получаем квадрат расстояния между векторами.		На <i>рисунке 3</i> представлен информационный граф вычисления расстояния между двумя векторами <math>x_i = (x_{i1}, ..., x_{id}), i = 1, ..., n</math> и <math>\mu^t_j = (\mu^t_{j1}, ..., \mu^t_{jd}) , j = 1, ..., k</math>. Выполняется операция поэлементного вычитания двух векторов (вершины <math>-</math>), затем возведение в квадрат (вершины <math>\rm sqr</math>), затем суммирование полученных результатов (вершина <math>+</math>). На выходе получаем квадрат расстояния между векторами.
	[[file:K-means-distance.PNG\|800px\|thumb\|center\|Рисунок 3. Схема вычисления расстояния между двумя векторами]]		[[file:K-means-distance.PNG\|800px\|thumb\|center\|Рисунок 3. Схема вычисления расстояния между двумя векторами]]


	На <i>рисунке 4</i> представлен информационный граф этапа пересчета центров масс кластеров <math>\mu^t_1, \mu^t_2,..., \mu^t_k</math>. Для каждого кластера <math>S^t_j, j = 1, ..., k</math> выполняется операция суммирования (вершина <math>sum_j</math>) векторов, которые принадлежат данному кластеру. Кроме того, для каждого кластера выполняется операция определения количества элементов в нем (вершина <math>size_j</math>). Затем выполняется операция деления (вершина <i>/</i>). На выходе получаем новые центры масс кластеров <math>\mu^{t+1}_1, \mu^{t+1}_2,..., \mu^{t+1}_k</math>.		На <i>рисунке 4</i> представлен информационный граф этапа пересчета центров масс кластеров <math>\mu^t_1, \mu^t_2,..., \mu^t_k</math>. Для каждого кластера <math>S^t_j, j = 1, ..., k</math> выполняется операция суммирования (вершина <math>\rm sum_j</math>) векторов, которые принадлежат данному кластеру. Кроме того, для каждого кластера выполняется операция определения количества элементов в нем (вершина <math>\rm size_j</math>). Затем выполняется операция деления (вершина <math>/</math>). На выходе получаем новые центры масс кластеров <math>\mu^{t+1}_1, \mu^{t+1}_2,..., \mu^{t+1}_k</math>.
	[[file:k-means-update.PNG\|800px\|thumb\|center\|Рисунок 4. Схема этапа пересчета центров масс кластеров]]		[[file:k-means-update.PNG\|800px\|thumb\|center\|Рисунок 4. Схема этапа пересчета центров масс кластеров]]

← Предыдущая версия		Версия от 21:04, 8 декабря 2016
Строка 192:		Строка 192:
	;[[глоссарий#Устойчивость\|''Устойчивость'']]: Алгоритм является устойчивым к погрешностям во входных данных, так как при вычислении центров кластеров расстояния между объектами усредняются, что приводит к уменьшению ошибки. Алгоритм также является устойчивым к погрешностям, допускаемых при вычислениях, так как операция сложения на каждой новой итерации выполняется над входными данными.		;[[глоссарий#Устойчивость\|''Устойчивость'']]: Алгоритм является устойчивым к погрешностям во входных данных, так как при вычислении центров кластеров расстояния между объектами усредняются, что приводит к уменьшению ошибки. Алгоритм также является устойчивым к погрешностям, допускаемых при вычислениях, так как операция сложения на каждой новой итерации выполняется над входными данными.

	;Сбалансированность: <p>Множество входных векторов можно равномерно разделить между параллельными вычислителями. Центры всех кластеров можно распространить на все вычислители (так как их заведомо меньше, чем число входных векторов). В таком случае на каждой итерации определение для каждого объекта ближайшего кластера представляет собой вычисление расстояния от каждого входного вектора, находящегося на вычислителе, до каждого кластера, и является сбалансированной операцией. После данного этапа происходит пересчёт центров кластеров. Данная операция является несбалансированной в случаях, когда число объектов в одном из кластеров значительно больше числа объектов в других кластерах, из-за чего один кластер занимает большое число вычислителей, а остальные занимают по одному или несколько вычислителей. В таком случае для данного кластера потребуется вычислить центр [[Нахождение_частных_сумм_элементов_массива_сдваиванием \| алгоритмом нахождения частичной суммы элементов массива путем сдваивания]]. Данная операция представляет несбалансированность порядка <math>O(\log (~~k*n~~))</math>. После данного шага происходит сбалансированная операция рассылки центров кластеров на все вычислители.</p><p>В идеальном случае параллелизации алгоритм не является сбалансированным, однако в реальных задачах, когда <math>n >> p</math>, где <math>p</math> - количество вычислителей, эта несбалансированность сглаживается наличием объектов из каждого кластера на каждом вычислителе</p>		;Сбалансированность: <p>Множество входных векторов можно равномерно разделить между параллельными вычислителями. Центры всех кластеров можно распространить на все вычислители (так как их заведомо меньше, чем число входных векторов). В таком случае на каждой итерации определение для каждого объекта ближайшего кластера представляет собой вычисление расстояния от каждого входного вектора, находящегося на вычислителе, до каждого кластера, и является сбалансированной операцией. После данного этапа происходит пересчёт центров кластеров. Данная операция является несбалансированной в случаях, когда число объектов в одном из кластеров значительно больше числа объектов в других кластерах, из-за чего один кластер занимает большое число вычислителей, а остальные занимают по одному или несколько вычислителей. В таком случае для данного кластера потребуется вычислить центр [[Нахождение_частных_сумм_элементов_массива_сдваиванием \| алгоритмом нахождения частичной суммы элементов массива путем сдваивания]]. Данная операция представляет несбалансированность порядка <math>O(\log (kn))</math>. После данного шага происходит сбалансированная операция рассылки центров кластеров на все вычислители.</p><p>В идеальном случае параллелизации алгоритм не является сбалансированным, однако в реальных задачах, когда <math>n >> p</math>, где <math>p</math> - количество вычислителей, эта несбалансированность сглаживается наличием объектов из каждого кластера на каждом вычислителе</p>

	;Соотношение последовательной и параллельной сложности: <math>{O(~~ndki~~) \over O(\log(~~ndk~~)i)} \thicksim O \bigg( {~~ndk~~ \over \log(~~ndk~~)} \bigg)</math>		;Соотношение последовательной и параллельной сложности: <math>{O(iknd) \over O(i \cdot \log(knd))} \thicksim O \bigg( {knd \over \log(knd)} \bigg)</math>

	;[[глоссарий#Вычислительная мощность\|''Вычислительная мощность'']]: <p>Последовательный алгоритм: <math>{O(~~ndki~~) \over ~~nd~~+n+1} \thicksim {O(~~dki~~) \over d+1} \thicksim O(~~ki~~)</math>, где <math>n</math> - число входных векторов, <math>d</math> - размерность векторов, <math>k</math> - число кластеров, <math>i</math> - число итераций, требуемое для сходимости</p><p>Параллельный алгоритм: <math>O(\log(~~ndk~~)i) \over ~~n*d~~+n+1</math></p>		;[[глоссарий#Вычислительная мощность\|''Вычислительная мощность'']]: <p>Последовательный алгоритм: <math>{O(iknd) \over nd+n+1} \thicksim {O(ikd) \over d+1} \thicksim O(ik)</math>, где <math>n</math> - число входных векторов, <math>d</math> - размерность векторов, <math>k</math> - число кластеров, <math>i</math> - число итераций, требуемое для сходимости</p><p>Параллельный алгоритм: <math>O(i \cdot \log(knd)) \over nd+n+1</math></p>

	;[[глоссарий#Детерминированность\|''Детерминированность'']]: Алгоритм является недетерминированным, так как результат зависит от выбора исходных центров кластеров, а их оптимальный выбор неизвестен.		;[[глоссарий#Детерминированность\|''Детерминированность'']]: Алгоритм является недетерминированным, так как результат зависит от выбора исходных центров кластеров, а их оптимальный выбор неизвестен.