DevbunovaViliana / Метод главных компонент (PСA) - История изменений

DevbunovaViliana: /* Программная реализация алгоритма */

2020-12-04T12:12:42Z

Программная реализация алгоритма

← Предыдущая версия		Версия от 12:12, 4 декабря 2020
Строка 94:		Строка 94:
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===

	[~~https~~:~~//wmpics.pics/di-ANZL~~.jpg ~~График производительности~~]		[[Файл:Время работы PCA.jpg\|мини\|центр\|Время работы PCA относительно количества потоков и размерности пространства признаков ]]

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

DevbunovaViliana: /* Свойства и структура алгоритма */

2020-12-04T12:07:19Z

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

← Предыдущая версия		Версия от 12:07, 4 декабря 2020
Строка 61:		Строка 61:

	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	[~~https~~:~~//wmpics.pics/di~~-~~2ZK0~~.png Блок схема алгоритма]
			[[Файл:Блок-схема алгоритма.png\|мини\|центр\|Блок-схема алгоритма]]

	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===
Строка 70:		Строка 71:
	=== Информационный граф ===		=== Информационный граф ===
	Так как алгоритм очень объемный и его не возможно представить в 3-ех мерном пространстве, то изобразим информационный граф самой частой операции в алгоритме: умножение матрицы на вектор.		Так как алгоритм очень объемный и его не возможно представить в 3-ех мерном пространстве, то изобразим информационный граф самой частой операции в алгоритме: умножение матрицы на вектор.
	[~~https~~:~~//wmpics.pics/di-PC11~~.png Информационный граф ~~операции~~ умножения матрицы на вектор]		[[Файл:Информационный граф умножения матрицы на вектор.png\|мини\|центр\|Информационный граф умножения матрицы на вектор]]
	Одной из самых сложных операций в алгоритме является операция перемножения матриц, ее информационный граф выглядит следующим образом:		Одной из самых сложных операций в алгоритме является операция перемножения матриц, ее информационный граф выглядит следующим образом:
	[~~https~~:~~//algowiki-project.org/algowiki/pool/images/f/f5/~~Fig1.svg Информационный граф перемножения матриц]		[[Файл:Fig1.svg\|мини\|центр\|Информационный граф перемножения матриц]]

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

DevbunovaViliana: /* Программная реализация алгоритма */

2020-12-03T14:46:30Z

Программная реализация алгоритма

← Предыдущая версия		Версия от 14:46, 3 декабря 2020
Строка 92:		Строка 92:

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

			[https://wmpics.pics/di-ANZL.jpg График производительности]

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

			Проведем оценку масштабируемости:
			*1. По количеству потоков: При увеличении количества потоков время работы алгоритма уменьшается. Отметим, что с каждым увеличением количества потоков уменьшается скорость роста времени работы при фиксированном колличестве потоков и увеличении размера признакого пространства.
			*2. По размеру пространства признаков: С увеличением размера данных задача считается дольше. Аналогично, заметим, что если брать график времени работы относительно фиксированного размера признаков: берем график времени в зависимости от количества потоков при 10 тысячах признаков, потом при 15, 20 и так далее, увидим, что скорость падения нашей функции с ростом размерности пространства увеличивается.
			*3. По двум напрвлениям сразу: Время работы алгоритма монотонно уменьшается с увеличением количества потоков и уменьшением размера признакого пространства одновременно.



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

DevbunovaViliana: /* Существующие реализации алгоритма */

2020-12-02T21:10:05Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 21:10, 2 декабря 2020
Строка 98:		Строка 98:

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===
			Есть реализация метода главных компонент в библиотеке [https://scikit-learn.org/ scikit-learn] для Python. [https://scikit-learn.org/stable/modules/generated/sklearn.decomposition.PCA.html Ссылка на библиотечный метод]. Но сам код реализации посмотреть невозможно, потому что это библиотека с закрытым кодом.

	== Литература ==		== Литература ==

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

2020-12-02T12:48:38Z

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

← Предыдущая версия		Версия от 12:48, 2 декабря 2020
Строка 75:		Строка 75:

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	Если посмотреть на блок-схему алгоритма, то видно, что он строго последовательный на макроуровне, но отдельно взятые операции можно распараллелить. Причем они могут быть распараллелены покоординатно (так как имеют независимость итераций в некоторых циклах): умножение матриц, деление вектора на константу, умножение вектора на константу, транспонирование матрицы, вычитание матриц, умножение матрицы на число.		Если посмотреть на блок-схему алгоритма, то видно, что он строго последовательный на макроуровне, но отдельно взятые операции можно распараллелить. Причем они могут быть распараллелены покоординатно (так как имеют независимость итераций в некоторых циклах): умножение матриц, деление вектора на константу, умножение вектора на константу, транспонирование матрицы, вычитание матриц, умножение матрицы на число. К примеру, для умножения квадратной матрицы <math>R^{d×d}</math> на вектор <math>R^d</math> нужно последовательно выполнить по <math>d</math> ярусов умножений и сложений, где в каждом ярусе <math>d</math> операций. Для алгоритма умножения матриц <math>R^{d×n}</math> на <math>R^{n×d}</math> требуется последовательно выполнить по <math>n</math> ярусов умножений и сложений, где в каждом из ярусов <math>d^2</math> операций.

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

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

2020-12-01T21:04:56Z

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

← Предыдущая версия		Версия от 21:04, 1 декабря 2020
Строка 78:		Строка 78:

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===
			На вход алгоритма поступает матрица <math>M \in R^{n×d}</math>, где по строкам записано признаковое представление объектов и число k до какого размера мы хотим сократить размерность пространства признаков (обычно <math>k << d</math>).
			На выходе мы получаем <math>k</math> векторов и соответствующих им собственных значений матрицы <math>M^TM</math>, отсортированных в порядке убывания. Проекция объектов из <math>M</math> на эти вектора дает новое представление этих объектов, но в пространстве размерности <math>k</math>, и это есть наилучшее представление для данной размерности (потеряли наименьшее количество информации при переходе).

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

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

2020-12-01T20:46:08Z

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

← Предыдущая версия		Версия от 20:46, 1 декабря 2020
Строка 75:		Строка 75:

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
			Если посмотреть на блок-схему алгоритма, то видно, что он строго последовательный на макроуровне, но отдельно взятые операции можно распараллелить. Причем они могут быть распараллелены покоординатно (так как имеют независимость итераций в некоторых циклах): умножение матриц, деление вектора на константу, умножение вектора на константу, транспонирование матрицы, вычитание матриц, умножение матрицы на число.

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

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

2020-12-01T20:29:36Z

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

← Предыдущая версия		Версия от 20:29, 1 декабря 2020
Строка 69:		Строка 69:

	=== Информационный граф ===		=== Информационный граф ===
			Так как алгоритм очень объемный и его не возможно представить в 3-ех мерном пространстве, то изобразим информационный граф самой частой операции в алгоритме: умножение матрицы на вектор.
			[https://wmpics.pics/di-PC11.png Информационный граф операции умножения матрицы на вектор]
			Одной из самых сложных операций в алгоритме является операция перемножения матриц, ее информационный граф выглядит следующим образом:
			[https://algowiki-project.org/algowiki/pool/images/f/f5/Fig1.svg Информационный граф перемножения матриц]

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

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

2020-12-01T19:31:02Z

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

← Предыдущая версия		Версия от 19:31, 1 декабря 2020
Строка 64:		Строка 64:

	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===
			Оценим сложности операций. Пусть <math>n</math> -- количество объектов в выборке, <math>d</math> -- размерность пространства признаков, <math>k</math> -- размерность итогового пространства (но так как основной смысл задачи -- это понижение размерности, то <math>k << n</math> и <math>k << d</math>, поэтому мы не будем учитывать его при подсчете асимптотической сложности), тогда: нахождение транспонированной матрицы <math>O(n*d)</math>,
			перемножение <math>M^TM</math>имеет сложность <math>O(n*d^2)</math>, случайная генерация вектора <math>O(d)</math>, вычисление <math>E_k</math> состоит из перемножения матрицы на вектор, что занимает <math>O(d^2)</math>, вычисление нормы вектора <math>O(d)</math> и покомпонентного деление вектора на константу <math>O(d)</math>. Подсчет <math>\lambda_k</math> использует уже посчитанное для <math>E_k</math> умножение матрицы на вектор, дополнительно происходит два раза скалярное произведение над векторами <math>O(d)</math>, и поэлементное деление вектора на константу <math>O(d)</math>.
			Вычисление <math>\lambda_k E_k E_k^T</math> занимает <math>O(d^2)</math>, вычитание матриц имеет сложность <math>O(d^2)</math>.

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

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

2020-12-01T15:00:51Z

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

← Предыдущая версия		Версия от 15:00, 1 декабря 2020
Строка 55:		Строка 55:
	*3. В цикле до сходимости вычислять:		*3. В цикле до сходимости вычислять:
	<math> E_{k+1} = \frac{M^TME_k}{\\|M^TME_k\\|} </math> -- сойдется к собственному вектору, отвечающему максимальному значению, тогда последовательность		<math> E_{k+1} = \frac{M^TME_k}{\\|M^TME_k\\|} </math> -- сойдется к собственному вектору, отвечающему максимальному значению, тогда последовательность
	<math>\lambda_{k} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}</math> сойдется к максимальному собственному значению.		<math>\lambda_{k+1} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}</math> сойдется к максимальному собственному значению.
	*4. Теперь вместо выражения <math>M^TM</math> в пункте 3 используем		*4. Теперь вместо выражения <math>M^TM</math> в пункте 3 используем
	<math> M^TM - \lambda_k E_k E_k^T</math>		<math> M^TM - \lambda_k E_k E_k^T</math>