Hubungan antara SVD dan PCA. Bagaimana cara menggunakan SVD untuk melakukan PCA?

352

Analisis komponen utama (PCA) biasanya dijelaskan melalui dekomposisi eigen dari matriks kovarians. Namun, dapat juga dilakukan melalui dekomposisi nilai singular (SVD) dari data matriks . Bagaimana cara kerjanya? Apa hubungan antara kedua pendekatan ini? Apa hubungan antara SVD dan PCA?X

Atau dengan kata lain, bagaimana cara menggunakan SVD dari matriks data untuk melakukan pengurangan dimensionalitas?

amuba
sumber
8
Saya menulis pertanyaan gaya-FAQ ini bersama dengan jawaban saya sendiri, karena sering ditanyakan dalam berbagai bentuk, tetapi tidak ada utas kanonik dan karenanya duplikat penutupan sulit. Berikan komentar meta di utas meta yang menyertainya ini .
amoeba
2
Selain jawaban amuba yang bagus dan terperinci dengan tautan lebih lanjutnya, saya mungkin merekomendasikan untuk memeriksa ini , di mana PCA dianggap berdampingan dengan beberapa teknik berbasis SVD lainnya. Diskusi di sana menyajikan aljabar yang hampir identik dengan amoeba dengan hanya sedikit perbedaan bahwa pidato di sana, dalam menggambarkan PCA, membahas tentang dekomposisi svd dari [atau ] bukannya - yang cukup mudah karena berkaitan dengan PCA yang dilakukan melalui komposisi eigend dari matriks kovarians. X/X/n XX/n-1X
ttnphns
PCA adalah kasus khusus SVD. PCA membutuhkan data yang dinormalisasi, unit yang idealnya sama. Matriksnya adalah nxn dalam PCA.
Orvar Korvar
@OrvarKorvar: Matriks nxn apa yang Anda bicarakan?
Cbhihe

Jawaban:

412

Biarkan matriks data berukuran n × p , di mana n adalah jumlah sampel dan p adalah jumlah variabel. Mari kita asumsikan bahwa itu berpusat , artinya kolom telah dikurangi dan sekarang sama dengan nol.Xn×halnhal

Kemudian kovarians matriks C diberikan oleh C = XX / ( n - 1 ) . Ini adalah matriks simetris dan sehingga dapat didiagonalisasi: C = V L V , di mana V adalah matriks vektor eigen (setiap kolom adalah vektor eigen) dan L adalah matriks diagonal dengan nilai eigen λ i dalam urutan menurun di diagonal . Vektor eigen disebut sumbu utama atau arah utamahal×halCC=XX/(n-1)

C=VL.V,
VL.λsayadari data. Proyeksi data pada sumbu utama disebut komponen utama , juga dikenal sebagai skor PC ; ini dapat dilihat sebagai variabel baru, yang ditransformasikan. The -th komponen utama diberikan oleh j th kolom X V . Koordinat i -th data titik dalam ruang PC baru diberikan oleh i baris -th X V .jjXVsayasayaXV

Jika sekarang kita melakukan dekomposisi nilai singular , kita memperoleh dekomposisi X = U S V , di mana U adalah matriks kesatuan dan S adalah matriks diagonal dari nilai singular s i . Dari sini orang dapat dengan mudah melihat bahwa C = V S UU S V/ ( n - 1 ) = V S 2X

X=USV,
USssayaartinya vektor singular kananVadalah arah utama dan bahwa nilai singular terkait dengan nilai eigen dari matriks kovarians melaluiλi=s 2 i /(n-1). Komponen utama yang diberikan olehXV=USVV=US.
C=VSUUSV/(n-1)=VS2n-1V,
Vλsaya=ssaya2/(n-1)XV=USVV=US

Untuk meringkas:

  1. Jika , maka kolom V adalah arah / sumbu utama.X=USVV
  2. Kolom merupakan komponen utama ( "skor").US
  3. Nilai singular terkait dengan nilai eigen dari matriks kovarians melalui . Nilai Eigen λ saya menunjukkan varian PC masing-masing.λsaya=ssaya2/(n-1)λsaya
  4. Skor standar yang diberikan oleh kolom dan pembebanan diberikan oleh kolomVS/n-1U . Lihat misalnya disinidan disiniuntuk alasan "memuat" tidak boleh dikacaukan dengan petunjuk utama.VS/n-1
  5. Di atas benar hanya jika berpusat. XHanya kemudian adalah matriks kovarians sama dengan .XX/(n-1)
  6. Di atas hanya benar untuk memiliki sampel dalam baris dan variabel dalam kolom. Jika variabel dalam baris dan sampel dalam kolom, maka dan bertukar interpretasi.U VXUV
  7. Jika seseorang ingin melakukan PCA pada matriks korelasi (bukan matriks kovarians), maka kolom tidak hanya dipusatkan, tetapi distandarisasi juga, yaitu dibagi dengan standar deviasi mereka.X
  8. Untuk mengurangi dimensi dari data dari ke , pilih kolom pertama dari , dan bagian kiri atas . Produk mereka adalah matriks mengandung PC pertama .k < p k U k × k S U k S k n × k khalk<halkUk×kSUkSkn×kk
  9. Selanjutnya mengalikan PC pertama dengan sumbu utama yang sesuai hasil matriks yang memiliki asli ukuran tetapi peringkat lebih rendah (peringkat ). Matriks ini menyediakan rekonstruksi data asli dari PC pertama . Ini memiliki kesalahan rekonstruksi serendah mungkin, lihat jawaban saya di sini .V k X k = U k S k V k n × p k X k kkVkXk=UkSkVkn×halkXkk
  10. Tegasnya, adalah n × n ukuran dan V adalah p × p ukuran. Namun, jika n > p maka kolom n - p terakhir dari U adalah arbitrer (dan baris S yang terkait adalah nol konstan); karena itu kita harus menggunakan ukuran ekonomi (atau tipis ) SVD yang mengembalikan U dari ukuran n × p , menjatuhkan kolom yang tidak berguna. Untuk n p besar , matriks UUn×nVhal×haln>haln-halUSUn×halnhalUjika tidak akan menjadi besar tidak perlu. Hal yang sama berlaku untuk situasi yang berlawanan dari .nhal

Tautan lebih lanjut

Memutar animasi PCA

amuba
sumber
5
@Antoine, kovarians matriks adalah dengan definisi sama dengan , di mana kurung sudut menunjukkan nilai rata-rata. Jika semua x i ditumpuk sebagai baris dalam satu matriks X , maka ungkapan ini sama dengan ( X - ˉ X ) ( X - ˉ X ) / ( n - 1 ) . Jika X dipusatkan maka disederhanakan menjadi(xsaya-x¯)(xsaya-x¯)xsayaX(X-X¯)(X-X¯)/(n-1)X . Pikirkan varian; itu sama dengan( x i - ˉ x ) 2 . Tetapi jika ˉ x = 0 (yaitu data terpusat), maka itu hanyalah nilai rata-rata x 2 i . XX/(n-1)(xsaya-x¯)2x¯=0xsaya2
amoeba
2
Contoh kode untuk PCA oleh SVD: stackoverflow.com/questions/3181593/…
optimist
1
Amoeba, saya bertanggung jawab untuk menambahkan satu lagi tautan sesuai dengan tautan yang Anda berikan. Semoga Anda merasa cocok.
ttnphns
2
@amoeba ya, tapi mengapa menggunakannya? Juga, mungkinkah menggunakan penyebut yang sama untuk ? Masalahnya adalah saya melihat rumus di mana λ i = s 2 i dan mencoba memahami, bagaimana menggunakannya? Sλsaya=ssaya2
Dims
1
@sera Hanya transpos matriks Anda dan singkirkan masalah Anda. Anda hanya akan bingung sebaliknya.
amoeba
22

Saya menulis cuplikan Python & Numpy yang menyertai jawaban @ amoeba dan saya tinggalkan di sini kalau-kalau itu berguna untuk seseorang. Komentar sebagian besar diambil dari jawaban @ 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)
pengguna115202
sumber
21

Biarkan saya mulai dengan PCA. Misalkan Anda memiliki n titik data yang masing-masing terdiri dari angka d (atau dimensi). Jika Anda memusatkan data ini (kurangi titik data rata-rata dari setiap vektor data x i ), Anda dapat menumpuk data untuk membuat matriksμxsaya

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

Matriks kovarians

S=1n-1saya=1n(xsaya-μ)(xsaya-μ)T=1n-1XTX

S

S=VΛVT=saya=1rλsayavsayavsayaT,

vsayasayaλsayasayaSsaya

PCA dari Gaussian Dataset yang Dihasilkan Secara Acak

SEBUAH=(1201)kamusayavsaya

SVD untuk contoh 2x2

SEBUAHSkamusayavsaya

XSEBUAH=X

X=saya=1rσsayakamusayavjT,

{kamusaya}{vsaya}Svsaya

kamusaya=1(n-1)λsayaXvsaya,

σsaya

σsaya2=(n-1)λsaya.

kamusayaXkamusayaXsayavsayaX

Saya membahas lebih detail dan manfaat hubungan antara PCA dan SVD dalam artikel yang lebih panjang ini .

Andre P
sumber
Terima kasih untuk anser Anda, Andre. Hanya dua koreksi kesalahan ketik kecil: 1. Dalam paragraf terakhir Anda bingung kiri dan kanan. 2. Dalam rumus (modal) untuk X, Anda menggunakan v_j alih-alih v_i.
Alon