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

1、最近邻决策和svm数字识别的实现和比较这次试验希望通过对数字识别的实现了解最近邻决策及svm的基本思想，并对丁模式 识别在实际中的应用能够有所认识。这里主要讨论了最近邻决策及svm的判别函数和决策 规则以及他们的局限性。i近邻决策规则:最近邻决策没有如同线性分类器那样假设样本是线性可分的，它没有假设函数的形式, 也就是说不是对参数的估计。只是假设y = f(xi，x2，,xp)是连续的，每一类内样本应该距离 很近。对于一个c类别的问题5，,3每类由表明类别样本叫个i=l,2,co对未知 的样木x,比较x与n =(叫个已知类別的样木之间的欧氏距离，决策x为与离他最近的样 本同类。bp：判别函数g

2、i(x) = min|x xf|, k=l,2，n： 其中x$角标i为j类，k为j类叫中第k个。决策规则：gj(x) = min gi(x), i = l,2, ，c； x g a)j最近邻决策的效果依赖于训练集样本的选择，为了解决过拟合的问题引入了 k-近邻法，取未 知样木x的k个近邻，看着k个近邻中多数属于哪一类，就把x归为那-类。设：ki，k2，.,kc分别是未知变量x的k个近邻中属于3i，0)2i，3c的样木数 判别函数：gi(x) = ki决策函数：gj (x) = max kj ; x 6 u)j近邻法很简单使川很方便但是所有的训练集都需要与未知样本计算一次距离，并h比较 求取最小

3、值，对于样木很多样木特征很多的情况下计算量会很人而且十分占内存是不能忍受 的。然而近邻法的收敛性【边肇祺】体现在nt 8时渐进平均错误率p满足cp*<p<p*(2-p*)c 1p*为贝叶斯错误率，c为类数。山此，理想情况下是训练集尽可能的大，是很孑盾的。支持向量机(svm)：对于一个线性可分的两类问题，我们可以通过班小=h，r-v + " = °确定一个分类面把 这两类分开。我们的目的是为了建立一个这样的分类而，事实上这样的分类而不是唯一确定 的。在感知器里我们通过梯度下降法优化出一个分类器初始值的选择、迭代步长等的不同得 到的分类器也不同。那么我们需要在这些分

4、离器里找一个故好的。如图3.10】所示，我们可以认为direction?的分类效果要比directionl的分类效果要好, 因为direction2的裕量比directionl大。我们需要在这各个分类器屮选择-个最优的。svm 是根据统计学习理论依照结构风险最小化的原则提出的，要求实现两个日的：1)两类问题摘自sergios theodoridis p121能够分开（经验风险最小）2） margin 大化（风险上界最小）既是在保证风险最小的子集 中选择经验风险最小的函数。figure 3.10an example of a linearly separable twtxlass problem

5、 with two possible linear classifiers. 把样本到分类而的距离进行归一化处理后我们得到里分类而最近的样木g（x）= lo1这样我们就有边界margin：这电满足这样条件的样木点就是我们所谓的支持向暈。这样我们就转化为一个优化问题【边肇祺】【sergiostheodoridis】：(3.72>(3.73>minimize j(u wq) = -|w|2 subject to yjiv xi + g)二 1.建立拉格朗h方程并引入kkt条件得到:赏（扫右_ i牙入心3*刃）(387)subject to= 0/=!a >0(3«9)由

6、上式得到判别函数式：f（x） = sgn 入）力（绚 x） + b对于不是线性可分的问题，我们可以通过加入松弛了 c来解决:mfx（入一十入i入）*力冷坷）aj > 0s. t.入= 0, 0 < aj < c由以上讨论我们得到判别函数只为向量的內积有关，因此我们可以选择一个非线性变换 e（x）将x映射到高维空间，在低维空间不可分的问题映射到高维空间后就有可能是线性可分 的。这里我们不需要知道e（x）是什么形式的只需要关注內枳运算即口j。山此，可以通过构 造核函数k（xjx）实现：（为入i 一扌入i入jyiyjk（xixj）这里的核函数的选择没有特别的方式，在【chihwei

7、hsu】中推荐使用径向基函数。印刷数字的识别：实验屮我们通过最近邻法和svm实现了对于印刷数字的识别，svm的实现是利川林智 仁老师的libsvm i具，最近邻法是自己的代码实现的。代码后附。实验数据整理如下：（原始数据见后附表）训练集个数：53个测试集个数：108个判别方法实验参数错分样本形式错分样本数正确率svm径向基函数c=100 g=0.0015-8(1) 6-5(2) 6-3(1)496.30%多项式c=100 g=0.01 d=l5-8(1) 6-5(2) 6-3(1)496.30%最近邻法5-6(1) 6-5(5) 6-8(1)793.52%这两种方法还是可以比较不错的实现卬刷数

8、字的识别的止确率最好能达到96.30% 另外根据肩附表中我们可以看到svm的训练结杲与核函数的选择有很密切的关系，合适的核函数【chihwei hsu可以得到较好的结果。实验总结：最近邻法算法简单很容易实现，但是它的效果与训练集的选择有很大的关系，收敛性是 在满足样木足够多的条件下的，这在实际屮是很难得到的。另外计算量很人在样本及样本特 征很多的情况下占内存会很大速度会很慢。svm根据结构风险最小化提出了使margin最大化的优化的方法，并且可以通过松弛子, 及适当的核函数把在低维空间中线性不可分的问题投影到高维空间使得在一定的松弛条件 下线性可分。但是核函数的选择是一个问题，试验中我们试凑出

9、来的一个核函数。林智仁老 师提供了一个工具可以通过交叉验证的方式得到一个较好的核函数。参考资料：边肇祺，张学工，模式识别，清华大学出版社,第二版sergios theodoridis,pattern recognition,4th,isbn 978-1-59749-272-0chih-wei hsu, chihchung chang, chih-jen lin, a practical guide to support vector classification, .tw/cjlin, october 2, 2008模式识别课件附：实验程序最近邻规则

10、：nearest_class mclc; clear;train_set = init_nn();test_se t = init_rm();correct_ratez miss_num, label =nn_classifier (train_setz test_set);miss_numcorrect_rateinit_nn m%nnclasser 初始化%the_set 返回整合后样本矩阵function the_set =rpath = uigetfile(1 *.path1r 1 select the bmp-file');i = 0;for index_l = 0:1:9c

11、lear file_num;for index_2 = 0:1:20%载入数据file_num(1) = num2str(index_l);file_num(2) = 1 -1;tmp_num = num2str(index_2);tmp_len = length(tmp_num);file_num(3 : tmp_len+2) = tmp_num;file_num(tmp_len+3 : tmp_len+6) = 1 .bmp 1;file_read = fopen(path,file_num,1r1);if file_read = -1break;end%图形载入tmp_data = im

12、read(path,file_num);%tmp_data = pre_process(tmp_data);tmp_data = threshold_trs(tmp_data,140);%imshow(tmp_data);tmp_data = im2double(tmp_data);%tmp_data = (tmp_data 一 128)/128;% 样本矩阵%if i=0the_set = transform_nn (tmp_da1, index_l);elseif i>=lthe_set =the_set transform_nn(tmp_data,1,index_l);endi =

13、 i + 1;%fclose(file_read);end % end for index_2end % end for index_lendnn_classifier.m%最近邻分类器%train_set训练集%test_set测试集%miss_num错分样木数%functioncorrect_rate, miss_numz label =nn_classifier (train_set z test_set)fea_train,num_train=size(train_set);fea_test, num_test=size(test_set);miss_num=0;for index_t

14、est= 1:1:num_testtest=test_set(:,index_test);min_dist=le+30;for index_train=1:1:num_traintrain=train_set:, index_train);v = train(1:1:fea_train-l) 一 test(1:1:fea_test-l);% dist=norm(v,2); % euclead distance% cosdist=acos(test1*train/(norm(test,2)*norm(train,2);distancetrain (fea_train);if min_dist &

15、gt;= dist min_dist = dist; label (index_test) endendif label(index_test)= test(fea_test)miss_num = miss_num + 1;end endcorrect_rate = (num_test - miss_num)/num_test; label = label'endtransform_nn m%把输入图像转换为nnclasser的格式% a输入图像% type是否为两类问题% flag类型标记% b返回转换后矩阵function b = transform_nn( aftype,flag

16、)c,r = size (a);b(1:c*r) = a(1:c*r); if type=0if flag =1b(c*r + 1) = 1; else b(c*r + 1) = -1; end %end for flag elseb (c*r + 1) = flag;endb = b* ;end %end for functionsvminit mclear; clc;filename,path = uigetfile (1 *.path 1,1 select the bmp-file1);i = 0;for index_l = 0:1:9clear file_num;for index_2

17、 = 0:1:20%载入数据file_num(1) = num2str(index_l);file_num(2) = * - *;tmp_num = num2str(index_2); tmp_len = length(tmp_num);file_num(3 : tmp_len+2) = tmp_num;file_num(tmp_len+3 : tmp_len+6) = 1.bmp 1;file_read = fopen(path,file_numa 1r1); if file_read = -1break;end%图形载入tmp_data = imread(path,file_num);%t

18、mp_data = pre_process(tmp_data);tmp_data = threshold_trs(tmp_data,140); %imshow(tmp_data);tmp_data = im2double(tmp_data);%tmp_data = (tmp_data 一 128)/128;%写出svm txt文件%if strcmp (filename, 1 train.path')file_txt = 1 train.txt1;transform(tmp_dataz file_txt,1,index_l);elseif strcmp(filename, 1 test.path1)file_txt = 'test.txt1;transform(tmp_datm,file_txt,1,index_l);end % end for ifi = i + 1;%fclose(file_read);end % end for index_2end % end for index_lmsgbox ( 1 finished 1 ,'系统提