Principal Component Analysis (PCA) ⚙️

PCA — алгоритм, уменьшающий пространство признаков так, чтобы потерять как можно меньше информации. Его часто спрашивали на собеседованиях, и, когда я впервые его изучил, то получил удовольствие от такого изящного применения линейной алгебры. Давайте же начнём разбор 🧑‍💻

Найти новые ортогональные оси (главные компоненты), вдоль которых дисперсия данных максимальна, и проецировать данные на первые k таких осей.

1) Нормирование.

Приводим признаки к сопоставимым шкалам. Иначе признаки с большими числовыми масштабами доминируют по дисперсии. Например, зарплата — в тысячах рублей, а рост — в десятках сантиметров, из-за этого и дисперсии будут несравнимы.

2) Центрирование.

Вычитаем среднее по каждому признаку. Нам важен разброс вокруг среднего, а не само значение среднего.

3) Строим ковариационную матрицу Σ.

Данная матрица показывает, как каждый из признаков меняется с другим.

4) Находим собственные векторы и собственные значения.

То есть решаем уравнение Σ v = λ v.

Почему именно собственные вектора, а не другие?

Мы решаем задачу max var(X, w), где:

То есть нам нужно, чтобы дисперсия (var) данных X по направлению вектора w была максимальной. Если раскрыть, чему равна var(X, w), то получим w.T Σ w, при условии, что норма w равна 1. А по принципу максимизации отношения Релея мы знаем, что данное выражение максимально, когда w — собственный вектор с максимальным собственным значением.

Таким образом в уравнении Σv=λv можно сказать, что:

5) Собираем матрицу W.

Данная матрица состоит из k собственных векторов с наибольшими собственными значениями.

6) Проецируем данные на новые оси.

Z = X W.

Теперь, если X была размерности n x d, а W имела размерность d x k, то Z будет иметь размерность n x k. Таким образом, мы и получим наши новые k признаков.

Полезным показателем является "объясняемая дисперсия", которую можно рассчитать на основе собственных значений. Объясняемая дисперсия показывает, какой объём информации (дисперсии) можно отнести к каждой из главных компонент. Ниже будет график, на котором видно, что большую часть дисперсии (~73% + ~23%) можно объяснить первыми двумя главными компонентами, а остальные два можно отбросить.

Подробнее можно почитать тут и тут.

Алгоритм довольно прост, поэтому у него есть много недостатков. На практике сейчас больше пользуются алгоритмом UMAP. Очень крутая страничка, на которой можно визуально посмотреть на него находится тут.

Надеюсь, что всё было понятно. Всем удачи! 🏆
Присоединяйтесь к нам в Telegram.