技術(shù)報(bào)告維數(shù)約簡(jiǎn)算法簡(jiǎn)述

1、計(jì)劃類(lèi)別 項(xiàng)目編號(hào) 項(xiàng)目技術(shù)報(bào)告課題名稱(chēng) 項(xiàng)目主持人 承擔(dān)單位 題目：維數(shù)約簡(jiǎn)算法簡(jiǎn)述機(jī)器學(xué)習(xí)是近幾年研究的熱點(diǎn)，維數(shù)約簡(jiǎn)算法是機(jī)器學(xué)習(xí)的必要手段，本文從維數(shù)約簡(jiǎn)算法的定義講起，介紹了幾種典型的數(shù)據(jù)降維算法，其中包括線(xiàn)性降維和非線(xiàn)性降維，流形學(xué)習(xí)是非線(xiàn)性降維的代表算法。并且介紹了每個(gè)算法的構(gòu)造過(guò)程及其特點(diǎn)，在此基礎(chǔ)上分析了所有維數(shù)約簡(jiǎn)算法的執(zhí)行效率時(shí)間和空間復(fù)雜度，并且給出了每個(gè)算法的特點(diǎn)和算法的核心思想，最后在此基礎(chǔ)上給予總結(jié)，為后面研究者提供參考和借鑒。關(guān)鍵詞：機(jī)器學(xué)習(xí)；維數(shù)約簡(jiǎn)；數(shù)據(jù)降維；線(xiàn)性降維；非線(xiàn)性降維Abstract：Machine learning，mainly realize

2、d 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-lin

3、ear 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 reduct

4、ion 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；

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

6、fdimensionality reduction）定義1：給定個(gè)數(shù)據(jù)點(diǎn)，。構(gòu)造映射，其中，即我們把叫作低維表示方法。假如映射F是線(xiàn)性的那么這種降維叫作線(xiàn)性降維，同理若F是非線(xiàn)性的則這種降維叫作非線(xiàn)性降維。定義2：構(gòu)造這樣一個(gè)映射其中，那么我們由此可以推導(dǎo)出，而我們把這種映射稱(chēng)為嵌入映射。定義3：拓?fù)淇臻g1這種空間是這樣一種形式的數(shù)對(duì)，而X和都是集合這種集合所具備的特點(diǎn)是：（1）集合的元素是無(wú)窮多且這些元素沒(méi)有邊界；（2）并且它們的交集也是沒(méi)有邊界的；（3）那么我們把這樣的集合數(shù)對(duì)稱(chēng)為拓?fù)淇臻g。定義4：Hausdorff空間1若對(duì)于空間中的任意的，存在的鄰域 和的鄰域，使，則稱(chēng)為一個(gè)Hausd

7、orff空間。定義5：流形1設(shè)是一個(gè)Hausdorff空間，如果對(duì)任意的一點(diǎn)，都有的一個(gè)開(kāi)鄰域與的某個(gè)開(kāi)子集同胚，則稱(chēng)是維拓?fù)淞餍危?jiǎn)稱(chēng)維流形。定義6：流形學(xué)習(xí)2對(duì)于數(shù)據(jù)集，如果存在，并且它是維數(shù)較低的流形，存在，其中，對(duì)于通過(guò)映射到低維空間，流形學(xué)習(xí)的含義就是將數(shù)據(jù)集X降低維數(shù)，同時(shí)根據(jù)構(gòu)造函數(shù)找出其所對(duì)應(yīng)的坐標(biāo)，這樣的過(guò)程就是流形學(xué)習(xí)，日常的一些較大數(shù)據(jù)的降維都是通過(guò)流形學(xué)習(xí)來(lái)實(shí)現(xiàn)的。維數(shù)約簡(jiǎn)算法是機(jī)器學(xué)習(xí)的重要組成部分，且方法眾多，不同的角度和使用方法，它們又有不同的分類(lèi)，但是有種分類(lèi)是較常用的且被大多數(shù)人所接受，這種分類(lèi)方法如圖1所示。3 典型的線(xiàn)性降維算法（A typical lin

8、eardimensionality reduction algorithm）3.1 主成分分析法主成分分析法顧名思義就是從眾多因素中提取出來(lái)主要成分即幾個(gè)關(guān)鍵因素，通過(guò)這幾種關(guān)鍵因素的分析出整個(gè)數(shù)據(jù)的特點(diǎn)3，需要注意的是當(dāng)我們提取出的關(guān)鍵特征，這些特征能夠代表整個(gè)數(shù)據(jù)的特點(diǎn)，即可以通過(guò)這些特征線(xiàn)性的表示出整個(gè)數(shù)據(jù)的特征，這有點(diǎn)像唯物辯證法中的通過(guò)事物的表象看到事物的本質(zhì)，或者是根本矛盾決定一般矛盾，由于該方法提出時(shí)間較早4，且操作起來(lái)簡(jiǎn)單并且降維后的結(jié)果較好因此廣泛地被人們用于維數(shù)約簡(jiǎn)中。endprint考慮點(diǎn)集令對(duì)譜分解（1）其中，為對(duì)角陣，并且，為對(duì)應(yīng)的特征向量，主成分按照式（2）變換得到

9、（2）3.2 多維尺度變換高維數(shù)據(jù)在數(shù)據(jù)空間中通常具有如下特點(diǎn)，數(shù)據(jù)間存在一定的距離和相似性5，正如數(shù)據(jù)在高維空間具備一定的拓?fù)潢P(guān)系，而這種關(guān)系通常表現(xiàn)在數(shù)據(jù)之間的距離和相似性，而為了保持?jǐn)?shù)據(jù)的這些特點(diǎn)將高維的數(shù)據(jù)降低到有限維的二三維空間準(zhǔn)中，我們把這種降維的方法叫作多維尺度變換，根據(jù)變換時(shí)保留原始數(shù)據(jù)之間的特點(diǎn)不同，又分為度量和非度量的多維尺度變換6，具體變換方法如下：假設(shè)數(shù)據(jù)集，其中單個(gè)樣本點(diǎn)為，其中，為樣本點(diǎn)個(gè)數(shù)，為樣本點(diǎn)維數(shù)，設(shè)所有樣本組成的維矩陣為，樣本間兩兩內(nèi)積組成的矩陣為。樣本與之間歐氏距離為（3）距離矩陣為（4）其中，。定義中心化矩陣：。對(duì)距離矩陣雙中心化有（5）設(shè)對(duì)做特征值分

10、解：設(shè)為從大到小排列的特征值，為對(duì)應(yīng)的特征向量，取前個(gè)特征值和對(duì)應(yīng)的特征向量得到低維表示為（6）下面給出輸出求A的冪集P（A）的另一種遞歸算法：（1）若n=0，P（A）=，輸出空集；（2）若n1，輸出A中的一個(gè)元素an后，求集合A-an=a1，a2，an-1的冪集輸出，并將A-an=a1，a2，an-1的冪集的每一個(gè)元素與an并起來(lái)輸出。4 非線(xiàn)性降維（Nonlinear dimensionality reduction）4.1 等距映射算法Tenenbaum J B等人在2000年提出了Isomap算法7，8，此算法與多維尺度變換有些類(lèi)似，多維尺度主要考慮數(shù)據(jù)間是有距離的而這種距離也稱(chēng)為歐式

11、距離，在此基礎(chǔ)上提出了等距離映射算法，該算法首先需要計(jì)算出數(shù)據(jù)間的最短距離，用臨近路徑二維表表示，將最短距離轉(zhuǎn)化為測(cè)地線(xiàn)距離，進(jìn)而將高維數(shù)據(jù)降為低維數(shù)據(jù)，具體的轉(zhuǎn)換構(gòu)造方法如下：（1）構(gòu)造局部鄰域。計(jì)算每個(gè)樣本點(diǎn)的近鄰點(diǎn)集合，一般采用近鄰或鄰域法。近鄰法就是找出離點(diǎn)最近的個(gè)點(diǎn)，鄰域法就是找出離距離半徑為的園內(nèi)的所有樣本點(diǎn)。（2）構(gòu)造鄰域圖。若與為近鄰點(diǎn)，則邊的權(quán)值為與之間的歐氏距離，記為。否則。（3）計(jì)算距離矩陣。若與為近鄰點(diǎn)，即為近鄰點(diǎn)，則，否則。然后對(duì)逐個(gè)樣本點(diǎn)順次計(jì)算。（7）（4）應(yīng)用MDS算法求得低維嵌入坐標(biāo)。根據(jù)等距離算法得到的歐式距離如圖2所示。根據(jù)歐式距離圖得到對(duì)應(yīng)的測(cè)地線(xiàn)距離根

12、據(jù)以上的算法步驟得到降維后的數(shù)據(jù)如圖3所示。4.2 局部線(xiàn)性嵌入該方法是最早提出的一種非線(xiàn)性降維的方法，該方法的特點(diǎn)主要處理非線(xiàn)性類(lèi)數(shù)據(jù)，通過(guò)將非線(xiàn)性的數(shù)據(jù)轉(zhuǎn)換成局部線(xiàn)性的數(shù)據(jù)，同時(shí)保持?jǐn)?shù)據(jù)間距離對(duì)應(yīng)關(guān)系等，使其拓?fù)潢P(guān)系不發(fā)生變化，因此該方法的特點(diǎn)是處理非線(xiàn)性的數(shù)據(jù)同時(shí)具備線(xiàn)性數(shù)據(jù)的處理速度，因此此方法廣泛地應(yīng)用于維數(shù)約簡(jiǎn)算法中，具體算法步驟如圖4所示。（1）確定局部鄰域：假設(shè)流形數(shù)據(jù)集為，單個(gè)數(shù)據(jù)樣本點(diǎn)表示為，其中為樣本點(diǎn)個(gè)數(shù)，為樣本點(diǎn)維數(shù)，為近鄰點(diǎn)個(gè)數(shù)。樣本點(diǎn)與之間的距離為（8）（2）計(jì)算局部重構(gòu)權(quán)值矩陣，定義誤差函數(shù)，使其把用其近鄰的線(xiàn)性組合表示的誤差最小（9）其中，為的個(gè)最近鄰點(diǎn)為與之

13、間的權(quán)值。對(duì)于樣本點(diǎn)的近鄰點(diǎn)權(quán)值矩陣通過(guò)以下方法計(jì)算求得：計(jì)算鄰接關(guān)系矩陣即矩陣的元素是對(duì)應(yīng)的兩個(gè)鄰接點(diǎn)的內(nèi)積，并求出矩陣的逆矩陣。計(jì)算拉格朗日因子，是保證對(duì)的歸一化操作：令 （10）其中，。求（11）（3）利用權(quán)值矩陣求低維嵌入坐標(biāo)，其中保持不變。（12）并且滿(mǎn)足其中，表示維單位陣，就是降維后的數(shù)據(jù)。上述優(yōu)化問(wèn)題可以轉(zhuǎn)化為下列帶約束優(yōu)化問(wèn)題（13）其中，要使損失函數(shù)值達(dá)到最小。使用Lagrange乘子法則取為的個(gè)非零特征值所對(duì)應(yīng)的特征向量。在處理過(guò)程中將特征值由小到大排列，通常第一個(gè)特征值幾乎為零，取2到個(gè)特征值所對(duì)應(yīng)的特征向量作為輸出結(jié)果。4.3 拉普拉斯特征映射算法該算法與上述算法9，1

14、0也有很多相似之處，該方法是將數(shù)據(jù)間的關(guān)系用圖的形式表示出來(lái)，通過(guò)構(gòu)造數(shù)據(jù)間的鄰接表來(lái)表示數(shù)據(jù)，數(shù)據(jù)表示圖的一個(gè)頂點(diǎn)，同時(shí)鄰近表中重復(fù)的數(shù)據(jù)我們用圖的相似度來(lái)表示，通過(guò)這樣的一張無(wú)向有權(quán)圖來(lái)處理流形數(shù)據(jù)就是該算法的核心思想。具體的算法步驟如下：（1）構(gòu)造無(wú)權(quán)有向鄰接圖。使用近鄰或近鄰，對(duì)每個(gè)樣本點(diǎn)的個(gè)近鄰點(diǎn)分別連上邊?；蚴且粋€(gè)預(yù)先賦定的值。（2）確定權(quán)重：確定樣本點(diǎn)之間鄰接關(guān)系權(quán)重的大小，求權(quán)重時(shí)有兩種方法可供選擇。a.簡(jiǎn)單化設(shè)定，若點(diǎn)與為近鄰點(diǎn)，則令，否則。b.選用熱核函數(shù)來(lái)確定，若點(diǎn)與為近鄰點(diǎn)，那么它們關(guān)系權(quán)重否則為0。（3）計(jì)算低維嵌入向量，Laplacian Eigenmaps要優(yōu)化的

15、目標(biāo)函數(shù)如下：（14）endprint定義對(duì)角矩陣，對(duì)角線(xiàn)上位置元素為矩陣第行元素之和，上述優(yōu)化問(wèn)題等價(jià)于以下優(yōu)化問(wèn)題：（15）次優(yōu)化問(wèn)題最終轉(zhuǎn)化為解下列廣義的特征向量問(wèn)題。（16）其中，為對(duì)角矩陣，為近鄰圖的拉普拉斯算子，使用最小的m個(gè)非零特征值對(duì)應(yīng)的特征向量作為降維后的結(jié)果輸出。4.4 局部切空間排列算法該方法是由浙江大學(xué)張振躍等提出的11，12，該方法的特點(diǎn)就是構(gòu)造出數(shù)據(jù)樣本的局部切空間，而將這樣的切空間數(shù)據(jù)用對(duì)應(yīng)的鄰域表來(lái)表示，進(jìn)而將這些切空間數(shù)據(jù)嵌入到這樣的鄰域表，進(jìn)而完成了高維的D維空間嵌入到d維空間中，具體的描述步驟如下所述。非線(xiàn)性降維的目的是：在嵌入映射函數(shù)具體表達(dá)式未知下從函

16、數(shù)值得到其低維的坐標(biāo)表示。假設(shè)嵌入映射足夠光滑，在確定的點(diǎn)處應(yīng)用泰勒定理，得到下列泰勒式：（17）其中，為映射在處的雅克比矩陣，為的一個(gè)近鄰點(diǎn)，則有（18）由的個(gè)列向量張成在處的且空間，即，向量便為對(duì)應(yīng)放射子空間的一階逼近局部坐標(biāo)，因具體表達(dá)式未知，無(wú)法計(jì)算出雅克比矩陣，故可借助的表達(dá)式來(lái)表示，由的一組標(biāo)準(zhǔn)正交基組成的矩陣，即有形式（19）其中，的值依賴(lài)于局部結(jié)構(gòu)中心的值。令，則（20）式（20）中表示放射變換矩陣。全局坐標(biāo)表滿(mǎn)足（21）其中，為的鄰域，為了逼近全局坐標(biāo)，需要尋求全局坐標(biāo)系和局部放射變換是上述表達(dá)式誤差最小。故我們的目標(biāo)可總結(jié)為尋求全局坐標(biāo)系統(tǒng)和局部坐標(biāo)變換使下式達(dá)到最?。?2

17、）LTSA算法步驟如下13：（1）構(gòu)造局部鄰域。取離最近的個(gè)樣本點(diǎn)作為的近鄰點(diǎn)，構(gòu)成的鄰域矩陣，其中。（2）局部線(xiàn)性投影。對(duì)每個(gè)樣本點(diǎn)的鄰域，求其中心化矩陣（23）其中，即為元素全為1的列向量，對(duì)中心化后的矩陣進(jìn)行奇異值分解（24）其中，為的非零奇異值。和的列向量分別為一組標(biāo)準(zhǔn)正交基，。取的前列構(gòu)成矩陣。依據(jù)下式計(jì)算出局部坐標(biāo)（25）（3）局部坐標(biāo)系統(tǒng)排列。全局坐標(biāo)系統(tǒng)是所有交疊的局部坐標(biāo)系統(tǒng)排列得到。同時(shí)整體坐標(biāo)應(yīng)滿(mǎn)足（26）其中，是待求得局部放射變換，為局部重構(gòu)誤差，若令，則（27）式（27）為重構(gòu)誤差的表達(dá)式。為在保持局部拓?fù)浣Y(jié)構(gòu)求得低維嵌入坐標(biāo)，本算法通過(guò)使全局坐標(biāo)排列的重構(gòu)誤差達(dá)到最

18、小來(lái)得到全局坐標(biāo)：（28）5 算法比較分析（Algorithm comparison analysis）上文講述了不同的維數(shù)約簡(jiǎn)算法的原理和數(shù)學(xué)構(gòu)造方法，接下來(lái)我們就從運(yùn)行時(shí)間、復(fù)雜度分析和參數(shù)設(shè)置和算法特點(diǎn)幾個(gè)方面給予分析比較，具體結(jié)果如表1、表2、表3所示14-16。6 結(jié)論（Conclusion）文章介紹了維數(shù)約簡(jiǎn)的數(shù)學(xué)定義，從本質(zhì)上對(duì)維數(shù)約簡(jiǎn)進(jìn)行了分析介紹，維數(shù)約簡(jiǎn)的本質(zhì)是降維，對(duì)于數(shù)據(jù)的降維分為線(xiàn)性降維和非線(xiàn)性降維，因此維數(shù)約簡(jiǎn)算法也分為線(xiàn)性和非線(xiàn)性，本文主要介紹了線(xiàn)性典型算法有主成分分析PCA算法和多維尺度變換算法20，非線(xiàn)性算法著重介紹了等距特征映射，局部線(xiàn)性嵌入，拉普拉斯特征映

19、射，局部切空間排列算法，并對(duì)各個(gè)算法的優(yōu)缺點(diǎn)進(jìn)行了分析，文章從宏觀上對(duì)每個(gè)算法進(jìn)行了簡(jiǎn)要的描述，僅對(duì)有興趣致力于該方面研究的科技工作者給予參考和借鑒。參考文獻(xiàn)（References）1 陳省身，陳維恒.微分幾何講義M.北京：北京大學(xué)出版社，1983.2 Silva V De，Tenenbaum J B.Global versus local methods in nonlinear dimensionality reductionJ.Neural Information Processing Systems，2002，15：705-712.3 Pearson K.On lines and pl

20、anes of closest fit to systems of points in spaceJ.Philosophical Magazine，1901，2（6）：559-572.4 譚璐.高維數(shù)據(jù)的降維理論及應(yīng)用D.長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)研究生院，2005.5 尹俊松.流形學(xué)習(xí)理論與方法研究及在人臉識(shí)別中的應(yīng)用D.長(zhǎng)沙：國(guó)防科技大學(xué)碩士學(xué)位論文，2007.6 馬馳，張紅云，苗奪謙.改進(jìn)的主曲線(xiàn)算法在指紋骨架提取中的應(yīng)用J.計(jì)算機(jī)工程與應(yīng)用，2010，46（16）：170-173.7 吳曉婷.基于流形學(xué)習(xí)的數(shù)據(jù)降維算法研究D.大連：遼寧師范大學(xué)碩士論文，2010.8 Tenenbaum J

21、 B.Silva V de.Langford J C.A global geometric framework for nonlinear-ensionality reductionJ.Science，2000，290（5500）：2319-2323.9 Belkin M，Niyogi P.Laplacian eigenmaps and spectral techniques for embedding and clusteringJ.Neural Information Processing Systems，2002，14：585-591.endprint10 屠紅磊，黃靜.基于K段主曲線(xiàn)算法的手繪形狀識(shí)別J.計(jì)算機(jī)應(yīng)用，2009，29（2）：456-458.11 Zhang Z