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

352

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

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

амеба
источник
8
Я написал этот вопрос в стиле FAQ вместе со своим собственным ответом, потому что он часто задается в различных формах, но нет канонического потока, и поэтому закрытие дубликатов затруднительно. Пожалуйста, предоставьте мета-комментарии в этой мета-ветке .
амеба
2
В дополнение к превосходному и подробному ответу амебы с его дальнейшими ссылками, я мог бы рекомендовать проверить это , где PCA считается рядом с некоторыми другими методами, основанными на SVD. Здесь обсуждается алгебра, почти идентичная амебе, с небольшим отличием в том, что речь, описывающая PCA, идет о svd-разложении [илиX/Икс/N ] вместо X- что просто удобно, поскольку оно связано с PCA, выполняемым посредством собственного разложения ковариационной матрицы. Икс/N-1Икс
ttnphns
СПС является частным случаем СВД. PCA нужны нормализованные данные, в идеале это же устройство. Матрица nxn в PCA.
Орвар Корвар
@OrvarKorvar: О какой матрице nxn вы говорите?
Cbhihe

Ответы:

412

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

Тогда ковариационная матрица C задается как C = XX / ( n - 1 ) . Это симметричная матрица, поэтому она может быть диагонализирована: C = V L V , где V - матрица собственных векторов (каждый столбец - собственный вектор), а L - диагональная матрица с собственными значениями λ i в порядке убывания на диагонали. , Собственные векторы называются главными осями или главными направлениями.п×пССзнак равноИксИкс/(N-1)

Сзнак равноВLВ,
ВLλяданных. Проекции данных по основным осям называются главными компонентами , также известными как оценки ПК ; их можно рассматривать как новые, преобразованные переменные. -го основного компонента задается J -го столбца X V . Координаты я -й точка данных в новом пространстве ПК задаются я -й строкой X V .JJИксВяяИксВ

Если мы теперь выполним разложение сингулярным значениям , мы получим разложение X = U S V , где U - унитарная матрица, а S - диагональная матрица особых значений s i . Отсюда легко увидеть, что C = V S UU S V/ ( n - 1 ) = V S 2Икс

Иксзнак равноUSВ,
USsячто означает, что правые сингулярные векторыVявляются главными направлениями и что сингулярные значения связаны с собственными значениями ковариационной матрицы черезλi=s 2 i /(n-1). Основные компоненты задаютсяXV=USVV=US.
Сзнак равноВSUUSВ/(N-1)знак равноВS2N-1В,
Вλязнак равноsя2/(N-1)ИксВзнак равноUSВВзнак равноUS

Обобщить:

  1. Если , то столбцы V являются главными направлениями / осями.Иксзнак равноUSВВ
  2. Столбцы являются основными компонентами («баллы»).US
  3. Сингулярные значения связаны с собственными значениями ковариационной матрицы через . Собственные значения λ i показывают дисперсии соответствующих ПК.λязнак равноsя2/(N-1)λя
  4. Стандартизированные оценки даны столбцами и нагрузки даны столбцамиVS/N-1U . Смотрите, например,здесьиздесь,почему «нагрузки» не следует путать с основными направлениями.ВS/N-1
  5. Вышеприведенное верно только в том случае, если центрирован. ИксТолько тогда ковариационная матрица равна .ИксИкс/(N-1)
  6. Вышеприведенное верно только для имеющих выборки в строках и переменные в столбцах. Если переменные находятся в строках, а выборки в столбцах, то U и V обмениваются интерпретациями.ИксUВ
  7. Если кто-то хочет выполнить PCA на корреляционной матрице (вместо ковариационной матрицы), то столбцы должны быть не только центрированы, но и стандартизированы, то есть разделены на их стандартные отклонения.Икс
  8. Чтобы уменьшить размерность данных от до K < р , выберите K первые столбцы U и K × K верхняя левая часть S . Их произведение U k S k является требуемой матрицей n × k, содержащей первые k ПК.пК<пКUК×КSUКSКN×КК
  9. Кроме умножение первого ПК с помощью соответствующих главных осей V к дает Й к = U к S к V к матрице , которая имеет оригинальный п × р размера , но более низкий ранг (ранг к ). Эта матрица X k обеспечивает реконструкцию исходных данных с первых k ПК. У этого есть самая низкая возможная ошибка реконструкции, см. Мой ответ здесь .КВКИксКзнак равноUКSКВКN×пКИксКК
  10. Строго говоря, имеет размер n × n, а V имеет размер p × p . Однако, если n > p, то последние n - p столбцов U произвольны (и соответствующие строки S имеют постоянный ноль); Поэтому следует использовать размер экономики (или тонкий ) СВД , который возвращает U из п × р размера, опуская бесполезные колонны. При больших n p матрица UUN×NВп×пN>пN-пUSUN×пN»пUв противном случае было бы излишне огромным. То же самое относится к противоположной ситуации .N«п

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

Вращающаяся анимация PCA

амеба
источник
5
(xix¯)(xix¯)xяИкс(XX¯)(XX¯)/(N-1)ИксИксИкс/(N-1)(Икся-Икс¯)2Икс¯знак равно0Икся2
2
Пример кода для PCA от SVD: stackoverflow.com/questions/3181593/…
оптимист
1
Amoeba, я взял на себя ответственность добавить еще одну ссылку в соответствии с предоставленными вами ссылками. Надеюсь, вы найдете это уместным.
ttnphns
2
@amoeba да, но зачем это использовать? Кроме того, возможно ли использовать один и тот же знаменатель для ? Проблема в том, что я вижу формулы, где λ i = s 2 i, и пытаюсь понять, как их использовать? Sλязнак равноsя2
Димс
1
@sera Просто перенеси свою матрицу и избавься от своей проблемы. В противном случае вы только запутаетесь.
амеба
22

Я написал фрагмент 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
источник
21

μИкся

X=(x1TμTx2TμTxnTμT),

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

Sзнак равно1N-1Σязнак равно1N(Икся-μ)(Икся-μ)Tзнак равно1N-1ИксTИкс

S

Sзнак равноВΛВTзнак равноΣязнак равно1рλяvяvяT,

vяяλяяSя

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

Aзнак равно(1201)Uяvя

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

ASUяvя

ИксAзнак равноИкс

Иксзнак равноΣязнак равно1рσяUяvJT,

{Uя}{vя}Svя

Uязнак равно1(N-1)λяИксvя,

σя

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

UяИксUяИксяvяИкс

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

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