主成分分析（PCA）特征選擇算法詳解

1. 問題

真實(shí)的訓(xùn)練數(shù)據(jù)總是存在各種各樣的問題：

1、 比如拿到一個汽車的樣本，里面既有以“千米/每小時”度量的最大速度特征，也有“英里/小時”的最大速度特征，顯然這兩個特征有一個多余。

2、 拿到一個數(shù)學(xué)系的本科生期末考試成績單，里面有三列，一列是對數(shù)學(xué)的興趣程度，一列是復(fù)習(xí)時間，還有一列是考試成績。我們知道要學(xué)好數(shù)學(xué)，需要有濃厚的興趣，所以第二項(xiàng)與第一項(xiàng)強(qiáng)相關(guān)，第三項(xiàng)和第二項(xiàng)也是強(qiáng)相關(guān)。那是不是可以合并第一項(xiàng)和第二項(xiàng)呢？

3、 拿到一個樣本，特征非常多，而樣例特別少，這樣用回歸去直接擬合非常困難，容易過度擬合。比如北京的房價：假設(shè)房子的特征是（大小、位置、朝向、是否學(xué)區(qū)房、建造年代、是否二手、層數(shù)、所在層數(shù)），搞了這么多特征，結(jié)果只有不到十個房子的樣例。要擬合房子特征->房價的這么多特征，就會造成過度擬合。

4、 這個與第二個有點(diǎn)類似，假設(shè)在IR中我們建立的文檔-詞項(xiàng)矩陣中，有兩個詞項(xiàng)為“l(fā)earn”和“study”，在傳統(tǒng)的向量空間模型中，認(rèn)為兩者獨(dú)立。然而從語義的角度來講，兩者是相似的，而且兩者出現(xiàn)頻率也類似，是不是可以合成為一個特征呢？

5、 在信號傳輸過程中，由于信道不是理想的，信道另一端收到的信號會有噪音擾動，那么怎么濾去這些噪音呢？

回顧我們之前介紹的《模型選擇和規(guī)則化》，里面談到的特征選擇的問題。但在那篇中要剔除的特征主要是和類標(biāo)簽無關(guān)的特征。比如“學(xué)生的名字”就和他的“成績”無關(guān)，使用的是互信息的方法。

而這里的特征很多是和類標(biāo)簽有關(guān)的，但里面存在噪聲或者冗余。在這種情況下，需要一種特征降維的方法來減少特征數(shù)，減少噪音和冗余，減少過度擬合的可能性。

下面探討一種稱作主成分分析（PCA）的方法來解決部分上述問題。PCA的思想是將n維特征映射到k維上（k<n），這k維是全新的正交特征。這k維特征稱為主元，是重新構(gòu)造出來的k維特征，而不是簡單地從n維特征中去除其余n-k維特征。

2. PCA計算過程

首先介紹PCA的計算過程：

假設(shè)我們得到的2維數(shù)據(jù)如下：

行代表了樣例，列代表特征，這里有10個樣例，每個樣例兩個特征?？梢赃@樣認(rèn)為，有10篇文檔，x是10篇文檔中“l(fā)earn”出現(xiàn)的TF-IDF，y是10篇文檔中“study”出現(xiàn)的TF-IDF。也可以認(rèn)為有10輛汽車，x是千米/小時的速度，y是英里/小時的速度，等等。

第一步分別求x和y的平均值，然后對于所有的樣例，都減去對應(yīng)的均值。這里x的均值是1.81，y的均值是1.91，那么一個樣例減去均值后即為（0.69,0.49），得到

第二步，求特征協(xié)方差矩陣，如果數(shù)據(jù)是3維，那么協(xié)方差矩陣是

這里只有x和y，求解得

對角線上分別是x和y的方差，非對角線上是協(xié)方差。協(xié)方差大于0表示x和y若有一個增，另一個也增；小于0表示一個增，一個減；協(xié)方差為0時，兩者獨(dú)立。協(xié)方差絕對值越大，兩者對彼此的影響越大，反之越小。

第三步，求協(xié)方差矩陣的特征值和特征向量，得到

上面是兩個特征值，下面是對應(yīng)的特征向量，特征值0.0490833989對應(yīng)特征向量為，這里的特征向量都?xì)w一化為單位向量。

第四步，將特征值按照從大到小的順序排序，選擇其中最大的k個，然后將其對應(yīng)的k個特征向量分別作為列向量組成特征向量矩陣。

這里特征值只有兩個，我們選擇其中最大的那個，這里是1.28402771，對應(yīng)的特征向量是。

第五步，將樣本點(diǎn)投影到選取的特征向量上。假設(shè)樣例數(shù)為m，特征數(shù)為n，減去均值后的樣本矩陣為DataAdjust(m*n)，協(xié)方差矩陣是n*n，選取的k個特征向量組成的矩陣為EigenVectors(n*k)。那么投影后的數(shù)據(jù)FinalData為

這里是

FinalData(10*1) = DataAdjust(10*2矩陣)×特征向量

得到結(jié)果是

這樣，就將原始樣例的n維特征變成了k維，這k維就是原始特征在k維上的投影。

上面的數(shù)據(jù)可以認(rèn)為是learn和study特征融合為一個新的特征叫做LS特征，該特征基本上代表了這兩個特征。

上述過程有個圖描述：

正號表示預(yù)處理后的樣本點(diǎn)，斜著的兩條線就分別是正交的特征向量（由于協(xié)方差矩陣是對稱的，因此其特征向量正交），最后一步的矩陣乘法就是將原始樣本點(diǎn)分別往特征向量對應(yīng)的軸上做投影。

如果取的k=2，那么結(jié)果是

這就是經(jīng)過PCA處理后的樣本數(shù)據(jù)，水平軸（上面舉例為LS特征）基本上可以代表全部樣本點(diǎn)。整個過程看起來就像將坐標(biāo)系做了旋轉(zhuǎn)，當(dāng)然二維可以圖形化表示，高維就不行了。上面的如果k=1，那么只會留下這里的水平軸，軸上是所有點(diǎn)在該軸的投影。

這樣PCA的過程基本結(jié)束。在第一步減均值之后，其實(shí)應(yīng)該還有一步對特征做方差歸一化。比如一個特征是汽車速度（0到100），一個是汽車的座位數(shù)（2到6），顯然第二個的方差比第一個小。因此，如果樣本特征中存在這種情況，那么在第一步之后，求每個特征的標(biāo)準(zhǔn)差，然后對每個樣例在該特征下的數(shù)據(jù)除以。

歸納一下，使用我們之前熟悉的表示方法，在求協(xié)方差之前的步驟是：

其中是樣例，共m個，每個樣例n個特征，也就是說是n維向量。是第i個樣例的第j個特征。是樣例均值。是第j個特征的標(biāo)準(zhǔn)差。

整個PCA過程貌似及其簡單，就是求協(xié)方差的特征值和特征向量，然后做數(shù)據(jù)轉(zhuǎn)換。但是有沒有覺得很神奇，為什么求協(xié)方差的特征向量就是最理想的k維向量？其背后隱藏的意義是什么？整個PCA的意義是什么？

3. PCA理論基礎(chǔ)

要解釋為什么協(xié)方差矩陣的特征向量就是k維理想特征，我看到的有三個理論：分別是最大方差理論、最小錯誤理論和坐標(biāo)軸相關(guān)度理論。這里簡單探討前兩種，最后一種在討論PCA意義時簡單概述。

3.1 最大方差理論

在信號處理中認(rèn)為信號具有較大的方差，噪聲有較小的方差，信噪比就是信號與噪聲的方差比，越大越好。如前面的圖，樣本在橫軸上的投影方差較大，在縱軸上的投影方差較小，那么認(rèn)為縱軸上的投影是由噪聲引起的。

因此我們認(rèn)為，最好的k維特征是將n維樣本點(diǎn)轉(zhuǎn)換為k維后，每一維上的樣本方差都很大。

比如下圖有5個樣本點(diǎn)：（已經(jīng)做過預(yù)處理，均值為0，特征方差歸一）

下面將樣本投影到某一維上，這里用一條過原點(diǎn)的直線表示（前處理的過程實(shí)質(zhì)是將原點(diǎn)移到樣本點(diǎn)的中心點(diǎn)）。

假設(shè)我們選擇兩條不同的直線做投影，那么左右兩條中哪個好呢？根據(jù)我們之前的方差最大化理論，左邊的好，因?yàn)橥队昂蟮臉颖军c(diǎn)之間方差最大。

這里先解釋一下投影的概念：

紅色點(diǎn)表示樣例，藍(lán)色點(diǎn)表示在u上的投影，u是直線的斜率也是直線的方向向量，而且是單位向量。藍(lán)色點(diǎn)是在u上的投影點(diǎn)，離原點(diǎn)的距離是（即或者）由于這些樣本點(diǎn)（樣例）的每一維特征均值都為0，因此投影到u上的樣本點(diǎn)（只有一個到原點(diǎn)的距離值）的均值仍然是0。

回到上面左右圖中的左圖，我們要求的是最佳的u，使得投影后的樣本點(diǎn)方差最大。

由于投影后均值為0，因此方差為：

中間那部分很熟悉啊，不就是樣本特征的協(xié)方差矩陣么（的均值為0，一般協(xié)方差矩陣都除以m-1，這里用m）。

用來表示，表示，那么上式寫作

由于u是單位向量，即，上式兩邊都左乘u得，

即

We got it！就是的特征值，u是特征向量。最佳的投影直線是特征值最大時對應(yīng)的特征向量，其次是第二大對應(yīng)的特征向量，依次類推。數(shù)據(jù)分析師培訓(xùn)

因此，我們只需要對協(xié)方差矩陣進(jìn)行特征值分解，得到的前k大特征值對應(yīng)的特征向量就是最佳的k維新特征，而且這k維新特征是正交的。得到前k個u以后，樣例通過以下變換可以得到新的樣本。

其中的第j維就是上的投影。

通過選取最大的k個u，使得方差較小的特征（如噪聲）被丟棄。