維數(shù)約簡算法簡述

馬發(fā)民+張林+王錦彪

摘 要：機器學(xué)習(xí)是近幾年研究的熱點，維數(shù)約簡算法是機器學(xué)習(xí)的必要手段，本文從維數(shù)約簡算法的定義講起，介紹了幾種典型的數(shù)據(jù)降維算法，其中包括線性降維和非線性降維，流形學(xué)習(xí)是非線性降維的代表算法。并且介紹了每個算法的構(gòu)造過程及其特點，在此基礎(chǔ)上分析了所有維數(shù)約簡算法的執(zhí)行效率時間和空間復(fù)雜度，并且給出了每個算法的特點和算法的核心思想，最后在此基礎(chǔ)上給予總結(jié)，為后面研究者提供參考和借鑒。

關(guān)鍵詞：機器學(xué)習(xí)；維數(shù)約簡；數(shù)據(jù)降維；線性降維；非線性降維

中圖分類號：TP301 文獻標(biāo)識碼：A

Abstract：Machine learning，mainly realized through dimensionality reduction，has become a hot topic for research in recent years.This paper first presents the definition of the dimensionality reduction algorithm，and then introduces several typical data dimensionality reduction algorithms including linear dimensionality reduction and non-linear dimensionality reduction（manifold learning is the typical algorithm of non-linear dimensionality reduction）.Besides，the paper elaborates on the construction process and characteristics of each algorithm，then analyzes the execution efficiency time and space complexity of all dimensionality reduction algorithms and provides the features and key point of each algorithm.Most importantly，the final conclusion offers references to future researchers.

Keywords：machine learning；dimensionality reduction；data dimensionality reduction；linear dimensionality reduction；

non-linear dimensionality reduction；manifold learning

1 引言（Introduction）

機器學(xué)習(xí)是近幾年比較火的一個研究方向，不論在模式識別還是圖像處理方面都要用到機器學(xué)習(xí)的理論，機器學(xué)習(xí)中有個重要的方面研究就是如何把大數(shù)據(jù)量內(nèi)容降低成有限的維數(shù)，從而提高機器學(xué)習(xí)的速度，這里面用到一個關(guān)鍵的算法就是維數(shù)約簡算法，它的原理就是通過線性和非線性的方法，將高維數(shù)據(jù)降低到可以解的低維數(shù)據(jù)從而提高機器學(xué)習(xí)的速度。接下來文章將從維數(shù)約簡數(shù)學(xué)定義說起，緊接著介紹常用的幾種維數(shù)約簡算法，并且給出這些算法的優(yōu)缺點，最后給出總結(jié)為后續(xù)做研究的人提供指引和方向。

2 維數(shù)約簡數(shù)學(xué)定義（Mathematical definition of

dimensionality reduction）

定義1：給定個數(shù)據(jù)點，

，。

構(gòu)造映射，其中

，即

我們把叫作低維表示方法。

假如映射F是線性的那么這種降維叫作線性降維，同理若F是非線性的則這種降維叫作非線性降維。

定義2：構(gòu)造這樣一個映射其中，那么我們由此可以推導(dǎo)出，而我們把這種映射稱為嵌入映射。

定義3：拓撲空間[1]

這種空間是這樣一種形式的數(shù)對，而X和都是集合這種集合所具備的特點是：

（1）集合的元素是無窮多且這些元素沒有邊界；

（2）并且它們的交集也是沒有邊界的；

（3）那么我們把這樣的集合數(shù)對稱為拓撲空間。

定義4：Hausdorff空間[1]

若對于空間中的任意的，存在的鄰域 和的鄰域，使，則稱為一個Hausdorff空間。

定義5：流形[1]

設(shè)是一個Hausdorff空間，如果對任意的一點，都有的一個開鄰域與的某個開子集同胚，則稱是維拓撲流形，簡稱維流形。

定義6：流形學(xué)習(xí)[2]

對于數(shù)據(jù)集，如果存在，

并且它是維數(shù)較低的流形，存在，其中，對于通過映射到低維空間，流形學(xué)習(xí)的含義就是將數(shù)據(jù)集X降低維數(shù)，同時根據(jù)構(gòu)造函數(shù)找出其所對應(yīng)的坐標(biāo)，這樣的過程就是流形學(xué)習(xí)，日常的一些較大數(shù)據(jù)的降維都是通過流形學(xué)習(xí)來實現(xiàn)的。

維數(shù)約簡算法是機器學(xué)習(xí)的重要組成部分，且方法眾多，不同的角度和使用方法，它們又有不同的分類，但是有種分類是較常用的且被大多數(shù)人所接受，這種分類方法如圖1所示。

3 典型的線性降維算法（A typical linear

dimensionality reduction algorithm）

3.1 主成分分析法

主成分分析法顧名思義就是從眾多因素中提取出來主要成分即幾個關(guān)鍵因素，通過這幾種關(guān)鍵因素的分析出整個數(shù)據(jù)的特點[3]，需要注意的是當(dāng)我們提取出的關(guān)鍵特征，這些特征能夠代表整個數(shù)據(jù)的特點，即可以通過這些特征線性的表示出整個數(shù)據(jù)的特征，這有點像唯物辯證法中的通過事物的表象看到事物的本質(zhì)，或者是根本矛盾決定一般矛盾，由于該方法提出時間較早[4]，且操作起來簡單并且降維后的結(jié)果較好因此廣泛地被人們用于維數(shù)約簡中。endprint

考慮點集

令

對譜分解

（1）

其中，，為對角陣，并且，，為對應(yīng)的特征向量，主成分按照式（2）變換得到

（2）

3.2 多維尺度變換

高維數(shù)據(jù)在數(shù)據(jù)空間中通常具有如下特點，數(shù)據(jù)間存在一定的距離和相似性[5]，正如數(shù)據(jù)在高維空間具備一定的拓撲關(guān)系，而這種關(guān)系通常表現(xiàn)在數(shù)據(jù)之間的距離和相似性，而為了保持數(shù)據(jù)的這些特點將高維的數(shù)據(jù)降低到有限維的二三維空間準(zhǔn)中，我們把這種降維的方法叫作多維尺度變換，根據(jù)變換時保留原始數(shù)據(jù)之間的特點不同，又分為度量和非度量的多維尺度變換[6]，具體變換方法如下：

假設(shè)數(shù)據(jù)集，其中單個樣本點為，其中，為樣本點個數(shù)，為樣本點維數(shù)，設(shè)所有樣本組成的維矩陣為，樣本間兩兩內(nèi)積組成的矩陣為。

樣本與之間歐氏距離為

（3）

距離矩陣為

（4）

其中，，。

定義中心化矩陣：。對距離矩陣雙中心化有

（5）

設(shè)

對做特征值分解：

設(shè)為從大到小排列的特征值，為對應(yīng)的特征向量，取前個特征值和對應(yīng)的特征向量得到低維表示為

（6）

下面給出輸出求A的冪集P（A）的另一種遞歸算法：

（1）若n=0，P（A）={}，輸出空集；

（2）若n>1，

輸出A中的一個元素an后，求集合A-an={a1，a2，…，an-1}的冪集輸出，并將A-an={a1，a2，…，an-1}的冪集的每一個元素與an并起來輸出。

4 非線性降維（Nonlinear dimensionality reduction）

4.1 等距映射算法

Tenenbaum J B等人在2000年提出了Isomap算法[7，8]，此算法與多維尺度變換有些類似，多維尺度主要考慮數(shù)據(jù)間是有距離的而這種距離也稱為歐式距離，在此基礎(chǔ)上提出了等距離映射算法，該算法首先需要計算出數(shù)據(jù)間的最短距離，用臨近路徑二維表表示，將最短距離轉(zhuǎn)化為測地線距離，進而將高維數(shù)據(jù)降為低維數(shù)據(jù)，具體的轉(zhuǎn)換構(gòu)造方法如下：

（1）構(gòu)造局部鄰域。計算每個樣本點的近鄰點集合，一般采用近鄰或鄰域法。近鄰法就是找出離點最近的個點，鄰域法就是找出離距離半徑為的園內(nèi)的所有樣本點。

（2）構(gòu)造鄰域圖。

若與為近鄰點，則邊的權(quán)值為與之間的歐氏距離，記為。

否則。

（3）計算距離矩陣。

若與為近鄰點，即為近鄰點，

則，否則。

然后對逐個樣本點順次計算。

（7）

（4）應(yīng)用MDS算法求得低維嵌入坐標(biāo)。

根據(jù)等距離算法得到的歐式距離如圖2所示。

根據(jù)歐式距離圖得到對應(yīng)的測地線距離根據(jù)以上的算法步驟得到降維后的數(shù)據(jù)如圖3所示。

4.2 局部線性嵌入

該方法是最早提出的一種非線性降維的方法，該方法的特點主要處理非線性類數(shù)據(jù)，通過將非線性的數(shù)據(jù)轉(zhuǎn)換成局部線性的數(shù)據(jù)，同時保持數(shù)據(jù)間距離對應(yīng)關(guān)系等，使其拓撲關(guān)系不發(fā)生變化，因此該方法的特點是處理非線性的數(shù)據(jù)同時具備線性數(shù)據(jù)的處理速度，因此此方法廣泛地應(yīng)用于維數(shù)約簡算法中，具體算法步驟如圖4所示。

（1）確定局部鄰域：假設(shè)流形數(shù)據(jù)集為，單個數(shù)據(jù)樣本點表示為，，其中為樣本點個數(shù)，為樣本點維數(shù)，為近鄰點個數(shù)。樣本點與之間的距離為

（8）

（2）計算局部重構(gòu)權(quán)值矩陣，定義誤差函數(shù)，使其把用其近鄰的線性組合表示的誤差最小

（9）

其中，為的個最近鄰點為與之間的權(quán)值。

對于樣本點的近鄰點權(quán)值矩陣通過以下方法計算求得：

計算鄰接關(guān)系矩陣

即矩陣的元素是對應(yīng)的兩個鄰接點的內(nèi)積，并求出矩陣的逆矩陣。

計算拉格朗日因子，是保證對的歸一化操作：

令 （10）

其中，，。

求

（11）

（3）利用權(quán)值矩陣求低維嵌入坐標(biāo)，其中保持不變。

（12）

并且滿足

其中，表示維單位陣，就是降維后的數(shù)據(jù)。

上述優(yōu)化問題可以轉(zhuǎn)化為下列帶約束優(yōu)化問題

（13）

其中，，要使損失函數(shù)值達到最小。使用Lagrange乘子法則取為的個非零特征值所對應(yīng)的特征向量。在處理過程中將特征值由小到大排列，通常第一個特征值幾乎為零，取2到個特征值所對應(yīng)的特征向量作為輸出結(jié)果。

4.3 拉普拉斯特征映射算法

該算法與上述算法[9，10]也有很多相似之處，該方法是將數(shù)據(jù)間的關(guān)系用圖的形式表示出來，通過構(gòu)造數(shù)據(jù)間的鄰接表來表示數(shù)據(jù)，數(shù)據(jù)表示圖的一個頂點，同時鄰近表中重復(fù)的數(shù)據(jù)我們用圖的相似度來表示，通過這樣的一張無向有權(quán)圖來處理流形數(shù)據(jù)就是該算法的核心思想。具體的算法步驟如下：

（1）構(gòu)造無權(quán)有向鄰接圖。使用近鄰或近鄰，對每個樣本點的個近鄰點分別連上邊?；蚴且粋€預(yù)先賦定的值。

（2）確定權(quán)重：確定樣本點之間鄰接關(guān)系權(quán)重的大小，求權(quán)重時有兩種方法可供選擇。

a.簡單化設(shè)定，若點與為近鄰點，則令，否則。

b.選用熱核函數(shù)來確定，若點與為近鄰點，那么它們關(guān)系權(quán)重否則為0。

（3）計算低維嵌入向量，Laplacian Eigenmaps要優(yōu)化的目標(biāo)函數(shù)如下：

（14）endprint

定義對角矩陣，對角線上位置元素為矩陣第行元素之和，上述優(yōu)化問題等價于以下優(yōu)化問題：

（15）

次優(yōu)化問題最終轉(zhuǎn)化為解下列廣義的特征向量問題。

（16）

其中，為對角矩陣，，為近鄰圖的拉普拉斯算子，，使用最小的m個非零特征值對應(yīng)的特征向量作為降維后的結(jié)果輸出。

4.4 局部切空間排列算法

該方法是由浙江大學(xué)張振躍等提出的[11，12]，該方法的特點就是構(gòu)造出數(shù)據(jù)樣本的局部切空間，而將這樣的切空間數(shù)據(jù)用對應(yīng)的鄰域表來表示，進而將這些切空間數(shù)據(jù)嵌入到這樣的鄰域表，進而完成了高維的D維空間嵌入到d維空間中，具體的描述步驟如下所述。

非線性降維的目的是：在嵌入映射函數(shù)具體表達式未知下從函數(shù)值得到其低維的坐標(biāo)表示。

假設(shè)嵌入映射足夠光滑，在確定的點處應(yīng)用泰勒定理，得到下列泰勒式：

（17）

其中，為映射在處的雅克比矩陣，為的一個近鄰點，則有

（18）

由的個列向量張成在處的且空間，即，向量便為對應(yīng)放射子空間的一階逼近局部坐標(biāo)，因具體表達式未知，無法計算出雅克比矩陣，故可借助的表達式來表示，由的一組標(biāo)準(zhǔn)正交基組成的矩陣，即有形式

（19）

其中，的值依賴于局部結(jié)構(gòu)中心的值。

令，則

（20）

式（20）中表示放射變換矩陣。

全局坐標(biāo)表滿足

（21）

其中，為的鄰域，為了逼近全局坐標(biāo)，需要尋求全局坐標(biāo)系和局部放射變換是上述表達式誤差最小。故我們的目標(biāo)可總結(jié)為尋求全局坐標(biāo)系統(tǒng)和局部坐標(biāo)變換使下式達到最小

（22）

LTSA算法步驟如下[13]：

（1）構(gòu)造局部鄰域。取離最近的個樣本點作為的近鄰點，構(gòu)成的鄰域矩陣，其中。

（2）局部線性投影。對每個樣本點的鄰域，求其中心化矩陣

（23）

其中，即為元素全為1的列向量，對中心化后的矩陣進行奇異值分解

（24）

其中，，為的非零奇異值。

和的列向量分別為一組標(biāo)準(zhǔn)正交基，。

取的前列構(gòu)成矩陣。依據(jù)下式計算出局部坐標(biāo)

（25）

（3）局部坐標(biāo)系統(tǒng)排列。

全局坐標(biāo)系統(tǒng)是所有交疊的局部坐標(biāo)系統(tǒng)排列得到。同時整體坐標(biāo)應(yīng)滿足

（26）

其中，，是待求得局部放射變換，為局部重構(gòu)誤差，若令，，則

（27）

式（27）為重構(gòu)誤差的表達式。

為在保持局部拓撲結(jié)構(gòu)求得低維嵌入坐標(biāo)，本算法通過使全局坐標(biāo)排列的重構(gòu)誤差達到最小來得到全局坐標(biāo)：

（28）

5 算法比較分析（Algorithm comparison analysis）

上文講述了不同的維數(shù)約簡算法的原理和數(shù)學(xué)構(gòu)造方法，接下來我們就從運行時間、復(fù)雜度分析和參數(shù)設(shè)置和算法特點幾個方面給予分析比較，具體結(jié)果如表1、表2、表3所示[14-16]。

6 結(jié)論（Conclusion）

文章介紹了維數(shù)約簡的數(shù)學(xué)定義，從本質(zhì)上對維數(shù)約簡進行了分析介紹，維數(shù)約簡的本質(zhì)是降維，對于數(shù)據(jù)的降維分為線性降維和非線性降維，因此維數(shù)約簡算法也分為線性和非線性，本文主要介紹了線性典型算法有主成分分析PCA算法和多維尺度變換算法[20]，非線性算法著重介紹了等距特征映射，局部線性嵌入，拉普拉斯特征映射，局部切空間排列算法，并對各個算法的優(yōu)缺點進行了分析，文章從宏觀上對每個算法進行了簡要的描述，僅對有興趣致力于該方面研究的科技工作者給予參考和借鑒。

參考文獻（References）

[1] 陳省身，陳維恒.微分幾何講義[M].北京：北京大學(xué)出版社，

1983.

[2] Silva V De，Tenenbaum J B.Global versus local methods in nonlinear dimensionality reduction[J].Neural Information Processing Systems，2002，15：705-712.

[3] Pearson K.On lines and planes of closest fit to systems of points in space[J].Philosophical Magazine，1901，2（6）：559-572.

[4] 譚璐.高維數(shù)據(jù)的降維理論及應(yīng)用[D].長沙：國防科學(xué)技術(shù)大學(xué)研究生院，2005.

[5] 尹俊松.流形學(xué)習(xí)理論與方法研究及在人臉識別中的應(yīng)用[D].長沙：國防科技大學(xué)碩士學(xué)位論文，2007.

[6] 馬馳，張紅云，苗奪謙.改進的主曲線算法在指紋骨架提取中的應(yīng)用[J].計算機工程與應(yīng)用，2010，46（16）：170-173.

[7] 吳曉婷.基于流形學(xué)習(xí)的數(shù)據(jù)降維算法研究[D].大連：遼寧師范大學(xué)碩士論文，2010.

[8] Tenenbaum J B.Silva V de.Langford J C.A global geometric framework for nonlinear-ensionality reduction[J].Science，

2000，290（5500）：2319-2323.

[9] Belkin M，Niyogi P.Laplacian eigenmaps and spectral techniques for embedding and clustering[J].Neural Information Processing Systems，2002，14：585-591.endprint

[10] 屠紅磊，黃靜.基于K段主曲線算法的手繪形狀識別[J].計算機應(yīng)用，2009，29（2）：456-458.

[11] Zhang Zhen-yue，Zha Hong-yuan.Principal manifolds and nonlinear dimensionality reduction via local tangent space alignment[J].SIAM Journal of Scientific Computing，2004，26（1）：313-338.

[12] Zhang Zhen-yue，Zha Hong-yuan.Linear low-rank approximations and nonlinear dimensionality reduction[J].Science in China Series A-Mathematics，2005，35（3）：

273-285.

[13] 雷曉花.流形學(xué)習(xí)研究及在文字識別中的應(yīng)用[D].天津：中國民航大學(xué)碩士論文，2011.

[14] 肖睿.高維空間模式鑒別分析及多流形學(xué)習(xí)[D].上海：上海交通大學(xué)電子信息與電氣工程學(xué)院自動化系，2011.

[15] 侯文廣，等.基于流形學(xué)習(xí)的三維空間空間網(wǎng)格剖分方法[J].電子學(xué)報，2012，37（11）：2579-2583.

[16] 黃啟宏，劉釗.流形學(xué)習(xí)中非線性維數(shù)約簡概述[J].計算機應(yīng)用研究，2007，24（11）：19-25.

[17] 張學(xué)工.模式識別[M].北京：清華大學(xué)出版社，2002.

[18] 胡潔.高維數(shù)據(jù)特征降維研究綜述[J].計算機應(yīng)用研究，2008，

25（9）：2601-2602.

[19] 王慶剛.流形學(xué)習(xí)算法及若干應(yīng)用研究[D].重慶：重慶大學(xué)博士學(xué)士論文，2009.

[20] 李光，等.基于流形理論的數(shù)據(jù)分類挖掘[J].艦船電子工程，2009，29（5）：91-93.

作者簡介：

馬發(fā)民（1986-），男，碩士，助教.研究領(lǐng)域：仿生算法，智能優(yōu)化算法.

張 林（1968-），男，碩士，教授.研究領(lǐng)域：網(wǎng)絡(luò)安全.

王錦彪（1947-），男，碩士，教授.研究領(lǐng)域：螞蟻算法，仿生算法.endprint