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

Использование двух разных стратегий, основанных на линейной алгебре, для понимания самой важной формулы уменьшения размерности

Предполагается, что читатель знаком с содержанием любого вводного курса линейной алгебры - ортогональность, собственное разложение, спектральная теорема, разложение по сингулярным значениям (SVD)…

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

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

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

Цель анализа главных компонентов

Важно сначала иметь смутное представление о том, чего пытается достичь PCA.

Он пытается уменьшить размерность входных данных. Но что это значит? Возьмем конкретный пример. Допустим, у нас есть две примерно взаимосвязанные характеристики, собранные в результате массового опроса канадских граждан: личное счастье и личные достижения.

Как мы видим, эти две характеристики тесно взаимосвязаны - люди с высокими личными достижениями, скорее всего, будут счастливее, и наоборот.

Предположим, что эти две функции - всего лишь сегмент гораздо большего набора данных с множеством, гораздо большим количеством функций (x3, x4… xn), связанных с ответами на разные вопросы в опросе. Допустим, у нас так много данных, что наша технология анализа данных начинает давать сбои, и мы хотим увидеть способы уменьшения размера нашего набора данных.

Просматривая графики всевозможных вопросов, мы видим, что личное счастье и личные достижения сильно взаимосвязаны. Мы могли бы сэкономить много места, если бы могли объединить эти две функции в одну функцию, что-то вроде «личного удовлетворения».

Это проблема «уменьшения размерности», идеально подходящая для анализа главных компонентов. Мы хотим проанализировать данные и прийти к основным компонентам - их объединению.

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

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

Это уменьшение размерности принесет в жертву некоторую информацию, но мы пытаемся найти линию, которая минимизирует потерю информации.

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

Мы видим, что при низкой дисперсии мы стираем большую часть наиболее важных данных, а сокращенный набор данных почти не напоминает наши 2D-данные.

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

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

* Все это применимо в более высоких измерениях, когда мы хотим уменьшить некоторое n-мерное пространство данных до некоторого k-мерного пространства данных, в котором вместо построения оптимальной линии мы строим оптимальную k-мерную гиперплоскость через n- пространственное пространство.

Во-первых, я займусь алгоритмом PCA без каких-либо концепций разложения по сингулярным значениям (SVD) и буду рассматривать его «с точки зрения собственных векторов».

Собственные векторы метода ковариационных матриц

Это, пожалуй, наиболее распространенный метод вычисления PCA, поэтому сначала я начну с него. Он основан на нескольких концепциях статистики, а именно на ковариационной матрице . Но сначала нам нужно установить формат наших входных данных.

Прежде всего, продолжая наш пример опроса, мы опросили 100 участников. У каждого из этих участников есть записанный ответ на вопросы анкеты "счастье" и "достижения".

Мы представляем это как входную матрицу X, которая имеет размер 100 x 2. Каждая строка представляет собой новый пример тренировки (индивидуальный), а каждый столбец - это счастье и достижения этого человека (x1) и достижения (x2).

Матрица ковариации

Что мы хотим сделать, так это построить матрицу ковариации 2 x 2, которая представляет ковариацию между каждой переменной. Я скоро объясню, почему мы ищем ковариационную матрицу. Но сначала давайте исследуем. В псевдоматематике ковариационная матрица выглядит примерно так:

Ковариация измеряет дисперсию между различными переменными. Отрицательная ковариация между некоторыми переменными a и b означает, что когда a увеличивается, b уменьшается. Положительная ковариация означает, что, когда a растет, растет и b.

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

И наши недиагональные ковариации такие же - ковариация между a и b такая же, как ковариация между b и a. (порядок не имеет значения).

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

Наша ковариационная матрица и все ковариационные матрицы симметричны, с дисперсиями по диагонали. Ковариацию можно рассматривать как диагональную дисперсию, если это хоть как-то помогает. Ковариация дает подробную информацию о ориентации данных, а дисперсия дает подробную информацию о среднем расстоянии от среднего.

Построение ковариационной матрицы.

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

Имея в виду точную формулу для расчета ковариации двух функций (каждая с N примерами):

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

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

Это оставляет нам модифицированный, «нормализованный» X, где среднее значение по всем столбцам (примеры) равно 0. В наборах данных с функциями, которые различаются по значениям (возраст, дни недели, деньги на сберегательном счете), мы также можем хотите разделить каждый столбец на стандартное отклонение столбца, но так как оба наших данных - от 1 до 10, нам не нужно этого делать.

Теперь, чтобы вычислить нашу ковариационную матрицу, мы можем просто умножить транспонирование нашей нормализованной матрицы Xnorm.

Выполняя матричное умножение построчно, мы видим, что точно вычисляем нашу ковариационную формулу для каждой из четырех записей в нашем выходном сигнале 2 x 2. Помните, что суммирование в точности равно скалярному произведению, и все встанет на свои места.

Все, что нам не хватает, - это разделить каждое суммирование ковариаций на количество примеров N, и мы можем сделать это, разделив наши выходные данные 2 x 2 на N. Итак, общая формула для любой ковариационной матрицы (и это работает для любого количества измерений!): выглядит следующим образом:

Никогда не перестает удивлять, насколько матричная запись может помочь упростить сложные формулы. Представьте, что вам нужно написать формулу матрицы свертки с помощью суммирования!

Собственные векторы матрицы ковариации и спектральной теоремы

Эта интуиция была вдохновлена ​​пользователем Amoeba на перекрестной проверке.

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

Наш «главный компонент» или вектор в 2D-пространстве, который максимизирует дисперсию всех проецируемых на него точек, является собственным вектором ковариационной матрицы, связанной с наибольшим собственным значением.

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

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

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

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

Чтобы сделать это конкретным, давайте создадим ковариационную матрицу C с конкретными значениями. Продолжим наш пример проблемы достижения счастья.

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

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

Теперь давайте посмотрим, можем ли мы переключиться на eigenbasis -, чтобы наши два собственных вектора стали нашими базисными векторами - наши (1, 0) = (0.83, 0.55) и (0, 1) = (- 0,55, 0,83). Мы можем построить эти базисные векторы на графике в декартовом пространстве координат и увидеть, что они действительно ортогональны и имеют единичную длину - точно так же, как наши нормальные единичные векторы, но повернутые.

Но теперь важно отметить, что мы собираемся использовать систему координат eigenbasis, где are (1, 0) фактически эквивалентны векторам, указанным выше в декартовой системе.

Итак, теперь, предполагая систему координат собственного базиса, как мы можем выразить нашу матрицу C? Что ж, вспоминая критическое и окончательное правило собственных векторов и собственных значений:

В первом примере мы можем просто подставить то, что мы знаем, в эту формулу для собственных значений и посмотреть, каким должно быть C, с помощью простого вывода, и мы можем прийти к выводу, что:

Мы на последнем этапе интуиции. Ключевым моментом сейчас является по-прежнему думать об этом C с точки зрения нашего нового собственного базиса как о ковариационной матрице.

Тот факт, что недиагонали равны нулю (и всегда будут равны 0 в матрице любого размера), означает, что в этом пространстве, где нет корреляции между двумя функциями (в среднем). В этом есть смысл:

Вы можете видеть, что с точки зрения собственного базиса, похоже, нет никакой корреляции (ковариации) между x1 и x2 в пространстве собственного базиса - это примерно похоже на гауссовский шум. Все, что мы получаем наверняка, - это наши дисперсии (теперь дисперсии по нашим новым осям, собственные векторы), которые теперь равны нашим собственным значениям.

Но вот что интересно: глядя на нашу новую матрицу ковариаций (которую вы можете рассматривать как просто матрицу ковариаций с «точки зрения» собственных векторов, как в составном изображении), мы замечаем, что максимальная дисперсия может быть достигнута, когда проецируется по оси x1.

Причина, по которой мы проецируем на некоторый вектор, заключается в том, что теперь, когда у нас есть ковариационная матрица без каких-либо ковариаций, мы можем строго измерить дисперсию в «диагональной» части наших данных. Мы можем относиться к этому так, как если бы мы находимся на одномерной линии, и беспокоиться только о дисперсии. Тот факт, что ковариации равны нулю, гарантирует, что мы не сможем добиться дополнительной дисперсии, сдвинув линию немного вверх или вниз.

Конечно, когда мы конвертируем вектор «ось x1» в нашем мире на основе собственных значений обратно в декартову плоскость, мы помним, что это просто собственный вектор x1.

Итак, x1 - это линия, которая максимизирует дисперсию. Возвращаясь к нашей формулировке правила в начале интуиции, x1 действительно является собственным вектором, связанным с наибольшим собственным значением.

Этот x1 является главным компонентом.

Если бы мы были в нескольких измерениях, с несколькими ортогональными собственными значениями, указывающими в разных направлениях, и хотели бы получить наиболее важные k функций из m функций, мы бы взяли собственные векторы, связанные с k наибольших собственных значений.

Теперь, когда мы понимаем, почему собственные векторы, связанные с наибольшими собственными значениями, являются главными компонентами, мы можем отступить и вспомнить, что все, что мы делаем, это находим собственные значения и собственные векторы ковариационной матрицы (X транспонирует X) / N

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

Обратите внимание: если вы просто хотели пойти в одну сторону и довольны этим, не стесняйтесь взять отпуск прямо сейчас! Это только для людей, которые запутались в двух разных представлениях SVD.

PCA с разложением по сингулярным значениям (SVD)

Это для людей, которые были знакомы с идеей SVD раньше и хорошо знакомы - я не буду тратить время на основы, поскольку эта статья уже довольно длинная. Я очень рекомендую эту лекцию, так как она очень хорошо связана с PCA. Кроме того, это Гилберт Стрэнг, так что вы действительно не ошибетесь.

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

Проведя несколько быстрых вычислений, мы поймем, почему SVD часто вызывается в коде для определения PCA. Они могут показаться случайными, но вскоре они обретут смысл.

Давайте умножим транспонированную А на себя, подставив определение SVD.

Мы видим, что этот окончательный результат справа полностью имитирует формат диагонализации матрицы . Это означает, что D - это собственные значения транспонированной A, а V - собственные векторы.

И обратите внимание на более важный факт - A может быть любым вектором. Это включает наш вектор данных X в начале этой статьи. Помните, что X транспонировал X на N для ковариационной матрицы? Итак, вычисление SVD автоматически вычисляет собственные векторы и собственные значения ковариационной матрицы.

Все, что нам не хватает, - это часть «более N», которую можно рассматривать как умножение ковариационной матрицы на скаляр 1 / N. Скаляры, умножающие матрицу, пропорционально изменяют собственные значения интересующей матрицы, поэтому все будет таким же, за исключением того, что наши собственные значения теперь все делятся на N.

Вот почему люди используют SVD для PCA.

Эккарт-Янг-Мирский и PCA

У этого подхода к СВД есть немного больше нюансов, но я не буду вдаваться в подробности. Это требует глубокого изучения теоремы Эккарта-Юнга-Мирского, которая включает разбиение SVD на компоненты первого ранга.

Напоминает подход собственных значений, вы можете найти некоторые связи. Я снова порекомендую лекцию Гилберта Стрэнга, поскольку это практически единственное обширное видео, подробно освещающее теорему Эккарта-Юнга-Мирского.

Вот и все, спасибо, что остались, и я надеюсь, что вы кое-что узнали. Я пойду спать, так как школьный вечер 5:02, ура.

Адам Дхалла - ученик средней школы из Ванкувера, Британская Колумбия. Он увлечен миром активного отдыха и в настоящее время изучает новейшие технологии в экологических целях. Посетите его веб-сайт adamdhalla.com.

Следите за его I nstagram и его LinkedIn. Чтобы получить больше похожего контента, подпишитесь на его информационный бюллетень здесь.