基于SVM的手寫(xiě)數(shù)字識(shí)別的應(yīng)用與實(shí)現(xiàn)【畢業(yè)作品】

基于SVM的手寫(xiě)數(shù)字識(shí)別的應(yīng)用與實(shí)現(xiàn)摘要手寫(xiě)數(shù)字識(shí)別是字符識(shí)別的一個(gè)分支，雖然只是識(shí)別簡(jiǎn)單的10個(gè)數(shù)字，但卻有著非常大的實(shí)用價(jià)值。在文獻(xiàn)檢索、郵政系統(tǒng)、辦公自動(dòng)化、表格錄入、銀行票據(jù)處理等方面都有著廣泛的應(yīng)用。手寫(xiě)數(shù)字雖然只有10個(gè)種類(lèi)，但很多情況下，對(duì)識(shí)別的精度要求非常高，而且每個(gè)人都有不同的字跡，想要做到準(zhǔn)確的識(shí)別，就很有難度了。支持向量機(jī)(SupportVectorMachine，SVM)最初于20世紀(jì)90年代由Vapnik提出，是基于統(tǒng)計(jì)學(xué)習(xí)理論的一項(xiàng)新技術(shù)，是借助于最優(yōu)化方法解決機(jī)器學(xué)習(xí)問(wèn)題的新工具，具有許多引人注目的優(yōu)點(diǎn)和有前途的實(shí)驗(yàn)性能，在人臉識(shí)別，手寫(xiě)數(shù)字識(shí)別，網(wǎng)頁(yè)分類(lèi)等方面有非常理想的效果。所以，本文將支持向量機(jī)應(yīng)用于手寫(xiě)數(shù)字識(shí)別，希望能夠得到不錯(cuò)的精度。手寫(xiě)數(shù)字識(shí)別一共有10類(lèi)樣本，是一個(gè)多分類(lèi)問(wèn)題，本文將多個(gè)支持向量機(jī)的二類(lèi)分類(lèi)器組合起來(lái)構(gòu)成一個(gè)多類(lèi)分類(lèi)器，以便實(shí)現(xiàn)手寫(xiě)數(shù)字識(shí)別。我們把樣本分為訓(xùn)練樣本集和測(cè)試樣本集，訓(xùn)練樣本集與測(cè)試樣本集都要經(jīng)過(guò)預(yù)處理得到點(diǎn)陣數(shù)據(jù)，然后再經(jīng)過(guò)特征提取，用來(lái)訓(xùn)練識(shí)別器以及進(jìn)行識(shí)別?！娟P(guān)鍵詞】手寫(xiě)數(shù)字識(shí)別，支持向量機(jī)，分類(lèi)器，特征提取，預(yù)處理

ApplicationandImplementationofHandwritingNumeralsRecognitionBasedonSVMAbstractHandwritingnumeralsrecognitionisabranchofthecharacterrecognition,althoughjustrecognitionsimple10figures,butithasaverybigpracticalvalue.Intheliteratureretrieval,thepostalsystem,officeautomation,formentry,bankbillsareprocessing,etcinawiderangeofapplications.Handwritingnumeralsalthoughonly10species,butinmanycases,theaccuracyrequirementofrecognitionisveryhigh,andeverybodyhasdifferenthandwriting,togetaccurateidentification,isverydifficult.TheSupportVectorMachine(SVM)intheearly1990s,isputproposedbyVapnik,indataminingisanewtechnology,isafurtheroptimizationmethodofmachinelearningproblemsolvingnewtools,hasmanycompellingadvantagesandpromisingexperimentalperformance,infacerecognition,Handwritingnumeralsidentification,classificationofwebpagesisveryidealeffect.So,thispaperwillsupportvectormachineappliedinHandwritingnumeralrecognition,thehopecanobtaingoodaccuracy.Handwritingnumeralsidentifyingatotaloftenkindsofsamples,isamultipleclassificationproblem,thispaperwillmoresupportvectormachineclassifieriicombinedformamultitudeofclassifier,inordertorealizeHandwritingnumeralrecognition.Weputthesamplesaredividedintothetrainingsamplesetandtestingsamples,thetrainingsamplesetandtestsamplesarethroughpretreatmentgetbitmapdata,thenafterfeatureextractionandrecognitionusedtotrainidentifier.【Keywords】HandwritingNumeralRecognition,SupportVectorMachine,Classifier,FeaturesExtraction,Preprocess

目錄摘要 IAbstract II1緒論 11.1研究背景 11.1.1手寫(xiě)數(shù)字識(shí)別概述 11.1.2研究的困難和問(wèn)題 11.1.3研究動(dòng)態(tài) 21.2手寫(xiě)數(shù)字識(shí)別的一般方法 31.2.1識(shí)別流程 31.2.2識(shí)別方法 32SVM（支持向量機(jī)）的相關(guān)研究 52.1SVM概述 52.1.1理論背景 52.1.2SVM簡(jiǎn)介 62.1.3SVM的優(yōu)點(diǎn) 72.2VC維 82.3SVM原理 82.3.1分類(lèi)問(wèn)題與機(jī)器學(xué)習(xí) 82.3.2兩類(lèi)可分問(wèn)題的線性分類(lèi)機(jī) 92.3.3非線性支持向量機(jī)——核函數(shù)方法 113數(shù)字識(shí)別預(yù)處理過(guò)程 133.1二值化 133.2平滑去噪 133.3歸一化 144基于SVM數(shù)字識(shí)別過(guò)程 164.1SVM分類(lèi)算法 164.1.1一對(duì)多（One-Versus-All，OVA）算法 164.1.2一對(duì)一（One-Versus-One，OVO）算法 174.1.3兩種分類(lèi)算法的優(yōu)缺點(diǎn)比較 184.2核函數(shù)的選擇 184.3實(shí)驗(yàn)結(jié)果及分析 194.3.1基于線性核函數(shù)的SVM分類(lèi)器的測(cè)試 204.3.2基于二次核函數(shù)的SVM分類(lèi)器的測(cè)試 204.3.3基于多項(xiàng)式核函數(shù)的SVM分類(lèi)器的測(cè)試 214.3.4基于徑向基核函數(shù)的SVM分類(lèi)器的測(cè)試 224.3.5測(cè)試結(jié)果分析 235結(jié)論 24參考文獻(xiàn) 251緒論1.1研究背景1.1.1手寫(xiě)數(shù)字識(shí)別概述阿拉伯?dāng)?shù)字作為唯一被世界各國(guó)通用的符號(hào)，是人類(lèi)文明發(fā)展的標(biāo)志之一，也是人類(lèi)交流溝通的主要媒介。在人們?nèi)粘Ｉ町?dāng)中，離不開(kāi)數(shù)字的使用，我們每天都要進(jìn)行大量的數(shù)字工作處理，比如郵政編碼、統(tǒng)計(jì)報(bào)表、財(cái)務(wù)報(bào)表、銀行匯款轉(zhuǎn)賬等等，如此繁瑣的數(shù)字工作處理占去了我們很大一部分時(shí)間，空間。而對(duì)于，計(jì)算機(jī)大范圍普及，人工智能高度發(fā)展的當(dāng)今社會(huì)，利用手寫(xiě)數(shù)字識(shí)別系統(tǒng)代替人們進(jìn)行這樣繁重的手工勞動(dòng)，備受?chē)?guó)內(nèi)外人士的高度重視。目前，市場(chǎng)上也出現(xiàn)了一些手寫(xiě)體數(shù)字識(shí)別的應(yīng)用，在許多范圍如稅務(wù)、財(cái)務(wù)、金融等領(lǐng)域中都有廣泛的應(yīng)用，有較高的商業(yè)價(jià)值。于是數(shù)字識(shí)別的準(zhǔn)確度問(wèn)題又浮上水面，但是現(xiàn)在還沒(méi)有哪個(gè)手寫(xiě)體數(shù)字識(shí)別器能達(dá)到100%的識(shí)別準(zhǔn)確率。因此，進(jìn)一步提高手寫(xiě)數(shù)字識(shí)別系統(tǒng)的識(shí)別性能是現(xiàn)在手寫(xiě)數(shù)字識(shí)別系統(tǒng)研究的重點(diǎn)[1]。數(shù)字識(shí)別在學(xué)科上是圖像處理和模式識(shí)別領(lǐng)域中的研究課題之一，主要研究利用計(jì)算機(jī)識(shí)別書(shū)寫(xiě)在紙上的阿拉伯?dāng)?shù)字。數(shù)字識(shí)別系統(tǒng)一般由圖像采集、信號(hào)預(yù)處理、特征提取、分類(lèi)識(shí)別等幾個(gè)部分組成，識(shí)別系統(tǒng)的識(shí)別方式可分為印刷體數(shù)字識(shí)別跟手寫(xiě)體數(shù)字識(shí)別，而后者根據(jù)書(shū)寫(xiě)時(shí)間跟識(shí)別時(shí)間的關(guān)系，又可分為聯(lián)機(jī)手寫(xiě)體識(shí)別與脫機(jī)手寫(xiě)體識(shí)別兩種，即實(shí)時(shí)手寫(xiě)體數(shù)字識(shí)別與非實(shí)時(shí)手寫(xiě)體數(shù)字識(shí)別。其中脫機(jī)手寫(xiě)體數(shù)字識(shí)別由于書(shū)寫(xiě)者得關(guān)系，其字符的隨意性較大，如筆畫(huà)的扭曲度、粗細(xì)，字體的大小、傾斜度等差異，都將影響到字符識(shí)別的準(zhǔn)確度。所以，系統(tǒng)的實(shí)現(xiàn)具有很大的困單，是字符識(shí)別領(lǐng)域內(nèi)極具挑戰(zhàn)性的課題。1.1.2研究的困難和問(wèn)題上文也有提到，數(shù)字的類(lèi)別只有10種，結(jié)構(gòu)也很簡(jiǎn)單，識(shí)別起來(lái)似乎也很簡(jiǎn)單。但是事實(shí)上，數(shù)字識(shí)別的識(shí)別率還不如更加復(fù)雜的漢字識(shí)別。也正是因?yàn)閿?shù)字的筆畫(huà)非常簡(jiǎn)單，同一數(shù)字的寫(xiě)法千差萬(wàn)別，世界各國(guó)，各地區(qū)的書(shū)寫(xiě)習(xí)慣、書(shū)寫(xiě)方式都有很大不同，很難做到兼顧到各地區(qū)各種寫(xiě)法的數(shù)字識(shí)別系統(tǒng)的高識(shí)別率。而且，數(shù)字的字形都很接近，比如：“1”和“7”，“3”和“8”，由于個(gè)人書(shū)寫(xiě)習(xí)慣不同，書(shū)寫(xiě)出來(lái)很容易變得很相似，在數(shù)字識(shí)別系統(tǒng)中，要準(zhǔn)確區(qū)分開(kāi)來(lái)，就變得很困單。另外，在實(shí)際應(yīng)用中，手寫(xiě)數(shù)字識(shí)別的精確度要求也比漢字識(shí)別要嚴(yán)格的多。因?yàn)?，?shù)字識(shí)別常被用到的領(lǐng)域是財(cái)會(huì)、金融等，這方面的嚴(yán)格性要求不言而喻，往往一字之差，帶來(lái)的差別與損失是無(wú)法估量的。但是數(shù)字識(shí)別系統(tǒng)的要求并不僅僅是識(shí)別率，需要處理的數(shù)據(jù)一般都是大批量的，所以，即使有了高的識(shí)別率，沒(méi)有相當(dāng)?shù)乃俣纫彩切胁煌ǖ?。但是高精度與高速度一般是相矛盾的，因此，研發(fā)高性能的數(shù)字識(shí)別系統(tǒng)是一項(xiàng)挑戰(zhàn)性非常高的項(xiàng)目。1.1.3研究動(dòng)態(tài)光學(xué)字符識(shí)別（OpticalCharacterRecognition，OCR）技術(shù)就是利用光學(xué)技術(shù)對(duì)文字和字符進(jìn)行掃描，確定其形狀，然后利用字符識(shí)別方法將形狀翻譯轉(zhuǎn)換成計(jì)算機(jī)內(nèi)碼的過(guò)程。早在50年代，歐美國(guó)家就開(kāi)始了OCR的研究，將浩如煙海的字符材料掃描進(jìn)計(jì)算機(jī)，讓其進(jìn)行信息處理。到了六七十年代，世界各國(guó)也相繼開(kāi)始了OCR的研究。OCR可以說(shuō)是一種不確定的技術(shù)研究，因?yàn)闋砍兜綍?shū)寫(xiě)者的書(shū)寫(xiě)習(xí)慣，識(shí)別的方法，訓(xùn)練測(cè)試的樣本等因素，都會(huì)影響到識(shí)別的正確率。其正確率就像一個(gè)趨勢(shì)函數(shù)，只能趨近，而不能達(dá)到100%，大家都以100%作為研究目標(biāo)。世界上第一個(gè)將該技術(shù)付諸實(shí)用的是日本東芝公司研發(fā)的手寫(xiě)體郵政編碼識(shí)別的信函自動(dòng)分揀系統(tǒng)，之后，隨著時(shí)間的推移，各種各樣的產(chǎn)品、系統(tǒng)相繼問(wèn)世。中國(guó)對(duì)于OCR方面的研究起步相對(duì)較晚，直到1989年，清華大學(xué)率先推出了國(guó)內(nèi)第一套中文OCR軟件——清華文通TH一OCR，至此中國(guó)的OCR技術(shù)正式起步。隨著研究的進(jìn)展，文字和數(shù)字識(shí)別市場(chǎng)逐漸穩(wěn)步擴(kuò)大，用戶遍布世界各地。近幾年來(lái)，中國(guó)國(guó)內(nèi)對(duì)于手寫(xiě)數(shù)字識(shí)別的研究還是相當(dāng)成功的，取得了很大的成績(jī)。手寫(xiě)數(shù)字識(shí)別技術(shù)可以用于郵政編碼、統(tǒng)計(jì)報(bào)表、財(cái)務(wù)報(bào)表、銀行票據(jù)等信息處理，一旦研究成功并投入應(yīng)用，將產(chǎn)生巨大的社會(huì)和經(jīng)濟(jì)效益。隨著信息化的發(fā)展，計(jì)算機(jī)的普及，人工智能的研究，手寫(xiě)數(shù)字識(shí)別的應(yīng)用也日益廣泛，因此，研究高識(shí)別率、高速度的高性能手寫(xiě)數(shù)字識(shí)別系統(tǒng)有著重大的現(xiàn)實(shí)意義。當(dāng)然隨著這些的發(fā)展，市場(chǎng)的推動(dòng)，手寫(xiě)數(shù)字識(shí)別技術(shù)將會(huì)取得更大的進(jìn)展。1.2手寫(xiě)數(shù)字識(shí)別的一般方法1.2.1識(shí)別流程手寫(xiě)數(shù)字識(shí)別一般來(lái)說(shuō)，首先把數(shù)字圖像經(jīng)過(guò)預(yù)處理，然后將得到的數(shù)據(jù)進(jìn)行特征提取直接輸入識(shí)別器進(jìn)行識(shí)別得到結(jié)果，如圖1-1所示。訓(xùn)練樣本訓(xùn)練樣本數(shù)字圖像預(yù)處理特征提取識(shí)別器訓(xùn)練測(cè)試樣本數(shù)字圖像預(yù)處理特征提取識(shí)別器結(jié)果圖1-1數(shù)字識(shí)別流程圖將數(shù)字識(shí)別的流程歸納一下，可分為預(yù)處理，特征提取跟識(shí)別器三個(gè)方面：（1）預(yù)處理，通過(guò)歸一化，二值化，細(xì)化等步驟，對(duì)圖像進(jìn)行處理，以提高精度。（2）特征提取，對(duì)于已經(jīng)經(jīng)過(guò)預(yù)處理的手寫(xiě)數(shù)字圖像，形狀多樣，數(shù)量繁多，樣本處在一個(gè)高維空間中，通過(guò)映射到低維空間或者變換的方法來(lái)提高精確度與速度。（3）識(shí)別器，經(jīng)過(guò)以上處理的手寫(xiě)數(shù)字圖像，通過(guò)選定的分類(lèi)器來(lái)實(shí)現(xiàn)數(shù)字識(shí)別。1.2.2識(shí)別方法對(duì)手寫(xiě)數(shù)字進(jìn)行前期處理后可以得到一個(gè)8×8或是16×l6的矩陣，然后需要對(duì)該矩陣的內(nèi)容進(jìn)行分類(lèi)，識(shí)別。在過(guò)去的幾十年中，研究者們提出了許多種用于識(shí)別手寫(xiě)數(shù)字的技術(shù)。目前而言最常用的方法有神經(jīng)網(wǎng)絡(luò)、決策樹(shù)和SVM方法。（1）人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetworks，ANNs）也簡(jiǎn)稱為神經(jīng)網(wǎng)絡(luò)（NNs）是一種模擬人腦內(nèi)部結(jié)構(gòu)，進(jìn)行分布式并行信息處理的算法數(shù)學(xué)模型。他具有良好的容錯(cuò)能力，自學(xué)習(xí)能力，分類(lèi)能力等，它可以處理一些環(huán)境復(fù)雜，背景知識(shí)不清，推理機(jī)制不明確的問(wèn)題，容許樣本有較大的缺損和畸變[7]?？梢圆扇【哂幸粋€(gè)隱含層的BP網(wǎng)絡(luò)來(lái)構(gòu)造手寫(xiě)數(shù)字識(shí)別核。網(wǎng)絡(luò)的輸入、輸出應(yīng)根據(jù)應(yīng)用的具體要求來(lái)設(shè)定，輸入特征數(shù)據(jù)為32×32的矩陣,轉(zhuǎn)換成1024×1的矩陣,因此神經(jīng)網(wǎng)絡(luò)輸入神經(jīng)元數(shù)目為1024。要識(shí)別0～9這10個(gè)數(shù)字,可以對(duì)于輸出“0”,采用(0,0,0,0)主要的目標(biāo)向量來(lái)表示,對(duì)于輸入“1”,采用(0,0,0,1)這樣的輸出向量來(lái)表示…以此類(lèi)推。因此,就可以確定輸出層的神經(jīng)元數(shù)目,也即輸出向量的維數(shù)。訓(xùn)練參數(shù)時(shí)，為了使BP網(wǎng)絡(luò)對(duì)輸入有一定的容錯(cuò)性，利用含有和不含有噪聲的輸入數(shù)據(jù)訓(xùn)練網(wǎng)絡(luò)。（2）決策樹(shù)方法最早產(chǎn)生于上世紀(jì)60年代到70年代末。決策樹(shù)一般都是由上往下來(lái)生成的，每個(gè)決策都有可能引出兩個(gè)或兩個(gè)以上的事件，這種決策分支畫(huà)成的圖形很像一棵樹(shù)，所以稱決策樹(shù)。決策樹(shù)在數(shù)據(jù)挖掘中是一種經(jīng)常用到的技術(shù)，可以用于分析數(shù)據(jù)，也可以用來(lái)作預(yù)測(cè)。決策樹(shù)算法有分類(lèi)精度高，成對(duì)模式簡(jiǎn)單，對(duì)噪聲數(shù)據(jù)有很好的健壯性等優(yōu)點(diǎn)，所以是目前應(yīng)用最為廣泛的歸納推理算法之一，備受研究者的關(guān)注[9]。針對(duì)某個(gè)數(shù)字均有著不同的手寫(xiě)體形式，它們有不同的特征屬性集。針對(duì)數(shù)字0~9的各種手寫(xiě)體數(shù)字的異體字來(lái)建立一個(gè)訓(xùn)練數(shù)據(jù)集，通過(guò)對(duì)該訓(xùn)練數(shù)據(jù)集進(jìn)行適當(dāng)?shù)臎_突消除和約化，建立數(shù)據(jù)集，再利用基于分層思想的決策樹(shù)算法產(chǎn)生決策樹(shù)。獲取數(shù)字圖片并預(yù)處理之后，掃描圖片，提取該數(shù)字的屬性特征，搜索生成好的決策樹(shù)，經(jīng)過(guò)層層分類(lèi)，可以得出該手寫(xiě)體數(shù)字。（3）SVM（支持向量機(jī)），是數(shù)據(jù)挖掘中的一項(xiàng)新技術(shù)，是借助于最優(yōu)化方法來(lái)解決機(jī)器學(xué)習(xí)問(wèn)題的新工具，是克服“維數(shù)災(zāi)難”和“過(guò)學(xué)習(xí)”等傳統(tǒng)困難的有力手段。本文主要討論基于SVM（支持向量機(jī)）手寫(xiě)數(shù)字識(shí)別的應(yīng)用與實(shí)現(xiàn)，因此，具體內(nèi)容將會(huì)在下文詳細(xì)介紹。

2SVM（支持向量機(jī)）的相關(guān)研究2.1SVM概述2.1.1理論背景支持向量機(jī)方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性和學(xué)習(xí)能力即對(duì)特定訓(xùn)練樣本的學(xué)習(xí)精度和無(wú)錯(cuò)誤地識(shí)別任意樣本的能力之間尋找最佳的折衷，來(lái)獲得最佳推廣能力[1]。傳統(tǒng)統(tǒng)計(jì)學(xué)的識(shí)別方法一般都是在樣本數(shù)目足夠多的前提下進(jìn)行研究的，現(xiàn)有的學(xué)習(xí)方法也多是基于此假設(shè)，所提出的各種方法也只有在樣本數(shù)趨向無(wú)窮大時(shí)其性能才有理論上的保證。而在實(shí)際應(yīng)用中，樣本數(shù)目通常都是有限的，因此一些在理論上很優(yōu)秀的學(xué)習(xí)方法，實(shí)際中的表現(xiàn)往往跟預(yù)想中有很大差距。作為傳統(tǒng)統(tǒng)汁學(xué)的重要發(fā)展和補(bǔ)充，統(tǒng)計(jì)學(xué)習(xí)理論（StatisticalLearningTheory，SLT）是一種專(zhuān)門(mén)研究小樣本情況下機(jī)器學(xué)習(xí)規(guī)律的理論，為研究有限樣本情況下機(jī)器學(xué)習(xí)的理論和方法提供了良好的理論框架，其核心思想是通過(guò)控制學(xué)習(xí)機(jī)器的容量實(shí)現(xiàn)對(duì)推廣能力的控制[4]。該理論針對(duì)小樣本統(tǒng)計(jì)問(wèn)題建立了一套新的理論體系，在這種體系下的統(tǒng)計(jì)推理規(guī)則不僅考慮了對(duì)漸近性能的要求，而且追求在現(xiàn)有有限信息的條件下得到最優(yōu)結(jié)果。Vapnik等人從六、七十年代開(kāi)始致力于此方面研究，隨著統(tǒng)計(jì)學(xué)習(xí)理論的不斷發(fā)展和完善，也由于神經(jīng)網(wǎng)絡(luò)等學(xué)習(xí)方法在理論上缺乏實(shí)質(zhì)性進(jìn)展，到了九十年代中期，統(tǒng)計(jì)學(xué)習(xí)理論開(kāi)始受到越來(lái)越廣泛的重視。在這一理論中發(fā)展出的支持向量機(jī)方法是一種新的通用學(xué)習(xí)機(jī)器，相比較以往其他的學(xué)習(xí)方法，表現(xiàn)出了很多理論和實(shí)踐上的優(yōu)勢(shì)。統(tǒng)計(jì)學(xué)習(xí)理論為解決有限樣本學(xué)習(xí)的問(wèn)題提供了一個(gè)統(tǒng)一的框架，它能夠?qū)⒑芏喱F(xiàn)有的方法納入其中，有望幫助解決如神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)選擇問(wèn)題、局部極小點(diǎn)問(wèn)題等許多原來(lái)難以解決的問(wèn)題。同時(shí)，在這一理論基礎(chǔ)上發(fā)展出的一種新的通用學(xué)習(xí)方法支持向量機(jī)已初步表現(xiàn)出很多優(yōu)于已有方法的性能。很多研究者認(rèn)為，統(tǒng)計(jì)學(xué)習(xí)理論和支持向量機(jī)正在成為繼神經(jīng)網(wǎng)絡(luò)研究之后的后起之秀，成為新的研究熱點(diǎn)，并將推動(dòng)機(jī)器學(xué)習(xí)理論和技術(shù)開(kāi)展出新的篇章。2.1.2SVM簡(jiǎn)介支持向量機(jī)(SupportVectorMachine，SVM)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識(shí)別中表現(xiàn)出許多特有的優(yōu)勢(shì)，并推廣應(yīng)用到了函數(shù)擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中。Vapnik執(zhí)統(tǒng)計(jì)機(jī)器學(xué)習(xí)之牛耳，他出版的《StatisticalLearningTheory》是一本完整闡述統(tǒng)計(jì)機(jī)器學(xué)習(xí)思想的名著，廣受世界各國(guó)研究人士歡迎。在該書(shū)中詳細(xì)的論證了統(tǒng)計(jì)機(jī)器學(xué)習(xí)跟傳統(tǒng)機(jī)器學(xué)習(xí)的本質(zhì)區(qū)別，就在于統(tǒng)計(jì)機(jī)器學(xué)習(xí)能夠精確的給出學(xué)習(xí)效果，能夠解答需要的樣本數(shù)等等一系列問(wèn)題。機(jī)器學(xué)習(xí)本質(zhì)上就是一種對(duì)問(wèn)題真實(shí)模型的逼近，這個(gè)與問(wèn)題真實(shí)解之間的誤差，叫做風(fēng)險(xiǎn)。然而真實(shí)的誤差是未知的，但是可以通過(guò)一些可以掌握的量來(lái)向他靠近，普遍的做法是通過(guò)分類(lèi)器在樣本數(shù)據(jù)上的測(cè)試結(jié)果跟真實(shí)結(jié)果之間的差值來(lái)表示，我們稱這個(gè)差值為經(jīng)驗(yàn)風(fēng)險(xiǎn)。以前的機(jī)器學(xué)習(xí)方法都致力于將經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化，選擇一個(gè)VC維很高的分類(lèi)函數(shù)，他雖然能夠?qū)⒚恳粋€(gè)樣本都精確的記住，但對(duì)樣本之外的數(shù)據(jù)分類(lèi)情況卻是慘不忍睹[10]。統(tǒng)計(jì)學(xué)習(xí)因此而引入了泛化誤差界的概念。真實(shí)風(fēng)險(xiǎn)應(yīng)該由經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信風(fēng)險(xiǎn)兩個(gè)部分所組成，經(jīng)驗(yàn)風(fēng)險(xiǎn)代表了分類(lèi)器在給定樣本上識(shí)別分類(lèi)的誤差；置信風(fēng)險(xiǎn)則表示我們可以在多大程度上信任分類(lèi)器在未知樣本上的識(shí)別分類(lèi)結(jié)果。然而，我們沒(méi)有辦法精確計(jì)算出置信風(fēng)險(xiǎn)，只能給出一個(gè)估計(jì)的范圍，這樣也使得整個(gè)誤差只能計(jì)算出其上界，卻無(wú)法計(jì)算出它準(zhǔn)確的值。統(tǒng)計(jì)學(xué)習(xí)將重點(diǎn)從經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化轉(zhuǎn)移到了如何使經(jīng)驗(yàn)風(fēng)險(xiǎn)與置信風(fēng)險(xiǎn)的和最小，經(jīng)驗(yàn)風(fēng)險(xiǎn)與置信風(fēng)險(xiǎn)的和又稱為結(jié)構(gòu)風(fēng)險(xiǎn)。SVM正是這樣一種努力將結(jié)構(gòu)風(fēng)險(xiǎn)最小化的算法。SVM的基本思想是：定義最優(yōu)線性超平面，并把尋找最優(yōu)線性超平面的算法歸結(jié)為求解一個(gè)凸規(guī)劃問(wèn)題。進(jìn)而基于Mercer核展開(kāi)定理，通過(guò)構(gòu)造一個(gè)非線性映射φ，把樣本空間映射到一個(gè)高維乃至無(wú)窮維的特征空間，使之在特征空間中可以應(yīng)用線性學(xué)習(xí)機(jī)的方法解決樣本空間中的高度非線性分類(lèi)和回歸問(wèn)題。支持向量機(jī)是針對(duì)線性可分情況進(jìn)行分析的，但是大多情況是數(shù)線性不可分的，換言之，低維空間向量集通常難于劃分，這時(shí)，就需要通過(guò)使用非線性映射算法將低維輸入空間線性不可分的樣本轉(zhuǎn)化到高維特征空間，使其變得線性可分，從而使得高維特征空間可以對(duì)樣本的非線性特征，采用線性算法進(jìn)行線性分析。但這個(gè)辦法卻會(huì)讓計(jì)算復(fù)雜度大大增加，而核函數(shù)的引入正好能夠巧妙地解決這個(gè)問(wèn)題。換言之，只要引入合適的核函數(shù)，我們就可以將它映射到高維空間得到高維空間的分類(lèi)函數(shù)。在SVM分類(lèi)器的構(gòu)造中，選擇不同的核函數(shù)將導(dǎo)致不同的SVM算法。支持向量機(jī)的關(guān)鍵就在于核函數(shù)，這也是支持向量機(jī)最引人喜歡的地方。支持向量機(jī)作為一種具有嚴(yán)密理論基礎(chǔ)的計(jì)算機(jī)學(xué)習(xí)的新方法，它已經(jīng)成為計(jì)算機(jī)學(xué)習(xí)、模式識(shí)別、計(jì)算機(jī)智能、預(yù)測(cè)預(yù)報(bào)等領(lǐng)域的熱點(diǎn)技術(shù)，在國(guó)內(nèi)外受到廣泛關(guān)注。2.1.3SVM的優(yōu)點(diǎn)SVM以統(tǒng)計(jì)學(xué)習(xí)理論為基礎(chǔ)，它具有很強(qiáng)的學(xué)習(xí)能力以及泛化性能。SVM學(xué)習(xí)結(jié)果是支持向量的集合，一般是學(xué)習(xí)樣本集中的一小部分，支持向量集可以充分的體現(xiàn)整個(gè)樣本集的屬性[1]。它的主要優(yōu)點(diǎn)大致可歸納為：（1）非線性映射是SVM方法的理論基礎(chǔ),SVM將輸入空間中的非線性問(wèn)題通過(guò)引用核函數(shù)映射到高維特征空間，然后在高維空間中構(gòu)造線性函數(shù)以作判別。（2）對(duì)特征空間劃分的最優(yōu)超平面是SVM的目標(biāo),最大化分類(lèi)邊際的思想是SVM方法的核心，SVM算法可最終轉(zhuǎn)化為凸優(yōu)化問(wèn)題,因而可保證算法的全局最優(yōu)性,避免了神經(jīng)網(wǎng)絡(luò)無(wú)法解決的局部極值問(wèn)題。（3）支持向量機(jī)是基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化的原則,保證了學(xué)習(xí)機(jī)器具有良好的泛化能力。（4）SVM是一種有堅(jiān)實(shí)理論基礎(chǔ)的新穎的小樣本學(xué)習(xí)方法。它能夠自動(dòng)識(shí)別出訓(xùn)練集中的一個(gè)子集，此子集基本上可以代表訓(xùn)練集中的全部信息，也就是說(shuō)只有這個(gè)子集對(duì)分類(lèi)及回歸問(wèn)題的求解起作用。從本質(zhì)上看,它避開(kāi)了從歸納到演繹的傳統(tǒng)過(guò)程,實(shí)現(xiàn)了高效的從訓(xùn)練樣本到預(yù)報(bào)樣本的“轉(zhuǎn)導(dǎo)推理”,大大簡(jiǎn)化了通常的分類(lèi)和回歸等問(wèn)題。（5）SVM的最終決策函數(shù)只由少數(shù)的支持向量所確定,計(jì)算的復(fù)雜性取決于支持向量的數(shù)目,而不是樣本空間的維數(shù),它將實(shí)際問(wèn)題通過(guò)非線性變換轉(zhuǎn)換到高維的特征空間，在高維空間中構(gòu)造線性判別函數(shù)來(lái)實(shí)現(xiàn)原空間中的非線性判別函數(shù)，特殊性質(zhì)能保證機(jī)器有較好的推廣能力，這在某種意義上避免了“維數(shù)災(zāi)難”。（6）少數(shù)的支持向量決定了最終結(jié)果,這幫助我們抓住了關(guān)鍵樣本并“剔除”了大量冗余樣本；而且，使用該方法不但算法比較簡(jiǎn)單,而且還具有較強(qiáng)的“魯棒”性，主要體現(xiàn)為:①增加、刪減非支持向量的樣本不會(huì)對(duì)模型造成影響；②支持向量樣本集也具有較好的“魯棒性”；③在一些應(yīng)用中,SVM方法對(duì)核的選擇范圍比較廣泛。2.2VC維VC維（Vapnik-ChervonenkisDimension）是為了研究學(xué)習(xí)過(guò)程一致收斂的速度和推廣性，由統(tǒng)計(jì)學(xué)習(xí)理論定義的有關(guān)函數(shù)集學(xué)習(xí)性能的一個(gè)重要指標(biāo)。VC維在有限的訓(xùn)練樣本情況下，當(dāng)樣本數(shù)n固定時(shí)，此時(shí)學(xué)習(xí)機(jī)器的VC維越高學(xué)習(xí)機(jī)器的復(fù)雜性越高。模式識(shí)別中VC維的直觀定義是:對(duì)一個(gè)指示函數(shù)集，如果存在H個(gè)樣本能夠被函數(shù)集中的函數(shù)按所有可能的H2種形式分開(kāi)，則稱函數(shù)集能夠把H個(gè)樣本打散，函數(shù)集的VC維就是它能打散的最大樣本數(shù)目H，如果對(duì)于任意數(shù)目的樣本都有函數(shù)可以將它們打散，則稱函數(shù)集的VC維無(wú)窮大?？梢酝ㄟ^(guò)使用一定的閾值將之轉(zhuǎn)化為指示函數(shù)來(lái)定義有界實(shí)函數(shù)的VC維[4]。通常說(shuō)的結(jié)構(gòu)風(fēng)險(xiǎn)最小化就是在保證分類(lèi)精度（經(jīng)驗(yàn)風(fēng)險(xiǎn)）的基礎(chǔ)上減少學(xué)習(xí)機(jī)器的VC維，令學(xué)習(xí)機(jī)器在整個(gè)樣本集上的期望風(fēng)險(xiǎn)得到有效控制。影響期望風(fēng)險(xiǎn)上界的因子有訓(xùn)練集的規(guī)模n和VC維h兩個(gè)方面?？梢园l(fā)現(xiàn)，結(jié)構(gòu)風(fēng)險(xiǎn)最小化的由來(lái)就是在保證分類(lèi)精度的同時(shí)降低學(xué)習(xí)機(jī)器的VC維，使得學(xué)習(xí)機(jī)器得以控制在整個(gè)樣本集上的期望風(fēng)險(xiǎn)。在有限的訓(xùn)練樣本情況下，當(dāng)樣本數(shù)n固定時(shí)，此時(shí)學(xué)習(xí)機(jī)器的VC維越高，則置信范圍就越大，此時(shí)，真實(shí)風(fēng)險(xiǎn)與經(jīng)驗(yàn)風(fēng)險(xiǎn)之間的差別就越大，這就是會(huì)出現(xiàn)過(guò)學(xué)習(xí)現(xiàn)象的原因。機(jī)器學(xué)習(xí)過(guò)程不但要使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，還要使其VC維盡量小，以縮小置信范圍，才能取得較小的實(shí)際風(fēng)險(xiǎn)，即對(duì)未來(lái)樣本有較好的推廣性，它與學(xué)習(xí)機(jī)器的VC維及訓(xùn)練樣本數(shù)有關(guān)。VC維反映了函數(shù)集的學(xué)習(xí)能力，VC維越大則學(xué)習(xí)機(jī)器越復(fù)雜，所以VC維又是學(xué)習(xí)機(jī)器復(fù)雜程度的一種衡量。2.3SVM原理2.3.1分類(lèi)問(wèn)題與機(jī)器學(xué)習(xí)SVM方法是從線性可分情況下的最優(yōu)分類(lèi)面提出的。所謂最優(yōu)分類(lèi)面就是要求分類(lèi)線將兩類(lèi)樣本準(zhǔn)確的分開(kāi)并使兩類(lèi)之間的距離最大。設(shè)有兩類(lèi)模式和，是從模式和中抽樣得到的訓(xùn)練集，其中、。若屬于類(lèi)，則對(duì)應(yīng)有；若屬于類(lèi)，則對(duì)應(yīng)有。尋求上的一個(gè)實(shí)函數(shù)個(gè)g（X），對(duì)于任給的未知模式，有或者（2.1）sgn()為符號(hào)函數(shù)，g()為決策（分類(lèi)）函數(shù)。稱解決上述問(wèn)題的方法為“分類(lèi)機(jī)”。當(dāng)g(X)為線性函數(shù)時(shí)，稱為線性分類(lèi)機(jī)；當(dāng)g(X)為非線性函數(shù)時(shí)，稱為非線性分類(lèi)機(jī)。如示意圖2-1所示：HHH1H2C1C2g(X)kk圖2-1樣本分布根據(jù)數(shù)據(jù)分布以及所對(duì)應(yīng)的y值，我們可以目測(cè)獲得一條分類(lèi)線g(X)。g(X)不僅可以將兩類(lèi)模式分開(kāi)，并且具有最寬的“邊帶”。對(duì)任一樣本進(jìn)行檢驗(yàn)，得到數(shù)據(jù)，若X處于g(X)上邊則屬于類(lèi)，反之，則屬于類(lèi)。但是一般情況下，樣本的維數(shù)都會(huì)很高，這種情況下已無(wú)法人為直觀地確定判別函數(shù)g(X)了。于是，我們需要一種根據(jù)給定的大量樣本確定判別函數(shù)的方法，即需要一個(gè)能夠由經(jīng)驗(yàn)數(shù)據(jù)學(xué)會(huì)對(duì)某些模式進(jìn)行分類(lèi)的“學(xué)習(xí)機(jī)”。2.3.2兩類(lèi)可分問(wèn)題的線性分類(lèi)機(jī)下面討論的是線性可分的情況，仍以圖2-1為例，對(duì)于這個(gè)二維問(wèn)題，線性分類(lèi)機(jī)的作用就是尋找一條分類(lèi)線將和劃分開(kāi)來(lái)，其表達(dá)式為g(X)。在線性可分的情況下，能夠準(zhǔn)確將和兩類(lèi)模式分開(kāi)的直線并不是唯一的。假設(shè)有直線H可以準(zhǔn)確地將和分開(kāi)，另有直線和直線之間隔出了一個(gè)沒(méi)有學(xué)習(xí)樣本的帶狀區(qū)域，稱之為邊帶，而H是邊帶的中分線，和與H之間的間距為k。顯然，最合理的分類(lèi)線應(yīng)該具有最寬的邊帶。該分類(lèi)線的表達(dá)式可以表達(dá)為：（2.2）為分類(lèi)線H的法線矢量，g(X)到原點(diǎn)的距離為。對(duì)于給定的N個(gè)樣本，g(X)滿足：（2.3a）也可以寫(xiě)成：（2.3b）因和與H之間的間距為k，而由于k是一個(gè)標(biāo)量，可以取，，所以，他們的表達(dá)式分別可以表達(dá)為為：（2.4）當(dāng)k增大時(shí)，變小。這樣，尋找最大帶寬k的問(wèn)題，變成了尋找最小的問(wèn)題，為了計(jì)算上的方便，取目標(biāo)函數(shù)為。而對(duì)于任意樣本點(diǎn)必定處于邊帶之外，則滿足：（2.5）將之轉(zhuǎn)換成為一個(gè)約束優(yōu)化問(wèn)題，可表達(dá)為：（2.6）接下來(lái)就輪到求解過(guò)程了，繼續(xù)看圖2-1，其實(shí)，我們只是想求得這樣一個(gè)線性函數(shù)：（2.7）而求這樣一個(gè)g(X)的過(guò)程就是求W（一個(gè)n維向量）和b（一個(gè)實(shí)數(shù)）兩個(gè)參數(shù)的過(guò)程，而b可以由W確定，而W又是給定的樣本決定的。W就可以表示為樣本的某種組合：（2.8）式中是拉格朗日乘子，是樣本點(diǎn)。為了固定三條直線不會(huì)移動(dòng)，可以加上樣本點(diǎn)的標(biāo)簽，它等譯1或者-1，這樣可以表達(dá)為：（2.9）因此，g(X)可表達(dá)為：（2.10）于是，得到最優(yōu)分類(lèi)函數(shù)：(2.11)可以用來(lái)判定樣本所屬的分類(lèi)。2.3.3非線性支持向量機(jī)——核函數(shù)方法對(duì)于給定的樣本集，若是非線性的，則需要使用一個(gè)非線性函數(shù)把數(shù)據(jù)映射到一個(gè)高維特征空間，再在高維特征空間建立優(yōu)化超平面。如圖2-2所示，假設(shè)圖中a和b之間紅色部分里的所有點(diǎn)定為正類(lèi)，兩邊的黑色部分里的點(diǎn)定為負(fù)類(lèi)，我們可以找到這樣一條曲線將兩類(lèi)正確的分隔開(kāi)來(lái)。aab圖2-2非線性可分的樣本分布該超平面在原空間可表示為決策面：（2.12）考慮到可能存在一些樣本不能被決策面正確分類(lèi),因此引入松弛變量，與懲罰參數(shù)C，決策面應(yīng)滿足約束：（2.13）分類(lèi)問(wèn)題變成：（2.14）為求解這個(gè)優(yōu)化問(wèn)題,引入拉格郎日函數(shù)：（2.15）其中，函數(shù)L的極值應(yīng)滿足條件：（2.16）由此可得到優(yōu)化問(wèn)題的對(duì)偶形式，最大化函數(shù)：（2.17）此式當(dāng)中函數(shù)是未知的，支持向量機(jī)理論只考慮高維特征空間的點(diǎn)積運(yùn)算,而不直接使用函數(shù),從而巧妙地解決了這個(gè)問(wèn)題。若K是正定核，則對(duì)偶問(wèn)題是一個(gè)凸二次規(guī)劃問(wèn)題，必定有解。求解上述最優(yōu)化問(wèn)題，得到最優(yōu)解，選擇一個(gè)的一個(gè)正分量，并以此計(jì)算：（2.18）構(gòu)造如下分類(lèi)函數(shù)以對(duì)樣本進(jìn)行分類(lèi)：（2.19）

3數(shù)字識(shí)別預(yù)處理過(guò)程為了提高手寫(xiě)數(shù)字識(shí)別的精度，一般在識(shí)別之前會(huì)采取一定的預(yù)處理過(guò)程。預(yù)處理過(guò)程一般包括二值化處理，平滑去噪處理和歸一化處理。3.1二值化數(shù)字圖像的二值化是為了減小數(shù)據(jù)存儲(chǔ)的容量，降處理的復(fù)雜性，其操作就是把數(shù)字灰度圖像處理成二值(0，l)圖像的過(guò)程。二值化處理方法很多,但考慮到大量數(shù)字識(shí)別的需要,一般只能采用一維的閾值分割算法進(jìn)行處理以獲得二值化數(shù)字圖像。首先，先給定一個(gè)固定閾值T，設(shè)f（i，j)為像素（0,1）的灰度值。當(dāng)時(shí)，像素點(diǎn)為數(shù)字筆畫(huà)上的點(diǎn)，將其像素值為0；當(dāng)時(shí)，像素點(diǎn)為背景上的點(diǎn)，置其像素為1。數(shù)字圖像二值化之后，要求圖像能夠真實(shí)的再現(xiàn)原本的數(shù)字，有以下幾點(diǎn)基本要求：筆畫(huà)之中不能出現(xiàn)間斷或者空白點(diǎn)；二值化的筆畫(huà)能夠再現(xiàn)原來(lái)文字的結(jié)構(gòu)特征。這一過(guò)程使其信息量大大減少，使其特征更集中，但是也很容易造成信息的丟失。3.2平滑去噪數(shù)字圖像在采集的過(guò)程中很有可能產(chǎn)生噪聲，破壞了圖像質(zhì)量，給以后的工作帶來(lái)大量不便，因此，需要平滑去噪處理去掉圖像中夾帶的噪聲點(diǎn)、干擾，平滑筆畫(huà)邊緣。具體操作如下：01？101？11？10111？？？1111000？？1000001？00000abcd圖3-1平滑模板如圖3-1所示，“1”代表黑點(diǎn)，“0”代表背景，“？”代表黑點(diǎn)或者背景。若某像素P的鄰域模板跟a，b平滑模板相符合，則將P的值改為1，變成黑像素；若某像素P的鄰域模板跟c，d平滑模板相符合，則將P的值改為0，變成白像素。當(dāng)模板旋轉(zhuǎn)90°，180°，270°之后，也是同樣的情況。數(shù)字圖像在平滑處理之后，若還有黑斑形式的噪聲無(wú)法去除，則可以用一個(gè)3×3的窗口區(qū)域在二值圖像上浮動(dòng)，當(dāng)該區(qū)域內(nèi)的黑點(diǎn)數(shù)與它所在的窗口區(qū)域的黑點(diǎn)數(shù)相等，則認(rèn)為該窗口區(qū)域的黑點(diǎn)為噪聲。只要將該窗口區(qū)域內(nèi)的黑點(diǎn)都變成白點(diǎn)就可以去除噪聲。3.3歸一化數(shù)字圖像在經(jīng)過(guò)以上一系列的處理之后，已經(jīng)為識(shí)別過(guò)程提高了不少準(zhǔn)確率，但是，原始圖像在大小尺寸上還是存在著不少差異，這時(shí)就需要利用歸一化處理將數(shù)字圖像統(tǒng)一成相同的大小規(guī)格。歸一化，首先要進(jìn)行的就是位置歸一化?？梢酝ㄟ^(guò)移動(dòng)圖像重心至點(diǎn)陣中心，或者移動(dòng)圖像外框到點(diǎn)陣的規(guī)定位置上來(lái)調(diào)整數(shù)字圖像的位置。然后則是大小歸一化，大小歸一化又可分為線性歸一化和非線性歸一化兩種。線性歸一化在字符識(shí)別中有很廣泛的應(yīng)用，通過(guò)對(duì)像素坐標(biāo)進(jìn)行線性變換來(lái)實(shí)現(xiàn)，將不同大小的圖像統(tǒng)一成固定大小。非線性歸一化則可以通過(guò)點(diǎn)密度的方法來(lái)實(shí)現(xiàn)。將圖像中的黑像素分別向水平軸和垂直軸投影，可以得到兩個(gè)方向的點(diǎn)密度公式：（3.1）式中，和是常數(shù)用來(lái)控制變換的強(qiáng)度，值越大變換強(qiáng)度越小。變換后的新坐標(biāo)位置（m,n）可以通過(guò)式3.1得到：（3.2）非線性歸一化的效果明顯要優(yōu)于線性，但是其計(jì)算量比線性歸一化要來(lái)的大。

4基于SVM數(shù)字識(shí)別過(guò)程經(jīng)過(guò)預(yù)處理的數(shù)字圖像還要經(jīng)過(guò)特征提取的過(guò)程來(lái)提高系統(tǒng)識(shí)別的效率和準(zhǔn)確度。所謂特征提取，就是將數(shù)字筆畫(huà)轉(zhuǎn)換為一組特征值的過(guò)程。首先，找出包含原始圖片中的數(shù)字部分的最小的矩形區(qū)域，然后把每一張圖片分成２５個(gè)小塊，統(tǒng)計(jì)每個(gè)小塊內(nèi)的黑色像素點(diǎn)所點(diǎn)比例，這樣每一個(gè)數(shù)字圖片就轉(zhuǎn)換成了一個(gè)２５維的向量，每一維的值就是對(duì)應(yīng)小塊的黑色像素的占比。接下來(lái)，就可以通過(guò)SVM分類(lèi)器進(jìn)行數(shù)字識(shí)別了。4.1SVM分類(lèi)算法阿拉伯?dāng)?shù)字一共有10個(gè)基本數(shù)字，也就是說(shuō)手寫(xiě)數(shù)字識(shí)別一共有10個(gè)樣本，很顯然，屬于多分類(lèi)問(wèn)題。而對(duì)于SVM這樣一個(gè)兩類(lèi)的識(shí)別器，支持向量機(jī)又該怎么來(lái)處理呢？SVM解決多類(lèi)問(wèn)題的方法主要有一對(duì)多（One-Versus-All，OVA）算法和一對(duì)一（One-Versus-One，OVO）算法，本文采用的是一對(duì)一（One-Versus-One，OVO）算法，下文將詳細(xì)介紹。4.1.1一對(duì)多（One-Versus-All，OVA）算法一對(duì)多分類(lèi)算法是支持向量機(jī)最早實(shí)現(xiàn)多類(lèi)分類(lèi)的算法。一對(duì)多算法是在一類(lèi)樣本與剩余的多類(lèi)樣本之間構(gòu)造決策平面，從而達(dá)到多類(lèi)識(shí)別的目的。假設(shè)一共有k類(lèi)樣本，將其中第j類(lèi)樣本看作正類(lèi)(j=1,2,…,k)，而將其他k-1類(lèi)樣本看作負(fù)類(lèi)，通過(guò)兩類(lèi)SVM方法可以求出這樣一個(gè)決策函數(shù)：（4.1）一共有k個(gè)這樣的決策函數(shù)?，F(xiàn)給定一個(gè)測(cè)試樣本分別代入k個(gè)決策函數(shù)，求出函數(shù)值，如果在k個(gè)中最大，則可判定測(cè)試樣本x屬于s類(lèi)。其實(shí)這種方法就是在每一類(lèi)樣本和剩余的樣本之間找出一個(gè)最優(yōu)決策面，將剩余的多類(lèi)看成一個(gè)整體進(jìn)行k次兩類(lèi)識(shí)別，如圖4-1所示：112311或222或33f1=0f2=0f3=0(a)(b)圖4-1一對(duì)多分類(lèi)設(shè)分類(lèi)問(wèn)題分“1”，“2”和“3”類(lèi)如圖3-1(a)所示，首先把“1”看做正類(lèi)，把“2”和“3”看做負(fù)類(lèi)，決策函數(shù)，和分別能將“1”類(lèi)，“2”類(lèi)和“3”類(lèi)分出來(lái)。任意輸入x若決策函數(shù)中有且僅有一個(gè)為正，那么就能判定x的歸屬了。然而，若是輸入對(duì)于x沒(méi)有或者不止一個(gè)取正值，如圖4-1(b)所示，那么，和中取值最大的者為x所屬類(lèi)別。4.1.2一對(duì)一（One-Versus-One，OVO）算法一對(duì)一分類(lèi)算法是基于兩類(lèi)問(wèn)題的分類(lèi)算法，利用兩類(lèi)SVM算法分別在每?jī)深?lèi)不同的樣本之間都構(gòu)造一個(gè)最優(yōu)決策面。如果一共k類(lèi)樣本，則需要構(gòu)造k(k-1)/2，(k>2)個(gè)分類(lèi)平面。而對(duì)于手寫(xiě)數(shù)字識(shí)別，就是k=10的情況，我們則需要構(gòu)造45個(gè)分類(lèi)器。這種方法相當(dāng)于將多類(lèi)問(wèn)題轉(zhuǎn)化為多個(gè)兩類(lèi)問(wèn)題來(lái)求解，本質(zhì)上跟兩類(lèi)SVM一樣。從樣本集中取出所有y=i和y=j的樣本點(diǎn)，通過(guò)SVM構(gòu)造的最優(yōu)決策函數(shù)為：（4.2）對(duì)于10分類(lèi)問(wèn)題的手寫(xiě)數(shù)字識(shí)別，則需要構(gòu)造45個(gè)這樣的決策函數(shù)。接下來(lái)的問(wèn)題是如何對(duì)未知樣本進(jìn)行準(zhǔn)確的預(yù)測(cè).往往采用投票法（Vote），計(jì)算所有的分類(lèi)器所分得的類(lèi)別，選擇得票數(shù)最多的類(lèi)別作為待分類(lèi)文檔應(yīng)屬類(lèi)別。圖4-2為手寫(xiě)數(shù)字識(shí)別一對(duì)一分類(lèi)的模型：112……9101213910采用投票法，得票多的類(lèi)為識(shí)別結(jié)果ij…………45個(gè)分類(lèi)器圖4-2手寫(xiě)數(shù)字識(shí)別一對(duì)一分類(lèi)法模型關(guān)于投票法（Vote）：若給出一個(gè)測(cè)試數(shù)字x，為了判斷它的所屬類(lèi)別，投票法必須考慮上述所有45個(gè)分類(lèi)器對(duì)x所屬類(lèi)別的判定：分類(lèi)機(jī)判定x屬于第i類(lèi)就意味著第i類(lèi)獲得一票，否則，第j類(lèi)的投票就增加一票，最后得票數(shù)最多的類(lèi)別就是最終x所屬的類(lèi)別。4.1.3兩種分類(lèi)算法的優(yōu)缺點(diǎn)比較一對(duì)一分類(lèi)算法的優(yōu)點(diǎn)在于每次投入訓(xùn)練的樣本較少，因此單個(gè)分類(lèi)器的訓(xùn)練速度較快，同時(shí)精度也較高，但是有k個(gè)分類(lèi)就需要訓(xùn)練k(k-1)/2個(gè)分類(lèi)器，當(dāng)k較大時(shí)分類(lèi)器的總數(shù)將過(guò)多，會(huì)影預(yù)測(cè)的速度。而一對(duì)多分類(lèi)算法構(gòu)造的分類(lèi)器只需要k個(gè)，比一對(duì)一要少很多，因此在類(lèi)別數(shù)目k較大時(shí)，一對(duì)多分類(lèi)算法的預(yù)測(cè)速度將比一對(duì)一分類(lèi)算法快。但是因?yàn)樗看螛?gòu)造分類(lèi)器的時(shí)候都需要用上全部的樣本類(lèi)，因此它在訓(xùn)練上花的時(shí)間相對(duì)較多。而本文討論的手寫(xiě)數(shù)字識(shí)別只有10個(gè)類(lèi)別，數(shù)目比較小，因此選擇一對(duì)一分類(lèi)算法效率與精確度會(huì)較高。4.2核函數(shù)的選擇核函數(shù)是SVM（支持向量機(jī)）的核心，不同的核函數(shù)可以構(gòu)造不同的SVM分類(lèi)器，而本文研究的正是基于SVM（支持向量機(jī)）的手寫(xiě)數(shù)字識(shí)別，因此核函數(shù)的選擇至關(guān)重要。核函數(shù)方法應(yīng)用非常廣泛,這與它特有的性質(zhì)是分不開(kāi)的：（1）核函數(shù)的引入使得輸入空間的維數(shù)h對(duì)核函數(shù)矩陣沒(méi)有影響，不僅大大減小了計(jì)算量還避免了“維數(shù)災(zāi)難”。（2）無(wú)需知道與之對(duì)應(yīng)的非線性變換函數(shù)Φ的形式以及參數(shù).（3）核函數(shù)方法還可以跟不同的算法結(jié)合，形成多種不同的基于核函數(shù)的算法，使很多原本不可行的算法變成可能，也減少了計(jì)算量函數(shù)K(x,y)的原始定義為：非線性映射φ()和內(nèi)積<>的復(fù)合函數(shù)，常規(guī)的構(gòu)造方案是先構(gòu)造非線性映射φ()，再根據(jù)K(x,y)的定義把他的表達(dá)式寫(xiě)出來(lái)。而我們通常判定K(x,y)為核函數(shù)，當(dāng)它滿足Mercer條件[4]：映射φ()以及核表達(dá)式(4.3)存在的條件是當(dāng)且僅當(dāng)對(duì)于任意的g(x)(4.4)有（4.5）常用的核函數(shù)有:線性核函數(shù)：多項(xiàng)式核函數(shù)：徑向基（RBF）核函數(shù)：4.3實(shí)驗(yàn)結(jié)果及分析不同的核函數(shù)可以構(gòu)造不同的SVM分類(lèi)器，本文選擇了線性核函數(shù)，二次核函數(shù)，多項(xiàng)式核函數(shù)以及徑向基核函數(shù)分別構(gòu)造SVM分類(lèi)器，并應(yīng)用于手寫(xiě)數(shù)字識(shí)別系統(tǒng)，進(jìn)行實(shí)驗(yàn)，比對(duì)。以下，對(duì)不同的核函數(shù)方法分別對(duì)3組0到9的阿拉伯?dāng)?shù)字進(jìn)行測(cè)試。待測(cè)試的真實(shí)數(shù)字如圖4-3所示：圖4-3真實(shí)數(shù)字4.3.1基于線性核函數(shù)的SVM分類(lèi)器的測(cè)試首先選用基于線性核函數(shù)的SVM方法進(jìn)行訓(xùn)練，然后進(jìn)行數(shù)字識(shí)別測(cè)試，結(jié)果如圖4-4所示：圖4-4線性核函數(shù)方法的測(cè)試結(jié)果這種SVM分類(lèi)器測(cè)試的正確率如圖4-5所示（k=1表示正確，k=0則表示錯(cuò)誤，ans表示正確率）：圖4-5線性核函數(shù)方法的測(cè)試正確率由圖可見(jiàn)，每一個(gè)數(shù)字的測(cè)試結(jié)果都是正確的，正確率為100%。4.3.2基于二次核函數(shù)的SVM分類(lèi)器的測(cè)試選用基于二次核函數(shù)的SVM方法進(jìn)行訓(xùn)練，然后進(jìn)行數(shù)字識(shí)別測(cè)試，結(jié)果如圖4-6所示：圖4-6二次核函數(shù)方法的測(cè)試結(jié)果這種SVM分類(lèi)器測(cè)試的正確率如圖4-7所示：圖4-7二次核函數(shù)方法的測(cè)試正確率由圖可見(jiàn)，該識(shí)別結(jié)果，識(shí)別三組數(shù)字的數(shù)字6都識(shí)別成了0，三組30個(gè)數(shù)字錯(cuò)了3個(gè)，正確率為90%。4.3.3基于多項(xiàng)式核函數(shù)的SVM分類(lèi)器的測(cè)試選用基于多