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

Автор: Девбунова Вилиана Олеговна, студент ММП ВМК МГУ (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 Алгоритм вычисления собственных значений метод степенных итераций

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

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

Будем искать подпространство меньшей размерности, в ортогональной проекции на которые среднеквадратичное расстояние между точками максимально. Будем использовать жадную стратегию: Будем подбирать единичные вектора $E_i$, такие что норма проекций на этот вектор будет максимальна.

• 1.$||M E_1||^2 → max_{E_1}$
• 2. $|M E_2||^2 → max_{E_2}$ и $E_1$ ортогонален $E_2$
• 3. и т.д.

Запишем задачу Лагранжа: $\frac{d}{dE_1}(E_1^TM^TME_1 - \lambda(E_1^TE_1 -1) = 0$

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

Алгоритм:

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

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

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

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

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

• 1. Вычислить $M^T$ из матрицы $M$.
• 2. Вычислить умножение $M^TM$
• 3. В цикле до сходимости вычислять:

$E_{k+1} = \frac{M^TME_k}{\|M^TME_k\|}$ -- сойдется к собственному вектору, отвечающему максимальному значению, тогда последовательность $\lambda_{k} = \frac{(E_k,M^TME_k)}{(E_k,E_k)}$ сойдется к максимальному собственному значению.

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

$M^TM - \lambda_k E_k E_k^T$

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

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

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

3 Литература

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