主成份分析算法 PCA

維數約減

維數約減 (Dimensionality Reduction) 是把 高維度數據 在 損失最小 的情況下轉換為 低維度數據 的動作。

動機：為什么需要維數約減

動機一：數據壓縮

維數約減即減少數據的維度，比如從 2 維降成 1 維，從 3 維降成 2 維等。好處是節省內存，提高運算速度。比如，我們有多個特征，其中兩個特征的相關性非常大，一個是用 cm 測量的長度，另外一個是用 inch 測量的長度 (實際上這可能是個真實的例子，因為一個實際問題可能有 1000 個特征，而采集這些特征的工程師可能不是同一個人，這樣他們采集回來的數據就可能存在重復，即高相關性)。那么我們可以把這兩個高相關性的特征用一條直線來表示，$x^{(i)} = {x_1^{(i)}, x_2^{(i)}}$ 簡化為 $z^{(i)} = {z_1^{(i)}}$。相同的原理，如果在一個 3 維空間里，一些點基本分布在一個平面上，那么就可以把 3 維降成 2 維，即 $x^{(i)} = {x_1^{(i)}, x_2^{(i)}, x_3^{(i)}}$ 簡化為 $z^{(i)} = {z_1^{(i)}, z_2^{(i)}}$。

數據壓縮

上圖示例的就是把用英寸測量的特征和用厘米測量的特征合并起來的示意圖。這里有個問題，為什么按 inch 測量的特征和按 cm 測量的特征不是在同一條直線上，而是在一條直線周圍波動？實際上這個是正常的，因為測量的人和誤差等方面的原因，會導致特征采集時數據會在誤差范圍內波動。

動機二：數據可視化

比如考查一個國家的經濟狀況，可能會有 50 個特征，經濟總量，人均 GDP，出口值，進口值等等。如果想要直觀地觀察多個特征之間的關系，就比較難辦。因為我們很難畫出 50 個特征的圖出來。這個時候，我們可以把 50 個特征簡化為 2 維或 3 維的數據，然后畫出 2D 或 3D 圖出來，就可以直觀地觀察這些數據的樣子。

主成份分析法

主成份分析法簡稱 PCA (Principal Component Analysis)，這是目前最常用和流行的數據降維方法。

假設需要把 2 維數據降為 1 維數據時，我們需要找出一個向量 $u^{(1)}$ ，以便讓 2 維數據的點在這個向量所在的直線上的 投射誤差最小 。

PCA - 2D to 1D

上圖中，我們的目標就是找到紅色的向量所在的直線，以便讓所有黑色的點到這條直線的平均距離最短，這樣我們就可以把原來在二維平面上的點映射到在紅色直線所在的一維直線上的綠色的點來表示。即把二維數據降為一維數據。

假如需要把 3 維數據降為 2 維數據時，我們需要找出兩個向量 $u^{(1)}, u^{(2)}$，以便讓 3 維數據的點在這兩個向量所決定的平面上的投射誤差最小。

從數學角度更一般地描述 PCA 算法，當我們需要從 n 維數據降為 k 維數據時，我們需要找出 k 個向量 $u^{(1)}, u^{(2)}, ... , u^{(k)}$ ，把 n 維的數據投射到這 k 個向量決定的線性空間里，最終使 投射誤差最小化 的過程。

PCA 算法主要步驟

步驟一：數據歸一化和縮放

在進行 PCA 算法前，需要對數據進行預處理。預處理包括兩個步驟：

• 數據歸一化 (Mean Normalization)：使數據的均值為零。加快 PCA 運算速度。
• 數據縮放 (Feature Scaling)：使不同的特征數值在同一個數量級。

數據歸一化公式為：

其中，$\mu_j$ 是訓練樣本中第 j 個特征 ($x_j^{(i)}$) 的平均值。然后用 $z_j^{(i)}$ 代替 $x_j^{(i)}$ 進行 PCA 運算。

接著對數據進行縮放，縮放只在不同特征數據不在同一個數量級上時才使用。

其中，$\mu_j$ 是訓練樣本中第 j 個特征 ($x_j^{(i)}$) 的平均值

$s_j$ 是訓練樣本中第 j 個特征 ($x_j^{(i)}$) 的范圍，即 $s_j = max(x_j^{(i)}) - min(x_j^{(i)})$。

步驟二：計算協方差矩陣的特征向量

數據預處理完，我們需要計算 協方差矩陣 (Covariance Matrix) ，用大寫的 Sigma 表示 (大寫的 Sigma 和累加運算符看起來幾乎一樣，但這里其實是一個數學符號而已，不是累加運算)：

如果把訓練樣例用行向量來表示，那么 X 將是一個 m x n 的矩陣，m 是訓練樣例個數，n 是特征個數。向量化計算 Sigma 的公式將是：

計算結果 Sigma 將是一個 n x n 矩陣。接著，計算協方差矩陣的 特征向量 (eigenvectors) ：

svd是奇異值分解 (Singular Value Decomposition)，是高級線性代數的內容。在 Octave 里，也可以使用eig函數來求解協方差矩陣的特征向量。這里，Sigma 是 n x n 矩陣，經過svd運算后，我們真正關心的是 U。它是一個 n x n 矩陣。如果我們選擇 U 的列作為向量，那么我們得到 n 個列向量 $u^{(1)}, u^{(2)}, ... , u^{(n)}$，我們如果需要把數據降維為 k 維，那么我們只需要選取前 k 個向量即可，即 $u^{(1)}, u^{(2)}, ... , u^{(k)}$。

步驟三：數據降維

接著，我們計算降維后的值 z，假設降維前的值為 $x^{(i)}$，降維后為 $z^{(i)}$，那么：

其中，$U_{reduce} = [u^{(1)} u^{(2)} ... u^{(k)}]$。看一下數據維度，$U_{reduce}$ 是 n x k 矩陣，$x^{(i)}$ 是 n x 1 矩陣，$z^{(i)}$ 是 k x 1 矩陣。

實現時可以用向量化來提高性能。假設 X 是 m x n 矩陣，m 表示訓練樣例個數，n 表示特征數。用大寫的 Z 表示降維后的數據，是一個 m x k 的矩陣。$U_{reduce}$ 是 n x k 的主成份特征矩陣，每列表示一個主成份特征。那么他們滿足下面的關系：

要從數學上證明這樣計算出來的 $z^{(i)}$ 就是 $x^{(i)}$ 在 $U_{reduce}$ 線性空間投射，使得其投射誤差最小，將是一個非常復雜的過程。所幸如果我們單純從應用 PCA 算法來對數據進行降維的角度來看的話，借用 Octave/Matlab 等現成函數，計算過程相對比較簡單。

PCA 的應用

數據還原

我們怎么樣從壓縮過的數據里還原出壓縮前的數據呢？從前文的計算公式，我們知道降維后的數據計算公式 $z^{(i)} = U_{reduce}^T x^{(i)}$。所以，如果要還原數據，我們可以使用下面的公式：

其中，$U_{reduce}$ 是 n x k 維矩陣，$z^{(i)}$ 是 k x 1 列向量。這樣算出來的 $x^{(i)}$ 就是 n x 1 列向量。

向量化運算公式為：

其中 $X_{approx}$ 是還原回來的數據，是個 m x n 矩陣，每行表示一個訓練樣例。Z 是個 m x k 矩陣，是壓縮后的數據。$U_{reduce}$ 是 n x k 的主成份特征矩陣，每列表示一個主成份特征。

PCA 算法中 K 參數的選擇

怎么樣選擇參數 K 呢？K 是主成份分析法中主成份的個數。可以用下面的公式來判斷選擇的 K 是否合適：

其中分子部分表示平均投射誤差的平方；分母部分表示所有訓練樣例到原點的距離的平均值。這里的物理意義用術語可以描述為 99% 的數據真實性被保留下來了 (99% of variance is retianed) 。簡單地理解為壓縮后的數據還原出原數據的的準確度為 99%。另外常用的比率還有 0.05 ，這個時候準確度就是 95%。在實際應用中，可以根據要解決的問題的場景來決定這個比率。

假設我們的還原率要求是 99%，那么用下面的算法來選擇參數 K：

1. 讓 K = 1
2. 運行 PCA 算法，計算出 $U_{reduce}, z^{(1)}, z^{(2)}, ... , z^{(m)}, x_{approx}^{(1)}, x_{approx}^{(2)}, ... , x_{approx}^{(m)}$
3. 利用 $\frac{ \frac{1}{m} \sum_{i-1}^m \| x^{(i)} - x_{approx}^{(i)} \|^2 }{ \frac{1}{m} \sum_{i=1}^m \| x^{(i)} \| }$ 計算投射誤差率，并判斷是否滿足要求，如果不滿足要求，K = K + 1，繼續步驟 2；如果滿足要求，K 即是我們選擇的參數

這個算法容易理解，但實際上效率非常低下，因為每做一次循環都需要運行一遍 PCA 算法。另外一個更高效的方法是利用svd函數返回的 S 矩陣：$[U, S, V] = svd(Sigma)$。其中 S 是個 n x n 對角矩陣，即只有對角線上的值非零其他元素均為零。

從數學上可以證明（從應用角度，可以忽略這個證明過程），投射誤差率也可以使用下面的公式計算：

這樣運算效率大大提高，我們只需要調用一次svd函數即可。

加快監督機器學習算法的運算速度

PCA 的一個典型應用是用來 加快監督學習 (Supervised Learning) 的速度 。

比如，我們有 m 個訓練數據 $(x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), ... , (x^{(m)}, y^{(m)})$，其中 $x^{(1)}$ 是 10,000 維的數據，想像一下，如果這是個圖片分類問題，如果輸入的圖片是 100 x 100 分辨率的。那么我們就有 10,000 維的輸入數據。

使用 PCA 來加快算法運算速度時，我們把輸入數據分解出來 $x^{(1)}, x^{(2)}, ... , x^{(m)}$，然后運用 PCA 算法對輸入數據進行降維壓縮，得到降維后的數據 $z^{(1)}, z^{(2)}, ... , z^{(m)}$，最后得到新的訓練樣例 $(z^{(1)}, y^{(1)}), (z^{(2)}, y^{(2)}), ... , (z^{(m)}, y^{(m)})$。利用新的訓練樣例訓練出關于壓縮后的變量 $z$ 的預測函數 $h_\theta(z)$。

需要注意，PCA 算法只用來處理訓練樣例，運行 PCA 算法得到的轉換參數 $U_{reduce}$ 可以用來對交叉驗證數據集 $x_{cv}^{(i)}$ 以及測試數據集 $x_{test}^{(i)}$ 進行轉換。當然，還需要相應地對數據進行歸一化處理或對數據進行縮放。

PCA 誤用

PCA 的典型應用場景是對數據進行壓縮，減少磁盤/內存占用，加快算法運行速度。另外一個是用來數據可視化 (降到 2 維或 3 維)。我們了解到 PCA 可以對數據進行降維，即減少特征數，有人用 PCA 來解決 過擬合 問題。這可能在某些情況下會起作用，但實際上 PCA 不是一個好的解決過擬合的方法 。解決過擬合應該使用正則化，加大成本函數里正則項的比重。

PCA 濫用

另外一個場景是在設計機器學習算法時，一開始就引入 PCA 來對數據進行壓縮降維。實際上這不是好的方法。我們應該盡量使用原始數據來進行機器學習運算，當出現問題時，比如內存占用太大，運算時間太長等問題時，我們才考慮用 PCA 來優化。PCA 是算法優化的一個步驟，而不是機器學習系統里的必須步驟。