Алговики - Вклад [ru]

DevbunovaViliana / Метод главных компонент (PСA)

2020-12-04T12:12:42Z

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

Автор:
Девбунова Вилиана Олеговна, студент ММП ВМК МГУ (417)

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

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

Метод Главных Компонент (англ. Principal Components Analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ.Karl Pearson) в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т. п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к сингулярному разложению матрицы данных.

Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (англ. Karhunen-Loeve)или преобразованием Хотеллинга (англ. Hotelling transform). Другие способы уменьшения размерности данных — это метод независимых компонент, многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, поиск наилучшей проекции (англ. Projection Pursuit), нейросетевые методы «узкого горла», самоорганизующиеся карты Кохонена и др.

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

Мы будем рассматривать только один вариант.

=== Вычислительное ядро алгоритма ===
Мы будем реализовывать PCA с помощью нахождения подпространства меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Для вычисления собственных значений и соответствующих им собственных векторов будем использовать метод степенных итераций

==== Алгоритм вычисления собственных значений метод степенных итераций ====
Метод степенных итераций - это итерационный метод вычисления собственных значений и собственных векторов вещественной матрицы.
Алгоритм вычисляет вектор <math>e</math>, содержащий собственные значения , и матрицу <math>E</math>, содержащую соответствующие собственные векторы, т. е. <math>e_i</math>-собственное значение, а столбец <math>E_i</math>-ортонормированный собственный вектор для <math>e_i</math>, для <math>i = 1,...,n</math>.

==== Задача нахождения подпространства меньшей размерности ====

Будем искать подпространство меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Будем использовать жадную стратегию:
Будем подбирать единичные вектора <math>E_i</math>, такие что норма проекций на этот вектор будет максимальна.
*1.<math>||M E_1||^2 → max_{E_1}</math>
*2. <math> |M E_2||^2 → max_{E_2}</math> и <math>E_1</math> ортогонален <math>E_2</math>
*3. и т.д.
Запишем задачу Лагранжа:
<math>\frac{d}{dE_1}(E_1^TM^TME_1 - \lambda(E_1^TE_1 -1) = 0</math>

<math>M^TME_1 - \lambda E_1 = 0</math>
Значит, задача сводится к последовательному нахождению собственных векторов, отвечающих максимальным собственным значениям матрицы <math>M^TM</math>

Алгоритм:
*1. Вычислить эрмитов матрицу (найти сопряженную транспонированную), <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. Вычислить собственные значения и собственные векторы <math>M^TM</math>, используя аметод степенных итераций.
*4. Отсортировать собственные значения и соответствующие столбцы собственных векторов в порядке убывания собственных значений. И взять первые <math>k</math> собственных векторов, отвечающих максимальным собственным значениям.

==== Анализ основных компонентов (PCA) ====
Анализ главных компонент, или сокращенно PCA, - это математическая процедура, которая преобразует набор (возможно коррелированных) переменных в меньшее число некоррелированных переменных, которые называют главными компонентами. Цель анализа главных компонент состоит в том, чтобы уменьшить размерность (количество признаков) набора данных, но сохранить как можно больше исходной изменчивости в данных. На первый основной компонент приходится большая часть изменчивости данных, на второй основной компонент приходится большая часть оставшейся изменчивости и т. д.
PCA можно рассматривать как метод проекции, при котором данные с <math>n</math>-признаками проецируются на подпространство с <math>n</math> (или меньшим количеством) признаков, сохраняя при этом большую часть информации.
Мы будем внешне задавать размерность признанного пространства, которое хотим получить <math>k</math>.
=== Макроструктура алгоритма ===
Макроструктура алгоритма:
*1. Вычислить <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. В цикле до сходимости вычислять:
<math> E_{k+1} = \frac{M^TME_k}{\|M^TME_k\|} </math> -- сойдется к собственному вектору, отвечающему максимальному значению, тогда последовательность
<math>\lambda_{k+1} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}</math> сойдется к максимальному собственному значению.
*4. Теперь вместо выражения <math>M^TM</math> в пункте 3 используем
<math> M^TM - \lambda_k E_k E_k^T</math>
*5. Повторяем пункт 3 и 4 столько раз, какой размерности хотим получить новое пространство.

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

[[Файл:Блок-схема алгоритма.png|мини|центр|Блок-схема алгоритма]]

=== Последовательная сложность алгоритма ===
Оценим сложности операций. Пусть <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>.

=== Информационный граф ===
Так как алгоритм очень объемный и его не возможно представить в 3-ех мерном пространстве, то изобразим информационный граф самой частой операции в алгоритме: умножение матрицы на вектор.
[[Файл:Информационный граф умножения матрицы на вектор.png|мини|центр|Информационный граф умножения матрицы на вектор]]
Одной из самых сложных операций в алгоритме является операция перемножения матриц, ее информационный граф выглядит следующим образом:
[[Файл:Fig1.svg|мини|центр|Информационный граф перемножения матриц]]

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

=== Входные и выходные данные алгоритма ===
На вход алгоритма поступает матрица <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>, и это есть наилучшее представление для данной размерности (потеряли наименьшее количество информации при переходе).

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

[[Файл:Время работы PCA.jpg|мини|центр|Время работы PCA относительно количества потоков и размерности пространства признаков ]]

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

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

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

=== Выводы для классов архитектур ===

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

== Литература ==
<references />
[1] Wikipedia contributors. Principal component analysis. In Wikipedia, The Free Encyclopedia from https://en.wikipedia.org/wiki/Principal_component_analysis

[[en:Multidimensional scaling]]

Файл:Время работы PCA.jpg

2020-12-04T12:10:51Z

DevbunovaViliana:

Время работы PCA относительно количества потоков и размера данных

DevbunovaViliana / Метод главных компонент (PСA)

2020-12-04T12:07:19Z

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

Автор:
Девбунова Вилиана Олеговна, студент ММП ВМК МГУ (417)

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

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

Метод Главных Компонент (англ. Principal Components Analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ.Karl Pearson) в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т. п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к сингулярному разложению матрицы данных.

Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (англ. Karhunen-Loeve)или преобразованием Хотеллинга (англ. Hotelling transform). Другие способы уменьшения размерности данных — это метод независимых компонент, многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, поиск наилучшей проекции (англ. Projection Pursuit), нейросетевые методы «узкого горла», самоорганизующиеся карты Кохонена и др.

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

Мы будем рассматривать только один вариант.

=== Вычислительное ядро алгоритма ===
Мы будем реализовывать PCA с помощью нахождения подпространства меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Для вычисления собственных значений и соответствующих им собственных векторов будем использовать метод степенных итераций

==== Алгоритм вычисления собственных значений метод степенных итераций ====
Метод степенных итераций - это итерационный метод вычисления собственных значений и собственных векторов вещественной матрицы.
Алгоритм вычисляет вектор <math>e</math>, содержащий собственные значения , и матрицу <math>E</math>, содержащую соответствующие собственные векторы, т. е. <math>e_i</math>-собственное значение, а столбец <math>E_i</math>-ортонормированный собственный вектор для <math>e_i</math>, для <math>i = 1,...,n</math>.

==== Задача нахождения подпространства меньшей размерности ====

Будем искать подпространство меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Будем использовать жадную стратегию:
Будем подбирать единичные вектора <math>E_i</math>, такие что норма проекций на этот вектор будет максимальна.
*1.<math>||M E_1||^2 → max_{E_1}</math>
*2. <math> |M E_2||^2 → max_{E_2}</math> и <math>E_1</math> ортогонален <math>E_2</math>
*3. и т.д.
Запишем задачу Лагранжа:
<math>\frac{d}{dE_1}(E_1^TM^TME_1 - \lambda(E_1^TE_1 -1) = 0</math>

<math>M^TME_1 - \lambda E_1 = 0</math>
Значит, задача сводится к последовательному нахождению собственных векторов, отвечающих максимальным собственным значениям матрицы <math>M^TM</math>

Алгоритм:
*1. Вычислить эрмитов матрицу (найти сопряженную транспонированную), <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. Вычислить собственные значения и собственные векторы <math>M^TM</math>, используя аметод степенных итераций.
*4. Отсортировать собственные значения и соответствующие столбцы собственных векторов в порядке убывания собственных значений. И взять первые <math>k</math> собственных векторов, отвечающих максимальным собственным значениям.

==== Анализ основных компонентов (PCA) ====
Анализ главных компонент, или сокращенно PCA, - это математическая процедура, которая преобразует набор (возможно коррелированных) переменных в меньшее число некоррелированных переменных, которые называют главными компонентами. Цель анализа главных компонент состоит в том, чтобы уменьшить размерность (количество признаков) набора данных, но сохранить как можно больше исходной изменчивости в данных. На первый основной компонент приходится большая часть изменчивости данных, на второй основной компонент приходится большая часть оставшейся изменчивости и т. д.
PCA можно рассматривать как метод проекции, при котором данные с <math>n</math>-признаками проецируются на подпространство с <math>n</math> (или меньшим количеством) признаков, сохраняя при этом большую часть информации.
Мы будем внешне задавать размерность признанного пространства, которое хотим получить <math>k</math>.
=== Макроструктура алгоритма ===
Макроструктура алгоритма:
*1. Вычислить <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. В цикле до сходимости вычислять:
<math> E_{k+1} = \frac{M^TME_k}{\|M^TME_k\|} </math> -- сойдется к собственному вектору, отвечающему максимальному значению, тогда последовательность
<math>\lambda_{k+1} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}</math> сойдется к максимальному собственному значению.
*4. Теперь вместо выражения <math>M^TM</math> в пункте 3 используем
<math> M^TM - \lambda_k E_k E_k^T</math>
*5. Повторяем пункт 3 и 4 столько раз, какой размерности хотим получить новое пространство.

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

[[Файл:Блок-схема алгоритма.png|мини|центр|Блок-схема алгоритма]]

=== Последовательная сложность алгоритма ===
Оценим сложности операций. Пусть <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>.

=== Информационный граф ===
Так как алгоритм очень объемный и его не возможно представить в 3-ех мерном пространстве, то изобразим информационный граф самой частой операции в алгоритме: умножение матрицы на вектор.
[[Файл:Информационный граф умножения матрицы на вектор.png|мини|центр|Информационный граф умножения матрицы на вектор]]
Одной из самых сложных операций в алгоритме является операция перемножения матриц, ее информационный граф выглядит следующим образом:
[[Файл:Fig1.svg|мини|центр|Информационный граф перемножения матриц]]

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

=== Входные и выходные данные алгоритма ===
На вход алгоритма поступает матрица <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>, и это есть наилучшее представление для данной размерности (потеряли наименьшее количество информации при переходе).

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

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

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

=== Выводы для классов архитектур ===

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

== Литература ==
<references />
[1] Wikipedia contributors. Principal component analysis. In Wikipedia, The Free Encyclopedia from https://en.wikipedia.org/wiki/Principal_component_analysis

[[en:Multidimensional scaling]]

Файл:Информационный граф умножения матрицы на вектор.png

2020-12-04T12:03:13Z

DevbunovaViliana:

Информационный граф умножения матрицы на вектор

Файл:Блок-схема алгоритма.png

2020-12-04T11:54:02Z

DevbunovaViliana:

Блок-схема алгоритма

DevbunovaViliana / Метод главных компонент (PСA)

2020-12-03T14:46:30Z

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

Автор:
Девбунова Вилиана Олеговна, студент ММП ВМК МГУ (417)

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

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

Метод Главных Компонент (англ. Principal Components Analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ.Karl Pearson) в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т. п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к сингулярному разложению матрицы данных.

Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (англ. Karhunen-Loeve)или преобразованием Хотеллинга (англ. Hotelling transform). Другие способы уменьшения размерности данных — это метод независимых компонент, многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, поиск наилучшей проекции (англ. Projection Pursuit), нейросетевые методы «узкого горла», самоорганизующиеся карты Кохонена и др.

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

Мы будем рассматривать только один вариант.

=== Вычислительное ядро алгоритма ===
Мы будем реализовывать PCA с помощью нахождения подпространства меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Для вычисления собственных значений и соответствующих им собственных векторов будем использовать метод степенных итераций

==== Алгоритм вычисления собственных значений метод степенных итераций ====
Метод степенных итераций - это итерационный метод вычисления собственных значений и собственных векторов вещественной матрицы.
Алгоритм вычисляет вектор <math>e</math>, содержащий собственные значения , и матрицу <math>E</math>, содержащую соответствующие собственные векторы, т. е. <math>e_i</math>-собственное значение, а столбец <math>E_i</math>-ортонормированный собственный вектор для <math>e_i</math>, для <math>i = 1,...,n</math>.

==== Задача нахождения подпространства меньшей размерности ====

Будем искать подпространство меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Будем использовать жадную стратегию:
Будем подбирать единичные вектора <math>E_i</math>, такие что норма проекций на этот вектор будет максимальна.
*1.<math>||M E_1||^2 → max_{E_1}</math>
*2. <math> |M E_2||^2 → max_{E_2}</math> и <math>E_1</math> ортогонален <math>E_2</math>
*3. и т.д.
Запишем задачу Лагранжа:
<math>\frac{d}{dE_1}(E_1^TM^TME_1 - \lambda(E_1^TE_1 -1) = 0</math>

<math>M^TME_1 - \lambda E_1 = 0</math>
Значит, задача сводится к последовательному нахождению собственных векторов, отвечающих максимальным собственным значениям матрицы <math>M^TM</math>

Алгоритм:
*1. Вычислить эрмитов матрицу (найти сопряженную транспонированную), <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. Вычислить собственные значения и собственные векторы <math>M^TM</math>, используя аметод степенных итераций.
*4. Отсортировать собственные значения и соответствующие столбцы собственных векторов в порядке убывания собственных значений. И взять первые <math>k</math> собственных векторов, отвечающих максимальным собственным значениям.

==== Анализ основных компонентов (PCA) ====
Анализ главных компонент, или сокращенно PCA, - это математическая процедура, которая преобразует набор (возможно коррелированных) переменных в меньшее число некоррелированных переменных, которые называют главными компонентами. Цель анализа главных компонент состоит в том, чтобы уменьшить размерность (количество признаков) набора данных, но сохранить как можно больше исходной изменчивости в данных. На первый основной компонент приходится большая часть изменчивости данных, на второй основной компонент приходится большая часть оставшейся изменчивости и т. д.
PCA можно рассматривать как метод проекции, при котором данные с <math>n</math>-признаками проецируются на подпространство с <math>n</math> (или меньшим количеством) признаков, сохраняя при этом большую часть информации.
Мы будем внешне задавать размерность признанного пространства, которое хотим получить <math>k</math>.
=== Макроструктура алгоритма ===
Макроструктура алгоритма:
*1. Вычислить <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. В цикле до сходимости вычислять:
<math> E_{k+1} = \frac{M^TME_k}{\|M^TME_k\|} </math> -- сойдется к собственному вектору, отвечающему максимальному значению, тогда последовательность
<math>\lambda_{k+1} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}</math> сойдется к максимальному собственному значению.
*4. Теперь вместо выражения <math>M^TM</math> в пункте 3 используем
<math> M^TM - \lambda_k E_k E_k^T</math>
*5. Повторяем пункт 3 и 4 столько раз, какой размерности хотим получить новое пространство.

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

=== Последовательная сложность алгоритма ===
Оценим сложности операций. Пусть <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>.

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

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

=== Входные и выходные данные алгоритма ===
На вход алгоритма поступает матрица <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>, и это есть наилучшее представление для данной размерности (потеряли наименьшее количество информации при переходе).

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

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

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

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

=== Выводы для классов архитектур ===

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

== Литература ==
<references />
[1] Wikipedia contributors. Principal component analysis. In Wikipedia, The Free Encyclopedia from https://en.wikipedia.org/wiki/Principal_component_analysis

[[en:Multidimensional scaling]]

DevbunovaViliana / Метод главных компонент (PСA)

2020-12-02T21:10:05Z

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

Автор:
Девбунова Вилиана Олеговна, студент ММП ВМК МГУ (417)

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

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

Метод Главных Компонент (англ. Principal Components Analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ.Karl Pearson) в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т. п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к сингулярному разложению матрицы данных.

Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (англ. Karhunen-Loeve)или преобразованием Хотеллинга (англ. Hotelling transform). Другие способы уменьшения размерности данных — это метод независимых компонент, многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, поиск наилучшей проекции (англ. Projection Pursuit), нейросетевые методы «узкого горла», самоорганизующиеся карты Кохонена и др.

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

Мы будем рассматривать только один вариант.

=== Вычислительное ядро алгоритма ===
Мы будем реализовывать PCA с помощью нахождения подпространства меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Для вычисления собственных значений и соответствующих им собственных векторов будем использовать метод степенных итераций

==== Алгоритм вычисления собственных значений метод степенных итераций ====
Метод степенных итераций - это итерационный метод вычисления собственных значений и собственных векторов вещественной матрицы.
Алгоритм вычисляет вектор <math>e</math>, содержащий собственные значения , и матрицу <math>E</math>, содержащую соответствующие собственные векторы, т. е. <math>e_i</math>-собственное значение, а столбец <math>E_i</math>-ортонормированный собственный вектор для <math>e_i</math>, для <math>i = 1,...,n</math>.

==== Задача нахождения подпространства меньшей размерности ====

Будем искать подпространство меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Будем использовать жадную стратегию:
Будем подбирать единичные вектора <math>E_i</math>, такие что норма проекций на этот вектор будет максимальна.
*1.<math>||M E_1||^2 → max_{E_1}</math>
*2. <math> |M E_2||^2 → max_{E_2}</math> и <math>E_1</math> ортогонален <math>E_2</math>
*3. и т.д.
Запишем задачу Лагранжа:
<math>\frac{d}{dE_1}(E_1^TM^TME_1 - \lambda(E_1^TE_1 -1) = 0</math>

<math>M^TME_1 - \lambda E_1 = 0</math>
Значит, задача сводится к последовательному нахождению собственных векторов, отвечающих максимальным собственным значениям матрицы <math>M^TM</math>

Алгоритм:
*1. Вычислить эрмитов матрицу (найти сопряженную транспонированную), <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. Вычислить собственные значения и собственные векторы <math>M^TM</math>, используя аметод степенных итераций.
*4. Отсортировать собственные значения и соответствующие столбцы собственных векторов в порядке убывания собственных значений. И взять первые <math>k</math> собственных векторов, отвечающих максимальным собственным значениям.

==== Анализ основных компонентов (PCA) ====
Анализ главных компонент, или сокращенно PCA, - это математическая процедура, которая преобразует набор (возможно коррелированных) переменных в меньшее число некоррелированных переменных, которые называют главными компонентами. Цель анализа главных компонент состоит в том, чтобы уменьшить размерность (количество признаков) набора данных, но сохранить как можно больше исходной изменчивости в данных. На первый основной компонент приходится большая часть изменчивости данных, на второй основной компонент приходится большая часть оставшейся изменчивости и т. д.
PCA можно рассматривать как метод проекции, при котором данные с <math>n</math>-признаками проецируются на подпространство с <math>n</math> (или меньшим количеством) признаков, сохраняя при этом большую часть информации.
Мы будем внешне задавать размерность признанного пространства, которое хотим получить <math>k</math>.
=== Макроструктура алгоритма ===
Макроструктура алгоритма:
*1. Вычислить <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. В цикле до сходимости вычислять:
<math> E_{k+1} = \frac{M^TME_k}{\|M^TME_k\|} </math> -- сойдется к собственному вектору, отвечающему максимальному значению, тогда последовательность
<math>\lambda_{k+1} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}</math> сойдется к максимальному собственному значению.
*4. Теперь вместо выражения <math>M^TM</math> в пункте 3 используем
<math> M^TM - \lambda_k E_k E_k^T</math>
*5. Повторяем пункт 3 и 4 столько раз, какой размерности хотим получить новое пространство.

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

=== Последовательная сложность алгоритма ===
Оценим сложности операций. Пусть <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>.

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

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

=== Входные и выходные данные алгоритма ===
На вход алгоритма поступает матрица <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>, и это есть наилучшее представление для данной размерности (потеряли наименьшее количество информации при переходе).

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

=== Выводы для классов архитектур ===

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

== Литература ==
<references />
[1] Wikipedia contributors. Principal component analysis. In Wikipedia, The Free Encyclopedia from https://en.wikipedia.org/wiki/Principal_component_analysis

[[en:Multidimensional scaling]]

DevbunovaViliana / Метод главных компонент (PСA)

2020-12-02T12:48:38Z

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

Автор:
Девбунова Вилиана Олеговна, студент ММП ВМК МГУ (417)

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

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

Метод Главных Компонент (англ. Principal Components Analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ.Karl Pearson) в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т. п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к сингулярному разложению матрицы данных.

Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (англ. Karhunen-Loeve)или преобразованием Хотеллинга (англ. Hotelling transform). Другие способы уменьшения размерности данных — это метод независимых компонент, многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, поиск наилучшей проекции (англ. Projection Pursuit), нейросетевые методы «узкого горла», самоорганизующиеся карты Кохонена и др.

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

Мы будем рассматривать только один вариант.

=== Вычислительное ядро алгоритма ===
Мы будем реализовывать PCA с помощью нахождения подпространства меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Для вычисления собственных значений и соответствующих им собственных векторов будем использовать метод степенных итераций

==== Алгоритм вычисления собственных значений метод степенных итераций ====
Метод степенных итераций - это итерационный метод вычисления собственных значений и собственных векторов вещественной матрицы.
Алгоритм вычисляет вектор <math>e</math>, содержащий собственные значения , и матрицу <math>E</math>, содержащую соответствующие собственные векторы, т. е. <math>e_i</math>-собственное значение, а столбец <math>E_i</math>-ортонормированный собственный вектор для <math>e_i</math>, для <math>i = 1,...,n</math>.

==== Задача нахождения подпространства меньшей размерности ====

Будем искать подпространство меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Будем использовать жадную стратегию:
Будем подбирать единичные вектора <math>E_i</math>, такие что норма проекций на этот вектор будет максимальна.
*1.<math>||M E_1||^2 → max_{E_1}</math>
*2. <math> |M E_2||^2 → max_{E_2}</math> и <math>E_1</math> ортогонален <math>E_2</math>
*3. и т.д.
Запишем задачу Лагранжа:
<math>\frac{d}{dE_1}(E_1^TM^TME_1 - \lambda(E_1^TE_1 -1) = 0</math>

<math>M^TME_1 - \lambda E_1 = 0</math>
Значит, задача сводится к последовательному нахождению собственных векторов, отвечающих максимальным собственным значениям матрицы <math>M^TM</math>

Алгоритм:
*1. Вычислить эрмитов матрицу (найти сопряженную транспонированную), <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. Вычислить собственные значения и собственные векторы <math>M^TM</math>, используя аметод степенных итераций.
*4. Отсортировать собственные значения и соответствующие столбцы собственных векторов в порядке убывания собственных значений. И взять первые <math>k</math> собственных векторов, отвечающих максимальным собственным значениям.

==== Анализ основных компонентов (PCA) ====
Анализ главных компонент, или сокращенно PCA, - это математическая процедура, которая преобразует набор (возможно коррелированных) переменных в меньшее число некоррелированных переменных, которые называют главными компонентами. Цель анализа главных компонент состоит в том, чтобы уменьшить размерность (количество признаков) набора данных, но сохранить как можно больше исходной изменчивости в данных. На первый основной компонент приходится большая часть изменчивости данных, на второй основной компонент приходится большая часть оставшейся изменчивости и т. д.
PCA можно рассматривать как метод проекции, при котором данные с <math>n</math>-признаками проецируются на подпространство с <math>n</math> (или меньшим количеством) признаков, сохраняя при этом большую часть информации.
Мы будем внешне задавать размерность признанного пространства, которое хотим получить <math>k</math>.
=== Макроструктура алгоритма ===
Макроструктура алгоритма:
*1. Вычислить <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. В цикле до сходимости вычислять:
<math> E_{k+1} = \frac{M^TME_k}{\|M^TME_k\|} </math> -- сойдется к собственному вектору, отвечающему максимальному значению, тогда последовательность
<math>\lambda_{k+1} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}</math> сойдется к максимальному собственному значению.
*4. Теперь вместо выражения <math>M^TM</math> в пункте 3 используем
<math> M^TM - \lambda_k E_k E_k^T</math>
*5. Повторяем пункт 3 и 4 столько раз, какой размерности хотим получить новое пространство.

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

=== Последовательная сложность алгоритма ===
Оценим сложности операций. Пусть <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>.

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

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

=== Входные и выходные данные алгоритма ===
На вход алгоритма поступает матрица <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>, и это есть наилучшее представление для данной размерности (потеряли наименьшее количество информации при переходе).

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

=== Выводы для классов архитектур ===

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

== Литература ==
<references />
[1] Wikipedia contributors. Principal component analysis. In Wikipedia, The Free Encyclopedia from https://en.wikipedia.org/wiki/Principal_component_analysis

[[en:Multidimensional scaling]]

DevbunovaViliana / Метод главных компонент (PСA)

2020-12-01T21:04:56Z

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

Автор:
Девбунова Вилиана Олеговна, студент ММП ВМК МГУ (417)

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

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

Метод Главных Компонент (англ. Principal Components Analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ.Karl Pearson) в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т. п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к сингулярному разложению матрицы данных.

Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (англ. Karhunen-Loeve)или преобразованием Хотеллинга (англ. Hotelling transform). Другие способы уменьшения размерности данных — это метод независимых компонент, многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, поиск наилучшей проекции (англ. Projection Pursuit), нейросетевые методы «узкого горла», самоорганизующиеся карты Кохонена и др.

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

Мы будем рассматривать только один вариант.

=== Вычислительное ядро алгоритма ===
Мы будем реализовывать PCA с помощью нахождения подпространства меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Для вычисления собственных значений и соответствующих им собственных векторов будем использовать метод степенных итераций

==== Алгоритм вычисления собственных значений метод степенных итераций ====
Метод степенных итераций - это итерационный метод вычисления собственных значений и собственных векторов вещественной матрицы.
Алгоритм вычисляет вектор <math>e</math>, содержащий собственные значения , и матрицу <math>E</math>, содержащую соответствующие собственные векторы, т. е. <math>e_i</math>-собственное значение, а столбец <math>E_i</math>-ортонормированный собственный вектор для <math>e_i</math>, для <math>i = 1,...,n</math>.

==== Задача нахождения подпространства меньшей размерности ====

Будем искать подпространство меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Будем использовать жадную стратегию:
Будем подбирать единичные вектора <math>E_i</math>, такие что норма проекций на этот вектор будет максимальна.
*1.<math>||M E_1||^2 → max_{E_1}</math>
*2. <math> |M E_2||^2 → max_{E_2}</math> и <math>E_1</math> ортогонален <math>E_2</math>
*3. и т.д.
Запишем задачу Лагранжа:
<math>\frac{d}{dE_1}(E_1^TM^TME_1 - \lambda(E_1^TE_1 -1) = 0</math>

<math>M^TME_1 - \lambda E_1 = 0</math>
Значит, задача сводится к последовательному нахождению собственных векторов, отвечающих максимальным собственным значениям матрицы <math>M^TM</math>

Алгоритм:
*1. Вычислить эрмитов матрицу (найти сопряженную транспонированную), <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. Вычислить собственные значения и собственные векторы <math>M^TM</math>, используя аметод степенных итераций.
*4. Отсортировать собственные значения и соответствующие столбцы собственных векторов в порядке убывания собственных значений. И взять первые <math>k</math> собственных векторов, отвечающих максимальным собственным значениям.

==== Анализ основных компонентов (PCA) ====
Анализ главных компонент, или сокращенно PCA, - это математическая процедура, которая преобразует набор (возможно коррелированных) переменных в меньшее число некоррелированных переменных, которые называют главными компонентами. Цель анализа главных компонент состоит в том, чтобы уменьшить размерность (количество признаков) набора данных, но сохранить как можно больше исходной изменчивости в данных. На первый основной компонент приходится большая часть изменчивости данных, на второй основной компонент приходится большая часть оставшейся изменчивости и т. д.
PCA можно рассматривать как метод проекции, при котором данные с <math>n</math>-признаками проецируются на подпространство с <math>n</math> (или меньшим количеством) признаков, сохраняя при этом большую часть информации.
Мы будем внешне задавать размерность признанного пространства, которое хотим получить <math>k</math>.
=== Макроструктура алгоритма ===
Макроструктура алгоритма:
*1. Вычислить <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. В цикле до сходимости вычислять:
<math> E_{k+1} = \frac{M^TME_k}{\|M^TME_k\|} </math> -- сойдется к собственному вектору, отвечающему максимальному значению, тогда последовательность
<math>\lambda_{k+1} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}</math> сойдется к максимальному собственному значению.
*4. Теперь вместо выражения <math>M^TM</math> в пункте 3 используем
<math> M^TM - \lambda_k E_k E_k^T</math>
*5. Повторяем пункт 3 и 4 столько раз, какой размерности хотим получить новое пространство.

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

=== Последовательная сложность алгоритма ===
Оценим сложности операций. Пусть <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>.

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

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

=== Входные и выходные данные алгоритма ===
На вход алгоритма поступает матрица <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>, и это есть наилучшее представление для данной размерности (потеряли наименьшее количество информации при переходе).

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

=== Выводы для классов архитектур ===

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

== Литература ==
<references />
[1] Wikipedia contributors. Principal component analysis. In Wikipedia, The Free Encyclopedia from https://en.wikipedia.org/wiki/Principal_component_analysis

[[en:Multidimensional scaling]]

DevbunovaViliana / Метод главных компонент (PСA)

2020-12-01T20:46:08Z

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

Автор:
Девбунова Вилиана Олеговна, студент ММП ВМК МГУ (417)

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

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

Метод Главных Компонент (англ. Principal Components Analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ.Karl Pearson) в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т. п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к сингулярному разложению матрицы данных.

Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (англ. Karhunen-Loeve)или преобразованием Хотеллинга (англ. Hotelling transform). Другие способы уменьшения размерности данных — это метод независимых компонент, многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, поиск наилучшей проекции (англ. Projection Pursuit), нейросетевые методы «узкого горла», самоорганизующиеся карты Кохонена и др.

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

Мы будем рассматривать только один вариант.

=== Вычислительное ядро алгоритма ===
Мы будем реализовывать PCA с помощью нахождения подпространства меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Для вычисления собственных значений и соответствующих им собственных векторов будем использовать метод степенных итераций

==== Алгоритм вычисления собственных значений метод степенных итераций ====
Метод степенных итераций - это итерационный метод вычисления собственных значений и собственных векторов вещественной матрицы.
Алгоритм вычисляет вектор <math>e</math>, содержащий собственные значения , и матрицу <math>E</math>, содержащую соответствующие собственные векторы, т. е. <math>e_i</math>-собственное значение, а столбец <math>E_i</math>-ортонормированный собственный вектор для <math>e_i</math>, для <math>i = 1,...,n</math>.

==== Задача нахождения подпространства меньшей размерности ====

Будем искать подпространство меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Будем использовать жадную стратегию:
Будем подбирать единичные вектора <math>E_i</math>, такие что норма проекций на этот вектор будет максимальна.
*1.<math>||M E_1||^2 → max_{E_1}</math>
*2. <math> |M E_2||^2 → max_{E_2}</math> и <math>E_1</math> ортогонален <math>E_2</math>
*3. и т.д.
Запишем задачу Лагранжа:
<math>\frac{d}{dE_1}(E_1^TM^TME_1 - \lambda(E_1^TE_1 -1) = 0</math>

<math>M^TME_1 - \lambda E_1 = 0</math>
Значит, задача сводится к последовательному нахождению собственных векторов, отвечающих максимальным собственным значениям матрицы <math>M^TM</math>

Алгоритм:
*1. Вычислить эрмитов матрицу (найти сопряженную транспонированную), <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. Вычислить собственные значения и собственные векторы <math>M^TM</math>, используя аметод степенных итераций.
*4. Отсортировать собственные значения и соответствующие столбцы собственных векторов в порядке убывания собственных значений. И взять первые <math>k</math> собственных векторов, отвечающих максимальным собственным значениям.

==== Анализ основных компонентов (PCA) ====
Анализ главных компонент, или сокращенно PCA, - это математическая процедура, которая преобразует набор (возможно коррелированных) переменных в меньшее число некоррелированных переменных, которые называют главными компонентами. Цель анализа главных компонент состоит в том, чтобы уменьшить размерность (количество признаков) набора данных, но сохранить как можно больше исходной изменчивости в данных. На первый основной компонент приходится большая часть изменчивости данных, на второй основной компонент приходится большая часть оставшейся изменчивости и т. д.
PCA можно рассматривать как метод проекции, при котором данные с <math>n</math>-признаками проецируются на подпространство с <math>n</math> (или меньшим количеством) признаков, сохраняя при этом большую часть информации.
Мы будем внешне задавать размерность признанного пространства, которое хотим получить <math>k</math>.
=== Макроструктура алгоритма ===
Макроструктура алгоритма:
*1. Вычислить <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. В цикле до сходимости вычислять:
<math> E_{k+1} = \frac{M^TME_k}{\|M^TME_k\|} </math> -- сойдется к собственному вектору, отвечающему максимальному значению, тогда последовательность
<math>\lambda_{k+1} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}</math> сойдется к максимальному собственному значению.
*4. Теперь вместо выражения <math>M^TM</math> в пункте 3 используем
<math> M^TM - \lambda_k E_k E_k^T</math>
*5. Повторяем пункт 3 и 4 столько раз, какой размерности хотим получить новое пространство.

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

=== Последовательная сложность алгоритма ===
Оценим сложности операций. Пусть <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>.

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

=== Выводы для классов архитектур ===

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

== Литература ==
<references />
[1] Wikipedia contributors. Principal component analysis. In Wikipedia, The Free Encyclopedia from https://en.wikipedia.org/wiki/Principal_component_analysis

[[en:Multidimensional scaling]]

DevbunovaViliana / Метод главных компонент (PСA)

2020-12-01T20:29:36Z

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

Автор:
Девбунова Вилиана Олеговна, студент ММП ВМК МГУ (417)

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

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

Метод Главных Компонент (англ. Principal Components Analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ.Karl Pearson) в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т. п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к сингулярному разложению матрицы данных.

Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (англ. Karhunen-Loeve)или преобразованием Хотеллинга (англ. Hotelling transform). Другие способы уменьшения размерности данных — это метод независимых компонент, многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, поиск наилучшей проекции (англ. Projection Pursuit), нейросетевые методы «узкого горла», самоорганизующиеся карты Кохонена и др.

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

Мы будем рассматривать только один вариант.

=== Вычислительное ядро алгоритма ===
Мы будем реализовывать PCA с помощью нахождения подпространства меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Для вычисления собственных значений и соответствующих им собственных векторов будем использовать метод степенных итераций

==== Алгоритм вычисления собственных значений метод степенных итераций ====
Метод степенных итераций - это итерационный метод вычисления собственных значений и собственных векторов вещественной матрицы.
Алгоритм вычисляет вектор <math>e</math>, содержащий собственные значения , и матрицу <math>E</math>, содержащую соответствующие собственные векторы, т. е. <math>e_i</math>-собственное значение, а столбец <math>E_i</math>-ортонормированный собственный вектор для <math>e_i</math>, для <math>i = 1,...,n</math>.

==== Задача нахождения подпространства меньшей размерности ====

Будем искать подпространство меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Будем использовать жадную стратегию:
Будем подбирать единичные вектора <math>E_i</math>, такие что норма проекций на этот вектор будет максимальна.
*1.<math>||M E_1||^2 → max_{E_1}</math>
*2. <math> |M E_2||^2 → max_{E_2}</math> и <math>E_1</math> ортогонален <math>E_2</math>
*3. и т.д.
Запишем задачу Лагранжа:
<math>\frac{d}{dE_1}(E_1^TM^TME_1 - \lambda(E_1^TE_1 -1) = 0</math>

<math>M^TME_1 - \lambda E_1 = 0</math>
Значит, задача сводится к последовательному нахождению собственных векторов, отвечающих максимальным собственным значениям матрицы <math>M^TM</math>

Алгоритм:
*1. Вычислить эрмитов матрицу (найти сопряженную транспонированную), <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. Вычислить собственные значения и собственные векторы <math>M^TM</math>, используя аметод степенных итераций.
*4. Отсортировать собственные значения и соответствующие столбцы собственных векторов в порядке убывания собственных значений. И взять первые <math>k</math> собственных векторов, отвечающих максимальным собственным значениям.

==== Анализ основных компонентов (PCA) ====
Анализ главных компонент, или сокращенно PCA, - это математическая процедура, которая преобразует набор (возможно коррелированных) переменных в меньшее число некоррелированных переменных, которые называют главными компонентами. Цель анализа главных компонент состоит в том, чтобы уменьшить размерность (количество признаков) набора данных, но сохранить как можно больше исходной изменчивости в данных. На первый основной компонент приходится большая часть изменчивости данных, на второй основной компонент приходится большая часть оставшейся изменчивости и т. д.
PCA можно рассматривать как метод проекции, при котором данные с <math>n</math>-признаками проецируются на подпространство с <math>n</math> (или меньшим количеством) признаков, сохраняя при этом большую часть информации.
Мы будем внешне задавать размерность признанного пространства, которое хотим получить <math>k</math>.
=== Макроструктура алгоритма ===
Макроструктура алгоритма:
*1. Вычислить <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. В цикле до сходимости вычислять:
<math> E_{k+1} = \frac{M^TME_k}{\|M^TME_k\|} </math> -- сойдется к собственному вектору, отвечающему максимальному значению, тогда последовательность
<math>\lambda_{k+1} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}</math> сойдется к максимальному собственному значению.
*4. Теперь вместо выражения <math>M^TM</math> в пункте 3 используем
<math> M^TM - \lambda_k E_k E_k^T</math>
*5. Повторяем пункт 3 и 4 столько раз, какой размерности хотим получить новое пространство.

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

=== Последовательная сложность алгоритма ===
Оценим сложности операций. Пусть <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>.

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

=== Выводы для классов архитектур ===

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

== Литература ==
<references />
[1] Wikipedia contributors. Principal component analysis. In Wikipedia, The Free Encyclopedia from https://en.wikipedia.org/wiki/Principal_component_analysis

[[en:Multidimensional scaling]]

DevbunovaViliana / Метод главных компонент (PСA)

2020-12-01T19:31:02Z

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

DevbunovaViliana / Метод главных компонент (PСA)

2020-12-01T15:00:51Z

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

DevbunovaViliana / Метод главных компонент (PСA)

2020-12-01T14:58:34Z

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

DevbunovaViliana / Метод главных компонент (PСA)

2020-12-01T14:20:53Z

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

DevbunovaViliana / Метод главных компонент (PСA)

2020-11-29T11:27:23Z

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

DevbunovaViliana / Метод главных компонент (PСA)

2020-10-21T12:15:28Z

DevbunovaViliana: Новая страница: «Автор: Девбунова Вилиана Олеговна, студент ММП ВМК МГУ (417) == Свойства и структура алгори...»

Автор:
Девбунова Вилиана Олеговна, студент ММП ВМК МГУ (417)

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

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

Метод Главных Компонент (англ. Principal Components Analysis, PCA) — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ.Karl Pearson) в 1901 г. Применяется во многих областях, таких как распознавание образов, компьютерное зрение, сжатие данных и т. п. Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений ковариационной матрицы исходных данных или к сингулярному разложению матрицы данных.

Иногда метод главных компонент называют преобразованием Кархунена-Лоэва (англ. Karhunen-Loeve)или преобразованием Хотеллинга (англ. Hotelling transform). Другие способы уменьшения размерности данных — это метод независимых компонент, многомерное шкалирование, а также многочисленные нелинейные обобщения: метод главных кривых и многообразий, поиск наилучшей проекции (англ. Projection Pursuit), нейросетевые методы «узкого горла», самоорганизующиеся карты Кохонена и др.

=== Математическое описание алгоритма ===
Приводится математическое описание решаемой задачи в виде совокупности формул и соотношений, как это принято в книгах и учебниках. По возможности, используются общепринятые обозначения и способы записи. Должны быть явно определены все использованные обозначения и описаны свойства входных данных. Представленное описание должно быть достаточным для однозначного понимания постановки решаемой задачи для человека, знающего математику.

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

Мы будем рассматривать только один вариант.

=== Вычислительное ядро алгоритма ===
Мы будем реализовывать PCA с помощью сингулярной декомпозиции значений, или сокращенно SVD. Для вычисления собственных значений и соответствующих им собственных векторов будем использовать алгоритм собственных значений Якоби

==== Алгоритм вычисления собственных значений методом Якоби ====
Алгоритм собственных значений Якоби - это итерационный метод вычисления собственных значений и собственных векторов вещественной симметричной матрицы.
Алгоритм вычисляет вектор <math>e</math>, содержащий собственные значения , и матрицу <math>E</math>, содержащую соответствующие собственные векторы, т. е. <math>e_i</math>-собственное значение, а столбец <math>E_i</math>-ортонормированный собственный вектор для <math>e_i</math>, для <math>i = 1,...,n</math>.

==== Сингулярная декомпозиция (SVD) ====
Сингулярная декомпозиция, или сокращенно SVD, - это метод матричного разложения для сведения матрицы к ее составным частям с целью упрощения некоторых последующих матричных вычислений.
SVD матрицы <math>M</math> - это факторизация <math>M</math> в произведение трех матриц <math>M = U \Sigma V^T</math>, где столбцы <math>U</math> и <math>V</math> ортонормированы, а матрица <math>\Sigma</math> диагональна с положительными вещественными числами. Учитывая, что <math>M</math> - действительная матрица <math>m × n</math>, которую мы хотим разложить, <math>U</math> - матрица <math>m × m</math>, <math>\Sigma</math> - диагональная матрица <math>m × n</math>, а <math>V^T</math> - транспонирование матрицы <math>n × n</math>.

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

Алгоритм разложения матрицы с помощью SVD:
*1. Вычислить эрмитов матрицу (найти сопряженную транспонированную), <math>M^T</math> из матрицы <math>M</math>.
*2. Вычислить умножение <math>M^TM</math>
*3. Вычислить собственные значения и собственные векторы <math>M^TM</math>, используя алгоритм Якоби.
*4. Отсортировать собственные значения и соответствующие столбцы собственных векторов в порядке убывания собственных значений.
*5. Взять квадратный корень из собственных значений, чтобы получить сингулярные значения матрицы <math>M</math>.
*6. Построить диагональную матрицу <math>\Sigma</math>, расположив сингулярные значения в порядке убывания вдоль ее диагонали. Заметим, что размер <math>\Sigma</math> есть <math>m × n</math>, таким образом, помещает верхние <math>r</math> сингулярных значений на диагональ и отбрасывает остальные <math>(r = min(m, n))</math> и блок с <math>m - r</math> строками и <math>n - r</math> столбцами содержит нули. Также вычислить <math>\Sigma^{-1}</math>
*7. Отсортированные столбцы собственных векторов представляют матрицу <math>V</math>. Вычислить ее транспонирование <math>V^T</math>
*8. Вычислить матрицу <math>U</math>, как <math>U = M V \Sigma ^{-1}</math>

==== Анализ основных компонентов (PCA) ====
Анализ главных компонент, или сокращенно PCA, - это математическая процедура, которая преобразует набор (возможно коррелированных) переменных в меньшее число некоррелированных переменных, которые называют главными компонентами. Цель анализа главных компонент состоит в том, чтобы уменьшить размерность (количество признаков) набора данных, но сохранить как можно больше исходной изменчивости в данных. На первый основной компонент приходится большая часть изменчивости данных, на второй основной компонент приходится большая часть оставшейся изменчивости и т. д.
PCA можно рассматривать как метод проекции, при котором данные с <math>n</math>-признаками проецируются на подпространство с <math>n</math> (или меньшим количеством) признаков, сохраняя при этом большую часть информации.

Алгоритм вычисления главных компонент:
*1. Входной набор данных <math>D</math> c <math>s</math> объектами и <math>f</math> признаками, т. е. размерность <math>D</math> равна <math>s × f</math>.
*2. Получить собственные значения с помощью алгоритма Якоби и <math>U</math> путем сингулярного векторного разложения матрицы <math>D</math> (или альтернативной матрицы <math>D^T</math> ).
*3. Выбрать <math>k</math> столбцов матрицы <math>U</math>, соответствующие <math>k</math> наибольшим собственным значениям. Здесь <math>k</math> - число измерений нового подпространства объектов <math>(k ≤ f)</math>
*4. Построить проекции матрицы <math>W^T</math> главных компонент на выбранные <math>k</math> собственных векторов.
*5. Преобразовать исходный набор данных <math>D</math> через <math>W</math> и получить <math>k</math>-мерное подпространство признаков <math>\hat{D}</math>.
Обратите внимание, что значения во входном наборе данных D должны быть стандартизированы.
=== Макроструктура алгоритма ===

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

=== Выводы для классов архитектур ===

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

== Литература ==
<references />
[1] Wikipedia contributors. Principal component analysis. In Wikipedia, The Free Encyclopedia from https://en.wikipedia.org/wiki/Principal_component_analysis

[[en:Multidimensional scaling]]