Участник:Илья Егоров/Алгоритм k-средних - История изменений

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

2016-12-19T14:19:42Z

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

Илья Егоров в 19:15, 13 декабря 2016

2016-12-13T19:15:28Z

← Предыдущая версия		Версия от 19:15, 13 декабря 2016
Строка 26:		Строка 26:
	== Математическое описание алгоритма ==		== Математическое описание алгоритма ==
	'''Исходные данные:'''		'''Исходные данные:'''
	* Совокупность <b>n</b> <b>d</b>-мерных векторов <math> X = \{x_1 \dots x_n\} , </math> где <math> x_i = \{x_{i1} \dots x_{id}\} </math>		* Совокупность <math>n</math> <math>d</math>-мерных векторов <math> X = \{x_1 \dots x_n\} , </math> где <math> x_i = \{x_{i1} \dots x_{id}\} </math>
	* Предполагаемое количество кластеров <b>k</b>		* Предполагаемое количество кластеров <math>k</math>

	'''Выходные данные:'''		'''Выходные данные:'''
Строка 37:		Строка 37:
	'''Алгоритм:'''		'''Алгоритм:'''

	1) <math> \mu_{i} = random </math>		1) <math> \mu_{i} = {\rm random} </math>

	2) <math> S_i = \{x \in S~\|~\underset{j}{\rm argmin } \|\|x-\mu_j\|\|_E = i\} i = 1 \dots k </math>		2) <math> S_i = \{x \in S~\|~\underset{j}{\rm argmin } \|\|x-\mu_j\|\|_E = i\} i = 1 \dots k </math>
Строка 47:		Строка 47:
	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==

	Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <math>X</math> и <math>\Mu</math>. Для ~~'''~~d~~'''~~-мерного вектора <math>a:</math>		Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между <math>X</math> и <math>\Mu</math>. Для <math>d</math>-мерного вектора <math>a:</math>

	<math>\|\|a\|\|=\sqrt{\sum_{i=1\dots d} a_i^2}</math>, поэтому заполнение одной ячейки такой матрицы потребует <math>d</math> операций умножения, <math>d-1</math> операций сложения и одну операция вычисления квадратного корня. Но так как эти расстояния используются только для сравнения, а ''sqrt'' является монотонно возрастающей функцией, то ее можно не вычислять. Поэтому нахождения матрицы расстояний потребует всего <math>n\times k\times d</math> операций умножений и <math>n\times k\times (d-1)</math> операций сложений.		<math>\|\|a\|\|=\sqrt{\sum_{i=1\dots d} a_i^2}</math>, поэтому заполнение одной ячейки такой матрицы потребует <math>d</math> операций умножения, <math>d-1</math> операций сложения и одну операция вычисления квадратного корня. Но так как эти расстояния используются только для сравнения, а ''sqrt'' является монотонно возрастающей функцией, то ее можно не вычислять. Поэтому нахождения матрицы расстояний потребует всего <math>n\times k\times d</math> операций умножений и <math>n\times k\times (d-1)</math> операций сложений.
Строка 54:		Строка 54:

	В алгоритме можно выделить следующие макрооперации:		В алгоритме можно выделить следующие макрооперации:
	*~~'''~~Вычисление расстояния между векторами~~'''~~,		*Вычисление расстояния между векторами,
	*~~'''~~Суммирование векторов~~'''~~,		*Суммирование векторов,
	*~~'''~~Поиск минимума в векторе~~'''~~,		*Поиск минимума в векторе,
	*~~'''~~Сравнение векторов~~'''~~,		*Сравнение векторов,
	*~~'''~~Деление вектора на скаляр~~'''~~.		*Деление вектора на скаляр.

	'''1)''' На шаге инициализации центроидов в общем случае (случайный выбор элементов) макроопераций не производится. Но так как правило определения количества кластеров ~~'''~~k~~'''~~ неоднозначно, то для некоторых вариантов макрооперации могут понадобиться. К примеру, существует класс стратегий поиска ~~'''~~k~~'''~~, которые базируются на определении центра масс всех объектов, и для которых будут дополнительно выполняться макрооперации ~~'''~~"Суммирование векторов"~~'''~~ и ~~'''~~"Деление вектора на скаляр"~~'''~~.		'''1)''' На шаге инициализации центроидов в общем случае (случайный выбор элементов) макроопераций не производится. Но так как правило определения количества кластеров <math>k</math> неоднозначно, то для некоторых вариантов макрооперации могут понадобиться. К примеру, существует класс стратегий поиска <math>k</math>, которые базируются на определении центра масс всех объектов, и для которых будут дополнительно выполняться макрооперации "Суммирование векторов" и "Деление вектора на скаляр".

	'''2a)''' При составлении матрицы расстояний ~~''' k~~ <math> \~~cdot~~ </math> ~~n'''~~ раз производится макрооперация ~~'''~~"Вычисление расстояния между векторами"~~'''~~.		'''2a)''' При составлении матрицы расстояний <math>k \times n </math> раз производится макрооперация "Вычисление расстояния между векторами".

	'''2b)''' При нахождение вектора распределения объектов по кластерам ~~'''~~n~~'''~~ раз производится макрооперация ~~'''~~"Поиск минимума в векторе"~~'''~~.		'''2b)''' При нахождение вектора распределения объектов по кластерам <math>n</math> раз производится макрооперация "Поиск минимума в векторе".

	'''3)''' При пересчете центроидов ~~'''~~n - k~~'''~~ раз производится макрооперация ~~'''~~"Суммирование векторов"~~'''~~ и ~~'''~~k~~'''~~ раз — ~~'''~~"Деление вектора на скаляр"~~'''~~.		'''3)''' При пересчете центроидов <math>n - k</math> раз производится макрооперация "Суммирование векторов" и <math>k</math> раз — "Деление вектора на скаляр".

	'''4)''' Для проверки критерия останова требуется ~~'''~~k~~'''~~ раз произвести макрооперацию ~~'''~~"Сравнение векторов"~~'''~~ для сопоставления обновленных значений центроидов с уже имеющимися.		'''4)''' Для проверки критерия останова требуется <math>k</math> раз произвести макрооперацию "Сравнение векторов" для сопоставления обновленных значений центроидов с уже имеющимися.

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

	'''Входные данные''': Количество кластеров <b>k</b>, <b>n</b> кластеризуемых элементов		'''Входные данные''': Количество кластеров <math>k</math>, <math>n</math> кластеризуемых элементов

	Дополнительные ограничения:		Дополнительные ограничения:
	* <b>k</b> — положительное число, т. е. <b>k > 0</b>.		* <math>k</math> — положительное число, т. е. <math>k > 0</math>.
	* Для кластеризуемых элементов определена метрика (расстояние между объектами)		* Для кластеризуемых элементов определена метрика (расстояние между объектами)

	'''Объём входных данных''': <b>n ~~<math>~~\~~cdot</math>~~ d + 1</b> (кластеризуемые объекты в виде векторов и число <b>k</b>)		'''Объём входных данных''': <math>n \times d + 1</math> (кластеризуемые объекты в виде векторов и число <math>k</math>)

	'''Выходные данные''': Массив, в который записаны принадлежности каждого элемента кластеру (допустим вывод в другой эквивалентной более удобной структуре).		'''Выходные данные''': Массив, в который записаны принадлежности каждого элемента кластеру (допустим вывод в другой эквивалентной более удобной структуре).

	'''Объём выходных данных''': Размер массива равен <b>2 ~~<math>~~\~~cdot~~</math~~> n</b~~>.		'''Объём выходных данных''': Размер массива равен <math>2 \times n</math>.

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

Konshin в 18:35, 13 декабря 2016

2016-12-13T18:35:24Z

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

	{{algorithm		{{algorithm

Илья Егоров в 17:10, 13 декабря 2016

2016-12-13T17:10:34Z

← Предыдущая версия		Версия от 17:10, 13 декабря 2016
Строка 216:		Строка 216:
	В результате проведённых экспериментов были получены следующие данные:		В результате проведённых экспериментов были получены следующие данные:

	* Максимальная эффективность в точке достигается при переходе от 1 потока на 2 при минимальном размере данных, она равна <math>87,5%</math>.		* Максимальная эффективность в точке достигается при переходе от 1 потока на 4 при минимальном размере данных, она равна <math>87,5%</math>.
	* Усредненная максимальная эффективность достигается при переходе с одного потока на два. Среднее время вычислений на всех рассмотренных потока снижается с 16,33 до 11.87 секунд, поэтому формально эффективность <math>= 16.33 / 11.87 / 2 \approx 68,4\%</math>		* Усредненная максимальная эффективность достигается при переходе с одного потока на два. Среднее время вычислений на всех рассмотренных потока снижается с 16,33 до 11.87 секунд, поэтому формально эффективность <math>= 16.33 / 11.87 / 2 \approx 68,4\%</math>
	* Минимальная эффективность в точке достигается при переходе от 1 потока на 16 при размере данных 800000, она равна <math>11,1\%</math>.		* Минимальная эффективность в точке достигается при переходе от 1 потока на 16 при размере данных 800000, она равна <math>11,1\%</math>.

Илья Егоров в 17:09, 13 декабря 2016

2016-12-13T17:09:54Z

← Предыдущая версия		Версия от 17:09, 13 декабря 2016
Строка 216:		Строка 216:
	В результате проведённых экспериментов были получены следующие данные:		В результате проведённых экспериментов были получены следующие данные:

	* Максимальная эффективность в точке достигается при переходе от 1 потока на 8 при минимальном размере данных, она равна <math>87,5%</math>.		* Максимальная эффективность в точке достигается при переходе от 1 потока на 2 при минимальном размере данных, она равна <math>87,5%</math>.
	* Усредненная максимальная эффективность достигается при переходе с одного потока на два. Среднее время вычислений на всех рассмотренных потока снижается с 16,33 до 11.87 секунд, поэтому формально эффективность <math>= 16.33 / 11.87 / 2 \approx 68,4\%</math>		* Усредненная максимальная эффективность достигается при переходе с одного потока на два. Среднее время вычислений на всех рассмотренных потока снижается с 16,33 до 11.87 секунд, поэтому формально эффективность <math>= 16.33 / 11.87 / 2 \approx 68,4\%</math>
	* Минимальная эффективность в точке достигается при переходе от 1 потока на 16 при размере данных 800000, она равна <math>11,1\%</math>.		* Минимальная эффективность в точке достигается при переходе от 1 потока на 16 при размере данных 800000, она равна <math>11,1\%</math>.

Илья Егоров в 17:08, 13 декабря 2016

2016-12-13T17:08:09Z

Илья Егоров в 17:06, 13 декабря 2016

2016-12-13T17:06:29Z

← Предыдущая версия		Версия от 17:06, 13 декабря 2016
Строка 205:		Строка 205:
	== Масштабируемость реализации алгоритма ==		== Масштабируемость реализации алгоритма ==

	Проведём исследование масштабируемости параллельной реализации алгоритма k-средних. Исследование проводилось на суперкомпьютере "Ломоносов" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Параллельная реализация была написана самостоятельно на языке C, [http://git.algowiki-project.org/iaegorov/Egorov-Bogomazov-k-means/tree/master ссылка на реализацию]. Так как на каждой итерации число действий на единицу данных не велико и данные должны быть собраны вместе при перерасчете центроидов, было решено для ускорения вычислений ~~'''~~воспользоваться только OpenMP без MPI~~'''~~.		Проведём исследование масштабируемости параллельной реализации алгоритма k-средних. Исследование проводилось на суперкомпьютере "Ломоносов" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Параллельная реализация была написана самостоятельно на языке C, [http://git.algowiki-project.org/iaegorov/Egorov-Bogomazov-k-means/tree/master ссылка на реализацию]. Так как на каждой итерации число действий на единицу данных не велико и данные должны быть собраны вместе при перерасчете центроидов, было решено для ускорения вычислений воспользоваться только OpenMP без MPI.

			Код собирался под gcc c опцией -fopenmp. В очереди задача не стояла, так как код считался на одном процессоре, hyperthreading не использовался.

	Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:		Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:

Илья Егоров в 17:05, 13 декабря 2016

2016-12-13T17:05:05Z

← Предыдущая версия		Версия от 17:05, 13 декабря 2016
Строка 74:		Строка 74:
	Последовательность шагов алгоритма следующая:		Последовательность шагов алгоритма следующая:

	'''1) Инициализация центроидов <math>\Mu</math>, <math> iter = 1 </math>, задание максимального количество итераций <math>maxiter</math>'''		'''1) Инициализация центроидов <math>\Mu</math>, <math> {\rm iter} = 1 </math>, задание максимального количество итераций <math>{\rm maxiter}</math>'''

	'''2a) Нахождение матрицы расстояний '''<math>{\rm dist}:</math>		'''2a) Нахождение матрицы расстояний '''<math>{\rm dist}:</math>
Строка 90:		Строка 90:
	'''4) Проверка критерия останова:'''		'''4) Проверка критерия останова:'''

	'''Если''' <math> \exists i: \tilde{\mu_i} \neq \mu_i</math>, <math> iter < maxiter </math>,		'''Если''' <math> \exists i: \tilde{\mu_i} \neq \mu_i</math>, <math> {\rm iter} < {\rm maxiter} </math>,

	'''то''' <math> inc(iter), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''		'''то''' <math> {\rm inc}({\rm iter}), \Mu=\tilde{\Mu},</math> '''GOTO 2.а.'''

	== Последовательная сложность алгоритма ==		== Последовательная сложность алгоритма ==
Строка 138:		Строка 138:


	'''3)''' В случае, если существует методология быстрого разделения '''n''' объектов на '''k''' множеств при помощи вектора индексации (косвенной адресации), все <math> \tilde{S_i} </math> могут быть обработаны параллельно. В рамках каждого отдельного <math> \tilde{S_i} </math> можно проводить распараллеливание дальше, так как <math> x_{lj} </math> также не зависят друг от друга. Таким образом, вычисление всех слагаемых для всех <math> \tilde{\mu_{ij}} </math> может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого <math> \tilde{\mu_{ij}} </math> может быть выполнено за <math> O(log(n)) </math> в худшем случае (при вхождении почти всех объектов в один кластер).		'''3)''' В случае, если существует методология быстрого разделения '''n''' объектов на '''k''' множеств при помощи вектора индексации (косвенной адресации), все <math> \tilde{S_i} </math> могут быть обработаны параллельно. В рамках каждого отдельного <math> \tilde{S_i} </math> можно проводить распараллеливание дальше, так как <math> x_{lj} </math> также не зависят друг от друга. Таким образом, вычисление всех слагаемых для всех <math> \tilde{\mu_{ij}} </math> может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого <math> \tilde{\mu_{ij}} </math> может быть выполнено за <math> O(\log(n)) </math> в худшем случае (при вхождении почти всех объектов в один кластер).

	Если же такой методологии не существует, то узким местом становится процесс распределения на множества согласно вектору <math>{\rm index}</math>, который можно выполнить за <math> n </math> операций косвенных адресаций.		Если же такой методологии не существует, то узким местом становится процесс распределения на множества согласно вектору <math>{\rm index}</math>, который можно выполнить за <math> n </math> операций косвенных адресаций.

Илья Егоров в 16:53, 13 декабря 2016

2016-12-13T16:53:01Z

Илья Егоров в 16:49, 13 декабря 2016

2016-12-13T16:49:50Z

← Предыдущая версия		Версия от 16:49, 13 декабря 2016
Строка 32:		Строка 32:
	* k центров кластеров <math> \Mu = \{\mu_1 \dots \mu_k \} </math>, где <math> \mu_i = \{\mu_{i1} \dots \mu_{id} \} </math> такие, что		* k центров кластеров <math> \Mu = \{\mu_1 \dots \mu_k \} </math>, где <math> \mu_i = \{\mu_{i1} \dots \mu_{id} \} </math> такие, что

	<math> \begin{cases}\tilde{\mu_i} = \underset{y}{argmin } \sum_{x \in S_i} \|\|x-y\|\|^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} \|\|x-\tilde{\mu_i}\|\|^2_E \end{cases} </math>		<math> \begin{cases}\tilde{\mu_i} = \underset{y}{\rm argmin } \sum_{x \in S_i} \|\|x-y\|\|^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} \|\|x-\tilde{\mu_i}\|\|^2_E \end{cases} </math>

	'''Алгоритм:'''		'''Алгоритм:'''

← Предыдущая версия		Версия от 17:08, 13 декабря 2016
Строка 117:		Строка 117:
	Распределение объектов по кластерам состоит из нахождения матрицы расстояний между <math>X</math> и <math>\Mu</math> (этапа '''2a)''') и нахождения индекса минимального элемента в каждой строке (этап '''2b)'''). Ниже приведен информационный граф данного этапа.		Распределение объектов по кластерам состоит из нахождения матрицы расстояний между <math>X</math> и <math>\Mu</math> (этапа '''2a)''') и нахождения индекса минимального элемента в каждой строке (этап '''2b)'''). Ниже приведен информационный граф данного этапа.

	[[Файл:EgorovBogomazovInf.png \|800px\|thumb\|center\|Нахождение вектора индексов распределения по кластерам]]		[[Файл:EgorovBogomazovInf.png \|800px\|thumb\|center\|Рисунок 1. Нахождение вектора индексов распределения по кластерам]]


	Рассмотрим этап вычисления ячейки <math> {\rm dist}_{ij} </math> матрицы более подробно. Он представляет из себя скалярное произведение d-мерных векторов <math> x_i </math> и <math> \mu_j </math>. Ниже приведена граф для данной операции.		Рассмотрим этап вычисления ячейки <math> {\rm dist}_{ij} </math> матрицы более подробно. Он представляет из себя скалярное произведение d-мерных векторов <math> x_i </math> и <math> \mu_j </math>. Ниже приведена граф для данной операции.

	[[Файл:EgorovBogomazovDist.png\|600px\|thumb\|center\|Операция вычисления расстояния]]		[[Файл:EgorovBogomazovDist.png\|600px\|thumb\|center\|Рисунок 2. Операция вычисления расстояния]]

	На этапе '''3)''' происходит суммирование всех <math> x_l </math> с одинаковым значением индекса в промежуточные суммы. Одновременно происходит подсчет количество элементов с фиксированным индексом. Затем происходит деление промежуточных сумм на соответствующее количество элементов в новом кластере, благодаря чему удается получить обновленные центроиды <math> \tilde{\mu}</math>		На этапе '''3)''' происходит суммирование всех <math> x_l </math> с одинаковым значением индекса в промежуточные суммы. Одновременно происходит подсчет количество элементов с фиксированным индексом. Затем происходит деление промежуточных сумм на соответствующее количество элементов в новом кластере, благодаря чему удается получить обновленные центроиды <math> \tilde{\mu}</math>

	[[Файл:EgorovBogomazovNewCluster.png\|800px\|thumb\|center\|Обновление центроидов]]		[[Файл:EgorovBogomazovNewCluster.png\|800px\|thumb\|center\|Рисунок 3. Обновление центроидов]]

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
Строка 223:		Строка 223:
	Ниже приведены графики зависимости вычислительного времени алгоритма и его эффективности от изменяемых параметров запуска — размера данных и числа процессоров:		Ниже приведены графики зависимости вычислительного времени алгоритма и его эффективности от изменяемых параметров запуска — размера данных и числа процессоров:

	[[file:Egorov_Bogomazov_Time.jpg\|thumb\|center\|700px\|Параллельная реализация алгоритма k-средних. Изменение вычислительного времени алгоритма в зависимости от числа процессоров и размера исходных данных.]]		[[file:Egorov_Bogomazov_Time.jpg\|thumb\|center\|700px\|Рисунок 4. Параллельная реализация алгоритма k-средних. Изменение вычислительного времени алгоритма в зависимости от числа процессоров и размера исходных данных.]]

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

	[[file:Egorov_Bogomazov_Efficiency.jpg\|thumb\|center\|700px\|Параллельная реализация алгоритма k-средних. Изменение эффективности алгоритма в зависимости от числа процессоров и размера исходных данных.]]		[[file:Egorov_Bogomazov_Efficiency.jpg\|thumb\|center\|700px\|Рисунок 5. Параллельная реализация алгоритма k-средних. Изменение эффективности алгоритма в зависимости от числа процессоров и размера исходных данных.]]

	Здесь построена эффективность перехода от последовательной реализации к параллельной. Рассчитывается она по формуле ''Время вычисления на 1 потоке / Время вычисления на T потоках / T'', где T — это число потоков. При вычислении на 1 процессоре она равна 100 % в силу используемой формулы, что и отражено на графике.		Здесь построена эффективность перехода от последовательной реализации к параллельной. Рассчитывается она по формуле ''Время вычисления на 1 потоке / Время вычисления на T потоках / T'', где T — это число потоков. При вычислении на 1 процессоре она равна 100 % в силу используемой формулы, что и отражено на графике.

← Предыдущая версия		Версия от 16:53, 13 декабря 2016
Строка 32:		Строка 32:
	* k центров кластеров <math> \Mu = \{\mu_1 \dots \mu_k \} </math>, где <math> \mu_i = \{\mu_{i1} \dots \mu_{id} \} </math> такие, что		* k центров кластеров <math> \Mu = \{\mu_1 \dots \mu_k \} </math>, где <math> \mu_i = \{\mu_{i1} \dots \mu_{id} \} </math> такие, что

	<math> \begin{cases}\tilde{\mu_i} = \underset{y}{\rm argmin } \sum_{x \in S_i} \|\|x-y\|\|^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} \|\|x-\tilde{\mu_i}\|\|^2_E \end{cases} </math>		<math> \begin{cases}\tilde{\mu_i} = \underset{y}{\rm argmin } \sum_{x \in S_i} \|\|x-y\|\|^2_E \\ \Mu = \underset{\tilde{\Mu}}{\rm argmin } \sum_{i \in k} \sum_{x \in S_i} \|\|x-\tilde{\mu_i}\|\|^2_E \end{cases} </math>

	'''Алгоритм:'''		'''Алгоритм:'''
Строка 38:		Строка 38:
	1) <math> \mu_{i} = random </math>		1) <math> \mu_{i} = random </math>

	2) <math> S_i = \{x \in S~\|~\underset{j}{argmin } \|\|x-\mu_j\|\|_E = i\} i = 1 \dots k </math>		2) <math> S_i = \{x \in S~\|~\underset{j}{\rm argmin } \|\|x-\mu_j\|\|_E = i\} i = 1 \dots k </math>

	3) <math> \tilde{\mu_{i}} = E_{x \in S_i}(x) </math>		3) <math> \tilde{\mu_{i}} = E_{x \in S_i}(x) </math>
Строка 76:		Строка 76:
	'''1) Инициализация центроидов <math>\Mu</math>, <math> iter = 1 </math>, задание максимального количество итераций <math>maxiter</math>'''		'''1) Инициализация центроидов <math>\Mu</math>, <math> iter = 1 </math>, задание максимального количество итераций <math>maxiter</math>'''

	'''2a) Нахождение матрицы расстояний '''<math>dist:</math>		'''2a) Нахождение матрицы расстояний '''<math>{\rm dist}:</math>

	<math>~~dist_~~{ij} = \sum_{l = 1\dots d} (x_{il}-\mu_{jl})^2</math>		<math>{\rm dist}_{ij} = \sum_{l = 1\dots d} (x_{il}-\mu_{jl})^2</math>

	'''2b) Нахождение вектора распределения объектов по кластерам '''<math>index: </math>		'''2b) Нахождение вектора распределения объектов по кластерам '''<math>{\rm index}: </math>

	<math>~~index_~~{i} = \underset{j}{argmin }~~~dist_~~{ij} </math>		<math>{\rm index}_{i} = \underset{j}{\rm argmin }~{\rm dist}_{ij} </math>

	'''3) Пересчет центроидов '''<math>\tilde{\Mu}:</math>		'''3) Пересчет центроидов '''<math>\tilde{\Mu}:</math>

	<math>\tilde{\mu_{ij}} = \sum_{l \in S_i} \dfrac{x_{lj}}{\|S_i\|} </math>, где <math>S_i = \{l~\|~l \in 1\dots n, ~~index_l~~ = i\} </math>		<math>\tilde{\mu_{ij}} = \sum_{l \in S_i} \dfrac{x_{lj}}{\|S_i\|} </math>, где <math>S_i = \{l~\|~l \in 1\dots n, {\rm index}_l = i\} </math>

	'''4) Проверка критерия останова:'''		'''4) Проверка критерия останова:'''
Строка 120:		Строка 120:


	Рассмотрим этап вычисления ячейки <math> ~~dist_~~{ij} </math> матрицы более подробно. Он представляет из себя скалярное произведение d-мерных векторов <math> x_i </math> и <math> \mu_j </math>. Ниже приведена граф для данной операции.		Рассмотрим этап вычисления ячейки <math> {\rm dist}_{ij} </math> матрицы более подробно. Он представляет из себя скалярное произведение d-мерных векторов <math> x_i </math> и <math> \mu_j </math>. Ниже приведена граф для данной операции.

	[[Файл:EgorovBogomazovDist.png\|600px\|thumb\|center\|Операция вычисления расстояния]]		[[Файл:EgorovBogomazovDist.png\|600px\|thumb\|center\|Операция вычисления расстояния]]
Строка 132:		Строка 132:
	Для получения общей картины достаточно определить, в том числе и с помощью информационного графа, каким ресурсом параллелизма обладает каждый из этапов алгоритма:		Для получения общей картины достаточно определить, в том числе и с помощью информационного графа, каким ресурсом параллелизма обладает каждый из этапов алгоритма:

	'''2a)''' Нахождение каждой ячейки матрицы <math> dist </math> может происходить полностью независимо, так как они находятся на одном ярусе. При рассмотрении операции вычисления значения конкретной ячейки <math> ~~dist_~~{ij} </math> можно заметить, что все операции умножения также независимы между собой, поэтому понадобится всего одно умножение. Конечный результат получается в результате суммирования всех слагаемых и достигается параллельно за <math> \log(d) </math> бинарных операций сложения при помощи стандартного метода ''reduction''.		'''2a)''' Нахождение каждой ячейки матрицы <math> {\rm dist} </math> может происходить полностью независимо, так как они находятся на одном ярусе. При рассмотрении операции вычисления значения конкретной ячейки <math> {\rm dist}_{ij} </math> можно заметить, что все операции умножения также независимы между собой, поэтому понадобится всего одно умножение. Конечный результат получается в результате суммирования всех слагаемых и достигается параллельно за <math> \log(d) </math> бинарных операций сложения при помощи стандартного метода ''reduction''.


	'''2b)''' Нахождение вектора распределений заключается в нахождении минимального элемента в каждой строке матрицы <math> dist </math>. При использовании ''reduction'' эту операцию можно выполнить за <math> \log(k) </math> бинарных операций сравнения.		'''2b)''' Нахождение вектора распределений заключается в нахождении минимального элемента в каждой строке матрицы <math> {\rm dist}</math>. При использовании ''reduction'' эту операцию можно выполнить за <math> \log(k) </math> бинарных операций сравнения.


	'''3)''' В случае, если существует методология быстрого разделения '''n''' объектов на '''k''' множеств при помощи вектора индексации (косвенной адресации), все <math> \tilde{S_i} </math> могут быть обработаны параллельно. В рамках каждого отдельного <math> \tilde{S_i} </math> можно проводить распараллеливание дальше, так как <math> x_{lj} </math> также не зависят друг от друга. Таким образом, вычисление всех слагаемых для всех <math> \tilde{\mu_{ij}} </math> может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого <math> \tilde{\mu_{ij}} </math> может быть выполнено за <math> O(log(n)) </math> в худшем случае (при вхождении почти всех объектов в один кластер).		'''3)''' В случае, если существует методология быстрого разделения '''n''' объектов на '''k''' множеств при помощи вектора индексации (косвенной адресации), все <math> \tilde{S_i} </math> могут быть обработаны параллельно. В рамках каждого отдельного <math> \tilde{S_i} </math> можно проводить распараллеливание дальше, так как <math> x_{lj} </math> также не зависят друг от друга. Таким образом, вычисление всех слагаемых для всех <math> \tilde{\mu_{ij}} </math> может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого <math> \tilde{\mu_{ij}} </math> может быть выполнено за <math> O(log(n)) </math> в худшем случае (при вхождении почти всех объектов в один кластер).

	Если же такой методологии не существует, то узким местом становится процесс распределения на множества согласно вектору <math>index</math>, который можно выполнить за <math> n </math> операций косвенных адресаций.		Если же такой методологии не существует, то узким местом становится процесс распределения на множества согласно вектору <math>{\rm index}</math>, который можно выполнить за <math> n </math> операций косвенных адресаций.