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

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

2016-12-19T14:17:11Z

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

Konshin в 22:14, 18 декабря 2016

2016-12-18T22:14:39Z

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

	{{algorithm		{{algorithm
	\| name = Алгоритм k средних		\| name = Алгоритм k средних

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

2016-12-15T11:24:01Z

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

← Предыдущая версия		Версия от 11:24, 15 декабря 2016
Строка 189:		Строка 189:
	На рисунке 5 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (использовались логарифмические оси). Разными цветами помечены запуски, соответствующие разным количествам объектам, участвующих в кластеризации. Можно видеть близкое к линейному увеличение времени работы программы в зависимости от количества процессоров. Также можно видеть увеличение времени работы алгоритма при увеличении количества объектов.		На рисунке 5 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (использовались логарифмические оси). Разными цветами помечены запуски, соответствующие разным количествам объектам, участвующих в кластеризации. Можно видеть близкое к линейному увеличение времени работы программы в зависимости от количества процессоров. Также можно видеть увеличение времени работы алгоритма при увеличении количества объектов.
	[[Файл:Plot_1.png\|thumb\|center\|900px\|Рисунок 5. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]		[[Файл:Plot_1.png\|thumb\|center\|900px\|Рисунок 5. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

			На рисунке 6 показана эта же зависимость, только в трехмерном пространстве. Аналогично с рисунком 5, были использованы логарифмические оси. Как и в случае двумерного рисунка, можно видеть близкое к линейному увеличение времени работы программы.
			[[Файл:Kmeans-3d.png\|thumb\|center\|900px\|Рисунок 6. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

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

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

2016-12-09T21:37:13Z

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

← Предыдущая версия		Версия от 21:37, 9 декабря 2016
Строка 185:		Строка 185:
	Исследуемый набор данных содержит векторы, размерность которых равна 49. Компоненты векторов являются вещественными числами. Количество кластеров равно 11. Пропущенные значения отсутствуют.		Исследуемый набор данных содержит векторы, размерность которых равна 49. Компоненты векторов являются вещественными числами. Количество кластеров равно 11. Пропущенные значения отсутствуют.

	Для исследования масштабируемости алгоритма была использована реализация на языке C с использованием MPI<ref>http://users.eecs.northwestern.edu/~wkliao/Kmeans/index.html</ref>. Код можно найти здесь: https://github.com/serban/kmeans.		Для исследования масштабируемости алгоритма была использована реализация на языке C с использованием MPI<ref>http://users.eecs.northwestern.edu/~wkliao/Kmeans/index.html</ref>. Код можно найти здесь: https://github.com/serban/kmeans. Данная реализация предоставляет возможность распараллеливать решение задачи с помощью технологий MPI, OpenMP И CUDA. Для запуска MPI-версии программы использовалась цель "mpi_main" Makefile.

	На рисунке 5 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров. Можно видеть, что при увеличении количества процессоров в N раз, время работы алгоритма уменьшается примерно в N раз (~~при условии, что количество объектов остается неизменным~~). ~~Также можно отметить~~, ~~что при фиксированном количестве процессоров~~, ~~зависимость времени работы алгоритма от количества объектов также близка к линейной.~~		На рисунке 5 показана зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров (использовались логарифмические оси). Разными цветами помечены запуски, соответствующие разным количествам объектам, участвующих в кластеризации. Можно видеть близкое к линейному увеличение времени работы программы в зависимости от количества процессоров. Также можно видеть увеличение времени работы алгоритма при увеличении количества объектов.
	~~[[Файл:Heatmap_kmeans.png\|thumb\|center\|900px\|Рисунок 5. Зависимости времени работы алгоритма~~ кластеризации ~~k-means в зависимости от количества используемых процессоров~~.]]		[[Файл:Plot_1.png\|thumb\|center\|900px\|Рисунок 5. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров.]]

	~~На рисунке 6 показана зависимости~~ времени работы ~~алгоритма кластеризации k-means~~ в зависимости от количества ~~используемых~~ процессоров ~~(при фиксированном количестве объектов, равном 50000)~~. ~~При визуализации была использована логарифмическая шкала. Можно отметить, что при заданном наборе данных~~ можно ~~наблюдать линейную зависимость~~ времени работы алгоритма от количества используемых процессоров, что согласуется с теоретической оценкой сложности последовательной версии алгоритма.
	[[Файл:~~50000kmeans~~.png\|thumb\|center\|900px\|Рисунок 6. Зависимости времени работы алгоритма кластеризации k-means в зависимости от количества используемых процессоров ~~(количество объектов равно 50000)~~.]]

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

Ivan.mashonskiy: /* Ресурс параллелизма алгоритма */

2016-12-08T14:40:38Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 14:40, 8 декабря 2016
Строка 122:		Строка 122:
	Параллельная сложность этапа обновления центров масс кластеров вычисляется следующим образом: так как обновление значений каждого из центров масс кластеров можно выполнять независимо, параллельная сложность определяется сложностью обновления центра масс самого большого кластера. В худшем случае для нахождения значения выражения <math>\mu^{(t+1)}_j = \frac{1}{\|S^{(t)}_i\|} \sum_{x_j \in S^{(t)}_i} x_j </math> требуется <math>O(\log n)</math> операций.		Параллельная сложность этапа обновления центров масс кластеров вычисляется следующим образом: так как обновление значений каждого из центров масс кластеров можно выполнять независимо, параллельная сложность определяется сложностью обновления центра масс самого большого кластера. В худшем случае для нахождения значения выражения <math>\mu^{(t+1)}_j = \frac{1}{\|S^{(t)}_i\|} \sum_{x_j \in S^{(t)}_i} x_j </math> требуется <math>O(\log n)</math> операций.

	С учетом вышесказанного, итоговая параллельная сложность алгоритма k средних определяется выражением <math>O(t * \log ~~kdn~~)</math>.		С учетом вышесказанного, итоговая параллельная сложность алгоритма k средних определяется выражением <math>O(t \cdot \log nkd)</math>.

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

Ivan.mashonskiy: /* Ресурс параллелизма алгоритма */

2016-12-08T14:40:09Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 14:40, 8 декабря 2016
Строка 116:		Строка 116:
	Учитывая данный факт можно оценить параллельную сложность алгоритма в предположении доступности неограниченного числа необходимых процессоров.		Учитывая данный факт можно оценить параллельную сложность алгоритма в предположении доступности неограниченного числа необходимых процессоров.

	В силу особенностей алгоритма k средних порядок выполнения основных этапов существенен, что не позволяет выполнять их параллельно. Таким образом, итоговая сложность параллельного алгоритма будет определяться, исходя из формулы <math>T = t * (T_{as} + T_{up})</math>, где <math>T_{as}</math> - параллельная сложность этапа распределения векторов по кластерам, <math>T_{up}</math> - параллельная сложность этапа обновления центров масс кластеров, <math>t</math> - общее число итераций алгоритма.		В силу особенностей алгоритма k средних порядок выполнения основных этапов существенен, что не позволяет выполнять их параллельно. Таким образом, итоговая сложность параллельного алгоритма будет определяться, исходя из формулы <math>T = t \cdot (T_{as} + T_{up})</math>, где <math>T_{as}</math> - параллельная сложность этапа распределения векторов по кластерам, <math>T_{up}</math> - параллельная сложность этапа обновления центров масс кластеров, <math>t</math> - общее число итераций алгоритма.

	Параллельная сложность этапа распределения векторов по кластерам с учетом доступности неограниченного числа процессоров вычисляется следующим образом: так как вычисление значений <math>\big \\| x_i - \mu^{(t)}_j \big \\|^2</math> для каждой пары векторов <math>x_i, i = 1, 2, ..., n</math> и <math>\mu^{(t)}_j, j = 1, 2, ..., k</math> можно выполнять независимо и для вычисления этого выражения требуется <math>O(\log d)</math> операций в соответствии с [[Нахождение_частных_сумм_элементов_массива_сдваиванием \| параллельной реализацией нахождения сумм элементов массива сдваиванием]]. Параллельная сложность реализации операции нахождения минимума из <math>k</math> элементов определяется как <math>O(\log k)</math>. Таким образом, сложность этапа распределения векторов по кластерам <math>O(\log kd)</math>.		Параллельная сложность этапа распределения векторов по кластерам с учетом доступности неограниченного числа процессоров вычисляется следующим образом: так как вычисление значений <math>\big \\| x_i - \mu^{(t)}_j \big \\|^2</math> для каждой пары векторов <math>x_i, i = 1, 2, ..., n</math> и <math>\mu^{(t)}_j, j = 1, 2, ..., k</math> можно выполнять независимо и для вычисления этого выражения требуется <math>O(\log d)</math> операций в соответствии с [[Нахождение_частных_сумм_элементов_массива_сдваиванием \| параллельной реализацией нахождения сумм элементов массива сдваиванием]]. Параллельная сложность реализации операции нахождения минимума из <math>k</math> элементов определяется как <math>O(\log k)</math>. Таким образом, сложность этапа распределения векторов по кластерам <math>O(\log kd)</math>.

Ivan.mashonskiy: /* Последовательная сложность алгоритма */

2016-12-08T14:39:31Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 14:39, 8 декабря 2016
Строка 76:		Строка 76:

	Для вычисления центра массы кластера, содержащего <math>n_i</math> d-мерных векторов, необходимо:		Для вычисления центра массы кластера, содержащего <math>n_i</math> d-мерных векторов, необходимо:
	* <math>n_i * (d - 1)</math> операций сложения		* <math>n_i \cdot (d - 1)</math> операций сложения
	* <math>d</math> операций деления		* <math>d</math> операций деления

	Для определения центров масс всех k кластеров требуется:		Для определения центров масс всех k кластеров требуется:
	* <math>n * (d - 1)</math> операций сложения		* <math>n \cdot (d - 1)</math> операций сложения
	* <math>k * d</math> операций деления		* <math>k \cdot d</math> операций деления

	Для определения расстояния между двумя d-мерными векторами, требуется:		Для определения расстояния между двумя d-мерными векторами, требуется:
Строка 89:		Строка 89:

	Для определения кластера для n d-мерного векторов, необходимо:		Для определения кластера для n d-мерного векторов, необходимо:
	* <math>n * k * d</math> операций вычитания		* <math>n \cdot k \cdot d</math> операций вычитания
	* <math>n * k * d</math> операций умножения		* <math>n \cdot k \cdot d</math> операций умножения
	* <math>n * k * (d - 1)</math> операций сложения		* <math>n \cdot k \cdot (d - 1)</math> операций сложения

	Таким образом, общая сложность одной итерации:		Таким образом, общая сложность одной итерации:
	* <math>O(n * k * d)</math> операций сложения/вычитания		* <math>O(n k d)</math> операций сложения/вычитания
	* <math>O(n * k * d)</math> операций умножения/деления		* <math>O(n k d)</math> операций умножения/деления

	Сложность всего алгоритма, состоящего из <math>t</math> итераций: <math>O(t * n * k * d)</math>		Сложность всего алгоритма, состоящего из <math>t</math> итераций: <math>O(t n k d)</math>

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

Ivan.mashonskiy в 14:37, 8 декабря 2016

2016-12-08T14:37:42Z

← Предыдущая версия		Версия от 14:37, 8 декабря 2016
Строка 6:		Строка 6:
	\| output_data = <math>n</math>		\| output_data = <math>n</math>
	\| pf_height = <math>O(t \cdot \log nkd)</math>		\| pf_height = <math>O(t \cdot \log nkd)</math>
	\| pf_width = <math>O(~~kdn~~)</math>		\| pf_width = <math>O(nkd)</math>
	}}		}}

Ivan.mashonskiy в 14:37, 8 декабря 2016

2016-12-08T14:37:19Z

← Предыдущая версия		Версия от 14:37, 8 декабря 2016
Строка 5:		Строка 5:
	\| input_data = <math>nd</math>		\| input_data = <math>nd</math>
	\| output_data = <math>n</math>		\| output_data = <math>n</math>
	\| pf_height = <math>O(t * \log ~~kdn~~)</math>		\| pf_height = <math>O(t \cdot \log nkd)</math>
	\| pf_width = <math>O(kdn)</math>		\| pf_width = <math>O(kdn)</math>
	}}		}}

Ivan.mashonskiy: /* Свойства алгоритма */

2016-12-08T14:36:37Z

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

← Предыдущая версия		Версия от 14:36, 8 декабря 2016
Строка 141:		Строка 141:
	=== Свойства алгоритма ===		=== Свойства алгоритма ===

	Соотношение последовательной и параллельной сложности алгоритма равно <math>\frac{O(tnkd)}{O(t * \log ~~kdn~~)}</math>.		Соотношение последовательной и параллельной сложности алгоритма равно <math>\frac{O(tnkd)}{O(t \cdot \log nkd)}</math>.

	Число операций алгоритма k средних оценивается как <math>O(tnkd)</math>, суммарный объем входных и выходных данных равен <math>n(d+1)</math>. Следовательно, вычислительная мощность алгоритма линейна по <math>k</math> и линейна по <math>t</math>.		Число операций алгоритма k средних оценивается как <math>O(tnkd)</math>, суммарный объем входных и выходных данных равен <math>n(d+1)</math>. Следовательно, вычислительная мощность алгоритма линейна по <math>k</math> и линейна по <math>t</math>.