1.前言

機器學習領域中所謂的降維就是指采用某種映射方法，將原高維空間中的數(shù)據(jù)點映射到低維度的空間中。降維的本質是學習一個映射函數(shù) f : x->y，其中x是原始數(shù)據(jù)點的表達，目前最多使用向量表達形式。 y是數(shù)據(jù)點映射后的低維向量表達，通常y的維度小于x的維度（當然提高維度也是可以的）。f可能是顯式的或隱式的、線性的或非線性的。
目前大部分降維算法處理向量表達的數(shù)據(jù)，也有一些降維算法處理高階張量表達的數(shù)據(jù)。之所以使用降維后的數(shù)據(jù)表示是因為在原始的高維空間中，包含有冗余信息以及噪音信息，在實際應用例如圖像識別中造成了誤差，降低了準確率；而通過降維,我們希望減少冗余信息所造成的誤差,提高識別（或其他應用）的精度。又或者希望通過降維算法來尋找數(shù)據(jù)內部的本質結構特征。
在很多算法中，降維算法成為了數(shù)據(jù)預處理的一部分，如PCA。事實上，有一些算法如果沒有降維預處理，其實是很難得到很好的效果的。

2.回顧PCA

Principal Component Analysis(PCA)是最常用的線性降維方法，它的目標是通過某種線性投影，將高維的數(shù)據(jù)映射到低維的空間中表示，并期望在所投影的維度上數(shù)據(jù)的方差最大，以此使用較少的數(shù)據(jù)維度，同時保留住較多的原數(shù)據(jù)點的特性。
通俗的理解，如果把所有的點都映射到一起，那么幾乎所有的信息（如點和點之間的距離關系）都丟失了，而如果映射后方差盡可能的大，那么數(shù)據(jù)點則會分散開來，以此來保留更多的信息。可以證明，PCA是丟失原始數(shù)據(jù)信息最少的一種線性降維方式。（實際上就是最接近原始數(shù)據(jù)，但是PCA并不試圖去探索數(shù)據(jù)內在結構）
設n維向量w為目標子空間的一個坐標軸方向（稱為映射向量），最大化數(shù)據(jù)映射后的方差，有：

其中m是數(shù)據(jù)實例的個數(shù)， xi是數(shù)據(jù)實例i的向量表達， x拔是所有數(shù)據(jù)實例的平均向量。定義W為包含所有映射向量為列向量的矩陣，經過線性代數(shù)變換，可以得到如下優(yōu)化目標函數(shù)：

其中tr表示矩陣的跡：

A是數(shù)據(jù)協(xié)方差矩陣。
容易得到最優(yōu)的W是由數(shù)據(jù)協(xié)方差矩陣前k個最大的特征值對應的特征向量作為列向量構成的。這些特征向量形成一組正交基并且最好地保留了數(shù)據(jù)中的信息。
PCA的輸出就是Y = W'X，由X的原始維度降低到了k維。
PCA追求的是在降維之后能夠最大化保持數(shù)據(jù)的內在信息，并通過衡量在投影方向上的數(shù)據(jù)方差的大小來衡量該方向的重要性。但是這樣投影以后對數(shù)據(jù)的區(qū)分作用并不大，反而可能使得數(shù)據(jù)點揉雜在一起無法區(qū)分。這也是PCA存在的最大一個問題，這導致使用PCA在很多情況下的分類效果并不好。具體可以看下圖所示，若使用PCA將數(shù)據(jù)點投影至一維空間上時，PCA會選擇2軸，這使得原本很容易區(qū)分的兩簇點被揉雜在一起變得無法區(qū)分；而這時若選擇1軸將會得到很好的區(qū)分結果。

Discriminant Analysis所追求的目標與PCA不同，不是希望保持數(shù)據(jù)最多的信息，而是希望數(shù)據(jù)在降維后能夠很容易地被區(qū)分開來，是另一種常見的線性降維方法。另外一些非線性的降維方法利用數(shù)據(jù)點的局部性質，也可以做到比較好地區(qū)分結果，例如LLE，Laplacian Eigenmap等。

3.回顧LDA

Linear Discriminant Analysis (也有叫做Fisher Linear Discriminant)是一種有監(jiān)督的（supervised）線性降維算法。與PCA保持數(shù)據(jù)信息不同，LDA是為了使得降維后的數(shù)據(jù)點盡可能地容易被區(qū)分！
假設原始數(shù)據(jù)表示為X，（m*n矩陣，m是維度，n是sample的數(shù)量）
既然是線性的，那么就是希望找到映射向量a， 使得 a'X后的數(shù)據(jù)點能夠保持以下兩種性質：

• 同類的數(shù)據(jù)點盡可能的接近（within class）
• 不同類的數(shù)據(jù)點盡可能的分開（between class）

所以呢還是上次PCA用的這張圖，如果圖中兩堆點是兩類的話，那么我們就希望他們能夠投影到軸1去（PCA結果為軸2），這樣在一維空間中也是很容易區(qū)分的。

可以發(fā)現(xiàn)，LDA最后也是轉化成為一個求矩陣特征向量的問題，和PCA很像，事實上很多其他的算法也是歸結于這一類，一般稱之為譜（spectral）方法。

3.非線性降維-局部線性嵌入LLE

Locally linear embedding（LLE）是一種非線性降維算法，它能夠使降維后的數(shù)據(jù)較好地保持原有流形結構。LLE可以說是流形學習方法最經典的工作之一。很多后續(xù)的流形學習、降維方法都與LLE有密切聯(lián)系。
下圖使用LLE將三維數(shù)據(jù)（b）映射到二維（c）之后，映射后的數(shù)據(jù)仍能保持原有的數(shù)據(jù)流形（紅色的點互相接近，藍色的也互相接近），說明LLE有效地保持了數(shù)據(jù)原有的流行結構。
但是LLE在有些情況下也并不適用：

• 如果數(shù)據(jù)分布在整個封閉的球面上，LLE則不能將它映射到二維空間，且不能保持原有的數(shù)據(jù)流形。
• 那么我們在處理數(shù)據(jù)中，首先假設數(shù)據(jù)不是分布在閉合的球面或者橢球面上。

LLE算法認為每一個數(shù)據(jù)點都可以由其近鄰點的線性加權組合構造得到。 算法的主要步驟分為三步：

尋找每個樣本點的k個近鄰點；

每個樣本點的近鄰點計算出該樣本點的局部重建權值矩陣；

由該樣本點的局部重建權值矩陣和其近鄰點計算出該樣本點的輸出值。

具體的算法流程下圖所示：

4.非線性降維-拉普拉斯特征映射

其實不是說每一個算法都比前面的好，而是每一個算法都是從不同角度去看問題，因此解決問題的思路是不一樣的。這些降維算法的思想都很簡單，卻在有些方面很有效。這些方法事實上是后面一些新的算法的思路來源。
Laplacian Eigenmaps[1] 看問題的角度和LLE有些相似，也是用局部的角度去構建數(shù)據(jù)之間的關系。
它的直觀思想是希望相互間有關系的點（在圖中相連的點）在降維后的空間中盡可能的靠近。Laplacian Eigenmaps可以反映出數(shù)據(jù)內在的流形結構。
使用時算法具體步驟為：
步驟1：構建圖
使用某一種方法來將所有的點構建成一個圖，例如使用KNN算法，將每個點最近的K個點連上邊。K是一個預先設定的值。
步驟2：確定權重
確定點與點之間的權重大小，例如選用熱核函數(shù)來確定。
Laplacian Eigenmap具有區(qū)分數(shù)據(jù)點的特性，可以從下面的例子看出：

見圖1所示，左邊的圖表示有兩類數(shù)據(jù)點（數(shù)據(jù)是圖片），中間圖表示采用Laplacian Eigenmap降維后每個數(shù)據(jù)點在二維空間中的位置，右邊的圖表示采用PCA并取前兩個主要方向投影后的結果，可以清楚地看到，在此分類問題上，Laplacian Eigenmap的結果明顯優(yōu)于PCA。

roll數(shù)據(jù)的降維
上圖說明的是，高維數(shù)據(jù)（圖中3D）也有可能是具有低維的內在屬性的（圖中roll實際上是2D的），但是這個低維不是原來坐標表示，例如如果要保持局部關系，藍色和下面黃色是完全不相關的，但是如果只用任何2D或者3D的距離來描述都是不準確的。
下面三個圖是Laplacian Eigenmap在不同參數(shù)下的展開結果（降維到2D），可以看到，似乎是要把整個帶子拉平了。于是藍色和黃色差的比較遠。

總結

以上是生活随笔為你收集整理的新兴机器学习算法：从无监督降维到监督降维的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。