PCA的實(shí)現(xiàn)一般有兩種，一種是用特征值分解去實(shí)現(xiàn)的，一種是用奇異值分解PCA的實(shí)現(xiàn)一般有兩種，一種是用特征值分解去實(shí)現(xiàn)的，一種是用奇異值分解去實(shí)現(xiàn)的。特征值和奇異值在大部分人的印象中，往往是停留在純粹的數(shù)學(xué)計(jì)去實(shí)現(xiàn)的。特征值和奇異值在大部分人的印象中，往往是停留在純粹的數(shù)學(xué)計(jì)算中。而且線性代數(shù)或者矩陣論里面，也很少講任何跟特征值與奇異值有關(guān)的算中。而且線性代數(shù)或者矩陣論里面，也很少講任何跟特征值與奇異值有關(guān)的應(yīng)用背景。奇異值分解是一個(gè)有著很明顯的物理意義的一種方法，它可以將一應(yīng)用背景。奇異值分解是一個(gè)有著很明顯的物理意義的一種方法，它可以將一個(gè)比較復(fù)雜的矩陣用更小更簡(jiǎn)單的幾個(gè)子矩陣的相乘來表示，這些小矩陣描述個(gè)比較復(fù)雜的矩陣用更小更簡(jiǎn)單的幾個(gè)子矩陣的相乘來表示，這些小矩陣描述的是矩陣的重要的特性。就像是描述一個(gè)人一樣，給別人描述說這個(gè)人長(zhǎng)得濃的是矩陣的重要的特性。就像是描述一個(gè)人一樣，給別人描述說這個(gè)人長(zhǎng)得濃眉大眼，方臉，絡(luò)腮胡，而且?guī)€(gè)黑框的眼鏡，這樣寥寥的幾個(gè)特征，就讓別眉大眼，方臉，絡(luò)腮胡，而且?guī)€(gè)黑框的眼鏡，這樣寥寥的幾個(gè)特征，就讓別人腦海里面就有一個(gè)較為清楚的認(rèn)識(shí)，實(shí)際上，人臉上的特征是有著無數(shù)種人腦海里面就有一個(gè)較為清楚的認(rèn)識(shí)，實(shí)際上，人臉上的特征是有著無數(shù)種的，之所以能這么描述，是因?yàn)槿颂焐陀兄浅：玫某槿≈匾卣鞯哪芰Γ?，之所以能這么描述，是因?yàn)槿颂焐陀兄浅：玫某槿≈匾卣鞯哪芰?，讓機(jī)器學(xué)會(huì)抽取重要的特征，SVD是一個(gè)重要的方法。featurereductionPCA，做數(shù)據(jù)壓縮（以圖像壓縮為代表）的算法，還有做搜索引LSI（LatentSemanticIndexing）奇異值與特征值基礎(chǔ)知識(shí)很緊密的關(guān)系，我在接下來會(huì)談到，特征值分解和奇異值分解的目的都是一樣，就是提取出一個(gè)矩陣最重要的特征。先談?wù)勌卣髦捣纸獍桑喝绻f一個(gè)向量v是方陣A的特征向量，將一定可以表示成下面的形式：這時(shí)候λv交向量。特征值分解是將一個(gè)矩陣分解成下面的形式：QA，Σ上的元素就是一個(gè)特征值。我這里引用了一些參考文獻(xiàn)中的內(nèi)容來說明一下。首先，要明確的是，一個(gè)矩陣其實(shí)就是一個(gè)線性變換，因?yàn)橐粋€(gè)矩陣乘以一個(gè)向量后得到的向量，其實(shí)就相當(dāng)于將這個(gè)向量進(jìn)行了線性變換。比如說下面的一個(gè)矩陣：它其實(shí)對(duì)應(yīng)的線性變換是下面的形式：因?yàn)檫@個(gè)矩陣M乘以一個(gè)向量(x,y)的結(jié)果是：上面的矩陣是對(duì)稱的，所以這個(gè)變換是一個(gè)對(duì)x，y軸的方向一個(gè)拉伸變換（每一個(gè)對(duì)角線上的元素將會(huì)對(duì)一個(gè)維度進(jìn)行拉伸變換，當(dāng)值>1時(shí)，是拉長(zhǎng)，當(dāng)值<1時(shí)時(shí)縮短），當(dāng)矩陣不是對(duì)稱的時(shí)候，假如說矩陣是下面的樣子：它所描述的變換是下面的樣子：這其實(shí)是在平面上對(duì)一個(gè)軸進(jìn)行的拉伸變換（如藍(lán)色的箭頭所示），在圖中，藍(lán)色的箭頭是一個(gè)最主要的變化方向（變化方向可能有不止一個(gè)），如果我們想要描述好一個(gè)變換，那我們就描述好這個(gè)變換主要的變化方向就好了。反過頭來看看之前特征值分解的式子，分解得到的Σ矩陣是一個(gè)對(duì)角陣，里面的特征值是由大到小排列的，這些特征值所對(duì)應(yīng)的特征向量就是描述這個(gè)矩陣變化方向（從主要的變化到次要的變化排列）當(dāng)矩陣是高維的情況下，那么這個(gè)矩陣就是高維空間下的一個(gè)線性變換，這個(gè)線性變化可能沒法通過圖片來表示，但是可以想象，這個(gè)變換也同樣有很多的N陣最主要的N個(gè)變化方向。我們利用這前N個(gè)變化方向，就可以近似這個(gè)矩陣（變換）。也就是之前說的：提取這個(gè)矩陣最重要的特征?？偨Y(jié)一下，特征值分解可以得到特征值與特征向量，特征值表示的是這個(gè)特征到底有多重要，而特征向量表示這個(gè)特征是什么，可以將每一個(gè)特征向量理解為一個(gè)線性的子空間，我們可以利用這些線性的子空間干很多的事情。不過，特征值分解也有很多的局限，比如說變換的矩陣必須是方陣。下面談?wù)勂娈愔捣纸狻Ｌ卣髦捣纸馐且粋€(gè)提取矩陣特征很不錯(cuò)的方法，但是它只是對(duì)方陣而言的，在現(xiàn)實(shí)的世界中，我們看到的大部分矩陣都不是方陣，比NMN*M可能是方陣，我們?cè)鯓硬拍苊枋鲞@樣普通的矩陣呢的重要特征呢？奇異值分解可以用來干這個(gè)事情，奇異值分解是一個(gè)能適用于任意的矩陣的一種分解的方法：AM*NUM*M（量是正交的，U左奇異向量），Σ是一個(gè)M*N（除了0，對(duì)角線上的元素稱為奇異值），VTN*N右奇異向量），從圖片來反映幾個(gè)相乘的矩陣的大小可得下面的圖片那么奇異值和特征值是怎么對(duì)應(yīng)起來的呢？首先，我們將一個(gè)矩陣A的轉(zhuǎn)置乘以A，將會(huì)得到一個(gè)方陣，我們用這個(gè)方陣求特征值可以得到：這里得到的v，就是我們上面的右奇異向量。此外我們還可以得到：這里的σ就是上面說的奇異值，u就是上面說的左奇異向量。奇異值σ跟特征值類似，在矩陣Σ中也是從大到小排列，而且σ的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上了。也就是說，我們也可以用前r大的奇異值來近似描述矩陣，這里定義一下部分奇異值分解：r是一個(gè)遠(yuǎn)小于m、n的數(shù)，這樣矩陣的乘法看起來像是下面的樣子：右邊的三個(gè)矩陣相乘的結(jié)果將會(huì)是一個(gè)接近于A的矩陣，在這兒，r越接近于n，則相乘的結(jié)果越接近于A。而這三個(gè)矩陣的面積之和（在存儲(chǔ)觀點(diǎn)來說，矩陣面積越小，存儲(chǔ)量就越?。┮h(yuǎn)遠(yuǎn)小于原始的矩陣A，我們?nèi)绻胍獕嚎s空間來表示原矩陣A，我們存下這里的三個(gè)矩陣：U、Σ、V就好了。奇異值的計(jì)算O(N^3問題的，matlab1000*10003老師在數(shù)學(xué)之美SVDGoogleSVD計(jì)算規(guī)模，也沒有給出太多有價(jià)值的信息。SVD用迭代的方法，當(dāng)矩陣的規(guī)模很大（比如說上億）的時(shí)候，迭代的次數(shù)也可能Map-ReduceMap-ReduceGoogleMPIMap-ReduceLanczos迭代就是一種解對(duì)稱方陣部分特征值的方法（之前談到了，解A’*A得到的對(duì)稱方陣的特征值就是解A的右奇異向量），是將一個(gè)對(duì)稱的方程化為一個(gè)三對(duì)角矩陣再進(jìn)行求解。按網(wǎng)上的一些文獻(xiàn)來看，Google應(yīng)該是用這種方法去做的奇異值分解的。請(qǐng)見Wikipedia上面的一些引用的論文，如果理解了那些論文，也“幾乎”可以做出一個(gè)SVD了。由于奇異值的計(jì)算是一個(gè)很枯燥，純數(shù)學(xué)的過程，而且前人的研究成果（論文中）幾乎已經(jīng)把整個(gè)程序的流程圖給出來了。更多的關(guān)于奇異值計(jì)算的部分，將在后面的參考文獻(xiàn)中給出，這里不再深入，我還是focus在奇異值的應(yīng)用中去。奇異值分解SVD與主成分分析PCA這里主要談?wù)勅绾斡肧VD去解PCA的問題。PCA的問題其實(shí)是一個(gè)基的變換，使得變換后的數(shù)據(jù)有著最大的方差。方差的大小描述的是一個(gè)變量的信息量，我們?cè)谥v一個(gè)東西的穩(wěn)定性的時(shí)候，往往說要減小方差，如果一個(gè)模型的方差很大，那就說明模型不穩(wěn)定了。但是對(duì)于我們用于機(jī)器學(xué)習(xí)的數(shù)據(jù)（主要是訓(xùn)練數(shù)據(jù)），方差大才有意義，不然輸入的數(shù)據(jù)都是同一個(gè)點(diǎn)，那方差就為0了，這樣輸入的多個(gè)數(shù)據(jù)就等同于一個(gè)數(shù)據(jù)了。以下面這張圖為例子：這個(gè)假設(shè)是一個(gè)攝像機(jī)采集一個(gè)物體運(yùn)動(dòng)得到的圖片，上面的點(diǎn)表示物體運(yùn)動(dòng)的位置，假如我們想要用一條直線去擬合這些點(diǎn)，那我們會(huì)選擇什么方向的線呢？當(dāng)然是圖上標(biāo)有signal的那條線。如果我們把這些點(diǎn)單純的投影到x軸或者y軸上，最后在x軸與y軸上得到的方差是相似的（因?yàn)檫@些點(diǎn)的趨勢(shì)是在45度左右的方向，所以投影到x軸或者y軸上都是類似的），如果我們使用原來的xy坐標(biāo)系去看這些點(diǎn)，容易看不出來這些點(diǎn)真正的方向是什么。但是如果我們進(jìn)行坐標(biāo)系的變化，橫軸變成了signal的方向，縱軸變成了noise的方向，則就很容易發(fā)現(xiàn)什么方向的方差大，什么方向的方差小了。一般來說，方差大的方向是信號(hào)的方向，方差小的方向是噪聲的方向，我們?cè)跀?shù)據(jù)挖掘中或者數(shù)字信號(hào)處理中，往往要提高信號(hào)與噪聲的比例，也就是信噪比。對(duì)上圖來說，如果我們只保留signal方向的數(shù)據(jù)，也可以對(duì)原數(shù)據(jù)進(jìn)行不錯(cuò)的近似了。PCA就是對(duì)原始的空間中順序地找一組相互正交的坐標(biāo)軸，第一個(gè)軸是使得方差最大的，第二個(gè)軸是在與第一個(gè)軸正交的平面中使得1、2NNrNrrfeature，用矩陣的m*nA，PNNm*n的矩陣Am*rnfeaturerfeature（rnrnfeatureSVDSVDPCA奇異向量，方差次大的坐標(biāo)軸就是第二個(gè)奇異向量…我們回憶一下之前得到的SVD在矩陣的兩邊同時(shí)乘上一個(gè)矩陣V，由于V是一個(gè)正交的矩陣，所以V轉(zhuǎn)置乘以V得到單位陣I，所以可以化成后面的式子將后面的式子與A*P那個(gè)m*n的矩陣變換為m*r的矩陣的式子對(duì)照看看，在這里，其實(shí)V就是P，也就是一個(gè)變化的向量。這里是將一個(gè)m*n的矩陣壓縮到一個(gè)m*r的矩陣，也就是對(duì)列進(jìn)行壓縮，如果我們想對(duì)行進(jìn)行壓縮（在PCA的觀點(diǎn)下，對(duì)行進(jìn)行壓縮可以理解為，將一些相似的sample合并在一起，或者將一些沒有太大價(jià)值的sample去掉）怎么辦呢？同樣我們寫出一個(gè)通用的行壓縮例子：mrSVDSVDUUTPCASVDSVDPCASVDPCAA’APCA。奇異值與潛在語義索引LSI潛在語義索引（LatentSemanticIndexing）PCASVDLSISVD“三個(gè)矩陣有非常清楚的物理含義。第一個(gè)矩XY章雷之間的相關(guān)性。因此，我們只要對(duì)關(guān)聯(lián)矩Aw我們就可以同時(shí)完成了近義詞分類和文章的分類。（的相關(guān)性）?！盠SILSAtutorial，具體的網(wǎng)址我將在最后的引用中給出：title現(xiàn)了（feature），title（這個(gè)矩陣其實(shí)是我們之前說的那種一行是一個(gè)sample的形式的一種轉(zhuǎn)置，這個(gè)會(huì)使得我們的左右奇異向量的意義產(chǎn)生變化，但是不會(huì)影響我們計(jì)算的過程）。比如說T1這個(gè)title中就有g(shù)uide、investing、market、stock四個(gè)詞，各出現(xiàn)了一次，我們將這個(gè)矩陣進(jìn)行SVD，得到下面的矩陣：左奇異向量表示詞的一些特性，右奇異向量表示文檔的一些特性，中間的奇異值矩陣表示左奇異向量的一行與右奇異向量的一列的重要程序，數(shù)字越大越重要。book0.152investing0.749rich0.363其次，右奇異向量中一的第一行表示每一篇文檔中的出現(xiàn)詞的個(gè)數(shù)的近似，比如說，T6是0.49，出現(xiàn)了5個(gè)詞，T2是0.22，出現(xiàn)了2個(gè)詞。然后我們反過頭來看，我們可以將左奇異向量和右奇異向量都取后2維（之前是3維的矩陣），投影到一個(gè)平面上，可以得到：在圖上，每一個(gè)紅色的點(diǎn)，都表示一個(gè)詞，每一個(gè)藍(lán)色的點(diǎn)，都表示一篇文檔，這樣我們可以對(duì)這些詞和文檔進(jìn)行聚類，比如說stock和market可以放