大數(shù)據(jù)課程報(bào)告

摘要流形學(xué)習(xí)辦法作為一類新興的非線性維數(shù)約簡(jiǎn)辦法，重要目的是獲取高維觀察數(shù)據(jù)的低維緊致表達(dá)，探索事物的內(nèi)在規(guī)律和本征構(gòu)造，已經(jīng)成為數(shù)據(jù)挖掘、模式識(shí)別和機(jī)器學(xué)習(xí)等領(lǐng)域的研究熱點(diǎn)。流形學(xué)習(xí)辦法的非線性本質(zhì)、幾何直觀性和計(jì)算可行性，使得它在許多原則的toy數(shù)據(jù)集和實(shí)際數(shù)據(jù)集上都獲得了令人滿意的成果，然而它們本身還存在著某些普遍性的問(wèn)題，例如泛化學(xué)習(xí)問(wèn)題、監(jiān)督學(xué)習(xí)問(wèn)題和大規(guī)模流形學(xué)習(xí)問(wèn)題等。因此，本文從流形學(xué)習(xí)辦法存在的問(wèn)題出發(fā)，在算法設(shè)計(jì)和應(yīng)用（圖像數(shù)據(jù)與蛋白質(zhì)互相作用數(shù)據(jù)）等方面展開(kāi)了一系列研究工作。首先對(duì)流形學(xué)習(xí)的典型辦法做了具體對(duì)比分析，然后針對(duì)流形的泛化學(xué)習(xí)和監(jiān)督學(xué)習(xí)、表征流形的局部幾何構(gòu)造、構(gòu)造全局的正則化線性回歸模型、大規(guī)模數(shù)據(jù)的流形學(xué)習(xí)等幾個(gè)方面進(jìn)行了重點(diǎn)研究，提出了三種有效的流形學(xué)習(xí)算法，并和有關(guān)研究成果進(jìn)行了理論與實(shí)驗(yàn)上的比較，從而驗(yàn)證了我們所提算法的有效性。核心詞：流形學(xué)習(xí)，維數(shù)約簡(jiǎn)，正交局部樣條鑒別投影，局部多尺度回歸嵌入目錄TOC\o"1-4"\h\z\u目錄 2第1章 研究背景 31.1 流形學(xué)習(xí)的研究背景 31.2 流形學(xué)習(xí)的研究現(xiàn)狀 41.3 流形學(xué)習(xí)的應(yīng)用 6第2章 流形學(xué)習(xí)辦法綜述 72.1 流形學(xué)習(xí)辦法介紹 8第3章 流形學(xué)習(xí)辦法存在的問(wèn)題 113.1 本征維數(shù)預(yù)計(jì) 113.2 近鄰數(shù)選擇 123.3 噪聲流形學(xué)習(xí) 123.4 監(jiān)督流形學(xué)習(xí) 13第4章 總結(jié) 13研究背景流形學(xué)習(xí)的研究背景隨著信息時(shí)代的到來(lái)，使得數(shù)據(jù)集更新更快、數(shù)據(jù)維度更高以及非構(gòu)造化性等問(wèn)題更突出。在科研研究的過(guò)程中不可避免地碰到大量的高維數(shù)據(jù)，這就需要一種技術(shù)能夠使在保持?jǐn)?shù)據(jù)信息足夠完整的意義下從海量數(shù)據(jù)集中提取出有效而又合理的約簡(jiǎn)數(shù)據(jù)，滿足人的存儲(chǔ)需求和感知需要。流形學(xué)習(xí)這一非監(jiān)督學(xué)習(xí)辦法應(yīng)運(yùn)而生，引發(fā)越來(lái)越多機(jī)器學(xué)習(xí)和認(rèn)知科學(xué)工作者的重視。而在海量的高維數(shù)據(jù)中，往往只有少量的有用信息，如果想快速高效的收集到人們想要的、有用的那些少量信息且快速的解決信息，這就需要某些核心技術(shù)的支持，即是必須采用對(duì)應(yīng)的降維技術(shù)。而流形學(xué)習(xí)正是在數(shù)據(jù)降維方面有著重要的奉獻(xiàn)。然而，降維的過(guò)程與《矩陣分析》中的內(nèi)容有著親密的關(guān)系?；诹餍蔚慕稻S辦法能充足運(yùn)用數(shù)據(jù)中所隱藏的低維有價(jià)值信息，進(jìn)一步提高檢索性能。Seung從神經(jīng)心理學(xué)的角度提出“感知以流形的形式存在，視覺(jué)記憶也可能是以穩(wěn)態(tài)的流形存儲(chǔ)”，為流形提供了與人類認(rèn)識(shí)有關(guān)的理由。流形學(xué)習(xí)的辦法重要有主成分分析（PCA）、多維尺度化（MDS）、基于局部切空間排列法（LTSA）和基于等度規(guī)映射（ISOMAP）、局部線性嵌入算法（LLE）、拉普拉斯特性映射（LE）等。另外，流形學(xué)習(xí)辦法在人臉識(shí)別、圖像解決、模式識(shí)別、計(jì)算機(jī)視覺(jué)、認(rèn)知科學(xué)、人工智能、人機(jī)交互等眾多學(xué)科中有著廣泛的應(yīng)用。線性維數(shù)約簡(jiǎn)辦法是通過(guò)在高維輸入空間與低維子空間之間建立線性映射關(guān)系，把高維數(shù)據(jù)樣本集投影到低維線性子空間。線性維數(shù)約簡(jiǎn)技術(shù)普通假設(shè)數(shù)據(jù)集采樣于一種全局線性的高維觀察空間。如果所要解決的數(shù)據(jù)集分布確實(shí)呈現(xiàn)出全局線性的構(gòu)造，或者在一定程度上能夠近似為全局線性構(gòu)造，則這些辦法能夠有效地挖掘出數(shù)據(jù)集內(nèi)在的線性構(gòu)造，獲得數(shù)據(jù)緊致的低維表達(dá)。在線性維數(shù)約簡(jiǎn)辦法中，使用最廣泛的算法有主分量分析（PrincipalComponentAnalysis,PCA）(Jolliffe,;TurkandPentland,1991)和線性鑒別分析（LinearDiscriminantAnalysis,LDA）(Dudaetal.,)。主分量分析（PCA）重要是根據(jù)高維數(shù)據(jù)在低維空間重構(gòu)誤差最小的原則，來(lái)尋找一組最優(yōu)的單位正交向量基（即主分量），并通過(guò)保存數(shù)據(jù)分布方差較大的若干主分量來(lái)達(dá)成降維的目的。然而，眾所周知，由于PCA算法沒(méi)有運(yùn)用數(shù)據(jù)樣本的類別信息，因此它是一種非監(jiān)督的線性維數(shù)約簡(jiǎn)辦法。與PCA算法不同，LDA算法考慮到樣本的類別信息，它是一種有監(jiān)督的辦法?；诟黝悩颖痉母咚狗植记也煌惖膮f(xié)方差矩陣相似的假設(shè)，LDA算法在Fisher準(zhǔn)則下選擇最優(yōu)的投影向量，以使得數(shù)據(jù)樣本的類間散度最大而類內(nèi)散度最小。由于LDA算法運(yùn)用了樣本的類別信息，而樣本的類別信息普通有助于改善識(shí)別率，因此LDA算法更合用于分類問(wèn)題。流形學(xué)習(xí)的研究現(xiàn)狀流形學(xué)習(xí)假定輸入數(shù)據(jù)是嵌入在高維觀察空間的低維流形上，流形學(xué)習(xí)辦法的目的是找出高維數(shù)據(jù)中所隱藏的低維流形構(gòu)造。通過(guò)十?dāng)?shù)年的研究與探索，人們提出了大量的流形學(xué)習(xí)理論與算法。典型的流形學(xué)習(xí)辦法有等距特性映射算法（ISOMAP）(Tenenbaumetal.,)、局部線性嵌入算法（LLE）(RoweisandSaul,;SaulandRoweis,)、Laplacian特性映射算法（LaplacianEigenmaps，LE）(BelkinandNiyogi,;BelkinandNiyogi,)、Hessian特性映射算法（Hessian-basedLocallyLinearEmbedding，HLLE）(DonohoandGrimes,)、最大差別展開(kāi)算法（MaximumVarianceUnfolding，MVU）(Weinbergeretal.,;WeinbergerandSaul,;WeinbergerandSaul,;Weinbergeretal.,)、局部切空間排列算法（LocalTangentSpaceAlignment,LTSA）(ZhangandZha,)、黎曼流形學(xué)習(xí)算法（RiemannianManifoldLearning,RML）(LinandZha,;Linetal.,)和局部樣條嵌入算法（LocalSplineEmbedding，LSE）(Xiangetal.,;Xiangetal.,)等。Tenenbaum提出的ISOMAP算法是多維尺度分析（MultidimensionalScaling,MDS）(CoxandCox,1994)在流形框架下的非線性推廣，其核心思想是用測(cè)地距離替代歐氏距離來(lái)表征流形上數(shù)據(jù)點(diǎn)的內(nèi)在幾何關(guān)系。對(duì)于樣本點(diǎn)和它的近鄰點(diǎn)之間的測(cè)地距離用它們之間的歐氏距離來(lái)替代；對(duì)于樣本點(diǎn)和近鄰點(diǎn)之外的點(diǎn)之間的測(cè)地距離用它們之間的最短途徑來(lái)替代。Bernstein等人證明了只要樣本是隨機(jī)抽取的，在樣本集足夠大且選擇適宜近鄰參數(shù)k時(shí)，近鄰圖上兩點(diǎn)的最短途徑能夠逼近它們的測(cè)地距離(Bernsteinetal.,)。當(dāng)應(yīng)用于內(nèi)蘊(yùn)平坦的凸流形時(shí)，ISOMAP算法能夠忠實(shí)地捕獲數(shù)據(jù)內(nèi)在的低維流形構(gòu)造(DeSilvaandTenenbaum,)。ISOMAP算法的重要缺點(diǎn)在于：①對(duì)樣本點(diǎn)的噪聲比較敏感；②對(duì)于含有較大曲率或稀疏采樣的數(shù)據(jù)集，不能發(fā)現(xiàn)其內(nèi)在的本征構(gòu)造；③需要計(jì)算全體數(shù)據(jù)集的測(cè)地距離矩陣，因此算法的時(shí)間復(fù)雜度較高。圍繞ISOMAP算法，已經(jīng)出現(xiàn)了許多有關(guān)的理論分析與研究工作。Balasubramanian等人對(duì)ISOMAP算法的拓?fù)浞€(wěn)定性進(jìn)行了進(jìn)一步探討(BalasubramanianandSchwartz,)。對(duì)于數(shù)據(jù)分布所在的低維流形含有較大的內(nèi)在曲率狀況，deSilva和Tenenbaum提出了保角等距特性映射算法（conformalISOMAP）(DeSilvaandTenenbaum,)。為了減小ISOMAP算法的計(jì)算復(fù)雜度，deSilva和Tenenbaum提出了帶標(biāo)記的等距特性映射算法（LandmarkISOMAP）(DeSilvaandTenenbaum,)。針對(duì)ISOMAP算法對(duì)于數(shù)據(jù)集噪聲敏感的問(wèn)題，Choi等人通過(guò)觀察圖中的網(wǎng)絡(luò)流提出了一種消除臨界孤立點(diǎn)的辦法以加強(qiáng)ISOMAP算法的拓?fù)浞€(wěn)定性(ChoiandChoi,)。在構(gòu)建近鄰圖方面，Yang提出通過(guò)構(gòu)造k連通圖方式來(lái)確保近鄰圖的連通性，以提高測(cè)地距離的預(yù)計(jì)精度(Yang,)。年，Xiang等人提出了局部樣條嵌入算法（LSE）(Xiangetal.,;Xiangetal.,)。Xiang認(rèn)為，對(duì)于嵌入在高維輸入空間的低維流形，非線性維數(shù)約簡(jiǎn)的任務(wù)事實(shí)上是尋找一組非線性的復(fù)合映射，即由局部坐標(biāo)映射（LocalCoordinatizationMapping）與全局排列映射（GlobalAlignmentMapping）復(fù)合而成的兼容映射（CompatibleMapping）。在兼容映射的概念框架下，LSE算法首先通過(guò)主分量分析計(jì)算每個(gè)樣本點(diǎn)局部鄰域在切空間上的投影獲得該鄰域全部樣本的局部坐標(biāo)，從而保持流形的局部幾何構(gòu)造信息；然后采用Sobolev空間的一組樣條函數(shù)把每個(gè)樣本點(diǎn)的局部坐標(biāo)映射成全局唯一的低維坐標(biāo)。它們均是運(yùn)用每個(gè)樣本的局部切空間來(lái)捕獲流形的局部幾何，樣本點(diǎn)在切空間的投影來(lái)表達(dá)樣本點(diǎn)的局部坐標(biāo)。然而它們的重要區(qū)別在于全局排列，LTSA算法是運(yùn)用仿射變換來(lái)進(jìn)行全局排列，而LSE算法是運(yùn)用樣條函數(shù)來(lái)獲得全局唯一的坐標(biāo)。因此相對(duì)于LTSA而言，LSE算法能夠?qū)崿F(xiàn)更小的重構(gòu)誤差。LSE算法的重要缺點(diǎn)在于：一是無(wú)法保持全局尺度信息；二是不能學(xué)習(xí)含有較大曲率的低維流形構(gòu)造。除此，如何選擇滿足規(guī)定的樣條函數(shù)也是一種值得考慮的問(wèn)題。不同流形學(xué)習(xí)算法的區(qū)別在于所嘗試保持流形的局部鄰域構(gòu)造信息以及運(yùn)用這些信息構(gòu)造全局嵌入的辦法不同，與以往的維數(shù)約簡(jiǎn)辦法相比，流形學(xué)習(xí)能夠有效地探索非線性流形分布數(shù)據(jù)的內(nèi)在規(guī)律與性質(zhì)。但是在實(shí)際應(yīng)用中流形學(xué)習(xí)辦法仍然存在某些缺點(diǎn)，例如本征維數(shù)預(yù)計(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)預(yù)計(jì)流形的本征維數(shù)(Freedman,)。為理解決樣本外點(diǎn)學(xué)習(xí)問(wèn)題，研究人員分別在流形學(xué)習(xí)的線性化、核化和張量化等方面作了有益的探索(Yanetal.,)。Geng等將樣本的類別信息融入到ISOMAP算法，提出了一種用于可視化和分類的有監(jiān)督的等距特性映射算法（S-ISOMAP）(Gengetal.,)。Zhang等提出了一種基于局部線性平滑的流形學(xué)習(xí)消噪模型(ZhangandZha,)。這些辦法的提出在一定程度上緩和了現(xiàn)在流形學(xué)習(xí)辦法中存在的某些問(wèn)題，但是還需要進(jìn)一步充實(shí)和完善。流形學(xué)習(xí)的應(yīng)用現(xiàn)在，流形學(xué)習(xí)辦法的應(yīng)用可歸納為下列幾個(gè)方面：數(shù)據(jù)的可視化。流形學(xué)習(xí)辦法在高維數(shù)據(jù)的可視化方面有了廣泛的應(yīng)用。人不能直接感知高維數(shù)據(jù)的內(nèi)部構(gòu)造，但對(duì)三維下列數(shù)據(jù)的內(nèi)在構(gòu)造卻有很強(qiáng)的感知能力。由于流形學(xué)習(xí)辦法能夠發(fā)現(xiàn)高維觀察數(shù)據(jù)中蘊(yùn)含的內(nèi)在規(guī)律和本征構(gòu)造，并且這種規(guī)律在本質(zhì)上不依賴于我們實(shí)際觀察到的數(shù)據(jù)維數(shù)。因此我們能夠通過(guò)流形學(xué)習(xí)辦法對(duì)高維輸入數(shù)據(jù)進(jìn)行維數(shù)約簡(jiǎn)，使高維數(shù)據(jù)的內(nèi)部關(guān)系和構(gòu)造在低于三維的空間中展示出來(lái)，從而使人們能夠直觀地認(rèn)識(shí)和理解高維的非線性數(shù)據(jù)的內(nèi)在規(guī)律，達(dá)成可視化的目的。信息檢索。隨著多媒體和網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，圖像和文本信息的應(yīng)用日益廣泛，對(duì)規(guī)模逐步龐大的圖像和文本數(shù)據(jù)庫(kù)如何進(jìn)行有效的管理已成為亟待解決的問(wèn)題。靈活、高效、精確的信息檢索方略是解決這一問(wèn)題的核心技術(shù)之一。這些圖像和文本信息呈現(xiàn)出高維、大規(guī)模、非線性構(gòu)造，運(yùn)用流形學(xué)習(xí)辦法來(lái)解決這些信息，在大大減少時(shí)間和空間計(jì)算復(fù)雜度的同時(shí)，能夠有效地保存這些信息在原始高維空間的相似性。圖像解決。流形學(xué)習(xí)給圖像解決領(lǐng)域提供了一種強(qiáng)有力的工具。眾所周知，圖像解決與圖像中物體的輪廓以及骨架等親密有關(guān)。如果我們把圖像中物體的輪廓以及骨架等當(dāng)作是嵌入在二維平面中的一維流形或者由一組一維流形構(gòu)成，那么顯然流形學(xué)習(xí)辦法憑借其強(qiáng)大的流形逼近能力能夠應(yīng)用于圖像解決領(lǐng)域。流形學(xué)習(xí)辦法綜述流形學(xué)習(xí)辦法作為一種新興的非線性維數(shù)約簡(jiǎn)辦法，重要目的是獲取高維觀察數(shù)據(jù)的低維緊致表達(dá)，探索事物的內(nèi)在規(guī)律和本征構(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ì)多個(gè)流形學(xué)習(xí)算法進(jìn)行性能比較和可視化分析，最后就流形學(xué)習(xí)辦法普遍存在的本征維數(shù)預(yù)計(jì)、近鄰數(shù)選擇、噪聲流形學(xué)習(xí)、樣本外點(diǎn)學(xué)習(xí)和監(jiān)督流形學(xué)習(xí)問(wèn)題等進(jìn)行了分析和討論。流形學(xué)習(xí)辦法介紹流形學(xué)習(xí)的定義：流形是局部含有歐氏空間性質(zhì)的空間。假設(shè)數(shù)據(jù)是均勻采樣于一種高維歐氏空間中的低維流形，流形學(xué)習(xí)就是從高維采樣數(shù)據(jù)中恢復(fù)低維流形構(gòu)造，即找到高維空間中的低維流形，并求出對(duì)應(yīng)的嵌入映射，以實(shí)現(xiàn)維數(shù)約簡(jiǎn)或者數(shù)據(jù)可視化。它是從觀察到的現(xiàn)象中去尋找事物的本質(zhì)，找到產(chǎn)生數(shù)據(jù)的內(nèi)在規(guī)律。流形學(xué)習(xí)用數(shù)學(xué)語(yǔ)言描述是：令Y且:Y是一種光滑的嵌套，其中D>>d。那么流形學(xué)習(xí)的目的是基于上的一種給定被觀察數(shù)據(jù)集合去恢復(fù)Y與，也就是在Y中隨機(jī)產(chǎn)生隱藏的數(shù)據(jù)，然后通過(guò)映射到觀察空間，使得。從流形學(xué)習(xí)的定義中能夠看出，這是一種把數(shù)據(jù)從高維映射到低維的過(guò)程，用到了線性變換，固然少不了矩陣的分解及其基本運(yùn)算。2.1.1多維尺度分析（MultidimensionalScaling,MDS）多維尺度分析（MultidimensionalScaling,MDS）是一種典型的線性降維辦法，其重要思想是：根據(jù)數(shù)據(jù)點(diǎn)間的歐氏距離，構(gòu)造關(guān)系矩陣，為了盡量地保持每對(duì)觀察數(shù)據(jù)點(diǎn)間的歐氏距離，只需對(duì)此關(guān)系矩陣進(jìn)行特性分解，從而獲得每個(gè)數(shù)據(jù)在低維空間中的低維坐標(biāo)。設(shè)給定的高維觀察數(shù)據(jù)點(diǎn)集為，，觀察數(shù)據(jù)點(diǎn)對(duì),間的歐氏距離為，傳統(tǒng)MDS的算法環(huán)節(jié)以下：a)首先根據(jù)求出的兩點(diǎn)之間的歐氏距離構(gòu)造n階平方歐式距離矩陣。b)將矩陣A進(jìn)行雙中心化計(jì)算，即計(jì)算（其中H為中心化矩陣，，將矩陣H左乘和右乘時(shí)稱為雙中心化）。c)計(jì)算低維坐標(biāo)Y。即將B奇異值分解，設(shè)B的最大的d個(gè)特性值，對(duì)應(yīng)特性向量，則d維低維坐標(biāo)為。即使作為線性辦法，MDS在流形學(xué)習(xí)中不能有效發(fā)現(xiàn)內(nèi)在低維構(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)行。2.1.2等距特性映射（ISOMAP）（1）基本思想:Tenenbaum等人提出的等距特性映射算法（ISOMAP）是建立在多維尺度分析（MDS）基礎(chǔ)上的一種非線性維數(shù)約簡(jiǎn)辦法。ISOMAP算法運(yùn)用全部樣本點(diǎn)對(duì)之間的測(cè)地距離矩陣來(lái)替代MDS算法中的歐氏距離矩陣，以保持嵌入在高維觀察空間中內(nèi)在低維流形的全局幾何特性。算法的核心是計(jì)算每個(gè)樣本點(diǎn)與全部其它樣本點(diǎn)之間的測(cè)地距離。對(duì)于近鄰點(diǎn)，運(yùn)用輸入空間的歐氏距離直接得到其測(cè)地距離；對(duì)于非近鄰點(diǎn)，運(yùn)用近鄰圖上兩點(diǎn)之間的最短途徑近似測(cè)地距離。然后對(duì)于構(gòu)造的全局測(cè)地距離矩陣，運(yùn)用MDS算法在高維輸入空間與低維嵌入空間之間建立等距映射，從而發(fā)現(xiàn)嵌入在高維空間的內(nèi)在低維表達(dá)(Tenenbaumetal.,)。（2）算法流程<1>構(gòu)造近鄰圖G<2>計(jì)算最短途徑<3>計(jì)算d維嵌入(3)算法分析ISOMAP算法是一種保持全局幾何特性的辦法，它的低維嵌入成果能夠反映出高維觀察樣本所在流形上的測(cè)地距離。如果高維觀察樣本所在的低維流形與歐氏空間的一種子集是整體等距的，且與樣本所在流形等距的歐氏空間的子集是一種凸集，那么ISOMAP算法能夠獲得比較抱負(fù)的嵌入成果。但是當(dāng)流形曲率較大或者流形上有“孔洞”，即與流形等距的歐氏空間的子集非凸時(shí)，流形上的測(cè)地距離預(yù)計(jì)會(huì)產(chǎn)生較大的誤差，造成嵌入成果產(chǎn)生變形。從算法的時(shí)間復(fù)雜度來(lái)看，ISOMAP算法有兩個(gè)計(jì)算瓶頸(DeSilvaandTenenbaum,)。第一種是計(jì)算n×n的最短途徑距離矩陣DG。當(dāng)使用Floyd算法時(shí)，計(jì)算復(fù)雜度為O(n3)；若采用Dijkstra算法，可將計(jì)算復(fù)雜度減少到O(kn2logn)（k為近鄰數(shù)大?。?Cormen,)。第二個(gè)計(jì)算瓶頸源于應(yīng)用MDS時(shí)的特性分解。由于距離矩陣是稠密的，因此特性分解的計(jì)算復(fù)雜度為O(n3)。從中我們能夠看出，隨著樣本個(gè)數(shù)n的增大，ISOMAP算法計(jì)算效率低下的問(wèn)題會(huì)變得十分突出。2.1.3局部線性嵌入（LLE）1、基本思想與ISOMAP和MVU算法不同，局部線性嵌入算法（LLE）是一種局部特性保持辦法。LLE算法的核心是保持降維前后近鄰之間的局部線性構(gòu)造不變。算法的重要思想是假定每個(gè)數(shù)據(jù)點(diǎn)與它的近鄰點(diǎn)位于流形的一種線性或近似線性的局部鄰域，在該鄰域中的數(shù)據(jù)點(diǎn)能夠由其近鄰點(diǎn)來(lái)線性表達(dá)，重建低維流形時(shí)，對(duì)應(yīng)的內(nèi)在低維空間中的數(shù)據(jù)點(diǎn)保持相似的局部近鄰關(guān)系，即低維流形空間的每個(gè)數(shù)據(jù)點(diǎn)用其近鄰點(diǎn)線性表達(dá)的權(quán)重與它們?cè)诟呔S觀察空間中的線性表達(dá)權(quán)重相似，而各個(gè)局部鄰域之間的互相重疊部分則描述了由局部線性到全局非線性的排列信息(RoweisandSaul,)。這樣就能夠把高維輸入數(shù)據(jù)映射到全局唯一的低維坐標(biāo)系統(tǒng)。2、算法流程LLE算法的基本環(huán)節(jié)分為三步：選擇鄰域計(jì)算重構(gòu)權(quán)值矩陣W求低維嵌入Y3、算法分析通過(guò)前面算法描述我們不難發(fā)現(xiàn)，LLE算法能夠?qū)W習(xí)任意維含有局部線性構(gòu)造的低維流形。它以重構(gòu)權(quán)值矩陣作為高維觀察空間與低維嵌入空間之間聯(lián)系的橋梁，使得數(shù)據(jù)點(diǎn)與其近鄰點(diǎn)在平移、旋轉(zhuǎn)和縮放等變化下保持近鄰關(guān)系不變。并且LLE算法含有解析的全局最優(yōu)解，無(wú)需迭代。在算法的計(jì)算復(fù)雜度上，選擇鄰域的計(jì)算復(fù)雜度為O(Dn2)，計(jì)算重構(gòu)權(quán)值矩陣的計(jì)算復(fù)雜度為O((D+k)k2n)，求解低維嵌入Y的計(jì)算復(fù)雜度為O(dn2)。因此與ISOMAP和MVU算法相比，LLE算法的計(jì)算復(fù)雜度要小得多。但LLE算法也存在某些缺點(diǎn)：①由于LLE算法只是保持局部近鄰的重構(gòu)權(quán)值關(guān)系，并不是保持距離關(guān)系，因此，LLE算法普通不能較好的恢復(fù)出含有等距性質(zhì)的流形。②LLE算法但愿樣本集均勻稠密采樣于低維流形，因此，對(duì)于受噪聲污染、樣本密度稀疏或互有關(guān)聯(lián)較弱的數(shù)據(jù)集，在從高維觀察空間到低維嵌入空間的映射過(guò)程中，可能會(huì)將互有關(guān)聯(lián)較弱的遠(yuǎn)點(diǎn)映射到局部近鄰點(diǎn)的位置，從而破壞了低維嵌入成果。流形學(xué)習(xí)辦法存在的問(wèn)題流形學(xué)習(xí)相對(duì)于傳統(tǒng)的線性維數(shù)約簡(jiǎn)辦法來(lái)說(shuō)，它能夠更加好地發(fā)現(xiàn)高維復(fù)雜非線性數(shù)據(jù)內(nèi)在的幾何構(gòu)造與規(guī)律。但其多個(gè)算法本身還存在著某些普遍性的問(wèn)題，例如本征維數(shù)預(yù)計(jì)問(wèn)題、近鄰數(shù)選擇問(wèn)題、噪聲流形學(xué)習(xí)問(wèn)題、泛化學(xué)習(xí)問(wèn)題和監(jiān)督學(xué)習(xí)問(wèn)題等。本小節(jié)將對(duì)這些問(wèn)題進(jìn)行簡(jiǎn)要的分析和討論。本征維數(shù)預(yù)計(jì)本征維數(shù)預(yù)計(jì)是流形學(xué)習(xí)的一種基本問(wèn)題(趙連偉etal.,)。本征維數(shù)普通被定義為描述數(shù)據(jù)集中全部數(shù)據(jù)所需要的自由參數(shù)（或獨(dú)立坐標(biāo)）的最小數(shù)目。它反映了隱藏在高維觀察數(shù)據(jù)中潛在低維流形的拓?fù)鋵傩?。在非線性維數(shù)約簡(jiǎn)過(guò)程中，本征維數(shù)預(yù)計(jì)的精確與否對(duì)低維空間的嵌入成果有著重要的影響。如果本征維數(shù)預(yù)計(jì)過(guò)大，將會(huì)保存數(shù)據(jù)的冗余信息，使嵌入成果中含有噪聲；相反如果本征維數(shù)預(yù)計(jì)過(guò)小，將會(huì)丟失數(shù)據(jù)的有用信息，造成高維空間中不同的點(diǎn)在低維空間可能會(huì)交疊。因此，設(shè)計(jì)穩(wěn)定可靠的本征維數(shù)預(yù)計(jì)辦法將有助于流形學(xué)習(xí)算法的應(yīng)用和性能的改善?，F(xiàn)在現(xiàn)有的本征維數(shù)預(yù)計(jì)辦法大致分為兩大類：特性映射法和幾何學(xué)習(xí)法(Camastra,)。特性映射法涉及全局PCA辦法(Bennett,1969)、局部PCA辦法(BruskeandSommer,1998;FukunagaandOlsen,1971)和多維尺度分析辦法(CoxandCox,)，它重要運(yùn)用了數(shù)據(jù)分布的本征特性是數(shù)據(jù)的局部特性的基本思想，對(duì)局部數(shù)據(jù)進(jìn)行特性分解，選用對(duì)應(yīng)特性值最大的特性向量作為本征特性。顯然，這類辦法所預(yù)計(jì)的本征維數(shù)大小在很大程度上取決于數(shù)據(jù)的局部鄰域劃分和閾值的選擇，因此特性映射辦法不能提供本征維數(shù)的可靠預(yù)計(jì)。幾何學(xué)習(xí)法重要基于近來(lái)鄰距離（NearestNeighborDistances）或分形維（FractalDimension）(Camastra,)來(lái)探索數(shù)據(jù)集所蘊(yùn)含的幾何信息，這類辦法普通需要充足的樣本數(shù)，因此，對(duì)于樣本數(shù)少、觀察空間維數(shù)較高的狀況，經(jīng)常會(huì)出現(xiàn)本征維數(shù)欠預(yù)計(jì)的狀況。近鄰數(shù)選擇流形學(xué)習(xí)探測(cè)低維流形構(gòu)造成功與否在很大程度上取決于近鄰數(shù)的選擇(Zeng,)，然而在構(gòu)造近鄰圖時(shí)如何選擇一種適宜的近鄰數(shù)是一種公開(kāi)的問(wèn)題。如果近鄰數(shù)選擇過(guò)大，將會(huì)產(chǎn)生“短路邊”現(xiàn)象（“short-circuit”edges），從而嚴(yán)重破壞原始流形數(shù)據(jù)的拓?fù)溥B通性。噪聲流形學(xué)習(xí)當(dāng)觀察數(shù)據(jù)均勻稠密采樣于一種抱負(fù)的低維光滑流形時(shí)，流形學(xué)習(xí)辦法能夠成功地挖掘出其內(nèi)在的低維構(gòu)造和本質(zhì)規(guī)律。但是在實(shí)際應(yīng)用中，我們經(jīng)常發(fā)現(xiàn)高維采樣數(shù)據(jù)由于受多個(gè)因素的影響，普通總是存在著噪聲和污染，這將勢(shì)必影響流形學(xué)習(xí)算法的低維嵌入成果。監(jiān)督流形學(xué)習(xí)現(xiàn)有的流形學(xué)習(xí)辦法多數(shù)用于無(wú)監(jiān)督學(xué)習(xí)狀況，如解決降維與數(shù)據(jù)可視化等問(wèn)題。當(dāng)已知數(shù)據(jù)的類別信息，如何運(yùn)用這些信息有效地改善原始流形學(xué)習(xí)算法的分類識(shí)別能力是監(jiān)督流形學(xué)習(xí)所要解決的問(wèn)題。從數(shù)據(jù)分類的角度來(lái)看，人們但愿高維觀察數(shù)據(jù)通過(guò)維數(shù)約簡(jiǎn)后在低維空間中類內(nèi)差別小而類間差別大，從而有助于樣本的分類識(shí)別。原始的流形學(xué)習(xí)算法都是無(wú)監(jiān)督學(xué)習(xí)過(guò)程，某些引進(jìn)監(jiān)督信息的改善算法紛紛被提出來(lái)(Lietal.,;Zhaoetal.,)。這些辦法的基本思想是運(yùn)用樣本的類別信息指導(dǎo)構(gòu)建有監(jiān)督的近鄰圖，然后運(yùn)用流形學(xué)習(xí)辦法進(jìn)行低維嵌入。盡管這些辦法能夠獲得較好的分類成果，但是這種通過(guò)類別屬性構(gòu)建的近鄰圖往往會(huì)被分割成多個(gè)互不相連的子圖，而不是一種完整的近鄰圖，這就給原始流形學(xué)習(xí)算法的最后應(yīng)用帶來(lái)了很大的不便?？偨Y(jié)流形學(xué)習(xí)是一種含有基礎(chǔ)性、前瞻性的研究方向，其研究成果和技術(shù)已經(jīng)立刻應(yīng)用于模式識(shí)別、計(jì)算機(jī)視覺(jué)、圖像解決等有關(guān)領(lǐng)域。如高維數(shù)據(jù)的可視化、可聽(tīng)化；基于內(nèi)容檢索的模型；視頻中三維對(duì)象的跟蹤和檢測(cè)；從靜態(tài)二維圖像中進(jìn)行三維對(duì)象的姿態(tài)預(yù)計(jì)和識(shí)別；二維和三維對(duì)象的形狀重構(gòu)；從運(yùn)動(dòng)中構(gòu)建構(gòu)造、從陰影中成形等。另外流形學(xué)習(xí)還應(yīng)用于自然語(yǔ)言解決、基因體現(xiàn)分析等生物信息解決領(lǐng)域，特別是在基因體現(xiàn)分析中，用于檢測(cè)和分辨不同的疾病和疾病類型。

盡管流形學(xué)習(xí)的算法和應(yīng)用在過(guò)去的幾年中已經(jīng)獲得了豐碩的成果，但是由于其數(shù)學(xué)理論基礎(chǔ)較為深厚復(fù)雜，以及多個(gè)學(xué)科之間交叉融合，因此仍有許多亟需研究和解決的問(wèn)題，特別在下述幾個(gè)方面：

1.現(xiàn)在已有諸多流形學(xué)習(xí)算法，但諸多算法只是建立在實(shí)驗(yàn)的基礎(chǔ)之上，并沒(méi)有充足理論基礎(chǔ)支持，因此我們首先要進(jìn)一步探索能夠有效學(xué)習(xí)到流形局部幾何和拓?fù)錁?gòu)造的算法，提高流形投影算法的性能，另外更重要的是要不停完善理論基礎(chǔ)。

2.各支幾何都是研究空間在變換群下的不變性，微分幾何亦是如此。而諸多狀況下我們正需要這種不變性，因此研究局部樣本密度、噪聲水平、流形的正則性、局部曲率、撓率構(gòu)造的交互作用對(duì)流形學(xué)習(xí)的研究有主動(dòng)增進(jìn)作用。

3.統(tǒng)計(jì)學(xué)習(xí)理論得到充足發(fā)展并逐步成熟，流形學(xué)習(xí)理論在其基礎(chǔ)上發(fā)展自然能夠把統(tǒng)計(jì)學(xué)中有用的技術(shù)應(yīng)用于流形學(xué)習(xí)中，如流形上的取樣和MonteCarlo預(yù)計(jì)、假設(shè)檢查，以及流形上有關(guān)不變測(cè)度的概率分布密度問(wèn)題，都值得進(jìn)一步研究。

4.現(xiàn)在大部分學(xué)習(xí)算法都是基于局部的，而基于局部算法一種很大缺點(diǎn)就在于受噪聲影響較大，因此要研究減小局部辦法對(duì)于噪聲和離群值的影響，提高學(xué)習(xí)算法魯棒性及泛化能力。5.譜辦法對(duì)噪聲十分敏感。但愿大家自己做做實(shí)驗(yàn)體會(huì)一下，流形學(xué)習(xí)中譜辦法的脆弱。6.采樣問(wèn)題對(duì)成果的影響。7.一種最尷尬的事情莫過(guò)于，如果用來(lái)做識(shí)別，流形學(xué)習(xí)線性化的辦法比原來(lái)非線性的辦法效果要好得多，如果用原始辦法做識(shí)別，那個(gè)效果叫一種差。也正由于此，使諸多人對(duì)流形學(xué)習(xí)產(chǎn)生了懷疑。8.把偏微分幾何辦法引入到流形學(xué)習(xí)中來(lái)是一種很有但愿的方向。這樣的工作在近來(lái)一年已有出現(xiàn)的跡象。

參考文獻(xiàn)[1]R.BasriandD.W.Jacobs.L