LDA与kNN实现手写数字识别

LDA与kNN实现手写数字识别摘要：本实验对美国国家邮政局数据库（USPostalServiceDatabase）收集的手写数字字符进行分类，首先用PCA的方法对实验数据降维，然后分别采用LDA和kNN的方法对数据进行分类，分类在训练样本上有很好的结果，但在测试样本上结果一般。一实验基础背景概述手写体阿拉伯数字，在邮政编码，统计报表，财务报表，银行票据等方面的用途广泛，故是图象处理和模式识别领域中的研究热点[1]。手写体字符由于书写者的因素,使其字符图像的随意性很大,例如,笔画的粗细、字体的大小、手写体的倾斜度、字符笔画的局部扭曲变形、字体灰度的差异等都直接影响到字符的正确识别。所以手写体数字字符的识别是数字字符识别领域内最具挑战性的课题。一幅字符图像至少包括数百个像素，如看做向量则有数百维，为了使字符图像包含的信息集中到维数尽可能少的特征向量上，同时又要使这些低维特征向量具有尽可能好的模式可分性，就首先要对字符进行特征提取。主成分分析（PCA）是研究较多的一种统计特征提取方法[2]。对于手写数字的识别，按使用特征的不同，大体可以分为两类：基于字符统计特征的识别方法和基于字符结构特征的识别方法。两类研究方法由于采用不同性质的模式特征，因此各具优势。一般来说，基于统计特征的方法，统计规律相对容易获得，并且统计规律更好的描述了一类模式的本质特征，对于与给定训练集差别不大的字符具有较高的识别率；基于字符结构特征的方法精确的描述了字符的细节特征，对书写结构较规范的字符有较高的识别率。具体方法有SVM，kNN等。本实验首先采用PCA降维，然后分别用LDA和kNN的方法实现手写数字的识别。二实验过程1.PCA降维PCA的基本思想是寻找一个最佳子空间，当高维数据x在该子空间进行投影后，所得分量具有最大方差。同时，在子空间用新分量对原始数据进行重建时，在均方误差最小的意义下逼近效果最优，即使下式最小化。21{||()||}MTiiiExWxW设12(,,,)TNx是N维随机向量，其协方差矩阵为1212{}{(,,,)}TxNNCExxEPCA的目的就是找到一个正交变换矩阵12[,,,]TM。对N维向量x进行正交变换，使得变换结果y的各分量(1,2,,)iiM间互不相关，并且当所有观测数据x沿1w方向投影时，PCA将使得到的分量1能量最大，即方差21{}E最大。这时1称为第一主分量；在与1w正交的条件下，观测数据x在2w上投影，使2能量最大，这时2称为第二主分量。对于N维向量x，由于投影后的维数MN，因此最多可以得到N个分量。在实际应用中通过截取其中()dN个主分量实现特征提取和降维。PCA有多种不同的数值计算方法，常用的是通过对x的协方差矩阵xC进行特征值分解来得到正交变换矩阵W。根据矩阵分析理论，如果x为实信号向量，协方差矩阵xC至少满足非负定的实对称矩阵，并且对于图像等自然生成的数据，xC几乎都是正定矩阵。因此TxCUVU构成xC的奇异值分解。其中12[,,,]NUuuu是xC特征向量构成的正交矩阵；12(,,,)NVdiag是特征值构成的对角阵。可以证明，当特征值按从大到小的顺序排列时，令TWU，那么U的各个基向量便是PCA的最优投影方向，按该方向对数据进行投影，得到的各主分量互不相关。因此通过求解协方差矩阵特征值对应的特征向量，可以获得各主分量对应的投影方向。2.LDA分类问题最简单的方法就是采用密度估计的思路并且假设密度是一个参数模型。假设{0,1}y并且0()(|0)fxfxY与1()(|1)fxfxY都是多元高斯分布，1/21/211()exp{()()}(2)||2Tkkkkdkfxxx，0,1k因此00|0~(,)XYN且11|1~(,)XYN。若假设01，则问题可以简化。在这种情况下，贝叶斯规则为*()argmax()kkhxx其中，111()log2TTkkkkkxx的MLE估计值为001101nSnSSnn分类规则为10*1()()()0,xxhx，其他其中，111()log2TTjjjjjxxSS011111(1),,nniiiiYYnn01:0:10111,,iiiiiYiYXXnn000111:0:10111()(),()().iiTTiiiiiYiYSXXSXXnn其中，0(1)iinY且1.iinY决策界10{:()()}xxx是线性的，所以这种方法为线性判别（LDA）。3.kNN和LSHkNN方法的基本思想即对每一个样本x，求其k个最近邻，将x进行分类。对于寻找近邻的方法，本文采用LSH[3]的方法。LSH算法的基本思想是对数据点集，利用一组具有一定约束条件的Hash函数来建立多个Hash表，使得在某种相似度量条件下，相似的点发生冲突的概率较大，而不相似的点发生冲突的概率相对较小。本文选择的Hash函数为10()0Trrxhxotherwise其中r是服从P稳定分布的抽样组成的向量。方程()gx的形式如下：12()((),(),,())tgxhxhxhx方程()gx将t个方程()(1,,)ihxit组成一个长度为t的向量，并将所有的哈希值()gx与检索点q的哈希值()gq相等的点x作为返回点。为了保证距离较近的点返回的概率增大，同时距离较远的点返回的概率减小，进一步引入l个方程()(1,,)igxil，并将l个方程()igx的返回点集合的并集作为LSH算法的返回结果。再计算q与返回结果的各点之间的距离，选取距离最小的k个点，确定q的类别。三实验结果与分析实验使用美国国家邮政局数据库（USPostalServiceDatabase）收集的手写数字字符，该字符数据库中包括7291个训练样本（USPSTrainingdata）和2007个测试样本（USPSTestingdata），每个样本都只经过简单的预处理并归一化为1616(256)像素的灰度图。该字库中字符笔画的形态，粗细和灰度等级都有显著的差别。1.PCA降维原图像如图1所示：246810121416246810121416图1原图像PCA特征值由大到小排序如图2所示：05010015020025030010-210-1100101102103104105106图2PCA的特征值可见前面的主成分起主要的作用，取前40个主成分，重建图像，结果如图3所示：246810121416246810121416图3前40主成分重建结果可见依然可以很好的识别。本文即选取前40个主成分计算。2.LDA用LDA的方法，实验训练样本识别率为92%，测试样本识别率为64%。3.kNN方程()gx为将6个方程()(1,,6)ihxi串联组成一个长度为6的向量。l的计算公式为：1loglog(1)kLp其中，为失败的概率，即至少以1的概率找到最近邻。k为6。01()()(1)wsttpufdtuuw1(1)pp实验选择的参数为：0.2,20wsf为高斯分布的密度函数。用kNN的方法，实验训练样本识别率为84%，测试样本识别率为60%。从上面的结果看，LDA比kNN的结果好些。但是理论上并不一定如此，可能因为我们对LSH算法的理解还不是很透彻。LDA与kNN在训练样本上有很好的结果，但是测试样本上结果一般。可能因为训练样本不够多，也可能是程序的原因，对LDA以及kNN的理解还有待提高。四结论与心得本实验首先用PCA的方法对实验数据降维，然后分别采用LDA和kNN的方法对数据进行分类，分类在训练样本上有很好的结果，但在测试样本上结果一般。另外，kNN的方法程序效率不高，运行需要较长时间。通过本次实验，我们对分类有了更深刻的理解，尤其对LDA以及kNN算法的理解更透彻了。参考文献[1]ChengD，YanH．Recognitionofhandwrittendigitalsbasedoncontourinformationl[J]．PatternRecognition，1998，31(3)：235—255.[2]XuLei．Theoriesofunsupervisedlearning，PCAanditsnonlinearextensionsI-A~．In：ProcessingofIEEEInternationalconferenceonNeuralnetworks941,C]，Orlando．Florida，USA，1994：1254—1257．[3]HisashiKoga,TetsuoIshibashi,andToshinoriWatanabe,FastHierarchicalClusteringAlgorithmUsingLocality-SensitiveHashing.附录1LDA识别程序clearallload'USPStrainingdata.mat';%data=reshape(traindata',[16,16,7291]);%画原图%fori=1:7291%data0=data(:,:,i);%data(:,:,i)=data0';%end%imagesc(data(:,:,1))N=40;%主成分个数f=traindata;cor=f'*f;[a,ev]=eig(cor);[ev,ind]=sort(diag(ev));ev=flipud(ev);%semilogy(ev,'r*')%画特征值a=a(:,flipud(ind));psi0=f*a;psi=psi0(:,1:N);%cdata=psi*a(:,1:N)';%画重建图像%cim=reshape(cdata',[16,16,7291]);%fori=1:7291%cim0=cim(:,:,i);%cim(:,:,i)=cim0';%end%imagesc(cim(:,:,1))%=================================================%LDA%=================================================fori=1:7291h(i)=find(traintarg(i,:)==1);ends0=find(h==1);s1=find(h==2);s2=find(h==3);s3=find(h==4);s4=find(h==5);s5=find(h==6);s6=find(h==7);s7=find(h==8);s8=find(h==9);s9=find(h==10);mu0=mean(psi(s0,:));mu1=mean(psi(s1,:));mu2=mean(psi(s2,:));mu3=mean(psi(s3,:));mu4=mean(psi(s4,:));mu5=mean(psi(s5,:));mu6=mean(psi(s6,:));mu7=mean(psi(s7,:));mu8=mean(psi(s8,:));mu9=mean(psi(s9,:));pi0=length(s0)/7291;pi1=length(s1)/7291;pi2=length(s2)/7291;pi3=length(s3)/7291;pi4=length(s4)/7291;pi5=length(s5)/7291;pi6=length(s6)/7291;pi7=length(s7)/7291;pi8=length(s8)/7291;pi9=length(s9)/7291;S00=(psi(s0,:)'-repmat(mu0,length(s0),1)')*(psi(s0,:)'-repmat(mu0,length(s0),1)')';S10=(psi(s1,:)'-re