LDA和kNN实现手写数字识别.doc

LDA与kNN实现手写数字识别 摘要：本实验对美国国家邮政局数据库（US Postal Service Database）收集的手写数字字符进行分类，首先用PCA的方法对实验数据降维，然后分别采用LDA和kNN的方法对数据进行分类，分类在训练样本上有很好的结果，但在测试样本上结果一般。 一 实验基础背景概述 手写体阿拉伯数字，在邮政编码，统计报表，财务报表，银行票据等方面的用途广泛，故是图象处理和模式识别领域中的研究热点[1]。手写体字符由于书写者的因素,使其字符图像的随意性很大,例如,笔画的粗细、字体的大小、手写体的倾斜度、字符笔画的局部扭曲变形、字体灰度的差异等都直接影响到字符的正确识别。所以手写体数字字符的识别是数字字符识别领域内最具挑战性的课题。 一幅字符图像至少包括数百个像素，如看做向量则有数百维，为了使字符图像包含的信息集中到维数尽可能少的特征向量上，同时又要使这些低维特征向量具有尽可能好的模式可分性，就首先要对字符进行特征提取。主成分分析（PCA）是研究较多的一种统计特征提取方法[2]。 对于手写数字的识别，按使用特征的不同，大体可以分为两类：基于字符统计特征的识别方法和基于字符结构特征的识别方法。两类研究方法由于采用不同性质的模式特征，因此各具优势。一般来说，基于统计特征的方法，统计规律相对容易获得，并且统计规律更好的描述了一类模式的本质特征，对于与给定训练集差别不大的字符具有较高的识别率；基于字符结构特征的方法精确的描述了字符的细节特征，对书写结构较规范的字符有较高的识别率。具体方法有SVM，kNN等。 本实验首先采用PCA降维，然后分别用LDA和kNN的方法实现手写数字的识别。 二 实验过程 1. PCA降维 PCA的基本思想是寻找一个最佳子空间，当高维数据在该子空间进行投影后，所得分量具有最大方差。同时，在子空间用新分量对原始数据进行重建时，在均方误差最小的意义下逼近效果最优， 即使下式最小化。 设是维随机向量，其协方差矩阵为 PCA的目的就是找到一个正交变换矩阵。对维向量进行正交变换，使得变换结果的各分量间互不相关，并且当所有观测数据沿方向投影时，PCA将使得到的分量能量最大，即方差最大。这时称为第一主分量；在与正交的条件下，观测数据在上投影，使能量最大，这时称为第二主分量。对于维向量，由于投影后的维数，因此最多可以得到个分量。在实际应用中通过截取其中个主分量实现特征提取和降维。 PCA有多种不同的数值计算方法，常用的是通过对的协方差矩阵进行特征值分解来得到正交变换矩阵。根据矩阵分析理论，如果为实信号向量，协方差矩阵至少满足非负定的实对称矩阵，并且对于图像等自然生成的数据，几乎都是正定矩阵。因此构成的奇异值分解。其中是特征向量构成的正交矩阵；是特征值构成的对角阵。 可以证明，当特征值按从大到小的顺序排列时，令，那么的各个基向量便是PCA的最优投影方向，按该方向对数据进行投影，得到的各主分量互不相关。 因此通过求解协方差矩阵特征值对应的特征向量，可以获得各主分量对应的投影方向。 2. LDA 分类问题最简单的方法就是采用密度估计的思路并且假设密度是一个参数模型。假设并且与都是多元高斯分布， ， 因此且。 若假设，则问题可以简化。在这种情况下，贝叶斯规则为 其中， 的MLE估计值为 分类规则为 其中， 其中，且 决策界是线性的，所以这种方法为线性判别（LDA）。 3. kNN和LSH kNN方法的基本思想即对每一个样本，求其个最近邻，将进行分类。对于寻找近邻的方法，本文采用LSH [3]的方法。 LSH算法的基本思想是对数据点集，利用一组具有一定约束条件的Hash函数来建立多个Hash表，使得在某种相似度量条件下，相似的点发生冲突的概率较大，而不相似的点发生冲突的概率相对较小。 本文选择的Hash函数为 其中是服从P稳定分布的抽样组成的向量。 方程的形式如下： 方程将个方程组成一个长度为的向量，并将所有的哈希值与检索点的哈希值相等的点作为返回点。为了保证距离较近的点返回的概率增大，同时距离较远的点返回的概率减小，进一步引入个方程，并将个方程的返回点集合的并集作为LSH算法的返回结果。 再计算与返回结果的各点之间的距离，选取距离最小的个点，确定的类别。 三 实验结果与分析 实验使用美国国家邮政局数据库（US Postal Service Database）收集的手写数字字符，该字符数据库中包括7291个训练样本（USPS Training data）和2007个测试样本（USPS Testing data），每个样本都只经过简单的预处理并归一化为像素的灰度图。该字库中字符笔画的形态，粗细和灰度等级都有显著的差别。 1. PCA降维 原图像如图1