Отношения между СВД и СПС. Как использовать SVD для выполнения PCA?

352

Анализ главных компонент (PCA) обычно объясняется с помощью собственного разложения ковариационной матрицы. Тем не менее, он также может быть выполнен с помощью сингулярного разложения (SVD) матриц данных $\mathbf X$ . Как это работает? Какова связь между этими двумя подходами? Какая связь между СВД и СПС?

Или, другими словами, как использовать SVD матрицы данных для уменьшения размерности?

pca dimensionality-reduction matrix svd амеба
источник

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

амеба

stats.stackexchange.com/questions/177102/…

kjetil b halvorsen

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

[или

X / \sqrt{n}

$\mathbf X/\sqrt{n}$

] вместо

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

X / \sqrt{n - 1}

$\mathbf X/\sqrt{n-1}$

X

$\bf X$

ttnphns

СПС является частным случаем СВД. PCA нужны нормализованные данные, в идеале это же устройство. Матрица nxn в PCA.

Орвар Корвар

@OrvarKorvar: О какой матрице nxn вы говорите?

Cbhihe

Ответы:

412

Пусть матрица данных имеет размер , где - количество выборок, а - количество переменных. Предположим, что он центрирован , то есть средние значения столбцов вычтены и теперь равны нулю. $\mathbf X$ $n \times p$ $n$ $p$

Тогда ковариационная матрица задается как . Это симметричная матрица, поэтому она может быть диагонализирована: где - матрица собственных векторов (каждый столбец - собственный вектор), а - диагональная матрица с собственными значениями в порядке убывания на диагонали. , Собственные векторы называются главными осями или главными направлениями. $p \times p$ $\mathbf C$ $\mathbf C = \mathbf X^\top \mathbf X/(n-1)$

С знак равно В L В^{⊤},

$\mathbf C = \mathbf V \mathbf L \mathbf V^\top,$

V

$\mathbf V$

L

$\mathbf L$

λ_{i}

$\lambda_i$ данных. Проекции данных по основным осям называются главными компонентами , также известными как оценки ПК ; их можно рассматривать как новые, преобразованные переменные.

-го основного компонента задается

-го столбца

. Координаты

-й точка данных в новом пространстве ПК задаются

-й строкой

j

$j$

j

$j$

X V

$\mathbf {XV}$

i

$i$

i

$i$

X V

$\mathbf{XV}$

Если мы теперь выполним разложение сингулярным значениям , мы получим разложение где - унитарная матрица, а - диагональная матрица особых значений . Отсюда легко увидеть, что $\mathbf X$

Икс знак равно U S В^{⊤},

$\mathbf X = \mathbf U \mathbf S \mathbf V^\top,$

U

$\mathbf U$

S

$\mathbf S$

s_{i}

$s_i$

что означает, что правые сингулярные векторы

являются главными направлениями и что сингулярные значения связаны с собственными значениями ковариационной матрицы через

. Основные компоненты задаются

С знак равно В S U^{⊤} U S В^{⊤} / (N - 1) знак равно В \frac{S^{2}}{N - 1} В^{⊤},

$\mathbf C = \mathbf V \mathbf S \mathbf U^\top \mathbf U \mathbf S \mathbf V^\top /(n-1) = \mathbf V \frac{\mathbf S^2}{n-1}\mathbf V^\top,$

V

$\mathbf V$

λ_{i} = s_{i}^{2} / (n - 1)

$\lambda_i = s_i^2/(n-1)$

X V = U S V^{⊤} V = U S

$\mathbf X \mathbf V = \mathbf U \mathbf S \mathbf V^\top \mathbf V = \mathbf U \mathbf S$

Обобщить:

Если , то столбцы являются главными направлениями / осями. $\mathbf X = \mathbf U \mathbf S \mathbf V^\top$ $\mathbf V$
Столбцы являются основными компонентами («баллы»). $\mathbf {US}$
Сингулярные значения связаны с собственными значениями ковариационной матрицы через . Собственные значения показывают дисперсии соответствующих ПК. $\lambda_i = s_i^2/(n-1)$ $\lambda_i$
Стандартизированные оценки даны столбцами и нагрузки даны столбцами $\sqrt{n-1}\mathbf U$ . Смотрите, например,здесьиздесь,почему «нагрузки» не следует путать с основными направлениями. $\mathbf V \mathbf S/\sqrt{n-1}$
Вышеприведенное верно только в том случае, если центрирован. $\mathbf X$ Только тогда ковариационная матрица равна . $\mathbf X^\top \mathbf X/(n-1)$
Вышеприведенное верно только для имеющих выборки в строках и переменные в столбцах. Если переменные находятся в строках, а выборки в столбцах, то и обмениваются интерпретациями. $\mathbf X$ $\mathbf U$ $\mathbf V$
Если кто-то хочет выполнить PCA на корреляционной матрице (вместо ковариационной матрицы), то столбцы должны быть не только центрированы, но и стандартизированы, то есть разделены на их стандартные отклонения. $\mathbf X$
Чтобы уменьшить размерность данных от до , выберите первые столбцы и верхняя левая часть . Их произведение является требуемой матрицей содержащей первые ПК. $p$ $k<p$ $k$ $\mathbf U$ $k\times k$ $\mathbf S$ $\mathbf U_k \mathbf S_k$ $n \times k$ $k$
Кроме умножение первого ПК с помощью соответствующих главных осей дает матрице , которая имеет оригинальный размера , но более низкий ранг (ранг ). Эта матрица обеспечивает реконструкцию исходных данных с первых ПК. У этого есть самая низкая возможная ошибка реконструкции, см. Мой ответ здесь . $k$ $\mathbf V_k^\top$ $\mathbf X_k = \mathbf U_k^\vphantom \top \mathbf S_k^\vphantom \top \mathbf V_k^\top$ $n \times p$ $k$ $\mathbf X_k$ $k$
Строго говоря, имеет размер а имеет размер . Однако, если то последние столбцов произвольны (и соответствующие строки имеют постоянный ноль); Поэтому следует использовать размер экономики (или тонкий ) СВД , который возвращает из размера, опуская бесполезные колонны. При больших матрица $\mathbf U$ $n\times n$ $\mathbf V$ $p \times p$ $n>p$ $n-p$ $\mathbf U$ $\mathbf S$ $\mathbf U$ $n\times p$ $n\gg p$ $\mathbf U$ в противном случае было бы излишне огромным. То же самое относится к противоположной ситуации . $n\ll p$

Дальнейшие ссылки

Что такое интуитивные отношения между SVD и PCA - очень популярной и очень похожей веткой по математике.
Почему PCA данных с помощью SVD данных? - обсуждение преимуществ использования PCA с помощью SVD [короткий ответ: численная стабильность].
PCA и анализ соответствия в их отношении к Biplot - PCA в контексте некоторых родственных методов, основанных на SVD.
Есть ли какое-либо преимущество SVD перед PCA? - вопрос, спрашивающий, есть ли какие-либо преимущества в использовании SVD вместо PCA [краткий ответ: некорректный вопрос].
Осмысление анализа главных компонент, собственных векторов и собственных значений - мой ответ, дающий нетехническое объяснение PCA. Чтобы привлечь внимание, я воспроизвожу здесь одну фигуру:

амеба
источник

⟨ (x_{i} - \bar{x}) (x_{i} - \bar{x})^{⊤} ⟩

$\langle (\mathbf x_i - \bar{\mathbf x})(\mathbf x_i - \bar{\mathbf x})^\top \rangle$

x_{i}

$\mathbf x_i$

X

$\mathbf X$

(X - \bar{X}) (X - \bar{X})^{⊤} / (n - 1)

$(\mathbf X - \bar{\mathbf X})(\mathbf X - \bar{\mathbf X})^\top/(n-1)$

X

$\mathbf X$

X X^{⊤} / (n - 1)

$\mathbf X \mathbf X^\top/(n-1)$

⟨ (x_{i} - \bar{x})^{2} ⟩

$\langle (x_i-\bar x)^2 \rangle$

\bar{x} = 0

$\bar x=0$

x_{i}^{2}

$x_i^2$

Пример кода для PCA от SVD: stackoverflow.com/questions/3181593/…

оптимист

Amoeba, я взял на себя ответственность добавить еще одну ссылку в соответствии с предоставленными вами ссылками. Надеюсь, вы найдете это уместным.

ttnphns

@amoeba да, но зачем это использовать? Кроме того, возможно ли использовать один и тот же знаменатель для

? Проблема в том, что я вижу формулы, где

и пытаюсь понять, как их использовать?

S

$S$

λ_{i} = s_{i}^{2}

$\lambda_i = s_i^2$

Димс

@sera Просто перенеси свою матрицу и избавься от своей проблемы. В противном случае вы только запутаетесь.

амеба

Я написал фрагмент Python & Numpy, сопровождающий ответ @ amoeba, и оставляю его здесь на случай, если он кому-нибудь пригодится. Комментарии в основном взяты из ответа @ amoeba.

import numpy as np
from numpy import linalg as la
np.random.seed(42)


def flip_signs(A, B):
    """
    utility function for resolving the sign ambiguity in SVD
    http://stats.stackexchange.com/q/34396/115202
    """
    signs = np.sign(A) * np.sign(B)
    return A, B * signs


# Let the data matrix X be of n x p size,
# where n is the number of samples and p is the number of variables
n, p = 5, 3
X = np.random.rand(n, p)
# Let us assume that it is centered
X -= np.mean(X, axis=0)

# the p x p covariance matrix
C = np.cov(X, rowvar=False)
print "C = \n", C
# C is a symmetric matrix and so it can be diagonalized:
l, principal_axes = la.eig(C)
# sort results wrt. eigenvalues
idx = l.argsort()[::-1]
l, principal_axes = l[idx], principal_axes[:, idx]
# the eigenvalues in decreasing order
print "l = \n", l
# a matrix of eigenvectors (each column is an eigenvector)
print "V = \n", principal_axes
# projections of X on the principal axes are called principal components
principal_components = X.dot(principal_axes)
print "Y = \n", principal_components

# we now perform singular value decomposition of X
# "economy size" (or "thin") SVD
U, s, Vt = la.svd(X, full_matrices=False)
V = Vt.T
S = np.diag(s)

# 1) then columns of V are principal directions/axes.
assert np.allclose(*flip_signs(V, principal_axes))

# 2) columns of US are principal components
assert np.allclose(*flip_signs(U.dot(S), principal_components))

# 3) singular values are related to the eigenvalues of covariance matrix
assert np.allclose((s ** 2) / (n - 1), l)

# 8) dimensionality reduction
k = 2
PC_k = principal_components[:, 0:k]
US_k = U[:, 0:k].dot(S[0:k, 0:k])
assert np.allclose(*flip_signs(PC_k, US_k))

# 10) we used "economy size" (or "thin") SVD
assert U.shape == (n, p)
assert S.shape == (p, p)
assert V.shape == (p, p)

user115202
источник

$\mu$ $x_i$

X = (\begin{array}{ccccc} x_{1}^{T} - μ^{T} \\ x_{2}^{T} - μ^{T} \\ ⋮ \\ x_{n}^{T} - μ^{T} \end{array}),

$X = \left( \begin{array}{ccccc} && x_1^T - \mu^T && \\ \hline && x_2^T - \mu^T && \\ \hline && \vdots && \\ \hline && x_n^T - \mu^T && \end{array} \right)\,.$

Ковариационная матрица

S знак равно \frac{1}{N - 1} Σ_{я знак равно 1}^{N} ({Икс}_{я} - μ) ({Икс}_{я} - μ)^{T} знак равно \frac{1}{N - 1} {Икс}^{T} Икс

$S = \frac{1}{n-1} \sum_{i=1}^n (x_i-\mu)(x_i-\mu)^T = \frac{1}{n-1} X^T X$

$S$

S знак равно В Λ В^{T} знак равно Σ_{я знак равно 1}^{р} λ_{я} v_{я} v_{я}^{T},

$S = V \Lambda V^T = \sum_{i = 1}^r \lambda_i v_i v_i^T \,,$

$v_i$ $i$ $\lambda_i$ $i$ $S$ $i$

PCA случайно сгенерированного набора данных Гаусса

$A = \left( \begin{array}{cc}1&2\\0&1\end{array} \right)$ $u_i$ $v_i$

SVD для примера 2x2

$A$ $\mathbb S$ $u_i$ $v_i$

$X$ $A = X$

Икс знак равно Σ_{я знак равно 1}^{р} σ_{я} U_{я} v_{J}^{T},

$X = \sum_{i=1}^r \sigma_i u_i v_j^T\,,$

$\{ u_i \}$ $\{ v_i \}$ $S$ $v_i$

U_{я} знак равно \frac{1}{\sqrt{(N - 1) λ_{я}}} Икс v_{я},

$u_i = \frac{1}{\sqrt{(n-1)\lambda_i}} Xv_i\,,$

$\sigma_i$

σ_{я}^{2} знак равно (N - 1) λ_{я},

$\sigma_i^2 = (n-1) \lambda_i\,.$

$u_i$ $X$ $u_i$ $X$ $i$ $v_i$ $X$

В этой длинной статье я расскажу о некоторых деталях и преимуществах отношений между PCA и SVD .

Андре П
источник

Спасибо за ваш ответ, Андре. Всего два небольших исправления опечаток: 1. В последнем абзаце вы путаете левый и правый. 2. В формуле (заглавной) для X вы используете v_j вместо v_i.

Алон