網易公開課，第14, 15課
notes，10
之前談到的factor analysis，用em算法找到潛在的因子變量，以達到降維的目的
這裡介紹的是另外一種降維的方法，principal components analysis (pca)， 比factor analysis更為直接，計算也簡單些
參考，a tutorial on principal component analysis, jonathon shlens
主成分分析基于，
在現實中，對于高維的資料，其中有很多元都是擾動噪音，或有些維是備援的，對描述資料特征沒有作用
比如我們在描述汽車速度的時候，用不同的機關mph or kph作為兩維，其實隻需要其中一維即可
那麼如果對于一個高維資料，比如3維空間，大部分資料都集中于一個二維平面，那麼我們用這個二維平面的兩個主向量來替代3維向量，就達到降維的目的
并且這樣的也盡可能的保留了原始變量的資訊不丢失
推而廣之，對于n維空間，資料點集中于一個k維的超平面，那麼我們就可以說這個超平面的k個主向量為主成分
看ng說的直升機自動駕駛的例子，描述直升機駕駛員的水準
x1，表示駕駛技能；x2，表示駕駛的愛好和興趣，這兩個次元其實是極度相關的，如下圖
可以看到其實所有點都是集中在u1這個axis附近的，是以我們可以用u1作為主成分來替代原先的x1和x2
其實可以看出，u1和u2是對x1和x2進行旋轉的結果，旋轉後發現其實資料集中在u1次元，u2方向表示noise
對于n維空間，旋轉後，發現用其中的k維就可以很好的描述資料，那麼這k維就是主成分，并且坐标軸都是正交的，即特征間是獨立的
是以旋轉後，選取得到的主成分也都是獨立的
用特征值和特征向量再解釋一下，
對于一個n維矩陣，目前的n個特征即坐标軸，并不一定可以很好的反映資料，比如上面的例子看起來資料和兩個坐标軸都是有很大相關性的
是以我們通過旋轉或線性變換，來找到可以更好的反映資料的新的坐标軸，比如上面的u1，u2
這些向量，稱為特征向量，而特征值表示該特征向量的重要性，即資料是否集中于該維上
這時你會發現，少部分的特征向量的特征值占了特征值總和的絕大部分，而大部分的特征向量的特征值都很小
比如上面的例子u1的特征值很大，而u2的特征值就很小
是以你可以選擇top k特征值的特征向量，來近似原來的n個特征向量，進而達到降維，且盡量的不丢失資料資訊
知道主成分分析的原理，下面的問題就是如何找到主成分？
首先做預處理，zero mean and unit variance
1和2，使x的均值為0
3. 算均方差
4. normalization 偏差，因為每維上的scale是不一樣的，比如一維是體重80，一維是身高1.8，是以需要規範化
好，如何找到u？
one way to pose this problem is as finding the unit vector u so that when the data is projected onto the direction corresponding to u, the variance of the projected data is maximized.
即找到一個機關向量，讓資料投影到u上的點的方差最大，即最分散
為什麼？
首先我們的目的是找到那個子超平面，使得資料點盡量集中在這個超平面上，即點到這個超平面的距離盡可能的小
如下圖，比較直覺，如左圖，當點到u向量距離最小時，方差是最大的
當選取右圖的方向時，方差是最小的
再者，方差大，點比較分散，才便于去區分
形式化的表達出來，
是以所有點的方差和為，
其中，中間那塊是x的協方差矩陣，
設，
上面的式子表示為，
兩邊同時乘上u
簡單解釋一下特征向量和特征值
<a href="http://zh.wikipedia.org/wiki/%e7%89%b9%e5%be%b5%e5%90%91%e9%87%8f">http://zh.wikipedia.org/wiki/%e7%89%b9%e5%be%b5%e5%90%91%e9%87%8f</a>
可以看到對于pca的求解其實很簡單， 隻需要下面幾步，
1. normalized zero mean and unit variance
2. 算出協方差矩陣
3. find top k 特征向量
pca的應用非常廣泛，
壓縮資料
可視化，高維資料無法可視化，降到2維或3維便于可視化
降低over-fitting， 用高維資料進行supervised learning，模型複雜度比較高，容易過拟合，通過pca降維達到防止過拟合的作用
去噪音，比如對于臉部識别，100×100的pixel，就是10000特征，通過pca降維可以找到主成分特征
異常檢測，通過pca可以找到由k個主成分組成的超平面，如果新的資料離該超平面很遠，就說明可能是異常資料
奇異值分解（singular value decomposition）
比如對于談到的臉部識别10000維的x，10000×10000的協方差矩陣
比如文本分析，可能次元更高
對于文本分析，之是以要使用pca，因為對于naive bayse而言，所有特征都是獨立的
即如果有兩篇文章x1，x2
x1中含有learn
而x2中含有study
對于bayse分類而言，這兩篇文章是完全不相關的
但是其實learn和study一定是相關的，是以用pca可以達到降維，并且可以更準确的描述相關性
這種高維的pca問題，就需要用svd去求解
svd用于把一個大矩陣分解成若幹個小矩陣，便于存儲和分析，具體參考上面blog裡面的reference
a矩陣，svd分解成，udv-transpose
其中u的列，是a×a-transpose的特征向量eigenvector
而v的列，是a-transpose×a的特征向量
為什麼？不知道，有空複習線性代數
根據前面svd的定義，我們知道x矩陣的svd分解，中v的列就是x-transpose*x的特征向量
是以對于x進行svd分解，就解決了pac問題
x矩陣是比較小的，比如文本50000特征向量，100個文本，那麼x就是100×50000d的svd分解，比對協方差矩陣50000×50000做特征值向量解要簡單的多
另外在上面的blog中引用數學之美中lsi的例子
比如對m個文本進行聚類，每個文本n個特征，n一般都很大比如50000
那麼傳統做法，就是餘弦法，每個文本之間通過餘弦法來計算相似度，這個計算量很大
而用svd分解，就可以很簡單
對于a，表示m個，n個特征的文本矩陣
進行svd分解，
這邊解釋一下，svd分解，應該是分解成mn = mm × mn × nn
但是這樣分解出來的子矩陣仍然很大，是以近似成，
其實和特征向量一樣，隻是選取奇異值top r的那些向量，進行了壓縮
而對于文本聚類而言，r=100，就代表類，也就是lsi中所謂的latent semantic
相當于現在你不用比較每個單詞特征來判斷文本是否相似，而是比較類特征是否相似，這個不但有效降維，而且解決原來上面提到的learn，study這樣的同義詞的問題
“三個矩陣有非常清楚的實體含義。第一個矩陣x中的每一行表示這類詞中每個詞的相關性。最後一個矩陣y中的每一清單示這類文章中每篇文章的相關性。中間的矩陣則表示詞類和文章類之間的相關性。是以，我們隻要對關聯矩陣a進行一次奇異值分解，我們就可以同時完成了近義詞分類和文章的分類”
之前不解，為何做svd分解，後得到的矩陣可以表示相關性
其實根據前面的定義，知道a-transpose×a等于
而v是a-transpose×a的特征向量矩陣，即文本之間協方差矩陣的特征向量矩陣，這就不難了解了
同樣a×a-transpose表示，列，即單詞特性的協方差矩陣。。。同理u。。。
ng總結無監督學習
首先分為兩類，
求子空間，subspace
因子分析，是density estimation算法，會計算出p(x)
主成分分析，單純的直接求解子空間，不是一個機率算法
是以如果單純為了降維和求解子空間，使用pca
如果需要使用機率p(x)就使用因子分析
求聚類，clumps或group
混合高斯，是density estimation算法
k-means，單純聚類算法，不是一個機率算法
本文章摘自部落格園，原文釋出日期：2014-08-13