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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сингулярная декомпозиция (SVD)

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

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

Алгоритм разложения матрицы с помощью SVD:

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

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

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

Алгоритм вычисления главных компонент:

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

Обратите внимание, что значения во входном наборе данных D должны быть стандартизированы.

Литература

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