組加權(quán)約束的核稀疏表示分類算法

鄭建煒 楊 平 王萬良 白 琮

(浙江工業(yè)大學計算機科學與技術(shù)學院 杭州 310023) (zjw@zjut.edu.cn)

?

組加權(quán)約束的核稀疏表示分類算法

鄭建煒 楊 平 王萬良 白 琮

(浙江工業(yè)大學計算機科學與技術(shù)學院 杭州 310023) (zjw@zjut.edu.cn)

提出了一種稱為核加權(quán)組稀疏表示分類器(kernel weighted group sparse representation classifier, KWGSC)的新型模式分類算法. 通過在核特征空間而非原輸入空間引入組稀疏性和保局性，KWGSC能夠獲得更有效的鑒別性重構(gòu)系數(shù)用于分類表示. 為獲得最優(yōu)重構(gòu)系數(shù)，提出了一種新的迭代更新策略進行模型求解并給出了相應的收斂性證明以及復雜度分析. 對比現(xiàn)存表示型分類算法，KWGSC具有的優(yōu)勢包括：1)通過隱含映射變換，巧妙地規(guī)避了經(jīng)典線性表示算法所固有的規(guī)范化問題；2)通過聯(lián)合引入距離加權(quán)約束和重構(gòu)冗余約束，精確地推導出查詢樣本的目標類別標簽；3)引入l2,p正則項調(diào)整協(xié)作機制中的稀疏性，獲得更佳的分類性能. 人造數(shù)值實驗表明：經(jīng)典線性表示型算法在非范數(shù)歸一化條件下無法找到正確的重構(gòu)樣本，而KWGSC卻未受影響. 實際的公共數(shù)據(jù)庫驗證了所提分類算法具有魯棒的鑒別力，其綜合性能明顯優(yōu)于現(xiàn)存算法.

稀疏表示技術(shù)；保局性；組稀疏正則項；核技術(shù)；范數(shù)歸一化問題

近年來，稀疏表示技術(shù)(sparse representation, SR)已經(jīng)在機器視覺、模式識別和信號處理等眾多領域獲得了廣泛應用和一致認可，包括圖像修復[1]、特征提取[2]、視頻檢測[3]和目標跟蹤[4]等.針對目標信號，SR搜尋少量基向量對其進行線性組合表示，采用稀疏正則化項解決解空間的病態(tài)問題，為信號分類增加魯棒性和鑒別性，其基向量稱為原子，而所有輸入樣本集合則稱為字典.許多現(xiàn)實信號，如圖像和音頻等，被公認為具有稀疏先驗本質(zhì).稀疏性約束不僅能夠給出目標解的唯一性，更能夠幫助解析真實的信號結(jié)構(gòu)，獲得魯棒的抗噪能力.此外，信號的稀疏表示還能夠帶來解卷和分離等輔助功能，有益于后續(xù)分類問題.雖然原始的稀疏最優(yōu)化是一個非凸問題，但其l1范數(shù)凸擴展以及更新優(yōu)化策略已被廣泛地研究改進[5-6].

Wright等人[7]將完整的輸入樣本集作為訓練字典，提出了一種鑒別性稀疏表示分類器(sparse representation classifier, SRC)并在人臉識別中獲得了卓越的性能.針對過完備的輸入字典，SRC通過稀疏的原子數(shù)據(jù)對輸入信號作近似線性表示，并選擇最小重構(gòu)誤差的類別標簽為目標模式歸屬.雖然SRC在信號去噪[8]、時間序列分類[9]、超分辨率重建[10]等眾多研究中都獲得了成功應用，但其對稀疏性的過分強調(diào)卻遭到了其他科研工作者的質(zhì)疑[11-13].鑒于稀疏性約束在高維特征中具有計算耗時較大的缺陷，Zhang等人[13]認為沒有必要在線性回歸問題中添加稀疏約束，并進一步指出SRC分類器的性能較NN，INNC[14]等近鄰型算法突出的根本原因并非其稀疏性，而是數(shù)據(jù)間的協(xié)作關系所致，從而提出了協(xié)作表示分類器(collaborative representation classifier, CRC).CRC采用l2范數(shù)替換耗時的l1范數(shù)，在保持鑒別能力的同時獲得了算法運行效率的大幅度提升.值得注意的是，SRC和CRC都屬于無監(jiān)督型算法，其在模式鑒別過程中并未引入輸入特征的類組標簽信息.為進一步提升識別性能，Majumdar等人[15]引入類組稀疏正則項，以類內(nèi)協(xié)作類間稀疏為基本思想提出了組稀疏分類器(group sparse classifier, GSC)，將l2,1范數(shù)作為線性重構(gòu)表示的約束.類似地，Jin等人[16]也采用組稀疏編碼進行圖像分類，以過完備字典為基礎，搜尋稀疏組原子進行測試樣本表示.理論分析和實驗結(jié)果都表示GSC具有較SRC和CRC更強的分類性能，鑒于此，GSC得到了廣泛應用且其改進算法不斷涌現(xiàn)[17].

雖然上述經(jīng)典表示型算法都具有可靠的鑒別能力，但是仍存在著3個關鍵問題有待解決：

1) SRC，CRC，GSC從范數(shù)約束形式出發(fā)，分別通過稀疏性、協(xié)作性和監(jiān)督性為主旨構(gòu)建分類模型，其全局表示過程中都忽略了輸入特征的局部分布結(jié)構(gòu)，但事實上局部保持特性(又稱保局性)被認為是非常有益的分類器屬性之一[18]；

2) 限于線性本質(zhì)，SRC和CRC等算法在應用于具有同向分布性質(zhì)的輸入特征時都表現(xiàn)出較弱的分類性能[6]，本文稱之為范數(shù)歸一化問題；

3) 實際分類任務中，字典矩陣的過完備性條件[7]并不一定滿足，導致SRC解的稀疏性不足，依靠協(xié)作機制進行重構(gòu)鑒別[19]，本文稱之為稀疏性不足問題.

針對保局性問題，F(xiàn)an等人[20]通過樣本距離對反映數(shù)據(jù)分布結(jié)構(gòu)，以測試樣本與輸入特征間的歐氏距離約束l1范數(shù)正則項，提出加權(quán)稀疏表示分類器(weighted sparse representation classifier，WSRC).類似地，加權(quán)協(xié)作表示分類器(weighted collaborative representation classifier, WCRC)[21-22]和加權(quán)組稀疏算法(weighted group sparse representation, WGSR)[23-24]分別將局部約束添加至l2范數(shù)和l2,1范數(shù)上，通過保局性引導進一步提升了CRC和GSC的分類性能.然而，現(xiàn)實分類數(shù)據(jù)往往具有復雜分布特征，包括多模態(tài)分布和奇異點分布等，簡單的距離加權(quán)約束并不能直觀地反映輸入特征形態(tài).并且，對于GSC而言，單純距離約束往往會破壞其組范數(shù)特性.

針對范數(shù)歸一化問題，核技術(shù)[25]被廣泛應用于表示型算法擴展，包括核稀疏表示分類器(kernel SRC，KSRC)[26-28]、核協(xié)作表示分類器(kernel CRC，KCRC)[21]及其加權(quán)版本[6,21].這些核算法通過隱含變換將輸入特征映射至高維特征空間(又稱核特征空間)，并進行線性分類操作.為解決隱含變換的計算問題，核算法采用核函數(shù)替代高維特征數(shù)據(jù)的內(nèi)積運算.眾所周知，核技術(shù)能夠捕獲輸入特征更多的非線性結(jié)構(gòu)，其性能優(yōu)于相應的線性分類器.然而，核算法對于鑒別性能提升的根源仍未得到理論分析和驗證，而且迄今為止關于GSC分類器的核化擴展算法仍未見報道.

針對稀疏性不足問題，Xu等人[29]理論證明了在lp(0

綜上所述，本文提出了核加權(quán)組稀疏表示分類器(kernel weighted group sparse representation classifier, KWGSC)，以l2,p組范數(shù)為約束，引入核技巧將GSC算法進行非線性擴展.此外，兼顧距離加權(quán)和重構(gòu)加權(quán)約束表示系數(shù)，使KWGSC在不破壞類組結(jié)構(gòu)的前提下提升算法的鑒別能力.

1 相關工作

以SRC和CRC為代表，本節(jié)簡要描述表示型算法的基本原理.將所有的輸入特征樣本X=(X1,X2,…,Xc)∈m×n作為字典數(shù)據(jù)，其中Xi=(xi1,xi2,…,xini)∈m×ni是第i類數(shù)據(jù)的訓練樣本子集，m維輸入特征xij表示第i類目標對象的第j個樣本，c是目標類別總數(shù)，ni為第i類特征樣本數(shù)，

所有的表示型算法都具有相似的模型原理，即以過完備輸入字典為前提，所有樣本一致分布于某子空間內(nèi).換言之，任意測試樣本y可通過訓練特征樣本進行協(xié)作線性表示，即

y=X1θ1+X2θ2+…+Xcθc=

x11θ11+x12θ12+…+xcncθcnc=Xθ，

(1)

其中,θ=(θ11,θ12,…,θcnc)T∈n是輸入特征X對應的重構(gòu)編碼系數(shù)向量.一般采用式(2)優(yōu)化求取最佳的θ解.

(2)

(3)

其中，參數(shù)λ需要人工設定，用于平衡重構(gòu)誤差和系數(shù)值之間的貢獻度，一般較高的λ值對應于更為稀疏的編碼系數(shù)解θ.根據(jù)β，Z，η，p各值的變化，式(3)可以演化為不同的稀疏(或協(xié)作)表示型算法.在得到優(yōu)化系數(shù)θ*后，設δi(θ*)為選擇符號，表示將θ中除第i類外所有元素都置為0的向量，則測試樣本可由各類訓練樣本進行重構(gòu)，即y=Xδi(θ*),i=1,2,…,c.最終可將y歸類為具有最小重構(gòu)誤差的類別標簽k，即

(4)

1.1 經(jīng)典表示型分類算法

經(jīng)典的表示型分類算法直接以測試樣本和訓練特征樣本的原始形式作為模型數(shù)據(jù)，同時忽略考慮樣本間的分布加權(quán)約束，即采用β=y，Z=X，η=1n(元素都為1的n維矩陣)，在不同的p值范數(shù)約束下進行算法模型描述.

當p=1時，即是經(jīng)典的稀疏表示分類器SRC[7].按照文獻[7]理論分析，在l1范數(shù)約束和過完備訓練特征條件下，通過式(3)求得的編碼系數(shù)θ具有稀疏性.即在式(1)中，假設測試樣本y是第i類目標數(shù)據(jù)，則除θi(第i類訓練特征所對應的編碼系數(shù))外的所有編碼系數(shù)值都為零.

當p=2時，則是經(jīng)典的協(xié)作表示分類器CRC[13].與SRC強調(diào)稀疏性不同，Zhang等人[13]認為SRC算法的鑒別性能之所以較KNN，INNC[14]等最近鄰型算法更為突出，其本質(zhì)原因是由于數(shù)據(jù)間的協(xié)作表示而非稀疏性.因此，CRC采用l2范數(shù)作為編碼系數(shù)的約束，大大提升了其運行效率.值得注意的是，CRC的編碼系數(shù)不會趨向于絕對零值，從理論上不具備稀疏性.然而，其中更具表示能力的訓練特征仍對應更高的編碼系數(shù)值，因此我們依然可以稱之為稀疏表示型算法.

當p=12時，式(3)轉(zhuǎn)變?yōu)閘分類器LHC[19].稀疏性范數(shù)約束l1要求模型輸入具有充足的訓練樣本，因而獲得接近于l0范數(shù)的稀疏解.然而，現(xiàn)實分類問題如圖像識別等往往存在高維數(shù)小樣本的情形，使得SRC解的稀疏性較弱，類似于CRC的協(xié)作分類機制.通過LHC算法得到的編碼系數(shù)較SRC更為稀疏，在樣本數(shù)受限的應用中有效地平衡了協(xié)作表示和稀疏表示的貢獻.

SRC，CRC，LHC都是無監(jiān)督學習算法，在模型構(gòu)建過程中忽略了樣本標簽信息，其性能有待進一步提升.GSC采用l2,1范數(shù)約束，設定p為2,1，對不同類別的特征樣本作l1范數(shù)約束，而同類樣本則采用l2范數(shù)約束，因此算法具有組稀疏性.已有的研究結(jié)果表明，GSC的綜合識別性能優(yōu)于SRC和CRC[16-17]，其模型求解策略與SRC基本一致，需要通過迭代更新進行編碼系數(shù)優(yōu)化求解，效率遜于CRC的閉式求解方案.

1.2 加權(quán)表示型分類算法

如引言所述，SRC，CRC，GSC這3種分類器通過稀疏性、協(xié)作性以及監(jiān)督性進行模型描述構(gòu)建，但卻忽視了輸入樣本的局部分布結(jié)構(gòu)因素.然而，保局性在眾多模式分類和機器學習算法中已被廣泛應用，包括數(shù)據(jù)分簇[30]、流形挖掘[31]、多任務學習[32]等領域.文獻[18,33]直接表明數(shù)據(jù)保局因子較稀疏性等更有模型指示意義.基于此，已有不少保局性表示型分類算法提出.由于保局性一般以權(quán)值形式約束于編碼系數(shù)，因此該類算法可以統(tǒng)稱為加權(quán)表示型分類算法.

與經(jīng)典表示型算法類似，保持式(3)其余部分不變，編碼系數(shù)權(quán)值通過η實現(xiàn)，其值一般取決于測試樣本與輸入特征的歐氏距離，即

(5)

其中，ηij代表第i類數(shù)據(jù)第j個編碼系數(shù)值的加權(quán)因子，帶寬參數(shù)σ需要人工經(jīng)驗設定，一般取為平均距離方差較為合理.

SRC，CRC的加權(quán)版算法分別為WSRC[20]和WCRC[21]，在η權(quán)值的影響下，遠距離樣本的編碼系數(shù)值趨向于零，而近鄰樣本獲得較高編碼系數(shù)的機率相對更大.因此WSRC和WCRC具有保局特性以及奇異點抑制特性.此外，部分加權(quán)表示型算法[22]采用訓練樣本構(gòu)建加權(quán)因子而非通過測試樣本計算，實驗結(jié)果表明其性能弱于WSRC和WCRC.

1.3 核表示型分類算法

模式分析的典型研究方向，包括分簇、低秩、主成分、關聯(lián)性以及識別等任務，都需要通過用戶指定的特征映射操作將輸入數(shù)據(jù)進行模式變換.相反地，核方法通過核技術(shù)的引入，以原輸入特征的成對相似性函數(shù)替換特征映射，通過隱含變換實現(xiàn)非線性空間中的線性操作，其典型代表有支持向量機[34]、核主成分分析[35]以及核Fisher鑒別分析[36]等.KSRC[26]和KCRC[21]分別通過核函數(shù)的引入，實現(xiàn)了在核特征空間中的稀疏表示系數(shù)計算.

假設測試樣本y和輸入特征X可通過非線性映射φ變換至高維F空間，將β和Z分別表述為φ(y)和Φ(X)，其中Φ是φ的矩陣描述形式，則式(3)可以改寫為

(6)

其中，暫時忽略加權(quán)因子，即令η=1n.由于φ是一個未知的隱含映射，核方法通過核函數(shù)替代F空間中兩兩特征樣本的內(nèi)積計算，用于算法的優(yōu)化求解實現(xiàn)，即式(6)調(diào)整為

(7)

其中K=Φ(X)TΦ(X)∈n×n是對稱半正定的核矩陣[36]，k(·,y)=(k(x11,y),k(x12,y),…,k(xcnc,y))T=Φ(X)Tφ(y).常見的核函數(shù)k(a,b)包括線性核、多項式核以及高斯核，其中應用最為廣泛的是高斯核函數(shù)，表達式為

(8)

式(8)是本文實驗所選用的核函數(shù)形式，其中帶寬參數(shù)σ需要人工設定，用于控制高維核空間中樣本對內(nèi)積的具體取值.

聯(lián)合添加核函數(shù)式(8)和加權(quán)因子式(5)于編碼系數(shù)計算式(3)，即可得到核加權(quán)表示型分類算法，文獻[6,21]都通過數(shù)值實驗和實際數(shù)據(jù)實驗驗證了其性能優(yōu)于常規(guī)的核化表示分類算法和加權(quán)表示分類算法.

2 核加權(quán)組稀疏分類算法KWGSC

根據(jù)第1節(jié)相關工作闡述，稀疏表示型算法，如GSC，WSRC，KCRC等，都通過協(xié)作表示原理，以重構(gòu)誤差最小為目標進行樣本判別，在模式識別領域獲得了廣泛的應用，取得了卓越的成效.總體來說，此類方法的核心問題是：選擇最具代表性且對應范數(shù)值最小的數(shù)據(jù)進行測試樣本重構(gòu)表示，以誤差最小化為準則進行模式鑒別，其中包括2個關鍵點，即精確重構(gòu)以及最小化范數(shù)值.基于此，本節(jié)首先詳細闡述了數(shù)據(jù)歸一化形式與特征優(yōu)選的聯(lián)系，然后提出KWGSC算法，并對其模型優(yōu)化進行了分析求解和收斂性證明.

2.1 稀疏表示與規(guī)范化問題

在模式識別領域，分類模型在實際應用中往往都會對輸入特征進行不同形式的規(guī)范化操作，包括均值化處理[36-37]和范數(shù)歸一化處理[21]等.不同預處理操作能夠規(guī)范輸入特征數(shù)據(jù)的分布狀態(tài)并提升分類器的數(shù)值穩(wěn)定性.然其對分類性能的具體影響仍未得到充分地理論分析與實驗驗證.本節(jié)從具體數(shù)值實例出發(fā)(如圖1和圖2所示)，分析討論稀疏表示型算法受范數(shù)歸一化操作的影響.

Fig. 1 Numeric examples for the norm normalization problem with different sparse representation algorithms.圖1 非歸一化數(shù)據(jù)對不同稀疏表示型算法影響的數(shù)值示例

Fig. 2 Norm normalization problem.圖2 范數(shù)歸一化問題

在圖1(a)中，通過標準高斯分布給出了3類人工設定數(shù)據(jù)，分別為以坐標(1,2)為中心的圓形數(shù)據(jù)，以坐標(5,0)為中心的方形數(shù)據(jù)以及以坐標(1,-3)為中心的三角形數(shù)據(jù).圖1(a)中實心圓點是圓形數(shù)據(jù)的中心，作為測試樣本，余下的所有輸入數(shù)據(jù)作為訓練樣本.從圖1可見，在范數(shù)值不一致的輸入數(shù)據(jù)中，大部分稀疏表示型算法都沒能選擇最優(yōu)的訓練樣本進行線性重構(gòu)，呈現(xiàn)出較弱的鑒別力，稱之為范數(shù)歸一化問題.該問題導致高范數(shù)值訓練數(shù)據(jù)被選擇為重構(gòu)樣本的概率大大提升.在圖1給定的數(shù)據(jù)中，圓形、方形和三角形3類樣本的l2范數(shù)值域分別為(0.433，17.668)，(13.194，48.659)，(3.494，31.602)，其中方形和三角形數(shù)據(jù)的范數(shù)值明顯高于圓形數(shù)據(jù)，也更有可能被選為表示樣本.在圖1(b)中，SRC的非零系數(shù)所對應的樣本分別為一個方形和一個三角形，都不是正確的圓形數(shù)據(jù)，違背了SRC算法提出時類內(nèi)線性表示的基本思想；CRC和GSC不是嚴格意義上的稀疏表示算法，本文選用前15%大的系數(shù)值進行顯示.在圖1(c)中，CRC的有效表示樣本包括3種不同類型的輸入數(shù)據(jù)，但以三角形和方形居多.在圖1(d)中，GSC通過組約束，剔除了方形表示樣本，然而三角形表示樣本數(shù)仍然多于同類圓形樣本.取決于保局特性，圖1(e)中WSRC選擇了正確的同類樣本進行稀疏表示，然而歸一化問題仍然存在，其表示樣本具有同類數(shù)據(jù)中較大的范數(shù)值.

圖2進一步闡明了范數(shù)歸一化操作對表示型分類算法的意義.在圖2(a)中，X1={x11,x12,x13}和X2={x21,x22,x23}是2類經(jīng)過l2范數(shù)歸一化的數(shù)據(jù)，按簇分布于單位圓上.將x11作為測試樣本，余下的作為訓練樣本.點q1是x12與x13連線以及x11與原點連線的交點，其至原點的歐氏距離設為b1.類似地，點q2是x12與x21連線以及x11與原點連線的交點，q2到原點的歐氏距離設為b2.假定x11可以通過x12和x13線性表示，由于輸入樣本分布于單位圓上，因此可以得到:

圖2(b)顯示了沒有經(jīng)過范數(shù)歸一化操作的2類數(shù)據(jù)，其中圓點數(shù)據(jù)的坐標為x11=(0.5,-0.8)，x12=(0.9,-0.5)，x13=(0.1,0.04)，方塊數(shù)據(jù)的坐標為x21=(3.4,1.5)，x22=(3.3,-1.0)，x23=(3.1,0.5)，則有

x11=(x12x13)(1.163,-5.465)T=

(x22x23)(0.575,-0.451)T=

X(0,1.163,-5.465,0,0,0)T=

X(0,0,0,0,0.575,-0.451)T，

(9)

其中X=(x11,x12,…,x23)是訓練數(shù)據(jù)矩陣.

類似地，將所有數(shù)據(jù)作l1范數(shù)歸一化，有x11=(0.38,-0.62)T，x12=(0.64,-0.36)T，x13=(0.71,0.29)T，x21=(0.69,0.3)T，x22=(0.77,-0.23)T，x23=(0.86,0.14)T，以及

x11=(x12x13)(1.252,-0.589)T=

(x22x23)(1.9,-1.248)T=

X(0,1.252,-0.589,0,0,0)T=

X(0,0,0,0,1.9,-1.248)T.

(10)

最后，再將所有數(shù)據(jù)作l2范數(shù)歸一化，有x11=(0.53,-0.85)T，x12=(0.87,-0.49)T，x13=(0.93,0.37)T，x21=(0.91,0.4)T，x22=(0.96,-0.29)T，x23=(0.99,0.16)T，以及

x11=(x12x13)(1.269,-0.624)T=

(x22x23)(2.62,-1.5)T=

X(0,1.269,-0.624,0,0,0)T=

X(0,0,0,0,2.62,-1.5)T.

(11)

聯(lián)合式(9)～(11)可見，在輸入數(shù)據(jù)沒有經(jīng)過歸一化操作時，式(9)中x12和x13對應的系數(shù)l1范數(shù)為6.63，而x22和x23對應的系數(shù)l1范數(shù)為1.03.因此，x22和x23被錯誤地選擇為重構(gòu)表示測試數(shù)據(jù)x11，而非x12和x13.當輸入數(shù)據(jù)經(jīng)過l1歸一化操作后，式(10)中x12，x13和x22，x23對應的系數(shù)l1范數(shù)分別1.84和3.14.因此，x12和x13被正確選擇為重構(gòu)表示數(shù)據(jù).進一步地，當輸入數(shù)據(jù)經(jīng)過l2歸一化操作后，式(11)中x12，x13和x22，x23對應的系數(shù)范數(shù)分別1.89和4.12，不僅能獲得所需的正確結(jié)果，且其范數(shù)差異較l1歸一化操作時更大，更具有鑒別性.該結(jié)論與圖2(a)的理論分析具有一致性，說明歸一化操作對稀疏表示型算法的影響以及l(fā)2范數(shù)歸一化的優(yōu)越性.

2.2 KWGSC算法描述

綜合第1節(jié)和2.1節(jié)分析，本節(jié)提出核加權(quán)組稀疏表示分類算法KWGSC，包含組稀疏范數(shù)、保局性、核函數(shù)等有利分類的技術(shù).值得強調(diào)的是：

2) 理想情況下，輸入特征樣本Z具有充分完備性，則表示系數(shù)的非零元素嚴格對應y的同類訓練樣本[7].很明顯，稀疏性約束(如l0范數(shù))在該情形下的重構(gòu)表示中起關鍵作用.然而，由于l0約束的NP難問題，實際應用中極限稀疏的系數(shù)解很難得到，更多地依賴協(xié)作機制進行重構(gòu)表示(如SRC中的l1正則項以及CRC中的l2正則項).為有效地平衡協(xié)作性和稀疏性的貢獻，本文將范數(shù)約束擴展至(0,1]范圍(區(qū)別于LHC中的固定值1/2)，并以組范數(shù)約束的形式構(gòu)建目標函數(shù).

結(jié)合式(3)(6)以及l(fā)2,p組范數(shù)約束的KWGSC目標模型為

(12)

(13)

其中,di與WSRC和WCRC中的權(quán)值意義一致，其元素dij在核特征空間中的取值為

(14)

此外，ri是類組加權(quán)系數(shù)，借鑒線性回歸分類器的思想[39]，其值表示為

(15)

其中,Ki=Φ(Xi)TΦ(Xi)∈ni×ni是第i類核矩陣，ki(·,y)=(k(xi1,y),k(xi2,y),…,k(xini,y))=Φ(Xi)Tφ(y)是y與第i類輸入數(shù)據(jù)的核向量.可見ηi=ridi由2部分組成：第1部分ri是第i類樣本Xi重構(gòu)測試樣本y的冗余，其值越小，代表y屬于第i類的概率越大，相應第i類的重構(gòu)系數(shù)θi越大；第2部分di用于懲罰遠距離樣本，dij值越大，說明相應的樣本xij離y越遠，對應重構(gòu)系數(shù)θij越小.

通過式(13)可見，對比GSC，KWCRC，WSRC等現(xiàn)存算法，KWGSC在核特征空間通過類組加權(quán)和距離加權(quán)凸顯了表示系數(shù)的組結(jié)構(gòu)特性，具有更多的鑒別性信息.結(jié)合式(4)和式(15)，在最優(yōu)化目標函數(shù)式(13)后，KWGSC通過表示系數(shù)θ*所建的模式鑒別規(guī)則為

(16)

即在核特征空間中，選擇重構(gòu)誤差最小的類為測試樣本y的類別標簽.

2.3 優(yōu)化求解和收斂性分析

現(xiàn)有稀疏表示型算法中CRC，KCRC，KWCRC等協(xié)作表示算法都具有閉式解，而SRC，GSC等(包括相應衍生算法)則需要迭代操作計算最優(yōu)系數(shù)解，包括特征標記法[40]、梯度投影法[41]、同倫分析法[42]、近端梯度法[43]等.KWGSC算法在核特征空間中兼顧類組重構(gòu)和樣本加權(quán)約束.因此，現(xiàn)有的迭代求解算法無法直接應用于計算KWGSC的目標系數(shù)θ*.針對該問題，本節(jié)采用一種新的迭代策略進行組l2,p問題優(yōu)化求解.為簡化公式描述，引入矩陣Π=diag((η1,η2,…,ηc))∈n×n，并定義=2,p，將核加權(quán)組稀疏的目標模型表示為

(17)

對式(17)依系數(shù)向量θ求微分可得:

Kθ-k(·,y)+λΠTDΠθ=0，

(18)

(19)

則可得:

θ=(K+λΠTDΠ)-1k(·,y).

(20)

需要注意的是:式(20)中D的計算包含系數(shù)θ.因此，系數(shù)θ的優(yōu)化策略是一個迭代更新過程，所提的核加權(quán)編碼求解具體方案如算法1所示，其實現(xiàn)過程中，值得強調(diào)3點：

2) 從式(20)可見，編碼系數(shù)θ的更新是一個閉式求解公式，易于直觀實現(xiàn).本文將初始θ(1)值取為n維元素恒等于1n的向量.

算法1. 核加權(quán)編碼系數(shù)迭代求解算法.

輸入: 帶類別標簽的特征樣本X，待測樣本y，參數(shù)值λ，σ，p，最大迭代數(shù)tmax；

輸出: 最優(yōu)編碼系數(shù)θ*.

① 計算核矩陣K以及待測樣本y與各特征樣本的核函數(shù)值k(·,y);

② 依式(14)計算距離加權(quán)d，依式(15)計算重構(gòu)加權(quán)r;

③ 根據(jù)d和r得到η，并構(gòu)建權(quán)值矩陣Π;

④ 迭代t=1，設初始編碼系數(shù)為θ(t);

⑤ 依η和θ(t)構(gòu)建塊對角矩陣D;

⑥ 按照式(20)求解θ(t+1);

⑦ 滿足收斂則輸出θ*，反之則令t=t+1，并轉(zhuǎn)步驟④.

引理1. 給定任意非零向量x和y，當p∈(0,1]時，

(21)

證明. 根據(jù)凹函數(shù)定義[44]，當p∈(0,1]時，已知凹函數(shù)xp在定義域(0,∞)中有yp-xp+pyp-1(x-y)≥0.對非零向量xi和yi則有:

(22)

將式(22)中所有的i∈{1,2,…,c}相加，則式(21)得證.

證畢.

定理1. 通過算法1迭代計算，目標函數(shù)式(17)的值逐次下降直至收斂.

證明. 定義第t次迭代時的誤差向量為et=φ(y)-Φ(X)θt，由于θt+1是式(18)的解，則有:

Φ(X)TΦ(X)θt+1-Φ(X)Tφ(y)+

λΠTDtΠθt+1=0.

(23)

通過對式(23)兩邊分別點乘θt-θt+1可得:

λ(θt-θt+1)TΠTDtΠθt+1=

(θt-θt+1)TΦ(X)T(φ(y)-Φ(X)θt+1)=

(Φ(X)θt-y+y-Φ(X)θt+1)T·

(φ(y)-Φ(X)θt+1)=-(et-et+1)Tet+1.

(24)

結(jié)合引理1和式(24)有：

λtr((θt-θt+1)Tθt+1ΠTDΠ)=

(et-et+1)Tet+1.

(25)

此外,

(et-et+1)Tet+1.

(26)

將式(25)與式(26)相加可以得到:

(et-et+1)T(et-et+1)≥0,

即目標函數(shù)式(17)在迭代更新過程中逐次降值，并具有明確的下確界0，則該算法收斂性得證.

證畢.

3 實驗分析

3.1 數(shù)據(jù)庫描述與實驗設置

1) 數(shù)據(jù)庫.采用AR人臉數(shù)據(jù)庫、COIL20物體圖像數(shù)據(jù)庫以及MNIST手寫字體數(shù)據(jù)庫驗證所提算法的性能.AR數(shù)據(jù)庫包含126個目標人物的4 000多幅正臉圖像，囊括光照、表情變化以及面部裝飾等情形.由于KWGSC并未針對外物遮擋進行算法設計，因此本文選擇AR數(shù)據(jù)庫中的非遮擋子集進行識別率測試[45]，包括50個男性目標和50個女性目標，每個目標選擇7個訓練樣本和7個測試樣本，所有圖像均被預處理至60×43灰度像素.COIL20物體圖像庫包含20個目標對象，每個對象由位置固定的攝像機拍下其水平旋轉(zhuǎn)的72張照片.所有目標圖像都經(jīng)過邊緣裁剪且縮放至40×40灰度像素，本文隨機選擇每類30個樣本作為訓練數(shù)據(jù)集，余下的所有樣本作為測試集.MNIST數(shù)據(jù)庫包含70 000個手寫字圖像，并劃分為訓練集和測試集.與文獻[21]類似，本文針對每個數(shù)字(0～9共10個數(shù)字)，從訓練集中隨機選擇50個樣本，從測試集中隨機選擇70個樣本，共計500個訓練數(shù)據(jù)和700個訓練數(shù)據(jù)進行實驗分析，該數(shù)據(jù)集中的所有圖像都統(tǒng)一裁剪調(diào)整至28×28灰度像素.

Fig. 3 Recognition performance versus parameter changes for different competing algorithms.圖3 不同算法識別率隨正則化參數(shù)變化的對比

2) 輸入特征形式.在不同的實驗過程中，輸入的特征數(shù)據(jù)包括原始灰度像素值和子空間投影樣本.原始灰度像素值將輸入圖像按列展開并串聯(lián)成單方向向量.以AR數(shù)據(jù)庫為例，將其中的任意訓練或測試樣本都調(diào)整為60×43=2 580×1的特征串.子空間投影樣本則將上述向量特征進行維數(shù)約簡操作，包括經(jīng)典的主成分分析算法(principal component analysis, PCA)和最新提出的迭代最近鄰線性投影算法(iterative nearest neighbors linear projections, INNLP)[14].PCA以最大化訓練樣本散度為目標函數(shù)，旨在保留輸入數(shù)據(jù)的主分布結(jié)構(gòu);INNLP則采用迭代最近鄰法進行鄰域矩陣構(gòu)建，并以局部結(jié)構(gòu)保持為目標函數(shù)計算線性投影矩陣，其正則化參數(shù)在本文中恒設為0.05.

3) 分類算法.選用不同的稀疏型分類算法進行實驗效果對比，包括經(jīng)典線性算法SRCF[7](F表示采用特征標記法訓練)、CRC[13]、LHC[19]和GSC[16]，距離加權(quán)線性算法WSRC[20]和WCRC[21]，核化算法KSRCF[28]、KSRCH[27](H表示采用同倫法訓練)、KCRC[6]和KWCRC[21].此外，本文還引入經(jīng)典分類算法最近鄰分類器(NNC)、新晉的迭代最近鄰分類器(INNC)以及兩者各自的核化版本KNNC[34]和KINNC[14]作為對比分類模型，以豐富的數(shù)據(jù)驗證所提算法KWGSC的鑒別性能.所對比的算法中，除NNC和KNNC外，都包含需要人工設定的正則化參數(shù)值λ，本文采用4倍交叉驗證進行最優(yōu)值確定.針對任意分類算法，考慮λ={10-8,10-7,…,10-1,100}進行鑒別分類，在不同輸入特征維數(shù)中選取具有最高平均識別率的λ值為最終模型參數(shù).除λ參數(shù)值外，各核化版算法都采用高斯核函數(shù)作為模型運行組件，其帶寬參數(shù)σ需要人工確定，本文將其統(tǒng)一設置為輸入特征距離矩陣的平均值.如無特殊聲明，組范數(shù)l2,p中的參數(shù)值p默認為1.圖3以GSC，KCRC，KSRCF，KSRCH，KWGSC算法為例，采用AR人臉數(shù)據(jù)庫和MNIST手寫字體數(shù)據(jù)庫為輸入特征，給出了不同正則化參數(shù)值環(huán)境下的算法分類性能對比結(jié)果，降維技術(shù)為PCA.其中，識別率的計算公式為1-mn，m是識別錯誤樣本數(shù)，n是所有測試樣本總數(shù).從圖3結(jié)果可以得到如下3點：

1) 參數(shù)λ的最優(yōu)值一般都小于1，且位于(10-4,10-1)區(qū)間內(nèi)的可能性更高；

2) 隨參數(shù)λ值在(10-8,10-1)區(qū)間內(nèi)變化，各算法的識別率波動較小，尤其在(10-8,10-4)區(qū)間內(nèi)，各算法的識別率基本保持不變，僅KSRCH算法在AR數(shù)據(jù)庫中有較大的差異；

3) 各算法在不同輸入特征維數(shù)下的最優(yōu)參數(shù)選值非常穩(wěn)定，如KWGSC，GSC，KSRCH算法都嚴格保持一致，而KCRC和KSRCF算法的最優(yōu) 值變化也非常接近.

上述3點綜合表明了稀疏表示型算法的人工待選參數(shù)確定較為直觀，減輕了算法實際應用的繁瑣程度.

3.2 歸一化范數(shù)分析

如3.1節(jié)所述，輸入特征的不同范數(shù)形式對稀疏表示型算法的性能具有明顯的影響，本節(jié)以GSC和KWGSC兩種算法為例，以MNIST，AR，COIL20三個數(shù)據(jù)庫為應用對象，在不同范數(shù)歸一化形式下進行算法識別率對比，如圖4所示.其中，降維技術(shù)仍然選用PCA，算法名稱_l2表示在l2范數(shù)歸一化中的識別率曲線，算法名稱_l1表示在l1范數(shù)歸一化中的識別率曲線，而算法名稱_l0則表示保持輸入特征不變無范數(shù)歸一化時的識別率曲線.

從圖4可見：隨著范數(shù)歸一化約束的變化，線性算法GSC的識別率具有較大幅度的變化，在不同子空間維數(shù)下誤差達到2%～6%；單獨對比GSC的識別率發(fā)現(xiàn)，在不同的范數(shù)歸一化約束中，l2范數(shù)的識別率最高，而l0非歸一化的識別率最低；此外，KWGSC算法通過引入高斯函數(shù)，輸入特征在F空間中具有恒為l2規(guī)范化的特點，因此其識別率在不同數(shù)據(jù)庫、不同子空間維數(shù)下的變化較小，誤差基本保持在1%以內(nèi).圖4所示實驗結(jié)果與正文理論分析部分完全吻合.在后續(xù)實驗中，為保證線性算法的識別率，統(tǒng)一采用l2范數(shù)進行輸入特征歸一化處理.

Fig. 4 Recognition performance versus norm changes for GSC and KWGSC.圖4 GSC和KWGSC兩種算法在不同歸一化范數(shù)下的識別率對比

3.3 識別性能分析

確定最優(yōu)模型參數(shù)和歸一化范數(shù)形式后，本節(jié)驗證所提算法在不同目標對象和不同輸入特征維數(shù)下的識別率性能.針對MNIST手寫字體數(shù)據(jù)庫，表1給出了所有分類器在不同目標數(shù)字下的識別率(輸入特征是150維的PCA降維樣本).表1中黑體數(shù)字表示相同維數(shù)特征下所有算法的最高識別率，帶單下劃線的數(shù)字表示第2高識別率，帶雙下劃線的數(shù)字則表示第3高識別率.通過表1可知，MNIST數(shù)據(jù)庫中不同數(shù)字對象的識別難度各異，其中數(shù)字“2”是識別率最高的對象，包括KWGSC和NNC在內(nèi)共計8種分類器對其取得了100%的識別率，而最低的識別率也達到了97.1%；數(shù)字“9”是綜合識別率最低的對象，其最高識別率僅為87.1%，由WSRC和KSRCH獲得.在15種分類器的對比中，本文所提的KWGSC具有最優(yōu)的綜合識別率，共計獲得4個最優(yōu)值(黑體)、4個次優(yōu)值(單下劃線)以及2個第3優(yōu)值(雙下劃線)，表明其在不同目標對象下具有更為穩(wěn)定的分類性能.雖然分類器WSRC也獲得了4個最優(yōu)值(黑體)，但其只有1個次優(yōu)值(單下劃線)，且沒有第3優(yōu)值(雙下劃線)，因此在該實驗對比中排第2.

特征維數(shù)測試中，分別以原始輸入特征和通過PCA，INNLP處理后的子空間特征進行分類實驗，子空間維數(shù)選為{50,100,150,200,250,300}，表2～4顯示了各分類器在所有數(shù)據(jù)庫中的識別性能對比，其中DR表示維數(shù)約簡操作(dimensionality reduction).

Table 1 Recognition Rate for Different Numbers on MNIST

Table 2 Recognition Rate versus Different Feature Dimensions on the MNIST Database

Table 3 Recognition Rate versus Different Feature Dimensions on the AR Database

Table 4 Recognition Rate versus Different Feature Dimensions on the COIL20 Database

從表2～4可以得出5個結(jié)論：

1) 考慮到實際圖像數(shù)據(jù)的分布多樣性，無法從所對比的15種算法中確定具有絕對優(yōu)勢的分類模型，大部分分類器在不同輸入特征中的表現(xiàn)有一定波動，本文嘗試從中挖掘相對穩(wěn)定且高性能的分類算法.

2) NNC，INNC及相應核化算法的綜合識別率相對低于其余稀疏型分類器.在MNIST手寫字體數(shù)據(jù)庫中，NNC和KNNC在PCA子空間中的最高識別率僅為86.3%，而其余算法的最低識別率達到87%，最高達到93.4%(KWGSC)；類似地，KINNC在INNLP子空間中的最高識別率僅為55.4%，遠低于余下算法的最低識別率62.9%.說明采用最近鄰模式進行鑒別判定無法勝任現(xiàn)實數(shù)據(jù)的精確分類，而協(xié)作表示對于復雜分布數(shù)據(jù)具有有益的模式鑒別效果.

3) 線性算法SRCF，CRC，LHC，GSC的對比中，LHC較SRCF和CRC有微弱優(yōu)勢，說明合理地平衡稀疏性和協(xié)作性能夠提升分類性能；GSC在COIL20物體圖像庫的PCA子空間中略遜于LHC算法，而在余下分類實驗中都優(yōu)于其他3種線性表示型算法.其中，在AR數(shù)據(jù)庫，GSC的最高識別率為94.0%，優(yōu)于同條件下的所有14種算法.究其原因，GSC采用有監(jiān)督的l2,1范數(shù)作為重構(gòu)系數(shù)約束，引入類別標簽引導最優(yōu)系數(shù)計算，優(yōu)于單一的l1，l2，l范數(shù)約束.

4) 核化算法的綜合識別率明顯高于對應的線性算法.KCRC，KSRCF，KWCRC，KWGSC等核分類算法在表2～4不同輸入特征的識別率中大部分高于相應的CRC，SRCF，WCRC，GSC算法，驗證了正文中關于核化算法具有更高鑒別性的論點.

Fig. 5 Recognition performance versus p in KWGSC.圖5 KWGSC在不同稀疏值p下的算法識別率測試

5) KWGSC算法兼具了上述結(jié)論中的所有優(yōu)勢，包括核化、監(jiān)督性、距離加權(quán)等，并且添加了重構(gòu)冗余系數(shù)約束，其綜合識別率明顯優(yōu)于其他算法.從表2～4可見，KWGSC在所有3個數(shù)據(jù)庫中都具有最多的最優(yōu)值、次優(yōu)值和第3優(yōu)值，在MNIST，AR，COIL20中的最高識別率分別達到93.4%，94.7%，99.8%.此外，KWGSC算法的穩(wěn)定性也優(yōu)于其他算法，在不同數(shù)據(jù)庫中的波動明顯小于其他所對比的算法.

通過表1～4的實驗可知，KWGSC分類器在鑒別性能和分類穩(wěn)定性上都優(yōu)于其余對比分類器.本節(jié)進一步測試KWGSC在組范數(shù)參數(shù)值p變化時的分類性能.圖5給出了在p∈{0.1,0.2,…,0.9,1.0}時KWGSC的識別率，其中NONE,PCA和INNLP分別表示原始輸入特征、PCA降維至150和INNLP降維至150時的識別率.從圖5可見，KWGSC的分類性能總體上隨p值變化波動較小，其識別率保持在2%內(nèi)，其中在MNIST的PCA和INNLP子空間和COIL20的PCA和NONE空間中的識別率基本保持不變.同時，圖5進一步顯示了KWGSC的最優(yōu)值并不一定來源于p=1，而是以[0.5,0.8]區(qū)間為最佳，該結(jié)果一方面驗證了LHC算法[19]的基本思想，同時也表明了LHC中將p值固定為12的缺陷.因此，本文在KWGSC分類算法中并未明確約束組范數(shù)值p，使之能夠在不同的分類任務中依目標數(shù)據(jù)進行參數(shù)優(yōu)選，勝任分布特性更為復雜的異構(gòu)數(shù)據(jù).

3.4 運行效率分析

除識別性能外，運行效率是影響分類算法實際應用能力的另一關鍵指標.本節(jié)選擇在MNIST，AR，COIL20數(shù)據(jù)庫中表現(xiàn)較為穩(wěn)健的9種分類算法進行測試效率對比，包括SRCF，CRC，GSC，LHC，WCRC，KSRCF，KCRC，KWCRC，KWGSC.表5顯示了各算法在不同數(shù)據(jù)庫中單個樣本的測試時間，其中各單元格所對應的識別率為表2～4原始維數(shù)列.所有的數(shù)據(jù)都通過10次實驗運行并取平均值得到，實驗平臺為Intel Core i5 CPU，雙核主頻2.80 GHz，內(nèi)存4 GB，32位Win 7操作系統(tǒng)以及Matlab 2014運行軟件.結(jié)合表1～5所示，CRC和KCRC在識別率上雖然與SRCF以及KSRCF較為接近，但是其運行效率卻遠遠優(yōu)于SRC型算法，達到了毫秒級的反應速度，完全可以勝任視頻跟蹤等在線應用系統(tǒng)；加權(quán)型表示算法WCRC以運行效率減弱為代價提升鑒別性能，從表4可見其運行時間接近于CRC算法的30倍，而識別率提升則并不顯著，因此實用性欠佳；GSC的識別率僅次于KWGSC，但其實現(xiàn)過程需要迭代計算操作(類似于SRCF)，因此運行效率較低；LHC的運行效率與GSC較為接近，而其綜合識別性能弱于GSC，算法優(yōu)勢并不明顯；最后，KWGSC的運行效率高于SRCF，KSRCF，GSC，LHC，WCRC等算法，僅次于CRC和KCRC，在大部分應用中都達到了10 ms級的運行效率(除AR數(shù)據(jù)庫外)，考慮到其具有最高最穩(wěn)定的鑒別性能，因此值得推廣應用.需要注意的是，GSC與KWGSC的求解算法類似，KWGSC的運行效率優(yōu)于GSC得益于重構(gòu)系數(shù)和距離加權(quán)的引入，使得其能夠在更少的迭代次數(shù)下獲得算法收斂.

Table 5 Testing Time of Competing Algorithms

4 總 結(jié)

通過數(shù)值實驗分析了不同范數(shù)歸一化操作對經(jīng)典線性表示模型的影響以及核化算法的魯棒性，以此為基礎提出核加權(quán)組稀疏分類算法(KWGSC).該算法以l2,p范數(shù)約束為基礎引入核技術(shù)，通過距離約束和重構(gòu)冗余加權(quán)提升算法的組稀疏特性和分類鑒別能力.本文所提算法在AR人臉數(shù)據(jù)庫、COIL20物體圖像庫以及MNIST手寫字體數(shù)據(jù)庫中獲得高識別率，明顯優(yōu)于現(xiàn)有的表示型分類算法.此外，為獲得最優(yōu)的重構(gòu)系數(shù)，提出一種新的迭代更新策略用于模型優(yōu)化求解，通過有限次迭代操作即可達到算法的全局最優(yōu)解，實驗驗證該算法的運行效率優(yōu)于經(jīng)典的GSC算法和SRC算法.總體來說，本文的創(chuàng)新點包括：

1) 首次采用數(shù)值實驗和圖例分析范數(shù)歸一化操作對分類性能的影響進行深度研究；

2) 對GSC算法進行核化擴展，并在距離加權(quán)的基礎上添加類組重構(gòu)加權(quán)，提升算法識別能力；

3) 以組范數(shù)l2,p，其中p∈(0,1]為約束，并在核空間中提出快速高效的迭代優(yōu)化算法用于模型求解.

分析研究發(fā)現(xiàn)，所提算法KWGSC雖然易于實現(xiàn)且性能卓越，但實現(xiàn)過程中需要固定受限的核函數(shù)，如高斯核或其擴展核函數(shù)，不適于算法的多核操作應用.此外，KWGSC算法并沒有對輸入數(shù)據(jù)進行特征加權(quán)約束，不適于遮擋應用環(huán)境和高含噪特征樣本.因此，后續(xù)工作將集中進行多核擴展和特征加權(quán)研究.

[1]Zhang Jian, Zhao Debin, Gao Wen. Group-based sparse representation for image restoration[J]. IEEE Trans on Image Processing, 2014, 23(8): 3336-3351

[2]Yang Wankou, Wang Zhenyu, Sun Changyin. A collaborative representation based projections method for feature extraction[J]. Pattern Recognition, 2015, 48(1): 20-27

[3]Tao Jianwen, Chung F L, Wang Shitong, et al. Sparse label propagation: A robust domain adaptation learning method[J]. Journal of Software, 2015, 26(5): 977-1000 (in Chinese)

(陶劍文, Chung F L, 王士同, 等. 稀疏標簽傳播: 一種魯棒的領域適應學習方法[J]. 軟件學報, 2015, 26(5): 977-1000)

[4]Hu Zhaohua, Yuan Xiaotong, Li Jun, et al. Robust fragments-based tracking with multi-feature joint kernel sparse representation[J]. Journal of Computer Research and Development, 2015, 52(7): 1692-1704 (in Chinese)

(胡昭華, 袁曉彤, 李俊, 等. 基于目標分塊多特征核稀疏表示的視覺跟蹤[J]. 計算機研究與發(fā)展, 2015, 52(7): 1692-1704)

[5]Candes E J, Tao T, Near-optimal signal recovery from random projections: Universal encoding strategies[J]. IEEE Trans on Information Theory, 2006, 52(12): 5406-5425

[6]Liu Weiyang, Yu Zhiding, Lu Lijia, et al. KCRC-LCD: Discriminative kernel collaborative representation with locality constrained dictionary for visual categorization[J]. Pattern Recognition, 2015, 48(10): 3076-3092

[7]Wright J, Yang A Y, Ganesh A, et al. Robust face recognition via adaptive sparse representation[J]. IEEE Trans on Pattern Analysis & Machine Intelligence, 2014, 44(12): 2368-2378

[8]Liu Jianwei, Cui Lipeng, Liu Zeyu, et al. Survey on the regularized sparse models[J]. Chinese Journal of Computers, 2015, 38(7): 1307-1325 (in Chinese)

(劉建偉, 崔立鵬, 劉澤宇, 等. 正則化稀疏模型綜述[J]. 計算機學報, 2015, 38(7): 1307-1325)

[9]Chen Zhihua, Zuo Wangmeng, Hu Qinghua, et al. Kernel sparse representation for time series classification[J]. Information Sciences, 2015, 292: 15-26

[10]Wang Lingfeng, Yan Hongping, Lü Ke, et al. Visual tracking via kernel sparse representation with multikernel fusion[J]. IEEE Trans on Circuits and Systems for Video Technology, 2014, 24(7): 1132-1141

[11]Rigamonti R, Brown M A, Lepetit V. Are sparse representations really relevant for image classification?[C] //Proc of the 27th IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2011: 1545-1552

[12]Shi Qinfeng, Eriksson A, Anton H, et al. Is face recognition really a compressive sensing problem?[C] //Proc of the 27th IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2011: 553-560

[13]Zhang Lei, Yang Meng, Feng Xiangchu. Sparse representation or collaborative representation: Which helps face recognition?[C] //Proc of Int Conf on Computer Vision. Piscataway, NJ: IEEE, 2011: 471-478

[14]Timofte R, Gool L V. Iterative nearest neighbors[J]. Pattern Recognition, 2015, 48(1): 60-72

[15]Majumdar A, Rabab K W. Fast group sparse classification[J]. Canadian Journal of Electrical and Computer Engineering, 2009, 34(4): 136-144

[16]Huang Jin, Nie Feiping, Huang Heng, et al. Supervised and projected sparse coding for image classification[C] //Proc of the 27th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2013: 438-444

[17]Wang Lijun, Lu Huchuan, Wang Dong. Visual tracking via structure constrained grouping[J]. IEEE Signal Processing Letters, 2015, 22(7): 794-798

[18]Wei Jiangshu, Lü Jiancheng, Zhang Yi. Robust classifier using distance-based representation with square weights[J]. Soft Computing, 2015, 19(2): 507-515

[19]Zhong Dexing, Xie Zichao, Li Yanrui, et al. Loosel1/2regularized sparse representation for face recognition[J]. IET Computer Vision, 2015, 9(2): 251-258

[20]Fan Zizhu, Ni Ming, Zhu Qi, et al. Weighted sparse representation for face recognition[J]. Neurocomputing, 2015, 151: 304-309

[21]Timofte R, Gool L V. Adaptive and weighted collaborative representation for image classification[J]. Pattern Recognition Letters, 2014, 42: 127-135

[22]Wu Jiqing, Timofte R, Gool L V. Learned collaborative representations for image classification[C] //Proc of IEEE Winter Conf on Applications of Computer Vision. Piscataway, NJ: IEEE, 2015: 456-463

[23]Chao Yuwei, Ye Yiren, Chen Yuwen, et al. Locality-constrained group sparse representation for robust face recognition[C] //Proc of IEEE Int Conf on Image Processing. Piscataway, NJ: IEEE, 2011: 761-764

[24]Tang Xin, Feng Guocan, Cai Jiaxin. Weighted group sparse representation for under sampled face recognition[J]. Neurocomputing, 2014, 145: 402-415

[25]Muller K, Mika S, Ratsch G, et al. An introduction to kernel-based learning algorithms[J]. IEEE Trans on Neural Networks, 2001, 12(2): 181-201

[26]Zhang Li, Zhou Weida, Chang P C, et al. Kernel sparse representation-based classifier[J]. IEEE Trans on Signal Processing, 2012, 60(4): 1684-1695

[27]Kang Cuicui, Liao Shengcai, Xiang Shiming, et al. Kernel Homotopy based sparse representation for object classification[C] //Proc of the 21st Int Conf on Pattern Recognition (ICPR). Piscataway, NJ: IEEE, 2012: 1479-1482

[28]Gao Shenghua, Tsang I W, Chia L T. Sparse representation with kernels[J]. IEEE Trans on Image Processing, 2013, 22(2): 423-434

[29]Xu Zongben, Chang Xiangyu, Xu Fengmin, et al. L1/2 regularization: A thresholding representation theory and a fast solver[J]. IEEE Trans on Neural Networks and Learning Systems, 2012, 23(7): 1013-1027

[30]Nie Feiping, Wang Xiaoqian, Huang Heng. Clustering and projected clustering with adaptive neighbors[C] //Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2014: 977-986

[31]Wang Lingfeng, Wu Huaiyu, Pan Chunhong. Manifold regularized local sparse representation for face recognition[J]. IEEE Trans on Circuits and Systems for Video Technology, 2015, 25(4): 651-659

[32]Wang Shengzheng, Jing Peng, Liu Wei. Anl2/l1regularization framework for diverse learning tasks[J]. Signal Processing, 2015, 109: 206-211

[33]Wang Jinjun, Yang Jianchao, Yu Kai, et al. Locality-constrained linear coding for image classification[C] //Proc of IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2010: 3360-3367

[34]Richard O D, Peter E H, David G S. Pattern Classification[M]. New York: Wiley, 2001

[35]Jerome F, Trevor H, Robert T. The Elements of Statistical Learning: Data Mining, Inference, and Prediction[M]. Berlin: Springer, 2001: 534-553

[36]Yan Hui, Jian Y. Sparse discriminative feature selection[J]. Pattern Recognition, 2015, 48(5): 1827-1835

[37]Zhang Pan, Lian Qiusheng. Low-rank relaxed collaborative representation combined with global and local features for face recognition[J]. Journal of Computer Research and Development, 2014, 51(12): 2663-2670 (in Chinese)

(張盼, 練秋生. 融合整體與局部特征的低秩松弛協(xié)作表示[J]. 計算機研究與發(fā)展, 2014, 51(12): 2663-2670)

[38]Zheng Zhonglong, Huang Xiaoqiao, Chen Zhongyu, et al. Regression analysis of locality preserving projections via sparse penalty[J]. Information Sciences, 2015, 303: 1-14

[39]Naseem I, Togneri R, Bennamoun M. Linear regression for face recognition[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2010, 32(11): 2106-2112

[40]Rajat R, Battle A, Lee H, et al. Self-taught learning: Transfer learning from unlabeled data[C] //Proc of the 20th Annual Conf on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2006: 801-808

[41]Liu J, Ji S, Ye J. SLEP: Sparse learning with efficient projections[CP/OL]. Arizona: Arizona State University, 2009[2014-10-12]. http://www.public.asu.edu/～jye02/Software/SLEP

[42]Salman A M, Romberg J. Dynamic updating forl1minimization[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2): 421-434

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

[44]Boyd S, Vandenberghe L. Convex Optimization[M]. Cambridge, UK: Cambridge University Press, 2009

[45]Yang Meng, Zhang Lei, Yang Jian, et al. Regularized robust coding for face recognition[J]. IEEE Trans on Image Processing, 2013, 22(5): 1753-1766

Zheng Jianwei, born in 1982. PhD and associate professor at Zhejiang University of Technology. His main research interests include machine learning, data mining, and computer vision.

Yang Ping, born in 1992. Master candidate at Zhejiang University of Technology. His main research interests include machine learning, data mining, and computer vision (2111412076@zjut.edu.cn).

Wang Wanliang, born in 1957. PhD and professor at Zhejiang University of Technology. His main research interests include deep learning, artificial intelligence and network control (wwl@zjut.edu.cn).

Bai Cong, born in 1981. PhD and lecturer at Zhejiang University of Technology. His main research interests include imagevideo retrieval and computer vision (congbai@zjut.edu.cn).

Kernel Sparse Representation Classification with Group Weighted Constraints

Zheng Jianwei, Yang Ping, Wang Wanliang, and Bai Cong

(CollegeofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou310023)

A new classification method called KWGSC (kernel weighted group sparse representation classifier) is proposed for pattern recognition. KWGSC integrates both group sparsity and data locality in the kernel feature space rather than in the original feature space. KWGSC can learn more discriminating sparse representation coefficients for classification. The iteratively update solution of thel2,p-norm minimization problem for KWGSC is also presented. There are several appealing aspects associated with KWGSC. Firstly, by mapping the data into the kernel feature space, the so-called norm normalization problem that may be encountered when directly applying sparse representation to non-normalized data classification tasks will be naturally alleviated. Secondly, the label of a query sample can be inferred more precisely by using of distance constraints and reconstruction constraints in together. Thirdly, thel2,pregularization (wherep∈(0,1]) is introduced to adjust the sparsity of collaborative mechanism for better performance. Numeric example shows that KWGSC is able to perfectly classify data with different normalization strategy, while conventional linear representation algorithms fail completely. Comprehensive experiments on widely used public databases also show that KWGSC is a robust discriminative classifier with excellent performance, being outperforming other state-of-the-art approaches.

sparse representation (SR); locality-constraint; group sparse regularizer; kernel trick; norm normalization problem

2015-08-11；

2016-02-16

國家自然科學基金項目(61602413,61379123,61502424)；國家科技支撐計劃基金項目(2012BAD10B01)；浙江省自然科學基金項目(LY15F030014,LY15F020028)

TP391.4

This work was supported by the National Natural Science Foundation of China (61602413, 61379123, 61502424), the National Key Technology R&D Program of China (2012BAD10B01), and the Natural Science Foundation of Zhejiang Province of China (LY15F030014, LY15F020028).