基于增量切空間校準的自適應流式大數據學習算法

談 超 吉根林 趙 斌

(南京師范大學計算機科學與技術學院 南京 210023)

(tutu_tanchao@163.com)

基于增量切空間校準的自適應流式大數據學習算法

談 超 吉根林 趙 斌

(南京師范大學計算機科學與技術學院 南京 210023)

(tutu_tanchao@163.com)

流形學習是為了尋找高維空間中觀測數據的低維嵌入.作為一種有效的非線性維數約減方法，流形學習被廣泛應用于數據挖掘、模式識別等機器學習領域.然而，對于樣本外點學習、增量學習和在線學習等流形學習方法，面對流式大數據的學習算法時間效率較低.為此提出了一種新的基于增量切空間的自適應流式大數據學習算法(self-adaptive streaming big data learning algorithm based on incremental tangent space alignment, SLITSA)，該算法采用增量PCA的思想，增量地構造子空間，能在線或增量地檢測數據流中的內在低維流形結構，在迭代過程中構建新的切空間進行調準，保證了算法的收斂性并降低了重構誤差.通過人工數據集以及真實數據集上的實驗表明:該算法分類精度和時間效率優于其他學習算法，可推廣到在線或流式大數據的應用當中.

流形學習；非線性維數約減；流式大數據；增量切空間；自適應

云計算、物聯網、移動互聯、社交網絡等新興信息技術和應用模式的快速發展，促使全球數據總量急劇增加，推動人類社會邁入大數據時代[1].流式大數據作為大數據的一種重要形態，在商務智能、市場營銷和公共服務等諸多領域有著廣泛的應用前景，并已在金融銀行業、互聯網、物聯網等場景的應用中取得了顯著的成效.但流式大數據呈現出的動態到達以及樣本數量規模大、類別多等顯著特征，使得其與傳統批量大數據在數據處理的要求、方式等方面有著明顯的不同，也使得當前諸多模式識別和機器學習等相關算法無法直接應用到流式大數據處理中.而在實際的數據挖掘、模式識別和機器學習中，降維是許多任務的先決條件.因此，開發有效的降維方法是大數據時代的一個研究熱點.

流形學習作為一種有效的非線性降維算法，主要是為了發現高維觀測數據的低維光滑流形結構.近幾年來，大多數流形學習算法都屬于“批量”模式，以批處理的方式執行，即在運行算法之前必須收集好所有的數據，不能有效地處理數據連續到達的大數據流問題.這些流形方法包括等距映射算法(isometric mapping, Isomap)[2]、Laplacian特征映射算法(Laplacian eigenmaps, LE)[3]、局部線性嵌入算法(locally linear embedding, LLE)[4]、局部切空間校準算法(local tangent space alignment, LTSA)[5]等.然而，在實際中很多應用都需要處理實時數據流，圖像或數據是依次收集的，例如新聞文本分析、網絡數據挖掘、視頻監控及地震信號監測等.這些應用要求增量形式的流形學習算法能夠持續有效地更新在新來的以及已有的數據基礎上構建的流形，而無需在整個數據集上進行重復計算.另外，增量學習算法能夠可視化數據流形的變化過程，這對理解流式大數據的結構特征提供了極大的幫助.

有學者提出了增量流形學習算法.其中典型的增量流形學習算法包括增量Isomap算法(incremental Isomap, IIsomap)[6]、增量Laplacian映射算法(incremental LE, ILE)[7]、增量LLE算法(incremental LLE, ILLE)[8]、增量LTSA算法(incremental LTSA, ILTSA)[9]及增量HLLE算法(incremental HLLE, IHLLE)[10]等.現有增量流形學習算法的思想總體可以歸結為2類：第1類是在假設現有結果完全正確的前提下處理新來的樣本.這類算法能夠高效地處理新來的數據.但是，當前的數據流常常不能夠準確地反映其本征的流形結構，特別是在非均勻采樣的情形下，這類算法無法正確地給出高維數據的低維嵌入.第2類方法在嵌入訓練數據集以外樣本的同時，更新訓練數據集的嵌入坐標，使其能夠更好地反映數據的特征.相比之下，這類方法能夠給出更加可靠的結果.

經過調研發現，現有增量流形學習算法有著一定的局限性.例如，對于一些增量學習方法，新點可能會改變當前鄰域以及流形的局部分布情況.典型的如IIsomap算法就無法保證鄰域矩陣的連續性，新點的加入可能刪除鄰域圖中的臨界邊，顯著地改變相應的測地距離，因此將會產生短回路、空洞現象或者過度卷曲等問題.此外，計算成本過高是另一個問題.例如ILE算法通過引入局部線性重構機制來加入新點的鄰接信息，更新已有數據集的內在結構.該算法需要解決(k+1)×(k+1)的特征問題，總的時間復雜度為O((k+1)3).雖然保證了鄰域矩陣的連續性，但更新節點仍需要巨大的計算代價.ILLE算法是對新增數據點進行逐個更新，計算代價高，新的觀測區域數據的出現會破壞原有的幾何結構.ILTSA算法主要是采用迭代算法計算整個過程，而迭代優化問題的哪個部分需要計算則是未知的，故計算量很大.文獻[11]中算法的問題類似于上述的ILTSA算法，必須重新構建校準矩陣來容納新加入的點，對于大規模流式數據集來說不是很實用.

現有增量學習算法的局限還表現在：近似誤差方面沒有保證.例如，在增量PCA算法[12]中，新樣本點是逐個加入的，更新后的特征空間是通過使用原始圖像的低維系數向量獲得,所以這些方法受到不可預測近似誤差的影響.其他增量算法也存在類似的問題[13-14]，例如ILLE算法的誤差在降維過程中會越來越大，這是因為該算法中新代價矩陣Mnew的特征值沒有得到更新.隨著新增樣本數目的增加，Mnew與原代價矩陣M的前d個最小的特征值之間的差值會增大，從而誤差也會越來越大.

最近，有許多semi-supervised特征提取算法[15-17]被提出，結合了半監督技術與局部判別分析方法.然而這些方法沒有充分考慮在動態流形方面的增量學習，這在如今的流式大數據領域已成為一個研究熱點.

針對上述問題，本文提出了一種新的基于增量切空間校準的自適應流式大數據學習算法(self-adaptive streaming big data learning algorithm based on incremental tangent space alignment, SLITSA).SLITSA不受限于樣本協方差矩陣的大小，可解決LTSA中對大規模矩陣的特征分解問題.受文獻[18-20]的思想啟發，SLITSA首先通過增量主成分分析方法找到樣本點的局部主成分;然后增量地構造高維空間中數據樣本的切空間來刻畫局部鄰域，避免重復構造特征空間，獲得新點的局部坐標;最后通過最小平方差最小化原點和映射點之間的誤差，得到新點的全局坐標.在合成和真實世界數據集上的實驗結果表明本文所提SLITSA算法可以更加精確有效地獲得原始數據的低維近似表達.

1 基于切空間校準的增量流形學習算法原理

本節內容由3個部分組成：1)在加入新樣本點以后更新協方差矩陣；2)構造增量形式的局部切空間；3)根據得到的局部幾何信息獲取低維全局坐標.

1.1協方差矩陣的更新

Min等人[21]證明了一個樣本的局部切空間可以由其鄰域中樣本點組成的協方差矩陣的特征向量來表示.而該矩陣的特征向量可以通過局部主成分分析的方法來求解，因此，計算樣本點在低維空間中映射坐標的問題可以轉化為求解局部主成分分析的問題.

1) 構造新的局部切空間.給定采樣自非線性流形的一組數據點X=(x1,x2,…,xN)，將它們從m維空間映射到d維空間.傳統主成分分析方法PCA搜索向量c，T和矩陣U，將X從高維流形映射到低維流形d中：X=ceT+UT+E.為了得到最優解，我們對重構誤差E進行最小化：min‖E‖‖X-(ceT+UT)‖F.其中，‖·‖F為矩陣的Frobenius形式;c為X的平均值，c=XeN;e是N維的單位列向量;矩陣U∈m×d是仿射子空間的一組標準正交基;而T則是X在空間d的低維特征向量.線性條件下的奇異值分解可以用于解決這個問題，而當在非線性條件下，特別是在實時環境中，情況要復雜得多.為了求解增量非線性映射問題，需要通過局部線性排列來實現.

Mnew=αMN+(1-α)xneweT，

式(2)的迭代過程是算法SLITSA的一個重要部分.其收斂性可由下述理論證明.在文獻[20-21]中可見一個類似的理論.

現在，我們將證明式(2)中計算CN的迭代過程收斂.

同理，

則有：

而

故：

證畢.

這里Xnew是xneweT的矩陣形式.

得到Cnew的增量矩陣形式表達式為

為便于計算，式(4)可以具體化為

其中Xnew-Mnew可具體化為

1.2構造增量形式的局部切空間

為了在低維空間增量地更新所有點的嵌入坐標，我們以下述步驟來進行矩陣的更新.

因為

將A=(y1,y2,…,yd+1)代入式(7)可知：Cnew=AAT，表示新樣本的鄰域點以及它自身的局部切空間矩陣.

2) 構造一個內積矩陣B.B=AAT，B的大小為k×k，遠遠小于C.這樣可以增量地構造局部切空間矩陣，而不是重復計算新的協方差矩陣C.矩陣B是在矩陣A的列向量張成的子空間上的正交投影.故在增量子空間上的新點xnew的局部坐標可以通過計算A的前d個奇異向量得到[22-23]，相當于B的前d個最小的特征值對應的特征向量u1,u2,…,ud.

3) 計算新加入樣本點xnew的局部坐標.得到增量協方差矩陣的特征向量以后，新加入的樣本點xnew的局部坐標可計算為

1.3獲得最優低維全局坐標

在本節中，我們根據局部切空間中的信息構造全局坐標.受Zhang等人[5]的LTSA算法啟發，基于B的特征向量ui，我們可以導出最優低維坐標ti的構造.

將ti寫成矩陣形式：

Ti=(ti1,ti2,…,tik)是由最優嵌入坐標組成的矩陣.為了盡可能多地保存特征空間中的低維幾何信息，我們將重構誤差Ei最小化，如式(10)所示，

優化函數可以寫為

2 算法描述與分析

2.1算法描述

給定N個m維樣本向量構成的矩陣X=(x1,x2,…,xN)，取樣自流形m，新增樣本點xnew插入到X中.本文提出的SLITSA算法將這些點映射到低維的空間，以增量的方式給出d維坐標y1,y2,…,yN(dlt;m)，以及新點的低維映射坐標yn.

根據第1節的分析，基于增量切空間校準的自適應流形學習SLITSA的算法描述見算法1.

算法1. 基于增量切空間的自適應流式大數據學習算法.

輸入：高維樣本集Xi=(xi1,xi2,…,xiN)、新增樣本點xnew，其中i=1,2,…,N；

輸出：低維嵌入坐標Ti=(ti1,ti2,…,tiN)與tnew.

步驟1. 更新協方差矩陣.

① 為每個點xi確定k個近鄰點(歐氏距離)，組成矩陣xi，i=1,2,…,N；

③ 根據式(3)計算Cnew.

步驟2. 構造增量形式的局部切空間.

① 對Cnew進行特征分解；基于Cnew的前d個最大的特征值λi和特征向量vi構造矩陣A和矩陣B：A=(y1,y2,…,yd+1)，B=AAT；

② 計算矩陣B的前d個最小的特征值對應的特征向量u1,u2,…,ud；

③ 根據式(8)計算新加入樣本點xnew的局部坐標.

步驟3. 獲得最優低維全局坐標.

基于B的前d個最小的特征值對應的特征向量構成Wi=(e,ui1,ui2,…,uid)，令計算前d個最小特征值對應的特征向量Ti=(ti1,ti2,…,tid)，即算法SLITSA針對每個數據點的最優低維坐標，其中i=1,2,…,N.同理，根據xnew的局部坐標可計算出其低維嵌入坐標tnew.

2.2算法分析

與LTSA相比，A和B這2個矩陣在我們算法中的作用十分重要.LTSA與本文算法的時間效率近似，首先它們都是基于大小為協方差矩陣來構造切空間，然后這2個算法均是按相近的方式在d+1階的矩陣上進行特征分解或奇異值分解.然而，矩陣A和B的使用使得本文算法具有了增量學習的能力.另一方面，與其他增量算法相比，對基于矩陣B的特征解構建的切空間進行調準，可以提高降維結果的精度，這一點可以在第3節的實驗中得到證實.

3 實驗與結果分析

本文用一系列實驗結果來展示所提算法的性能和優勢，算法用Matlab實現，實驗環境為Core-2 2.2 GHz CPU的PC，具有2 GB內存.實驗所用數據取自一些典型的非線性流形學習數據集，包括來自真實世界的圖像，可以推廣到在線或流式大數據的應用當中.其中第1個數據集Swiss Roll是仿真數據，代表基本的非線性流形，常用于流形學習算法的直觀降維實驗中；后3個數據集都是真實世界中采樣的數字和人臉圖像數據集，具有多種特征維數，常用于流形學習算法在模式識別和圖像處理實驗中，能夠從識別精度和重構誤差等角度來深入考察算法對高維流形的學習效果.為了清楚地展示不同算法對這些數據集高維樣本點的降維效果，一般采用染色的辦法，相同顏色的點代表在高維空間中的位置關系.

3.1SwissRoll數據集增量降維實驗

第1組實驗是在Swiss Roll數據集[2]上測試增量學習能力，與增量Isomap算法進行比較.該數據集有500個初始樣本點，將從3維空間映射到2維空間中.設k為近鄰點數，數據點以隨機順序遞增.

首先，為了展示算法增量更新新點的精確度，我們在原來3維流形中加入一個坐標為[2,2,3]的新點，用本文提出的算法SLITSA和LTSA進行降維以后，計算該點在降維后新空間中的位置距離，如表1所示，可見當點數從開始的500個遞增至5 000個時(每次增加500個點)，該點在2種算法降維后的新空間中位置距離逐漸縮小.

Table 1 Comparison of Distance in New Space Between

為了進行對比，我們又對增量Isomap算法(IIsomap)和Isomap算法進行了同樣實驗，結果如表2所示.可以看出，該點在增量Isomap算法(IIsomap)和Isomap算法降維以后的新空間中位置變化較大，并且隨著點數增大而逐漸拉大.說明本文提出的算法在降維后能夠較好地保持原始空間中點的位置，并檢測高維空間中流形的結構關系.

Table 2 Comparison of Distance in New Space Between

3.2MNIST數據集分類精度實驗

本節中所用的數據集是MNIST手寫數字數據集[24].我們選取該數據集中的5類手寫數字圖像，其中包括數字0，1，3，4，6的圖像，每張手寫圖像大小為28×28，部分圖像如圖1所示.我們取每個數字的600張圖片作為測試集，4 000張作為訓練集，降到d維以后進行分類(d=11,12,…,20).當遺忘因子p取不同值時(p=0,1,…,8)，分類的結果如表3所示.

Table 3 Classification Accuracy After Dimensional Reduction of SLITSA on MINIST Dataset表3 SLITSA算法在MNIST數據集上降維后的分類精度

3.3面部圖像分類精度實驗

維數約減通常作為很多機器學習中分類任務的預處理步驟，所以降維在這些分類任務中起到重要作用.本節中我們首先在Olivetti Faces數據集[24]上展示采用不同算法降維以后的分類效果.

我們選擇此數據集中共8個人的人臉圖像，每人各選10張不同表情的圖像，每張圖像的大小為64×64，部分圖像如圖2所示:

Fig. 2 Some images of Olivetti Faces dataset圖2 人臉圖像數據集中部分圖像

將選取的人臉圖像數據集分為訓練集和測試集這2組.我們使用訓練集來學習1個投影矩陣，并將人臉圖像從高維空間映射到1個低維子空間.將數據集降到不同維數后，我們用k近鄰算法(kNN)作為分類器，在子空間估計測試樣本的分類精確度，設近鄰點數k=5.

從圖3所示的分類精確度可以看出，本文算法SLITSA能夠很好地發現輸入流形的內在結構信息，分類精度優于增量LE[7]、增量LTSA[9]、增量Isomap[6]、增量LLE[8]及增量HLLE[10]等比較算法.對于增量Isomap算法來說，新點的加入會導致短路邊問題，引起噪音現象，由于算法本身的原因，無法克服新點對鄰域圖中臨界邊的影響，導致了算法受到鄰域大小限制，對新點的學習能力大大削弱，不利于進行增量學習.而其他增量算法如增量LE、增量LTSA、增量LLE及增量HLLE等把數據點鄰域的樣本協方差矩陣的主元當作數據點切空間的標準正交基，在一些非均勻采樣的流形學習中，樣本鄰域的均值點與樣本自身有可能偏離程度較大，這時算法就會造成較大誤差，算法對于新來的樣本點不能進行有效的處理.而我們的算法SLITSA可以精確地映射樣本點到低維空間中，原因可以總結為SLITSA在特征空間的學習過程中使用了A和B這2個矩陣，保證了收斂并降低了重構誤差.

Fig. 3 Accuracy results of kNN classification after dimensional reduction on Olivetti Faces dataset圖3 Olivetti Faces數據集降到不同維數后kNN分類的精確度

為了進一步說明本文提出的算法在其他較大規模數據集上的效果，我們選擇Frey Face人臉圖像數據集[24]，將本文算法SLITSA與其他增量算法(增量LE、增量LTSA、增量LLE及增量HLLE等)在該數據集上降到10～100維并進行精確度對比，如圖4所示.Frey Face表情數據庫由1965幅維像素的面部表情圖像組成，包含不同姿態和表情的圖像數據.我們將其中600個圖像作為測試樣本，并在剩下的部分中隨機選擇10個圖像作為測試集.將數據集降到不同維數后，用k近鄰算法(kNN)作為分類器，估計測試樣本的分類精確度，設近鄰點數k=5.在本實驗中，SLITSA算法及其他增量算法的參數設置與Olivetti Faces數據集上的實驗相同.

Fig. 4 Accuracy results of kNN classification after dimensional reduction on Frey Face dataset圖4 Frey Face數據集降到不同維數后kNN分類的精確度

從圖4所示的分類精確度可以看出，算法SLITSA能夠很好地發現輸入流形的內在結構信息，在同樣條件下降維以后和增量LE、增量LTSA、增量LLE及增量HLLE等算法相比，具有不錯的學習效果，主要是歸功于流形學習過程中2個矩陣的使用，取得了更精確的降維結果，保證了收斂并降低了重構誤差，可知算法SLITSA具有更好的穩定性及更可靠的準確性.

3.4RenderedFace數據集上的降維結果

Fig. 5 Dimensionality reduction results on Rendered Face dataset圖5 Rendered Face數據集上的降維結果

本節中考慮Rendered Face數據集[2]上的實驗結果，如圖5所示.該數據集包含698個人臉雕塑圖像，具有64×64像素.人臉圖像具有2組姿態參數，從上到下和從左到右.我們用SLITSA算法將這698個高維圖像數據集降到2維，并在2維的坐標圖中展示其結果，每個點代表一個人臉圖像.隨機選取10個圖像作為樣本，并用圓圈進行標記.我們可以直觀地看出，人臉沿著橫坐標從朝向左邊轉到朝向右邊，沿著縱坐標從仰視變為俯視.故通過我們的算法，低維的映射結果能夠很好地保持原始數據集的內在結構.

3.5算法時間性能比較

為了展示本算法SLITSA與其他增量算法(增量LE、增量LTSA、增量LLE及增量HLLE等)的計算效率，我們在3.1節中的Swiss Roll數據集和3.4節的Rendered Face數據集上進行降維實驗，將原數據集降到2維以后進行了時間復雜度的比較.

如圖6所示，增量HLLE算法(IHLLE)的時間復雜度遠遠高出其他算法，在圖7中我們列出了其中4種算法的時間復雜度.一開始本算法SLITSA的復雜度高于增量LE算法，但隨著樣本點數n的增加，本算法SLITSA的復雜度漸趨平穩，并且比增量LE算法以外的其他已有增量流形學習算法都快，故在目前已有的增量流形學習算法中能夠達到良好的效果.圖8所展示的是Rendered Face數據集上的實驗，可見在100～600個高維圖像數據集降維實驗中，本算法始終保持較低的時間復雜度，結合前面3.1～3.4節的分類精度和重構誤差實驗，可知本算法SLITSA的綜合性能非常優秀，具有重要的研究價值.

Fig. 6 Computation complexity on Swiss Roll dataset圖6 Swiss Roll數據集上的時間復雜度比較

Fig. 7 Computation complexity of four incremental methods圖7 4種增量算法的時間復雜度比較

Fig. 8 Computation complexity on Rendered Face dataset圖8 Rendered Face數據集上的時間復雜度比較

4 結束語

本文基于增量切空間提出了一種新的增量流形學習算法SLITSA.該算法采用增量PCA的思想，增量地構造子空間，樣本點局部信息的更新是從已有點和新點的特征向量得到的，故在更新局部切空間時無需重復計算整個協方差矩陣，與傳統的批量模式算法相比，實時效果有了一定提高；受已有樣本影響的自適應因子控制，新點的高維坐標局部線性重構以后保存了其到低維空間的映射，并反映了增量的性質；算法SLITSA可以精確地映射樣本點到低維空間中，原因是SLITSA在特征空間的學習過程中使用了A和B這2個矩陣，在迭代過程中我們基于矩陣B的特征解構建的切空間進行了調準，保證了收斂并降低了重構誤差.可以提高降維結果的精度，使得本文算法具有了增量學習的能力.

大量針對實際數據集的實驗表明本文算法與其他算法相比，具有較好的降維效果及識別能力，可以很好地應用于大規模數據流分析中.其中，手寫數字數據集是機器學習和模式識別領域被廣泛使用的標準測試樣本集，這里我們使用該數據集對本文提出的算法和相關算法進行實驗驗證和比較，具有一定的客觀性和說服力.盡管人工智能在現實世界中的應用環境發生了變化，特別是在流式大數據的分析和識別中，數據集從靜態變為了動態數據，而我們的實驗表明，本文提出的方法采用增量PCA的思想，增量地構造子空間，實時效果有了一定提高，并反映了增量的性質，使得該文算法具有了增量學習的能力.故這里雖然使用的手寫數字數據集屬于靜態數據集，但在近期將我們的方法應用于其他類型的符號識別可能特別有前途，包括動態環境下的流式數據集.在這些環境下，應用本文算法不但可以識別新的樣本，與傳統的批量模式算法相比，本文算法SLITSA可以精確地映射樣本點到低維空間中，保證了收斂并降低了重構誤差，可以提高降維結果的精度.

[1]Li Zhijie, Li Yuanxiang, Wang Feng, et al. Online learning algorithms for big data analytics: A survey[J]. Journal of Computer Research and Development, 2015, 52(8): 1707-1721 (in Chinese)(李志杰, 李元香, 王峰, 等. 面向大數據分析的在線學習算法綜述[J].計算機研究與發展, 2015, 52(8): 1707-1721)

[2]Tenenbaum J, Silva V, Langford J. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000, 290(5500): 2319-2323

[3]Belkin M, Niyogi P. Laplacian eigenmaps for dimensionality reduction and data representation [J]. Neural Computation, 2003, 15(6): 1373-1396

[4]Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290 (5500): 2323-2326

[5]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

[6]Law M H C, Jain A K. Incremental nonlinear dimensionality reduction by manifold learning[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2006, 28(3): 377-391

[7]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

[8]Kouropteva O, Okun O, Pietik?inen M. Incremental locally linear embedding[J]. Pattern Recognition, 2005, 38(10): 1764-1767

[9]Abdel-Mannan O, Hamza A B, Youssef A. Incremental line tangent space alignment algorithm[C] //Proc of the Canadian Conf on Electrical and Computer Engineering. Piscataway, NJ: IEEE, 2007: 1329-1332

[10]Li Housen, Jiang Hao, Barrio R, et al. Incremental manifold learning by spectral embedding methods[J]. Pattern Recognition Letters, 2011, 32(10): 1447-1455

[11]Zhang Peng, Qiao Hong, Zhang Bo. An improved local tangent space alignment method for manifold learning[J]. Pattern Recognition Letters, 2011, 32(2): 181-189

[12]Zhao Haitao, Yuen Pongchi, Kwok J T. A novel incremental principal component analysis and its application for face recognition[J]. IEEE Trans on Systems, 2006, 36(4): 873-886

[13]Han Zhi, Meng Deyu, Xu Zongben, et al. Incremental alignment manifold learning[J]. Journal of Computer Science and Technology, 2011, 26(1): 153-165

[14]Li Bo, Du Jing, Zhang Xiaoping. Feature extraction using maximum nonparametric margin projection[J]. Neurocomputing, 2016, 188(5): 225-232

[15]Ling Gohfan, Han Pangying, Yee K E, et al. Face recognition via semi-supervised discriminant local analysis[C] //Proc of the 3rd Int Conf on Signal and Image Processing Applications(ICSIPA). Piscataway, NJ: IEEE, 2015: 292-297

[16]Han Pangying, Yin O S, Ling Gohfan. Semi-supervised generic descriptor in face recognition[C] //Proc of the 11th Int Colloquium on Signal Processing and Its Applications(CSPA). Piscataway, NJ: IEEE, 2015: 21-25[

17]Xu Yunfei, Huang Houjun, Yang Lin, et al. Semi-supervised local fisher discriminant analysis for speaker verification[J]. Advances in Information Sciences and Service Sciences, 2014, 6(6): 1-11

[18]Cheng Miao, Fang Bin, Tang Yuanyan, et al. Incremental embedding and learning in the local discriminant subspace with application to face recognition[J]. IEEE Trans on Systems, Man, and Cybernetics-PART C: Applications and Reviews, 2010, 40(5): 580-591

[19]Mantziou E, Papadopoulos S, Kompatsiaris Y. Scalable training with approximate incremental laplacian eigenmaps and PCA[C] //Proc of the 21st ACM Int Conf on Multimedia. New York: ACM, 2013: 381-384

[20]Weng Juyang, Zhang Yilu, Hwang W S. Candid covariance-free incremental principal component analysis[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 2003, 25(8): 1034-1040

[21]Min Wanli, Lu Ke, He Xiaofei. Locality pursuit embedding[J]. Pattern Recognition, 2004, 37(4): 781-788

[22]Li Yongmin. On incremental and robust subspace learning[J]. Pattern Recognition, 2004, 37(7): 1509-1518

[23]Golub G H, Van Loan C F. Matrix Computations[M]. Baltimore, MD: Johns Hopkins University Press, 2012[24]Roweis S. Research: Data for MATLAB[OL].[2016-03-20]. http://www.cs.nyu.edu/～roweis/data.html

TanChao, born in 1983. PhD. Lecturer. Member of CCF. Her main research interests include machine learning and data mining.

JiGenlin, born in 1964. PhD. Professor, PhD supervisor. Member of CCF. His main research interests include data mining and its application.

ZhaoBin, born in 1978. PhD. Associate professor, MSc supervisor. Member of CCF. His main research interests include data mining and its application (zhaobin@njnu.edu.cn).

Self-AdaptiveStreamingBigDataLearningAlgorithmBasedonIncrementalTangentSpaceAlignment

Tan Chao, Ji Genlin, and Zhao Bin

(School of Computer Science and Technology, Nanjing Normal University, Nanjing 210023)

Manifold learning is developed to find the observed data’s low-dimension embeddings in high dimensional data space. As a type of effective nonlinear dimension reduction method, it has been widely applied to the machine learning field, such as data mining and pattern recognition, etc. However, when processing a large scale data stream, the complexity of time is too high for many traditional manifold learning algorithms, including out of sample learning algorithm, incremental learning algorithm, online learning algorithm, and so on. This paper presents a novel self-adaptive learning algorithm based on incremental tangent space alignment (named SLITSA) for big data stream processing. SLITSA adopts the incremental PCA to construct the subspace incrementally, and can detect the intrinsic low dimensional manifold structure of data streams online or incrementally. In order to ensure the convergence of SLITSA and reduce the reconstruction error, it can also construct a new tangent space for adjustment during the iterative process. Experiments on artificial data sets and real data sets show that the classification accuracy and time efficiency of the proposed algorithm are better than other manifold learning algorithms, which can be extended to the application of streaming data and real-time big data analytics.

manifold learning; nonlinear dimension reduction; big data streams; incremental tangent space; self-adaptive

2016-09-20；

2017-02-21

國家自然科學基金項目(41471371,61702270)；江蘇省高校自然科學基金項目(15KJB520022)

This work was supported by the National Natural Science Foundation of China (41471371, 61702270) and the Natural Science Foundation of Jiangsu Provincial Education Department (15KJB520022).

吉根林(glji@njnu.edu.cn)

TP181