ＳＶＭ算法及其在多類(lèi)字母圖象識(shí)別中的應(yīng)用

摘要：支持向量機(jī)是一種新的統(tǒng)計(jì)學(xué)習(xí)算法，其學(xué)習(xí)原則是使結(jié)構(gòu)風(fēng)險(xiǎn)最小，與經(jīng)典的學(xué)習(xí)方法的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小原則不同，這使得支持向量機(jī)具有很強(qiáng)的泛化能力。因?yàn)橹С窒蛄繖C(jī)算法是一個(gè)凸二次優(yōu)化問(wèn)題，能夠保證所求的局部最優(yōu)解就是全局最優(yōu)解。目前，研究的絕大多數(shù)是兩類(lèi)問(wèn)題。然而，即使我們能夠?qū)深?lèi)問(wèn)題正確分類(lèi)，也不能意味著實(shí)際應(yīng)用中多類(lèi)分類(lèi)問(wèn)題的解決。在這篇文章中，我們介紹了支持向量機(jī)算法，并且通過(guò)多類(lèi)字母圖象分類(lèi)問(wèn)題說(shuō)明支持向量機(jī)算法在多類(lèi)分類(lèi)問(wèn)題中的應(yīng)用。

關(guān)鍵詞：支持向量機(jī)；核函數(shù)；字母圖象；余類(lèi)

中圖分類(lèi)號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)08-1pppp-0c

1 引言

基于數(shù)據(jù)的機(jī)器學(xué)習(xí)是現(xiàn)代智能技術(shù)中十分重要的一個(gè)方面，主要研究如何從一些觀測(cè)數(shù)據(jù)（樣本）出發(fā)得到目前尚不能通過(guò)原理分析得到的規(guī)律，利用這些規(guī)律去分析客觀對(duì)象，對(duì)未來(lái)數(shù)據(jù)或無(wú)法觀測(cè)的數(shù)據(jù)進(jìn)行預(yù)測(cè)。一項(xiàng)頗為有效的技術(shù)-支持向量機(jī)（Support Vector Machines，簡(jiǎn)稱(chēng)SVM），近幾年來(lái)逐漸成為機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)。支持向量機(jī)是美國(guó)貝爾實(shí)驗(yàn)室V.Vapnik針對(duì)分類(lèi)和回歸問(wèn)題，為適合小樣本學(xué)習(xí)問(wèn)題而提出的通用學(xué)習(xí)算法 [1]，它根據(jù)VC（Vapnik-Chervonenkis）理論，基于結(jié)構(gòu)風(fēng)險(xiǎn)最小（Structural Risk Minimization，SRM）原理 [1]，而非經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化（Empirical Risk Minimization，ERM）原理，從而能夠兼顧訓(xùn)練錯(cuò)誤和泛化能力，開(kāi)辟了機(jī)器學(xué)習(xí)算法的新天地。目前絕大多數(shù)討論僅局限于用SVM解決兩類(lèi)問(wèn)題。然而，兩類(lèi)分類(lèi)問(wèn)題的解決并不意味著多類(lèi)分類(lèi)問(wèn)題的解決。對(duì)于多類(lèi)分類(lèi)問(wèn)題，我們提出基本訓(xùn)練樣本集和訓(xùn)練樣本集兩個(gè)層次的概念，通過(guò)不斷調(diào)節(jié)基本訓(xùn)練樣本集，求得對(duì)訓(xùn)練樣本集的最優(yōu)決策函數(shù)。對(duì)高維多類(lèi)分類(lèi)問(wèn)題具有很強(qiáng)的實(shí)踐價(jià)值。本文通過(guò)字母圖象識(shí)別的實(shí)際多類(lèi)分類(lèi)問(wèn)題的解決，說(shuō)明SVM算法的基本原理以及在多類(lèi)分類(lèi)問(wèn)題中的應(yīng)用。

2 支持向量機(jī)

SVM 是一種基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化的分類(lèi)器，通過(guò)解二次規(guī)劃問(wèn)題，尋找將數(shù)據(jù)分為兩類(lèi)的最佳超平面。它的核心內(nèi)容是：對(duì)于輸入空間中非線性可分問(wèn)題，選擇一個(gè)適當(dāng)?shù)挠成洌瑢⑤斎肟臻g中的樣本點(diǎn)映射到一個(gè)高維特征空間，使得對(duì)應(yīng)的樣本點(diǎn)在該空間線性可分，而且通過(guò)對(duì)核函數(shù)的深入研究，在解決策函數(shù)過(guò)程中的計(jì)算仍在原空間進(jìn)行，大大降低了在映射后的高維特征空間計(jì)算的復(fù)雜性。關(guān)于SVM的詳細(xì)介紹可參考文獻(xiàn)[2-4]。

2.1 線性可分支持向量機(jī)

2.1.1 線性可分

4 實(shí)驗(yàn)及其結(jié)果

本文的多類(lèi)字母圖象分類(lèi)問(wèn)題的實(shí)驗(yàn)數(shù)據(jù)數(shù)據(jù)庫(kù)來(lái)自UCI數(shù)據(jù)庫(kù)（www.ics.uci.edu / ~ mlearn / databases）。軟件環(huán)境：Matlab/WinXP，所選用核函數(shù)就是上文介紹的 Gauss 徑向基核函數(shù)，總共有 3864 個(gè)樣本（其中字母A的樣本790個(gè)，其中字母B的樣本766個(gè)，其中字母C的樣本 736 個(gè)，其中字母 D 的樣本 805個(gè)，其中字母E的樣本768 個(gè)，每個(gè)樣本采集了包括水平像素均值，垂直像素均值等 16 個(gè)特征，關(guān)于特征采集的詳細(xì)介紹參見(jiàn)www.ics.uci.edu/~mlearn/databases的英文文檔，我們隨機(jī)地選取一部分作為訓(xùn)練樣本集，第一次實(shí)驗(yàn)時(shí)我們從每一類(lèi)中隨機(jī)選取400個(gè)樣本組成訓(xùn)練樣本集，基本訓(xùn)練樣本集從每一類(lèi)的已選取的400個(gè)樣本中隨機(jī)選取100個(gè)組成，此時(shí)基本訓(xùn)練樣本集有500個(gè)樣本，訓(xùn)練樣本集有2000個(gè)樣本，其余的作為測(cè)試樣本集。在調(diào)優(yōu)過(guò)程中，為了更能代表整個(gè)余類(lèi)的情況，減少計(jì)算的量，我們將訓(xùn)練樣本集由第一次實(shí)驗(yàn)時(shí)每一類(lèi)的400個(gè)樣本隨機(jī)選取300個(gè)樣本重新組成，基本訓(xùn)練樣本集從已選取的300個(gè)樣本隨機(jī)選取150重新組成，其余的均作為測(cè)試樣本集。此時(shí)基本訓(xùn)練樣本集有750個(gè)樣本，訓(xùn)練樣本集有1500個(gè)樣本，其余的作為測(cè)試樣本集。運(yùn)用我們的調(diào)優(yōu)方法反復(fù)實(shí)驗(yàn)以確定最后的對(duì)于訓(xùn)練樣本集最優(yōu)的決策函數(shù)集。為了對(duì)比說(shuō)明問(wèn)題，我們將每次所得到的決策函數(shù)集應(yīng)用于測(cè)試樣本集。其結(jié)果如下表所示：

通過(guò)以上表格，我們發(fā)現(xiàn)通過(guò)這樣的調(diào)優(yōu)過(guò)程不僅得到對(duì)于訓(xùn)練樣本集最優(yōu)的決策函數(shù)集（正確率已達(dá)100％），而且發(fā)現(xiàn)這樣的對(duì)訓(xùn)練樣本集最優(yōu)的決策函數(shù)集具有很強(qiáng)的泛化能力（正確率已達(dá)98.4％）。

5 討論

(1)本文的研究中解決了一個(gè)五類(lèi)字母圖象識(shí)別的分類(lèi)問(wèn)題，對(duì)解決多類(lèi)分類(lèi)問(wèn)題提供了很好的例子，可推廣到更多類(lèi)問(wèn)題的研究。對(duì)原問(wèn)題的二十六個(gè)字母圖象的識(shí)別的多類(lèi)分類(lèi)問(wèn)題的研究將是下一階段的研究重點(diǎn)。

(2)采用的支持向量機(jī)的算法時(shí)得到的支持向量數(shù)目過(guò)于龐大，即使借助于最先進(jìn)的計(jì)算機(jī)，計(jì)算的量都顯得很大，如何在分類(lèi)效果同等的情況下，使得到的支持向量盡可能少一點(diǎn)，或是篩選特征，刪去一些對(duì)分類(lèi)結(jié)果沒(méi)有影響的特征，減少計(jì)算的量，將是我們需要深入研究的另一個(gè)方面。

參考文獻(xiàn)：

[1]Christopher J CBurges.A Tutorial on support vector machines for pattern recognition[J].Data Mining and Knowledge Discovery，1998.2:121-167.

[2]張學(xué)工.關(guān)于統(tǒng)計(jì)學(xué)習(xí)理論與支持向量機(jī)[J].自動(dòng)化學(xué)報(bào)，2000，(1):32-42.

[3]Vapnik V N.The Nature of Statistical Learning Theory[M].New York：Springer-Verlag，1995:1-15.

[4]S R Gunn.Support Vector Machines for Classification and Regression[R].Technical Report，Images Speech and Intelligent Systems Research Group，University of Southampton，1997.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”