PCA主成分分析原理

主成分分析（Principal components analysis，以下簡稱PCA）是最重要的降維方法之一。在資料壓縮消除備援和資料噪音消除等領域都有廣泛的應用。一般我們提到降維最容易想到的算法就是PCA，下面我們就對PCA的原理做一個總結。

1. PCA的思想

PCA顧名思義，就是找出資料裡最主要的方面，用資料裡最主要的方面來代替原始資料。具體的，假如我們的資料集是n維的，共有m個資料$(x^{(1)},x^{(2)},...,x^{(m)})$。我們希望将這m個資料的次元從n維降到n'維，希望這m個n'維的資料集盡可能的代表原始資料集。我們知道資料從n維降到n'維肯定會有損失，但是我們希望損失盡可能的小。那麼如何讓這n'維的資料盡可能表示原來的資料呢？

我們先看看最簡單的情況，也就是n=2，n'=1,也就是将資料從二維降維到一維。資料如下圖。我們希望找到某一個次元方向，它可以代表這兩個次元的資料。圖中列了兩個向量方向，$u_1$和$u_2$，那麼哪個向量可以更好的代表原始資料集呢？從直覺上也可以看出，$u_1$比$u_2$好。

為什麼$u_1$比$u_2$好呢？可以有兩種解釋，第一種解釋是樣本點到這個直線的距離足夠近，第二種解釋是樣本點在這個直線上的投影能盡可能的分開。

假如我們把n'從1維推廣到任意維，則我們的希望降維的标準為：樣本點到這個超平面的距離足夠近,或者說樣本點在這個超平面上的投影能盡可能的分開。

基于上面的兩種标準，我們可以得到PCA的兩種等價推導。

2. PCA的推導:基于小于投影距離

我們首先看第一種解釋的推導，即樣本點到這個超平面的距離足夠近。

假設m個n維資料$(x^{(1)}, x^{(2)},...,x^{(m)})$都已經進行了中心化，即$\sum\limits_{i=1}^{m}x^{(i)}=0$。經過投影變換後得到的新坐标系為$\{w_1,w_2,...,w_n\}$,其中$w$是标準正交基，即$||w||_2=1, w_i^Tw_j=0$。

如果我們将資料從n維降到n'維，即丢棄新坐标系中的部分坐标，則新的坐标系為$\{w_1,w_2,...,w_{n'}\}$,樣本點$x^{(i)}$在n'維坐标系中的投影為：$z^{(i)} = (z_1^{(i)}, z_2^{(i)},...,z_{n'}^{(i)})$.其中，$z_j^{(i)} = w_j^Tx^{(i)}$是$x^{(i)}$在低維坐标系裡第j維的坐标。

如果我們用$z^{(i)}$來恢複原始資料$x^{(i)}$,則得到的恢複資料$\overline{x}^{(i)} = \sum\limits_{j=1}^{n'}z_j^{(i)}w_j = Wz^{(i)}$,其中，W為标準正交基組成的矩陣。

現在我們考慮整個樣本集，我們希望所有的樣本到這個超平面的距離足夠近，即最小化下式：

$$

\sum\limits_{i=1}^{m}||\overline{x}^{(i)} - x^{(i)}||_2^2

将這個式子進行整理，可以得到:

\begin{align} \sum\limits_{i=1}^{m}||\overline{x}^{(i)} - x^{(i)}||_2^2 & = \sum\limits_{i=1}^{m}|| Wz^{(i)} - x^{(i)}||_2^2 \\& = \sum\limits_{i=1}^{m}(Wz^{(i)})^T(Wz^{(i)}) - 2\sum\limits_{i=1}^{m}(Wz^{(i)})^Tx^{(i)} + \sum\limits_{i=1}^{m} x^{(i)T}x^{(i)} \\& = \sum\limits_{i=1}^{m}z^{(i)T}z^{(i)} - 2\sum\limits_{i=1}^{m}z^{(i)T}W^Tx^{(i)} +\sum\limits_{i=1}^{m} x^{(i)T}x^{(i)} \\& = \sum\limits_{i=1}^{m}z^{(i)T}z^{(i)} - 2\sum\limits_{i=1}^{m}z^{(i)T}z^{(i)}+\sum\limits_{i=1}^{m} x^{(i)T}x^{(i)} \\& = - \sum\limits_{i=1}^{m}z^{(i)T}z^{(i)} + \sum\limits_{i=1}^{m} x^{(i)T}x^{(i)} \\& = -tr( W^T（\sum\limits_{i=1}^{m}x^{(i)}x^{(i)T})W) + \sum\limits_{i=1}^{m} x^{(i)T}x^{(i)} \\& = -tr( W^TXX^TW) + \sum\limits_{i=1}^{m} x^{(i)T}x^{(i)} \end{align}

其中第（1）步用到了$\overline{x}^{(i)}=Wz^{(i)}$,第二步用到了平方和展開，第（3）步用到了矩陣轉置公式$(AB)^T =B^TA^T$和$W^TW=I$,第（4）步用到了$z^{(i)}=W^Tx^{(i)}$，第（5）步合并同類項，第（6）步用到了$z^{(i)}=W^Tx^{(i)}$和矩陣的迹,第7步将代數和表達為矩陣形式。

注意到$\sum\limits_{i=1}^{m}x^{(i)}x^{(i)T}$是資料集的協方差矩陣，W的每一個向量$w_j$是标準正交基。而$\sum\limits_{i=1}^{m} x^{(i)T}x^{(i)}$是一個常量。最小化上式等價于：

\underbrace{arg\;min}_{W}\;-tr( W^TXX^TW) \;\;s.t. W^TW=I

這個最小化不難，直接觀察也可以發現最小值對應的W由協方差矩陣$XX^T$最大的n'個特征值對應的特征向量組成。當然用數學推導也很容易。利用拉格朗日函數可以得到

J(W) = -tr( W^TXX^TW) + \lambda(W^TW-I)

對W求導有$-XX^TW+\lambda W=0$, 整理下即為：

這樣可以更清楚的看出，W為$XX^T$的n'個特征向量組成的矩陣，而$λ$為$XX^T$的特征值。當我們将資料集從n維降到n'維時，需要找到最大的n'個特征值對應的特征向量。這n'個特征向量組成的矩陣W即為我們需要的矩陣。對于原始資料集，我們隻需要用$z^{(i)}=W^Tx^{(i)}$,就可以把原始資料集降維到最小投影距離的n'維資料集。

如果你熟悉譜聚類的優化過程，就會發現和PCA的非常類似，隻不過譜聚類是求前k個最小的特征值對應的特征向量，而PCA是求前k個最大的特征值對應的特征向量。

3. PCA的推導:基于最大投影方差

現在我們再來看看基于最大投影方差的推導。

對于任意一個樣本$x^{(i)}$，在新的坐标系中的投影為$W^Tx^{(i)}$,在新坐标系中的投影方差為$W^Tx^{(i)}x^{(i)T}W$，要使所有的樣本的投影方差和最大，也就是最大化$\sum\limits_{i=1}^{m}W^Tx^{(i)}x^{(i)T}W$,即：

\underbrace{arg\;max}_{W}\;tr( W^TXX^TW) \;\;s.t. W^TW=I

觀察第二節的基于最小投影距離的優化目标，可以發現完全一樣，隻是一個是加負号的最小化，一個是最大化。

利用拉格朗日函數可以得到

J(W) = tr( W^TXX^TW) + \lambda(W^TW-I)

對W求導有$XX^TW+\lambda W=0$, 整理下即為：

XX^TW=（-\lambda）W

和上面一樣可以看出，W為$XX^T$的n'個特征向量組成的矩陣，而$−λ$為$XX^T$的特征值。當我們将資料集從n維降到n'維時，需要找到最大的n'個特征值對應的特征向量。這n'個特征向量組成的矩陣W即為我們需要的矩陣。對于原始資料集，我們隻需要用$z^{(i)}=W^Tx^{(i)}$,就可以把原始資料集降維到最小投影距離的n'維資料集。

4. PCA算法流程

從上面兩節我們可以看出，求樣本$x^{(i)}$的n'維的主成分其實就是求樣本集的協方差矩陣$XX^T$的前n'個特征值對應特征向量矩陣W，然後對于每個樣本$x^{(i)}$,做如下變換$z^{(i)}=W^Tx^{(i)}$，即達到降維的PCA目的。

下面我們看看具體的算法流程。

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

輸出：降維後的樣本集D′

1)對所有的樣本進行中心化：$x^{(i)} = x^{(i)} - \frac{1}{m}\sum\limits_{j=1}^{m} x^{(j)}$

2) 計算樣本的協方差矩陣$XX^T$

3) 對矩陣$XX^T$進行特征值分解

4）取出最大的n'個特征值對應的特征向量$(w_1,w_2,...,w_{n'})$, 将所有的特征向量标準化後，組成特征向量矩陣W。

5）對樣本集中的每一個樣本$x^{(i)}$,轉化為新的樣本$z^{(i)}=W^Tx^{(i)}$

6) 得到輸出樣本集$D' =(z^{(1)}, z^{(2)},...,z^{(m)})$

有時候，我們不指定降維後的n'的值，而是換種方式，指定一個降維到的主成分比重門檻值t。這個門檻值t在（0,1]之間。假如我們的n個特征值為$\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

5. 核主成分分析KPCA介紹

在上面的PCA算法中，我們假設存在一個線性的超平面，可以讓我們對資料進行投影。但是有些時候，資料不是線性的，不能直接進行PCA降維。這裡就需要用到和支援向量機一樣的核函數的思想，先把資料集從n維映射到線性可分的高維N>n,然後再從N維降維到一個低次元n', 這裡的次元之間滿足n'使用了核函數的主成分分析一般稱之為核主成分分析(Kernelized PCA, 以下簡稱KPCA。假設高維空間的資料是由n維空間的資料通過映射$ϕ$産生。

則對于n維空間的特征分解：

\sum\limits_{i=1}^{m}x^{(i)}x^{(i)T}W=\lambda W

映射為：

\sum\limits_{i=1}^{m}\phi(x^{(i)})\phi(x^{(i)})^TW=\lambda W

通過在高維空間進行協方差矩陣的特征值分解，然後用和PCA一樣的方法進行降維。一般來說，映射$ϕ$不用顯式的計算，而是在需要計算的時候通過核函數完成。由于KPCA需要核函數的運算，是以它的計算量要比PCA大很多。

6.PCA算法總結

這裡對PCA算法做一個總結。作為一個非監督學習的降維方法，它隻需要特征值分解，就可以對資料進行壓縮，去噪。是以在實際場景應用很廣泛。為了克服PCA的一些缺點，出現了很多PCA的變種，比如第六節的為解決非線性降維的KPCA，還有解決記憶體限制的增量PCA方法Incremental PCA，以及解決稀疏資料降維的PCA方法Sparse PCA等。

PCA算法的主要優點有：

1）僅僅需要以方差衡量資訊量，不受資料集以外的因素影響。　

2）各主成分之間正交，可消除原始資料成分間的互相影響的因素。

3）計算方法簡單，主要運算是特征值分解，易于實作。

PCA算法的主要缺點有：

1）主成分各個特征次元的含義具有一定的模糊性，不如原始樣本特征的解釋性強。

2）方差小的非主成分也可能含有對樣本差異的重要資訊，因降維丢棄可能對後續資料處理有影響。

摘自：

http://www.cnblogs.com/pinard/p/6239403.html