基于特別的特征表示方法的局部線性KNN算法*

卞則康，王士同，王宇翔

1.江南大學(xué)數(shù)字媒體學(xué)院，江蘇無(wú)錫 214122

2.中國(guó)船舶科學(xué)研究中心，江蘇無(wú)錫 214082

1 引言

近年來(lái)，圖像特征提取和圖像分類一直是人臉識(shí)別中的研究熱點(diǎn)，特征表示方法的選取直接影響到人臉圖像分類的效果。為了解決這些問(wèn)題，提出了一些廣泛使用的特征提取算法，其中包括線性算法[1-3]和非線性算法[4-5]。此外，文獻(xiàn)[6]提出的基于稀疏表示的算法已經(jīng)成功應(yīng)用到人臉識(shí)別中，它解決了特征表示和分類之間的魯棒性問(wèn)題。該算法通過(guò)學(xué)習(xí)得到測(cè)試樣本的稀疏表示，并將之應(yīng)用到最小誤差分類器中進(jìn)行分類。對(duì)于圖像分類，提出了多種特征提取的算法[7-9]，這些算法通過(guò)利用標(biāo)簽信息來(lái)進(jìn)行判別字典的學(xué)習(xí)和稀疏表示。但是這些方法也導(dǎo)致了其他問(wèn)題，如分類的限制和計(jì)算的復(fù)雜性。

針對(duì)上述問(wèn)題，本文提出了一種新的局部線性K最近鄰算法（locally linearKnearest neighbor method），即L2KNN算法。L2KNN算法首先提出了一種特別的特征表示方法，即應(yīng)用重建、局部性和稀疏性的標(biāo)準(zhǔn)來(lái)表示每個(gè)測(cè)試數(shù)據(jù)。這種新的數(shù)據(jù)表示方法具有最近鄰集群效應(yīng)（clustering effect of nearest neighbors，CENN），它能夠增強(qiáng)與測(cè)試樣本相同類別的訓(xùn)練樣本的系數(shù)，增加相同類中訓(xùn)練樣本的相關(guān)性。然后將學(xué)習(xí)得到的特征表示應(yīng)用到圖像分類中，提出了一種新的分類器L2KNNc(L2KNN-based classifier）。

2 相關(guān)研究

基于局部特征稀疏編碼和基于全局特征編碼的特征表示方法是最常見(jiàn)的兩種特征表示方法，已經(jīng)廣泛應(yīng)用到目標(biāo)識(shí)別[6]、場(chǎng)景識(shí)別[9]和動(dòng)作識(shí)別[10-11]中。文獻(xiàn)[12]提出了一種使用稀疏編碼來(lái)學(xué)習(xí)字典和系數(shù)向量，從而表示圖像的局部特征的編碼學(xué)習(xí)算法。文獻(xiàn)[10]提出了一種帶局部約束的線性編碼方法，這種方法考慮到在特征編碼過(guò)程中的局部信息的約束。文獻(xiàn)[13]進(jìn)一步提出了一種Laplacian系數(shù)編碼的特征表示方法，這種方法充分考慮到局部特征之間的相似性和局部性。

文獻(xiàn)[6]提出了一種基于全局特征的稀疏編碼方法，提高了人臉識(shí)別的魯棒性，并且進(jìn)一步應(yīng)用到其他的識(shí)別應(yīng)用中，如目標(biāo)識(shí)別、場(chǎng)景識(shí)別和動(dòng)作識(shí)別。為了進(jìn)一步提高算法的性能，提出了一些改進(jìn)方法，如文獻(xiàn)[11]和文獻(xiàn)[14]在算法中考慮了字典的內(nèi)相變化。另一種改進(jìn)方法是通過(guò)對(duì)稀疏表示進(jìn)行學(xué)習(xí)得到一個(gè)判別字典。文獻(xiàn)[7]提出了一種判別奇異值分解方法（discriminative singular value decomposition，D-KSVD），文獻(xiàn)[8]通過(guò)引進(jìn)一個(gè)新的標(biāo)簽一致的正則化項(xiàng)對(duì)文獻(xiàn)[7]中的方法進(jìn)行改進(jìn)。文獻(xiàn)[15]提出了一種聯(lián)合字典的學(xué)習(xí)方法（joint dictionary learning，JDL），通過(guò)對(duì)全局共享的字典和每個(gè)類特有的子字典進(jìn)行學(xué)習(xí)得到聯(lián)合字典。文獻(xiàn)[9]提出了使用Fisher識(shí)別字典學(xué)習(xí)方法（Fisher discrimination dictionary learning，F(xiàn)DDL）來(lái)學(xué)習(xí)得到一個(gè)結(jié)構(gòu)化字典，這個(gè)結(jié)構(gòu)化字典中包含了一系列特定類的子字典。

相比之下，本文提出的L2KNN算法與上述使用判別字典的算法有以下不同：第一，L2KNN算法中不包含任何的判別項(xiàng)，主要著眼于建立特征表示的方法和其分類器之間的聯(lián)系，基于判別字典的方法沒(méi)有這種聯(lián)系。第二，本文算法不需要學(xué)習(xí)字典，避免了由于更新字典和稀疏系數(shù)帶來(lái)的時(shí)間消耗。第三，有些基于判別字典的算法需要對(duì)每一個(gè)類的子字典進(jìn)行學(xué)習(xí)，如果每一個(gè)類的訓(xùn)練樣本量較低，會(huì)影響算法的性能，而本文算法不需要對(duì)子字典進(jìn)行學(xué)習(xí)。第四，有些基于判別字典的算法在其目標(biāo)函數(shù)中包含線性分類器，這就排除了其他性能較好的非線性分類器，本文算法通過(guò)建立新的分類器來(lái)改善算法的分類性能，并且提高分類器的泛化性能。

3 算法描述

3.1 L2KNN算法

L2KNN算法首先提出了一種特別的特征表示方法，它表示一個(gè)測(cè)試樣本是所有訓(xùn)練樣本的線性組合，如果測(cè)試樣本和訓(xùn)練樣本屬于同一個(gè)類，則其相應(yīng)的系數(shù)約束為非零，否則為零。具體方法如下：

假設(shè)給定m個(gè)訓(xùn)練樣本bi∈Rn(i=1,2,…,m)，對(duì)于一個(gè)測(cè)試樣本x∈Rn，訓(xùn)練樣本和測(cè)試樣本均用?2范式進(jìn)行歸一化，相關(guān)系數(shù)向量v=[v1,v2,…,vm]T∈Rm,則測(cè)試樣本可以定義為：

其中，vi的定義如下：

上述特別的表示方法是一種高度的稀疏表示方法，即傳統(tǒng)的基于稀疏表示的方法[6]。傳統(tǒng)的基于稀疏表示的方法具有以下優(yōu)點(diǎn)：第一，通過(guò)稀疏表示的方法構(gòu)建的模型較直觀，容易被理解和操作。第二，基于稀疏表示的方法對(duì)目標(biāo)圖像的識(shí)別是通過(guò)圖像的整體方面來(lái)把握的，通過(guò)對(duì)所有的訓(xùn)練樣本進(jìn)行訓(xùn)練，得到一個(gè)相關(guān)系數(shù)，并依據(jù)相關(guān)系數(shù)進(jìn)行分類識(shí)別。第三，在高維空間中，基于稀疏表示的特征表示方法受到特征提取的個(gè)數(shù)的限制較小，對(duì)圖像的識(shí)別率較高。

基于上述特別的特征表示方法的算法與傳統(tǒng)的基于稀疏表示的算法有以下不同：

（1）與測(cè)試樣本同類的訓(xùn)練樣本之間往往是高度相關(guān)的，傳統(tǒng)的稀疏表示的方法傾向于求出其中一個(gè)訓(xùn)練樣本非零系數(shù)[16]，而特別的特征表示方法是求出一組訓(xùn)練樣本的非零系數(shù)。

（2）基于特別的特征表示算法具有最近鄰集群效應(yīng)，加強(qiáng)了同類數(shù)據(jù)間的相關(guān)性。

（3）基于特別的特征表示算法的分類器的泛化性能較高。

為了解決上述的問(wèn)題，在文獻(xiàn)[17]的啟發(fā)下，本文提出了L2KNN算法，算法的目標(biāo)函數(shù)定義如下：

其中，x∈Rn表示測(cè)試樣本中的一個(gè)測(cè)試樣本；B=[b1,b2,…,bm]∈Rn×m表示所有的訓(xùn)練樣本；v∈Rm是基于上述特別的特征表示方法下的相關(guān)系數(shù)向量。向量d=[d1,d2,…,dm]T∈Rm表示測(cè)試樣本和每一個(gè)訓(xùn)練樣本之間的距離度量，具體的定義公式如下：

式（3）第一部分定義了重構(gòu)標(biāo)準(zhǔn)，第二部分通過(guò)使用l1范數(shù)的魯棒性定義了稀疏標(biāo)準(zhǔn)，第三部分維持相關(guān)系數(shù)和距離度量之間的局部屬性。3個(gè)參數(shù)λ、α和β調(diào)節(jié)不同部分的比重。

本文提出的L2KNN算法顯示了最鄰近分組效應(yīng)CENN，具體定義和證明如下：從CENN中可以看出，如果訓(xùn)練樣本與測(cè)試樣本高度相關(guān)并且接近，則訓(xùn)練樣本會(huì)獲得相似和大的相關(guān)系數(shù)，因此這些訓(xùn)練樣本很有可能與測(cè)試樣本屬于同一類。L2KNN算法傾向于用相似且較大的相關(guān)系數(shù)來(lái)表示與測(cè)試樣本屬于同一類的訓(xùn)練樣本，這與上文提出的特別的特征表示方法的情況一致。

定義1最近鄰集群效應(yīng)CENN[17]：假設(shè)v=[v1,v2,…,vm]T是目標(biāo)函數(shù)（3）的最優(yōu)解，令ρ=biTbj(i,j=1,2,…,m)表示樣本bi和bj之間的相關(guān)系數(shù)。如果vi和vj的符號(hào)一致，則CENN可以表示為：

因?yàn)樗械膶?shí)驗(yàn)樣本都是經(jīng)過(guò)?2范式進(jìn)行歸一化，C是一個(gè)常數(shù)。

證明首先，式（3）等價(jià)于：

v=[v1,v2,…,vm]T是符合特別的特征表示的相關(guān)系數(shù)向量，因此分別對(duì)vi和vj求偏導(dǎo)，得出如下公式：

因?yàn)関i和vj的符號(hào)一致，所以sign(vi)=sign(vj)，將式（7）中兩個(gè)公式相減得：

對(duì)式（8）兩邊取絕對(duì)值，并且F(v)≤F(0),‖x‖2=1,得：

最近鄰集群效應(yīng)CENN表明，如果兩個(gè)訓(xùn)練樣本之間有一個(gè)很高的相關(guān)性，即ρ≈1，并且與測(cè)試樣本很接近（di≈dj，并且di、dj的數(shù)值也很大），則這兩個(gè)樣本的相關(guān)系數(shù)也相似，即vi≈vj。這正符合本文提出的特征表示方法的思想。

因此，本文提出的L2KNN算法不僅具有其他稀疏表示的優(yōu)點(diǎn)，并且還具有最近鄰集群效應(yīng)，對(duì)后續(xù)的分類步驟有很大的幫助。

3.2 算法求解

對(duì)于求解L2KNN算法，主要是優(yōu)化公式（3），求解式（3）的過(guò)程實(shí)質(zhì)上是一個(gè)正則化優(yōu)化的過(guò)程，對(duì)于大多數(shù)的正則化求解，一般采用的是快速迭代閾值下降法（fast iterative shrinkage thresholding algorithm，ISTA）[18]。從式（3）的形式上看，其正則化包含了兩部分：一個(gè)?1正則化問(wèn)題和一個(gè)?2正則化問(wèn)題。第一部分體現(xiàn)了稀疏性，如同LASSO算法（least absolute shrinkage and selection operator）[19]；第二部分體現(xiàn)了系數(shù)之間的相關(guān)性。因此，式（3）可以使得相關(guān)性較高的特征集中在一起。借鑒文獻(xiàn)[17]的求解方法，對(duì)式（3）的變換如下表示：

利用?2范式的性質(zhì)，式（10）可以變化為：

進(jìn)一步轉(zhuǎn)化為：

令：

則目標(biāo)函數(shù)轉(zhuǎn)化為帶?1正則化的LASSO型的目標(biāo)函數(shù)：

經(jīng)過(guò)一系列的變換，將式（10）優(yōu)化問(wèn)題轉(zhuǎn)化成式（14）的優(yōu)化問(wèn)題。對(duì)于式（14）的優(yōu)化求解，本文采用的是FISTA算法，具體的算法步驟詳見(jiàn)文獻(xiàn)[18]。

解決帶?1正則化的LASSO型目標(biāo)函數(shù)可以表示為：

對(duì)于式（15）的求解，采用FISTA算法，其主要步驟如下：

算法1FISTA算法

輸入：Lf=2×λmax(ATA),λ,其中λmax()表示最大特征值

初始化：y1=x0∈Rn,t1=1

Stepk(k＞0)：計(jì)算

直至滿足停止條件

輸出：x

應(yīng)用FISTA算法的求解LASSO算法，提高了算法的運(yùn)算速率，時(shí)間復(fù)雜度為O(1/k2)。

因此L2KNN算法的求解步驟如下：

算法2L2KNN算法

輸入：訓(xùn)練數(shù)據(jù)集B∈Rn×m，測(cè)試數(shù)據(jù)集X∈Rn×N

實(shí)驗(yàn)參數(shù)：λ、α、β、δ

1.使用式（4）計(jì)算出d。

2.根據(jù)式（13）構(gòu)造出新的B′、x′、λ′。

3.應(yīng)用算法1中的FISTA算法求解式（14）。

輸出相關(guān)系數(shù)矩陣：V∈Rm×N

3.3 L2KNNc分類器

通過(guò)上述所示的算法求出相關(guān)系數(shù)向量v，對(duì)于測(cè)試樣本x進(jìn)行分類，使用如下的分類器：

其中，c表示樣本中的總類別數(shù)；Bc表示第c類的訓(xùn)練樣本集合。L2KNNc分類器對(duì)測(cè)試數(shù)據(jù)進(jìn)行分類，是計(jì)算每一個(gè)類別中的訓(xùn)練樣本的相關(guān)系數(shù)的和，通過(guò)比較每個(gè)類別相關(guān)系數(shù)和的大小決定測(cè)試數(shù)據(jù)屬于哪一個(gè)類別。如圖1所示。

Fig.1 L2KNNcclassifier圖1 L2KNNc分類器

圖1顯示有4個(gè)訓(xùn)練樣本b1、b2、b3、b4，它們的標(biāo)簽分別是1、1、2、2。訓(xùn)練樣本對(duì)于測(cè)試樣本x的系數(shù)向量為v=[0.2,0.4,0.3,0.1]T，分類器通過(guò)比較s1＞s2，判定測(cè)試樣本x屬于1類。

但是值得注意的是，當(dāng)有的訓(xùn)練樣本中混入了一些噪聲，使得同一類中一些訓(xùn)練樣本遠(yuǎn)離測(cè)試樣本，這樣它的系數(shù)就成為拖尾系數(shù)，由式（16）定義的L2KNNc分類器的泛化性能會(huì)有所下降。在實(shí)際應(yīng)用中，同一類中不是所有的訓(xùn)練樣本都需要，一些受到噪聲影響的樣本所帶有的拖尾系數(shù)反而降低了分類性能。因此，為了提高L2KNNc分類器的泛化性能，使用系數(shù)截?cái)嘁蕴岣咚惴ǖ男阅?，在分類過(guò)程中只需要每一類中前k個(gè)最大的vi系數(shù)，用前k個(gè)系數(shù)的和作為判斷依據(jù)，具體如下：

這里，T(k)表示每一類中前k個(gè)最大的系數(shù)集合。在實(shí)際應(yīng)用中，參數(shù)k的設(shè)置對(duì)算法的分類性能有重要的影響。

3.4 時(shí)間復(fù)雜度分析

本文提出的L2KNN算法的時(shí)間消耗主要集中在算法2中第1、第3步。對(duì)于每一個(gè)n維的測(cè)試樣本，第1步需要分別計(jì)算出與m個(gè)訓(xùn)練樣本的距離度量，則算法2中第1步的時(shí)間復(fù)雜度為O(mn)。在應(yīng)用FISTA算法求解過(guò)程中，F(xiàn)ISTA算法收斂的時(shí)間復(fù)雜度為O(1/k2)，k表示迭代的總次數(shù)，在每次迭代中，求解梯度的時(shí)間復(fù)雜度為O(mn)，則算法2中第3步的時(shí)間復(fù)雜度為O(mn/k2)。則運(yùn)行一次L2KNN算法的時(shí)間復(fù)雜度為O((mn/k2)+mn)。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)設(shè)置

為了測(cè)試本文算法的分類性能，在人臉數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，一共4個(gè)人臉數(shù)據(jù)集，分別是AR Face[20]、Extended Yale Face B[21]、ORL Face[22]和 PIE[23]。為了檢測(cè)本文算法的分類性能，一共選取了3種對(duì)比算法，分別是SRC、FDDL[9]、LASSO[19]算法。分別比較本文算法與3種對(duì)比算法在不同數(shù)據(jù)集上的分類準(zhǔn)確率和標(biāo)準(zhǔn)差。

本文提出的L2KNN算法存在4個(gè)參數(shù)λ、α、β和δ。因?yàn)閿?shù)據(jù)集的不同，所以每個(gè)數(shù)據(jù)集的參數(shù)的取值也不一樣。因此對(duì)于每一個(gè)數(shù)據(jù)集，本文需要進(jìn)行尋參操作，選取最佳的實(shí)驗(yàn)參數(shù)。其中參數(shù)α、λ、δ的取值范圍可以表示為{0.001,0.005,0.010,0.020,0.050,0.100},β為{1,2,3,4,5,6}。通過(guò)對(duì)前一個(gè)集合中隨機(jī)抽取3個(gè)數(shù)（可重復(fù)抽?。┙M合作為參數(shù)α、λ、δ的值，可以組成36組，再?gòu)牡诙€(gè)集合中抽取一個(gè)數(shù)作為β的值，則一共有36×6組的參數(shù)組合。對(duì)于每一個(gè)數(shù)據(jù)集，需要用本文算法對(duì)這36×6組的參數(shù)組合進(jìn)行實(shí)驗(yàn)，通過(guò)實(shí)驗(yàn)結(jié)果選取正確率最高的參數(shù)組合，這個(gè)過(guò)程便是本文的尋參操作。通過(guò)尋參操作確定的參數(shù)組合將是后續(xù)對(duì)比實(shí)驗(yàn)中本文算法的參數(shù)值。

本文的實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)選擇算法的分類準(zhǔn)確率和標(biāo)準(zhǔn)差，其中分類標(biāo)準(zhǔn)差表明算法的穩(wěn)定性。為了比較算法的運(yùn)行速率，本文實(shí)驗(yàn)選擇的比較標(biāo)準(zhǔn)是單個(gè)樣本的運(yùn)行時(shí)間，即算法運(yùn)行一次的總時(shí)間除以測(cè)試樣本的總數(shù)，這是一個(gè)平均時(shí)間。

為了檢測(cè)算法的最近鄰集群效應(yīng)，本文借鑒文獻(xiàn)[17]中的兩種評(píng)價(jià)方法，即正確激活率（true accept rate，TAR）和假激活率（false accept rate，F(xiàn)AR），具體定義如下：

其中，Nt表示測(cè)試樣本的數(shù)量；c表示樣本的類別總量；ti表示第i個(gè)測(cè)試樣本中非零相關(guān)系數(shù)所對(duì)應(yīng)的訓(xùn)練樣本中與第i個(gè)測(cè)試樣本屬于同一類的訓(xùn)練樣本個(gè)數(shù)；fi表示與第i個(gè)測(cè)試樣本同屬一類的訓(xùn)練樣本中相關(guān)系數(shù)為0的樣本的個(gè)數(shù)。

4.2 實(shí)驗(yàn)結(jié)果與分析

4.2.1 Extended Yale Face B數(shù)據(jù)集

本小節(jié)實(shí)驗(yàn)選取的是Extended Yale Face B數(shù)據(jù)集，本文使用的是一種常用的裁剪版本[25]，所有的圖像經(jīng)過(guò)手動(dòng)對(duì)齊、裁剪，然后調(diào)整大小為168×192像素。本次實(shí)驗(yàn)的訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)的選取規(guī)則如下：每次實(shí)驗(yàn)，對(duì)于每一類，隨機(jī)選取其中的20幅圖像作為訓(xùn)練集，余下的圖像作為測(cè)試集。圖像數(shù)據(jù)在使用之前要使用PCA（principal component analysis）降維方法將圖像數(shù)據(jù)的維度降至300維。經(jīng)過(guò)參數(shù)尋優(yōu)后，本次實(shí)驗(yàn)中L2KNN算法的實(shí)驗(yàn)參數(shù)設(shè)置如下：δ=0.1,λ=0.01,α=0.005,β=5，設(shè)置L2KNNc分類器的參數(shù)k=6。實(shí)驗(yàn)一共運(yùn)行10次，實(shí)驗(yàn)結(jié)果取平均值，如表1所示。

Table 1 Results of experiment onYale Bdatabase表1 Yale B數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表1是各算法的實(shí)驗(yàn)準(zhǔn)確率和標(biāo)準(zhǔn)差。實(shí)驗(yàn)數(shù)據(jù)表明，本文提出的L2KNN算法相比其他3種經(jīng)典的算法具有很好的分類性能。相比兩種經(jīng)典的基于字典學(xué)習(xí)判別的算法，本文算法具有較好的準(zhǔn)確率，相比FDDL算法具有一定的穩(wěn)定性，相比SRC算法準(zhǔn)確率較高。本文算法在計(jì)算過(guò)程中避免了更新字典所帶來(lái)的時(shí)間消耗，因此本文算法在運(yùn)行時(shí)間消耗上小于這兩種算法。相比傳統(tǒng)的LASSO算法，L2KNN算法加入了最近鄰集群項(xiàng)，提高了算法的分類性能，并使用系數(shù)截取的方式增強(qiáng)了分類器的泛化性能，提高了算法的分類性能和穩(wěn)定性。

4.2.2 AR Face數(shù)據(jù)集

本次實(shí)驗(yàn)選用的數(shù)據(jù)集是人臉識(shí)別中常用的AR Face數(shù)據(jù)集，此數(shù)據(jù)集一共包含126個(gè)人臉的圖像。本文選用其中一種常用的數(shù)據(jù)子集，50名男性和50名女性的圖像構(gòu)成一個(gè)新的數(shù)據(jù)集，這些圖像被統(tǒng)一縮放到165×120像素，此數(shù)據(jù)集是本次的實(shí)驗(yàn)數(shù)據(jù)集。對(duì)于本次實(shí)驗(yàn)的訓(xùn)練集和測(cè)試集的構(gòu)造方法如下：對(duì)于每一類的圖像，AR數(shù)據(jù)集隨機(jī)抽取10張作為訓(xùn)練數(shù)據(jù)集，余下的作為測(cè)試數(shù)據(jù)集。數(shù)據(jù)在使用之前將圖像向量的維度用PCA降維到200維。經(jīng)過(guò)參數(shù)尋優(yōu)后，L2KNN算法的實(shí)驗(yàn)參數(shù)設(shè)置如下：δ=0.01,λ=0.01,α=0.01,β=5。設(shè)置L2KNNc分類器的參數(shù)k=5。實(shí)驗(yàn)一共運(yùn)行10次，實(shí)驗(yàn)結(jié)果取平均值，如表2所示。

Table 2 Results of experiment onAR database表2 AR數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表2的實(shí)驗(yàn)結(jié)果表明，本文提出的L2KNN算法的運(yùn)行效率比常用的基于字典判別的算法SRC、FDDL的運(yùn)行效率高，相比于經(jīng)典的LASSO算法，本文算法的運(yùn)行效率大致相當(dāng)。在算法的分類準(zhǔn)確率方面，L2KNN算法具有比其他3種算法高的分類性能。相比于4.2.1小節(jié)中的實(shí)驗(yàn)設(shè)置，對(duì)每一類訓(xùn)練樣本選取的數(shù)量減少，因此基于字典判別的算法的分類準(zhǔn)確率下降較快。本文算法直接建立特征表示與分類器之間的聯(lián)系，因此分類性能基本上沒(méi)受影響，并且分類性能和穩(wěn)定性比SRC、FDDL算法好。L2KNN算法相比LASSO算法，增加了最近鄰集群的性能，在訓(xùn)練樣本減少的情況下，分類性能沒(méi)受太大的影響。

4.2.3 ORL Face數(shù)據(jù)集和PIE數(shù)據(jù)集

為了進(jìn)一步研究算法的分類性能。本次實(shí)驗(yàn)選擇ORL Face數(shù)據(jù)集和PIE數(shù)據(jù)集。ORL數(shù)據(jù)集含有40個(gè)不同的目標(biāo)，每個(gè)目標(biāo)含有10張圖像，是一個(gè)較小的數(shù)據(jù)集。PIE數(shù)據(jù)集是一個(gè)較大的人臉數(shù)據(jù)庫(kù)，本文選用其中的一個(gè)子集作為本次實(shí)驗(yàn)的數(shù)據(jù)集，即共有68個(gè)不同的人臉數(shù)據(jù)，每個(gè)人選取170張圖像。對(duì)于ORL數(shù)據(jù)集先縮放至64×64像素，再使用PCA降維至100維；對(duì)于PIE數(shù)據(jù)集縮放至32×32像素，再使用PCA降維至200維。每個(gè)數(shù)據(jù)集運(yùn)行10次，實(shí)驗(yàn)結(jié)果取均值。

對(duì)于數(shù)據(jù)集ORL，每一類中隨機(jī)選取3張圖像作為訓(xùn)練集，余下的7張作為測(cè)試集。實(shí)驗(yàn)的參數(shù)設(shè)置為：δ=0.01,λ=0.01,α=0.005,β=5。對(duì)于L2KNNc分類器設(shè)置k=2。實(shí)驗(yàn)結(jié)果如表3所示。

Table 3 Results of experiment onORLdatabase表3 ORL數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

對(duì)于數(shù)據(jù)集PIE，每一類中隨機(jī)選取15張圖像作為訓(xùn)練集，余下的155張作為測(cè)試集。實(shí)驗(yàn)的參數(shù)設(shè)置為：δ=0.01,λ=0.02,α=0.01,β=6。對(duì)于L2KNNc分類器設(shè)置k=10。實(shí)驗(yàn)結(jié)果如表4所示。

Table 4 Results of experiment onPIEdatabase表4 PIE數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表3和表4的實(shí)驗(yàn)結(jié)果顯示，在較小數(shù)據(jù)集中，因?yàn)橛?xùn)練樣本較少，所以算法的分類性能都出現(xiàn)了一定程度的下降。在較大的數(shù)據(jù)集中，由于在每一類中選取的訓(xùn)練樣本相對(duì)樣本的總量較少，不能有效地學(xué)習(xí)出有用信息，從而影響到算法的分類性能。實(shí)驗(yàn)結(jié)果表明，在較大的和較小的數(shù)據(jù)集中，本文提出的L2KNN算法具有較好的分類性能，運(yùn)行時(shí)間較少，算法的性能比較穩(wěn)定。

4.2.4 最近鄰集群效應(yīng)的有效性和算法的泛化性能

最近鄰集群效應(yīng)是本文提出的L2KNN算法的重要理論依據(jù)。為了評(píng)估CENN對(duì)于L2KNN算法的影響，通過(guò)設(shè)置不同的實(shí)驗(yàn)參數(shù)λ、α、β，比較分類準(zhǔn)確率、正確激活率（TAR）和假激活率（FAR）的數(shù)值變化。TAR和FAR的具體含義，以Extended Yale Face B數(shù)據(jù)集為例，其中一個(gè)類a的訓(xùn)練樣本個(gè)數(shù)是20個(gè)，如果測(cè)試樣本與訓(xùn)練樣本同屬于a類，則TAR的最理想值為20，即a的訓(xùn)練樣本的數(shù)量，則FAR的理想值為0。實(shí)驗(yàn)結(jié)果如表5所示。

Table 5 Results of experiment on Yale B database表5 Yale B數(shù)據(jù)集的實(shí)驗(yàn)指標(biāo)

表5的實(shí)驗(yàn)結(jié)果表明，在相同的λ、β下，隨著α的增大，算法的分類準(zhǔn)確率在增加，算法的TAR值在增加，F(xiàn)AR值在減小。這意味著，算法的集群效應(yīng)在增加，算法的分類性能在提高，對(duì)于樣本而言，正確激活的數(shù)量在增多，錯(cuò)誤激活的數(shù)量在減少。同樣的，在相同的λ、α下，隨著β的增加，也會(huì)出現(xiàn)相同的效果。從表5的實(shí)驗(yàn)結(jié)果中還可以看出，當(dāng)α、β一定的情況下，隨著λ的增加，抑制了集群效應(yīng)，使得算法的準(zhǔn)確率在下降，TAR在下降，F(xiàn)AR在上升。

為了提高本文算法的泛化性能，本文使用系數(shù)截?cái)嗟姆椒?，選取系數(shù)前k個(gè)最大的系數(shù)作為分類器的分類標(biāo)準(zhǔn)。為了測(cè)試k值對(duì)于L2KNNc分類的影響，本次實(shí)驗(yàn)選取Extended Yale Face B數(shù)據(jù)集，實(shí)驗(yàn)數(shù)據(jù)的設(shè)置如4.2.1小節(jié)，對(duì)于AR Face數(shù)據(jù)集，實(shí)驗(yàn)參數(shù)的設(shè)置如4.2.2小節(jié)。實(shí)驗(yàn)結(jié)果如圖2和圖3所示。

從圖2和圖3的實(shí)驗(yàn)結(jié)果中可以看出，k值的改變能夠影響算法的分類效果。隨著k值的增加，算法的分類準(zhǔn)確率也在增加，但是到達(dá)一個(gè)最大值之后，隨著k值的增加，算法的性能不會(huì)增加，甚至出現(xiàn)降低。因此，系數(shù)截?cái)嗟姆椒梢詠G棄一些“較遠(yuǎn)”的數(shù)據(jù)影響，有效地增加算法分類性能，提高算法的泛化性能。圖2和圖3的實(shí)驗(yàn)結(jié)果證明，選擇一個(gè)合適的k值對(duì)算法的分類性能具有重要的影響。

Fig.2 Accuracy ofL2KNNcbased on Yale Bdatabase for differentk圖2 對(duì)不同k取值L2KNNc分類器在Yale B數(shù)據(jù)集上的準(zhǔn)確率

Fig.3 Accuracy ofL2KNNcbased on ARdatabase for differentk圖3 對(duì)不同k取值L2KNNc分類器在AR數(shù)據(jù)集上的準(zhǔn)確率

5 結(jié)束語(yǔ)

本文提出了一種基于特別的特征表示方法的局部線性KNN分類算法(L2KNN算法)，并將之應(yīng)用到人臉識(shí)別中。在L2KNN算法中提出了一種特別的特征表示方法，其具有最近鄰集群效應(yīng)，增加了同類數(shù)據(jù)之間的相關(guān)性。使用系數(shù)截?cái)嗟姆椒ㄔ黾恿朔诸惼鱈2KNNc的泛化性能，進(jìn)一步提升了算法的分類性能。本文使用FISTA算法優(yōu)化目標(biāo)函數(shù)，提高了算法的運(yùn)行速率。實(shí)驗(yàn)結(jié)果表明，本文提出的L2KNN算法的實(shí)用性和有效性較佳。

[1]Turk M,Pentland A.Eigenfaces for recognition[J].Journal of Cognitive Neuroscience,1991,3(1):71-86.

[2]Belhumeur P N,Hespanha J P,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]Liu Chengjun,Yang Jian.ICA color space for pattern recognition[J].IEEE Transactions on Neural Networks,2009,20(2):248-257.

[4]Liu Chengjun.Capitalize on dimensionality increasing techniques for improving face recognition grand challenge performance[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(5):725-737.

[5]You Di,Hamsici O C,Martinez A M.Kernel optimization in discriminant analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,33(3):631-638.

[6]Wright J,Yang A Y,Ganesh A,et al.Robust face recognition via sparse representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,31(2):210-227.

[7]Zhang Qiang,Li Baoxin.DiscriminativeK-SVDfor dictionary learning in face recognition[C]//Proceedings of the 23rd Conference on Computer Vision and Pattern Recognition,San Francisco,Jun 13-18,2010.Washington:IEEE Computer Society,2010:2691-2698.

[8]Jiang Zhuolin,Lin Zhe,Davis L S.Label consistentK-SVD:learning a discriminative dictionary for recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(11):2651-2664.

[9]Yang Meng,Zhang Lei,Feng Xiangchu,et al.Sparse representation based Fisher discrimination dictionary learning for image classification[J].International Journal of Computer Vision,2014,109(3):209-232.

[10]Chen Junzhou,Li Qing,Peng Qiang,et al.CSIFT based locality-constrained linear coding for image classification[J].PatternAnalysis andApplications,2015,18(2):441-450.

[11]Zhao Zhongqiu,Cheung Y M,Hu Haibo,et al.Expanding dictionary for robust face recognition:pixel is not necessary while sparsity is[J].IET Computer Vision,2015,9(5):648-654.

[12]Shi Jun,Li Yi,Zhu Jie,et al.Joint sparse coding based spatial pyramid matching for classification of color medical image[J].Computerized Medical Imaging and Graphics,2014,41(1):61-66.

[13]Gao Shenghua,Tsang W H,Chia L T.Laplacian sparse coding,hypergraph Laplacian sparse coding,and applications[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(1):92-104.

[14]Deng Weihong,Hu Jiani,Guo Jun.Extended SRC:undersampled face recognition via intraclass variant dictionary[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(9):1864-1870.

[15]Feng Zhizhao,Yang Meng,Zhang Lei,et al.Joint discriminative dimensionality reduction and dictionary learning for face recognition[J].Pattern Recognition,2013,46(8):2134-2143.

[16]Zou Hui,Hastie T.Regularization and variable selection via the elastic net[J].Journal of the Royal Statistical Society:Series B Statistical Methodology,2005,67(5):301-320.

[17]Liu Qingfeng,Liu Chengjun.A novel locally linearKNN method with applications to visual recognition[J].IEEE Transactions on Neural Networks and Learning Systems,2017,28(9):2010-2021.

[18]Beck A,Teboulle M.A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J].SIAM Journal on Imaging Sciences,2009,2(1):183-202.

[19]Tibshirani R.Regression shrinkage and selection via the LASSO[J].Journal of the Royal Statistical Society:Series B Methodological,1996,58(1):267-288.

[20]Martinez A M,Kak A C.PCA versus LDA[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(2):228-233.

[21]Lee K C,Ho J,Kriegman D J.Acquiring linear subspaces for face recognition under variable lighting[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(5):684-698.

[22]Ahonen T,Hadid A,Pietik?inen M.Face recognition with local binary patterns[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(12):2037-2041.

[23]Sim T,Baker S,Bsat M.The CMU pose,illumination,and expression database[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(12):1615-1618.