增量與演化流形學習綜述

談超，關佶紅，周水庚

(1.同濟大學 計算機科學與技術系，上海201804;2.復旦大學計算機學院，上海200433;3.復旦大學上海市智能信息處理重點實驗室，上海200433)

流形學習是近10余年來發展起來的一種非線性維數約簡方法，旨在發現嵌入在高維非線性數據空間的低維光滑流形的內在幾何結構或內在維數，便于對數據的深層理解和進一步處理.近年來，流形學習在許多研究領域，包括數據挖掘、機器學習、圖像處理和計算機視覺等都引起了廣泛的關注.基于流形學習的非線性維數約減方法成為了機器學習中的研究熱點[1].流形學習的基本前提是:觀測空間中的點在高維觀測空間張成一個流形，通過有效地展開觀測空間中卷曲的流形或發現內在的主要變量，可以對數據集進行降維[2].流形學習的意義在于把人的認知流形規律引入到機器學習研究之中[3].當采樣數據處于高維流形空間時，要從采樣數據中學習并發現低維流形的內在幾何結構，這意味著流形學習比傳統的維數約減方法更能體現出事物的本質規律.

近10余年來出現了一些知名的線性與非線性的數據降維算法，如主成分分析(principle component analysis，PCA)[4]、等距映射(isometric mapping，Isomap)[5]、拉普拉斯特征映射 (Laplacian eigenmap，LE)[6]、局部線性嵌入(local linear em-bedding，LLE)[7]等.盡管這些算法的提出大大推動了流形學習的發展，但它們都不具有動態增量處理數據的能力，難以滿足計算效率的實際需求.

為了從高維數據流和大規模海量數據集中探索有價值的信息，人們迫切需要增量地發現內在低維流形結構.許多實際應用如數據流挖掘、視頻監控和語音識別都要求高維數據的實時嵌入.一個簡單的做法是:每當一個新數據點進來時，在所有已存在數據點上運行數據嵌入算法.考慮到大多數數據嵌入算法具有至少需要O(n2)的時間復雜度(n是數據點的數量)，因此其時間復雜度過高，運算量過大.增量學習方法就是為了解決上述問題而提出的.實施增量流形學習主要考慮以下2個方面的問題:1)如何保證在線狀態下實時動態地處理增量數據;2)如何有效地處理大規模海量數據的嵌入[8].當前，增量地處理新加入樣本是流形學習和動態數據流分析的研究熱點.

流形學習的主要目的是對高維數據集的觀察或測量值建立預測模型，當有新的輸入值時，這些預測模型就可以預測出相對的輸出值.多數流形學習算法都是通過優化某個代價函數來求得輸出坐標，而演化學習是基于模仿生物演化行為而發展的最優化方法，可以適用于許多最優化問題;因此可以用于解決許多困難的機器學習問題，比如用在流形學習中的演化流形學習，為發現高維觀察值的低維流形提供了新的途徑.

本文立足于流形學習，對增量流形學習和演化流形學習的最新進展進行綜述.首先，對流形學習的研究背景和現狀進行簡要介紹，在此基礎上，對增量流形學習算法進行分類，并對增量流形學習的主要算法進行綜合對比與分析.然后介紹了流形學習的另外一個方向:演化流形學習，概括了該領域的主要算法，包括非監督演化學習及監督演化學習.最后討論了增量流形學習及演化流形學習可擴展和待解決的問題，以及進一步的研究方向.

1 流形學習:概念與方法

1.1 流形學習的基本概念

流形學習的主要目標是發現嵌入在高維數據空間中觀測數據的低維光滑流形.流形學習對維數約減的過程可概括為:設數據是均勻采樣于一個高維歐氏空間中，流形學習就是找到高維空間中的低維流形，并求出相應的嵌入映射，以實現維數約減[9].

流形學習的數學定義:設Y?Rd，f∶Y→RM是一個光滑嵌套，M＞d，流形學習的目標是基于RM上的一個給定被觀測數據集合{xi}恢復Y與f，在Y中隱藏的數據{yi}被映射到觀測空間RM，使得xi=f(yi)[10].

1.2 傳統流形學習算法

近年來，流形學習領域出現了很多研究成果，在包括數據挖掘、機器學習、圖像處理[11]和計算機視覺等領域得到了廣泛應用[12-15].流形學習中的很多典型算法都是針對線性和非線性降維來進行的.主成分分析算法(PCA)是線性降維方法中的代表;非線性方法中，發表在2000年《Science》上的等距映射算法(Isomap)[5]和局部線性嵌入算法(LLE)[7]是2個著名的流形學習降維算法.Isomap算法使用最近鄰圖中的最短路徑得到近似的測地線距離，代替不能表示內在流形結構的歐氏距離，然后用多尺度分析[16](multidimensional scaling analysis，MDS)進行處理，得到嵌入在高維空間中的低維坐標.LLE能實現高維輸入數據映射到一個全局低維坐標系中，同時保留了鄰接點之間的關系和固有的非線性結構.另外還有拉普拉斯特征映射算法(LE)、局部切空間排列算法(local tangent space alignment，LTSA)[17]等一系列著名的流形學習算法，在非線性降維方面均取得了顯著的效果.

目前，流形學習中的非線性維數約減算法大部分都是應用于數據可視化，并已在人臉圖像處理、手寫數字圖像及語言處理等方面取得了良好的效果.

1.3 傳統流形學習算法分類

按原始觀察空間與經過仿射變換后的嵌入空間保持鄰域結構的不同方式，傳統流形學習算法可劃分為全局嵌入法和局部嵌入法.

1)全局嵌入法.如等距離映射算法(Isomap)，將流形上鄰近的點映射到低維空間中的鄰近點，同時將流形上距離遠的點映射到低維空間中距離遠的點，從而保持低維空間中點之間的距離關系及流形的結構.

2)局部嵌入法.如局部線性嵌入算法(LLE)、拉普拉斯特征映射算法(LE)、局部切空間排列算法(LTSA)等，這些方法將流形上距離近的點映射到低維空間中的鄰近點，得到局部空間的低維坐標，再通過線性嵌入、拉普拉斯映射及切空間排列調準等方法得到全局的低維坐標，從而實現流形學習降維.

1.4 傳統流形學習算法的不足

傳統流形學習方法在尋找規模不斷增加的數據集的內在規律時，新數據集到來后不是利用已經獲得的低維流形結構，而是把新數據集和已有數據集合并成更大規模的數據集，通過重新學習來發現整個數據集的低維流形[8].這些方法的共同特點是以批量或者離線的方式處理數據，不具有增量學習的能力.因此，傳統流形學習算法不適用于增量學習.

2 增量流形學習

增量流形學習是針對傳統批量流形學習算法的不足而發展起來的一種新興流形學習算法，它在動態數據處理過程中新數據加入后，構建與原來數據集之間的鄰域關系，重新表達加入新數據點后的高維數據集的嵌入空間，從而揭示高維空間中數據點之間的本質關系.

增量流形算法的一個優點是可以將數據流形的演化進行可視化.當獲得越來越多數據點時，流形變化的可視化能顯示出數據流的一些性質.適應性也是增量流形學習的一個優點——算法可以在數據逐漸變化中調整流形.例如，假設學習N個個體的面部圖像的流形.經過一段時間后，不同人的臉部逐漸改變，這稱為時間效應，是人臉識別中一個最具挑戰性的研究工作.如果面部圖像的流形可以根據這些面部變化調整，系統的性能就能提高[17].實際應用中大量流數據的產生為增量流形學習提供了廣闊的發展前景.在數據挖掘中，數據通常是從一個數據流中有序地收集.在這種情況下，如果能用新增數據點對已有學習結果進行有效的更新，那將會非常有用.例如在圖像檢索[18]、人臉識別、數據可視化等應用領域，該技術能更好地描述圖像的內蘊結構和語義關系.

2.1 增量流形學習的分類

目前增量流形學習方法主要可以分為2種:樣本獨立訓練和樣本依賴訓練.前者將新樣本嵌入到新構建的子空間中，是全局嵌入法的增量形式;而后者則側重保持局部的鄰域結構，求解在局部鄰接信息約束下的優化問題.前者的優勢是易于從理論角度進行理解，在表達數據全局結構的基礎上進行新樣本點的增量嵌入;后者一般只需要進行增量譜方法的計算，計算量上具有一定的優勢.表1所列為現有主要的增量流形學習方法，如IDR(incremental dimension reduction algorithm)[19]、增量 IAM(incremental alignment method)[20]、譜嵌入增量流形學習算法[21]及增量 LLE 算法[22]等.本文分別對其中主要的方法進行詳細介紹.

表1 主要的增量流形學習算法Table 1 Major incremental manifold learning algorithms

2.2 針對數據流的增量Isomap算法

考慮數據流的特點，Law等提出了增量式的Isomap 算法[1，23]，增量式學習不僅能夠更有效地計算，同時能夠發現流形結構演化的過程.

2.2.1 增量 Isomap算法

增量Isomap的思想是通過更新坐標來保持最佳的測地距，其算法主要過程分為以下幾步[1].

1)更新測地距.就Isomap算法而言，對每個新增的數據點yn+1都將引入一個新的頂點vn+1到圖G中.然而，新增的頂點不僅會改變原有的鄰域結構和一些已知的最短路徑，也增加了新的路徑.在算法中，首先增加或移去某條與vn+1相關的邊.點對之間的測地距離需要重新計算，這里使用一種改進的Dijkstra算法.對于增加的邊，需要檢查是否存在新的最短路徑;對于移去的邊，需要重新計算所有曾經基于該邊來計算的點對.

2)尋找新樣本xn+1的坐標.匹配其與最接近目標值的樣本xi的內積形式，盡可能與目標值接近來確定其相應的位置.

3)全局坐標校準.根據調整后的測地距離矩陣Gnew，更新內在低維空間的數據點坐標.這里存在2種更新方法，一種是對損失函數構造梯度下降算法來更新;另一種是子空間迭代，直接對調整后的矩陣作相應的特征分解，可視為求解增量的特征值問題，通過特征分解得到坐標.

2.2.2 增量Isomap算法的不足、擴展與改進

當加入一個樣本點，可能會引起“短路邊”出現，樣本點對之間的測地距發生很大的變化，導致點的坐標產生很大的偏差.一些擴展和改進增量Isomap算法的研究包括如下[23].

1)一個增量的測地距更新規則.該測地距被用在增量Isomap中，通過改變測地距的稀疏性來提高坐標更新的效率.

2)增量地更新拓撲空間坐標的方法.使用子空間迭代方法來增量地更新插入新點以后的全局坐標，并使用 Rayleigh-Ritz加速[24].該方法獨立于測地結構的定義，故也可以被用在其他增量非線性維數約減方法中.

3)對已有的增量式方法的改進[23].由于Isomap的測地線計算是全局算法，因此，改進的算法并非是完全在線的.Isomap是一個全局的算法，對任何新樣本，需要考慮它是如何與其他樣本相互影響的，為了找到其坐標，需要將所有數據點的幾何信息都保存起來，不適宜在大數據集上使用.解決該問題有2種方法:一種辦法是當累積了足夠數量的樣本時忽略最舊的樣本點，這給算法帶來了適應性的優勢;另一種是維持一組固定大小的“標記點”(landmark points)，并只考慮新樣本點與標記點之間的關系，最后，可以通過沿著流形的高斯分布來壓縮數據點集，無需存儲額外的信息.

在文獻[25]中，作者提出了一種基于小世界模型的增量流形學習算法，將Isomap算法應用于增量處理新樣本中.首先，對于新樣本點，在訓練集中找出它的k近鄰點及一些距離較遠的點，接下來通過保持新樣本和周圍這些點的測地距離來獲得新樣本點的低維嵌入.從而新樣本可以有效地映射到低維空間中，該算法具有較低的復雜度.

2.3 針對LLE的2種增量算法

L.K.Saul等提出的線性化的LLE算法假設流形是局部線性的，訓練樣本的投影值不會因新樣本的加入而發生改變[26].這是一種線性近似的方法，實際上，當新樣本點加入時，由于原始數據集中一些樣本的k近鄰點會發生改變，它們投影以后的值也會隨之改變.故LLE不適用于順序到來的實時數據.另外LLE進行降維的原始數據集必須是數量固定的，當新點加入時，LLE必須在擴展后的數據集上重新運行，對新點不具有一般性，這使得LLE不能用于動態系統的高維數據集，時間復雜度過高.針對LLE的這些不足，近年來出現了2種方法來實現增量計算.

1)O.Kouropteva等提出的一種增量 LLE算法[27].

當加入新樣本點后，假設新代價矩陣Mnew與原代價矩陣M的前d個最小特征值近似相等，通過最小化(YnewMnewTTnew－diag(λ1，λ2，…，λd))求出所有樣本的低維映射.該算法成功地求解了增量特征問題，但是存在2個缺點:①最優化問題.LLE已將最優化問題轉化為求解矩陣特征向量的問題，而這種增量LLE方法又重新回到了求解最優化問題，處理不便;②病態條件下的特征問題.由于假設Mnew的特征值與原代價矩陣M的前d個最小的特征值近似相等，隨著新增樣本數目的增加，它們之間的差值將越來越大，從而導致特征值和特征向量解的誤差對微小的擾動非常敏感.

2)朱明旱等提出的一種基于正交迭代的增量LLE 算法[28].

該算法分為2步:首先更新代價矩陣，在這個步驟中避免了一些重復的權值計算;然后不斷地利用前一次的處理結果來計算各樣本的投影值，避免了新樣本加入時的重復計算，并將求投影坐標時所需的對高階矩陣的分解轉化為對低階矩陣的分解.此方法降低了分解矩陣的階數和數據的運算量，從而提高了計算效率，較好地解決了在新樣本不斷加入的情況下總體流形不斷更新的問題.

2.4 動態增殖流形學習算法

對于不斷增加的海量觀測數據集序列，不可能一次獲得嵌入到高維數據空間上的所有數據點集，對于新來的觀測數據子集，如何把其包含的幾何信息融合到以前所獲信息中去是一個要解決的問題.對于已獲得的觀測數據集，要對整個數據集進行流形學習以發現其內在規律.目前的流形學習算法對于海量觀測數據往往計算復雜度過高.流形學習的增量非線性維數約減和增量LLE是對新增單個數據點進行逐個更新，但逐點更新計算代價較高，并且新的觀測區域數據的出現會破壞原有的幾何結構.

為了解決以上問題，曾憲華等提出了一種動態增殖流形學習算法[8].這是通過整合重疊鄰域中的信息來發現全局幾何結構的一種方法，保證嵌入空間和內在低維空間對應數據點與局部鄰域內的點保持相同的序關系，任何數據點和它的近鄰點具有旋轉、平移與伸縮不變性.先用LLE計算各子集的流形，再將各子集的流形整合，得到整體流形結構，這是一種分批處理的思想.利用這一思想，增殖流形學習算法處理不斷增加的數據集時，對稠密的近鄰或重疊數據子集(稠密是指該子集中的點能夠反映嵌入流形上某一部分的內在幾何結構)分塊，發現其低維流形結構.然后固定一塊，對另一塊施加平移、旋轉和伸縮變換，使得兩者的低維流形具有觀察數據子集間相同的近鄰關系，這樣隨著觀測數據集的增多，通過平移、旋轉及伸縮變換整合得到的流形更加逼近高維數據空間的內在低維全局結構.這是一個增殖并保持原有信息的過程，因此稱之為動態增殖流形學習.

增殖流形學習利用分治的方法和嵌入機理，把大任務分成多個不同的小任務，利用一種或多種流形學習算法實現，用于實際應用中大數據集或超大數據集的內在幾何結構及其內在規律的動態發現和整合，通過不斷動態發現局部數據集的內在幾何結構，拓撲成幾何結構更加完善的低維流形.這種動態拓撲低維流形的方法是在線或者增量的方法，可以克服現有流形學習算法存在的缺陷[8].

該算法學習所需的數據子集必須是相鄰或重疊的，否則發現的低維流形將有較大的扭曲，即整個數據集是非稠密的.非稠密的數據集上的增殖流形學習是該算法進一步的研究方向.

2.5 增量LTSA算法

如前所述，等距映射(Isomap)[5]、局部線性嵌入(LLE)[7]和局部切空間調準(LTSA)[17]等算法在一些人工合成的數據集上取得了滿意的可視化效果，并在一些分類問題中得到了應用.但上述方法都是批處理模式，即在降維時所有數據都要準備好.而在監控等應用中，圖像數據是逐步得到的，批處理模式需要大量的計算量，重復地進行批處理降維極其耗時[29].

針對批處理模式算法的不足，國內外學者開始考慮增量式的流形學習算法，這里討論的是非監督式的非線性流形降維問題，對于屬于非參數化的增量流形學習算法來說，很適合數據的逐步獲取.增量式算法的另一個好處是能檢測數據流中的漸進變化，可以很容易地修改以達到“遺忘”的效果[29].增量Isomap及標志點的增量式Isomap方法[23]可以降低在處理新數據點時的時間復雜度.通過使用標志點，可以降低Isomap算法的空間要求，能較好地支持大數據量的應用.但由于Isomap算法基于最短測地距，在處理新數據時，需要進行耗時的圖重構，時間復雜度依然比較高[29].Liu等提出的增量 LTSA算法能快速處理新數據點，通過最小化新數據點與已有數據點的低維坐標的最小重構誤差，得到新數據點的低維嵌入坐標[30].受標志點 Isomap算法的啟發，Yin等的標志點LTSA算法能降低對內存的要求[31].下面介紹幾種對應的增量式算法.

1)增量 LTSA 算法[30].

假設給定n個數據點xi的全局低維坐標ti，對于新觀測到的樣本點xn+1，更新現有的坐標ti并給出xn+1的映射ti+1.算法由3步組成:首先，對于新數據點xn+1，更新已有數據點的局部幾何信息;接著使用xn+1相對于已有數據點的局部幾何信息估計tn+1;最后更新所有數據點的全局低維坐標ti.算法具體步驟見文獻[30].根據文獻[30]，增量 LTSA算法最大的運算量是計算實對稱半正定的排列矩陣B的最小特征向量集.當新數據點到達時，只改變部分數據點的近鄰結構，而受輕度擾動的實對稱矩陣的特征值與特征向量不會產生大的變化.這使得重用當前的變換矩陣和坐標來更新更加有效.更確切地說，因為LTSA算法中的排列矩陣B更具有局部性，新數據點的影響也更局部化，使得矩陣的更新更簡單[29].相對于文獻[23]中增量式的 Isomap算法，LTSA的增量式算法不需要費時的圖重構過程而顯得更有效.不過，相對于原始LTSA算法時間復雜度較高，增量LTSA算法使用了Rayleigh-Ritz加速方法來提高算法效率.

2)帶標記點的增量LTSA算法.

在標記點Isomap算法[23]中，尋找保持一組標記點的測地距的映射，代替所有成對點的測地距，減少計算復雜度.標記點增量LTSA算法與之類似，令最先的u個點為標志點，在其中找k個最小距離的近鄰點，構建局部切空間.新數據點的局部切空間使用標記點的局部幾何信息構建，新點的低維全局坐標通過最小二乘問題求解.此方法解決了測地距離矩陣存儲空間大及計算復雜度高的問題，為在大數據集上的使用提供了便利.

2.6 增量拉普拉斯特征映射算法

Jia等提出的增量拉普拉斯特征映射算法[32]，通過一定意義上局部鄰域信息的理想化保持計算數據集的低維表示，提出子流形分析算法及線性增量的模式來增量地學習新樣本點并將其映射到低維空間.該算法將局部線性重構機制用于更新已存在樣本的低維嵌入結果，并加入新的鄰接信息.更新機制類似于迭代算法，每當觀測到一個新樣本，只更新鄰域發生變化的樣本點，局部地改進現有樣本的嵌入結果.算法的主要步驟如下.

1)更新鄰接矩陣w.構造新樣本點xn+1與已知樣本點之間的權重，重構樣本點之間因新點插入而改變的權重.

2)在低維空間映射新點.這里作者給出了2種方法，第1種是線性增量法，最小化加權距離目標函數從而得到新點的低維映射yn+1.第2種是在新點的k個最近鄰域即子流形上應用拉普拉斯映射，通過構建子鄰接矩陣并計算特征值和特征向量來得到新點在子流形中的低維坐標.接著計算新點的全局坐標yn+1，計算過程可看作是坐標變換問題，通過變換保持新點與其k個最近鄰點之間的關系.通過在子流形上使用拉普拉斯映射，算法檢測到新點xn+1與已知點之間的內在結構信息，再計算它們之間的約束權重矩陣來最小化重構誤差.服從該約束的最佳權重可通過解最小二乘問題得到，再由權向量得出xn+1的全局坐標yn+1.

3)更新已存在樣本點的低維嵌入坐標.若已存在樣本點的鄰域由于xn+1的插入而改變，除了計算yn+1，它們的嵌入坐標也需要被更新.這里使用局部線性重構機制來加入新的鄰接信息，并修改已存在樣本的低維嵌入結果.更新分為2步:首先找到每個已有點xi周圍的k個最近鄰點并計算重構權重來最小化耗費函數ε;然后基于這些權重來找每個點的低維坐標yi.這里，某個點有可能不能立即得到精確的低維嵌入坐標，但隨著增量學習的更新步驟，低維坐標可不斷被調整，直到近似最優化.

該算法的增量模式可以被一般化到其他非線性流形學習算法中去，例如LLE和Isomap.與一般迭代算法不同的是，增量拉普拉斯特征映射算法很簡單，當依次觀測樣本時可以實現在線學習.

2.7 增量等距嵌入算法

Zhao等提出了增量等距嵌入的方法[33-34]，通過只映射新的數據點，并調整存在的嵌入結果，用增量的方法來產生新的嵌入結果.此外，這些方法也可以刪除已存在的數據點并相應地調整嵌入的結果，通過在數據流上建立“滑動窗口”并嵌入增量數據，來約減一個無界數據流的維數.

2.8 增量校準算法

與已有流形學習算法相比，為保持度量，避免陷入局部最小的問題，Han等提出了增量校準算法[20].該算法屬于局部保持映射，其主要思想是增量地校準輸入數據的局部坐標，通過成塊地對齊鄰域信息，迭代產生整個高維數據集的低維映射.該方法包括2個步驟:增量和校準.第1個步驟增量地尋找鄰域塊用于接下來的校準;第2個步驟迭代地對齊鄰域塊的低維坐標，產生整個數據集的低維嵌入.該算法與增量LTSA算法和增量等距嵌入算法都具有一定的相似性，都是通過局部校準鄰域信息來增量學習高維數據，從而得到其低維的嵌入坐標.這種增量校準算法能適應不斷增加的觀測數據集的處理需求，對在線數據流處理、圖像檢索等方面具有良好的應用價值.

2.9 高維增量在線學習

在最近的統計學習中，高維輸入數據的非線性近似函數是一個重要的問題，特別是在增量和實時的情況中.越來越多的問題領域中，增量和實時這2個特性都很重要.例如動態進程的在線模型，由可視化監督所觀測，高級計算機接口的用戶模型和數值函數學習，控制模型特別是在高維移動系統如人類或仿真機器人的背景中.針對這些任務的理想算法需要避免潛在數量上的問題，如輸入數據的冗余，消除不恰當的輸入維數，在數據保持有效的情況下學習更新的計算復雜度較低，允許在線增量學習，并獲得準確的函數近似及足夠的一般性.

局部加權回歸映射(locally weighted projection regression，LWPR)[35]是高維空間中具有冗余輸入維度的增量非線性近似函數的新算法，其核心是應用局部線性模型的非參數化回歸.為了保持計算效率和數量的魯棒性，每個局部模型以部分最小二乘回歸意義，在輸入空間里用所選方向的一個單邊變化回歸的較小數，預先形成了回歸分析.Sethu等討論了局部學習技術是如何成功地用在高維空間中，并回顧了各種局部維數約減技術，提出了LWPR算法.LWPR的特點是:1)應用基于增量訓練的第二順序學習法快速學習;2)使用統計上有效的隨機leave-one-out交叉確認來學習，無需存儲訓練數據;3)僅依賴于局部信息來調整其加權核，最小化增量學習負面干擾的危險;4)具有與輸入數量呈線性的計算復雜度;5)可以處理大量的(可能是冗余的)輸入，例如上升到90維的數據集中的各種經驗估計，一般解釋為產生了預變異和信任距離.

文獻[35]提出，LWPR是第一個真正的增量空間局部學習方法，可以成功并有效地用于非常高維的空間中.

2.10 增量流形學習算法小結

1)技術分類.

①鄰接矩陣的更新.更新鄰接信息矩陣對于增量學習來說是必不可少的步驟.一些增量算法如增量LLE、增量拉普拉斯特征映射和增量LTSA等，保持數據集內部的局部鄰接信息并通過已存在樣本的鄰接信息取得低維的嵌入.

②迭代的使用.增量校準算法是一種典型的代表，它在找到鄰域塊之后，對齊它們的低維坐標，多次使用迭代的方法來達到增量學習的目的.

2)算法的區別和相似性.

①全局和局部的區別.增量Isomap保持了原Isomap算法的全局性質，而增量LLE仍然是研究新樣本點與鄰域之間的局部關系，這一點在增量拉普拉斯特征映射和增量LTSA中的第2、第3步也有體現，基于局部線性映射的增量學習算法[36]也屬于這種類型.

②步驟的相似性.通過上面幾種主要增量流形學習降維算法的闡述，可以看出，增量Isomap算法、增量LTSA和增量拉普拉斯特征映射都包括3個步驟.其中增量Isomap包括:首先更新測地線距離;接著更新坐標;最后尋找新樣本xn+1的坐標.增量拉普拉斯特征映射為:第1步，更新鄰接矩陣w;第2步，在低維空間映射新點;第3步，更新已存在樣本點的嵌入結果.增量LTSA首先根據新數據點xn+1更新已有數據點的局部幾何信息;接著使用xn+1相對于已有數據點的局部幾何信息估計全局低維坐標;最后更新所有數據點的全局低維坐標.可以看出，增量拉普拉斯特征映射和增量LTSA的步驟非常類似.

③處理數據的類型以及數學表達的方式.增量Isomap是等距嵌入的算法，它主要是從保持測地線的角度來處理新加入的樣本.增量LLE是通過解協方差矩陣的特征值和特征向量來求新點在低維坐標下的映射.增量拉普拉斯特征映射和增量LTSA都是從數據點的局部幾何信息出發，根據新點與其相鄰的已有點之間的鄰接關系來估計其全局坐標，是通過研究鄰域關系進行的嵌入算法.表2對上文提到的增量流形學習算法進行了對比分析.

3)主要存在的問題.

Isomap的測地線計算是一個全局的算法，因此，增量Isomap算法并非是完全在線的，對任何樣本，在找到其坐標之前需要考慮它是如何與其他樣本相互影響的;增量LLE牽涉到最優化問題，LLE本身是將最優化問題轉化為求解矩陣特征向量的問題，而增量LLE實際上又重新回到了最優化問題，并且由于新點的特征值沒有更新，隨著新增樣本數目的增加，新點與已知點的前d個最小的特征值間的差值會越來越大，從而導致誤差會越來越大.表3對部分增量流形學習算法的優缺點及適用范圍進行了整體的概括和評價.

表2 增量流形學習算法的對比分析Table 2 Comparative analysis of incremental manifold learning algorithms

表3 部分增量流形學習算法的評價及適用范圍Table 3 Evaluation and applicable field of incremental learning methods

3 演化流形學習

3.1 演化學習的概念

實際系統往往是動態的，數據沿著時間不斷變化，靜態數據上的常規學習并不適合.針對動態問題的解法包括:1)在數據集上應用靜態算法;2)在每個時間點上對數據應用靜態算法，包括時間進化機制和動態預測.

演化學習是在時間進化數據上的學習問題，學習任務包括靜態狀態和時間進化機制的學習，可分為半監督學習(分類/回歸)和非監督學習(聚類/密度估計)等.

1)增量學習:根據有限內存或在線設備，數據組織成批量或流狀模型.與演化學習的不同在于:增量學習假設所有數據來自同一分布，對整個數據集的輸出單一，如分類、回歸、數據分類或密度模型.增量算法的期望對數據順序敏感，因此不對臨時數據進行推進.

2)在線學習:實際學習環境中的一種特殊類型，即連續循環的一組序列.當在時間t預測時，學習者只能觀察到t為止的樣本，故動態地更新以尋求較低的遺憾值(regret).與演化學習不同，在每個時間點t，在線學習觀察單個樣本，而演化學習觀察一組樣本，故演化學習可以在線或離線地處理數據[37-38].在線學習要求每個樣本點的回饋，而演化學習中，一組樣本可能是標記的、未標記的、或部分標記的.最小化在線學習與離線學習相應的遺憾值在每個時間點不存在一般化問題.而演化學習旨在達到2個目標:在每個時間點的損失一般化及時間進化機制的學習.

演化學習與增量學習、在線學習[35]的比較如表4所示.

表4 演化學習算法與其他學習算法的比較Table 4 Comparison of evolution learning algorithms with other learning methods

前面提到，演化學習是一種基于演化發展的最優化方法，可以用于解決機器學習中的最優化問題，用在流形學習中，為發現高維數據集的低維流形提供了新的途徑.首先，當數據分布移動時，可能不適合采用傳統的聚類算法來處理整體數據;其次，如果對每個新樣本點獨立使用傳統的聚類算法，不能保留聚類結果沿著時間的連貫性.這里就體現出演化流形學習的必要性，下面將從非監督和半監督2個方面來對演化流形學習算法進行討論.

3.2 非監督演化學習

近年來演化聚類成為數據挖掘中提取信息的一項新的研究熱點.在流形學習領域，聚類是一個基本的問題[39-41].傳統的聚類算法，如 K-means[42]和譜聚類[43]都是基于靜態數據，并假設所有數據是獨立同分布(independent and identically-distributed，I.I.D)的，即樣本來自同一個潛在的分布.在這種數據上的聚類任務產生出了演化聚類問題[44].此外，與增量演化聚類[45]不同的是，由于數據的分布時刻彼此相鄰，沿著時間順序的聚類結果應該是連續的.演化聚類的目標包括:對每個時間點t，輸出xt上的一個分布πt;保持分類的質量和沿t分布{πt}Tt=1的光滑性;聚類追蹤等.演化聚類的意義在于:可解釋機器學習及數據挖掘算法;保持沿著時間的聚類結果的連貫性，特別是在可視化方面[44];聚類追蹤為動態網絡行為的分析提供有力對策.由于種種原因，例如數據大小的變化、聚類數目的變化、聚類沿著時間的動態行為(出生、交叉和死亡等)，演化聚類具有很大的挑戰性.前面一節提到，當數據分布移動時，采用傳統的聚類算法處理整體數據時，不能保留聚類結果沿著時間的連貫性.故將演化聚類用在流形學習中，對于處理動態高維數據集的低維流形并得出其聚類結果具有積極意義.

演化譜聚類和演化聚類是2種基本的數據組成方式[46-47].目前研究的主要問題包括:1)什么是演化;2)光滑代表什么;3)演化K－均值、演化GMM等方法是否有一般化的方法;4)聚類行為;5)聚類數目和數據大小的變化.

Zhang等提出了在線演化冪簇混合算法(online evolutionary exponential family mixture)[48]，該方法提出了對聚類問題的密度估計的觀點，針對冪簇混合模型(K－均值模型和多項式混合模型)進行密度估計，屬于非監督的算法.它采用了期望－最大化(expectation-maximization，EM)方法進行計算:E步屬于冪簇混合(exponential family mixture，EFM)的聚類問題;M步使用EFM的閉合形式解法.Zhang等還提出了2個框架:第1個框架依賴歷史數據，即當前的模式分布近似于歷史數據的分布;第2個框架依賴于歷史模型，即當前的模型分布近似于歷史模型分布.這2種框架都基于EFM模型[44]，該方法用于流形學習中，對動態高維數據集進行數據降維以后的聚類，屬于演化流形學習的非監督方法，有待解決的是聚類追蹤的問題.

3.3 半監督演化學習

演化分類是指學習一條針對不同時期的演化分類鏈.它的意義在于當使用歷史分類器或所有歷史數據都無用的情況下，歷史分類信息可能有助于分布緩慢進化，可以使用而不是拋棄歷史標記.Jia等提出了半監督演化分類算法(semi-supervised evolutionary classification)[49]，將一般學習問題中的光滑假設擴展到演化數據中.光滑假設是指:若2個數據點靠得很近，容易有近似的標記.而演化光滑假設是指:若時間點t1和t2靠得很近，兩分類函數ft1和ft2容易近似.實現以上假設的直接方法是對時間t積分，當t不連續時，用反向差異來近似以上積分，這是學習算法的一種時間調整.

學習數據的自然演化信息在機器學習研究中是一種新的挑戰.上述算法屬于演化流形學習的半監督方法，應用在真實世界的流形學習中，處理經過降維以后的實時數據，并對數據集學習了一系列演化的分類函數，無論是穩定性還是精確性方面都產生了更好的性能.

3.4 演化流形學習小結

一種超越了獨立同分布假設(I.I.D)[42-43]的學習問題的新類型稱為演化學習.最近又提出了一些非監督算法[50-53]、半監督算法[54-55]和有監督的流形學習算法[56-57]，在線增量學習的向量量化策略[58]，以及增量譜聚類[59]等演化流形學習算法，取得了令人滿意的結果.但這些僅僅是探索工作，未提供理論分析.演化學習主要是基于模仿生物演化行為而發展的最優化算法，用于學習高維流形時，可以幫助人們解決許多困難的流形學習問題.無論是非監督演化聚類還是半監督演化分類，都是建立在已有監督或非監督學習算法之上，引進了時間進化的條件.相信通過進一步的理論探索，無論是增量學習、在線學習還是演化學習都將在流形學習領域產生新的研究點和研究價值.

4 總結與展望

目前，流形學習在許多領域都有廣泛的應用，例如模式識別、統計回歸、智能控制、生物信息、數據挖掘、數據壓縮、時間序列分析等，是近年來機器學習領域的研究熱點.而增量流形學習能發現大規模海量數據集的內在低維信息，更好地解決在線和增量的問題;演化學習在流形學習中的應用，解決了傳統流形學習存在的不足，比如觀察數據集的移動分布，及時間連貫性等問題，學習數據的自然演化信息，建立更接近真實世界的優化模型.

現有流形學習算法主要面臨的問題是在線環境下的誤差、優化及收斂性等問題.這與鄰域圖上各點鄰域點的選取、坐標映射過程中方程的求解以及算法收斂性等方面都有一定關系.未來工作可以從這幾個方面展開，以解決存在的這些問題.另外還有以下幾個方面值得進一步地研究.

1)減少算法中參數的依賴性.目前的增量流形學習算法中近鄰數是變量，如何依據要處理的問題和數據的分布自適應地選擇適當的局部近鄰數值得進一步研究.

2)目前的增量流形學習算法大多屬于非監督學習，如何提高新增樣本點的學習能力是一個重要的問題.雖然標記點技術已用于增量Isomap和增量LTSA等算法中，但它們還不具有監督意義.可以考慮將監督算法與增量流形學習領域的算法相結合，提高在線學習的能力.

3)提高算法的效率.增量流形學習一般比批量算法的時間復雜度更高，如何對已有算法進行加速，使之應用到對計算時間要求較高的新領域，也是值得深入研究的問題.

4)當樣本點包含噪聲點時，原始的流形學習算法(如ISOMAP和LLE)受到了很大的影響，增量Isomap算法也存在類似的問題.如何減少噪聲干擾在增量流形學習中也是一個重要的問題.

5)就目前來看，許多實際應用中的數據集都存在規律性，因此研究流形與數據集的關系成為了一個重要領域.在將來的工作中，必須找到一個行之有效的方法來分析高度相關、復雜分布的數據集的內在結構.最近Zhang等提出的自適應流形學習算法通過自適應地選擇局部鄰域結構，將局部結構拼接在一起產生全局參數信息，解決了局部依賴問題[60].怎樣使用增量流形的性質來模擬未知的概念和設計新的算法是今后研究的另一個方向.

6)演化學習的產生是為了解決現有學習算法與實際系統中的困境，目前出現的成果還僅是一些探索工作，包括非監督演化學習及半監督演化學習.對這些算法進行更深入的理論分析，并在更多的數據集上進行實驗來評價算法的性能和價值，是值得進一步探討的問題.

[1]LAW M，ZHANG Nan，JAIN A K.Nonlinear manifold learning for data stream[C]//Proceedings of the Fourth SIAM International Conference on Data Mining.Lake Buena Vista，USA，2004:33-44.

[2]徐蓉，姜峰，姚鴻勛，等.流形學習概述[J].智能系統學報，2006，1(1):44-51.XU Rong，JIANG Feng，YAO Hongxun，et al.Overview of manifold learning[J].CAAI Transactions on Intelligent Systems，2006，1(1):44-51.

[3]SEUNG H，LEE D.The manifold ways of perception[J].Science，2000，290(5500):2268-2269.

[4]PEARSON K.On lines and planes of closest fit to systems of points in space[J].Philosophical Magazine，1901，2(6):559-572.

[5]TENENBAUM J，DE SILVA V，LANGFORD J.A global geometric framework for nonlinear dimensionality reduction[J].Science，2000，290(5500):2319-2323.

[6]BELKIN M，NIYOGI P.Laplacian eigenmaps for dimensionality reduction and data representation[J].Neural Computation，2003，15(6):1373-1396.

[7]ROWEI S，SAUL L.Nonlinear dimensionality reduction by locally linear embedding[J].Science，2000，290(5500):2323-2326.

[8]曾憲華，羅四維.動態增殖流形學習算法[J].計算機研究與發展，2007，44(9):1462-1468.ZENG Xianhua，LUO Siwei.A dynamically incremental manifold learning algorithm[J].Journal of Computer Research and Development，2007，44(9):1462-1468.

[9]DE SILVA V，TENENBAUM J B.Global versus local methods in nonlinear dimensionality reduction[M]//BECKER S，THRUN S，OBERMAYER K.Advances in Neural Information Processing Systems.Cambridge，USA:The MIT Press，2003:721-728.

[10]BERGER M，GOSTIAUX B.Differential geometry:manifolds，curves and surfaces[M].[S.l.]:Springer-Verlag，1988:474.

[11]PLESS R，SOUVENIR R.A survey of manifold learning for images[J].IPSJ Transactions on Computer Vision and Applications，2009，1:83-94.

[12]BREGLER C，OMPHUNDRO S M.Nonlinear manifold learning for visual speech recognition[C]//Proceedings of the 5th International Conference on Computer Vision.Washington，DC，USA:IEEE Computer Society，1995:494-499.

[13]HADID A，KOUROPTEVA O，PIETIKANINEN M.Unsupervised learning using locally linear embedding:experiments in face pose analysis[C]//Proceedings of the 16th International Conference on Pattern Recognition.Quebec City，Canada，2002:111-114.

[14]JENKINS O C，MATARIC M J.A spatiotemporal extension to Isomap nonlinear dimension reduction[C]//Proceedings of the 21th International Conference on Machine Learning.New York，USA，2002:2551-2556.

[15]NISKANEN M，SILVEN O.Comparison of dimensionality reduction methods for wood surface inspection[C]//Proceedings of the 6th International Conference on Quality Control by Artificial Vision.Gatlinburg，USA，2003:178-188.

[16]KRUSKAL J B，WISH M.Multidimensional scaling[M].Beverly Hills，USA:Sage Publications，1977.

[17]ZHANG Zhenyue，ZHA Hongyuan.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J].SIAM Journal of Scientific Computing，2004，26(1):313-338.

[18]LU Ke，HE Xiaofei.Image retrieval based on incremental subspace learning[J].Pattern Recognition，2005，38(11):2047-2054.

[19]YE Jieping，LI Qi，XIONG Hui，et al.IDR/QR:an incremental dimension reduction algorithm via QR decomposition[J].IEEE Transactions on Knowledge and Data Engineering，2005，17(9):1208-1222.

[20]HAN Zhi，MENG Deyu，XU Zongben，et al.Incremental alignment manifold learning[J].Journal of Computer Science and Technology，2011，26(1):153-165.

[21]LI Housen，JIANG Hao，BARRIO R，et al.Incremental manifold learning by spectral embedding methods[J].Pattern Recognition Letters，2011，32(10):1447-1455.

[22]KOUROPTEVA O，OKUN O，PIETIKAINEN M.Incremental locally linear embedding algorithm[C]//Proceedings of the 14th Scandinavian Conference Image Analysis.Joensuu，Finland，2005:521-530.

[23]LAW M H C，JAIN A K.Incremental nonlinear dimensionality reduction by manifold learning[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28(3):337-391.

[24]GOLUB G H，VAN LOAN C F.Matrix computations[M].Baltimore，USA:Johns Hopkins University Press，1996:1-694.

[25]SHI Lukui，YANG Qingxin，LIU Enhai，et al.An incremental manifold learning algorithm based on the small world model[C]//Proceedings of the 2010 International Conference on Life System Modeling and Intelligent Computing，and 2010 International Conference on Intelligent Computing forSustainable Energy and Environment.Wuxi，China，2010:324-332.

[26]SAUL L K，ROWEIS S T.Think globally，fit locally:unsupervised learning of low dimensional manifolds[J].Journal of Machine Learning Research，2003，4:119-155.

[27]KOUROPTEVA O，OKUN O，PIETIKANEN M.Incremental locally linear embedding[J].Pattern Recognition，2005，38(10):1764-1767.

[28]朱明旱，羅大庸，易勵群，等.基于正交迭代的增量LLE算法[J].電子學報，2009，37(1):132-136.ZHU Minghan，LUO Dayong，YI Liqun，et al.Incremental locally linear embedding algorithm based on orthogonal iteration method[J].Acta Electronica Sinica，2009，37(1):132-136.

[29]劉小明.數據降維及分類中的流形學習研究[D].杭州:浙江大學，2007:1-108.LIU Xiaoming.Research on data dimension reduction and manifold learning in classification[D].Hangzhou:Zhejiang University，2007:1-108.

[30]LIU Xiaoming，YIN Jianwei，FENG Zhilin，et al.Incremental manifold learning via tangent space alignment[C]//Proceedings of the Second International Conference on Artificial Neural Networks in Pattern Recognition.Ulm，Germany，2006:107-121.

[31]YIN Jianwei，LIU Xiaoming，FENG Zhilin，et al.A local tangent space alignment based transductive classification algorithm[C]//Proceedings of the Second International Conference on Artificial Neural Networks in Pattern Recognition.Ulm，Germany，2006:93-106.

[32]JIA Peng，YIN Junsong，HUANG Xinsheng，et al.Incremental Laplacian eigenmaps by preserving adjacent information between data points[J].Pattern Recognition Letters，2009，30(16):1457-1463.

[33]ZHAO Dongfang，YANG Li.Incremental isometric embedding of high-dimensional data using connected neighborhood graphs[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31(1):86-98.

[34]ZHAO Dongfang，YANG Li.Incremental construction of neighborhood graphs for nonlinear dimensionality reduction[C]//Proceedings of the 18th International Conference on Pattern Recognition.Hong Kong，China，2006:177-180.

[35]VIJAYAKUMAR S，DSOUZA A，SCHAAL S.Incremental online learning in high dimensions[J].Neural Computation，2005，17(12):2602-2634.

[36]FRITZKE B.Incremental learning of local linear mappings[C]//Proceedings of the International Conference on Artificial Neural Networks.Paris，France，1995:217-222.

[37]WANG Yi，LIU Shixia，FENG Jianhua，et al.Mining naturally smooth evolution of clusters from dynamic data[C]//Proceedings of the SIAM International Conference on Data Mining.Minneapolis，USA，2007:125-134.

[38]AHMED A，XING E.Dynamic non-parametric mixture models and the recurrent Chinese restaurant process:with applications to evolutionary clustering[C]//Proceedings of the SIAM International Conference on Data Mining.Atlanta，USA，2008:219-230.

[39]SOUVENIR R，PLESS R.Manifold clustering[C]//Proceedings of the 10th IEEE International Conference on Computer Vision.Beijing，China，2005:648-653.

[40]CAO Wenbo，HARALICK R.Nonlinear manifold clustering by dimensionality[C]//Proceedings of the 18th International Conference on Pattern Recognition.Hong Kong，China，2006:920-924.

[41]XU Rui，WUNSCHLL D.Survey on clustering algorithms[J].IEEE Transactions on Neural Networks，2003，16(3):645-678.

[42]HARTIGAN J A，WONG M A.A k-means clustering algorithm[J].Applied Statistics，1979，28(1):100-108.

[43]NG A Y，JORDAN M I，WEISS Y.On spectral clustering:analysis and an algorithm[C]//Neural Information Processing Systems:Natural and Synthetic.Vancouver，Canada，2001:849-856.

[44]CHAKRABARTI D，KUMAR R，TOMKINS A.Evolutionary clustering[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Philadelphia，USA，2006:554-560.

[45]CHARIKAR M，CHEKURI C，FEDER T，et al.Incremental clustering and dynamic information retrieval[C]//Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing.El Paso，USA，1997:626-635.

[46]CHI Yun，SONG Xiaodan，ZHOU Dengyong，et al.Evolutionary spectralclusteringbyincorporatingtemporal smoothness[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Jose，USA，2007:153-162.

[47]TANG Lei，LIU Huan，ZHANG Jianping，et al.Community evolution in dynamic multi-mode networks[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Las Vegas，USA，2008:677-685.

[48]ZHANG Jianwen，SONG Yangqiu，CHEN Gang，et al.Online evolutionary exponential family mixture[C]//Proceedings of International Joint Conference on Artificial Intelligence.Pasadena，USA，2009:1610-1615.

[49]JIA Yangqing，YAN Shuicheng，ZHANG Changshui，et al.Semi-supervised classification on evolutionary data[C]//Proceedings of International Joint Conference on Artificial Intelligence.Pasadena，USA，2009:1083-1088.

[50]SANGER T D.Optimal unsupervised learning in a singlelayer linear feed-forward neural network[J].IEEE Transactions on Neural Networks，1989，1(2):459-473.

[51]WEINBERGER K Q，SAUL L K.Unsupervised learning of image manifolds by semidefinite programming[J].International Journal of Computer Vision，2006，70(1):77-90.

[52]GOH A，VIDAL R.Segmenting motions of different types by unsupervised manifold clustering[C]//IEEE Conference on Computer Vision and Pattern Recognition.Minneapolis，USA，2007:1-6.

[53]GOH A，VIDAL R.Unsupervised riemannian clustering of probability density functions[C]//Proceedings of the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases.Antwerp，Belgium，2008:377-392.

[54]HE Xiaofei.Incremental semi-supervised subspace learning for image retrieval[C]//Proceedings of the 12th Annual ACM International Conference on Multimedia.New York，USA，2004:2-8.

[55]BELKIN M，NIYOGI P.Semi-supervised learning on riemannian manifolds[J].Machine Learning，2004，56(1/2/3):209-239.

[56]孟德宇，徐宗本，戴明偉.一種新的有監督流形學習方法[J].計算機研究與發展，2007，44(12):2072-2077.MENG Deyu，XU Zongben，DAI Mingwei.A new supervised manifold learning method[J].Journal of Computer Research and Development，2007，44(12):2072-2077.

[57]CHENG Miao，FANG Bin，TANG Yuanyan，et al.Incremental embedding and learning in the local discriminant subspace with application to face recognition[J].IEEE Transactions on Systems，Man，and Cybernetics，Part C:Applications and Reviews，2010，40(5):580-591.

[58]XU Ye，SHEN Furao，HASEGAWA Q，et al.An online incremental learning vector quantization[C]//Proceedings of the 13th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining.Bangkok，Thailand，2009:1046-1053.

[59]NING Huazhong，XU Wei，CHI Yun，et al.Incremental spectral clustering by efficiently updating the eigen-system[J].Pattern Recognition，2010，43(1):113-127.

[60]ZHANG Zhenyue，WANG Jing，ZHA Hongyuan.Adaptive manifold learning[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34(2):253-265.