基于圖論的機器學習算法設計及在神經(jīng)網(wǎng)絡中的應用研究.pdf

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

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

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

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

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

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

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

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

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

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