[筆記] 機器學習 降維 ( Dimension Reduction ) 與 PCA

使用降維的原因

1. 資料壓縮

   • 降低記憶體佔用空間
   • 增加運算效率

• 將 2 維降為 1 維

1. 資料可視化

   • 將多維降到 2 維或 3 維
   • 進行資料可視化，可以更了解資料

• 多維資料

• 降為 2 維並可視化

主成成分分析法 PCA ( Principal Componet Analysis )

• PCA 的目的為 : 假設我們要將資料從 n 維降到 k 維，找到 k 個向量 u⁽¹⁾，u⁽²⁾，…，u^(k)，將資料投影到這些向量時，投影距離誤差能夠最小化

  • PCA 與線性回歸的差別

    • PCA : 目的為找出最小化的投影距離，最小化的是與直線的垂直距離

      

    • 線性回歸 : 目的為給定一個 x 可以預測出 y，最小化的是實際 y 與預測 y 的距離

      

資料預處理

• PCA 前須先進行特徵縮放與均值歸一化
• 特徵縮放與均值歸一化 : $\dfrac{x_j^{(i)} - μ_j}{s_j}$

算法

• 假設將資料從 n 維降到 k 維

1. 計算協方差矩陣 Σ ( covariance matrix )

   • Σ =

   • Σ 為 n * n 矩陣

     Sigma = (1 / m) * X' * X;

2. 計算 Σ 的特徵向量 ( eigenvectors )

   [U, S, V] = svd(Sigma);
   Ureduce = U(:, 1:k);
   z = Ureduce' * x;

   • svd() 為奇異值分解 ( singular value decomposition )
   • eig() 是不同的函式，但也能得到相同結果，svd() 相對穩定

   • 真正需要的會是 U 矩陣，U 矩陣為 n n 矩陣，只要取出前 k 列 ( column )，就是我們需要的 u⁽¹⁾，u⁽²⁾，…，u^(k)，取出後為 n k 矩陣

     • 

   • 計算 z

     • z = [u⁽¹⁾ u⁽²⁾ … u^(k)]^Tx
     • z 為 k * 1 矩陣

function [U, S] = pca(X)

[m, n] = size(X);

U = zeros(n);
S = zeros(n);

Sigma = (1 / m) * X' * X;
[U, S, V] = svd(Sigma);

end

• 在 Octave 上 PCA 的函式

function Z = projectData(X, U, K)

Z = zeros(size(X, 1), K);

Ureduce = U(:, 1:K);
Z = X * Ureduce;

end

• 在 Octave 上算出 Z 的函式

重建原始資料

• 原始資料 :

  

• z 的算法 : z = $U_{reduce}^Tx$

• 降維後 :

  

• 還原 x : x_approx = U_reducez

• 還原後 :

  

function X_rec = recoverData(Z, U, K)

X_rec = zeros(size(Z, 1), size(U, 1));
            
Ureduce = U(:, 1:K);
X_rec = Z * Ureduce'

end

• 在 Octave 上算出 x_approx 的函式

如何選擇 k

• 將資料從 n 維降到 k 維
• k 又被稱作主成分的數量

• 平均平方映射誤差 ( Average Squared Projection Error ) :

  • $\dfrac{1}{m}\sum{i = 1}^{m}||x^{(i)} - x{approx}^{(i)}||^2$
  • 原始資料 $x^{(i)}$ 和映射值 $x_{approx}^{(i)}$ 之間的差
  • PCA 的目的就是縮小這個差距

• 資料的總變差 ( (Total Variation ) :

  • $\dfrac{1}{m}\sum_{i = 1}^{m}||x^{(i)}||^2$
  • 平均來看，訓練資料距離零向量多遠

• 選擇 k 的方法 :

  • $\dfrac{\dfrac{1}{m}\sum{i = 1}^{m}||x^{(i)} - x{approx}^{(i)}||^2}{\dfrac{1}{m}\sum_{i = 1}^{m}||x^{(i)}||^2} ≤ 0.01$ ( 1% )
  • 通常希望數據的變化誤差較小，會選擇 0.01 ~ 0.05 ( 1% ~ 5% )
  • 設定成小於等於 0.01 可以想成是保留了 99% 的差異性

• 算法 :

  • 使用 PCA 計算 k = 1，2，…
  • 得到 U_reduce，z，x_approx
  • 檢查 $\dfrac{\dfrac{1}{m}\sum{i = 1}^{m}||x^{(i)} - x{approx}^{(i)}||^2}{\dfrac{1}{m}\sum_{i = 1}^{m}||x^{(i)}||^2}$ 是否 ≤ 0.01
  • 直到達成條件

• 使用 svd() 選擇 k 的算法:

  • [U, S, V] = svd(Sigma)，其中的 S = $\begin{bmatrix} S{11} & 0 & 0 & … \ 0 & S{22} & 0 & … \ 0 & 0 & S{33} & … \ … & … & … & S{nn} \end{bmatrix}$

  • $1 - \dfrac{\sum{i = 1}^{k}S{ii}}{\sum{i = 1}^{n}S{ii}} ≤ 0.01$ → $\dfrac{\sum{i = 1}^{k}S{ii}}{\sum{i = 1}^{n}S{ii}} ≥ 0.99$

    • 等於 $\dfrac{\dfrac{1}{m}\sum{i = 1}^{m}||x^{(i)} - x{approx}^{(i)}||^2}{\dfrac{1}{m}\sum_{i = 1}^{m}||x^{(i)}||^2} ≤ 0.01$

  • 這樣就只需要調用一次 svd()，改變 k 就可以持續尋找符合的 k 值

錯誤的使用 PCA

• 不適用於解決過度擬合

  • 因為 PCA 可能會丟棄一些重要訊息
  • 使用正規化較適合

• 不適用於剛開始設計機器學習系統

  • 先使用原始資料訓練，不要一開始就使用 PCA
  • 當發現算法非常緩慢或占用記憶體非常大時，再考慮 PCA

總結

• 降維的目的

  • 減少記憶體的使用
  • 增加運算效率
  • 資料可視化 ( 降到 2 或 3 維 )

tags: 筆記 機器學習 降維 PCA