特征选择和特征提取
參考文獻1：PCA的數學原理（講得極好）
參考文獻2：《機器學習導論》
題外話：
上次，參加國內業界最牛逼之一的格林深瞳的筆試和面試，沒想到竟然都通過了。高興之余，實際上，還有很長的路要走。
說實話，也是有點幸運，出了很多畢設相關的視覺知識。畢設做得很認真，然后面試時，我自然和面試的那位年輕小伙講得滔滔不絕。但是第二關是相關的機器學習和深度學習的知識。機器學習我能答上，深度學習就有點措手不及（實際上筆試中相關的深度學習題目我做得不怎么樣）。其中一個就是PCA降維。這個東西很早就想看，一直推來推去。現在正式進入主題：
為何降維？
特征選擇：從原始輸入向量d維中選出信息量最多的k維，并丟棄（d-k）維，記為x（k維）
特征提取：d維向量x投影到k維的x'。這些方法可以是監督的，也可以是非監督的。
雖然，分類方法或回歸方法應該能夠利用任何必要的特征，而丟棄不想關的特征。然而，有許多原因使得我們對把降維作為一個單獨的預處理步驟感興趣。
1）算法的復雜度依賴于樣本維度d和樣本數量N
2）如果輸入是不必要的，我們就節省了它的開銷
3）較簡單的模型更為魯棒
特征選擇——子集選擇：
d個變量有2d個可能的子集。除非d很小，一般我們不可能對所有的子集進行檢驗。通常會采用啟發式的方式。
有兩種啟發式的方式：向前選擇和向后選擇
向前選擇（偽代碼）：
（1）令子集為F，初始化為F={?}，T={xi|i=1,...,d}。
（2）計算誤差j=argmin（i）E(F∪xi)
（3）IF E小于閥值||E不會減少
（i）算法終止：exit（）
ELSE
（ii）F=F∪xj，且T=T-xj
（4）goto（2）
問題和改進：
1）搜索復雜度為d+(d-1)+...+(d-k)=O(d2)
2）可能兩個特征本身都不好，但是兩者合在一起，作用卻很大。可能一個解決方法是依次添加m個而不是1個。或者通過回溯并且檢查以前添加的哪個特征可以去掉，但搜索速度慢，一個算法是：浮動搜索可以解決一些問題。
向后選擇：則是首先包括所有特征，然后每次踢掉一個特征，并且是去掉導致誤差最小的那個。
對比：如果我們預料到有許多無用的特征，向前搜索更可取。
缺點：在像人臉識別這樣的應用中，特征選擇不是降維的好方法，因為個體像素本身并不攜帶很多識別信息；攜帶臉部識別信息的是許多像素值的組合。
特征提取——主成分分析：
雖然上圖中提到了許多方法，但是這里我只討論主成分分析：
（1）內積——投影（我似乎悟到了歸一化向量的內積能體現向量的相似度，即夾角能體現相似度）
（2）矩陣相乘A×B：看成A×Bi(Bi為B的第i列)，于是，看成B矩陣中每一列形成的向量在A（A由創建的一組基一行一行地躺下來形成的）的投影。
（3）如何選擇基：選擇不同的基可以對同樣一組數據給出不同的表示，而且如果基的數量少于向量本身的維數，則可以達到降維的效果。但是我們還沒有回答一個最最關鍵的問題：如何選擇基才是最優的。或者說，如果我們有一組N維向量，現在要將其降到K維（K小于N），那么我們應該如何選擇K個基才能最大程度保留原有的信息？
（4）那么如何選擇這個方向（或者說基）才能盡量保留最多的原始信息呢？一種直觀的看法是：希望投影后的投影值盡可能分散。我們希望投影后投影值盡可能分散，而這種分散程度，可以用數學上的方差來表述。
（5）投影到一維的情況：通常，我們事先讓投影后的所有值組成的向量的每個分量減去該分量的均值。這樣，（4）中所提到的方差，在這步之后，就等于求每個值得平方和。簡化了問題。
（6）于是上面的問題被形式化表述為：尋找一組基，使得所有數據變換為這個基上的坐標表示后，方差值最大。
（7）直觀上，強調的是，對于二維降到一維，投影之后，我們就得到了一堆標量，然后求其平方和，使之最小化。對于A為m×n的矩陣。即有m個基躺下來。先考慮一個基，每一個數據過來，和它做內積，就變成了一個標量，...，N個數據得到N個標量。計算其離散度，即平法和。同樣地，對第二個、第三個，...，第m個基都是如此。最終把所有的離散度（平法和）加起來優化。其中，物理上，m個其代表數據從m個方向投影，希望每個方向投影的離散度結果之和最大化。
（8）在（7）中說的很好了，但問題來了，我們總能夠找到一個使方差最大的的基，那我找第二個基的時候，也找相同的基好了，或者稍微偏一點點，那也能接近地找到最大的方差。這么說來，問題就大了，所有基方向都趨于相同。怪怪的！
（9）我們想找到其他的約束條件來解決這個問題。從直觀上說，讓兩個字段盡可能表示更多的原始信息，我們是不希望它們之間存在（線性）相關性的，因為相關性意味著兩個字段不是完全獨立，必然存在重復表示的信息。
（10）在原坐標基上，顯然每個實例向量的各個分量之間的協方差是客觀存在，不能改變的了。但是，我們希望投影后，得到的新維度的實例向量的各個分量之間的協方差為0，是它們完全獨立，沒有冗余的信息量，同樣的數據比特，當然沒有冗余信息（之間完全獨立最好，而不是幾個數據或幾個變量來表達一個變量的信息）。那么，我們在第一個基方向選定以后（更加最大方差），然后，選擇第二個方向和第一個方向正交（垂直）的方向，同時，我們還想在這個約束條件下方差最大化！同樣地，選第三個方向和第一個、第二個方向正交，同時在這個約束條件下，最大化方差，依次類推，直到滿足終止條件。
（11）至此，我們得到了降維問題的優化目標：將一組N維向量降為K維（K大于0，小于N），其目標是選擇K個單位（模為1）正交基，使得原始數據變換到這組基上后，各字段兩兩間協方差為0，而字段的方差則盡可能大（在正交的約束下，取最大的K個方差）。
（12）考慮一個問題：
我們看到，最終要達到的目的與實例向量各個分量內方差及實例向量各個分量間協方差有密切關系。因此我們希望能將兩者統一表示，仔細觀察發現，兩者均可以表示為內積的形式，而內積又與矩陣相乘密切相關。于是我們來了靈感：
假設我們只有a和b兩個實例向量，那么我們將它們按行組成矩陣X：
其中，AA,BB,AB,BA分別是a分量的方差，b分量的方差，a、b之間的協方差，b、a之間的協方差。
根據矩陣相乘的運算法則，這個結論很容易被推廣到一般情況：
設我們有m個n維數據記錄，將其按列排成n乘m的矩陣X，設C=frac{1}{m}XX^mathsf{T}，則C是一個對稱矩陣，其對角線分別個各個分量的方差，而第i行j列和j行i列元素相同，表示i和j兩個分量的協方差。
重述一下我們的目標：
（1）希望投影的第一個方向的方差最大。
（2）希望投影的第二個方向與第一個方向正交（協方差為零）且使它的方差最大化。
我們已經可以想象到未來的美好景象：
各個方向投影后：它是一個對角化的方陣，且對角元素從左上角到右下角依次減小。方陣的維數取決于算法終止的時刻。
（13）根據上述推導，我們發現要達到優化目前，等價于將協方差矩陣對角化：即除對角線外的其它元素化為0，并且在對角線上將元素按大小從上到下排列，這樣我們就達到了優化目的。
（14）現在事情很明白了！我們要找的P不是別的，而是能讓原始協方差矩陣對角化的P。換句話說，優化目標變成了尋找一個矩陣P，滿足PCP^mathsf{T}是一個對角矩陣，并且對角元素按從大到小依次排列，那么P的前K行就是要尋找的基，用P的前K行組成的矩陣乘以X就使得X從N維降到了K維并滿足上述優化條件。
（15）現在所有焦點都聚焦在了協方差矩陣對角化問題上，有時，我們真應該感謝數學家的先行，因為矩陣對角化在線性代數領域已經屬于被玩爛了的東西，所以這在數學上根本不是問題。
（16）
由上文知道，協方差矩陣C是一個是對稱矩陣，在線性代數上，實對稱矩陣有一系列非常好的性質：
1）實對稱矩陣不同特征值對應的特征向量必然正交。
2）設特征向量lambda重數為r，則必然存在r個線性無關的特征向量對應于lambda，因此可以將這r個特征向量單位正交化。
由上面兩條可知，一個n行n列的實對稱矩陣一定可以找到n個單位正交特征向量，設這n個特征向量為e_1,e_2,cdots,e_n，我們將其按列組成矩陣：
E=egin{pmatrix} e_1 & e_2 & cdots & e_n end{pmatrix}
則對協方差矩陣C有如下結論：
E^mathsf{T}CE=Lambda=egin{pmatrix} lambda_1 & & & \ & lambda_2 & & \ & & ddots & \ & & & lambda_n end{pmatrix}
其中Lambda為對角矩陣，其對角元素為各特征向量對應的特征值（可能有重復）。
以上結論不再給出嚴格的數學證明，對證明感興趣的朋友可以參考線性代數書籍關于“實對稱矩陣對角化”的內容。
到這里，我們發現我們已經找到了需要的矩陣P：
P=E^mathsf{T}
P是協方差矩陣的特征向量單位化后按行排列出的矩陣，其中每一行都是C的一個特征向量。如果設P按照Lambda中特征值的從大到小，將特征向量從上到下排列，則用P的前K行組成的矩陣乘以原始數據矩陣X，就得到了我們需要的降維后的數據矩陣Y。
（17）
PCA算法
總結一下PCA的算法步驟：
設有m條n維數據。
1）將原始數據按列組成n行m列矩陣X
2）將X的每一行（代表一個屬性字段）進行零均值化，即減去這一行的均值
3）求出協方差矩陣C=frac{1}{m}XX^mathsf{T}
4）求出協方差矩陣的特征值及對應的特征向量
5）將特征向量按對應特征值大小從上到下按行排列成矩陣，取前k行組成矩陣P
6）Y=PX即為降維到k維后的數據
（18）例子略（詳見參考文獻1）
總結
- 上一篇： python替换字符的操作_Python
- 下一篇： c#与java_C#与Java的区别