線性回歸分類器在模式識別中的應用

徐　潔，祝文康（1.廣東工業大學 智能信息處理實驗室，廣東廣州510006；.韶關學院數學與統計學院，廣東韶關51005）

線性回歸分類器在模式識別中的應用

徐潔1，2，祝文康2
（1.廣東工業大學 智能信息處理實驗室，廣東廣州510006；2.韶關學院數學與統計學院，廣東韶關512005）

摘要：線性回歸分類器（LRC）在人臉識別上呈現出了優越的性能，然而，隨著每類的訓練樣本數量增大,LRC的分類速度變得很慢.除此之外，LRC還有一致命的弱點：對大樣本問題束手無策，即當每類用于訓練的樣本數量大于樣本的維數時，LRC無法工作.解決以上問題的一個行而有效辦法是對LRC作局部化處理.可以對LRC作了兩類局部拓展：一是基于K最近鄰的線性回歸分類器（KNN-LRC）.KNN-LRC借助KNN算法對每類訓練的樣本作了篩選，從而避免了大樣本問題的出現，但卻受到近鄰參數選擇的困擾.二是在此基礎上進一步提出了基于L1范數的自適應局部線性回歸分類器（LI-LRC）.L1-LRC具有自適應的近鄰選擇機制，同時能取得比KNN-LRC更好的分類性能.在兩個數據庫上，比較各種相關分類器的性能.從分類的結果來看，KNN-LRC和L1-LRC較其它相關分類器的性能好.

關鍵詞：線性回歸分類器；局部；K最近鄰；L1正則化；模式分類

最近，Naseem等人提出了線性回歸分類器（LRC）并將其成功應用在人臉識別問題上［1］.LRC分類的基本思想是為測試樣本尋找最好的類重構，即具有最好的類重構的類別即被認為是測試樣本的類別所在.從文獻［1］報告的實驗結果來看，LRC確實獲得了令人鼓舞的結果.然而，當每類用于訓練的樣本數量很大時，LRC時耗大.除此之外，由于LRC是專門為類似人臉識別的小樣本問題［2-3］而設計的，故當面對大樣本問題，LRC無力可施.

為克服LRC的不足，筆者提出兩類局部的線性回歸分類器.一類是K最近鄰線性回歸分類器（KNNLRC).與LRC對比，KNN-LRC需要額外增加一個近鄰選擇的步驟.換而言之，KNN-LRC是在所選擇的近鄰上執行LRC.盡管只是對LRC作了局部處理，但KNN-LRC取得了比LRC更好的分類性能，同時通過對近鄰參數的調節，KNN-LRC避免了大樣本問題的出現.但像許多局部的方法一樣，KNN-LRC同樣面臨著如何選擇最佳近鄰參數的困擾.為解決此類問題，Wang等人和Mekuz等人在做了很多的嘗試，并給出了相應的解決辦法［4-5］.

除KNN-LRC外，本文還提出另外一類局部線性回歸分類器，自適應的局部線性回歸分類器 （L1-LRC）.與KNN-LRC不同，L1-LRC不需要事前人為地把近鄰參數設定，而是在LRC原有的目標優化上對回歸系數增加L1范數正則化約束.因此，L1-LRC也被認為是帶懲罰的最小二乘法，它同時實現了系數的連續收縮和自適應的變量選擇.由此得到的回歸系數是稀疏的.而非零項的回歸系數所關聯的樣本有著相似的特征，因此也被認為是測試樣本的相似近鄰.L1-LRC的這一特點提供了相似近鄰的自適應選擇機制.

1　　局部線性回歸分類器

1.1 K最近鄰局部線性回歸分類器（KNN-LRC）

其中，βi=［βi,1,βi,2,…,βi,k］T是y在第i類的回歸系數向量.

如果ds(y)=mindi(y)，y則被分到第s類.

1.2自適應的局部回歸分類器（L1-LRC）

通常，如果測試樣本屬于第i類，該測試樣本能很好地被同類的樣本線性表示.在LRC原有的目標優化下，增加對回歸系數作L1范數正則化約束.最佳的回歸系數向量可通過求解：

得到.但由于在現實的應用中，可提供的訓練樣本數量十分有限，同時數據采集過程中容易混入噪聲和離群點，故y=Xβ很難實現.為此，放松公式(3)約束條件如下：

為方便計算，選擇公式(4)來求解最佳的回歸系數.現存的許多Matlab代碼可直接用于求解.有一點值得注意，與KNN-LRC不同，由公式(4)求解得到的回歸系數是稀疏的.當正則化參數λ增加時，β只有很少一部分的項非零.由于非零項所關聯的樣本與測試樣本有著相似的特征，因此被認為是測試樣本的“相似”近鄰.由此看來，L1-LRC具有自適應的近鄰選擇機制.

1.3KNN-LRC和L1-LRC與LRC的優劣性比較

1.4KNN-LRC和L1-LRC以及LRC的計算復雜性

圖1　　一個關于正則化方法可行的演示

2　　仿真實驗

為進一步檢驗KNN-LRC和L1-LRC的算法性能,在UCI的Wine數據庫和CENPARMI手寫阿拉伯數字庫上分別比較了KNN-LRC和L1-LRC與最近鄰分類器(NNC)［10］,最小距離分類器(MDC)［11］,線性回歸分類器(LRC)［1］和稀疏表示分類器(SRC)［12］的性能.實驗中,采用“l1_ls”［13］來求解SRC.L1-LRC中的正則化參數和KNN-LRC中的近鄰參數K均采用全局到局部的搜索方法來設定.

2.1在UCI Wine數據集上的實驗

來自于UCI的Wine［14］數據集共有13個特征，3個類別，共178個樣本.每類選取48個樣本用于實驗. 在UCI Wine數據集中隨機選取T=(30,40)幅圖像用于訓練,剩余圖像用于測試.每組實驗運行10次.NNC、MDC、SRC、LRC、KNN-LRC和L1-LRC直接用于分類，最大的平均識別率和相應的標準方差記錄在表1和表2記錄了各種方法的運行時間.

表1　　當T(=30,40)時，各種方法的最大平均識別率和相應的標準差

表2　各方法10次實驗的平均運行時間 （單位：s）

為更進一步考察近鄰參數對KNN-LRC分類性能的影響，圖2給出了隨近鄰參數變化的KNN-LRC識別率曲線變化.觀察圖2不難發現：當每類的訓練樣本數為30或40時，KNN-LRC分別在K=8和K=5時取得最高的識別率.隨著近鄰參數K的不斷增大，KNN-LRC的性能出現下降的趨勢.尤其是當K>12時，兩類情況的識別率都少于40%.由此可見參數的選擇對KNN-LRC的性能有一定的影響.再來觀察L1-LRC的近鄰數，訓練樣本不同，近鄰參數也不一樣；即便每類用于訓練樣本數量一樣，不同類樣本采用的近鄰參數也不盡相同.可見，L1-LRC具有近鄰參數的自適應選擇機制.

圖2　不同近鄰參數下KNN-LRC的識別率變化曲線

表3　L1-LRC的近鄰參數是10次實驗的平均結果及其標準差

2.2在CENPARMI手寫阿拉伯數字庫上的實驗

CENPARMI手寫阿拉伯數字庫包含10個類的6 000個從“0”到“9”的121數字圖像［15］.本實驗選取個圖像用于訓練，剩余的樣本用于測試.6種分類器直接對121維的樣本圖像進行分類.表4列出了每種方法的最大識別率和相應的近鄰參數和每種方法的運行時間.圖4是KNN-LRC隨近鄰參數K變化的識別率曲線圖.

觀察表4，以及圖4和圖5，可以發現：（1）KNN-LRC和L1-LRC要比NNC、MDC、SRC和LRC的分類性能要好；（2）當T=(30,50)時，LRC的分類性能并不差，這結果與在UCI Wine數據庫上所做的實驗反差很大.相對于UCI Wine數據庫的樣本，在CENPARMI手寫阿拉伯數字庫的樣本的維度要比每類用于訓練的樣本數量要大，這是典型的小樣本問題.而LRC是為類似人臉識別的小樣本問題而設計，因此在該類情況下，LRC的分類效果要比NNC、MDC和SRC好.但是當每類用于訓練的樣本數達到130時，LRC出現了在UCI Wine數據集上的類似問題，只取得了10%的識別率.與LRC對比起來，KNN-LRC和L1-LRC對訓練樣本數量無具體要求，也表現得更為穩定；（3）當每類用于訓練的樣本達到130時，MDC遭受了在UCI Wine數據庫的同樣情況；（4）觀察表4關于SRC的實驗結果，當用于訓練的樣本數越大，SRC取得的分類性能越好.當T=130，SRC的識別率是91.6%，這比NNC、MDC和LRC的要高.SRC能取得如此好的分類結果，可歸功于SRC其自身的分類準則.SRC力求為每個測試樣本找到最能對其進行稀表示的類別所在.當訓練樣本數達到130時，這為SRC提供的充足的訓練樣本，非常有利于稀疏重構.盡管如此，SRC還是要遜色于L1-LRC和K1-LRC；（5）KNN-LRC的分類性能與近鄰參數K的選擇有著緊密的聯系，就圖4所示結果，可以發現當時，KNN-LRC最好的實驗結果是在K=10取得，隨著K增加到60，KNN-LRC的識別率只有65%.由此可見，KNN-LRC對近鄰參數的選擇很敏感；（6）從表5的運行時間來看，KNN-LRC要比LRC快；L1-LRC要比KNN-LRC慢，卻比SRC要快.

表4　　在CENPARMI手寫阿拉伯數字庫上，各種方法的最大訓別率和運行時間

圖4　　在CENPARMI手寫阿拉伯數字庫上，不同近鄰參數下KNN-LRC的識別曲線圖

圖5　　在CENPARMI手寫阿拉伯數字庫上，NN-LRC和L1-LRC的每類樣本的近鄰參數的變化

3　　結語

本文提出兩類局部的線性回歸分類器：KNN-LRC和L1-LRC.KNN-LRC和L1-LRC很好地克服了LRC的不足，并取得了不錯的分類性能，這在UCI Wine數據庫和CENPARMI手寫阿拉伯數字庫上得到很好的驗證.

參考文獻：

［1］Naseem I,Togneri R,Bennamoun M.Linear regression for face recognition［J］.Pattern Analysis and Machine Intelligence,IEEE Transactions on,2010,32(11):2106-2112.

［2］Fukunaga K.Introduction to statistical pattern recognition［M］.New York:Academic press,2013.

［3］Chen L F,Liao H Y M,Ko M T,et al.A new LDA-based face recognition system which can solve the small sample size problem［J］.Pattern recognition,2000,33(10):1713-1726.

［4］Zhang Z,Wang J,Zha H.Adaptive manifold learning［J］.Pattern Analysis and Machine Intelligence,IEEE Transactions on,2012, 34(2):253-265.

［5］Mekuz N,Tsotsos J K.Parameterless Isomap with adaptive neighborhood selection［M］.Berlin:Pattern Recognition Springer Berlin Heidelberg,2006:364-373.

［6］Hastie T,Tibshirani R,Friedman J,et al.The elements of statistical learning［M］.New York:springer,2009.

［7］Seber G A F.Linear Regression Analysis［M］.New York:Wiley-Interscience,2003.

［8］Ryan T P.Modern Regression Methods［M］.New York:Wiley-Interscience,1997.

［9］Chen S S,Donoho D L,Saunders M A.Atomic decomposition by basis pursuit［J］.SIAM journal on scientific computing,1998,20 (1):33-61.

［10］Cover T,Hart P.Nearest neighbor pattern classification［J］.Information Theory,IEEE Transactions on,1967,13(1):21-27.

［11］Gonzalez R C,Woods R E.Digital Image Processing［M］.New York:Addison Wesley,1997.

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

［13］Kim S,Koh K,Lustig M,et al.A method for large-scale l1-regularized least squares problems with applications in signal processing and statistics［J］.IEEE J.Select.Topics Signal Process,2007.

［14］Blake C L,Merz C J.Repository of machine learning databases［EB/OL］.(1998-01-05)［2015-03-21］.http://www.ics.uci.edi/mlearn/ MLRepositery.html.

［15］Suen C Y,Nadal C,Legault R,et al.Computer recognition of unconstrained handwritten numerals［J］.Proceedings of the IEEE, 1992,80(7):1162-1180.

（責任編輯：邵曉軍）

中圖分類號：TP301.6

文獻標識碼：A

文章編號：1007-5348（2015）08-0001-07

［收稿日期］2015-05-12

［基金項目］國家自然科學基金（61305036）；中國博士后基金（2014M560657）.

［作者簡介］徐潔（1979-），女，廣東韶關人，韶關學院數學與統計學院助理研究員，博士；研究方向：數據挖掘、計算機視覺、智能信息處理.

Local Linear Regression Classifiers for Pattern Classification

XU Jie1,2，ZHU Wen-kang2

（1.Intelligent Information Processing Lab,Guangdong University of Technology,Guangzhou 510006,Guangdong, China;2.School of Mathematics and Statistics,Shaoguan University,Shaoguan 512005,Guangdong,China）

Abstract：The linear regression classifier(LRC)has been developed and shows great potential for face recognition.However,when the size of training sample per class is large,LRC is time-consuming.Moreover,LRC cannot be applied to the large sample size cases.To solve these problems,the paper develops two local approaches. One is the K-nearest neighbor based linear regression classifier(KNN-LRC),which regresses the testing sample onto its K-nearest neighbors in each class,instead of the whole set of training samples per class.Due to the relative smaller K compared to the number of training samples per class,KNN-LRC runs faster than LRC.In addition,by tuning K,LRC can be performed in any cases,even in the large size sample cases.However,with the common K the performance of KNN-LRC is suboptimal.It further develops the auto-adaptive local regression classifier(L1-LRC),which actually is LRC with a constraint of the L1-norm regularization on the regression coefficients.L1-LRC provides a mechanism of adaptive neighbor selection,and achieves better performance than KNN-LRC.These two local classifiers are evaluated on the three public available databases.Experimental evaluation shows that the proposed methods performe better than the state-of-the-art methods.

Key words:linear regression classifier;locality;K-nearest neighbors;L1 regularization;pattern classification