多維數據降維方法

文/戴云翔 路東東

1 引言

數據降維是一個過程，在數據降維過程是要保證在降低數據集維度的過程后，數據不丟失、不失真，降維后的數據依然要包含數據的原有信息。在科技發展的今天，數據的采集益發容易，采集的數據的量越來越大，很多時候數據量均在G量級上。在機器學習中，在數據量過少時容易引發數據的“欠擬合”；但如果特征值（維度）過多，會引起維度災難。維度災難最直接的后果就是“過擬合”，進而導致分類錯誤，這也是數據降維研究的初衷。

特征降維的方法根據特征提取方式的不同可以分為：特征選擇和特征抽取；根據樣本信息可利用可分為：監督降維、半監督降維和無監督降維；根據處理數據屬性類別的不同可分為：線性降維和非線性降維。本文就處理數據類別方面對多維數據降維方法進行闡述。

2 線性降維方法

常用的線性降維方法主要有主成分分析降維和稀疏主成分降維。這兩種降維方法均能夠獲得原始數據中的數據的主要成分，但兩種方法在數據的可解釋性上又有所區別。

2.1 主成分分析降維

主成分分析（Principle Component Analysis, PCA）降維的目標是找到數據中最主要的元素和結構，去除噪聲和冗余，對原有的復雜數據進行降維，揭示處隱藏在復雜數據背后的簡單數據。

主成分分析的步驟為：

（3）計算累積貢獻率，求出恰當的主成分個數。

主成分分析方法對原始數據進行線性降維，降維后的數據保留原有數據的特征，但原有數據的內在結構將不復存在。

2.2 稀疏主成分分析

稀疏主成分分析（Sparse Principle Compenent Analysis, SPCA) 是在PCA分析基礎上，將載荷矩陣轉化為Lesso懲罰回歸問題得到稀疏載荷。與PCA相比，基于SPCA獲得的主成分有很強的解釋能力，能夠解釋數據內在的結構，直觀來說就是在應用稀疏主成分分析方法進行數據降維后，可以直接獲得對原始數據貢獻率大的原始數據中的具體項。

稀疏主成分分析的步驟為：

（2）在所給的A矩陣的條件下，求解彈性網回歸問題：

其中，λ和λj為彈性懲罰系數。

（4）重復步驟（2）和（3）至B收斂

（5）標準化βj后即可得到稀疏載荷向量

3 非線性降維方法

非線性降維方法有局部線性嵌入方法（Locally Linear Embedding，LLE）、核主成分分析（Kernel Principal Component Analysis，KPCA）和等距特征映射（Isometric Feature Mapping，Isomap）。

其中，LLE算法幾何意義直觀、待定參數少可以學習任意維數的高維流形、有整體解析最優解、適用于非線性數據的要求流形上點分布均勻且稠密采樣；當流形呈卷曲狀，可能造成流形結構在重構過程扭曲；當流形為封閉式流形（球形、橢球形）時，方法失效；LLE對噪聲敏感，對多流形數據局部線性化差。

KPCA算法：PCA的非線性提升，適于解決非線性特征提取問題，能提供比PCA更多的特征數目，可以最大限度的提取特征信息。同PCA一樣，存儲空間大、計算復雜度高，提取的特征意義不明確。

ISOMAP算法：參數設定簡單、保證全局最優；計算速度快；計算高維數據數據點間的距離時，使用測地線距離而不是歐式距離，很好的保持了數據的內部幾何結構。然而該方法對內部曲率較大的流形展開能力較差，不能對訓練數據以外的數據進行降維。

對于非線性降維方法，本文將著重介紹等距特征映射方法和局部線性嵌入方法。

3.1 等距特征映射

3.1.1 構建鄰接圖 G

定義鄰接圖G覆蓋所有數據點，數據點與其近鄰點有邊相連，邊的長度為兩點之間的距離dx(i,j)。計算近鄰點有如下兩種方法：

（1）基于歐氏距離尋找離樣本點最近的K個近鄰點，基于此方法的等距特征映射叫K-Isomap；

（2）將樣本點選定半徑為常數δ的圓內所有點都作為樣本點的近鄰點，基于此方法的等距特征映射叫

3.1.2 計算節點相互之間的最短路徑

（1）初始化dG(i,j)。若G中結點i、j之間有邊相連，則否則

3.1.3 計算低維嵌入

使用多尺度變換計算方法計算流形的低維嵌入，選擇低維空間的任意兩個嵌入坐標yi、yj，最小化代價函數如公式（3）所示，di,j為兩點之間的最短路徑。

3.2 局部線性嵌入方法

LLE算法的思想是：假設數據的結構在局部意義下是線性的，通過局部的線性來逼近全局的非線性。對于數據集中任意一點xi，都可以尋找它的K個近鄰點線性組合表示，具體組合的權重需要通過最小化重構誤差得到。最后將樣本點映射到低維空間的同時盡量保持各樣本點與其近鄰點的關系不變。LLE算法的具體步驟如下：

3.2.1 選取鄰域

3.2.2 計算樣本的鄰域重構

對于每個點xi，LLE算法局部特性描述方法和ISOMAP不同。LLE算法需要計算每個點xi在其鄰域集合內的重構權值，構建所有樣本點間的重構權值矩陣W。在這里認為非近鄰點間的重構權值Wi,j=0。

為了求得最佳的重構權值，定義重構誤差為：

這里的重構權值反映了近鄰點對中心點的貢獻程度。為了使重構權值具有平移不變形，對于任意樣本點xi與其鄰域點的重構權值給以約束最后利用拉格朗日乘子法，可對式（5）求解。

3.2.3 計算低維嵌入

最后求取低維嵌入坐標的代價函數為：

為了使得低維嵌入坐標 的具有平移、旋轉、縮放不變性，還需要對式（6）添加一些約束條件：

這樣，式（6）可寫為：

式中Ii和表示單位陣I和WT的第i列，根據矩陣跡的性質

可將式（6）進一步寫成：

LLE算法的優點是利用了局部線性關系有效的記錄了數據的內蘊幾何結構，相比于ISOMAP

算法計算復雜度更低，且無需迭代。算法的最終求解可歸結為稀疏矩陣的特征值計算問題。

LLE算法只是保持局部近鄰關系，而不是樣本點間的測地線距離關系，所以不能很好的保持具有等距特性的數據的流形結構。LLE 算法假設樣本是均勻稠密分布的，對于噪聲較為敏感。

4 結束語

本文對數據降維方法進行了簡要概述，同時對線性降維方法中常用的PCA降維方法、稀疏主成分分析方法的步驟進行了具體闡述。在非線性降維方面對Isomap算法、LLE算法的具體步驟進行了詳細的介紹。四種降維方法各有利弊，在應用數據降維方法進行數據降維時，鑒于數據類型的多樣性及需要提取的特征的差異，在具體特征提取時，需要進行具體分析，以便獲得最好的降維效果。