1、LDA 与 kNN 实现手写数字识别 丁红霞 201028017726002 陈楠 2010E8017769005 摘要： 本实验对美国 国家邮政局数据库（ US Postal Service Database）收集的手写数字字符进行分类，首先用 PCA 的方法对实验数据降维，然后分别采用 LDA 和 kNN 的方法对数据进行分类，分类在训练样本上有很好的结果，但在测试样本上结果一般。 一 实验基础背景概述 手写体阿拉伯数字 ，在邮政编码，统计报表，财务报表，银行票据等方面的用途广泛，故 是图象处理和模式识别领域中的研究 热点 1。 手写体字符由于书写者的因素 ,使其字符图像的随意性很大 ,例
2、如 ,笔画的粗细、字体的大小、手写体的倾斜度、字符笔画的局部扭曲变形、字体灰度的差异等都直接影响到字符的正确识别。所以手写体数字字符的识别是数字字符识别领域内最具挑战性的课题。 一幅字符图像至少包括数百个像素，如看做向量则有数百维，为了使字符图像包含的信息集中到维数尽可能少的特征向量上，同时又要使这些低维特征向量具有尽可能好的模式可分性，就首先要对字符进行特征提取。主成分分析（ PCA）是研究较多的一种统计特征提取方法 2。 对于手写数字的识别，按使用特 征的不同，大体可以分为两类：基于字符统计特征 的识别方法和 基于字符结构特征的识别方法。两类研究方法由于采用不同性质的模式特征，因此各具优势
3、。一般来说，基于统计特征的方法，统计规律相对容易获得，并且统计规律更好的描述了一类模式的本质特征，对于与给定训练集差别不大的字符具有较高的识别率；基于字符结构特征的方法精确的描述了字符的细节特征，对书写结构较规范的字符有较高的识别率。具体方法有 SVM， kNN 等。 本实验首先采用 PCA 降维，然后分别用 LDA 和 kNN 的方法实现手写数字的识别。 二 实验过程 1. PCA 降维 PCA 的基本思想是寻找一个最佳子空间，当高维数据 x 在该子空间 进行投影后，所得分量具有最大方差。同时，在子空间用新分量对原始数据进行重建时，在均方误差最小的意义下逼近效果最优， 即使 下式 最小化。
4、21| ( ) | M TiiiE x W x W 设 12( , , , )TNx 是 N 维随机向量，其协方差矩阵为 1212 ( , , , ) TxNNC E x x E PCA 的目的就 是找到一个 正交变换矩阵 12 , , , T MW w w w 。对 N 维向量 x 进行正交变换，使得变换结果 y 的各分量 ( 1, 2, , )i iM 间互不相关，并且当所有观测数据 x 沿1w 方向投影时， PCA 将使得到的分量 1 能量最大，即方差 21E 最大。这时 1 称为第一主分量；在与 1w 正交的条件下，观测数据 x 在 2w 上投影，使 2 能量最大，这时 2 称为第二主
5、分量。对于 N 维向量 x ，由于投影后的维数 MN ，因此最多可以得到 N 个分量。在实际应用中通过截取其中 ()dN 个主分量实现特征提取和降维。 PCA 有多种不同的数值计算方法，常用的是通过对 x 的协方差 矩阵 xC 进行特征值分解来得到正交变换矩阵 W 。根据矩阵分析理论，如果 x 为实信号向量，协方差矩阵 xC 至少满足非负定的实对称矩阵，并且对于图像等自然生成的数据， xC 几乎都是正定矩阵。因此TxC UVU 构成 xC 的奇异值分解。其中 12 , , , NU u u u 是 xC 特征向量构成的正交矩阵； 12( , , , )NV diag 是特征值构成的对角阵。 可
6、以证明，当特征值 按从大到小的顺序排列时，令 TWU ，那么 U 的各个基向量便是 PCA 的最优投影方向 ，按该方向对数据进行投影，得到的各主分量互不相关。 因此通过求解协方差矩阵特征值对应的特征向量，可以获得各主分量对应的投影方向。 2. LDA 分类问题最简单的方法就是采用密度估计的思路并且假设密度是一个参数模型。假设0,1y 并且 0 ( ) ( | 0)f x f x Y与 1 ( ) ( | 1)f x f x Y都是多元高斯分布， 1/ 2 1 / 211( ) e x p ( ) ( ) ( 2 ) | | 2 Tk k k kdkf x x x ， 0,1k 因此 00| 0
7、 ( , )X Y N 且 11| 1 ( , )X Y N 。 若假设 01 ，则问题可以简化。在这种情况下，贝叶斯规则为 * ( ) a rg m a x ( )kkh x x 其中， 111( ) l o g2TTk k k k kxx 的 MLE 估计值为 0 0 1 101n S n SS nn 分类规则为 10* 1 ( ) ( )() 0, xxhx ， 其 他 其中， 111( ) l o g2 TTj j j j jx x S S 011111(1 ) , ,nniiiiYY 01: 0 : 10111,iiiii Y i YXXnn0 0 0 1 1 1: 0 : 1011
8、1( ) ( ) , ( ) ( ) .TTi i i ii Y i YS X X S X X 其中，0 (1 )iinY且1 .iinY决策界 10 : ( ) ( )x x x 是线性的，所以这种方法为线性判别（ LDA）。 3. kNN 和 LSH kNN 方法的基本思想即对每一个样本 x ，求其 k 个最近邻，将 x 进行分类。对于寻找近邻的方法，本文采用 LSH 3的方法。 LSH 算法的基本思想是对数据点集，利用一组具有一定约束条件的 Hash 函数来建立多个 Hash 表，使得在某种相似度量条件下，相似的点发生冲突的概率较大，而不相似的点发生冲突的概率相对较小。 本文选择的 Ha
9、sh 函数为 10() 0 Tr rxhx othe rwi se 其中 r 是服从 P 稳定分布的抽样组成的向量。 方程 ()gx 的形式如下： 12( ) ( ( ) , ( ) , , ( ) )tg x h x h x h x 方程 ()gx 将 t 个方程 ( )( 1, , )ih x i t 组成一个长度为 t 的向量，并将 所有的哈希值()gx 与检索点 q 的哈希值 ()gq 相等的点 x 作为返回点。为了保证距离较近的点返回的概率增大，同时距离较远的点返回的 概率减小，进一步引入 l 个方程 ( )( 1, , )ig x i l ，并将 l 个方程 ()igx的返回点集合
10、的并集作为 LSH 算法的返回结果。 再计算 q 与返回结果的各点之间的距离，选取距离最小的 k 个点，确定 q 的类别。 三 实验结果与分析 实验使用美国国家邮政局数据库（ US Postal Service Database）收集的手写数字字符，该字符数据库中包括 7291个训练样本（ USPS Training data）和 2007个测试样本（ USPS Testing data），每个样本都只经过简单的预处理并归一化为 16 16( 256) 像素的灰度图。该字库中字符笔画的形态，粗细和灰度等级都有显著的差别。 1. PCA 降维 原图像如图 1 所示： 2 4 6 8 10 12
11、14 16246810121416图 1 原图像 PCA 特征值由大到小排序 如图 2 所示： 0 50 100 150 200 250 30010-210-1100101102103104105106图 2 PCA 的特征值 可见前面的主成分起主要的作用， 取前 40 个主成分，重建图像 ，结果如图 3 所示： 2 4 6 8 10 12 14 16246810121416图 3 前 40 主成分重建结果 可见依然可以很好的识 别。 本文即选取前 40 个主成分计算。 2. LDA 用 LDA 的方法，实验 训练 样本识别率 为 92%，测试 样本识别率 为 64%。 3. kNN 方程 (
12、)gx 为 将 6 个方程 ( )( 1, , 6)ih x i 串联 组成一个长度为 6 的向量 。 l 的计算公式为： 1loglog(1 )kL p 其中， 为失败的概率，即至少以 1 的概率找到最近邻。 k 为 6。 0 1( ) ( ) (1 )w s ttp u f dtu u w 1 (1)pp 实验选择的参数为： 0.2, 20w sf 为高斯分布的密度函数。 用 kNN 的方法，实验 训练样本识别率 为 84%，测试 样本识别率 为 60%。 从上面的结果看， LDA 比 kNN 的结果好些。 但是理论上并 不一定如此，可能因为我们对 LSH 算法的理解还不是很透彻。 LDA
13、 与 kNN 在训练样本上有很好的结果，但是测试样本上结果一般。可能因为训练样本不够多，也可能是程序的原因，对 LDA 以及 kNN 的理解还有待提高。 四 结论与心得 本实验 首先用 PCA 的方法对实验数据降维，然后分别采用 LDA 和 kNN 的方法对数据进行分类，分类在训练样本上有很好的结果，但在测试样本上结果一般。另外， kNN 的方法程序效率不高，运行需要较长时间。 通过本次实验，我们对分类有了更深刻的理解，尤其对LDA 以及 kNN 算法的理解更透彻了。 参考文献 1 Cheng D， Yan H Recognition of handwritten digitals based
14、 on contour informationlJ Pattern Recognition， 1998， 31(3)： 235 255. 2 Xu Lei Theories of unsupervised learning， PCA and its nonlinear extensionsI-A In：Processing of IEEE International conference on Neural network s941,C， Orlando Florida， USA，1994： 1254 1257 3 Hisashi Koga, Tetsuo Ishibashi, and Tos
15、hinori Watanabe, Fast Hierarchical Clustering Algorithm Using Locality-Sensitive Hashing. 附录 1 LDA 识别程序 clear all load USPStrainingdata.mat; % data=reshape(traindata,16,16,7291); % 画原图 % for i=1:7291 % data0=data(:,:,i); % data(:,:,i)=data0; % end % imagesc(data(:,:,1) N=40; % 主成分个数 f=traindata; cor
16、 = 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); % for i=1:7291 % cim0=cim(:,:,i); % cim(:,:,i)=cim0; % end % imagesc(cim(:,:,1) %= % LDA %= for i=1:7291 h
17、(i)=find(traintarg(i,:)=1); end s0=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=mea
18、n(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,:)-re
19、pmat(mu0,length(s0),1)*(psi(s0,:)-repmat(mu0,length(s0),1); S10=(psi(s1,:)-repmat(mu1,length(s1),1)*(psi(s1,:)-repmat(mu1,length(s1),1); S20=(psi(s2,:)-repmat(mu2,length(s2),1)*(psi(s2,:)-repmat(mu2,length(s2),1); S30=(psi(s3,:)-repmat(mu3,length(s3),1)*(psi(s3,:)-repmat(mu3,length(s3),1); S40=(psi(
20、s4,:)-repmat(mu4,length(s4),1)*(psi(s4,:)-repmat(mu4,length(s4),1); S50=(psi(s5,:)-repmat(mu5,length(s5),1)*(psi(s5,:)-repmat(mu5,length(s5),1); S60=(psi(s6,:)-repmat(mu6,length(s6),1)*(psi(s6,:)-repmat(mu6,length(s6),1); S70=(psi(s7,:)-repmat(mu7,length(s7),1)*(psi(s7,:)-repmat(mu7,length(s7),1); S
21、80=(psi(s8,:)-repmat(mu8,length(s8),1)*(psi(s8,:)-repmat(mu8,length(s8),1); S90=(psi(s9,:)-repmat(mu9,length(s9),1)*(psi(s9,:)-repmat(mu9,length(s9),1); S0=S00/length(s0); S1=S10/length(s1); S2=S20/length(s2); S3=S30/length(s3); S4=S40/length(s4); S5=S50/length(s5); S6=S60/length(s6); S7=S70/length(
22、s7); S8=S80/length(s8); S9=S90/length(s9); S=(S00+S10+S20+S30+S40+S50+S60+S70+S80+S90)/7291; % % d0=psi(:,:)*inv(S)*mu0-0.5*mu0*inv(S)*mu0+log(pi0); d1=psi(:,:)*inv(S)*mu1-0.5*mu1*inv(S)*mu1+log(pi1); d2=psi(:,:)*inv(S)*mu2-0.5*mu2*inv(S)*mu2+log(pi2); d3=psi(:,:)*inv(S)*mu3-0.5*mu3*inv(S)*mu3+log(p
23、i3); d4=psi(:,:)*inv(S)*mu4-0.5*mu4*inv(S)*mu4+log(pi4); d5=psi(:,:)*inv(S)*mu5-0.5*mu5*inv(S)*mu5+log(pi5); d6=psi(:,:)*inv(S)*mu6-0.5*mu6*inv(S)*mu6+log(pi6); d7=psi(:,:)*inv(S)*mu7-0.5*mu7*inv(S)*mu7+log(pi7); d8=psi(:,:)*inv(S)*mu8-0.5*mu8*inv(S)*mu8+log(pi8); d9=psi(:,:)*inv(S)*mu9-0.5*mu9*inv(
24、S)*mu9+log(pi9); d=d0 d1 d2 d3 d4 d5 d6 d7 d8 d9; for i=1:7291 h(i)=find(d(i,:)=max(d(i,:); end for i=1:7291 hh(i)=find(traintarg(i,:)=1); end n=0; for i=1:7291 if h(i)=hh(i) n=n+1; end end train=n/7291 % 训练样本识别率 % % load USPStestingdata.mat; % test tf=testdata; tcor = tf*tf; ta,tev=eig(tcor); tev,t
25、ind=sort(diag(tev); tev=flipud(tev); ta=ta(:,flipud(tind); tpsi0=tf*ta; tpsi=tpsi0(:,1:N); td0=tpsi(:,:)*inv(S)*mu0-0.5*mu0*inv(S)*mu0+log(pi0); td1=tpsi(:,:)*inv(S)*mu1-0.5*mu1*inv(S)*mu1+log(pi1); td2=tpsi(:,:)*inv(S)*mu2-0.5*mu2*inv(S)*mu2+log(pi2); td3=tpsi(:,:)*inv(S)*mu3-0.5*mu3*inv(S)*mu3+log
26、(pi3); td4=tpsi(:,:)*inv(S)*mu4-0.5*mu4*inv(S)*mu4+log(pi4); td5=tpsi(:,:)*inv(S)*mu5-0.5*mu5*inv(S)*mu5+log(pi5); td6=tpsi(:,:)*inv(S)*mu6-0.5*mu6*inv(S)*mu6+log(pi6); td7=tpsi(:,:)*inv(S)*mu7-0.5*mu7*inv(S)*mu7+log(pi7); td8=tpsi(:,:)*inv(S)*mu8-0.5*mu8*inv(S)*mu8+log(pi8); td9=tpsi(:,:)*inv(S)*mu9-0.5*mu9*inv(S)*mu9+log(pi9); td=td0 td1 td2 td3 td4 td5 td6 td7 td8 td9; for i=1:2007 th(i)=find(td(i,:)=max(td(i,:); end for i=1:2007 thh(i)=find(testtarg(i,:)=1); end m=0; for i=1:2007 if th(i)=thh(i) m=m+1; end end test=m/2007 % 测试样本识别率
