路 梅，李凡長

1.蘇州大學(xué) 計算機學(xué)院，江蘇 蘇州 215006

2.江蘇師范大學(xué) 計算機學(xué)院，江蘇 徐州 221116

鄰域嵌入的張量學(xué)習(xí)*

路 梅1,2，李凡長1+

1.蘇州大學(xué) 計算機學(xué)院，江蘇 蘇州 215006

2.江蘇師范大學(xué) 計算機學(xué)院，江蘇 徐州 221116

+Corresponding author:E-mail:lfzh@suda.edu.cn

LU M ei,LI Fanzhang.Neighborhood-embedded tensor learning.Journal of Frontiers of Computer Science and Technology,2017,11(7)：1102-1113.

傳統(tǒng)的機器學(xué)習(xí)算法把數(shù)據(jù)表示成向量的形式進(jìn)行處理，而現(xiàn)實世界許多應(yīng)用中的數(shù)據(jù)都是以張量形式存在的，如圖像、視頻數(shù)據(jù)等，如果將這些本質(zhì)上非向量形式的數(shù)據(jù)強制轉(zhuǎn)換成向量表示，不僅會產(chǎn)生維數(shù)災(zāi)難和和小樣本問題，而且會破壞數(shù)據(jù)本身的內(nèi)部空間排列結(jié)構(gòu)，不利于發(fā)現(xiàn)數(shù)據(jù)的好的低維表示。判別鄰域嵌入（discrim inant neighborhood embedding，DNE）是比較流行的面向向量的判別分析方法，在改進(jìn)DNE算法的基礎(chǔ)上，提出了面向張量數(shù)據(jù)的局部一致保持的鄰域嵌入張量判別學(xué)習(xí)（neighborhood-embedded tensor learning，NTL）算法。NTL算法不僅克服了DNE面向向量的缺點，而且彌補了DNE方法偏重數(shù)據(jù)的鄰域點而忽略數(shù)據(jù)的非鄰域點影響的不足，通過精心設(shè)計目標(biāo)函數(shù)（嵌入3個圖：同類結(jié)點的鄰接圖、不同類結(jié)點的鄰接圖、其他結(jié)點的關(guān)聯(lián)圖），使投影空間的同類結(jié)點更加緊湊，不同類結(jié)點更加疏遠(yuǎn)，從而增強了算法的判別能力。3個公開數(shù)據(jù)庫（ORL、PIE和COIL20）上的實驗驗證了NTL擁有更高的識別率，同時也擁有更高的算法效率。

判別鄰域嵌入（DNE）；張量子空間分析（TSA）；維數(shù)約簡；判別分析；張量學(xué)習(xí)

1 引言

隨著科學(xué)技術(shù)的飛速發(fā)展，越來越多的應(yīng)用研究需要處理大量的高維數(shù)據(jù)，如圖像檢索、文本分類、語音識別和基因表示等。為了有效地表示和識別高維數(shù)據(jù)，傳統(tǒng)的機器學(xué)習(xí)算法[1-16]把原始的高維數(shù)據(jù)投影到低維向量空間進(jìn)行降維和特征提取，最大限度地保留其內(nèi)在信息的同時得到高維數(shù)據(jù)的低維表示。維數(shù)約簡對于處理高維數(shù)據(jù)非常重要。目前較為流行的降維算法有主成分分析（principal componentanalysis，PCA）[7,12]、半監(jiān)督降維方法（sem isupervised dimensionality reduction，SSDR）[13,17]、邊界Fisher分析（marginal Fisher analysis，MFA）[13]、局部保持投影（locality preserving projections，LPP）[10]、判別鄰域嵌入（discriminantneighborhood embedding，DNE）[14]等。PCA方法廣泛應(yīng)用于圖像檢索和特征提取中，是經(jīng)典的降維方法。PCA通過最大化代表原始圖像的協(xié)方差矩陣，以達(dá)到最小化重建樣本誤差，最大限度保留數(shù)據(jù)的全局結(jié)構(gòu)信息的目的。PCA方法是一種無監(jiān)督的方法，只能解釋兩個特征集合之間的全局相關(guān)關(guān)系，而且只能作用于向量表示的數(shù)據(jù)。為了得到數(shù)據(jù)更合理的低維表示，降維過程中充分利用有標(biāo)記信息以及保留樣本點的判別信息和局部結(jié)構(gòu)信息非常重要。SSDR是一種半監(jiān)督的降維方法，能夠充分利用有監(jiān)督信息和無類別標(biāo)記信息降維。MFA方法考慮到樣本數(shù)據(jù)的判別信息，構(gòu)建類內(nèi)鄰接圖和邊界點的類間鄰接圖，通過最小化類內(nèi)距離之和與類間距離之和的比值尋找最優(yōu)投影方向。LPP方法是拉普拉斯映射的一種線性近似，同時具有流形學(xué)習(xí)方法和線性降維方法的一些優(yōu)點，但是LPP方法是無監(jiān)督學(xué)習(xí)方法，沒有有效地利用已知訓(xùn)練點的分類信息。

與PCA方法類似，SSDR、MFA、LPP和DNE方法也都是面向向量的降維方法。但是現(xiàn)實世界的許多應(yīng)用中，數(shù)據(jù)都表示成張量形式。例如，圖像可以表示成二階張量，視頻可以表示成三階張量。如果將這些本質(zhì)上非向量形式的數(shù)據(jù)強制轉(zhuǎn)換成向量表示，會產(chǎn)生維數(shù)災(zāi)難和小樣本問題。具體來說，將矩陣或者更高階的數(shù)據(jù)表示成一階向量，形成了高維的向量空間，面向向量的降維方法在求解投影向量時需計算解特征值問題，計算過程由于維數(shù)太高過于耗時，從而產(chǎn)生維數(shù)災(zāi)難。同時，樣本數(shù)目常常小于向量空間的維數(shù)，因此需求解特征值的矩陣奇異。為解決此類問題，面向向量的降維方法通常先用PCA降維，但是這一過程常常會丟失某些有用的判別信息。除此之外，基于向量的表示破壞了圖像、視頻等多維數(shù)據(jù)本身的內(nèi)部空間排列結(jié)構(gòu)，在尋找投影向量的過程中不考慮數(shù)據(jù)本身在空間排列上的約束，因此不利于發(fā)現(xiàn)數(shù)據(jù)的低維表示。為了克服上述缺點，在傳統(tǒng)機器學(xué)習(xí)算法的基礎(chǔ)上延伸了許多面向張量的學(xué)習(xí)算法[18-24]?；趶埩康慕稻S方法可以直接處理張量數(shù)據(jù)，避免了直接處理向量所帶來的一系列問題。He等人提出的張量子空間分析（tensor subspace analysis，TSA）方法可以看成是LPP算法在張量上的拓展[20]。

本文對DNE方法進(jìn)行改進(jìn)，并和張量表示結(jié)合，提出了一種新的算法——領(lǐng)域嵌入的張量判別學(xué)習(xí)（neighborhood-embedded tensor learning，NTL）方法。在DNE中，大小為n1×n2的圖像表示成向量空間數(shù)據(jù)點，DNE的線性轉(zhuǎn)換表示為Y=PTX，其中P是n×n的投影矩陣，因此DNE有n個待估計的參數(shù)。在本文方法中，圖像表示成二階張量，張量子空間的線性轉(zhuǎn)換為Y=UTXV，其中U和V分別是大小為n1×d1(d1＜n1)和 n2×d2(d2＜n2)的矩陣，共有 2(d1+d2)個待估計的參數(shù)，遠(yuǎn)遠(yuǎn)小于DNE算法需要估計的參數(shù)。NTL方法通過構(gòu)造3個圖（同類結(jié)點的鄰接圖、不同類結(jié)點的鄰接圖、其他結(jié)點的關(guān)聯(lián)圖），精心設(shè)計目標(biāo)函數(shù)，通過最小化目標(biāo)函數(shù)使得同類結(jié)點更加緊湊，不同類結(jié)點更加疏遠(yuǎn)。

NTL方法在以下幾方面值得關(guān)注：

（1）傳統(tǒng)的機器學(xué)習(xí)方法如PCA、MFA、DNE等方法都是面向向量的維數(shù)約簡算法，都是通過找到一個從高維到低維的映射實現(xiàn)降維。NTL方法通過尋找映射l2＜n2)實現(xiàn)降維。

（2）NTL方法的計算比較簡單，通過計算兩個特征值問題即可。因為求解特征值的矩陣大小為n1×n1以及n2×n2，遠(yuǎn)遠(yuǎn)小于面向向量算法的求解特征值的矩陣大小，所以NTL的存儲空間和時間復(fù)雜度相對較小。

（3）NTL方法不僅關(guān)注了結(jié)點的相鄰關(guān)系對低維空間數(shù)據(jù)點關(guān)系的影響，同時也考慮了結(jié)點的不相鄰關(guān)系對低維空間數(shù)據(jù)點關(guān)系的影響，因此和DNE相比具有更強的判別性能。

（4）本文主要考慮二階張量的學(xué)習(xí)問題，NTL方法也可以推廣到更高階的張量學(xué)習(xí)中。

本文組織結(jié)構(gòu)如下：第2章是張量和DNE方法的相關(guān)知識的簡單介紹；第3章提出鄰域嵌入的張量學(xué)習(xí)方法，給出目標(biāo)函數(shù)和優(yōu)化算法；第4章通過若干個分類方法的對比實驗，驗證本文方法的有效性；第5章是總結(jié)和展望。

2 相關(guān)知識介紹

2.1 張量

2.1.1 張量代數(shù)

定義1（N階張量）被稱為p階逆變、q階協(xié)變的N階張量，若在坐標(biāo)變換時，其分量按如下方式變換：

其中，N=p+q。

張量A的每一維稱作一個模式（mode），高階張量又稱多模態(tài)數(shù)據(jù)、多重線性代數(shù)。如，N階張量共有N個模式，維I1,I2,…,IN分別叫作第一模式，第二模式，…，第N模式。

人們熟知的標(biāo)量是零階張量，向量是一階張量，矩陣是二階張量。

定義2（張量的n-mode展開）張量的模式 n 展開為，其元素的行坐標(biāo)為 in，列坐標(biāo)為 (in+1-1)In+2In+3…INI1I2…In-1+(in+2-1)In+3In+4…INI1I2…In-1+(iN-1)I1I2…In-1+(i1-1)I2I3…In-1+(i2-1)I3I4…In-1+ …+in-1。

張量的n-mode展開實質(zhì)上是把高階張量展開成矩陣集合的形式，又叫張量矩陣化。

例如，三階張量按第一模式有兩種展開方式，如圖1所示。

定義 3（張量乘法） 設(shè)是n-階張量，是矩陣，則張量A和矩陣U的乘積是一個 I1×I2×…×In-1×J×A×In+1×…×IN張量，又叫nmode積，表示如下：

張量乘法用張量展開式表示如下：

Fig.1 Two kindsof three-order tensorunfolding圖1 三階張量按照第一模式展開的兩種方式

2.1.2 張量學(xué)習(xí)過程

圖2給出了數(shù)據(jù)的張量表示的機器學(xué)習(xí)過程。由若干個張量表示的訓(xùn)練樣本組成訓(xùn)練樣本集合，使用張量學(xué)習(xí)方法，如TSA等，把訓(xùn)練樣本TS投影到由基向量U(1)×U(2)×…×U(N)張成的空間，得到訓(xùn)練樣例的低維表示GS，然后利用基向量U(1),U(2),…,U(N)把張量表示的測試樣例TT投影到基向量張成的空間得到測試樣例的低維表示GT，最后可以使用KNN、SVM等方法實現(xiàn)分類、檢索等應(yīng)用。

2.2 DNE算法

DNE算法是有監(jiān)督子空間學(xué)習(xí)方法。利用鄰域信息和類別信息，DNE算法使得數(shù)據(jù)樣本在低維空間的投影保持了原來的鄰域關(guān)系，同類樣本的低維投影形成緊湊的子流形，不同類的樣本投影盡可能地分開。

印刷行業(yè)的生產(chǎn)過程中，難免會由于溶劑型油墨的揮發(fā)而產(chǎn)生VOCs，因洗車水、潤版液、清洗橡皮布等產(chǎn)生廢液，從而對環(huán)境產(chǎn)生影響。當(dāng)問及多家企業(yè)對于政府下達(dá)的如此嚴(yán)苛的環(huán)保政策的看法時，回答多是：企業(yè)的立場應(yīng)與政府保持一致，如此嚴(yán)苛的環(huán)保要求一定程度上對企業(yè)來說是一種約束與鞭策，它能更好地促進(jìn)企業(yè)規(guī)范化、可持續(xù)化、綠色化發(fā)展?？陀^上也解決了印刷行業(yè)供給側(cè)改革問題，即要求清理僵尸企業(yè)，淘汰落后產(chǎn)能，將企業(yè)的發(fā)展方向鎖定為新興領(lǐng)域、創(chuàng)新領(lǐng)域，創(chuàng)造新的經(jīng)濟(jì)增長點。在嚴(yán)峻的政策環(huán)境下，只以價格取勝而不顧及質(zhì)量、環(huán)保要求的企業(yè)被關(guān)閉，印刷市場更加規(guī)范，客觀上增加了符合要求企業(yè)的活源。

DNE算法的目標(biāo)函數(shù)如下所示，

其中，I是單位矩陣；P是投影矩陣。

3 鄰域嵌入的張量學(xué)習(xí)

3.1 鄰域嵌入的張量學(xué)習(xí)方法及目標(biāo)函數(shù)是二階張量，li∈{1,2,…,c}是Xi的類別標(biāo)記，N是樣本的個數(shù)，n1和n2分別是Xi的第一模式和第二模式的維數(shù)，c是

DNE方法是一種有監(jiān)督的學(xué)習(xí)方法，面向的是向量形式的數(shù)據(jù)。如果要處理的數(shù)據(jù)是圖像，則使用DNE方法分類時，首先要把圖像數(shù)據(jù)轉(zhuǎn)換成向量，然后才能使用DNE方法進(jìn)行處理。許多已有的降維方法都是以這種方式處理圖像數(shù)據(jù)的，但是文獻(xiàn)[25]指出這樣的處理方式對圖像數(shù)據(jù)而言并不是十分有效。本文提出一種新穎的面向張量數(shù)據(jù)的子空間學(xué)習(xí)方法，叫作鄰域嵌入的張量學(xué)習(xí)方法NTL。NTL方法可以看作是對DNE方法改進(jìn)，并將其拓展到張量空間的學(xué)習(xí)上。

Fig.2 Tensor-data-basedmachine learning process圖2 數(shù)據(jù)張量表示的機器學(xué)習(xí)過程

NTL方法描述如下：依據(jù)給定的數(shù)據(jù)集和類別標(biāo)記，對DNE稍作改進(jìn)。把所有的結(jié)點分成3類，第一類是同類的k近鄰結(jié)點，第二類是不同類的k近鄰結(jié)點，第三類是除了第一類、第二類以外的其他結(jié)點。對于第一類結(jié)點，通過降維以后，希望這些結(jié)點更加緊湊；對于第二類結(jié)點，希望降維后的結(jié)點更加疏遠(yuǎn)；對于第三類結(jié)點，根據(jù)這些結(jié)點的鄰域鏈接情況，使用類似于PCA的方法確定其和鄰域點的遠(yuǎn)近關(guān)系。由此，按照如下方式構(gòu)造圖G1、G2和G3。

G1=＜V,E1,F1＞：數(shù)據(jù)集上的所有數(shù)據(jù)構(gòu)成圖G1的頂點V={X1,X2,…,XN}；若數(shù)據(jù) Xi和 Xj屬于同一類，并且 Xi是 Xj的 k1-鄰近點，或者 Xj是 Xi的 k1-鄰近點，則在結(jié)點Xi和Xj之間連一條線；若數(shù)據(jù)Xi和Xj不屬于同一類，并且Xi是Xj的k2-鄰近點，或者Xj是Xi的k2-鄰近點，則在結(jié)點Xi和Xj之間連一條線.圖G1的權(quán)重F1可以按如下方式定義：

G3=＜V,E3,F3＞：數(shù)據(jù)集上的所有數(shù)據(jù)構(gòu)成圖G3的頂點V={X1,X2,…,XN}；若數(shù)據(jù) Xi和 Xj屬于同一類，并且 Xi不是 Xj的k1-鄰近點，或者 Xj不是 Xi的k1-鄰近點，則在結(jié)點Xi和Xj之間連一條線；若數(shù)據(jù)Xi和 Xj不屬于同一類，并且 Xi不是 Xj的k2-鄰近點，或者Xj不是Xi的k2-鄰近點，則在結(jié)點Xi和 Xj之間連一條線。圖G3的權(quán)重F3按如下方式定義：

其中，no=N2-ns-nd。

投影后的類內(nèi)緊湊程度為：

投影后的類間分離程度為：

同時，希望投影后第三類結(jié)點均方差盡可能大，則得到目標(biāo)函數(shù)為：

3.2 目標(biāo)函數(shù)的優(yōu)化

先進(jìn)行如下的化簡：

3)，“tr”表示矩陣的跡。又由于||A||2=tr(ATA)，類似的，可以得到：

注意到上述兩個函數(shù)的優(yōu)化彼此相互依賴，因此U和V不能單獨求解。為了求解上述優(yōu)化問題，先固定矩陣V（滿足條件VTV=Il1），則根據(jù)，可以計算出和的值，帶入優(yōu)化公式（1）。優(yōu)化問題轉(zhuǎn)化為求解的特征值問題。設(shè)d是的特征值的個數(shù)，不失一般性，設(shè)特征值為λ1≥λ2≥…≥λd，其對應(yīng)的特征向量分別為u1,u2,…,ud，取d1個最大的特征值對應(yīng)的特質(zhì)向量構(gòu)成特征矩陣U。

4 實驗結(jié)果

為了驗證NTL算法的有效性，將其應(yīng)用在3個公開數(shù)據(jù)庫中，即ORL數(shù)據(jù)庫（http://www.uk.research.att.com/facedatabase.htm l）、PIE數(shù)據(jù)庫（http://mu.edu/projects/project_418.htm l）以及COIL20數(shù)據(jù)庫（http://www.cs.columbia.edu/CAVE/software/softlib/coil-20.php），并與PCA、MFA、DNE、TSA等算法進(jìn)行比較。每張圖像數(shù)字化并歸一化，其灰度值為0～255。為了有效地計算，所有圖像都縮放為32×32像素。實驗中，PCA、MFA和DNE算法處理的圖像數(shù)據(jù)都表示成1 024維的向量形式，TSA和NTL算法處理的圖像數(shù)據(jù)表示成(32×32)-維的二階張量形式。為了避免小樣本問題，MFA和DNE算法采用二次降維，另外由于PCA降維能去除噪聲，為了測試在不去除噪聲情況下算法的性能，采用隨機降維，降到100維。設(shè)置NTL的參數(shù)α=20。隨機選取訓(xùn)練集和測試集，利用計算得到的投影矩陣把訓(xùn)練集和測試集投影到低維空間，采用最近鄰分類器進(jìn)行分類，識別率為20次實驗的平均值。實驗中，設(shè)置TSA和NTL算法的迭代次數(shù)為2次。

4.1 ORL人臉數(shù)據(jù)庫

ORL人臉數(shù)據(jù)庫包含40人的400張人臉圖像，每個人的圖片總數(shù)為10張。其中一些人臉的圖像是在不同時期拍攝的。人的臉部表情和臉部細(xì)節(jié)有著不同程度的變化，比如睜眼或閉眼、笑或非笑，以及戴眼鏡或不戴眼鏡；人臉姿態(tài)也有相當(dāng)程度的變化，深度旋轉(zhuǎn)和平面旋轉(zhuǎn)可達(dá)20°。隨機從每個個體集合中選取l(l=3,4,5,6,7,8)，選擇60%樣本作為訓(xùn)練集，其余的40%作為測試集。

各算法在ORL數(shù)據(jù)集上的實驗結(jié)果在表1、表2和圖3中給出。表1給出了各算法作用在ORL數(shù)據(jù)集上的最好識別率，括號內(nèi)的值是相應(yīng)算法取得最好值時的判別子空間的維度。表2給出了各算法作用在ORL數(shù)據(jù)集上的最優(yōu)識別結(jié)果（包括平均識別率及其對應(yīng)的標(biāo)準(zhǔn)差）。圖3給出了ORL數(shù)據(jù)集隨機選取l=3和l=5時各算法隨維度增加的識別率。

Table 1 Optimalaccuracy and cost time of allmethodson ORL database表1 ORL數(shù)據(jù)集上各算法最佳識別率和耗費時間

Table2 Averageaccuracy,mean varianceand optimalembedded dimension of allmethodson ORL database表2 ORL數(shù)據(jù)集上各算法平均識別率、均方差和最優(yōu)嵌入維數(shù)

Fig.3 Accuracy ofallmethodsvs.dimension on ORL database圖3 各算法在ORL數(shù)據(jù)集上隨維度增加的識別率

從表1、表2以及圖3中可以看到：

（1）對于ORL數(shù)據(jù)集上的每個l，NTL算法與原來的DNE算法相比，最佳算法識別率最高提升了24.7%(l=4)，最低提升了6.9%(l=8)，平均提升了12.3%。NTL算法的性能比PCA、MFA和DNE算法好，NTL算法略好于TSA算法。出現(xiàn)這種結(jié)果的主要原因是PCA、MFA和DNE算法都是面向向量表示形式的數(shù)據(jù)，NTL和TSA算法是面向張量表示形式的數(shù)據(jù)，因為張量表示的數(shù)據(jù)最大限度地保留了數(shù)據(jù)內(nèi)在的結(jié)構(gòu)，同時也克服了傳統(tǒng)面向向量的算法存在的維數(shù)災(zāi)難、小樣本等問題，所以與PCA、MFA和DNE算法相比，NTL算法和TSA算法能更好地保留數(shù)據(jù)的內(nèi)在幾何結(jié)構(gòu)，獲得數(shù)據(jù)更好的低維表示，從而取得較好的識別性能。

（2）從表1中可以看出，PCA算法耗費時間最少，NTL算法和TSA算法相當(dāng)，但是比MFA和DNE算法耗費時間少。NTL算法不僅在識別率上而且在時間上都優(yōu)于MFA和DNE算法。所有算法都運行在Intel Core i5-2520M 2.50 GHz，8 GB內(nèi)存的個人電腦上，使用Matlab7.0編程實現(xiàn)。

（3）對于ORL數(shù)據(jù)集上的每個l，NTL算法的最好性能在較低維就能達(dá)到。在維數(shù)較低的時候，NTL算法的平均識別率隨著張量子空間維數(shù)的增加迅速提升。當(dāng)張量子空間的維數(shù)達(dá)到一定數(shù)值時，NTL算法的性能趨于平穩(wěn)，提升幅度較小。

4.2CMUPIE人臉庫

本文采用卡耐基梅隆大學(xué)的PIE人臉庫，PIE是姿態(tài)（Pose）、光照（Illum ination）和表情（Expression）的縮寫。CMU PIE人臉庫建立于2000年11月，它來自68個人的40 000張照片，其中包括了每個人的13種姿態(tài)條件、43種光照條件和4種表情下的照片。隨機從每個個體集合中選取l(l=5,10,20,30)，選擇60%樣本作為訓(xùn)練集，其余的40%作為測試集。

各算法在PIE數(shù)據(jù)集上的實驗結(jié)果在表3、表4和圖4中給出。表3給出了各算法作用在PIE數(shù)據(jù)集上的最佳識別率和耗費時間。表4給出了各算法作用在PIE數(shù)據(jù)集上的最優(yōu)識別結(jié)果（包括平均識別率及其對應(yīng)的標(biāo)準(zhǔn)差），括號內(nèi)的值是相應(yīng)算法取得最好值時的判別子空間的維度。圖4出了PIE數(shù)據(jù)集隨機選取l=5和l=20時各算法隨維度增加的識別率。

Table3 Optimalaccuracy and cost timeofallmethodson PIE database表3 PIE數(shù)據(jù)集上各算法最佳識別率和耗費時間

Table 4 Average accuracy,mean variance and optimalembedded dimension of allmethodson PIE database表4 PIE數(shù)據(jù)集上各算法平均識別率、均方差和最優(yōu)嵌入維數(shù)

Fig.4 Accuracy of allmethodsvs.dimension on PIE database圖4 各算法在PIE數(shù)據(jù)集上隨維度增加的識別率

從表3、表4以及圖4中可以看到：

（1）相對于上面的ORL數(shù)據(jù)庫而言，PIE數(shù)據(jù)庫較為復(fù)雜。當(dāng)l值較小也就是訓(xùn)練樣本較少時，PCA、DNE和MFA算法性能不是特別理想，隨著l的增加，MFA算法性能有較大的提升?？偟膩碚f，對于PIE數(shù)據(jù)集上的每個l，NTL算法與原來的DNE算法相比，最佳算法識別率最高提升了62.6%(l=5)，最低提升了31.9%(l=30)，平均提升了51.3%。NTL算法的性能比PCA、MFA和DNE算法好，NTL算法略好于TSA算法。因為張量表示的數(shù)據(jù)最大限度地保留了數(shù)據(jù)內(nèi)在的結(jié)構(gòu)，同時面向張量表示數(shù)據(jù)的算法克服了維數(shù)災(zāi)難、小樣本等問題，所以與面向向量表示數(shù)據(jù)的PCA、MFA和DNE算法相比，NTL和TSA算法能更好地保留數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，獲得數(shù)據(jù)更好的低維表示，從而取得較好的識別性能。

（2）從表3中可以看出，NTL算法耗費的時間遠(yuǎn)遠(yuǎn)小于傳統(tǒng)的PCA、MFA和DNE算法，識別率卻高于這些算法。NTL算法的耗費和TSA相當(dāng)，識別率略高于TSA算法。和運行在ORL數(shù)據(jù)庫的結(jié)果相比，NTL算法的時間耗費大大降低，原因可能是PIE數(shù)據(jù)庫相對更大更復(fù)雜，NTL作為面向張量數(shù)據(jù)的算法，極大限度地關(guān)注數(shù)據(jù)內(nèi)在的結(jié)構(gòu)，在處理大數(shù)據(jù)上具有更強的能力。所有算法都運行在IntelCore i5-2520M 2.50 GHz，8 GB內(nèi)存的個人電腦上，使用Matlab7.0編程實現(xiàn)。

（3）對于PIE數(shù)據(jù)集上的每個l，NTL算法的最好性能在較低維就能達(dá)到。在維數(shù)較低的時候，NTL算法的平均識別率隨著張量子空間維數(shù)的增加迅速提升。當(dāng)張量子空間的維數(shù)達(dá)到一定的數(shù)值時，NTL算法的性能趨于平穩(wěn)，提升幅度較小。

4.3 各算法性能隨著訓(xùn)練數(shù)據(jù)增加的變化情況

一個好的分類算法應(yīng)當(dāng)隨著訓(xùn)練數(shù)據(jù)的增加，其分類精度也相應(yīng)增加。本實驗在哥倫比亞圖像數(shù)據(jù)庫COIL20上驗證本文算法的有效性。哥倫比亞圖像數(shù)據(jù)庫包含20個對象，每個對象在水平上旋轉(zhuǎn)360°，每隔5°拍攝一張照片，因此每個對象共72幅圖，一共1 440幅圖片。實驗中按照5∶95，1∶9，2∶8，3∶7和4∶6的比例隨機抽取訓(xùn)練樣本集和測試樣本集，實驗進(jìn)行20次，實驗結(jié)果為其平均值。圖5給出了訓(xùn)練樣本和測試樣本比例為5∶95，1∶9，2∶8以及3∶7時各算法隨緯度增加的識別率。圖6給出了各算法的最佳識別率隨著訓(xùn)練樣本和測試樣本比率遞增的實驗結(jié)果。

從圖5中可以看出，當(dāng)訓(xùn)練樣本數(shù)與測試樣本數(shù)的比率較小時（如二者的比率為5∶95時），這些算法的性能有較大的差距。MFA算法的性能相對較差，其次是PCA和DNE算法，這3個算法都是面向向量的算法；然后是TSA算法，NTL算法性能最好，這兩種算法都是面向張量的算法。這說明即使當(dāng)訓(xùn)練樣本數(shù)較少時，面向張量的算法因為保持著數(shù)據(jù)的內(nèi)部幾何結(jié)構(gòu)性質(zhì)，所以能在低維空間更好地表征原始數(shù)據(jù)。因此在訓(xùn)練樣本數(shù)據(jù)較少時，張量表示的學(xué)習(xí)方法相對于傳統(tǒng)的面向向量的學(xué)習(xí)方法在性能上更具有優(yōu)勢。隨著訓(xùn)練樣本數(shù)和測試樣本數(shù)比率的提升（如二者的比率是3∶7時），這幾種算法的性能幾乎相當(dāng)。從圖6中可以看出，隨著訓(xùn)練數(shù)據(jù)的增加，各算法的性能都得到了不同程度的提升。除此之外，還可以看出NTL算法的性能始終要優(yōu)于PCA、MFA、DNE和TSA算法。

Fig.5 Accuracy of allmethodsvs.dimension on COIL20 database圖5 各算法在COIL20數(shù)據(jù)集上識別率隨維度增加的變化情況

Fig.6 Accuracy of allmethodsvs.ratio of training samplesand testing sampleson COIL20 database圖6 各算法在COIL20數(shù)據(jù)集上識別率隨訓(xùn)練樣本和測試樣本比率增加的變化情況

5 結(jié)論和展望

本文在改進(jìn)的判別鄰域嵌入（DNE）方法的基礎(chǔ)上提出了新的面向張量數(shù)據(jù)的鄰域嵌入的張量學(xué)習(xí)（NTL）方法。由于傳統(tǒng)的機器學(xué)習(xí)算法把數(shù)據(jù)表示成向量的形式進(jìn)行處理，現(xiàn)實世界以張量形式存在的諸多數(shù)據(jù)如圖像、視頻數(shù)據(jù)，如果被強制轉(zhuǎn)換成向量表示，不僅會產(chǎn)生維數(shù)災(zāi)難和小樣本問題，而且會破壞數(shù)據(jù)本身的內(nèi)部空間排列結(jié)構(gòu)，不利于發(fā)現(xiàn)數(shù)據(jù)好的低維表示。除此之外，DNE算法只是利用了數(shù)據(jù)之間的鄰域關(guān)系，卻忽略了非鄰域關(guān)系對算法判別性能的影響。本文提出的NTL算法面向張量數(shù)據(jù)，解決了DNE算法存在的上述問題，通過實驗也驗證了NTL算法不僅提升了識別率，而且還提高了算法學(xué)習(xí)的效率，在處理更為復(fù)雜的數(shù)據(jù)上，NTL算法具有更強的能力。

[1]Batur A U,Hayes IIIM H.Linear subspaces for illumination robust face recognition[C]//Proceedings of the 2001 Conference on Computer Vision and Pattern Recognition,Kauai,USA,Dec 8-14,2001.Washington:IEEEComputer Society,2001:296-301.

[2]Belhumeur PN,Hespanha JP,Kriegman D J.Eigenfaces vs.fisherfaces:recognition using class specific linear projection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,19(7):711-720.

[3]Belkin M,NiyogiP.Laplacian eigenmaps and spectral techniques for embedding and clustering[C]//Proceedings of the 14th International Conference on Neural Information Processing Systems:Natural and Synthetic,Vancouver,Canada,Dec 3-8,2001.Cambridge,USA:M ITPress,2001:585-591.

[4]CaiDeng,He Xiaofei,Han Jiawei.SRDA:an efficientalgorithm for large-scale discrim inant analysis[J].IEEE Transactions on Know ledge and Data Engineering,2008,20(1):1-12.

[5]CaiDeng,He Xiaofei,Han Jiawei,etal.Orthogonal Laplacianfaces for face recognition[J].IEEETransactions on Image Processing,2006,15(11):3608-3814.

[6]He Ran,Zheng Weishi,Hu Baogang,et al.Nonnegative sparse coding for discriminative sem i-supervised learning[C]//Proceedings of the 2011 Conference on Computer Vision and Pattern Recognition,Colorado Springs,USA,Jun 20-25,2011.Washington:IEEEComputer Society,2011:2849-2856.

[7]Levin A,Shashua A.Principal component analysis over continuous subspaces and intersection of half-spaces[C]//LNCS 2352:Proceedings of the 7th European Conference on Computer Vision,Copenhagen,May 28-31,2002.Berlin,Heidelberg:Springer,2002:635-650.

[8]Li Ping,Bu Jiajun,Yang Yi,etal.Discriminative orthogonal nonnegative matrix factorization w ith flexibility for data representation[J].Expert Systems w ith Applications,2014,41(4):1283-1293.

[9]LiWei,Prasad S,Fow ler JE,et al.Locality-preserving dimensionality reduction and classification for hyperspectral image analysis[J].IEEE Transactions on Geoscience and Remote Sensing,2012,50(4):1185-1198.

[10]He Xiaofei,Niyogi P.Locality preserving projections[C]//Advances in Neural Information Processing Systems 16,Vancouver,Canada,Dec 8-13,2003.Cambridge,USA:MIT Press,2003:153-160.

[11]Shi Jun,Jiang Qikun,Zhang Qi,etal.Sparse kernelentropy componentanalysis for dimensionality reduction of biomedicaldata[J].Neurocomputing,2015,168(C):930-940.

[12]CaiDeng,He Xiaofei,Han Jiawei.Document clustering using locality preserving indexing[J].IEEE Transactions on Know ledgeand Data Engineering,2005,17(12):1624-1637.

[13]Yan Shuicheng,Xu Dong,Zhang Benyu,et al.Graph embedding and extension:a general framework for dimensionality reduction[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(1):40-51.

[14]Zhang Wei,Xue Xiangyang,Lu Hong,et al.Discrim inant neighborhood embedding for classification[J].Pattern Recognition,2006,39(11):2240-2243.

[15]Lu Mei,Zhao Xiangjun,Zhang Li,et al.Sem i-supervised concept factorization for document clustering[J].Information Sciences:an International Journal,2016,331(C):86-98.

[16]Yang Xibei,Qian Yuhua,Yang Jingyu.Hierarchical structures on multigranulation spaces[J].Journal of Computer Scienceand Technology,2012,27(6):1169-1183.

[17]Zhang Daoqiang,Zhou Zhihua,Chen Songcan.Semi-supervised dimensionality reduction[C]//Proceedings of the 7th SIAM International Conference on Data M ining,M inneapolis,M innesota,USA,Apr 26-28,2007.Philadelphia,USA:SIAM,2007:629-634.

[18]De Lathauwer L,Vandewalle J.Dimensionality reduction in higher-order signalprocessing and rank-(R1,R2,…,RN)reduction inmultilinearalgebra[J].LinearA lgebra and ItsApplications,2004,391(1):31-55.

[19]Hall A,Qu G,Sethi IK,Hartrick C.Tensor-based temporal behavior analysis in pain medicine[C]//Proceedings of the 11th International Conference on Machine Learning and Applications,Florida,USA,Dec 12-15,2012.Washington:IEEEComputer Society,2012:626-629.

[20]He Xiaofei,Cai Deng,Niyogi P.Tensor subspace analysis[C]//Advances in Neural Information Processing Systems 18,Vancouver,Canada,Dec 5-8,2005.Cambridge,USA:M ITPress,2005:499-506.

[21]Ye Jieping,Janardan R,LiQi.Two-dimensional linear discrim inantanalysis[C]//Advances in Neural Information Processing Systems 17,Vancouver,Canada,Dec 13-18,2004.Cambridge,USA:M ITPress,2004:1569-1576.

[22]Sun Jiantao,Zeng Huajun,Liu Huan,etal.CubeSVD:a novel approach to personalized Web search[C]//Proceedings of the 14th InternationalConference onWorldWideWeb,Chiba,Japan,May 10-14,2005.New York:ACM,2005:382-390.

[23]ShashuaA,ZassR,Hazan T.Multi-way clustering using supersymmetric non-negative tensor factorization[C]//LNCS 3954:Proceedings of the 9th European Conference on Computer Vision,Graz,Austria,May 7-13,2006.Berlin,Heidelberg:Springer,2006:595-608.

[24]Ishteva M,De Lathauwer L,Absil P,et al.Dimensionality reduction for higher-order tensors:algorithms and applications[J].International Journal of Pure and Applied Mathematics,2008,42(3):337-343.

[25]Chen Songcan,Zhu Yulian,Zhang Daoqiang,et al.Feature extraction approaches based on matrix pattern:MatPCA and MatFLDA[J].Pattern Recognition Letters,2005,26(8):1157-1167.

LU Meiwas born in 1976.She isa Ph.D.candidate at Soochow University.Her research interests includemachine learning,pattern recognition and artificial intelligence,etc.

路梅（1976—），女，江蘇徐州人，蘇州大學(xué)計算機科學(xué)與技術(shù)學(xué)院博士研究生，主要研究領(lǐng)域為機器學(xué)習(xí)，模式識別，人工智能等。

李凡長（1964—），男，云南宣威人，1995年于中國科技大學(xué)獲得碩士學(xué)位，現(xiàn)為蘇州大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域為人工智能，機器學(xué)習(xí)等。

Neighborhood-Embedded Tensor Learning*

LUMei1,2,LIFanzhang1+
1.Collegeof Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China
2.College of Computer Science and Technology,Jiangsu NormalUniversity,Xuzhou,Jiangsu 221116,China

Mostof traditionalmachine learning algorithms process vectorized data,while in realworld a lotof data exist in the form of tensor,such as images and video.If these tensor data are forced to be vectorized,the so called“curse of dimensionality”and“small sample size problem”w ill be encountered as well as the intrinsic structure w illbe destroyed.Thus,thegood lower dimensional representation of theoriginaldata can notbe captured.Discriminant neighborhood embedding(DNE)is a popular discrim inant analysismethod but based on vectorized data.To address this issue,this paper proposes a novel neighborhood-embedded tensor learning(NTL)which inherits the power of DNE.In addition,NTL overcomes another lim itation of DNE that it neglects the role of the points out of the neighborhood of a data point.By designing an objective function elaborately(three graphs are encoded in the object function:intraclass graph,interclass graph and other points association graph),NTLmaps the data into a low dimension subspacewhere the data in the same classw illbemore compactand the data in the differentclassw illbe more separable.The experimental results on three public data bases(ORL,PIE and COIL20)demonstrate thatNTL achievesbetter recognition rate,whilebeingmuchmore efficient.

discrim inant neighborhood embedding(DNE);tensor subspace analysis(TSA);dimensionality reduc-tion;discrim inantanalysis;tensor learning

g was born in 1964.He

the M.S.degree in computer science and technology from University of Science and Technology of China in 1995.Now he is a professor and Ph.D.supervisor at Soochow University.His research interests include artificial intelligence andmachine learning,etc.

A

：TP181

*The NationalNatural Science Foundation of ChinaunderGrantNos.61033013,61402207,61272297(國家自然科學(xué)基金).

Received 2016-05,Accepted 2016-07.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-07-14,http://www.cnki.net/kcms/detail/11.5602.TP.20160714.1616.004.htm l