基于低秩結(jié)構(gòu)學(xué)習(xí)數(shù)據(jù)表示.pdf

1、隨著計(jì)算機(jī)硬件及采樣技術(shù)的發(fā)展，海量高維數(shù)據(jù)的獲取也變得越來(lái)越容易，例如圖像與視頻數(shù)據(jù)、文本與網(wǎng)頁(yè)數(shù)據(jù)等。那些高維數(shù)據(jù)不但會(huì)顯著地增加計(jì)算和存儲(chǔ)代價(jià)，也使得推理、學(xué)習(xí)和識(shí)別等任務(wù)無(wú)法完成，并對(duì)傳統(tǒng)的機(jī)器學(xué)習(xí)與統(tǒng)計(jì)分析理論提出了嚴(yán)峻的挑戰(zhàn)，如維數(shù)災(zāi)難和小樣本問(wèn)題等。如何獲取高維數(shù)據(jù)的低維表示并探索其內(nèi)在規(guī)律及本質(zhì)結(jié)構(gòu)，已成為機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識(shí)別、計(jì)算機(jī)視覺(jué)及統(tǒng)計(jì)分析等領(lǐng)域研究的熱點(diǎn)問(wèn)題。
　　維數(shù)約簡(jiǎn)可在很大程度上避免維數(shù)災(zāi)

2、難，使得學(xué)習(xí)任務(wù)(如分類或聚類等)更加穩(wěn)定和高效。然而很多經(jīng)典的維數(shù)約簡(jiǎn)技術(shù)存在著一定的局限性，比如傳統(tǒng)譜聚類算法、低秩矩陣恢復(fù)與填充算法與非參數(shù)核學(xué)習(xí)算法的計(jì)算復(fù)雜度非常高，通常是樣本數(shù)n的立方或者O(n6.5)；傳統(tǒng)的非負(fù)矩陣分解沒(méi)有充分考慮數(shù)據(jù)與特征的幾何結(jié)構(gòu)，以及半監(jiān)督數(shù)據(jù)表示學(xué)習(xí)沒(méi)有利用核矩陣固有的低秩結(jié)構(gòu)信息等。因此，本論文以學(xué)習(xí)數(shù)據(jù)的有效表示為主題，通過(guò)挖掘數(shù)據(jù)本身固有的結(jié)構(gòu)如幾何結(jié)構(gòu)、稀疏與低秩結(jié)構(gòu)等信息來(lái)更有效地學(xué)習(xí)數(shù)

3、據(jù)的表示。另外，再加以利用可獲得的少量監(jiān)督信息如少量標(biāo)簽數(shù)據(jù)或成對(duì)約束等來(lái)學(xué)習(xí)數(shù)據(jù)更有效的表示。從利用的信息由少到多，所取得的主要研究成果為：
　　1.提出了一種局部與全局一致性的兩階段譜聚類框架，可充分挖掘利用數(shù)據(jù)分布空間的拓?fù)鋷缀闻c低秩結(jié)構(gòu)來(lái)學(xué)習(xí)數(shù)據(jù)的有效表示。該框架主要包括兩個(gè)階段：第一階段是利用快速采樣算法獲得少量樣本代表點(diǎn)(簡(jiǎn)稱代表點(diǎn))；第二階段是由正交化的密度加權(quán)Nystrom低秩近似方法來(lái)得到全部數(shù)據(jù)的低維數(shù)據(jù)表示。

4、在此框架下，首先定義了局部和全局兩種距離測(cè)度方法，可準(zhǔn)確地反映數(shù)據(jù)的幾何結(jié)構(gòu)；然后又提出了一種快速兩階段近鄰傳播采樣算法，可得到少量富含信息的代表點(diǎn)，該采樣算法是一種非均勻采樣的方式；最后給出了一種快速密度加權(quán)低秩近似譜聚類算法。該算法不但在聚類質(zhì)量、效率及內(nèi)存需求方面都超過(guò)了傳統(tǒng)的譜聚類與近鄰傳播方法，而且可處理較大規(guī)模數(shù)據(jù)的問(wèn)題，學(xué)習(xí)獲得的數(shù)據(jù)表示可應(yīng)用于后面的章節(jié)。
　　2.提出了一種雙圖正則的非負(fù)矩陣分解框架，可充分利用數(shù)

5、據(jù)的流形與低秩結(jié)構(gòu)來(lái)學(xué)習(xí)非負(fù)數(shù)據(jù)的有效表示。該框架同時(shí)考慮了數(shù)據(jù)流形和特征流形的幾何結(jié)構(gòu)，并分別在數(shù)據(jù)空間和特征空間創(chuàng)建兩個(gè)近鄰圖來(lái)反映它們各自的幾何流形結(jié)構(gòu)。在此框架下，首先給出了一種雙圖正則非負(fù)矩陣分解模型，并推導(dǎo)了一種交替迭代更新規(guī)則；作為上述模型的拓展，然后又提出了一種雙圖正則非負(fù)矩陣三分解模型，并提供了一種交替迭代更新算法；最后分別提供了兩種算法的收斂性證明。大量的實(shí)驗(yàn)結(jié)果表明提出的兩種算法比相關(guān)算法的聚類性能更好，并能學(xué)習(xí)得

6、到更有效的基于部分的數(shù)據(jù)表示。
　　3.提出了一種魯棒低秩矩陣分解框架，可充分利用數(shù)據(jù)的稀疏與低秩結(jié)構(gòu)恢復(fù)被幅值較大的噪聲或奇異點(diǎn)損壞的數(shù)據(jù)，而且還能填充丟失的數(shù)據(jù)。傳統(tǒng)的核范數(shù)最小化算法每次迭代都需要對(duì)較大規(guī)模的矩陣進(jìn)行奇異值分解，故此它們具有很高的時(shí)間復(fù)雜度。為了克服上述算法的局限性，把矩陣分解的思想引入到傳統(tǒng)的核范數(shù)最小化模型中。再根據(jù)給定數(shù)據(jù)分布于單線性子空間或多子空間，分別給出了兩種不同的魯棒低秩矩陣分解模型。提出的兩種

7、優(yōu)化問(wèn)題分別為核范數(shù)與l1或l2，1范數(shù)最小化的混合問(wèn)題，又提供了一種基于交替方向法的迭代求解算法。最后再推廣到低秩矩陣填充問(wèn)題，并給出了一種相應(yīng)的交替迭代求解算法。
　　4.提出了一種基于核矩陣元素分類的數(shù)據(jù)表示學(xué)習(xí)框架，可充分利用數(shù)據(jù)的幾何與低秩結(jié)構(gòu)及給定的少量成對(duì)約束信息。該框架以圖Laplacian的譜嵌入作為輔助，再利用成對(duì)約束信息去提升它得到新的數(shù)據(jù)表示。為了更準(zhǔn)確地刻畫(huà)數(shù)據(jù)的幾何結(jié)構(gòu)，首先創(chuàng)建了一種對(duì)稱偏好近鄰圖。然

8、后基于平方損失函數(shù)，把學(xué)習(xí)數(shù)據(jù)表示的問(wèn)題轉(zhuǎn)化為一個(gè)半正定二次線性規(guī)劃問(wèn)題，可由常用的半正定規(guī)劃軟件包如SDPT3進(jìn)行有效地求解。最后再把學(xué)習(xí)得到數(shù)據(jù)表示應(yīng)用于半監(jiān)督聚類及直推式分類問(wèn)題。
　　5.提出了一種基于理想核矩陣填充學(xué)習(xí)數(shù)據(jù)表示的框架，可充分利用數(shù)據(jù)的幾何和低秩結(jié)構(gòu)及給定的少量成對(duì)約束信息。由于一般給定的成對(duì)約束的數(shù)目比精確重構(gòu)低秩核矩陣需要的采樣數(shù)目少很多，因此也考慮把圖Laplacian的譜嵌入作為輔助，進(jìn)而把整個(gè)較大

9、規(guī)模核矩陣的求解轉(zhuǎn)化為一個(gè)較小規(guī)模的對(duì)稱半正定矩陣求解問(wèn)題。上述的模型還是一個(gè)核范數(shù)正則最小二乘問(wèn)題。然后又提出了一種特征值迭代閾值算法去有效地求解給出的優(yōu)化問(wèn)題。最后還提供了該算法收斂于其最優(yōu)解的嚴(yán)格理論證明。
　　6.提出了一種基于復(fù)合信息的半監(jiān)督學(xué)習(xí)框架，可充分利用數(shù)據(jù)的幾何和低秩結(jié)構(gòu)及給定的少量數(shù)據(jù)標(biāo)簽與成對(duì)約束信息。該框架不但能利用少量的樣本標(biāo)簽與給定的成對(duì)約束信息，還能利用了大量的無(wú)標(biāo)簽數(shù)據(jù)。基于上述的框架，給出了一種