技術報告維數(shù)約簡算法簡述

1、計劃類別 項目編號 項目技術報告課題名稱 項目主持人 承擔單位 題目：維數(shù)約簡算法簡述機器學習是近幾年研究的熱點，維數(shù)約簡算法是機器學習的必要手段，本文從維數(shù)約簡算法的定義講起，介紹了幾種典型的數(shù)據(jù)降維算法，其中包括線性降維和非線性降維，流形學習是非線性降維的代表算法。并且介紹了每個算法的構造過程及其特點，在此基礎上分析了所有維數(shù)約簡算法的執(zhí)行效率時間和空間復雜度，并且給出了每個算法的特點和算法的核心思想，最后在此基礎上給予總結，為后面研究者提供參考和借鑒。關鍵詞：機器學習；維數(shù)約簡；數(shù)據(jù)降維；線性降維；非線性降維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）機器學習是近幾年比較火的一個研究方向，不論在模式識別還是圖像處理方面都要用到機器學習的理論，機器學習中有個重要的方面研究就是如何把大數(shù)據(jù)量內容降低成有限的維數(shù)，從而提高機器學習的速度，這里面用到一個關鍵的算法就是維數(shù)約簡算法，它的原理就是通過線性和非線性的方法，將高維數(shù)據(jù)降低到可以解的低維數(shù)據(jù)從而提高機器學習的速度。接下來文章將從維數(shù)約簡數(shù)學定義說起，緊接著介紹常用的幾種維數(shù)約簡算法，并且給出這些算法的優(yōu)缺點，最后給出總結為后續(xù)做研究的人提供指引和方向。2 維數(shù)約簡數(shù)學定義（Mathematical definition o

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

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

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

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

10、解：設為從大到小排列的特征值，為對應的特征向量，取前個特征值和對應的特征向量得到低維表示為（6）下面給出輸出求A的冪集P（A）的另一種遞歸算法：（1）若n=0，P（A）=，輸出空集；（2）若n1，輸出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ù)間是有距離的而這種距離也稱為歐式

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

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

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

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

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

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

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

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

19、射，局部切空間排列算法，并對各個算法的優(yōu)缺點進行了分析，文章從宏觀上對每個算法進行了簡要的描述，僅對有興趣致力于該方面研究的科技工作者給予參考和借鑒。參考文獻（References）1 陳省身，陳維恒.微分幾何講義M.北京：北京大學出版社，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ù)的降維理論及應用D.長沙：國防科學技術大學研究生院，2005.5 尹俊松.流形學習理論與方法研究及在人臉識別中的應用D.長沙：國防科技大學碩士學位論文，2007.6 馬馳，張紅云，苗奪謙.改進的主曲線算法在指紋骨架提取中的應用J.計算機工程與應用，2010，46（16）：170-173.7 吳曉婷.基于流形學習的數(shù)據(jù)降維算法研究D.大連：遼寧師范大學碩士論文，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段主曲線算法的手繪形狀識別J.計算機應用，2009，29（2）：456-458.11 Zhang Z