流形學(xué)習(xí)的理論與方法研究.pdf

1、科學(xué)的進(jìn)步，特別是信息產(chǎn)業(yè)的發(fā)展，把我們帶入了一個(gè)嶄新的信息時(shí)代。在信息時(shí)代的科學(xué)研究過程中，不可避免的會(huì)遇到大量的高維數(shù)據(jù)，如全球氣候模型、圖像分類系統(tǒng)、文本聚類和基因序列的建模等。在實(shí)際應(yīng)用中，用高維數(shù)據(jù)來表示的觀測(cè)點(diǎn)可以模擬成可能帶有噪音的低維非線性流形上的樣本點(diǎn)或者逼近這些樣本點(diǎn)。因此，數(shù)據(jù)降維尤其是非線性降維成為數(shù)據(jù)挖掘的一個(gè)重要手段，進(jìn)行降維的目的是為了從高維空間中找出隱藏的低維結(jié)構(gòu)。 過去幾年來，非線性降維在包括數(shù)

2、據(jù)挖掘、機(jī)器學(xué)習(xí)、圖像分析和計(jì)算機(jī)視覺等許多研究領(lǐng)域都吸引了廣泛的關(guān)注。最近，已經(jīng)發(fā)展出一些有效的算法來進(jìn)行非線性降維。這些算法包括等距映射(Isomap)、局部線性嵌入(LLE)以及它的變換形式：海賽局部線性嵌入(HLLE)和局部切空間排列(LTSA)等。所有的這些算法都有一個(gè)共同的特征：找出每個(gè)數(shù)據(jù)點(diǎn)周圍的局部性質(zhì)以及采用這些所收集到的局部性質(zhì)信息將流形非線性的映射到一個(gè)低維的空間中。然而，這些算法的實(shí)現(xiàn)在收集鄰域的局部信息以及采用

3、這些收集的局部信息構(gòu)造全局的嵌入上都是不同的。比如，Isomap利用每個(gè)鄰域的鄰域點(diǎn)之間的聯(lián)系和歐氏距離在數(shù)據(jù)點(diǎn)上構(gòu)造出一個(gè)圖，并根據(jù)圖距離來估計(jì)出所有數(shù)據(jù)點(diǎn)之間的測(cè)地距離。構(gòu)造出的全局低維坐標(biāo)需要保持估計(jì)的測(cè)地距離。LLE找出每個(gè)點(diǎn)同它的鄰域點(diǎn)之間的一個(gè)線性組合關(guān)系，并且由此決定保持這種線性組合結(jié)構(gòu)的低維嵌入。LTSA將每個(gè)點(diǎn)的鄰域點(diǎn)投影到它在流形上的局部切空間上，然后排列所有的局部坐標(biāo)來決定低維的全局坐標(biāo)。顯然的，局部幾何結(jié)構(gòu)的恢復(fù)

4、效率決定了這些算法的效率。 LLE是流形學(xué)習(xí)方面經(jīng)典的局部非線性方法，它有參數(shù)少、計(jì)算快、易求全局最優(yōu)解等優(yōu)點(diǎn)，并在圖像分類、圖像識(shí)別、譜重建、數(shù)據(jù)可視化等方面都有著廣泛的應(yīng)用。但是，LLE可能會(huì)將相隔較遠(yuǎn)的點(diǎn)映射到低維空間中鄰近點(diǎn)的位置，從而導(dǎo)致嵌入結(jié)果有著比較明顯的扭曲。這其中的一個(gè)重要原因是，LLE采用的單個(gè)重構(gòu)權(quán)并不能完全的反映出流形的局部幾何性質(zhì)。此外，用以求解重構(gòu)權(quán)的有約束的最小二乘問題的最優(yōu)解也許不是唯一的，而且L

5、LE采用正則化方法求解涉及到正則因子γ的選取，難以保證所求的解是最優(yōu)解。這些都是LLE所面臨的問題。 有一些共同的因素影響著流形學(xué)習(xí)方法的效果。流形學(xué)習(xí)方法首先面臨的是鄰域選取的問題，需要選取出一個(gè)合適的鄰域以獲取局部的線性信息，鄰域選取的結(jié)果直接影響著最終的嵌入結(jié)果。很顯然的，鄰域越小可以認(rèn)為鄰域的線性結(jié)構(gòu)越明顯，但是我們需要注意的是，鄰域之間需要有足夠的交疊以保證較遠(yuǎn)的點(diǎn)之間有足夠的聯(lián)系，這又使得鄰域不能過小。從直觀上想像，

6、流形上曲率大的樣本點(diǎn)的鄰域應(yīng)該小一些，而流形上曲率小的樣本點(diǎn)處的鄰域可以大一些。因此，關(guān)于鄰域選取的主要困難在于：在加強(qiáng)樣本點(diǎn)之間的關(guān)聯(lián)性的時(shí)候，應(yīng)該如何自適應(yīng)的選取鄰域以匹配流形的局部幾何性質(zhì)?此外，流形上的曲率以及樣本點(diǎn)密度的變化，不可避免的會(huì)使得所尋找的局部鄰域結(jié)構(gòu)產(chǎn)生偏差。在利用這些局部鄰域結(jié)構(gòu)來構(gòu)造全局的低維嵌入時(shí)，需要將這些偏差計(jì)入考慮范圍。因此，流形學(xué)習(xí)還面臨著這些問題：如何估計(jì)流形上的曲率?如何估計(jì)流形曲率和樣本點(diǎn)密度的

7、變化對(duì)尋找局部鄰域結(jié)構(gòu)的影響?在利用局部鄰域結(jié)構(gòu)來構(gòu)造全局的低維嵌入時(shí)，應(yīng)該如何計(jì)入這種影響以減輕低維嵌入的偏差?對(duì)于上述問題，本文給出了較完善的解答。本文的主要貢獻(xiàn)如下： 1.我們對(duì)LLE的重構(gòu)權(quán)向量的性質(zhì)進(jìn)行詳細(xì)的分析，在理論上證明了(用正則化方法)確定最優(yōu)權(quán)在數(shù)值上是不穩(wěn)定的，同時(shí)在給定精度下，存在著多組線性無關(guān)的近似最優(yōu)權(quán)向量。 2.我們提出了修正的局部線性嵌入方法(ModifiedLocallyLinearEm

8、beddingUsingMultipleWeights，簡(jiǎn)稱MLLE)，采用線性無關(guān)的權(quán)向量來建立鄰域內(nèi)穩(wěn)定的局部線性結(jié)構(gòu)，并在低維嵌入中保持這種局部線性結(jié)構(gòu)。MLLE改善了LLE方法的穩(wěn)定性和有效性。 3.我們從理論上證明了MLLE對(duì)采自等距流形的樣本點(diǎn)有著理想的結(jié)果，通過MLLE和LTSA之間的詳細(xì)對(duì)比和理論分析，揭示了LLE、MLLE和LTSA之間的內(nèi)在聯(lián)系。這為進(jìn)一步理解與分析建立了基礎(chǔ)。 4.我們提出了自適應(yīng)鄰

9、域選取的方法，以解決非線性降維方法中面臨的鄰域選取的難題?；卩徲蚓植烤€性逼近的分析，我們給出了決定鄰域集是否能在一個(gè)給定精度內(nèi)被一個(gè)線性擬合所逼近的標(biāo)準(zhǔn)。進(jìn)而提出兩個(gè)算法(采用鄰域壓縮和鄰域擴(kuò)張策略)來選取能夠滿足這個(gè)標(biāo)準(zhǔn)的鄰域。我們的方法從理論上保證了所選出的鄰域在匹配流形的局部幾何性質(zhì)的前提下，能夠盡可能地?cái)U(kuò)張鄰域以加強(qiáng)樣本點(diǎn)之間的關(guān)聯(lián)性。自適應(yīng)鄰域選取方法能適用于所有基于鄰域的流形學(xué)習(xí)方法。 5.我們給出估計(jì)流形局部曲率

10、的方法，并通過引入流形的局部曲率來修正LTSA中的極小化模型。這個(gè)改進(jìn)能減少LTSA造構(gòu)造全局嵌入的偏差。結(jié)合自適應(yīng)的鄰域選取和曲率修正，我們提出了一種自適應(yīng)的流形學(xué)習(xí)方法一自適應(yīng)局部切空間排列方法(Adaptivelocaltangentspacealignment，簡(jiǎn)稱ALTSA)。雖然曲率模型是針對(duì)LTSA而設(shè)計(jì)，但我們相信所提出的基本思想也能適用于其它的流形學(xué)習(xí)方法。 6.我們給出了大量的數(shù)值例子(模擬例子和實(shí)際例子)，