基于圖論的機(jī)器學(xué)習(xí)算法設(shè)計及在神經(jīng)網(wǎng)絡(luò)中的應(yīng)用研究.pdf

1、機(jī)器學(xué)習(xí)是人工智能的一個分支，其研究的目標(biāo)是構(gòu)建一個能夠從數(shù)據(jù)中自主學(xué)習(xí)出一定的規(guī)律（或模式）并將此規(guī)律應(yīng)用于后續(xù)數(shù)據(jù)處理的系統(tǒng)。作為一個基礎(chǔ)性的學(xué)科分支，機(jī)器學(xué)習(xí)在許多領(lǐng)域有著重要的應(yīng)用，例如生物信息學(xué)、人工智能、航空航天、現(xiàn)代醫(yī)學(xué)等。
　　圖論作為一個數(shù)學(xué)分支，其在機(jī)器學(xué)習(xí)中的研究與應(yīng)用近年來得到了快速的發(fā)展?；趫D論的機(jī)器學(xué)習(xí)算法就是把機(jī)器學(xué)習(xí)的問題歸結(jié)為圖論的問題，然后利用圖論理論進(jìn)行分析和求解的一類學(xué)習(xí)算法。相比較于其他

2、算法模型，基于圖論的機(jī)器學(xué)習(xí)算法有著以下優(yōu)勢：一、圖論作為一個數(shù)學(xué)分支，有著深厚的數(shù)學(xué)理論背景，這為對機(jī)器學(xué)習(xí)算法從理論上分析做了必要的準(zhǔn)備。二、圖論具有模型簡單、概括力強(qiáng)的特點，這使得很多問題可以利用圖論模型進(jìn)行描述和求解。三、圖論模型可以利用矩陣描述并利用線性代數(shù)和矩陣?yán)碚撝R進(jìn)行分析和求解，因此表達(dá)形式簡潔但富有概括力，同時便于進(jìn)行深入理論分析。四、基于圖論譜分析的機(jī)器學(xué)習(xí)算法很多具有閉合的解析解表達(dá)式，或者可以利用凸優(yōu)化理論進(jìn)行

3、求解，這樣可以求得全局最優(yōu)解，避免局部最優(yōu)解。
　　已有的基于圖論的機(jī)器算法研究主要集中在兩個方面：一個是基于圖論的半監(jiān)督學(xué)習(xí)算法，包括半監(jiān)督分類算法、半監(jiān)督降維等；二是基于圖論的無監(jiān)督學(xué)習(xí)算法，包括譜聚類算法、無監(jiān)督降維算法等。雖然已有算法在很多應(yīng)用中取得了成功，但仍有許多不足，概況說來有以下幾點：一、圖論的半監(jiān)督學(xué)習(xí)算法已被成功應(yīng)用于許多領(lǐng)域，其主要特點是能夠利用極少量標(biāo)記樣本對大量未標(biāo)記樣本進(jìn)行分類，這就減少了很多用于標(biāo)記樣

4、本時所消耗的人力和財力等資源。但半監(jiān)督學(xué)習(xí)多為直推式學(xué)習(xí)且/或預(yù)測新樣本時運算量較大。監(jiān)督學(xué)習(xí)的優(yōu)勢是能夠在輸入樣本空間中構(gòu)建一個監(jiān)督模型，從而對已見樣本和未見樣本都能高效地進(jìn)行直接分類；其缺陷是要構(gòu)建一個具有很好泛化能力的模型往往需要大量標(biāo)記樣本進(jìn)行訓(xùn)練。能否將二者的優(yōu)勢結(jié)合，利用極少標(biāo)記樣本在輸入空間中構(gòu)建出一個具有良好泛化能力的高效監(jiān)督模型是一個很值得探討的問題，具有很大的實用價值。本文在這方面進(jìn)行了嘗試。二、現(xiàn)有的聚類算法，如譜

5、聚類，雖然能夠在很多情況下取得較好的結(jié)果，但在應(yīng)對高維非線性流形分布的數(shù)據(jù)時仍然有不足，具體表現(xiàn)為：對于不同流形分布出現(xiàn)交疊或有類間有大量歧義點時聚類結(jié)果往往不滿意或者需要進(jìn)行復(fù)雜的非光滑優(yōu)化問題求解，從而需要很大的計算量和內(nèi)存開銷；更進(jìn)一步，聚類算法對于每個類別，無法在給出類別標(biāo)記信息的同時給出此類中最具代表性的樣本點，而這一點在如視頻或者文本自動摘要上有著重要應(yīng)用。三、在處理時空分布數(shù)據(jù)（spatio-temporal data)時

6、，由于時空分布數(shù)據(jù)具有一定的空間分布特性，同時這種分布特性在時間上可能存在不斷演化，而且此類數(shù)據(jù)的數(shù)據(jù)量一般較大。傳統(tǒng)的機(jī)器學(xué)習(xí)算法（如SVM）適合于處理靜態(tài)的向量數(shù)據(jù)，其很難學(xué)習(xí)和描述此類時空數(shù)據(jù)中蘊(yùn)含的這種復(fù)雜的、動態(tài)的時空交互演化關(guān)系。針對以上問題，本文主要工作和創(chuàng)新點可歸結(jié)為以下幾個方面：
　　一、本文對基于圖論的半監(jiān)督學(xué)習(xí)算法Local and Global Consistency(LGC)進(jìn)行了改進(jìn)，使其具備“各向異性

7、”的傳播特性，即在高樣本密度區(qū)域具有較快的標(biāo)記信息傳播，在低樣本密度區(qū)具有較慢的標(biāo)記信息傳播，從而抑制類間區(qū)域的不正確標(biāo)記信息傳播。在此基礎(chǔ)上本文提出了一種兩步學(xué)習(xí)的新型監(jiān)督學(xué)習(xí)框架，能夠在極少的標(biāo)記樣本數(shù)量情況下在輸入空間中構(gòu)建并學(xué)習(xí)一個具有良好泛化能力的監(jiān)督模型。
　　二、受到LGC算法和流形排序算法的啟發(fā)，本文把傳統(tǒng)歐氏空間中點云中心概念拓展到黎曼幾何中流形中心概念，提出了一種基于圖論的k均值算法用于非線性流形聚類。該算法不

8、僅對傳統(tǒng)高斯分布類型數(shù)據(jù)（適合于經(jīng)典k均值算法）具有很好的效果，而且對于（低維）流形分布的高維數(shù)據(jù)同樣能夠給出很好的聚類結(jié)果，同時給每一類選出一個最具代表性的樣本點，這些代表點在數(shù)據(jù)集壓縮及自動摘要上有著重要的應(yīng)用。
　　三、進(jìn)一步，本文針對以上算法中（也是許多其他圖論算法中）的關(guān)鍵排序矩陣的計算量大的特點，提出了一種時間和空間均為線性復(fù)雜度的快速算法，對于大樣本集具有很好的可擴(kuò)展性，并把該算法引入到神經(jīng)網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)的分析中，使得

9、網(wǎng)絡(luò)模型具有多種可視化效果，有助于更好地理解模型和數(shù)據(jù)。同時在已有工作的基礎(chǔ)上本文拓展了一種新型時空數(shù)據(jù)（Spatio-temporal data）學(xué)習(xí)架構(gòu)，NeuCube架構(gòu)，使原有架構(gòu)能更好地對任何時空數(shù)據(jù)進(jìn)行處理，使早期事件預(yù)警以及時空模式識別性能具有較大改善。
　　四、除此之外，本文還對圖論機(jī)器學(xué)習(xí)算法中的一些其他問題進(jìn)行了研究。例如，不同類間往往存在歧義點（也稱“橋接點”），這會對很多流形聚類算法的性能造成嚴(yán)重影響。針對

10、這種情況，本文給出了一種有效去除類間歧義點的算法。還有，非線性多變量向量值函數(shù)的擬合，常用的方法是多層神經(jīng)網(wǎng)絡(luò)或者單個分量函數(shù)逐個擬合，但前者網(wǎng)絡(luò)類型和大小的選擇缺乏統(tǒng)一的指導(dǎo)原則且一般訓(xùn)練收斂速度較慢，使得普通用戶較難使用；后者則需要多次擬合，且會丟棄不同分量函數(shù)間存在的潛在關(guān)聯(lián)信息。對此，本文對加權(quán)LS-SVM進(jìn)行了拓展，使之可以對任意非線性多變量向量值函數(shù)進(jìn)行一次擬合，高效易用，擬合精度也更佳。
　　同時，為了驗證所提算法的