談 超 吉根林 趙 斌

(南京師范大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 南京 210023)

(tutu_tanchao@163.com)

基于增量切空間校準(zhǔn)的自適應(yīng)流式大數(shù)據(jù)學(xué)習(xí)算法

談 超 吉根林 趙 斌

(南京師范大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 南京 210023)

(tutu_tanchao@163.com)

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

流形學(xué)習(xí)；非線性維數(shù)約減；流式大數(shù)據(jù)；增量切空間；自適應(yīng)

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

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

有學(xué)者提出了增量流形學(xué)習(xí)算法.其中典型的增量流形學(xué)習(xí)算法包括增量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]等.現(xiàn)有增量流形學(xué)習(xí)算法的思想總體可以歸結(jié)為2類：第1類是在假設(shè)現(xiàn)有結(jié)果完全正確的前提下處理新來的樣本.這類算法能夠高效地處理新來的數(shù)據(jù).但是，當(dāng)前的數(shù)據(jù)流常常不能夠準(zhǔn)確地反映其本征的流形結(jié)構(gòu)，特別是在非均勻采樣的情形下，這類算法無法正確地給出高維數(shù)據(jù)的低維嵌入.第2類方法在嵌入訓(xùn)練數(shù)據(jù)集以外樣本的同時，更新訓(xùn)練數(shù)據(jù)集的嵌入坐標(biāo)，使其能夠更好地反映數(shù)據(jù)的特征.相比之下，這類方法能夠給出更加可靠的結(jié)果.

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

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

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

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

1 基于切空間校準(zhǔn)的增量流形學(xué)習(xí)算法原理

本節(jié)內(nèi)容由3個部分組成：1)在加入新樣本點以后更新協(xié)方差矩陣；2)構(gòu)造增量形式的局部切空間；3)根據(jù)得到的局部幾何信息獲取低維全局坐標(biāo).

1.1協(xié)方差矩陣的更新

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

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

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

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

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

同理，

則有：

而

故：

證畢.

這里Xnew是xneweT的矩陣形式.

得到Cnew的增量矩陣形式表達(dá)式為

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

其中Xnew-Mnew可具體化為

1.2構(gòu)造增量形式的局部切空間

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

因為

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

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

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

1.3獲得最優(yōu)低維全局坐標(biāo)

在本節(jié)中，我們根據(jù)局部切空間中的信息構(gòu)造全局坐標(biāo).受Zhang等人[5]的LTSA算法啟發(fā)，基于B的特征向量ui，我們可以導(dǎo)出最優(yōu)低維坐標(biāo)ti的構(gòu)造.

將ti寫成矩陣形式：

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

優(yōu)化函數(shù)可以寫為

2 算法描述與分析

2.1算法描述

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

根據(jù)第1節(jié)的分析，基于增量切空間校準(zhǔn)的自適應(yīng)流形學(xué)習(xí)SLITSA的算法描述見算法1.

算法1. 基于增量切空間的自適應(yīng)流式大數(shù)據(jù)學(xué)習(xí)算法.

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

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

步驟1. 更新協(xié)方差矩陣.

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

③ 根據(jù)式(3)計算Cnew.

步驟2. 構(gòu)造增量形式的局部切空間.

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

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

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

步驟3. 獲得最優(yōu)低維全局坐標(biāo).

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

2.2算法分析

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

3 實驗與結(jié)果分析

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

3.1SwissRoll數(shù)據(jù)集增量降維實驗

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

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

Table 1 Comparison of Distance in New Space Between

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

Table 2 Comparison of Distance in New Space Between

3.2MNIST數(shù)據(jù)集分類精度實驗

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

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

3.3面部圖像分類精度實驗

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

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

Fig. 2 Some images of Olivetti Faces dataset圖2 人臉圖像數(shù)據(jù)集中部分圖像

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

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

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

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

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

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

3.4RenderedFace數(shù)據(jù)集上的降維結(jié)果

Fig. 5 Dimensionality reduction results on Rendered Face dataset圖5 Rendered Face數(shù)據(jù)集上的降維結(jié)果

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

3.5算法時間性能比較

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

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

Fig. 6 Computation complexity on Swiss Roll dataset圖6 Swiss Roll數(shù)據(jù)集上的時間復(fù)雜度比較

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

Fig. 8 Computation complexity on Rendered Face dataset圖8 Rendered Face數(shù)據(jù)集上的時間復(fù)雜度比較

4 結(jié)束語

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

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

[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)(李志杰, 李元香, 王峰, 等. 面向大數(shù)據(jù)分析的在線學(xué)習(xí)算法綜述[J].計算機(jī)研究與發(fā)展, 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

國家自然科學(xué)基金項目(41471371,61702270)；江蘇省高校自然科學(xué)基金項目(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