多維數(shù)據(jù)降維方法

文/戴云翔 路東東

1 引言

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

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

2 線性降維方法

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

2.1 主成分分析降維

主成分分析（Principle Component Analysis, PCA）降維的目標(biāo)是找到數(shù)據(jù)中最主要的元素和結(jié)構(gòu)，去除噪聲和冗余，對原有的復(fù)雜數(shù)據(jù)進(jìn)行降維，揭示處隱藏在復(fù)雜數(shù)據(jù)背后的簡單數(shù)據(jù)。

主成分分析的步驟為：

（3）計(jì)算累積貢獻(xiàn)率，求出恰當(dāng)?shù)闹鞒煞謧€(gè)數(shù)。

主成分分析方法對原始數(shù)據(jù)進(jìn)行線性降維，降維后的數(shù)據(jù)保留原有數(shù)據(jù)的特征，但原有數(shù)據(jù)的內(nèi)在結(jié)構(gòu)將不復(fù)存在。

2.2 稀疏主成分分析

稀疏主成分分析（Sparse Principle Compenent Analysis, SPCA) 是在PCA分析基礎(chǔ)上，將載荷矩陣轉(zhuǎn)化為Lesso懲罰回歸問題得到稀疏載荷。與PCA相比，基于SPCA獲得的主成分有很強(qiáng)的解釋能力，能夠解釋數(shù)據(jù)內(nèi)在的結(jié)構(gòu)，直觀來說就是在應(yīng)用稀疏主成分分析方法進(jìn)行數(shù)據(jù)降維后，可以直接獲得對原始數(shù)據(jù)貢獻(xiàn)率大的原始數(shù)據(jù)中的具體項(xiàng)。

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

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

其中，λ和λj為彈性懲罰系數(shù)。

（4）重復(fù)步驟（2）和（3）至B收斂

（5）標(biāo)準(zhǔn)化βj后即可得到稀疏載荷向量

3 非線性降維方法

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

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

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

ISOMAP算法：參數(shù)設(shè)定簡單、保證全局最優(yōu)；計(jì)算速度快；計(jì)算高維數(shù)據(jù)數(shù)據(jù)點(diǎn)間的距離時(shí)，使用測地線距離而不是歐式距離，很好的保持了數(shù)據(jù)的內(nèi)部幾何結(jié)構(gòu)。然而該方法對內(nèi)部曲率較大的流形展開能力較差，不能對訓(xùn)練數(shù)據(jù)以外的數(shù)據(jù)進(jìn)行降維。

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

3.1 等距特征映射

3.1.1 構(gòu)建鄰接圖 G

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

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

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

3.1.2 計(jì)算節(jié)點(diǎn)相互之間的最短路徑

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

3.1.3 計(jì)算低維嵌入

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

3.2 局部線性嵌入方法

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

3.2.1 選取鄰域

3.2.2 計(jì)算樣本的鄰域重構(gòu)

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

為了求得最佳的重構(gòu)權(quán)值，定義重構(gòu)誤差為：

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

3.2.3 計(jì)算低維嵌入

最后求取低維嵌入坐標(biāo)的代價(jià)函數(shù)為：

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

這樣，式（6）可寫為：

式中Ii和表示單位陣I和WT的第i列，根據(jù)矩陣跡的性質(zhì)

可將式（6）進(jìn)一步寫成：

LLE算法的優(yōu)點(diǎn)是利用了局部線性關(guān)系有效的記錄了數(shù)據(jù)的內(nèi)蘊(yùn)幾何結(jié)構(gòu)，相比于ISOMAP

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

LLE算法只是保持局部近鄰關(guān)系，而不是樣本點(diǎn)間的測地線距離關(guān)系，所以不能很好的保持具有等距特性的數(shù)據(jù)的流形結(jié)構(gòu)。LLE 算法假設(shè)樣本是均勻稠密分布的，對于噪聲較為敏感。

4 結(jié)束語

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