PCA 主成分分析

# PCA 主成分分析 ***用一句話簡述PCA (Principle Component Analysis): 基底(basis)轉換，將原本的資料集$X$，從目前空間「投影」到子空間上，並建立新的坐標系（coordinate system）*** ## Outline * 功用: 降低資料維度，同時保持每筆資料的**區別性** * 目的: 得到正交投影矩陣$W$，從而得到新的資料集$Z$ * 方法概念: 將原本的資料集$X$，從目前空間(較高維度) 「**正交投影**」到子空間(較低維度)上，用矩陣、線性代數的角度來看這個操作就是 $Z=WX$。 * 優點: 節省內存、計算資源 * 缺點: 降低維度的同時，資料也有所缺失，可能失去關鍵訊息、不是所有資料都適合用PCA處理降低資料維度不是件難事，最粗暴的方法就是將多餘的資料刪除，但這明顯不是最好的方法，也無法保證降維後的資料是可區分，因此對PCA 來說，除了將原本的資料集$X$，投影到一個較低維度空間，最重要的是最大程度保留資料之間的「區別性」，換句話說，就是讓資料集$Z$ 裡的每筆資料彼此總差異越大越好。 ## Problem Formulation 以下用個例子來解釋PCA的用途: > 假設今天有 $n$ 個人的健康檢查報告，每個人都有年齡、身高、體重等等，總共 $m$ 個數值，分別用$x_1, x_2, ..., x_n$ 代表，$x_i$ 是 $m \times 1$ 階的向量 $\ \forall\ i=1,2,...,n$，向量中的每一個元素紀錄不同的檢查數值，醫生想從中許多人的數據中看出不同族群是否存在關連性，但覺得 $m$ 筆資料太複雜，看不出來，因此想把它縮減成 $k$ 筆數據，這時候就可以用到PCA，而要將原本的資料從 $m$ 筆數據變成 $k$ 筆數據，就可以利用正交投影矩陣$W$。 > > 方便以下說明，令 $X= [x_1 \ x_2\cdot\cdot\cdot x_n]$、 $W=\left[ > \begin{array}{ccc} > w_1^T \\ > w_2^T \\ > \cdot\\ > \cdot\\ > w_k^T \\ > \end{array} > \right]$ 分別是 $m \times n$ 階、$k \times m$ 階的矩陣，而 $Z=WX=\left[ > \begin{array}{ccc} > z_1 \\ > z_2 \\ > \cdot\\ > \cdot\\ > z_k \\ > \end{array} > \right]$ 是 $k \times n$ 階的矩陣 \ PCA實際上就是利用一個正交投影矩陣$W$，把原本的資料集$X$ 投影到一個「好的子空間」，而好的子空間應該讓投影後的資料夠分散，換句話說，也就是讓資料集$Z$ 裡的每筆資料彼此總差異越大越好，所以第一個碰到的問題就是**判斷資料差異的度量是甚麼**? > 根據**變異數(Variance)** 定義，變異數是資料的離均差平方總和，幾何上象徵著資料的分散程度，可以當作一種判別資料差異的標準，這也是PCA採取的方式，當然也有其他評估差異的標準，像是MSE、相對差異、絕對差異等等，但不見得存在和變異數相同的好處。既然知道變異數可以用來當作度量衡，那就希望當資料集$X$ 透過正交投影矩陣$W$ 投影到新的座標系的各個坐標軸上時，能得到最大的變異數，事實上，新的座標系的各個坐標軸分別就是$w_1, w_2, ..., w_k$，也就是說，PCA的本質就是**線性組合(linear combination)**，或者說**基底(basis)轉換**: > 將以標準基底(standard basis)為基底的資料集$X$ 轉換成以 $\{w_1, w_2, ..., w_k\}$ 為基底的資料集$Z$ 因此，接下來遇到第二個問題，也是PCA裡最主要的問題: ### 如何找出新的基底$w_1, w_2, ..., w_k$ ? 這裡直接先給答案，正交投影矩陣$W$ 跟資料集$X$ 的**共變異數矩陣(Covariance matrix) $S$** 有關: > $w_1$ 就是共變異數矩陣的最大特徵值(Eigenvalue) 對應到的特徵向量(Eigenvector)，而$w_2$就是第二大Eigenvalue對應到的Eigenvector，以此類推。中文有點繞，或許英文會比較好懂: > $w_1$ is the eigenvector of the covariance matrix corresponding to the largest eigenvalue. 如果想知道更詳細內容，不妨看看以下證明會更清楚來龍去脈。 ## Theorem 根據上述設定，要找出一個 $k \times m$ 階的正交投影矩陣$W$ ，就要依序找出 $k$ 個正交基底，事實上，找出一個子空間的正交基底不是件難事，利用 ***Gram–Schmidt process*** 很快可以解決，但PCA還要考慮到變異數的問題，因此PCA中不使用這個方法。首先，要找出第一個基底 $w_1$，在PCA中也被稱為**第一主成分**，是新的座標系中的一個座標軸， $w_1^TX$ 的幾何意義就是將 $X$ 投影到 $w_1$ 這個新的座標軸上，因此希望經過投影的新座標點在 $w_1$ 軸上足夠分散，也就是找到最大的 $Var(z_1)$。然而，$Var(z_1)=w_1^TSw_1$, where $S$ is the covariance matrix of $X$。 > \begin{split} > Var(z_1) &=& \frac{1}{n}\displaystyle\sum_{z\in z_1}(z-\bar{z_1})^2 = \frac{1}{n}\displaystyle\sum_{i=1}^n(w_1^TX_i-w_1^T\bar{X})^2\\ &=& \frac{1}{n}\displaystyle\sum_{i=1}^n(w_1^T(X_i-\bar{X}))^2 = \frac{1}{n}\displaystyle\sum_{i=1}^nw_1^T(X_i-\bar{X})(X_i-\bar{X})^Tw_1 \\ > &=& w_1^T\ [\frac{1}{n}\displaystyle\sum_{i=1}^n(X_i-\bar{X})(X_i-\bar{X})^T]\ w_1 \\ > &=& w_1^TSw_1 \\ > where, \bar{X}=\cfrac{1}{n}\displaystyle\sum_{i=1}^nX_i > \end{split} --- 因此，變成一個最佳化問題: \begin{gather*} Find\ \ w_1\ \ which\ \ maximizes\ \ w_1^TSw_1\ \ s.t.\ \ \lVert w_1 \rVert=1 \end{gather*} > 使用**拉格朗日乘子**(Lagrange multiplier)可以得到以下 Lagrange Function: > \begin{gather*} > g(w_1)=w_1^TSw_1-\alpha(w_1^Tw_1-1) > \end{gather*} > > 因為共變異數矩陣$S$ 是**對稱(symmetric)** 且 **半正定(positive-semidefinite)** ...[2] > \begin{split} > 0&=&\nabla{g(w_1)}=(S+S^T)w_1-2\alpha w_1 .... [3]\\ > &=& 2Sw_1-2\alpha w_1 > \end{split} > > 因此， > \begin{gather*} > Sw_1-\alpha w_1=0 \\ > Sw_1=\alpha w_1\ \ \ \ ...(1)\\ > w_1^T(Sw_1)=w_1^T(\alpha w_1)=\alpha w_1^Tw_1=\alpha\ \ \ \ ...(2) > \end{gather*} > > 從(1)式可以看出 $\alpha$ 跟 $w_1$ 的關係，分別是對應的特徵值和特徵向量，而(2)式又可以發現 $w_1^TSw_1$ 的最大值就是 $\alpha$，因此可以得知 $w_1$ 就是對應到"共變異數矩陣$S$ 的最大特徵值$\lambda _1$ "的那個"特徵向量"，而 $\lVert w_1 \rVert=1$ 限制條件也可以透過正規化(normalization)輕鬆達成。 --- 找出第一主成分後，就要接著找**第二主成分$w_2$**，一樣也是一個最佳化問題，但限制條件多了一個，因為已經知道 $w_1$，因此在找其他基底時，都要和已經找到的所有基底垂直: \begin{gather*} Find\ \ w_2\ \ which\ \ maximizes\ \ w_2^TSw_2\ \ s.t.\ \ \lVert w_2 \rVert=1\ \ and\ \ w_1^Tw_2=0 \end{gather*} > Lagrange Function: > \begin{gather*} > g(w_2)=w_2^TSw_2-\alpha(w_2^Tw_2-1)-\beta(w_1^Tw_2) \\ > 0=\nabla{g(w_2)}=2Sw_2-2\alpha w_2-\beta w_1 > \end{gather*} > > 因此， > \begin{gather*} > 2Sw_2-2\alpha w_2-\beta w_1=0\ \ \ \ ...(3)\\ > w_1^T(2Sw_2-2\alpha w_2-\beta w_1)=0 \\ > 2w_1^TSw_2-2\alpha w_1^Tw_2-\beta w_1^Tw_1=0 \\ > 2w_1^TSw_2-\beta=0\ \ \ \ ...(4)\\ > \end{gather*} > > 然而，$w_1^TSw_2=(w_1^TSw_2)^T=w_2^TS^Tw_1=w_2^T(Sw_1)=w_2^T(\lambda _1w_1)=\lambda _1w_2^Tw_1=0$ > 因此由(4)式可得出 $\beta=0$，再帶入(3)式: > \begin{gather*} > 2Sw_2-2\alpha w_2=0 \\ > Sw_2=\alpha w_2 \\ > w_2^TSw_2=\alpha w_2^Tw_2=\alpha > \end{gather*} > > 可得到和 $w_1$ 相同的結果，$\alpha$ 跟 $w_2$ 的關係，也是對應的特徵值和特徵向量，而 $w_2^TSw_2$ 的最大值也就是 $\alpha$，然而，為了滿足 $w_1^Tw_2=0$ 的條件，$\alpha$ 不能選擇最大的特徵值，也就是說，$w_2$ 就是對應到"共變異數矩陣$S$ 的第二大特徵值$\lambda _2$ "的那個"特徵向量"，而且因為 $S$ 是一個**實對稱矩陣**，這個特徵向量一定和 $w_1$ 垂直，證明如下[4]: > \begin{split} > \lambda _1\left< w_1, w_2 \right>&=&\left< \lambda _1w_1, w_2 \right>=\left< Sw_1, w_2 \right>=w_1^TS^Tw_2=w_1^TSw_2 \\ > &=&\left< w_1, Sw_2 \right> > = \left< w_1, \lambda _2w_2 \right>=\bar{\lambda _2}\left< w_1, w_2 \right>=\lambda _2\left< w_1, w_2 \right> \\ > 因為 \lambda _1\neq\lambda _2，\left< w_1, w_2 \right>=0 > \end{split} 以此類推，用相同的方法，可以輕鬆證明出 $w_1, w_2,...,w_k$ 分別就是特徵值由大排到小對應到的特徵向量。 ## Conclusion PCA就是個處理資料的方法，輸入是一筆資料，輸出也是一筆資料，本質上就只是把資料的**基底轉換**，而經過證明推導後，可以發現實作方式也很簡單，步驟如下: 1. 將資料集$X$ 標準化。 2. 建立共變異數矩陣$S$。 3. 計算共變異數矩陣$S$ 的 Eigenvalues 和 Eigenvectors。 4. 挑選Eigenvectors，建立正交投影矩陣$W$。 5. 利用正交投影矩陣$W$ 將資料集$X$ 轉換成將資料集$Z$。經過PCA處理的資料集$Z$ ，切斷不同特徵的關聯性[1]，在機器學習、資料分析上有很大的幫助，可以有效降低**過度擬合**(Overfitting)的問題。 ## Reference [1] [ML Lecture 13: Unsupervised Learning - Linear Methods 李宏毅教授](https://www.youtube.com/watch?v=iwh5o_M4BNU&t=2780s) [2] [Covariance matrix - wiki](https://en.wikipedia.org/wiki/Covariance_matrix) [3] [Deriving the Gradient and Hessian of Linear and Quadratic Functions in Matrix Notation, University of British Columbia](https://www.cs.ubc.ca/~schmidtm/Courses/Notes/linearQuadraticGradients.pdf) [4] [對稱矩陣的特徵向量相互垂直 - youtube 學用數學](https://www.youtube.com/watch?v=UrmTCRavJpY) [5] [主成分分析(Principal Component Analysis, PCA)與其有關的數學 - CB Hsu](https://medium.com/%E9%87%8F%E5%8C%96%E4%BA%A4%E6%98%93%E7%9A%84%E8%B5%B7%E9%BB%9E-%E9%82%81%E5%90%91%E9%87%8F%E5%8C%96%E4%BA%A4%E6%98%93%E7%85%89%E9%87%91%E8%A1%93%E5%B8%AB%E4%B9%8B%E8%B7%AF/%E4%B8%BB%E6%88%90%E5%88%86%E5%88%86%E6%9E%90-principal-component-analysis-pca-%E8%88%87%E5%85%B6%E6%9C%89%E9%97%9C%E7%9A%84%E6%95%B8%E5%AD%B8-4135a375ac52)