Понимая PCA, как работают алгоритмы понижения размерности данных

Цель данной статьи - дать детальное представление о PCA (Principal Component Analysis) с необходимыми математическими доказательствами.

В задачах, связанных с анализом данных, мы работаем со сложными данными - данными высокой размерности. Мы отрисовываем их и находим различные паттерны или используем их для обучения некоторой модели. Один из способов понять, что такое "размерность" заключается в следующем. Представьте, что у вас есть точка Х, если мы рассматриваем эту точку как физических объект, то размерности - это просто сторона, с которой вы смотрите на нее. Словно отвечаете на вопрос "где точка расположена, когда я смотрю на нее с вертикальной или горизонтальной оси".

С ростом размерности также растут сложность в визуализации и вычислительная сложность. Итак, как как же снизить размерность данных?

• Убрать избыточные измерения

• Сохранить только важные измерения

Для начала введем несколько определений.

Дисперсия - величина показывающая, как размазаны наши данные. Математически, это средний квадрат отклонений от среднего значения по выборке.

где E(t) - математическое ожидание какой-то величины t, а - значение x в i − ом измерении. Ковариация - мера линейной зависимости двух выборок.

Один из способов наблюдения ковариации является то, как взаимосвязаны две выборки (1).

Положительная ковариация означает то, что Х и У положительно взаимосвязаны, т.е. с увеличением Х также увеличивается и У. Отрицательная ковариация изображает в точности противоположную взаимосвязь. Впрочем, нулевая ковариация означает то, что Х и У не связаны вообще.

Теперь давайте подумаем о требованиях анализа данных. Так как мы пытаемся найти паттерны среди множества данных, хотелось бы, чтобы эти данные были распределены по каждому измерению. Также мы хотим, чтобы измерения были независимы.

Таким образом, если данные имеют высокую ковариацию в n-мерном представлении, мы заменяем это представление на линейную комбинацию этих n измерений. Теперь данные будут зависеть от линейной комбинации этих n связанных измерений с высокой ковариацией (зависимые = имеют высокую ковариацию).

Итак, что же делает PCA?

PCA находит множество новых измерений (сторон, с которых можно смотреть на данные), которые ортогональны (таким образом линейно независимы) и отранжированы по величине дисперсии, которую они объясняют. Это значит, что более значимые principal оси будут первыми (более значимые = больше дисперсия/больше разброс в данных).

1) Рассчитать ковариационную матрицу выборки

2) Рассчитать собственные значения и соответствующие собственные вектора

3) Отсортировать собственные вектора по значениям их собственных значений в убывающем порядке

4) Выбрать k первых собственных векторов и это будет новое k-мерное пространство

5) Преобразовать исходные точки из n-мерного пространства в k-мерное

Для понимания деталей работы PCA, вы должны иметь представления о собственных значениях и векторах.

Убедитесь, что вы поняли концепцию собственных значений и векторов перед тем, как пойдете дальше.

[Covariance_matrix] ∗[Eigenvector] = [Eigenvalue] * [Eigenvector]

Предположим, у нас есть знания о дисперсии и ковариации. Давайте взглянем на то, что из себя представляет Covariance_matrix.

Ниже показана ковариационная матрица некоторой величины с 4-мя измерениями: a, b, c, d.

- дисперсия по оси a,

- ковариация между размерностями a и b

Если у нас есть матрица Х размерность n ∗m, где n− число точек, а n− размерность одной точки, тогда ковариационную матрицу можно посчитать как:

Важно заметить, что матрица ковариации содержит

· Дисперсию измерений на главной диагонали

· Ковариацию измерений вне главной диагонали

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

Таким образом, наша ковариационная матрица должна иметь:

1) Большие значения на элементах главной диагонали

2) Нулевые значения на элементах вне главной диагонали. Мы зовем это диагональной матрицей.
Итак, мы должны преобразовать исходные точки так, чтобы их матрица ковариации стала диагональной матрицей. Процесс преобразования матрицы к диагональному виду называется диагонализацией.

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

Это определяет цель PCA:

· Найти линейно независимые измерения, которые могут практически без потерь представлять данные.

· Эти новые измерения должны позволять нам проектировать/реконструировать исходное пространство. Ошибка реконструкции/проекции должна быть минимальной

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

Скажем, что пурпурная линия будет нашей новой размерностью.

Если посмотреть на красные линии (проекция синих точек на пурпурную линию), т.е. перпендикулярное расстояние каждой точки на прямую линию, это и есть ошибка проекции. Сумма ошибок по всем точкам будет являться общей ошибкой проекции.

Новые точки будут проекциями (красные точки) исходных синих точек. Как можно видеть, мы преобразовали точки в двумерном пространстве в одномерное, с помощью проекции этих точек на прямую линию. Эта пурпурная линия называется principal осью. Так как мы проецируем точки на одно измерение, то и principal ось у нас одна.

Выбор прямой линии на втором рисунке намного лучше, т.к.

· Ошибка проецирования меньше, чем в случае с первым рисунком

· Новые точки после проекции лучше распределены, чем в первом случаем (больше дисперсия)

Два пункта, описанные выше, связаны. Если мы будем уменьшать ошибку проецирования, то дисперсия будет расти.

Как?

Теперь мы хотим преобразовать исходное множество точек так, чтобы ковариационная матрица преобразованных точек была диагональной матрицей. Как это сделать?

Вот в чем трюк. Если мы найдем матрицу собственных векторов матрицы и используем ее как матрицу P (P используется для преобразования Х в Y), то матрица (ковариационная матрица преобразованных точек) будет диагональной матрицей. Следовательно, Y будет множеством преобразованных точек.

Теперь, если мы ходит преобразовать точки к k-мерному пространству, мы выбираем k первых собственных векторов матрицы (отсортированных по собственных значениями в убывающем порядке) и формируем матрицу P.

Теорема2:

Теорема 3: Пусть А будет вещественной симметричной матрицей размерностью n ∗n и все собственные значения матрицы А будут различны. Тогда существует ортогональная матрица , где D - диагональная матрица, у которой диагональные элементы равны собственным значениям матрицы А.

Доказательство:

Пусть A имеет следующие собственные значения с таким, что и 1 ≤ i ≤ n.

Следовательно, матрица обратима и диагональна с диагональными вхождениями из матрицы А. Тем более, основываясь на теореме 2, ортогональное множество. Следовательно, Р - ортогональная матрица.

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

Теорема 3: Пусть А будет вещественной симметричной матрицей размерностью n ∗n и все собственные значения матрицы А будут различны. Тогда существует ортогональная матрица , где D - диагональная матрица, у которой диагональные элементы равны собственным значениям матрицы А.

Доказательство:

Пусть A имеет следующие собственные значения с таким, что и 1 ≤ i ≤ n.

Следовательно, матрица обратима и диагональна с диагональными вхождениями из матрицы А. Тем более, основываясь на теореме 2, ортогональное множество. Следовательно, Р - ортогональная матрица.

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

Очевидно, что выбор Р диагонализирует . Это главная идея метода PCA. Мы можем обобщить результаты работы PCA в матрицы Р и Cy:

· Principal компоненты матрицы X - это собственные вектора матрицы Cx

· i-ое диагональное значение матрицы - дисперсия матрицы X вдоль pi.

Заключение.

[new data]k∗n= [top k eigenvectors]k∗m[original data]m∗n

В следующем посте мы реализуем PCA на питоне и используем для цветовой аугментации данных.

Заметка.

РСА - аналитический подход. Мы можете делать PCA, используя SVD, или вы можете делать РСА через декомпозицию по собственным векторам (как мы делали в этом посте), или вы можете делать РСА другими методами. SVD всего лишь еще один численный метод. Поэтому не впадайте в ступор при терминах РСА и SVD. Тем не менее, существуют некоторые факторы в производительности, говорящие в пользу SVD, а не декомпозиции по собственным векторам или другим методам. Мы исследуем SVD в следующих постах.