(机器学习作业)基于稀疏表示的数据缩减算法.doc

基于稀疏表示的数据缩减学 院： 学 号： 姓 名： 年 级： 导 师： 目 录1 稀疏表示理论31.1 稀疏表示基本理论31.2 基于稀疏表示的人脸识别及实验42 基于稀疏表示的数据缩减算法62.1 算法思想62.1.1 实例分析72.1.2 对比分析82.2 人脸数据库介绍及实验仿真结果102.2.1 orl库2的仿真结果与分析102.2.2 pie人脸数据库7,8的仿真结果与分析142.2.3 extended yale b库的仿真结果及分析163 小结18参考文献19附录 论文程序源代码201 稀疏表示理论1.1 稀疏表示基本理论稀疏表示理论在实际中越来越得到广泛的应用，例如图像去噪、重构、编码，模式识别与机器视觉等领域。2009年wright et al1等人根据稀疏表示和压缩感知理论提出基于稀疏表示的人脸识别方法（sparse representation based classification，src），算法提出两个假设前提：（1）同类样本处于同一个线性子空间，任何一个测试样本均可以用来自该类的训练样本线性表示；（2）用所有的训练样本构成字典，则测试样本在该字典上的表示是稀疏的，同时该稀疏系数包含了样本的类别信息。因此，直接用所有类的训练样本当字典，通过最小化稀疏表示系数的范数来求解该稀疏系数，分类时将测试样本归属于最小残差的一类，在图像识别中取得了较好的结果。假定测试样本图像，其中（表示图片长度方向像素个数，表示图片高度方向像素个数），将整个图像库中的所有训练样本直接作为字典，测试样本可以通过字典中的原子进行线性表示。而理论上每个训练样本仅与字典中同类的所有原子相关性最大，与非同类的原子相关性较小或者无关，因此最理想状态下，测试样本仅仅需要使用字典中同类原子线性表示进行重构，而其它类别的样本系数值很小，几乎为零。由上述理论可知，测试样本属于第类，则它仅需要由同类的个原子可以线性组合表示，表达式如下所示： （1-1）若在所有字典上进行线性表示，则表达式如下： （1-2）其中a和分别为： （1-3）解集为，在理论上讲，应是稀疏的，即仅有少数元素数值为非零的，大部分元素值为零值或很小。按照稀疏表示的求解模型，求解下面方程： （1-4）其中代表范数，表示向量中非零元数的个数，对范数的求解是一个np问题，可通过穷举法求解，但是所需时间较长，而理论证明，若信号在字典上的表示足够稀疏，则稀疏表示系数的求解等价于求解一下 范数模型： （1-5）1.2 基于稀疏表示的人脸识别及实验orl人脸库2共有40个类，每类有10张图片，在本实验中采用orl库，将每类前5张图片作为该类的字典，则所有类组合成的字典将拥有200个原子，其中图1.1就是第一类样本的第6张图片在该字典上求解的系数分布，横轴为原子，纵轴为原子对应的系数值。从上图可知，系数是稀疏的，大部分系数数值为0，且属于同一类的样本解出来的系数较大，即对应字典中的原子与要表示的测试样本相关性越大，也就是同类原子对样本的重构能力更强，非同类原子对样本的重构能力很弱。为了对测试样本进行分类，利用上面求得系数的稀疏分布，分别用字典中的每一类字典的所有原子样本以及它们对应的系数值对测试样本进行线性重构，然后用重构出来的图片分别和原始测试样本比较求得残差，假如类别数为，则共有项残差，而测试样本属于重构残差最小的那一类。其中每类字典对测试样本的重构残差公式如下： （1-6）其中，表示只提取出第类样本所对应的系数，即仅使用第类样本重构测试样本。根据公式（1-6），完善上述实验，求出每一类字典对测试样本的重构残差，如下图1.2所示：图1.1基于稀疏表示的系数分布图示可见，第一类字典对测试样本的重构残差最小，其它类字典对样本的重构残差较大，即测试样本和第一类字典原子最相似，因此应属于第一类，与实验已知结论相符。综上所述，基于稀疏表示的人脸识别算法流程如下：给定训练样本矩阵：，有个类的样本，共有个样本，给定测试样本，并对和字典的每列原子进行归一化。求解下面最小范数：计算残差：对测试样本进行分类图1.2src算法重构残差图2 基于稀疏表示的数据缩减算法针对目前的数据缩减算法都不能较好地刻画出数据的空间相互关系和模式的空间分布。此外，它们对含有遮挡、腐蚀的数据进行分析时，性能退化很明显。而稀疏表征从感知角度较好地刻画了数据的相互关系和分布，因此，提出了从稀疏表征学习入手，选择出具有代表性的数据，使得一方面能较好地刻画出数据的内在几何特性和空间分布，另一方面对腐蚀、遮挡具有好的鲁棒性。并在常用的人脸样本库上进行实验，选择具有代表性的样本，然后用pca分类器对选出的样本图像进行分类识别以验证选出的样本的好坏。通常原始的人脸库样本的数据量非常大，在此情况下进行分类很耗时，而且过多的数据也会造成误判，影响最终的识别率。利用稀疏表示的原理去除数据集中相似冗余的样本,使训练样本集精简但又同时具有较高的信息量。因此对原始人脸库样本数据进行缩减期望达到的效果是：1）减少冗余数据量，提高计算速度；2）选出的样本代表性强，不影响分类的识别率或对其影响较小。2.1 算法思想假设原始样本集共有个样本，设定稀疏表示系数阈值为，重构残差阈值为。用所有训练样本做字典，即。对字典中的每一个原子，用除去自身的样本做字典，求解稀疏表示系数，生成系数矩阵，求解模型为：，利用系数矩阵从中选择样本，使其能很好地描述：若中某元素满足，则将其取出构成新的系数矩阵。将中元素对应的中的原子取出，构成新的字典。用系数矩阵和字典对样本进行重构，得到其重构残差为：。若满足：，则将从中删除掉。最后得到缩减后的字典即训练样本集为：。用图形表示上面的思想如图2.1所示： 图2.1算法流程图2.1.1 实例分析以pie数据库中的pose-05部分为例，选取第一个人的第二张图片为测试样本，然后选取前10个人的的任意20张照片（除了第一个人的第二张图片）组成训练样本集，即字典，图2.2为用字典对测试样本进行稀疏表示所得的所有系数画出的图像，以及非零系数对应的字典中原子的图片。实验结果得五个系数非零对应的图片分别为17号、4号、15号、11号、1号，它们所对应的系数值分别为0.6435，0.2103，0.0923，0.0297，0.0085，剩余的系数值并非绝对为零，而是非常小，几乎为零。而且用17号，4号，15号，11号，1号图像对2号测试图像进行重构时，重构残差非常小，说明我们选择出来的图像能够包含2号测试图像中的信息。因此，对训练样本集来说，2号图像是冗余图像，可以将其从训练样本集中删去。 图2.22号图像稀疏表示后的系数及其对应的图片2.1.2 对比分析目前的数据缩减去冗余的算法都是采用计算距离的方式，即认为在某一区域内距离近的为相似数据或重复数据，可以删除。同样是上例，求出2号测试图像与所有图像的欧氏距离如图2.4所示，为了更好地看到对比结果，从中取出前30个距离放大显示，并对上述非零系数对应的原子的距离用棕红和红色加注，如图2.5所示：从图2.5可以看出非零系数值对应的原子与2号测试图像的距离都不长，但是并不是距离短的其稀疏系数值为非零，比如11号图像，这也就是利用稀疏表示选择样本与一般距离选样的区别，更说明了稀疏描述是从人的感知角度刻画了数据间的相互关系，能更好的描述数据。图2.42号测试图像与所有训练样本的归一化距离图2.52号测试图像与前30个训练样本的归一化距离基于稀疏表示的数据缩减算法（1）输入训练样本矩阵，总共有类人脸的幅图像，以及测试样本矩阵，并将测试样本集与训练样本集做各列归一化处理，pca 降维处理。（2）样本选择：for do计算上每一个样本在除去自身的剩余样本字典时的稀疏表示系数，生成系数矩阵；if ；用稀疏表示系数大于所对应的原子构成新的字典对进行重构，重构残差为：；if 删除训练样本集中的样本endendend最后可得缩减后的训练样本集为：（3）用缩减后的训练样本集做投影空间即特征脸空间：，将训练样本集与测试样本集都投影在特征脸空间得：，（4）测试样本投影特征与第类训练样本之间的欧氏距离： （5）将测试样本判为与训练样本投影特征欧氏距离最小的样本所对应的类别： ，其中为测试样本的类别（6）计算出正确分类的测试样本个数与测试样本总数的比值，即识别率reco。2.2 人脸数据库介绍及实验仿真结果本论文中采用常见的人脸数据库来检验算法的可行性与有效性。2.2.1 orl库2的仿真结果与分析orl库包含40个人的400幅图像，每个人10幅不同的图像，每幅图像大小为112*96。这些图像的拍摄时间不同，面部表情（如睁眼、闭眼、微笑等）和面部配饰（如戴眼镜、不戴眼镜等）均有变化，并且头部的倾斜度也有过改变。在实验中，所有图像都被裁剪为32*32像素的灰度图像，然后被拉成列，保存为.mat文件，此文件在实验中表示为。orl库中第17个人的样本图像如图2.6所示：图2.6orl库第17个人的原始图像本实验中我们随机选取每类图像中的8张图片用作训练样本，其余用作测试样本，则训练样本总数为320张，测试样本总数为160。实验时，将测试样本与字典都降到100维，并通过pca算法对测试样本进行分类识别。在本文提出的的算法中有两个可变的参数：稀疏表示系数阈值和重构残差阈值。因此在orl数据库上我们做两组实验。本实验中除训练样本与测试样本再次随机选取外，其余的实验条件都相同，每组实验做10次，最后的识别率为10次实验结果的平均值。第一组实验：选定=0.145保持不变，让稀疏表示系数阈值发生变化，观察在不同的稀疏阈值条件下的压缩效果以及识别率。表2.1和2.2列出了不同稀疏系数阈值下的实验结果，包括识别率（%）、选样样本数以及它们的平均值和方差，图2.7画出了识别率以及选样样本数随系数阈值变化的曲线。从图2.7中可以看出，随着稀疏表示系数阈值的增大，选择出的样本数减少，即缩减后的样本数越少。当稀疏阈值为0.3时，选择的样本数仅为135，缩减率较高（缩减率=（总的样本数-选样样本数）/总的样本数）可以达到57.8%，此时识别率为95.13%，接近未选样时的95.25%，满足我们的识别要求。表2.1库上=0.145时的识别率（%）orl12345678910averagestd0.0596.2598.7596.2592.5096.2592.5097.5095.0092.5097.5095.252.490.0896.2598.7595.0092.5096.2591.2597.5095.0092.5097.5095.252.490.0996.2597.5095.0092.5096.2591.2597.5095.0092.5097.5095.132.320.1095.0097.5096.2592.596.2591.2597.5095.0092.5097.5095.132.320.1293.7597.5095.0091.2596.2591.2597.5095.0092.5097.5094.752.490.1595.0097.5095.0090.0096.2591.2597.5093.7592.5097.5094.632.700.1693.7597.5095.0090.0095.0091.2597.5095.0092.5097.5094.502.650.2093.7596.2595.0090.0096.2591.2597.5095.0090.2597.5094.382.720.2596.2596.2595.0091.2596.2591.2597.595.0092.5097.5094.882.390.3096.2598.7595.0092.5096.2591.2597.5095.0091.2597.5095.132.66对比96.2598.7595.0092.5096.2591.2597.5095.0092.5097.5095.252.49表2.2库上=0.145时的选样样本数orl12345678910averagestd0.052852892922872902932912912962922913.100.082462422452442442462452492412402442.660.092242282272312272332292352252262293.540.102132062112182102202162242112122145.360.121831851911911861931961951931901904.350.151581591671631651671641681681611643.680.161491531601551571611601641581561574.320.201421391431411421481411431461401432.720.251331341361341411401391381421351373.220.301291381301341351321421471371271356.15对比3203203203203203203203203203203200.00 图2.7orl上识别率与选样样本数随稀疏阈值变化曲线第二组实验：固定稀疏表示系数阈值=0.3，改变重构残差阈值，观察在不同残差阈值条件下的缩减效果及识别率。表2.3和2.4列出了不同重构残差阈值下的实验结果，包括识别率（%）、选样样本数以及它们的平均值和方差，图2.3画出了识别率以及选样样本数随系数阈值变化的曲线。表2.3库上=0.3时的识别率（%）orl12345678910averagestd0.0596.2597.5095.0091.2596.2591.2597.5085.0093.7597.5094.134.000.0897.597.5095.0090.0096.2592.5097.5095.0092.5097.5095.132.660.1097.5096.2595.0090.0096.2591.2597.5095.0091.2597.5094.752.870.14596.2598.7595.0092.5096.2591.2597.5095.0091.2597.5095.132.660.1595.0097.5095.0092.5096.2590.0097.5093.7592.5097.5094.752.550.1896.2596.2595.0090.0096.2591.2597.5095.0092.5097.5094.752.620.2093.7597.5095.0092.5096.2591.2597.5093.7591.2597.5094.632.500.2593.7597.5095.0092.5095.0091.2597.5093.7592.5097.5094.632.290.2892.5097.5095.0092.5095.0090.0097.5093.7593.7597.5094.502.510.3092.5097.5095.0090.0095.0090.0097.5093.7593.7597.5094.252.84对比96.2598.7595.0092.5096.2591.2597.5095.0092.5097.5095.252.49表2.4库上=0.3时的选样样本数orl12345678910averagestd0.051972042012012012101912082001952015.400.081571711631651591641671721671631654.490.101491561561481571541541651541501544.630.1451291381301341351321421471371271345.850.151281311321301321401381461391271246.590.181351421431401461341431651471411448.150.201181181241251211371371311271201246.820.251141151131141121161171201201171162.600.281151121131161151151141181151141151.560.301151111131131141131161131151131141.36对比3203203203203203203203203203203200.00从图2.8可以看出，本组实验中识别率有两个峰值点，分别是=0.08和=0.145，识别率都为95.13%，而其选择的样本数分别为165和134。识别率较高，并且缩减效果较好，可以达到我们的识别要求。图2.8orl上识别率与选样样本数随残差阈值变化曲线2.2.2 pie人脸数据库7,8的仿真结果与分析pie库由卡耐基梅隆大学创建，所谓pie就是姿势（pose），光照（illumination）和表情（expression）。pie库是由68个人的41368幅人脸图像组成，其中包括了每个人的13种姿态条件，43种光照条件和4种表情下的图像，且每张图像被裁剪为64*649。本实验中所用的pie数据库中有68类图像，每类有49张图像。图2.9给出了pie人脸库中第一个人的12幅图像，从图可以看出这些图像的光照强度是不同的。图2.9pie人脸库中第一个人的12张图像本实验中我们随机选取每类图像中的20张图像用作训练样本，剩余的29张图像用作测试样本，则训练样本数为1360张图像，测试样本数为1972张图像。实验时将测试样本与字典都降到200维，并用pca算法对测试样本进行分类识别。本实验中做了一组实验，即设定残差阈值=0.05，通过调节稀疏表示系数阈值，得到不同缩减效果下的选样样本数，即缩减后的训练样本集。本实验总共做十次，最后的实验结果为十次实验的平均值。表2.5和2.6列出了不同稀疏系数阈值下的实验结果，包括识别率（%）、选样样本数以及它们的平均值，图2.10画出了识别率以及选样样本数随稀疏表示系数阈值变化的曲线。表2.5pie库上时的识别率（%）pie12345678910average0.1074.1478.5580.4878.5580.4895.3991.3895.6992.1992.9085.970.1573.7878.5081.0378.4581.0395.6491.6395.7491.7992.7586.040.1874.1478.5581.0378.5581.0395.3391.7995.7992.0992.7086.100.2074.2478.5081.3478.5081.3495.4491.5395.7492.1992.8086.160.2374.2478.7081.3478.7081.3495.6991.5395.8492.0492.6586.210.2574.3978.7081.4478.7081.4495.6491.4895.8992.0492.8586.260.2874.3478.8081.5478.7081.5495.6491.5895.7992.1992.9586.310.3074.3978.7081.5478.7081.5495.6491.5395.8492.1993.0586.310.3374.1978.9081.4478.9081.4495.6491.5395.8992.2493.1086.330.3574.1478.9081.5478.9081.5495.5991.6395.9492.1493.1086.340.4074.3978.7081.8078.7581.8095.6991.7395.9492.2993.1586.42对比74.6578.9081.9078.9081.9095.8492.3995.8492.6593.2086.66表2.6pie库上时的选样样本数pie12345678910average0.104635485575485575255375214835105250.154475455915455915885565365684795390.185005556385556386246155705485205760.205405916615916616556575915895586090.236006427156427157247286356536026660.256336377476377477667736927136396980.286806807936807938358347487787027520.307097178217178218788717758077587870.337727558507558509509098258628268350.3580579087679087610069098568938808680.409138769908769901158978963962982969对比13601360136013601360136013601360136013601360图4.10pie上识别率与选样样本数随稀疏阈值变化曲线图2.10反映出随着稀疏表示系数阈值的增大，选择出来的样本数逐渐增多，识别率也越来越高。由于pie库中数据较多，压缩程度过大势必会影响到对测试样本的识别效果。当和0.30时，测试样本的识别率都为86.31，选样样本数为752和787，缩减率为44.71%和42.13%，去除掉近一半的冗余样本。压缩效果较好并且识别率较高。因此，本文中的缩减算法在pie库上的效果较好。2.2.3 extended yale b库的仿真结果及分析extended yale b人脸库包含38个人取自不同光照条件下的2414张正面人脸图像，除第11-17个人外，每个人都有64张图像，这些图像含有丰富的光照和表情的变化，每张图像大小为168*192像素。图2.11给出了yale b库中的图像样本，从中可以看出这些图像只限于光照的变化。图2.11yale b人脸库中图像样本本实验中，将yale b库中的第11-17类除去，使用余下的31人的图像，从每类图像中随机选取32幅作为训练样本，余下的图像用于测试，则训练样本数与测试样本数都为992幅，所有图像尺寸归一化为32*32。表2.7yale b上的识别率（%）yale b12345678910average0.0578.4365.0282.8678.1376.1172.0880.7578.2379.0376.1176.670.0877.9265.0282.2677.9275.4071.9880.8578.0278.6375.8176.380.1077.6264.2182.4677.8275.7171.7780.7577.6278.3375.6076.190.1577.4264.3182.5678.0274.8071.7780.3476.7178.5375.2075.970.1877.8264.4282.5678.2374.9071.2780.4477.3279.0375.5076.150.2077.8264.3182.8678.2374.8071.8680.4477.3278.6376.0176.230.2578.2364.6283.1778.3375.7171.7780.7577.8279.1376.1176.560.2878.2364.8283.0678.2375.5071.9880.6577.8279.1376.0176.540.3078.2364.9283.0678.2375.8171.9880.4477.8278.9376.1176.560.3578.2364.8283.2778.2375.6073.3880.4477.8279.5476.2176.750.4078.2364.8282.9678.3375.5072.3880.6577.9279.3376.3176.64对比78.4364.8283.3778.5376.0172.2880.5477.8279.2376.1176.71表2.8yale b上的选样样本数yale b12345678910average0.056876216736576836516686736596606630.085595175455525425475655655795155490.105154735175125035085335205434845160.155294765425465185035435545564865250.186015196025895675465835996015275730.206305456576335936006136696335876160.257366547477336876717047507026617050.287837077907747237007477897406937450.307927218187957357197738097647247650.358357728548377747728148428147788090.40879815884888822838864889871819857对比992992992992992992992992992992992实验时，将测试样本与字典都降到200维，并通过pca算法对测试样本进行识别分类。在该数据库上做一组实验，设定重构残差阈值，通过调节稀疏表示系数阈值得到不同压缩效果下的选样样本数。本实验总共做十次，最后的实验结果为十次实验的平均值。表2.7和2.8列出了不同稀疏系数阈值下的实验结果，包括识别率（%）、选样样本数以及它们的平均值，图2.12画出了识别率以及选样样本数随系数表示系数阈值变化的曲线。图2.12yale b上识别率与选样样本数随残差阈值变化曲线从图2.12中可以看出yale b库中的样本经过筛选后，识别率超过了未选样时的识别率。当时，识别率为76.75%，超过了未选样时的识别率，但选样样本数较多为809。当时，识别率达到76.67%，与未选样似的76.71%接近，此时的样本数为663。虽然压缩效果不好（仅为35.68%），但在一定程度上去除了冗余样本，并且识别率较高。说明该算法在yale b库上效果较好。3 小结本文基于稀疏表示的理论基础，提出了基于稀疏表示的数据缩减算法，然后利用经典的pca算法对测试样本进行分类。通过在不同的人脸数据库上进行多次试验，实验结果表明本文中的算法能够在一定程度上去除冗余样本，并且对测试样本的识别率较高，具有可行性。参考文献1j.wright,a.y.yang,a.ganesh,s.s.sastry,y.ma.robust face recognition via sparserepresentationj. ieee transactions on pattern analysis and machine intelligence, 2009, 31(2):210-227.2the orl database. http:/www.cam-orl.co.uk3谢德艳.局部信息保持投影及应用d.西安电子科技大学硕士论文.2010.4何国辉,甘俊英.pca类内平均脸法在人脸识别中的应用研究j.五邑大学,信息学院.2006.5黄旗明.分割巨型stl格式形体文件的关键技术 j.机械, 2000,27(3):21- 22.6高全学.基于子空间分析的人脸识别研究d.西北工业大学博士学位论文.2005.7郝秀娟.基于图论的多样性描述及应用d.西安电子科技大学硕士论文.2011.8sim t, baker s, bsat m. the cmu pose, illumination, and expression (pie) database. procj.ieee intl conf. automatic face and gesture recognition, may 2002.9j. yang, d. zhang, a. f. frangi, and j. y. yang, two-dimensional pca: a new approach to appearance-based face representation and recognitionj. ieee trans. pattern anal.mach.intell,2004,vol.26,no. 1:131-137.附录 论文程序源代码clc ; clear all;classnum = 68;classimagenum = 49;classtrainnum =20;classtestnum = 29;trainnum = classnum*classtrainnum;testnum = classnum*classtestnum;num_bases = classnum*classtrainnum;result = ;fid = fopen（pie.txt,a+）;fprintf（fid,%20s,class number:）;fprintf（fid,%20g,classnum）;fprintf（fid,%20s,training number:）;fprintf（fid,%20grn,classtrainnum）; load pie_pose05_64x64;load pie_sss_12;for iii = 1:10 ss = sss（iii,:）;for i = 1:classnum for j = 1:classtrainnum index1 = （i-1）*classtrainnum+j; index2 = （i-1）*classimagenum+ss（j）; trainbase（:,index1） = double（fea（index2,:）; endendclear i j index1 index2;for i = 1:classnum for j = 1:classtestnum index1 = （i-1）*classtestnum+j; index2 = （i-1）*classimagenum+ss（classtrainnum+j）; testbase（:,index1） = double（fea（index2,:）; endendclear i j index1 index2;ix = repmat（1:classnum,classtrainnum,1）; trlab = ix（:）; ix = repmat（1:classnum,classtestnum,1）; telab = ix（:）; ix = repmat（1:classnum,classtrainnum,1）; labdiction = ix（:）; x1=trainbase testbase; d,n = size（x1）;%= normalization =%normx1=zeros（d,n）;for i=1:n normx1（:,i）=x1（:,i）/norm（x1（:,i）;endx1 = normx1; clear normx1;trx =x1（:,1:classtrainnum*classnum）;tex = x1（:,classtrainnum*classnum+1:classimagenum*classnum）;par.dim = 200; % the pca dimension disc_set,disc_value,mean_image= eigenface_f（trx,par.dim）; trainbase = disc_set* trx; par.lambda = 0.01; lab = 1:num_bases; mu = 0.3; lambda = 0.11; e = ; index = ; xout = ; fprintf（fid,%20s,mu:）; fprintf（fid,%20g,mu）;fprintf（fid,%20s,wuchayuzhi:）;fprintf（fid,%20grn,lambda）;for i = 1:num_bases diction = trainbase; diction（:,find（lab=i） = 0; s = zeros（size（diction,2）,1）; x0 = diction*trainbase（:,i）; x = l1eq_pd（x0,diction, trainbase（:,i）,1e-3）; s（find（xmu）,:） = x（find（xmu）,:）; e = （trainbase（:,i）