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

### 使用降維的原因

1. 資料壓縮

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


* 將 2 維降為 1 維

2. 資料可視化

* 將多維降到 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`