Stanford機器學習-數據降維

本欄目（Machine learning）包括單參數的線性回歸、多參數的線性回歸、Octave Tutorial、Logistic Regression、Regularization、神經網路、機器學習系統設計、SVM（Support Vector Machines 支持向量機）、聚類、降維、異常檢測、大規模機器學習等章節。內容大多來自Standford公開課machine learning中Andrew老師的講解和其他書籍的借鑒。（https://class.coursera.org/ml/class/index）

PS: 盼望已久的十一長假就要到了~祝大家國慶快樂，玩的開心！(*^__^*)

第十講. 降維——Dimensionality Reduction

===============================

（一）、為什麼要降維?

（二）、主成分分析Principal Component Analysis(PCA)

（三）、PCA 演算法流程

（四）、從壓縮數據中恢復原數據

（五）、怎樣決定降維個數/主成分個數

（六）、應用PCA進行降維的建議

本章主要講述應用PCA演算法進行數據降維的原理

=====================================

（一）、為什麼要降維？

About data：

我們需要一組關於XXX的數據，定義就鋪天蓋地的來了，百萬級個特徵拿過來，我們怎麼進行機器學習啊？！李航老師在他的博客《機器學習新動向：從人機交互中》中提到，學習精度越高，學習確信度越高，學習模型越複雜，所需要的樣本也就越多。樣本複雜度滿足以下不等式

由此可見，feature太多會造成模型複雜，訓練速度過慢，因此我們引入降維。

About Visualization：

多維數據很難進行可視化分析，因此我們需要降維分析。

=====================================

（二）、AboutPrincipal Component Analysis (PCA)

PCA 目的：降維——find a low dimension surface on which to project data ~

如圖所示，藍色的點project到紅色surface上得到綠點，尋找surface使得兩點之間的orthogonal distance總和最小，就是PCA的任務。

PCA 與 Linear Regression 的區別：

1. PCA衡量的是orthogonal distance, 而linear regression是所有x點對應的真實值y=g(x)與估計值f(x)之間的vertical distance距離2. more general 的解釋：PCA中為的是尋找一個surface，將各feature{x1,x2,...,xn}投影到這個surface後使得各點間variance最大（跟y沒有關係，是尋找最能夠表現這些feature的一個平面）；而Linear Regression是給出{x1,x2,...,xn}，希望根據x去預測y，所以進行回歸

=====================================

（三）、PCA 演算法流程

假設有m個samples，每個數據有n維。----------------------------------------數據預處理----------------------------------------1.計算各個feature的平均值，計μj ;（X_j⁽ⁱ⁾表示第i個樣本的第j維特徵的value）

μj = Σ_mX_j⁽ⁱ⁾/m

2.將每一個feature scaling：將在不同scale上的feature進行歸一化；3.將特徵進行mean normalization令X_j⁽ⁱ⁾= (X_j⁽ⁱ⁾-μ_j)/s_j這樣呢，我們需要做的就是兩件事：第一，如何尋找這個surface？第二，給定surface，怎樣求點到surface投影的value？---------------------------------------PCA演算法選取k個主分量----------------------------------------4.求n?n的協方差矩陣Σ：

5. 根據SVD求取特徵值和特徵向量：[U,S,V] = SVD（Σ）其中，SVD為奇異值分解（singular value decomposition），在matlab中有函數[U,S,V] = svd(A) 返回一個與A同大小的對角矩陣S（由Σ的特徵值組成），兩個酉矩陣U和V，且滿足= U*S*V"。若A為m?n陣，則U為m?m陣，V為n?n陣。奇異值在S的對角線上，非負且按降序排列。那麼對於方陣Σ呢，就有Σ = USV"ΣΣ" = USV"*VS"U" = U(ΣΣ")U"Σ"Σ = VS"U"*USV" = V(Σ"Σ)V"i.e. U是ΣΣ"的特徵向量矩陣；V是Σ"Σ的特徵向量矩陣，都是n*n的矩陣由於方陣的SVD相當於特徵值分解，所以事實上U = V, 即Σ = USU", U是特徵向量組成的正交矩陣我們的目的是，從n維降維到k維，也就是選出這n個特徵中最重要的k個，也就是選出特徵值最大的k個~so...goto next step6. 按特徵值從大到小排列，重新組織U如果使用matlab的svd求得特徵值，就可以直接跳過這步了，因為該函數返回值中，奇異值在S的對角線上按照降序排列。否則的話應進行排序，並按照該次序找到對應的特徵向量重新排列。7. 選擇k個分量按照第五、六步中講的svd過後，我們得到了一個n?n的矩陣Σ和U，這時，我們就需要從U中選出k個最重要的分量；即選擇前k個特徵向量，即為U_reduce, 該矩陣大小為n?k

這樣對於一個n維向量x，就可以降維到k維向量z了：

=====================================

（四）、從壓縮數據中恢復原數據

我們已經知道，可以根據z⁽ⁱ⁾= U_reduce"? x⁽ⁱ⁾將n維向量x降維到k維向量z，那麼有時我們需要恢復n維向量，怎麼做呢？由於U_reduce是正交矩陣（下面U_reduce簡記為U），即U" =U^-1, 所以x_approx=(U")^-1?z =(U^-1)^-1?z = Uz(PS：這裡的逆操作為偽逆操作)注意：這裡恢復出的x_approx並不是原先的x，而是向量x的近似值。

=====================================

（五）、怎樣決定降維個數/主成分個數

首先從一個general一點的思路去想呢，我們是希望，選出主成分之後進行數據分析，不會造成大量特徵的丟失，也就是說可以用下式的error ratio表示經過壓縮後的性能如何。error ratio =

然後呢，我們定義一個threshold（10% for example）,如果error ratio<threshold，說明這樣選取主成分是可以接受的，else not從數學上可以證明，上面這個error ratio 可以表示為

所以，可以用下式進行k的合理選取：

=====================================

（六）、應用PCA進行降維的建議

1. PCA可以降維，那讓我們聯想到了之前說過擬合問題是由維度過高或者參數過多造成的，那麼可不可以用PCA解決overfitting的問題呢？

Ans：NO！應用PCA提取主成分可能會解決一些overfitting的問題，但是呢，不建議用這種方法解決overfitting問題，還是建議用第三章中講過的加入regularization項（也稱為ridge regression）來解決。

2. PCA中主成分分析應用到那部分數據呢？

Ans：Only Training Data！可以用Cross-Validation data 和 test Data進行檢驗，但是選擇主分量的時候只應用training data.

3. 不要盲目PCA

Notice：only 當你在原數據上跑到了一個比較好的結果，又嫌它太慢的時候才採取PCA進行降維，不然降了半天白降了~

關於Machine Learning更多的學習資料將繼續更新，敬請關注本博客和新浪微博Sophia_qing。

推薦閱讀：