台湾 || 语言: 大陆简体港澳繁體台灣正體

PCA降維，特徵值分解，SVD， KPCA

雪花台灣 2019-02-25 14:16

一、背景

PCA作為一個面試常常考的考點。為什麼呢？

PCA結合了概率論，線性代數等高等數學知識。

理解了PCA的原理，也就說明了面試者有者良好的數學基礎。

仔細學習一遍PCA，相當於複習了整個本科的概率論跟線性代數。

二、數學知識

需要用到下面這些基礎概念，知道的可以跳過。

協方差與方差：

協方差用來衡量兩個隨機變數的總體誤差，記作

協方差可以用來衡量兩個隨機變數的相關性，方差就是一個隨機變數與它本身的協方差，Cov(X,X)。

協方差為正，那麼正相關；協方差為負，那麼負相關；協方差為0，兩個隨機變數相互獨立。

2. 協方差矩陣

協方差只能計算兩個隨機變數之間的相關性。有時候我們需要計算多個隨機變數的關聯程度，比如兩兩之間的關係。

舉例，有N個隨機變數，組成一個隨機向量 $m{X} = [X_1,X_2,X_3,...X_n]^T$ ，那麼這個隨機向量的協方差矩陣記作 :

其實就是將隨機變數兩兩之間的協方差表示成矩陣的形式。

協方差矩陣是一個方陣，它的對角線上的元素就是每個維度隨機變數的方差。

3. 矩陣的特徵值

準確地說，只有方陣才有特徵值。對於一個方陣，它的特徵值定義為：

4. 方陣的特徵值分解

對於一個方陣，總可以寫成如下形式：

$m{A} = m{V^T Lambda V}$

其中， $m{V}^T$ 是由特徵向量組成的矩陣，是一個對角矩陣，其對角線上的元素就是特徵值:

方陣的特徵值分解

5. 矩陣的奇異值分解

只有方陣才能做特徵值分解。而對任意形狀的矩陣，可以做奇異值分解。奇異值分解其實就是對於方陣的協方差矩陣 $m{X^TX} 和 m{XX^T}$ 做特徵值分解推導出來的：

左右兩邊的矩陣分別是 $m{X^TX} 和 m{XX^T}$ 的特徵向量。中間的矩陣對角線的元素是 $m{X^TX}$ 的特徵值。

三、主成分分析 PCA

PCA是一種用來降維的方法。

先從最簡單的情況討論，把二維數據降到一維。

看下面的例子，我們選取一條直線，然後作每個點到這條直線的投影，用垂足來代替原來的點，下面有兩個方向1和2：

方向1

方向2

方向1做投影的時候，由於中間兩個點垂足幾乎重合了，導致損失了信息。因此直覺上方向1沒有方向2好。

如何量化一個投影的好壞程度？我們可以用投影以後的整個數據集的方差來評價。方差越大，說明數據分散得越開，這樣可以最大程度地保留高維度的信息不被丟失掉。

考慮對於一個D維度的數據集，我們想把它投影到一維空間，如何用數學語言描述？

首先，求投影的操作可以直接表示為兩個向量的點乘：

$m{x^Tv} = |m{x}||m{v}|cos heta$

當是單位向量的時候，剛好兩個向量點乘的結果剛好等於它的投影。

對於數據集。選取一個D維的單位向量，即 $m{v^T}m{v}=1$ 。

那麼就是數據集在該方向上的投影的結果，因為：

$m{Xv} = left[ egin{matrix} m{x}^T_1 \ m{x}^T_2 \ m{x}^T_3 \ ...\ m{x}^T_N end{matrix} ight] m{v} = left[ egin{matrix} m{x}^T_1m{v} \ m{x}^T_2 m{v}\ m{x}^T_3 m{v}\ ...\ m{x}^T_Nm{v} end{matrix} ight] = left[ egin{matrix} a_1 \ a_2 \ a_3\ ...\ a_N end{matrix} ight]$

就是訓練樣本n在投影以後的一維空間的坐標。

定義一個隨機變數 $m{Z} = m{Xv} = [a_1,a_2,...,a_N]^T$ ，我們希望最大化隨機變數的方差，表示為數學公式為：

$max_m{v} Cov(m{Z},m{Z}) = max_m{v} m{(Xv-mu)^T(Xv-mu)} \ s.t m{v^Tv} = 1$

如果我們事先對數據進行預處理，令 $m{x_n} = m{x_n} - mu$ ，則可以簡化:

$m{(Xv-mu)^T(Xv-mu)} = m{(Xv)^T(Xv)} = m{v^TX^TXv}$

簡化後的目標為：

$max_{m{v}} m{v^TX^TXv} \ s.t m{v^Tv} = 1$

求解上式，帶等式約束條件的優化，使用拉格朗日乘子法，變為：

$max_{m{v}} m{v^TX^TXv} - alpha( m{v^Tv} - 1)$

上式對向量求導，得到：

$2m{X^TXv} - 2alpham{v} = 0$

可以得到：

$m{X^TXv}=alpham{v}$

假如把 $m{X^TX}$ 它是一個協方差矩陣，剛好是這個協方差矩陣的特徵值，此時是對應的特徵向量。

上面的式子兩邊乘 $m{v^T}$ 得到:

$m{v^TX^TXv}=alpham{v^Tv}=lambda$

於是我們的問題變成了：

$max_{m{v}} lambda \ s.t m{v^Tv} = 1$

我們要求的方向向量，就是協方差矩陣的最大的特徵值所對應的特徵向量。那麼我們就可以對協方差矩陣 $m{X^TX}$ 做特徵值分解來獲得 $m{v_1}$ 。

這只是得出了一維的情況。如果我們需要降為S個維度呢？

那麼我們要繼續找另外一條直線來投影，我們還是希望方差最大。但是如果跟第一次一樣，我們所獲得得還會是一模一樣的直線，因此有必要加上限制條件。我們希望第二次找到的直線與第一次的垂直，即 $m{v_2^Tv_1} = 0$ ，目標函數為：

$max_{m{v}} m{v_2^TX^TXv_2} \ s.t m{v_2^Tv_1} = 0 \ m{v_2^Tv_2} = 1$

依然用上面的方法，目標可以變成：

$max_{m{v}} lambda \ s.t m{v_2^Tv_1} = 0 \ m{v_2^Tv_2} = 1$

這裡的 $m{v_2}$ 不能選擇特徵值最大的特徵向量 $m{v_1}$ 了，因為不滿足約束條件 $m{v_2^Tv_1} = 0$ 。我們可以選擇第二大的特徵值對應的向量。由於不同的特徵值所對應的特徵向量一定相互垂直，所以肯定滿足條件。

通過不斷選取最大的特徵值對應的特徵向量，直到選取的個數達到要求降維的維度數S。我們可以把它拼成一個維度為(D * S)的矩陣。

然後降維的操作可以通過得到：

然而，實際應用中，並不一定要求出矩陣的協方差矩陣 $m{X^TX}$ 再做特徵值分解。可以直接對矩陣做奇異值分解（SVD），我們仍舊能得到對於的特徵向量。

PCA的演算法流程總結：

輸入數據，需要降的目標維度p
將數據中心化為
對進行奇異值分解，選取最大的前p個特徵值對應的特徵向量，組成矩陣
新的數據集為：

四、KPCA

對於有些數據，直接用PCA降維效果不好，可能需要先將輸入數據做高維映射以後再降維，這種方法叫做KPCA，比如：

我們依然可以對輸入用高維映射，然後採用核方法來進行降維。高維映射詳細介紹參見：

折射：高維映射與核方法（Kernel Methods）?

zhuanlan.zhihu.com

通過高維映射，我們把輸入變成了更高維的輸入。想要應用Kernel Trick，我們需要湊出 $m{Phi}m{Phi}^T$ 的形式。

下面給出推導：

令Gram矩陣為： $m{K} = m{Phi}m{Phi}^T$

對於任何單位方向向量，一定可以通過一個向量關於 $m{Phi}^T$ 變換得到，即：

$m{v} = m{Phi}^Tm{alpha}$

我們按照前面的推導，可以一直推到這一步 $m{X^TXv}=lambdam{v}$ 。

把裡面的換成映射之後的，換成 $m{Phi}^Tm{alpha}$ :

$m{Phi^TPhi m{Phi}^Tm{alpha}}=lambdam{Phi}^Tm{alpha}$

化簡後得：

$m{Phi}^T(m{K}m{alpha}- lambdam{alpha}) = 0$

可以發現，其實是Gram矩陣的特徵向量。

KPCA的演算法流程：

對於輸入數據選取合適的核函數，計算Gram矩陣
將矩陣中心化為，就是每個元素減去它這一列的均值。
對矩陣進行特徵值分解，找到特徵向量組成的矩陣。
新的數據集為：

推薦閱讀：

相关文章