【文章內(nèi)容簡(jiǎn)介】 提出了帶標(biāo)記的等距特征映射算法（Landmark ISOMAP）(De Silva and Tenenbaum, 2003)。針對(duì) ISOMAP 算法對(duì)于數(shù)據(jù)集噪聲敏感的問(wèn)題，Choi 等人通過(guò)觀察圖中的網(wǎng)絡(luò)流提出了一種消除臨界孤立點(diǎn)的方法以加強(qiáng) ISOMAP 算法的拓?fù)浞€(wěn)定性(Choi and Choi, 2007)。在構(gòu)建近鄰圖方面，Yang 提出通過(guò)構(gòu)造k 連通圖方式來(lái)確保近鄰圖的連通性，以提高測(cè)地距離的估計(jì)精度(Yang, 2005)。2009 年，Xiang 等人提出了局部樣條嵌入算法（LSE）(Xiang et al., 2006。Xiang et al., 2008)。Xiang 認(rèn)為，對(duì)于嵌入在高維輸入空間的低維流形，非線性維數(shù)約簡(jiǎn)的任務(wù)實(shí)際上是尋找一組非線性的復(fù)合映射，即由局部坐標(biāo)映射（Local Coordinatization Mapping）與全局排列映射（Global Alignment Mapping）復(fù)合而成的兼容映射（Compatible Mapping）。在兼容映射的概念框架下，LSE 算法首先通過(guò)主分量分析計(jì)算每個(gè)樣本點(diǎn)局部鄰域在切空間上的投影獲得該鄰域所有樣本的局部坐標(biāo)，從而保持流形的局部幾何結(jié)構(gòu)信息；然后采用Sobolev 空間的一組樣條函數(shù)把每個(gè)樣本點(diǎn)的局部坐標(biāo)映射成 全局唯一的低維坐標(biāo)。它們均是利用每個(gè)樣本的局部切空間來(lái)捕獲流形的局部幾何，樣本點(diǎn)在切空間的投影來(lái)表示樣本點(diǎn)的局部坐標(biāo)。然而它們的主要區(qū)別在于全局排列，LTSA 算法是利用仿射變換來(lái)進(jìn)行全局排列，而 LSE 算法是利用樣條函數(shù)來(lái)獲得全局唯一的坐標(biāo)。因此相對(duì)于 LTSA 而言，LSE 算法能夠?qū)崿F(xiàn)更小的重構(gòu)誤差。LSE 算法的主要缺點(diǎn)在于：一是無(wú)法保持全局尺度信息；二是不能學(xué)習(xí)具有較大曲率的低維流形結(jié)構(gòu)。除此，如何選擇滿足要求的樣條函數(shù)也是一個(gè)值得考慮的問(wèn)題。不同流形學(xué)習(xí)算法的區(qū)別在于所嘗試保持流形的局部鄰域結(jié)構(gòu)信息以及利用這些信息構(gòu)造全局嵌入的方法不同，與以往的維數(shù)約簡(jiǎn)方法相比，流形學(xué)習(xí)能夠有效地探索非線性流形分布數(shù)據(jù)的內(nèi)在規(guī)律與性質(zhì)。但是在實(shí)際應(yīng)用中流形學(xué)習(xí)方法仍然存在一些缺點(diǎn)，比如本征維數(shù)估計(jì)問(wèn)題、樣本外點(diǎn)學(xué)習(xí)問(wèn)題、監(jiān)督流形學(xué)習(xí)問(wèn)題和噪聲流形學(xué)習(xí)問(wèn)題等。為了解決這些問(wèn)題，相關(guān)的算法也不斷涌現(xiàn)出來(lái)。Freedman 等提出了一種基于簡(jiǎn)化單純復(fù)形的流形重構(gòu)方法來(lái)自動(dòng)估計(jì)流形的本征維數(shù)(Freedman, 2002)。為了解決樣本外點(diǎn)學(xué)習(xí)問(wèn)題，研究人員分別在流形學(xué)習(xí)的線性化、核化和張量化等方面作了有益的探索(Yan et al., 2007)。Geng 等將樣本的類別信息融入到 ISOMAP 算法，提出了一種用于可視化和分類的有監(jiān)督的等距特征映射算法（SISOMAP）(Geng et al., 2005)。Zhang 等提出了一種基于局部線性平滑的流形學(xué)習(xí)消噪模型(Zhang and Zha, 2003)。這些方法的提出在一定程度上緩解了目前流形學(xué)習(xí)方法中存在的一些問(wèn)題，但是還需要進(jìn)一步充實(shí)和完善。 流形學(xué)習(xí)的應(yīng)用目前，流形學(xué)習(xí)方法的應(yīng)用可歸納為以下幾個(gè)方面：1)數(shù)據(jù)的可視化。流形學(xué)習(xí)方法在高維數(shù)據(jù)的可視化方面有了廣泛的應(yīng)用。人不能直接感知高維數(shù)據(jù)的內(nèi)部結(jié)構(gòu)，但對(duì)三維以下數(shù)據(jù)的內(nèi)在結(jié)構(gòu)卻有很強(qiáng)的感知能力。由于流形學(xué)習(xí)方法可以發(fā)現(xiàn)高維觀測(cè)數(shù)據(jù)中蘊(yùn)含的內(nèi)在規(guī)律和本征結(jié)構(gòu)，而且這種規(guī)律在本質(zhì)上不依賴于我們實(shí)際觀測(cè)到的數(shù)據(jù)維數(shù)。因此我們可以通過(guò)流形學(xué)習(xí)方法 對(duì)高維輸入數(shù)據(jù)進(jìn)行維數(shù)約簡(jiǎn)，使高維數(shù)據(jù)的內(nèi)部關(guān)系和結(jié)構(gòu)在低于三維的空間中展示出來(lái)，從而使人們能夠直觀地認(rèn)識(shí)和了解高維的非線性數(shù)據(jù)的內(nèi)在規(guī)律，達(dá)到可視化的目的。2)信息檢索。隨著多媒體和網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，圖像和文本信息的應(yīng)用日益廣泛，對(duì)規(guī)模逐漸龐大的圖像和文本數(shù)據(jù)庫(kù)如何進(jìn)行有效的管理已成為亟待解決的問(wèn)題。靈活、高效、準(zhǔn)確的信息檢索策略是解決這一問(wèn)題的關(guān)鍵技術(shù)之一。這些圖像和文本信息呈現(xiàn)出高維、大規(guī)模、非線性結(jié)構(gòu)，利用流形學(xué)習(xí)方法來(lái)處理這些信息，在大大降低時(shí)間和空間計(jì)算復(fù)雜度的同時(shí)，能夠有效地保留這些信息在原始高維空間的相似性。3)圖像處理。流形學(xué)習(xí)給圖像處理領(lǐng)域提供了一個(gè)強(qiáng)有力的工具。眾所周知，圖像處理與圖像中物體的輪廓以及骨架等密切相關(guān)。如果我們把圖像中物體的輪廓以及骨架等看成是嵌入在二維平面中的一維流形或者由一組一維流形構(gòu)成，那么顯然流形學(xué)習(xí)方法憑借其強(qiáng)大的流形逼近能力可以應(yīng)用于圖像處理領(lǐng)域。第2章 流形學(xué)習(xí)方法綜述流形學(xué)習(xí)方法作為一種新興的非線性維數(shù)約簡(jiǎn)方法，主要目標(biāo)是獲取高維觀測(cè)數(shù)據(jù)的低維緊致表示，探索事物的內(nèi)在規(guī)律和本征結(jié)構(gòu)，已經(jīng)成為數(shù)據(jù)挖掘、模式識(shí)別和機(jī)器學(xué)習(xí)等領(lǐng)域的研究熱點(diǎn)。本章首先探討了流形學(xué)習(xí)的基礎(chǔ)性問(wèn)題，即高維數(shù)據(jù)分析的流形建模問(wèn)題；然后依據(jù)保持流形幾何特性的不同，把現(xiàn)有的流形學(xué)習(xí)方法劃分為全局特性保持方法和局部特性保持方法，并介紹了每一類方法中有代表性的流形學(xué)習(xí)算法的基本原理，對(duì)各種流形學(xué)習(xí)算法進(jìn)行性能比較和可視化分析，最后就流形學(xué)習(xí)方法普遍存在的本征維數(shù)估計(jì)、近鄰數(shù)選擇、噪聲流形學(xué)習(xí)、樣本外點(diǎn)學(xué)習(xí)和監(jiān)督流形學(xué)習(xí)問(wèn)題等進(jìn)行了分析和討論。 流形學(xué)習(xí)方法介紹流形學(xué)習(xí)的定義：流形是局部具有歐氏空間性質(zhì)的空間。假設(shè)數(shù)據(jù)是均勻采樣于一個(gè)高維歐氏空間中的低維流形，流形學(xué)習(xí)就是從高維采樣數(shù)據(jù)中恢復(fù)低維流形結(jié)構(gòu)，即找到高維空間中的低維流形，并求出相應(yīng)的嵌入映射，以實(shí)現(xiàn)維數(shù)約簡(jiǎn)或者數(shù)據(jù)可視化。它是從觀測(cè)到的現(xiàn)象中去尋找事物的本質(zhì)，找到產(chǎn)生數(shù)據(jù)的內(nèi)在規(guī)律。流形學(xué)習(xí)用數(shù)學(xué)語(yǔ)言描述是：令Y206。(yi)且166。: Y174。194。是一個(gè)光滑的嵌套，其中D d。那么流形學(xué)習(xí)的目標(biāo)是基于194。上的一個(gè)給定被觀測(cè)數(shù)據(jù)集合(xi)去恢復(fù)Y與166。，也就是在Y 中隨機(jī)產(chǎn)生隱藏的數(shù)據(jù)(yi)，然后通過(guò)166。 映射到觀測(cè)空間，使得{xi=f(yi)}。從流形學(xué)習(xí)的定義中可以看出，這是一個(gè)把數(shù)據(jù)從高維映射到低維的過(guò)程，用到了線性變換，當(dāng)然少不了矩陣的分解及其基本運(yùn)算。 多維尺度分析（Multidimensional Scaling, MDS）多維尺度分析（Multidimensional Scaling, MDS）是一種經(jīng)典的線性降維方法，其主要思想是：根據(jù)數(shù)據(jù)點(diǎn)間的歐氏距離，構(gòu)造關(guān)系矩陣，為了盡可能地保持每對(duì)觀測(cè)數(shù)據(jù)點(diǎn)間的歐氏距離，只需對(duì)此關(guān)系矩陣進(jìn)行特征分解，從而獲得每個(gè)數(shù)據(jù)在低維空間中的低維坐標(biāo)。DDDx206。194。x設(shè)給定的高維觀測(cè)數(shù)據(jù)點(diǎn)集為Y=lU，i，觀測(cè)數(shù)據(jù)點(diǎn)對(duì)i，Tyj間的歐氏距離為Dij=xiyj，傳統(tǒng)MDS 的算法步驟如下：a)首先根據(jù)求出的兩點(diǎn)之間的歐氏距離Dij構(gòu)造n階平方歐式距離矩陣A=(Dij2) n180。n。b)將矩陣A進(jìn)行雙中心化計(jì)算，即計(jì)算B=1HAH2（其中H 為中心化eeTH=In，將矩陣H左乘和右乘時(shí)稱為雙中心化）矩陣。c)計(jì)算低維坐標(biāo)Y。即將B奇異值分解，設(shè)B的最大的d個(gè)特征值L=diag(l1,l2,...,ld)Y=lUT。235。u1,u2,...,ud249。則d維低維坐標(biāo)為，對(duì)應(yīng)特征向量，U=233。雖然作為線性方法，MDS在流形學(xué)習(xí)中不能有效發(fā)現(xiàn)內(nèi)在低維結(jié)構(gòu)。但是從這一基本的算法中我們可以清楚的看出矩陣分析在流形學(xué)習(xí)研究中的應(yīng)用。在這個(gè)MDS算法中，運(yùn)用到了矩陣中的線性空間變換、矩陣特征值和特征向量的計(jì)算、矩陣的中心化計(jì)算、矩陣的奇異值的分解等相關(guān)知識(shí)點(diǎn)。想象一下，如果沒(méi)有這些知識(shí)點(diǎn)做基礎(chǔ)，這些算法如何進(jìn)行。 等距特征映射（ISOMAP）（1）基本思想:Tenenbaum等人提出的等距特征映射算法（ISOMAP）是建立在多維尺度分析（MDS）基礎(chǔ)上的一種非線性維數(shù)約簡(jiǎn)方法。ISOMAP算法利用所有樣本點(diǎn)對(duì)之間的測(cè)地距離矩陣來(lái)代替MDS算法中的歐氏距離矩陣，以保持嵌入在高