基于K最近邻的L2，1范数稀疏回归分类器

徐 洁，祝文康

（韶关学院 数学与信息科学学院，广东 韶关 512005）

最近，Ren［4］等人提出了基于旋转不变范数的回归分类器(RRC).RRC的基本原理是把全体训练样本作为原子字典库，利用L2,1范数比L2范数对野点更具抗干扰性的特点，用L2,1范数代替L2范数对样本作度量，同时，对重构系数作L2,1范数的正则化约束，使得到的系数矩阵具有组稀疏特点.以此重构方式得到的正确类样本与测试样本靠得更近，而错误类样本与测试样本离得更远.实验表明，RRC有效.

然而，当训练样本的数量很大时，RRC利用全体训练样本作为原子字典库存在耗时大的缺点.另一方面，过度追求重构系数的稀疏，容易导致原本是同类样本更具优势的稀疏重构，让部分有着与测试样本相似的非同类的训练样本以更为稀疏的方式来重构测试样本.具体例子可参考图1.基于以上两方面的考虑，本文提出了基于K最近邻的范数稀疏回归分类器（KNN-SRC）.KNN-SRC利用K最近邻（KNN）［5］算法为每个测试样本量身定做了原子字典库，即每个测试样本只有K个训练样本，基于筛选后的训练样本，执行RRC算法.

1 基于旋转不变范数的回归分类器（RRC）

对一般的分类问题，不妨假设有C个模式类，n个训练样本，样本矩阵为A=［a1;a2;…;an］∈Rn×d；N个测试样本，测试样本矩阵为Y=［y2,y2,yN］∈Rd×N.

利用L2,1范数对野点更具抗干扰性的特点，对系统ATX=Y作L2,1范数度量和正则化约束，即：

其中X=［x1,x2,…,xN］∈Rn，是系数矩阵，最优的系数矩阵具有组稀疏的特点.

基于最优的稀疏系数矩阵，基于旋转不变范数的回归分类器可设计为：对给定的测试样本yj，定义δi()∈Rn为测试样本yj所联系的第i类样本的系数向量，其中为测试样本yj对应的最优稀疏系数向量.δi(j)只有对应第i类样本的元素非0，其余位置的元素均为0.计算测试样本yj的第i类的重构样本，即=ATδi(j).定义测试样本yj与的误差为：

RRC的分类准则是：如果rij=minrij(yj)，则yj被认为是第l类的样本.

2 基于K最近邻的L2,1范数稀疏回归分类器（KNN-SRC）

2.1算法原理

KNN-SRC首先利用KNN对每一个测试样本的字典原子作筛选，再基于所选择的k个最近的原子对测试样本稀疏重构，稀疏重构系数的求解可借助信号处理领域里求解多测量变量模型的方法得到.算法最后计算测试样本与类重构样本的距离.以重构误差的大小依据，对测试样本作分类判断.具体方法如下.

给定一个测试样本yj，利用KNN算法在全体训练样本中找到Kj个与其近邻样本.假设属于第i类的个最近邻样本为. 测试样本yj的Kj个最近邻样本矩阵记为.以为原子字典库，在L2,1范数度量下对测试样本yj作稀疏重构，重构系数可通过求解以下的优化问题得到：

如果近邻参数Kj＜＜n，yi=很难实现.可采用以下两种方式放松约束条件：

其中ε是任意小的正实数，ρ是正则化参数.

本文采用（6）式的目标优化函数来求解稀疏重构系数.

（7）式的目标优化函数常用于信号处理交换领域，可对拉格朗日函数执行梯度下降法，以获得迭代解［6］：

其中D是对角矩阵，对角的元素为dij==1/(2‖ui‖2)，ui是U的第i行向量.

显而易见，U*的前n行即为测试样本yj最佳的重构系数.定义第i类的刻画函数可选择测试样本yj所关联的第i类样本的重构系数，除了第i类样本所关联的系数外，()的其余系数为0.计算测试样本yj在第i类的重构样本的误差，即：

2.2 KNN-JSRC算法

输入：训练样本集A∈Rn×d；测试样本yj∈Rd,j=1,…,N；正则化参数ρ；最近邻参数Kj.

输出：yj的类标.

（1）利用KNN算法，在所有的训练样本中寻找与yj最近的Kj个近邻样本，记为∈RKj×d；

（2）设B=(,ρI)；

（3）初始化Dt∈R(n+d)×(n+d)为单位矩阵；

（4）利用公式（8）迭代计算出U；

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

end.

2.3 KNN-SRC与RRC的对比

当测试样本被极为少数的训练样本最大限度地稀疏重构，而所用于稀疏重构的训练样本与测试样本不同类，只是在形状上与测试样本极为相像，也或许只是测试样本的一部分时，KNN-SRC比RRC更为鲁棒.如图 1 例子［7］所示.对于测试样本Y，即数字“8”，用“0”，“1”到“9”等 10 类数字样本稀疏重构.很明显，用Y1和Y2重构Y的系数要比用X1、X2和X3重构Y时的系数稀疏.但同时也导致了分类器的性能下降，因为Y1和Y2明显与Y不是同类样本.因此，在执行RRC前用KNN对原子字典进行筛选，很有必要.

图1 两类手写数字的识别问题

3 实验与分析

为进一步检验KNN-JSRC的算法性能，在UCI的Wine数据库和Yale人脸数据库上比较了KNN-JSRC 与最近邻分类器(NNC)［8］，最小距离分类器(MDC)， 线性回归分类器(LRC)［9］，稀疏表示分类器(SRC)［10］和RRC的分类性能.本实验中采用了“BPDN_homotopy_function.m”［11］来计算SRC.实验过程中所有参数均采用全局到局部的搜索方法来设定.

3.1数据库的描述

Wine来自UCI数据集，是真实生活中的数据.Wine有13个特征，分3类，共178个样本.

Yale人脸数图像库中包括了15个人的165幅灰度人脸图像，每个人由11幅照片构成，这些照片在不同的表情和光照等条件下拍摄.在这个实验中，图像被处理成32×32分辨率.图2显示了Yale人脸库中某个人的11幅图像.

图2 Yale人脸数据库中部分人脸图像

3.2实验设计及结果

在Wine数据集上，分别从每类中随机取20、30和40个样本用作训练，剩余的样本用作测试.实验重复10次.所有的实验在图像原有的13维空间进行，实验最后只报告各种比较方法的平均实验结果及相应的标准方差.

在Wine数据集上，还就冗余数据对分类性能的影响作了进一步探究.从每类中随机选取20个样本用作训练，每次单一的实验都有60个训练样本，这其中包括了部分冗余的样本.给定正则化参数λ=1，让近邻的参数K作40到50的变化，相应的实验结果在图3中作了直观的描述.

在 Yale人脸数据库上，先用PCA［12］对数据进行降维.在40维的PCA子空间里再对所有的分类方法作比较.对每类样本，分别选择前3和4个样本用作训练，剩余的样本用作测试.

图3 在不同的近邻参数下，KNN-JSRC的识别率变化（其中λ=0.1）

3.3实验分析

（1）在UCI的Wine数据集上，6种分类器在不同的训练样本数下的最高平均识别率以及对应的标准方差见表1,在Yale人脸数据库上，6种分类方法在不同的训练样本下的最高识别率以及相应的维度见表2.从表1和表2可见，UCI的Wine数据库上，无论随机选取20，30还是40个样本用于训练，KNN-JSRC取得了较其它方法好的实验结果.同样，在Yale人脸库上，无论训练样本是3还是4，KNN-JSRC同样是取得了较其它分类器好的分类性能.

（2）表1中LRC的识别率只有33%，意味着只有很少一部分的样本被正确识别.这其中的原因是LRC专门为人脸识别设计的，而人脸识别本身是小样本问题，即：样本的维度大于样本的数量.在Wine上，样本的维度是13，比每类用于训练的样本数量小，即：（13＜20）.此种情况下，利用最小二乘法来求解最佳回归系的LRC系统不能正常工作.

（3）图1的实验结果表明，冗余数据在一定情况下会对数据的识别起干扰作用.在Wine数据集上，从3类的样本中选取20个样本用作训练，每次可用于训练样本数为60.由图1可见，最高识别率只需要48个样本用作训练，其余的12样本均可被视为冗余数据.从图1的曲线图可见，随着冗余的训练样本数量的增加(即：K＞48)，识别率呈下降的趋势.由此可见，对RRC的局部拓展很有必要.

表1 UCI的Wine数据训练结果

表2 Yale的人脸数据训练结果

4 结语

本文有机地整合了KNN和RRC，提出一类新颖的局部分类方法KNN-SRC.该方法有助于学习具有组稀疏特点的稀疏表示系数，引入KNN算法，对原子字典库所做的预处理，在一定程度避免了由过分追求稀疏重构带来的误分类，这对分类性能的提高有一定的帮助.KNN-SRC的分类性能在两个数据库上得以检验，从实验结果看来，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.