特征分解以及奇異值分解

首先我們來看幾個(gè)公式
variance公式:
\sigma ^ { 2 } ( x ) = \frac { 1 } { n } \sum _ { i = 1 } ^ { n } \left( x _ { i } - \mu \right) ^ { 2 }
covariance公式, 即E [ ( x - E [ x ] ) ( y - E [ y ] ) ]:
\sigma ( x , y ) = \frac { 1 } { n } \sum _ { i = 1 } ^ { n } \left( x - \mu _ { x } \right) \left( y - \mu _ { y } \right)
當(dāng)隨機(jī)變量x和y相同時(shí), covariance等同于variance: \sigma ( x , x ) = \sigma ^ { 2 } ( x )
如果協(xié)方差covariance等于0說明這兩個(gè)隨機(jī)變量不相關(guān)
協(xié)方差矩陣:
\mathbf { \Sigma } = \left[ \begin{array} { c c c c } { \sigma \left( X _ { 1 } , X _ { 1 } \right) } & { \sigma \left( X _ { 1 } , X _ { 2 } \right) } & { \dots } & { \sigma \left( X _ { 1 } , X _ { n } \right) } \\ { \sigma \left( X _ { 2 } , X _ { 1 } \right) } & { \sigma \left( X _ { 2 } , X _ { 2 } \right) } & { \dots } & { \sigma \left( X _ { 2 } , X _ { n } \right) } \\ { \vdots } & { \vdots } & { \ddots } & { \vdots } \\ { \sigma \left( X _ { n } , X _ { 1 } \right) } & { \sigma \left( X _ { n } , X _ { 2 } \right) } & { \dots } & { \sigma \left( X _ { n } , X _ { n } \right) } \end{array} \right]
均值中心化(mean centering): 指得是將一系列的樣本點(diǎn)的均值置0,也就是每個(gè)樣本點(diǎn)的值減去所有樣本點(diǎn)的均值, 這樣新生成的所有樣本點(diǎn)的均值即為0。
現(xiàn)在我們設(shè)z:
z=\left[ \begin{array} { c c c c } {v_{11}}&{v_{12}}&v_{13}&...\\{v_{21}}&{v_{22}}&v_{23}&...\\{v_{31}}&{v_{32}}&v_{33}&... \end{array}\right]
其中z的每一行都是mean centred后的特征向量feature vector, 此時(shí), 之前的協(xié)方差矩陣\Sigma就可表示為 (因?yàn)榫刀甲優(yōu)?, 所以原來(x-\mu_1)(y-\mu_2)直接變?yōu)榱藊*y )
\Sigma \propto \mathbf { Z } ^ { \mathrm { T } } \mathbf { Z }

1. ****Principal axes of variation (變化主軸)

Principal axes of variation指的是對于高維數(shù)據(jù)而言, 變化率最顯著的數(shù)據(jù)所在維度, 為了理解這一概念, 首先介紹基向量(basis)

一組基是由n維空間中n個(gè)線性獨(dú)立的向量組成, 這些向量之間是垂直的, 它們構(gòu)成了一個(gè)坐標(biāo)系統(tǒng), 而n維空間中有無限組基向量

基向量

**
**

第一主成分軸(****The ?rst principal axis****)：

第一主成分軸指的是對在n維空間中的數(shù)據(jù)點(diǎn), 指向最大variance方向的軸

**
**

第一和第二成分主軸

第二主成分軸是指垂直于第一主成分軸同時(shí)指向最大variance方向的軸

以此類推, 第三主成分軸是垂直于第一和第二的前提下, 指向有著最大variance的軸

2. ****特征向量和特征根

特征向量和特征根

最多有n對 特征向量-特征根對
其中若A是對稱矩陣(對于任何方形矩陣X，X+X^T是對稱矩陣)的話, 則特征向量的集合是正交的
如果A是協(xié)方差矩陣的話, 那這些特征根就是主成分坐標(biāo)軸(principal axes)

對于n\leq4的情況, 可以通過代數(shù)的方法解得特征根和特征方程。
但對于更大的矩陣, 就需要特征分解(Eigendecomposition,簡寫為EVD)了。

3. ****特征分解

特征值分解（EVD），在這里，選擇一種特殊的矩陣——對稱陣（酉空間中叫hermite矩陣即厄米陣）。對稱陣有一個(gè)性質(zhì)：它總能相似對角化，對稱陣不同特征值對應(yīng)的特征向量兩兩正交。一個(gè)矩陣能相似對角化即說明其特征子空間即為其列空間，若不能對角化則其特征子空間為列空間的子空間。現(xiàn)在假設(shè)存在mxm的滿秩對稱矩陣A，它有m個(gè)不同的特征值，設(shè)特征值為\lambda_i,對應(yīng)的單位特征向量為x_i
則有:
\left.\begin{aligned} A x _ { 1 } & = \lambda _ { 1 } x _ { 1 } \\ A x _ { 2 } & = \lambda _ { 2 } x _ { 2 } \\...\\ A x _ { m } & = \lambda _ { m } x _ { m } \end{aligned} \right.
將上面的式子用矩陣形式表示, 進(jìn)而:
\left. \begin{array} { c } { A U = U \Lambda } \\ { U = \left[ x _ { 1 } x _ { 2 } \cdots x _ { m } \right] } \end{array} \right.
\Lambda = \left[ \begin{array} { c c c } { \lambda _ { 1 } } & { \dots } & { 0 } \\ { \vdots } & { \ddots } & { \vdots } \\ { 0 } & { \cdots } & { \lambda _ { m } } \end{array} \right]
令式子A U = U \Lambda兩邊各除以一個(gè)U, 則有(由于對稱陣特征向量兩兩正交，所以U為正交陣，正交陣的逆矩陣等于其轉(zhuǎn)置):
A = U \Lambda U ^ { - 1 } = U \Lambda U ^ { T }
這里假設(shè)A有m個(gè)不同的特征值，實(shí)際上，只要A是對稱陣其均有如上分解。

特征分解

如果A是對稱矩陣(譬如協(xié)方差矩陣), 此時(shí)Q^{-1}=Q^T (即特征向量是正交的), 所以此時(shí)
\mathbf { A } = \mathbf { Q } \mathbf { \Lambda } \mathbf { Q } ^ { \mathrm { T } }
將eigenvector和對應(yīng)的eigenvalue排序, PCA取前k個(gè)

要明確的是，一個(gè)矩陣其實(shí)就是一個(gè)線性變換，因?yàn)橐粋€(gè)矩陣乘以一個(gè)向量后得到的向量，其實(shí)就相當(dāng)于將這個(gè)向量進(jìn)行了線性變換。比如說下面的一個(gè)矩陣：
M = \left[ \begin{array} { l l } { 3 } & { 0 } \\ { 0 } & { 1 } \end{array} \right]
因?yàn)檫@個(gè)矩陣M乘以一個(gè)向量(x,y)的結(jié)果是:
\left[ \begin{array} { l l } { 3 } & { 0 } \\ { 0 } & { 1 } \end{array} \right] \left[ \begin{array} { l } { x } \\ { y } \end{array} \right] = \left[ \begin{array} { c } { 3 x } \\ { y } \end{array} \right]
它其實(shí)對應(yīng)的線性變換是下面的形式：

拉伸變換

上面的矩陣是對稱的，所以這個(gè)變換是一個(gè)對x，y軸的方向一個(gè)拉伸變換, 當(dāng)矩陣不是對稱的時(shí)候，假如說矩陣是下面的樣子：

M = \left[ \begin{array} { l l } { 1 } & { 1 } \\ { 0 } & { 1 } \end{array} \right]
它所描述的變換是下面的樣子：

非對稱矩陣

在圖中，藍(lán)色的箭頭是一個(gè)最主要的變化方向（變化方向可能有不止一個(gè)），如果我們想要描述好一個(gè)變換，那我們就描述好這個(gè)變換主要的變化方向就好了。反過頭來看看之前特征值分解的式子，分解得到的Σ矩陣是一個(gè)對角陣，里面的特征值是由大到小排列的，這些特征值所對應(yīng)的特征向量就是描述這個(gè)矩陣變化方向(從主要的變化到次要的變化排列), 當(dāng)矩陣是高維的情況下，那么這個(gè)矩陣就是高維空間下的一個(gè)線性變換，我們通過特征值分解得到的前N個(gè)特征向量，那么就對應(yīng)了這個(gè)矩陣最主要的N個(gè)變化方向。我們利用這前N個(gè)變化方向，就可以近似這個(gè)矩陣(變換)。也就是之前說的：提取這個(gè)矩陣最重要的特征。

總結(jié)一下，特征值分解可以得到特征值與特征向量，特征值表示的是這個(gè)特征到底有多重要，而特征向量表示這個(gè)特征是什么

4. ****PCA流程

輸入：n維樣本集D=(x^{(1)}, x^{(2)},...,x^{(m)})，要降維到的維數(shù)n'.
輸出：降維后的樣本集D'

  1. 對所有的樣本進(jìn)行中心化：x^{(i)} = x^{(i)} - \frac{1}{m}\sum\limits_{j=1}^{m} x^{(j)}
  2. 計(jì)算樣本的協(xié)方差矩陣XX^T, 注意, 協(xié)方差矩陣就等于XX^T
  3. 對矩陣XX^T進(jìn)行特征值分解
  4. 取出最大的n'個(gè)特征值對應(yīng)的特征向量(w_1,w_2,...,w_{n'}), 將所有的特征向量標(biāo)準(zhǔn)化后，組成特征向量矩陣W。
  5. 對樣本集中的每一個(gè)樣本x^{(i)}, 轉(zhuǎn)化為新的樣本 z^{(i)}=W^Tx^{(i)}
  6. 得到輸出樣本集D' =(z^{(1)}, z^{(2)},...,z^{(m)})

有時(shí)候，我們不指定降維后的n'的值，而是換種方式，指定一個(gè)降維到的主成分比重閾值t。這個(gè)閾值t在（0,1]之間。假如我們的n個(gè)特征值為\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_n, 則n'可以通過下式得到:
\frac{\sum\limits_{i=1}^{n'}\lambda_i}{\sum\limits_{i=1}^{n}\lambda_i} \geq t

這里對PCA算法做一個(gè)總結(jié)。作為一個(gè)非監(jiān)督學(xué)習(xí)的降維方法，它只需要特征值分解，就可以對數(shù)據(jù)進(jìn)行壓縮，去噪。因此在實(shí)際場景應(yīng)用很廣泛。為了克服PCA的一些缺點(diǎn)，出現(xiàn)了很多PCA的變種，比如第六節(jié)的為解決非線性降維的KPCA，還有解決內(nèi)存限制的增量PCA方法Incremental PCA，以及解決稀疏數(shù)據(jù)降維的PCA方法Sparse PCA等。

PCA算法的主要優(yōu)點(diǎn)有：

1）僅僅需要以方差衡量信息量，不受數(shù)據(jù)集以外的因素影響。

2）各主成分之間正交，可消除原始數(shù)據(jù)成分間的相互影響的因素。

3）計(jì)算方法簡單，主要運(yùn)算是特征值分解，易于實(shí)現(xiàn)。

PCA算法的主要缺點(diǎn)有：

1）主成分各個(gè)特征維度的含義具有一定的模糊性，不如原始樣本特征的解釋性強(qiáng)。

2）方差小的非主成分也可能含有對樣本差異的重要信息，因降維丟棄可能對后續(xù)數(shù)據(jù)處理有影響。

5. ****奇異值分解

奇異值分解是一個(gè)有著很明顯的物理意義的一種方法，它可以將一個(gè)比較復(fù)雜的矩陣用更小更簡單的幾個(gè)子矩陣的相乘來表示，這些小矩陣描述的是矩陣的重要的特性。

特征值分解是一個(gè)提取矩陣特征很不錯(cuò)的方法，但是它只是對方陣而言的，在現(xiàn)實(shí)的世界中，我們看到的大部分矩陣都不是方陣, 比如說有N個(gè)學(xué)生，每個(gè)學(xué)生有M科成績，這樣形成的一個(gè)N * M的矩陣就不可能是方陣, 此時(shí)即用到了奇異值分解, 奇異值分解是一個(gè)能適用于任意的矩陣的一種分解的方法:

奇異值分解

其中p是矩陣M的秩, 秩代表線性不相關(guān)的行或者列的數(shù)量

U是一個(gè)m * p的方陣（里面的向量是正交的，U里面的列向量稱為左奇異向量），Σ是一個(gè)p * p的矩陣（除了對角線的元素都是0，對角線上的元素稱為奇異值），V’(V的轉(zhuǎn)置)是一個(gè)p * n的矩陣，里面的行向量也是正交的，V里面的向量稱為右奇異向量。

左奇異向量集合是MM^T的特征向量集合
右奇異向量集合是M^TM的特征向量集合
The singular values are the square roots of the eigenvalues of the corresponding eigenvectors of M^TM and MM^T
如果M是mean centred的特征向量矩陣的話, V的列向量是M^TM的特征向量, 它們是M的主成分(principle components)。

那么奇異值和特征值是怎么對應(yīng)起來的呢？首先，我們將一個(gè)矩陣M的轉(zhuǎn)置乘以M，將會得到一個(gè)方陣，我們用這個(gè)方陣求特征值可以得到：
\left( M ^ { T } M \right) v _ { i } = \lambda _ { i } v _ { i }
這里得到的v，就是我們上面的右奇異向量。此外我們還可以得到:
\left. \begin{array} { l } { \sigma _ { i } = \sqrt { \lambda } _ { i } } \\ { u _ { i } = \frac { 1 } { \sigma } M v _ { i } } \end{array} \right.
這里的σ就是上面說的奇異值，u就是上面說的左奇異向量
奇異值σ跟特征值類似，在矩陣Σ中也是從大到小排列，而且σ的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上了。也就是說，我們也可以用前r大的奇異值來近似描述矩陣，這里定義一下部分奇異值分解:

近似奇異值分解

右邊的三個(gè)矩陣相乘的結(jié)果將會是一個(gè)接近于M的矩陣，在這兒，r越接近于p，則相乘的結(jié)果越接近于M。而這三個(gè)矩陣的面積之和（在存儲觀點(diǎn)來說，矩陣面積越小，存儲量就越?。┮h(yuǎn)遠(yuǎn)小于原始的矩陣M，我們?nèi)绻胍獕嚎s空間來表示原矩陣A，我們存下這里的三個(gè)矩陣：U、Σ、V就好了。

SVD流程：

SVD流程

至于為什么要用基于SVD的PCA是因?yàn)?

  1. 計(jì)算可行性

  2. SVD的速度比EVD更快

除此之外, SVD適用的場合有:

  1. 求偽逆(Pseudoinverse)

  2. 解homogeneous linear equations, 如Ax=0

  3. 數(shù)據(jù)挖掘: 如基于CF的推薦系統(tǒng)

SVD求偽逆的一個(gè)例子

A矩陣的偽逆代表其與A的乘積等于單位矩陣

我們來具體算一個(gè)矩陣A的偽逆：

\mathbf { A } = \left[ \begin{array} { c c } { 1 } & { 1 } \\ { 0 } & { 1 } \\ { 1 } & { 0 } \\ { 1 } & { 1 } \end{array} \right] \Rightarrow \mathbf { A } ^ { * } \mathbf { A } = \left[ \begin{array} { c c c c } { 1 } & { 0 } & { 1 } & { 1 } \\ { 1 } & { 1 } & { 0 } & { 1 } \end{array} \right] \left[ \begin{array} { c c } { 1 } & { 1 } \\ { 0 } & { 1 } \\ { 1 } & { 0 } \\ { 1 } & { 1 } \end{array} \right] = \left[ \begin{array} { c c } { 3 } & { 2 } \\ { 2 } & { 3 } \end{array} \right]

易知，rank(A*A)=2。下面來求矩陣A*A的特征值，于是有

\operatorname { det } \left| \begin{array} { c c } { 3 - \lambda } & { 2 } \\ { 2 } & { 3 - \lambda } \end{array} \right| = \lambda ^ { 2 } - 6 \lambda + 9 - 4 = ( \lambda - 5 ) ( \lambda - 1 ) \Rightarrow \lambda _ { 1 } = 5 , \lambda _ { 2 } = 1

接下來求對應(yīng)的特征向量，因?yàn)?/p>

\mathbf { A } ^ { * } \mathbf { A } v = \lambda v \Rightarrow \left( \mathbf { A } ^ { * } \mathbf { A } - \lambda I \right) v = 0

所以可知當(dāng)λ1=5時(shí)，對應(yīng)的特征向量（注意結(jié)果要正交歸一化）：

\mathbf { A } ^ { * } \mathbf { A } - 5 I = \left[ \begin{array} { c c } { - 2 } & { 2 } \\ { 2 } & { - 2 } \end{array} \right] \Rightarrow u _ { 1 } = \left[ \begin{array} { c } { \frac { 1 } { \sqrt { 2 } } } \\ { \frac { 1 } { \sqrt { 2 } } } \end{array} \right]

同理還有當(dāng)λ2=1時(shí)，對應(yīng)的特征向量

\mathbf { A } ^ { * } \mathbf { A } - 1 I = \left[ \begin{array} { c c } { 2 } & { 2 } \\ { 2 } & { 2 } \end{array} \right] \Rightarrow u _ { 2 } = \left[ \begin{array} { c } { \frac { 1 } { \sqrt { 2 } } } \\ { - \frac { 1 } { \sqrt { 2 } } } \end{array} \right]

如此便得到了SVD中需要的U矩陣

U=\left[ \begin{array} { c c } { \frac { 1 } { \sqrt { 2 } } } & { \frac { 1 } { \sqrt { 2 } } } \\ { \frac { 1 } { \sqrt { 2 } } } & { \frac { - 1 } { \sqrt { 2 } } } \end{array} \right]

為了求出矩陣V，先求W：

\mathbf { w } = \mathbf { A } \mathbf { U } = \left[ \begin{array} { c c } { 1 } & { 1 } \\ { 0 } & { 1 } \\ { 1 } & { 0 } \\ { 1 } & { 1 } \end{array} \right] \left[ \begin{array} { c c } { \frac { 1 } { \sqrt { 2 } } } & { \frac { 1 } { \sqrt { 2 } } } \\ { \frac { 1 } { \sqrt { 2 } } } & { \frac { - 1 } { \sqrt { 2 } } } \end{array} \right] = \left[ \begin{array} { c c } { \sqrt { 2 } } & { 0 } \\ { 1 / \sqrt { 2 } } & { - 1 / \sqrt { 2 } } \\ { 1 / \sqrt { 2 } } & { 1 / \sqrt { 2 } } \\ { \sqrt { 2 } } & { 0 } \end{array} \right]= \left[ \begin{array} { l l } { w _ { 1 } } & { w _ { 2 } } \end{array} \right]

于是可知

v _ { 1 } = \frac { w _ { 1 } } { \sqrt { 5 } } , \quad v _ { 2 } = \frac { w _ { 2 } } { \sqrt { 1 } } \Rightarrow \mathbf { V } = \left[ \begin{array} { l l } { v _ { 1 } } & { v _ { 2 } } \end{array} \right]

所以根據(jù)公式A的偽逆就是, 其中V*代表其轉(zhuǎn)置矩陣

\mathbf { A } ^ { \dagger } = \mathbf { U } \mathbf { \Lambda } \mathbf { V } ^ { * } = \left[ \begin{array} { c c } { \frac { 1 } { \sqrt { 2 } } } & { \frac { 1 } { \sqrt { 2 } } } \\ { \frac { 1 } { \sqrt { 2 } } } & { \frac { - 1 } { \sqrt { 2 } } } \end{array} \right] \left[ \begin{array} { c c } { \frac { 1 } { \sqrt { 5 } } } & { 0 } \\ { 0 } & { \frac { 1 } { \sqrt { 1 } } } \end{array} \right] \left[ \begin{array} { c c c } { \frac { \sqrt { 2 } } { \sqrt { 5 } } } & { 1 / \sqrt { 10 } } & { 1 / \sqrt { 10 } } & { \frac { \sqrt { 2 } } { \sqrt { 5 } } } \\ { 0 } & { - 1 / \sqrt { 2 } } & { 1 / \sqrt { 2 } } & { 0 } \end{array} \right]

6. ****SVD和EVD的計(jì)算方法

普遍來說, 這些計(jì)算方法都是迭代的:

  1. Power Iteration

-Repeated for each E.V. by rotating and truncating the input to remove the effect of the previous E.V.

  1. “Arnoldi Iteration” and the “Lanczos Algorithm”

-Move ef?cient variants of Power Iteration

-use the “Gram-Schmidt” process to ?nd the orthonormal basis of the top-r E.Vs

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容