LDA与kNN实现手写数字识别

1、用于手写数字识别的线性判别分析和kNN在这个实验中，美国邮政服务数据库收集的手写数字字符被分类。首先用主成分分析法对实验数据进行降维，然后用线性判别分析和kNN对数据进行分类。分类在训练样本上有很好的结果，但在测试样本上的结果是一般的。实验基本背景概述手写阿拉伯数字广泛用于邮政编码、统计报表、财务报表、银行票据等。因此，它们是图像处理和模式识别领域的研究热点1。由于作者的因素，手写字符在其字符图像中具有很大的随机性。例如，笔画的粗细、字体的大小、笔迹的倾斜、字符笔画的局部变形以及字体灰度的差异直接影响字符的正确识别。因此，手写数字字符识别是数字字符识别领域中最具挑战性的课题。字符图像至少包含数

2、百个像素，作为一个矢量，它有数百个维度。为了将字符图像中包含的信息集中在维数尽可能小的特征向量上，同时使这些低维特征向量具有尽可能好的模式可分性，必须首先提取字符。主成分分析是一种统计特征提取方法，已经被研究了很多2。根据不同的使用特点，手写体数字的识别一般可分为两类：基于字符统计特征的识别方法和基于字符结构特征的识别方法。这两种研究方法各有优势，因为它们采用了不同的模型特征。一般来说，基于统计特征的统计规则相对容易获得，并且统计规则更好地描述了一类模式的基本特征，对于与给定训练集差别不大的字符具有更高的识别率。基于字符结构特征的方法准确描述了字符的细节特征，对于书写结构更加规范的字符具有更高

3、的识别率。具体方法有SVM法、kNN法等。实验中，首先用主成分分析法进行降维，然后分别用线性判别分析和近邻法进行手写数字识别。2.实验过程1.主成分分析维度缩减主成分分析的基本思想是寻找一个最优子空间。当在这个子空间中投影高维数据时，得到的分量具有最大的方差。同时，当用新的分量重建子空间时，在最小均方误差的意义上，近似效果是最佳的，即使下面的公式被最小化。假设它是一个多维随机向量，其协方差矩阵为主成分分析的目的是寻找一个正交变换矩阵。对维度向量进行正交变换，使得变换结果的每个分量互不相关，当所有观测数据都沿该方向投影时，主成分分析将使得到的分量能量最大，即方差最大。这被称为第一主成分。在正交条

4、件下，观测数据向上投影，使能量最大化，称为第二主成分。对于维度向量，由于投影维度，可以获得最大数量的组件。在实际应用中，特征提取和降维是通过截取其中一个主成分来实现的。主成分分析有许多不同的数值计算方法。常用协方差矩阵的特征值分解来获得正交变换矩阵。根据矩阵分析理论，如果是实信号向量，协方差矩阵至少满足非负定实对称矩阵，并且几乎所有自然生成的数据如图像都是正定矩阵。由此形成的奇异值分解。其中正交矩阵由特征向量组成；它是由特征值组成的对角矩阵。可以证明，当特征值按从大到小的顺序排列时，每个基向量就是主成分分析的最佳投影方向，数据在这个方向上投影，得到的主成分互不相关。因此，通过求解对应于协方差矩

5、阵的特征值的特征向量，可以获得对应于每个主分量的投影方向。2.伦敦发展署最简单的Knn和LSHkNN方法的基本思想是找到每个样本的最近邻并对其进行分类。对于寻找邻居的方法，本文采用了LSH 3。LSH算法的基本思想是一组数据点，使用一组带有一定约束的哈希函数来建立多个哈希表，这样在一定的相似性度量条件下，相似点之间的冲突概率较高，不同点之间的冲突概率相对较低。本文选择的哈希函数是其中一个向量由服从P稳定分布的样本组成。方程式的形式如下：该等式将形成一个长度向量，并且所有与检索点的散列值相等的散列值将被作为返回点。为了保证从距离较近的点返回的概率增加，而从距离较远的点返回的概率降低，进一步引入2

6、个方程，将2个方程的返回点集的并集作为LSH算法的返回结果。然后计算每个点与返回结果之间的距离，并选择距离最小的点来确定类别。三个实验结果及分析该实验使用美国邮政服务数据库收集的手写数字字符，包括7，291个训练样本(美国邮政服务训练数据)和2007个测试样本(美国邮政服务测试数据)。每个样本都经过简单的预处理，并归一化为像素的灰度级。在这个字体库中，字符笔画的形状、粗细和灰度有很大的不同。1.主成分分析维度缩减原始图像如图1所示。图1原始图像主成分分析特征值从大到小排序，如图2所示。图2主成分分析的特征值可以看出，前主成分起主要作用。取前40个主成分，重建图像。结果如图3所示。图3前40名主

7、成分重构结果显然，它仍然可以被很好地识别。本文选取了前40个主成分进行计算。2.伦敦发展署采用线性判别分析方法，实验训练样本的识别率为92%，测试样本的识别率为64%。3.kNN该方程将六个方程串联起来，形成一个长度为6的向量。的计算公式是：其中，最近邻被发现的概率为失败的概率，即至少为。六个。实验中选择的参数为：它是高斯分布的密度函数。采用kNN方法，实验训练样本的识别率为84%，测试样本的识别率为60%。从以上结果来看，线性判别分析优于kNN。然而，理论上不一定如此，也许是因为我们对LSH算法的理解不是很透彻。LDA和kNN在训练样本上有很好的效果，但在测试样本上效果一般。对LDA和kNN

8、的理解还有待提高，要么是因为没有足够的训练样本，要么是因为程序的原因。4.结论和经验本实验采用主成分分析法对实验数据进行降维，并分别采用线性判别分析和近邻法对数据进行分类。分类在训练样本上有很好的结果，但在测试样本上的结果是一般的。此外，kNN的方法效率低下，需要很长时间才能运行。通过这个实验，我们对分类有了更深的了解，尤其是线性判别分析和kNN算法。参考1程德德，颜宏.基于轮廓信息的手写数字识别J.中国医学，2001 .模式识别，1998，31(3):235255。2徐磊。无监督学习理论，主成分分析及其非线性扩展。在：美国电气和电子工程师学会国际神经网络会议处理，奥兰多。美国佛罗里达，199

9、4:12541257。3阿桔久史，石桥哲雄和渡边俊雄，使用局部敏感散列的快速分层聚类算法。附录1 LDA识别程序清除所有加载USPStrainingdata.mat% data=整形(traindata，16，16，7291)；%插图i=1:7291的百分比% data0=数据(:I)；% data(:I)=data 0；% end% imagesc(数据(:1)N=40主成分的百分比f=traindatacor=f * fa，ev=eig(cor)。ev，ind=排序(diag(ev)；ev=fli pud(ev)；% semilog (ev，r *)%绘制特征值a=a(:fli pud(i

10、nd)；psi0=f*a。psi=psi0(:1:牛顿)；% cdata=psi*a(:1:N)；%绘制重建图像% cim=整形(cdata，16，16，7291)；i=1:7291的百分比% cim0=cim(:I)；% cim(:I)=CIM 0；% end% imagesc(cim(:1)%=% LDA%=对于i=1:7291h(i)=find(traintarg(i，)=1)；目标s0=find(h=1)；S1=查找(h=2)；S2=查找(h=3)；S3=查找(h=4)；s4=查找(h=5)；s5=查找(h=6)；S6=查找(h=7)；S7=查找(h=8)；S8=查找(h=9)；s9=

11、查找(h=10)；mu0=平均值(psi(s0，)；mu1=平均值(psi(s1，)；mu2=平均值(psi(s2，)；mu3=平均值(psi(s3，)；mu4=平均值(psi(s4，)；mu5=平均值(psi(s5，)；mu6=平均值(psi(s6，)；mu7=平均值(psi(s7，)；mu8=平均值(psi(s8，)；mu9=平均值(psi(s9，)；pi0=长度(s0)/7291；pi1=长度(S1)/7291；pi2=长度(S2)/7291；pi3=长度(S3)/7291；pi4=长度(S4)/7291；pi5=长度(S5)/7291；pi6=长度(S6)/7291；pi7=长度(s7

12、)/7291 .pi8=长度(S8)/7291；pi9=长度(S9)/7291；S00=(psi(S0，)-repmat(mu0，长度(s0)，1)*(psi(s0，)-repmat(mu0，长度(s0)，1)；s10=(psi(s1，)-repmat(mu1，长度(S1)，1)*(psi(s1，)-repmat(mu1，长度(S1，1)；s20=(psi(s2，)-repmat(mu2，长度(S2)，1)*(psi(s2，)-repmat(mu2，长度(S2，1)；s30=(psi(s3，)-repmat(mu3，长度(S3)，1)*(psi(s3，)-repmat(mu3，长度(S3)，1

13、)；s40=(psi(s4，)-repmat(mu4，长度(S4)，1)*(psi(s4，)-repmat(mu4，长度(S4)，1)；s50=(psi(s5，)-repmat(mu5，长度(S5)，1)*(psi(s5，)-repmat(mu5，长度(S5)，1)；s60=(psi(s6，)-repmat(mu6，长度(S6)，1)*(psi(s6，)-repmat(mu6，长度(S6)，1)；s70=(psi(s7，)-repmat(mu7，长度(S7)，1)*(psi(s7，)-repmat(mu7，长度(S7)，1)；s80=(psi(s8，)-repmat(mu8，长度(S8)，1)

14、*(psi(s8，)-repmat(mu8，长度(S8)，1)；s90=(psi(s9，)-repmat(mu9，长度(S9)，1)*(psi(s9，)-repmat(mu9，长度(S9)，1)；S0=S00/长度(s0)；S1=S10/长度(S1)；S2=S20/长度(S2)；S3=S30/长度(S3)；S4=S40/长度(S4)；S5=S50/长度(S5)；S6=S60/长度(S6)；S7=S70/长度(S7)；S8=S80/长度(S8)；S9=S90/长度(S9)；s=(S00 S10 S20 S30 S40 S50 S60 S70 S80 S90)/7291；% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %