最近邻决策和SVM数字识别的实现和比较..docxVIP

最近邻决策和SVM数字识别的实现和比较这次试验希望通过对数字识别的实现了解最近邻决策及SVM的基本思想，并对于模式识别在实际中的应用能够有所认识。这里主要讨论了最近邻决策及SVM的判别函数和决策规则以及他们的局限性。最近邻决策规则：最近邻决策没有如同线性分类器那样假设样本是线性可分的，它没有假设函数的形式，也就是说不是对参数的估计。只是假设是连续的，每一类内样本应该距离很近。对于一个C类别的问题，每类由表明类别样本个。对未知的样本X, 比较X与个已知类别的样本之间的欧氏距离，决策X为与离他最近的样本同类。即：判别函数其中角标i为类，k为类中第K个。决策规则 :最近邻决策的效果依赖于训练集样本的选择，为了解决过拟合的问题引入了k-近邻法，取未知样本X的k个近邻，看着k个近邻中多数属于哪一类，就把X归为那一类。设：分别是未知变量X的k个近邻中属于的样本数判别函数：决策函数：近邻法很简单使用很方便但是所有的训练集都需要与未知样本计算一次距离，并且比较求取最小值，对于样本很多样本特征很多的情况下计算量会很大而且十分占内存是不能忍受的。然而近邻法的收敛性【边肇祺】体现在时渐进平均错误率P满足为贝叶斯错误率，C为类数。由此，理想情况下是训练集尽可能的大，是很矛盾的。支持向量机（SVM）：对于一个线性可分的两类问题，我们可以通过确定一个分类面把这两类分开。我们的目的是为了建立一个这样的分类面，事实上这样的分类面不是唯一确定的。在感知器里我们通过梯度下降法优化出一个分类器初始值的选择、迭代步长等的不同得到的分类器也不同。那么我们需要在这些分离器里找一个最好的。如图3.10所示，我们可以认为direction2的分类效果要比 direction1的分类效果要好，因为direction2的裕量比direction1大。我们需要在这各个分类器中选择一个最优的。SVM是根据统计学习理论依照结构风险最小化的原则提出的，要求实现两个目的：1）两类问题能够分开（经验风险最小）2）margin最大化（风险上界最小）既是在保证风险最小的子集中选择经验风险最小的函数。把样本到分类面的距离进行归一化处理后我们得到里分类面最近的样本g(x) = 1。这样我们就有边界margin：这里满足这样条件的样本点就是我们所谓的支持向量。这样我们就转化为一个优化问题【边肇祺】【Sergios Theodoridis】：建立拉格朗日方程并引入KKT条件得到：由上式得到判别函数式：对于不是线性可分的问题，我们可以通过加入松弛子C来解决：由以上讨论我们得到判别函数只与向量的內积有关，因此我们可以选择一个非线性变换将x映射到高维空间，在低维空间不可分的问题映射到高维空间后就有可能是线性可分的。这里我们不需要知道是什么形式的只需要关注內积运算即可。由此，可以通过构造核函数实现：这里的核函数的选择没有特别的方式，在【Chih-Wei Hsu】中推荐使用径向基函数。印刷数字的识别：实验中我们通过最近邻法和SVM实现了对于印刷数字的识别，SVM的实现是利用林智仁老师的libsvm工具，最近邻法是自己的代码实现的。代码后附。实验数据整理如下：（原始数据见后附表）训练集个数：53个测试集个数：108个判别方法实验参数错分样本形式错分样本数正确率SVM径向基函数C=100 g=0.0015-8(1) 6-5(2) 6-3(1)496.30%多项式C=100 g=0.01 d=15-8(1) 6-5(2) 6-3(1)496.30%最近邻法5-6(1) 6-5(5) 6-8(1)793.52%这两种方法还是可以比较不错的实现印刷数字的识别的正确率最好能达到96.30%另外根据后附表中我们可以看到SVM的训练结果与核函数的选择有很密切的关系，合适的核函数【Chih-Wei Hsu】可以得到较好的结果。实验总结：最近邻法算法简单很容易实现，但是它的效果与训练集的选择有很大的关系，收敛性是在满足样本足够多的条件下的，这在实际中是很难得到的。另外计算量很大在样本及样本特征很多的情况下占内存会很大速度会很慢。SVM根据结构风险最小化提出了使margin最大化的优化的方法，并且可以通过松弛子，及适当的核函数把在低维空间中线性不可分的问题投影到高维空间使得在一定的松弛条件下线性可分。但是核函数的选择是一个问题，试验中我们试凑出来的一个核函数。林智仁老师提供了一个工具可以通过交叉验证的方式得到一个较好的核函数。参考资料：边肇祺,张学工,模式识别,清华大学出版社,第二版Sergios Theodoridis,Pattern Recognition,4th,ISBN 978-1-59749-272-0Chih-Wei Hsu, Chih-Chung Chang, Chih-Jen Lin, A Practical Gui