PCA要做的就是找出一個低維度的投影平面(在這個例子是一條紅色直線)，當我們將data投影到上面，data與這條線之間的平方投影誤差(squared projection error)能夠最小化。平方投影誤差就是data「原始的」位置與「投影到平面上後」的位置之間距離的「平方」。
正式定義：
當你想將二維資料降成一維時，PCA會尋找一個對資料進行投影的方向，或稱一個向量${ u }^{ (i) }\in { R }^{ n }$，在這邊就是${ u }^{ (i) }\in { R }^{ 2 }$，使得投影誤差能夠最小化。這個向量是正是負都沒關係，因為即使是相反方向，定義出的直線(投影方向)還是一樣的。
以此類推，如果要將n維資料降成k維時，我們就要找出k個方向(向量)來將data投影到由這k個向量所形成的一個k維平面上。
以右圖為例，假設我要將三維降成兩維，現在k=2，則我們要找出從原點延伸出來的兩個方向(向量)：${ u }^{ (1) }$與${ u }^{ (2) }$，這兩個向量會定義一個二維平面，我們就可以將data投影到這個平面上。
用線性代數的術語來說，就是要將data投影到這k個向量生成的線性子空間中。
那麼PCA跟線性回歸有什麼關係呢？看起來很像但兩者意義不太一樣，線性回歸要最小化的東西是每個點與回歸直線之間的平方誤差，是一個垂直距離，它是某個點與透過假設所得到的其預測值y之間的距離。而PCA要最小化的東西是每個點與直線之間的直角距離(orthogonal distance)。
線性回歸做的是用x中所有的值來預測一個特殊變數y，但在PCA沒有這麼一個要預測的y，我們擁有的就是一群特徵${ x }_{ 1 },{ x }_{ 2 }, ... , { x }_{ n }$，這些特徵都是被同等對待的，沒有所謂的特殊變數y需要被預測。
因此，如果我要將三維降成兩維，我要做的就是找出兩個方向，並將data投影到二維平面上，此時三個特徵${ x }_{ 1 }$、${ x }_{ 2 }$與${ x }_{ 3 }$是被同等對待的。
問題：
主成分分析演算法
在使用PCA之前，我們習慣先做mean normalization以及feature scaling。mean normalization是一定要做的，feature scaling則視data set而定，我們先計算每個特徵的平均${ u }_{ j }$，並將每個特徵${ x }_{ j }^{ (i) }$用${ x }_{ j }-{ u }_{ j }$取代，如果每個特徵值範圍差太多，我們再用特徵縮放來處理。${ S }_{ j }代表最大值減最小值。
現在問題就是，該如何找到我們要的${ u }^{ (1) }$、${ u }^{ (2) }$、${ z }_{ 1 }$與${ z }_{ 2 }$等等呢？
以數學角度來說，我們要先計算一個covariance矩陣，它的符號與「求和」符號一樣，在這邊不要搞混就好，我們會將它存在一個Sigma變數中，接下來就是要求它的eigenvectors，將svd()方法用於這個covariance矩陣會得到三個矩陣U,S,V。U矩陣為一個n*n矩陣，如果想要將矩陣降到k維，我們就只要取U矩陣的前k個行向量，這k個向量就是我們要找的k個方向，將data投影到上面。
如果要將我們原始的data set $x\in { R }^{ n }$用一個低維度的$z\in { R }^{ k }$表示，就是取U矩陣的前k個向量，取出來後把這個n*k矩陣叫做${ U }_{ reduce }$。而z就是這個矩陣的轉置乘上x，z是一個k*n矩陣，而x是一個n*1向量，最後會得出一個k*1向量，還算合理。如果要針對某個training example ${ x }^{ (i) }$，我們就在x上面加個上標i即可，最後會得出${ z }^{ (i) }$。
總結，右邊的計算方式是一種向量化寫法，在octave中「'」代表「T」：
問題：
主成分元素的個數
當我們要將資料從n維降成k維時，k是一個PCA演算法要輸入的變數，這個k又叫作「主成分元素的個數」，以下講解該如何找出這個k。
首先，PCA在做的就是要最小化平均平方投影誤差。另外，我們的data的總變異就是所有樣本長度的平均。
只要這個k能夠使得這兩者相除小於0.01，找出當中最小的k即可。當別人問你留下了多少主成分，你可以說你選擇了一個k，代表留下了k個主成分，這個k保留了99%的variance。0.01是大家最常用的數值，0.05也可以，最常見就是k保留了95%~99%的variance。
再來，該怎麼選k呢？你可以從k=1開始一直算，直到該式子小於等於0.01為止。很明顯這不太有效率，我們可以換個方式，用svd分解來找，取出svd分解後的Sigma矩陣，給定一個k，我們只要算出1減掉這k個對角線的值的總和除以n個對角線的值的總和是否小於等於0.01即可。換個角度講就是，這k個對角線的值的總和除以n個對角線的值的總和要大於等於0.99。
因此，你只要慢慢增加k就好，而且只要呼叫一次SVD即可。
總結：
重建資料(Reconstruction)
以下面例子來說，我們該如何將$z\in { R }$轉回$x\in { R }^{2}$呢？由於$z={ U }_{ reduce }^{T}x$，要重建成原本的資料只要求${ x }_{ approx }={ U }_{ reduce }z$即可，但是只能重建成近似資料，沒辦法一模一樣。
問題：假設我們要進行降維，但是是降成k=n維(也就是一模一樣維度)，以下何者算正確？
假設你有個100*100=10000pixels的影像資料，你的特徵向量{x}^{(i)}就會包含10000個pixels的亮度值，也就是特徵向量為10000維。想像一下如果將這個10000維的特徵向量丟給監督學習演算法，例如邏輯回歸、神經網路或是支援向量機，這速度想必會非常慢，此時用PCA壓縮一下資料可以加快演算法的速度。
首先我們先取出data set中的input部分，也就是特徵向量x，這還是10000維。此時對它做PCA後，可能可以得到一個低維度(或許1000維)的特徵向量z，這樣我們將會得到一個新的data set，這個新的data set，input部分已經變成了z。
錯誤的PCA用法：使用PCA來降低特徵數量以防止over-fitting
正確的用法：使用regularization來防止over-fitting
最後，在使用PCA以前，你應該確保演算法在原始數據上進行過嘗試，只有在這種嘗試達不到你預期結果時才採用PCA。因為大部分人在做project時會加入「將資料進行壓縮」這個步驟，而其實不用壓縮似乎也不影響結果。
沒有留言:
張貼留言