基于K最近鄰的L2，1范數(shù)稀疏回歸分類器

徐 潔，祝文康

（韶關(guān)學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，廣東 韶關(guān) 512005）

最近，Ren［4］等人提出了基于旋轉(zhuǎn)不變范數(shù)的回歸分類器(RRC).RRC的基本原理是把全體訓(xùn)練樣本作為原子字典庫，利用L2,1范數(shù)比L2范數(shù)對(duì)野點(diǎn)更具抗干擾性的特點(diǎn)，用L2,1范數(shù)代替L2范數(shù)對(duì)樣本作度量，同時(shí)，對(duì)重構(gòu)系數(shù)作L2,1范數(shù)的正則化約束，使得到的系數(shù)矩陣具有組稀疏特點(diǎn).以此重構(gòu)方式得到的正確類樣本與測試樣本靠得更近，而錯(cuò)誤類樣本與測試樣本離得更遠(yuǎn).實(shí)驗(yàn)表明，RRC有效.

然而，當(dāng)訓(xùn)練樣本的數(shù)量很大時(shí)，RRC利用全體訓(xùn)練樣本作為原子字典庫存在耗時(shí)大的缺點(diǎn).另一方面，過度追求重構(gòu)系數(shù)的稀疏，容易導(dǎo)致原本是同類樣本更具優(yōu)勢的稀疏重構(gòu)，讓部分有著與測試樣本相似的非同類的訓(xùn)練樣本以更為稀疏的方式來重構(gòu)測試樣本.具體例子可參考圖1.基于以上兩方面的考慮，本文提出了基于K最近鄰的范數(shù)稀疏回歸分類器（KNN-SRC）.KNN-SRC利用K最近鄰（KNN）［5］算法為每個(gè)測試樣本量身定做了原子字典庫，即每個(gè)測試樣本只有K個(gè)訓(xùn)練樣本，基于篩選后的訓(xùn)練樣本，執(zhí)行RRC算法.

1 基于旋轉(zhuǎn)不變范數(shù)的回歸分類器（RRC）

對(duì)一般的分類問題，不妨假設(shè)有C個(gè)模式類，n個(gè)訓(xùn)練樣本，樣本矩陣為A=［a1;a2;…;an］∈Rn×d；N個(gè)測試樣本，測試樣本矩陣為Y=［y2,y2,yN］∈Rd×N.

利用L2,1范數(shù)對(duì)野點(diǎn)更具抗干擾性的特點(diǎn)，對(duì)系統(tǒng)ATX=Y作L2,1范數(shù)度量和正則化約束，即：

其中X=［x1,x2,…,xN］∈Rn，是系數(shù)矩陣，最優(yōu)的系數(shù)矩陣具有組稀疏的特點(diǎn).

基于最優(yōu)的稀疏系數(shù)矩陣，基于旋轉(zhuǎn)不變范數(shù)的回歸分類器可設(shè)計(jì)為：對(duì)給定的測試樣本yj，定義δi()∈Rn為測試樣本yj所聯(lián)系的第i類樣本的系數(shù)向量，其中為測試樣本yj對(duì)應(yīng)的最優(yōu)稀疏系數(shù)向量.δi(j)只有對(duì)應(yīng)第i類樣本的元素非0，其余位置的元素均為0.計(jì)算測試樣本yj的第i類的重構(gòu)樣本，即=ATδi(j).定義測試樣本yj與的誤差為：

RRC的分類準(zhǔn)則是：如果rij=minrij(yj)，則yj被認(rèn)為是第l類的樣本.

2 基于K最近鄰的L2,1范數(shù)稀疏回歸分類器（KNN-SRC）

2.1算法原理

KNN-SRC首先利用KNN對(duì)每一個(gè)測試樣本的字典原子作篩選，再基于所選擇的k個(gè)最近的原子對(duì)測試樣本稀疏重構(gòu)，稀疏重構(gòu)系數(shù)的求解可借助信號(hào)處理領(lǐng)域里求解多測量變量模型的方法得到.算法最后計(jì)算測試樣本與類重構(gòu)樣本的距離.以重構(gòu)誤差的大小依據(jù)，對(duì)測試樣本作分類判斷.具體方法如下.

給定一個(gè)測試樣本yj，利用KNN算法在全體訓(xùn)練樣本中找到Kj個(gè)與其近鄰樣本.假設(shè)屬于第i類的個(gè)最近鄰樣本為. 測試樣本yj的Kj個(gè)最近鄰樣本矩陣記為.以為原子字典庫，在L2,1范數(shù)度量下對(duì)測試樣本yj作稀疏重構(gòu)，重構(gòu)系數(shù)可通過求解以下的優(yōu)化問題得到：

如果近鄰參數(shù)Kj＜＜n，yi=很難實(shí)現(xiàn).可采用以下兩種方式放松約束條件：

其中ε是任意小的正實(shí)數(shù)，ρ是正則化參數(shù).

本文采用（6）式的目標(biāo)優(yōu)化函數(shù)來求解稀疏重構(gòu)系數(shù).

（7）式的目標(biāo)優(yōu)化函數(shù)常用于信號(hào)處理交換領(lǐng)域，可對(duì)拉格朗日函數(shù)執(zhí)行梯度下降法，以獲得迭代解［6］：

其中D是對(duì)角矩陣，對(duì)角的元素為dij==1/(2‖ui‖2)，ui是U的第i行向量.

顯而易見，U*的前n行即為測試樣本yj最佳的重構(gòu)系數(shù).定義第i類的刻畫函數(shù)可選擇測試樣本yj所關(guān)聯(lián)的第i類樣本的重構(gòu)系數(shù)，除了第i類樣本所關(guān)聯(lián)的系數(shù)外，()的其余系數(shù)為0.計(jì)算測試樣本yj在第i類的重構(gòu)樣本的誤差，即：

2.2 KNN-JSRC算法

輸入：訓(xùn)練樣本集A∈Rn×d；測試樣本yj∈Rd,j=1,…,N；正則化參數(shù)ρ；最近鄰參數(shù)Kj.

輸出：yj的類標(biāo).

（1）利用KNN算法，在所有的訓(xùn)練樣本中尋找與yj最近的Kj個(gè)近鄰樣本，記為∈RKj×d；

（2）設(shè)B=(,ρI)；

（3）初始化Dt∈R(n+d)×(n+d)為單位矩陣；

（4）利用公式（8）迭代計(jì)算出U；

（5）forj=1,2,…,N

end.

2.3 KNN-SRC與RRC的對(duì)比

當(dāng)測試樣本被極為少數(shù)的訓(xùn)練樣本最大限度地稀疏重構(gòu)，而所用于稀疏重構(gòu)的訓(xùn)練樣本與測試樣本不同類，只是在形狀上與測試樣本極為相像，也或許只是測試樣本的一部分時(shí)，KNN-SRC比RRC更為魯棒.如圖 1 例子［7］所示.對(duì)于測試樣本Y，即數(shù)字“8”，用“0”，“1”到“9”等 10 類數(shù)字樣本稀疏重構(gòu).很明顯，用Y1和Y2重構(gòu)Y的系數(shù)要比用X1、X2和X3重構(gòu)Y時(shí)的系數(shù)稀疏.但同時(shí)也導(dǎo)致了分類器的性能下降，因?yàn)閅1和Y2明顯與Y不是同類樣本.因此，在執(zhí)行RRC前用KNN對(duì)原子字典進(jìn)行篩選，很有必要.

圖1 兩類手寫數(shù)字的識(shí)別問題

3 實(shí)驗(yàn)與分析

為進(jìn)一步檢驗(yàn)KNN-JSRC的算法性能，在UCI的Wine數(shù)據(jù)庫和Yale人臉數(shù)據(jù)庫上比較了KNN-JSRC 與最近鄰分類器(NNC)［8］，最小距離分類器(MDC)， 線性回歸分類器(LRC)［9］，稀疏表示分類器(SRC)［10］和RRC的分類性能.本實(shí)驗(yàn)中采用了“BPDN_homotopy_function.m”［11］來計(jì)算SRC.實(shí)驗(yàn)過程中所有參數(shù)均采用全局到局部的搜索方法來設(shè)定.

3.1數(shù)據(jù)庫的描述

Wine來自UCI數(shù)據(jù)集，是真實(shí)生活中的數(shù)據(jù).Wine有13個(gè)特征，分3類，共178個(gè)樣本.

Yale人臉數(shù)圖像庫中包括了15個(gè)人的165幅灰度人臉圖像，每個(gè)人由11幅照片構(gòu)成，這些照片在不同的表情和光照等條件下拍攝.在這個(gè)實(shí)驗(yàn)中，圖像被處理成32×32分辨率.圖2顯示了Yale人臉庫中某個(gè)人的11幅圖像.

圖2 Yale人臉數(shù)據(jù)庫中部分人臉圖像

3.2實(shí)驗(yàn)設(shè)計(jì)及結(jié)果

在Wine數(shù)據(jù)集上，分別從每類中隨機(jī)取20、30和40個(gè)樣本用作訓(xùn)練，剩余的樣本用作測試.實(shí)驗(yàn)重復(fù)10次.所有的實(shí)驗(yàn)在圖像原有的13維空間進(jìn)行，實(shí)驗(yàn)最后只報(bào)告各種比較方法的平均實(shí)驗(yàn)結(jié)果及相應(yīng)的標(biāo)準(zhǔn)方差.

在Wine數(shù)據(jù)集上，還就冗余數(shù)據(jù)對(duì)分類性能的影響作了進(jìn)一步探究.從每類中隨機(jī)選取20個(gè)樣本用作訓(xùn)練，每次單一的實(shí)驗(yàn)都有60個(gè)訓(xùn)練樣本，這其中包括了部分冗余的樣本.給定正則化參數(shù)λ=1，讓近鄰的參數(shù)K作40到50的變化，相應(yīng)的實(shí)驗(yàn)結(jié)果在圖3中作了直觀的描述.

在 Yale人臉數(shù)據(jù)庫上，先用PCA［12］對(duì)數(shù)據(jù)進(jìn)行降維.在40維的PCA子空間里再對(duì)所有的分類方法作比較.對(duì)每類樣本，分別選擇前3和4個(gè)樣本用作訓(xùn)練，剩余的樣本用作測試.

圖3 在不同的近鄰參數(shù)下，KNN-JSRC的識(shí)別率變化（其中λ=0.1）

3.3實(shí)驗(yàn)分析

（1）在UCI的Wine數(shù)據(jù)集上，6種分類器在不同的訓(xùn)練樣本數(shù)下的最高平均識(shí)別率以及對(duì)應(yīng)的標(biāo)準(zhǔn)方差見表1,在Yale人臉數(shù)據(jù)庫上，6種分類方法在不同的訓(xùn)練樣本下的最高識(shí)別率以及相應(yīng)的維度見表2.從表1和表2可見，UCI的Wine數(shù)據(jù)庫上，無論隨機(jī)選取20，30還是40個(gè)樣本用于訓(xùn)練，KNN-JSRC取得了較其它方法好的實(shí)驗(yàn)結(jié)果.同樣，在Yale人臉庫上，無論訓(xùn)練樣本是3還是4，KNN-JSRC同樣是取得了較其它分類器好的分類性能.

（2）表1中LRC的識(shí)別率只有33%，意味著只有很少一部分的樣本被正確識(shí)別.這其中的原因是LRC專門為人臉識(shí)別設(shè)計(jì)的，而人臉識(shí)別本身是小樣本問題，即：樣本的維度大于樣本的數(shù)量.在Wine上，樣本的維度是13，比每類用于訓(xùn)練的樣本數(shù)量小，即：（13＜20）.此種情況下，利用最小二乘法來求解最佳回歸系的LRC系統(tǒng)不能正常工作.

（3）圖1的實(shí)驗(yàn)結(jié)果表明，冗余數(shù)據(jù)在一定情況下會(huì)對(duì)數(shù)據(jù)的識(shí)別起干擾作用.在Wine數(shù)據(jù)集上，從3類的樣本中選取20個(gè)樣本用作訓(xùn)練，每次可用于訓(xùn)練樣本數(shù)為60.由圖1可見，最高識(shí)別率只需要48個(gè)樣本用作訓(xùn)練，其余的12樣本均可被視為冗余數(shù)據(jù).從圖1的曲線圖可見，隨著冗余的訓(xùn)練樣本數(shù)量的增加(即：K＞48)，識(shí)別率呈下降的趨勢.由此可見，對(duì)RRC的局部拓展很有必要.

表1 UCI的Wine數(shù)據(jù)訓(xùn)練結(jié)果

表2 Yale的人臉數(shù)據(jù)訓(xùn)練結(jié)果

4 結(jié)語

本文有機(jī)地整合了KNN和RRC，提出一類新穎的局部分類方法KNN-SRC.該方法有助于學(xué)習(xí)具有組稀疏特點(diǎn)的稀疏表示系數(shù)，引入KNN算法，對(duì)原子字典庫所做的預(yù)處理，在一定程度避免了由過分追求稀疏重構(gòu)帶來的誤分類，這對(duì)分類性能的提高有一定的幫助.KNN-SRC的分類性能在兩個(gè)數(shù)據(jù)庫上得以檢驗(yàn)，從實(shí)驗(yàn)結(jié)果看來，KNN-SRC比NNC、MDC、LRC、SRC和RRC有效.

：

［1］Yuan Ming，Lin Yi.Model selection and estimation in regression with grouped variables［J］.Journal of the Royal Statistical Society：Series B，2006，68（1）：49-67.

［2］Argyriou A，Evgeniou T，Pontil M.Convex multi-task feature learning［J］.Machine Learning， 2008，73(3)：243-272.

［3］Obozinski G，Taskar B，Jordan M I.Joint covariate selection and joint subspace selection for multiple classification problems［J］.Statistics and Computing，2010，20（6）：231-252.

［4］Ren C X，Dai D Q，Yan H.Robust classification using L2，1-norm based regression model［J］.Pattern Recognition，2012，45(7)：2708-2718.

［5］Cover T M， Hart P E.Nearest neighbor pattern classification［J］.IEEE Trans Inform Theory，1967，13(1)：21-27.

［6］Nie Feiping，Huang Heng，Cai Xiao，et al.Efficient and robust feature selection via joint L2，1-norms minimization［C］.Montreal:Advances in Neural Information Processing Systems,2010：1813-1821.

［7］Yang Jian，Zhang Lei，Xu Yong，et al.Beyond Sparsity：the Role of L1-optimizer in Pattern Classification［J］.Pattern Recognition， 2012，45(3)：1104-1118.

［8］Cover T M，Hart P E.Nearest neighbor pattern classification［J］.IEEE Transactions on Information Theory， 1967，13(1)：21-27.

［9］Naseem I，Togneri R，Bennamoun M.Linear Regression for Face Recognition［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(11)：2106-2112.

［10］Wright J，Yang A，Ganesh A，et al.Robust face recognition via sparse representation［J］.IEEE Trans On Pattern Analysis and Machine Intelligence，2009，31(2)：210-227.

［11］Yang A，Ganesh A，Sastry S，et al.Fast l1-Minimization Algorithms and An Application in Robust Face Recognition:A Review［C］.Berkeley:University of California,2010.

［12］Joliffe I T.Principal Component Analysis［M］.New York:Springer-Verlag，1986.