Relación entre SVD y PCA. ¿Cómo usar SVD para realizar PCA?

352

El análisis de componentes principales (PCA) generalmente se explica a través de una descomposición propia de la matriz de covarianza. Sin embargo, también se puede realizar a través de descomposición en valores singulares (SVD) de la matriz de datos . ¿Como funciona? ¿Cuál es la conexión entre estos dos enfoques? ¿Cuál es la relación entre SVD y PCA?X

O, en otras palabras, ¿cómo usar SVD de la matriz de datos para realizar la reducción de dimensionalidad?

ameba
fuente
8
Escribí esta pregunta de estilo de preguntas frecuentes junto con mi propia respuesta, porque con frecuencia se hace de varias formas, pero no hay un hilo canónico y, por lo tanto, es difícil cerrar los duplicados. Proporcione meta comentarios en este meta thread adjunto .
ameba
2
Además de una excelente y detallada respuesta de la ameba con sus enlaces adicionales, podría recomendar comprobar esto , donde PCA se considera junto a otras técnicas basadas en SVD. La discusión allí presenta álgebra casi idéntica a la de la ameba con una pequeña diferencia de que el discurso allí, al describir PCA, trata sobre la descomposición svd de [o ] en lugar de , que es simplemente conveniente ya que se relaciona con el PCA realizado a través de la descomposición propia de la matriz de covarianza. X/X/n XX/n1X
ttnphns
PCA es un caso especial de SVD. PCA necesita los datos normalizados, idealmente la misma unidad. La matriz es nxn en PCA.
Orvar Korvar
@OrvarKorvar: ¿De qué matriz nxn estás hablando?
Cbhihe

Respuestas:

412

Deje que la matriz de datos tenga un tamaño , donde es el número de muestras y es el número de variables. Supongamos que está centrado , es decir, las medias de columna se han restado y ahora son iguales a cero. n × p n pXn×pnp

Entonces la matriz de covarianza viene dada por . Es una matriz simétrica y, por lo tanto, se puede diagonalizar: donde es una matriz de vectores propios (cada columna es un vector propio) y es una matriz diagonal con valores propios en orden decreciente en la diagonal. Los vectores propios se denominan ejes principales o direcciones principales de los datos. Las proyecciones de los datos en los ejes principales se denominan componentes principales , también conocidos como puntajes de PCC C = XX / ( n - 1 ) C = V L V , V L λ i j j X V i i X Vp×pCC=XX/(n1)

C=VLV,
VLλi; Estos pueden ser vistos como variables nuevas y transformadas. El -ésimo componente principal viene dado por la -ésima columna de . Las coordenadas del punto de datos -ésimo en el nuevo espacio de PC están dadas por la fila -ésima de .jjXViiXV

Si ahora realizamos una descomposición de valores singulares de , obtenemos una descomposición donde es una matriz unitaria y es la matriz diagonal de valores singulares . Desde aquí se puede ver fácilmente que lo que significa que los vectores singulares derechos son direcciones principales y que los valores singulares están relacionados con los valores propios de la matriz de covarianza a través de . Los componentes principales están dados porX = U S V , U S s i C = V S UU S V/ ( n - 1 ) = V S 2X

X=USV,
USsiVλi=s 2 i /(n-1)XV=USVV=US
C=VSUUSV/(n1)=VS2n1V,
Vλi=si2/(n1)XV=USVV=US .

Para resumir:

  1. Si , entonces las columnas de son direcciones / ejes principales.X=USVV
  2. Las columnas de son componentes principales ("puntajes").US
  3. Los valores singulares están relacionados con los valores propios de la matriz de covarianza a través de . Los valores propios muestran las variaciones de las PC respectivas.λi=si2/(n1)λi
  4. Los puntajes estandarizados están dados por columnas de y las cargas están dadas por columnas de . Vea, por ejemplo, aquí y aquí por qué las "cargas" no deben confundirse con las instrucciones principales.n1UVS/n1
  5. Lo anterior es correcto solo si está centrado. XSolo entonces la matriz de covarianza es igual a .XX/(n1)
  6. Lo anterior es correcto solo para tiene muestras en filas y variables en columnas. Si las variables están en filas y las muestras en columnas, entonces y intercambian interpretaciones.XUV
  7. Si se desea realizar PCA en una matriz de correlación (en lugar de una matriz de covarianza), entonces las columnas de no solo deben estar centradas, sino también estandarizadas, es decir, divididas por sus desviaciones estándar.X
  8. Para reducir la dimensionalidad de los datos a partir de para , seleccione primeras columnas de , y parte superior izquierda de . Su producto es la matriz requerida que contiene las primeras PC.pk<pkUk×kSUkSkn×kk
  9. Multiplicando aún más las primeras PC por los ejes principales correspondientes produce matrix que tiene la original tamaño pero es de rango inferior (de rango ). Esta matriz proporciona una reconstrucción de los datos originales de las primeras PC. Tiene el error de reconstrucción más bajo posible, vea mi respuesta aquí .kVkXk=UkSkVkn×pkXkk
  10. Estrictamente hablando, es de tamaño y es de tamaño. Sin embargo, si , las últimas columnas de son arbitrarias (y las filas correspondientes de son constantes cero); por lo tanto, se debe usar una SVD de tamaño económico (o delgada ) que devuelva de tamaño, dejando caer las columnas inútiles. Para grandes la matriz sería innecesariamente enorme. Lo mismo se aplica para una situación opuesta deUn×nVp×pn>pnpUSUn×pnpUnp.

Enlaces adicionales

Animación giratoria de PCA

ameba
fuente
55
@Antoine, la matriz de covarianza es, por definición, igual a , donde los corchetes angulares indican el valor promedio . Si todos están apilados como filas en una matriz , entonces esta expresión es igual a . Si está centrado, entonces se simplifica a . Piensa en la varianza; es igual a . Pero si (es decir, los datos están centrados), entonces es simplemente el valor promedio de .x i X ( X - ˉ X ) ( X - ˉ X ) / ( n - 1 ) X(xix¯)(xix¯)xiX(XX¯)(XX¯)/(n1)XXX/(n1)(xix¯)2x¯=0xi2
ameba
2
Una muestra de código para PCA de SVD: stackoverflow.com/questions/3181593/…
optimista el
1
Amoeba, asumí la responsabilidad de agregar un enlace más en línea con los enlaces proporcionados por usted. Espero que lo encuentres apropiado.
ttnphns
2
@amoeba sí, pero ¿por qué usarlo? Además, ¿es posible usar el mismo denominador para ? El problema es que veo fórmulas donde y trato de entender, ¿cómo usarlas? Sλi=si2
Dims
1
@sera Simplemente transponga su matriz y elimine su problema. De lo contrario, solo te confundirás.
ameba
22

Escribí un fragmento de Python & Numpy que acompaña la respuesta de @ ameeba y lo dejo aquí en caso de que sea útil para alguien. Los comentarios se toman principalmente de la respuesta de @ ameeba.

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)
usuario115202
fuente
21

Déjame comenzar con PCA. Suponga que tiene n puntos de datos compuestos de d números (o dimensiones) cada uno. Si centra estos datos (resta el punto medio de datos de cada vector de datos ) puede apilar los datos para hacer una matrizμxi

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

La matriz de covarianza

S=1n1i=1n(xiμ)(xiμ)T=1n1XTX

medidas en qué grado las diferentes coordenadas en las que se proporcionan sus datos varían juntas. Por lo tanto, tal vez no sea sorprendente que PCA, que está diseñado para capturar la variación de sus datos, se pueda dar en términos de la matriz de covarianza. En particular, la descomposición del valor propio de resulta serS

S=VΛVT=i=1rλiviviT,

donde es el -ésimo componente principal , o PC, y es el -ésimo valor propio de y también es igual a la varianza de los datos a lo largo de la -ésima PC. Esta descomposición proviene de un teorema general de álgebra lineal, y algunos trabajos no tienen que hacer para motivar al relatino a PCA.viiλiiSi

PCA de un conjunto de datos gaussiano generado aleatoriamente

SVD es una forma general de entender una matriz en términos de su espacio de columna y espacio de fila. (Es una forma de reescribir cualquier matriz en términos de otras matrices con una relación intuitiva con el espacio de filas y columnas). Por ejemplo, para la matriz podemos encontrar direcciones y en el dominio y rango para queA=(1201)uivi

SVD para un ejemplo 2x2

Puede encontrarlos considerando cómo como transformación lineal transforma una esfera de unidad en su dominio en una elipse: los semiejes principales de la elipse se alinean con y son sus preimágenes.ASuivi

En cualquier caso, para la matriz de datos anterior (realmente, solo configure ), SVD nos permite escribirXA=X

X=i=1rσiuivjT,

donde y son conjuntos de vectores ortonormales. Una comparación con la descomposición del valor propio de revela que los "vectores singulares derechos" son iguales a las PC, los "vectores singulares derechos" son{ v i } S v i{ui}{vi}Svi

ui=1(n1)λiXvi,

y los "valores singulares" están relacionados con la matriz de datos a través deσi

σi2=(n1)λi.

Es un hecho general de que los vectores singulares derecha abarcan todo el espacio de la columna de . En este caso específico, nos da una proyección a escala de los datos en la dirección del -ésimo componente principal. Los vectores singulares izquierdos en general abarcan el espacio de filas de , lo que nos da un conjunto de vectores ortonormales que abarcan los datos de manera muy similar a las PC. X u i X i v i XuiXuiXiviX

Entro en más detalles y beneficios de la relación entre PCA y SVD en este artículo más largo .

Andre P
fuente
Gracias por tu respuesta Andre. Solo dos pequeños errores tipográficos: 1. En el último párrafo estás confundiendo izquierda y derecha. 2. En la fórmula (mayúscula) para X, está utilizando v_j en lugar de v_i.
Alon