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

[непроверенная версия]

Версия 17:20, 1 декабря 2020

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

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
3 Литература

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} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}[/math] сойдется к максимальному собственному значению.

4. Теперь вместо выражения M^TM в пункте 3 используем

[math] M^TM - \lambda_k E_k E_k^T[/math]

5. Повторяем пункт 3 и 4 столько раз, какой размерности хотим получить новое пространство.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 Литература

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

@@ Строка 20: / Строка 20: @@
 === Вычислительное ядро алгоритма ===
-Мы будем реализовывать PCA с помощью сингулярной декомпозиции значений, или сокращенно SVD. Для вычисления собственных значений и соответствующих им собственных векторов будем использовать алгоритм собственных значений Якоби
+Мы будем реализовывать PCA с помощью нахождения подпространства меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Для вычисления собственных значений и соответствующих им собственных векторов будем использовать метод степенных итераций
-==== Алгоритм вычисления собственных значений методом Якоби ====
+==== Алгоритм вычисления собственных значений метод степенных итераций ====
-Алгоритм собственных значений Якоби - это итерационный метод вычисления собственных значений и собственных векторов вещественной симметричной матрицы.
+Метод степенных итераций - это итерационный метод вычисления собственных значений и собственных векторов вещественной матрицы.
 Алгоритм вычисляет вектор <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>.
+Будем искать подпространство меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Будем использовать жадную стратегию:
+Будем подбирать единичные вектора <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>
-SVD является наиболее известным и широко используемым методом декомпозиции матриц. Все матрицы имеют сингулярное разложение, которое делает их более стабильными. Он часто используется в широком спектре приложений, включая сжатие, шумоподавление и сокращение данных.
+<math>M^TME_1 - \lambda E_1 = 0</math>
+Значит, задача сводится к последовательному нахождению собственных векторов, отвечающих максимальным собственным значениям матрицы <math>M^TM</math>
-Алгоритм разложения матрицы с помощью SVD:
+Алгоритм:
 *1. Вычислить эрмитов матрицу (найти сопряженную транспонированную), <math>M^T</math> из матрицы <math>M</math>.
 *2. Вычислить умножение <math>M^TM</math>
-*3. Вычислить собственные значения и собственные векторы <math>M^TM</math>, используя алгоритм Якоби.
+*3. Вычислить собственные значения и собственные векторы <math>M^TM</math>, используя аметод степенных итераций.
-*4. Отсортировать собственные значения и соответствующие столбцы собственных векторов в порядке убывания собственных значений.
+*4. Отсортировать собственные значения и соответствующие столбцы собственных векторов в порядке убывания собственных значений. И взять первые <math>k</math> собственных векторов, отвечающих максимальным собственным значениям.
-*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> (или меньшим количеством) признаков, сохраняя при этом большую часть информации.
+Мы будем внешне задавать размерность признанного пространства, которое  хотим получить <math>k</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 должны быть стандартизированы.
 === Макроструктура алгоритма ===
+Макроструктура алгоритма:
+*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} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}</math> сойдется к максимальному собственному значению.
+*4. Теперь вместо выражения M^TM в пункте 3 используем
+<math> M^TM - \lambda_k E_k E_k^T</math>
+*5. Повторяем пункт 3 и 4 столько раз, какой размерности хотим получить новое пространство.
 === Схема реализации последовательного алгоритма ===
+[https://wmpics.pics/di-2ZK0.png Блок схема алгоритма]
 === Последовательная сложность алгоритма ===