最近鄰決策和SVM數(shù)字識(shí)別的實(shí)現(xiàn)和比較

1、最近鄰決策和svm數(shù)字識(shí)別的實(shí)現(xiàn)和比較這次試驗(yàn)希望通過對(duì)數(shù)字識(shí)別的實(shí)現(xiàn)了解最近鄰決策及svm的基本思想，并對(duì)丁模式 識(shí)別在實(shí)際中的應(yīng)用能夠有所認(rèn)識(shí)。這里主要討論了最近鄰決策及svm的判別函數(shù)和決策 規(guī)則以及他們的局限性。i近鄰決策規(guī)則:最近鄰決策沒有如同線性分類器那樣假設(shè)樣本是線性可分的，它沒有假設(shè)函數(shù)的形式, 也就是說不是對(duì)參數(shù)的估計(jì)。只是假設(shè)y = f(xi，x2，,xp)是連續(xù)的，每一類內(nèi)樣本應(yīng)該距離 很近。對(duì)于一個(gè)c類別的問題5，,3每類由表明類別樣本叫個(gè)i=l,2,co對(duì)未知 的樣木x,比較x與n =(叫個(gè)已知類別的樣木之間的歐氏距離，決策x為與離他最近的樣 本同類。bp：判別函數(shù)g

2、i(x) = min|x xf|, k=l,2，n： 其中x$角標(biāo)i為j類，k為j類叫中第k個(gè)。決策規(guī)則：gj(x) = min gi(x), i = l,2, ，c； x g a)j最近鄰決策的效果依賴于訓(xùn)練集樣本的選擇，為了解決過擬合的問題引入了 k-近鄰法，取未 知樣木x的k個(gè)近鄰，看著k個(gè)近鄰中多數(shù)屬于哪一類，就把x歸為那-類。設(shè)：ki，k2，.,kc分別是未知變量x的k個(gè)近鄰中屬于3i，0)2i，3c的樣木數(shù) 判別函數(shù)：gi(x) = ki決策函數(shù)：gj (x) = max kj ; x 6 u)j近鄰法很簡(jiǎn)單使川很方便但是所有的訓(xùn)練集都需要與未知樣本計(jì)算一次距離，并h比較 求取最小

3、值，對(duì)于樣木很多樣木特征很多的情況下計(jì)算量會(huì)很人而且十分占內(nèi)存是不能忍受 的。然而近鄰法的收斂性【邊肇祺】體現(xiàn)在nt 8時(shí)漸進(jìn)平均錯(cuò)誤率p滿足cp*<p<p*(2-p*)c 1p*為貝葉斯錯(cuò)誤率，c為類數(shù)。山此，理想情況下是訓(xùn)練集盡可能的大，是很孑盾的。支持向量機(jī)(svm)：對(duì)于一個(gè)線性可分的兩類問題，我們可以通過班小=h，r-v + " = °確定一個(gè)分類面把 這兩類分開。我們的目的是為了建立一個(gè)這樣的分類而，事實(shí)上這樣的分類而不是唯一確定 的。在感知器里我們通過梯度下降法優(yōu)化出一個(gè)分類器初始值的選擇、迭代步長(zhǎng)等的不同得 到的分類器也不同。那么我們需要在這些分

4、離器里找一個(gè)故好的。如圖3.10】所示，我們可以認(rèn)為direction?的分類效果要比directionl的分類效果要好, 因?yàn)閐irection2的裕量比directionl大。我們需要在這各個(gè)分類器屮選擇-個(gè)最優(yōu)的。svm 是根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論依照結(jié)構(gòu)風(fēng)險(xiǎn)最小化的原則提出的，要求實(shí)現(xiàn)兩個(gè)日的：1)兩類問題摘自sergios theodoridis p121能夠分開（經(jīng)驗(yàn)風(fēng)險(xiǎn)最?。?） margin 大化（風(fēng)險(xiǎn)上界最小）既是在保證風(fēng)險(xiǎn)最小的子集 中選擇經(jīng)驗(yàn)風(fēng)險(xiǎn)最小的函數(shù)。figure 3.10an example of a linearly separable twtxlass problem

5、 with two possible linear classifiers. 把樣本到分類而的距離進(jìn)行歸一化處理后我們得到里分類而最近的樣木g（x）= lo1這樣我們就有邊界margin：這電滿足這樣條件的樣木點(diǎn)就是我們所謂的支持向暈。這樣我們就轉(zhuǎn)化為一個(gè)優(yōu)化問題【邊肇祺】【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、上式得到判別函數(shù)式：f（x） = sgn 入）力（絢 x） + b對(duì)于不是線性可分的問題，我們可以通過加入松弛了 c來解決:mfx（入一十入i入）*力冷坷）aj > 0s. t.入= 0, 0 < aj < c由以上討論我們得到判別函數(shù)只為向量的內(nèi)積有關(guān)，因此我們可以選擇一個(gè)非線性變換 e（x）將x映射到高維空間，在低維空間不可分的問題映射到高維空間后就有可能是線性可分 的。這里我們不需要知道e（x）是什么形式的只需要關(guān)注內(nèi)枳運(yùn)算即口j。山此，可以通過構(gòu) 造核函數(shù)k（xjx）實(shí)現(xiàn)：（為入i 一扌入i入jyiyjk（xixj）這里的核函數(shù)的選擇沒有特別的方式，在【chihwei

7、hsu】中推薦使用徑向基函數(shù)。印刷數(shù)字的識(shí)別：實(shí)驗(yàn)屮我們通過最近鄰法和svm實(shí)現(xiàn)了對(duì)于印刷數(shù)字的識(shí)別，svm的實(shí)現(xiàn)是利川林智 仁老師的libsvm i具，最近鄰法是自己的代碼實(shí)現(xiàn)的。代碼后附。實(shí)驗(yàn)數(shù)據(jù)整理如下：（原始數(shù)據(jù)見后附表）訓(xùn)練集個(gè)數(shù)：53個(gè)測(cè)試集個(gè)數(shù)：108個(gè)判別方法實(shí)驗(yàn)參數(shù)錯(cuò)分樣本形式錯(cuò)分樣本數(shù)正確率svm徑向基函數(shù)c=100 g=0.0015-8(1) 6-5(2) 6-3(1)496.30%多項(xiàng)式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%這兩種方法還是可以比較不錯(cuò)的實(shí)現(xiàn)卬刷數(shù)

8、字的識(shí)別的止確率最好能達(dá)到96.30% 另外根據(jù)肩附表中我們可以看到svm的訓(xùn)練結(jié)杲與核函數(shù)的選擇有很密切的關(guān)系，合適的核函數(shù)【chihwei hsu可以得到較好的結(jié)果。實(shí)驗(yàn)總結(jié)：最近鄰法算法簡(jiǎn)單很容易實(shí)現(xiàn)，但是它的效果與訓(xùn)練集的選擇有很大的關(guān)系，收斂性是 在滿足樣木足夠多的條件下的，這在實(shí)際屮是很難得到的。另外計(jì)算量很人在樣本及樣本特 征很多的情況下占內(nèi)存會(huì)很大速度會(huì)很慢。svm根據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化提出了使margin最大化的優(yōu)化的方法，并且可以通過松弛子, 及適當(dāng)?shù)暮撕瘮?shù)把在低維空間中線性不可分的問題投影到高維空間使得在一定的松弛條件 下線性可分。但是核函數(shù)的選擇是一個(gè)問題，試驗(yàn)中我們?cè)嚋惓?/p>

9、來的一個(gè)核函數(shù)。林智仁老 師提供了一個(gè)工具可以通過交叉驗(yàn)證的方式得到一個(gè)較好的核函數(shù)。參考資料：邊肇祺，張學(xué)工，模式識(shí)別，清華大學(xué)出版社,第二版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模式識(shí)別課件附：實(shí)驗(yàn)程序最近鄰規(guī)則

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%載入數(shù)據(jù)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訓(xùn)練集%test_set測(cè)試集%miss_num錯(cuò)分樣木數(shù)%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%把輸入圖像轉(zhuǎn)換為nnclasser的格式% a輸入圖像% type是否為兩類問題% flag類型標(biāo)記% b返回轉(zhuǎn)換后矩陣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%載入數(shù)據(jù)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 ,'系統(tǒng)提