DevbunovaViliana / Метод главных компонент (PСA): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
 
(не показано 7 промежуточных версий этого же участника)
Строка 61: Строка 61:
  
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
[https://wmpics.pics/di-2ZK0.png Блок схема алгоритма]
+
 +
[[Файл:Блок-схема алгоритма.png|мини|центр|Блок-схема алгоритма]]
  
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
Строка 69: Строка 70:
  
 
=== Информационный граф ===
 
=== Информационный граф ===
 +
Так как алгоритм очень объемный и его не возможно представить в 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>, и это есть наилучшее представление для данной размерности (потеряли наименьшее количество информации при переходе).
  
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
Строка 85: Строка 93:
  
 
=== Масштабируемость алгоритма и его реализации ===
 
=== Масштабируемость алгоритма и его реализации ===
 +
 +
[[Файл:Время работы PCA.jpg|мини|центр|Время работы PCA относительно количества потоков и размерности пространства признаков ]]
 +
 +
К сожалению, мы не можем рассчитать в GFlops, потому что не можем точно сказать количество операций (не знаем за сколько шагов у нас сойдется собственное значение и собственный векторв).
 +
 +
Проведем оценку масштабируемости:
 +
*1. По количеству потоков: При увеличении количества потоков время работы алгоритма уменьшается. Отметим, что с каждым увеличением количества потоков уменьшается скорость роста времени работы при фиксированном колличестве потоков и увеличении  размера признакого пространства.
 +
*2. По размеру пространства признаков: С увеличением размера данных задача считается дольше.  Аналогично, заметим, что если брать график времени работы относительно фиксированного размера признаков: берем график времени в зависимости от количества потоков при 10 тысячах признаков, потом при 15, 20 и так далее, увидим, что скорость падения нашей функции с ростом размерности пространства увеличивается.
 +
*3. По двум напрвлениям сразу:  Время работы алгоритма монотонно уменьшается с увеличением количества потоков и уменьшением размера признакого пространства одновременно.
 +
 +
  
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
Строка 91: Строка 110:
  
 
=== Существующие реализации алгоритма ===
 
=== Существующие реализации алгоритма ===
 +
Есть реализация метода главных компонент в библиотеке [https://scikit-learn.org/ scikit-learn] для Python. [https://scikit-learn.org/stable/modules/generated/sklearn.decomposition.PCA.html Ссылка на библиотечный метод]. Но сам код реализации посмотреть невозможно, потому что это библиотека с закрытым кодом.
  
 
== Литература ==
 
== Литература ==

Текущая версия на 15:12, 4 декабря 2020

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

Содержание

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

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

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

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

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

Задача анализа главных компонент имеет много версий, вот базовые из них:

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

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

1.3 Вычислительное ядро алгоритма

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

1.3.1 Алгоритм вычисления собственных значений метод степенных итераций

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

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

Будем искать подпространство меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Будем использовать жадную стратегию: Будем подбирать единичные вектора [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] собственных векторов, отвечающих максимальным собственным значениям.

1.3.3 Анализ основных компонентов (PCA)

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

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

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

  • 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 столько раз, какой размерности хотим получить новое пространство.

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

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

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

Оценим сложности операций. Пусть [math]n[/math] -- количество объектов в выборке, [math]d[/math] -- размерность пространства признаков, [math]k[/math] -- размерность итогового пространства (но так как основной смысл задачи -- это понижение размерности, то [math]k \lt \lt n[/math] и [math]k \lt \lt 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].

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

Так как алгоритм очень объемный и его не возможно представить в 3-ех мерном пространстве, то изобразим информационный граф самой частой операции в алгоритме: умножение матрицы на вектор.

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

Одной из самых сложных операций в алгоритме является операция перемножения матриц, ее информационный граф выглядит следующим образом:

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

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

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

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

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

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

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

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

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

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

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

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

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

Проведем оценку масштабируемости:

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


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

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

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

Есть реализация метода главных компонент в библиотеке scikit-learn для Python. Ссылка на библиотечный метод. Но сам код реализации посмотреть невозможно, потому что это библиотека с закрытым кодом.

3 Литература

[1] Wikipedia contributors. Principal component analysis. In Wikipedia, The Free Encyclopedia from https://en.wikipedia.org/wiki/Principal_component_analysis