Участник:Ян-Мартин Тамм/Строгий алгоритм С средних - История изменений

Darel в 02:42, 19 декабря 2016

2016-12-19T02:42:00Z

← Предыдущая версия		Версия от 02:42, 19 декабря 2016
Строка 3:		Строка 3:
	\| name = Строгий алгоритм С средних (K-means, Hard C-Means)		\| name = Строгий алгоритм С средних (K-means, Hard C-Means)
	\| serial_complexity = <math>O(nkdi)</math>		\| serial_complexity = <math>O(nkdi)</math>
	\| pf_height = <math>O(log_2(k)log_2(d)i)</math>		\| pf_height = <math>O((log_2(n)+log_2(d)+log_2(k))i)</math>
	\| pf_width = <math>O(nkd)</math>		\| pf_width = <math>O(nkd)</math>
	\| input_data = <math>nd+1</math>		\| input_data = <math>nd+1</math>

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

2016-12-19T02:40:57Z

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

← Предыдущая версия		Версия от 02:40, 19 декабря 2016
Строка 113:		Строка 113:

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	~~Самой трудоёмкой операцией является распределение~~ по кластерам. ~~Так, для~~ рассчёта расстояния от данного вектора до всех кластеров можно провести суммирование <math>d</math> элементов за <math>log_2(d)</math> операций. После этого нужно найти наименьшее значение из <math>k</math> элементов за <math>log_2(k)</math> операций. Данные операции для каждого из <math>n</math> векторов, можно делать параллельно. ~~Для сходимости всё так же потребуется~~ <math>i</math> итераций, общая сложность ~~получается~~ <math>O(log_2(k)log_2(d)i)</math>.		Распределение по кластерам.
			Для рассчёта расстояния от данного вектора до всех кластеров можно провести суммирование <math>d</math> элементов за <math>log_2(d)</math> операций. После этого нужно найти наименьшее значение из <math>k</math> элементов за <math>log_2(k)</math> операций. Данные операции для каждого из <math>n</math> векторов, можно делать параллельно.
			<math>O(log_2(k)+log_2(d))</math>.

			Обновление кластерных центров
			<math>O(log(n))</math>.

			Рассчёт <math>J</math> для каждой координаты каждого вектора.
			Вычитаем, возводим в квадрат, складываем за <math>log_2(d)</math> операций и полученные значения складываем за <math>log_2(n)</math> операций. <math>O(log_2(d)+log_2(n)</math>.

			На сходимость уйдёт <math>i</math> итераций, общая сложность <math>O((log_2(n)+log_2(d)+log_2(k))i)</math>

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

Chalker в 23:07, 18 декабря 2016

2016-12-18T23:07:22Z

← Предыдущая версия		Версия от 23:07, 18 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|~~{{REVISIONUSER}}~~}}		{{Assignment\|Coctic}}
	{{algorithm		{{algorithm
	\| name = Строгий алгоритм С средних (K-means, Hard C-Means)		\| name = Строгий алгоритм С средних (K-means, Hard C-Means)

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

2016-12-18T22:47:48Z

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

← Предыдущая версия		Версия от 22:47, 18 декабря 2016
Строка 113:		Строка 113:

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	Самой трудоёмкой операцией является распределение по кластерам. Так, для рассчёта ~~расстояний,~~ можно провести суммирование <math>d</math> элементов за <math>log_2(d)</math> операций. ~~Расстояние от данного вектора до всех кластеров можно найти за одну операцию, после чего~~ нужно найти наименьшее значение из <math>k</math> элементов за <math>log_2(k)</math> операций. ~~И всё это нужно сделать~~ для <math>n</math> векторов, ~~что~~ можно ~~сделать~~ параллельно ~~за одну операцию~~. Для сходимости всё так же потребуется <math>i</math> итераций, общая сложность получается <math>O(log_2(k)log_2(d)i)</math>.		Самой трудоёмкой операцией является распределение по кластерам. Так, для рассчёта расстояния от данного вектора до всех кластеров можно провести суммирование <math>d</math> элементов за <math>log_2(d)</math> операций. После этого нужно найти наименьшее значение из <math>k</math> элементов за <math>log_2(k)</math> операций. Данные операции для каждого из <math>n</math> векторов, можно делать параллельно. Для сходимости всё так же потребуется <math>i</math> итераций, общая сложность получается <math>O(log_2(k)log_2(d)i)</math>.

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

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

2016-12-18T22:44:08Z

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

← Предыдущая версия		Версия от 22:44, 18 декабря 2016
Строка 47:		Строка 47:

	== Макроструктура алгоритма ==		== Макроструктура алгоритма ==
	Как ~~уже говорилось раньше~~, первоначальное распределение векторов по кластерам может быть произвольным, например, можно случайным образом выбрать <math>k</math> векторов из множества всех векторов <math>U</math>.<br>		Как указано выше, первоначальное распределение векторов по кластерам может быть произвольным, например, можно случайным образом выбрать <math>k</math> векторов из множества всех векторов <math>U</math>.<br>
	Далее начинается цикл, его первая операция — распределение векторов по кластерам. В ней для каждого вектора считается расстояние от него, до каждого кластера <math>\rho = \big \\| u - c \big \\|^2=\sum_{i=1}^d (u_i-c_i)^2</math>, после чего из них выбирается наименьшее и заносится в матрицу.<br>Подсчёт функции <math>J</math> можно проводить одновременно с первым шагом, так как в ней суммируются те же самые расстояния.<br>Пересчёт центров кластеров — сумма всех векторов кластера, делённая на количество объектов в кластере. <math>		Далее начинается цикл, его первая операция — распределение векторов по кластерам. В ней для каждого вектора считается расстояние от него, до каждого кластера <math>\rho = \big \\| u - c \big \\|^2=\sum_{i=1}^d (u_i-c_i)^2</math>, после чего из них выбирается наименьшее и заносится в матрицу.<br>Подсчёт функции <math>J</math> можно проводить одновременно с первым шагом, так как в ней суммируются те же самые расстояния.<br>Пересчёт центров кластеров — сумма всех векторов кластера, делённая на количество объектов в кластере. <math>
	c = \frac{1}{\|C\|} \sum\limits_{u \in C} u		c = \frac{1}{\|C\|} \sum\limits_{u \in C} u

Darel: /* Математическое описание алгоритма */

2016-12-18T22:43:37Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 22:43, 18 декабря 2016
Строка 34:		Строка 34:
	\end{cases}		\end{cases}
	</math>		</math>
	<li>Считаем значение функции <math>J</math> и прекращаем работу алгоритма, если это значение меньше заданного порога <math>\varepsilon</math>, либо ~~значение мало изменилось после~~ текущей ~~итерации~~.</li>		<li>Считаем значение функции <math>J</math> и прекращаем работу алгоритма, если это значение меньше заданного порога <math>\varepsilon</math>, либо если разница значений функции <math>J</math> на текущей и предыдущей итерациях меньше некоторого заданного порога <math>\delta</math>.</li>
	<li>Обновляем значения центров кластеров		<li>Обновляем значения центров кластеров
	:<math>		:<math>

Coctic в 10:18, 23 ноября 2016

2016-11-23T10:18:00Z

← Предыдущая версия		Версия от 10:18, 23 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|{{REVISIONUSER}}}}
	{{algorithm		{{algorithm
	\| name = Строгий алгоритм С средних (K-means, Hard C-Means)		\| name = Строгий алгоритм С средних (K-means, Hard C-Means)

Darel в 23:09, 22 ноября 2016

2016-11-22T23:09:35Z

← Предыдущая версия		Версия от 23:09, 22 ноября 2016
Строка 1:		Строка 1:
			{{Assignment}}
	{{algorithm		{{algorithm
	\| name = Строгий алгоритм С средних (K-means, Hard C-Means)		\| name = Строгий алгоритм С средних (K-means, Hard C-Means)

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

2016-11-22T23:09:10Z

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

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

	Исследовалась сильная масштабируемость алгоритма. На графике видно, что алгоритм хорошо распараллеливается и достигается значительное ускорение. Рассчитывалось распределение десятимерных векторов на десять кластеров.		Исследовалась сильная масштабируемость алгоритма. На графике видно, что алгоритм хорошо распараллеливается и достигается значительное ускорение. Рассчитывалось распределение десятимерных векторов на десять кластеров.

			Компилятор mpicc, опция -O2. Исследуемые точки: для 1024, 2048, 4096, 8192, 16384, 32768 векторов программа запускалась на 1, 2, 4, 8, 16, 32, 64, 128, 256 ядрах. Режим исполнения по умолчанию – SMP-режим, на каждый вычислительный узел один mpi процесс.

	[[Файл:HCM_BlueGene.png]]		[[Файл:HCM_BlueGene.png]]

Coctic в 11:15, 18 ноября 2016

2016-11-18T11:15:57Z

← Предыдущая версия		Версия от 11:15, 18 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~
	{{algorithm		{{algorithm
	\| name = Строгий алгоритм С средних (K-means, Hard C-Means)		\| name = Строгий алгоритм С средних (K-means, Hard C-Means)