第十三章支持向量機(jī)第一頁，共36頁。

13.1支持向量機(jī)的分類思想

傳統(tǒng)模式識(shí)別技術(shù)只考慮分類器對(duì)訓(xùn)練樣本的情況，以最小化訓(xùn)練集上的分類錯(cuò)誤為目標(biāo)，通過為訓(xùn)練過程提供充足的訓(xùn)練樣本來試圖提高分類器在未見過的測(cè)試集上的識(shí)別率。然而，對(duì)于少量的訓(xùn)練樣本集合來說，我們不能保證一個(gè)很好地分類訓(xùn)練樣本的分類器也能很好地分類測(cè)試樣本。在缺乏代表性的小訓(xùn)練集情況下，一味的降低訓(xùn)練集上的分類錯(cuò)誤將會(huì)導(dǎo)致過渡擬合。支持向量機(jī)以結(jié)構(gòu)化風(fēng)險(xiǎn)最小化為原則，即兼顧訓(xùn)練誤差與測(cè)試誤差的最小化，具體體現(xiàn)在分類模型的選擇和模型參數(shù)的選擇上。第二頁，共36頁。13.1.1分類模型的選擇

要分類如圖13.1（a）所示的兩個(gè)樣本，我們看到圖中的曲線可以將（a）中的訓(xùn)練樣本全部分類正確，而直線則會(huì)錯(cuò)分兩個(gè)訓(xùn)練樣本；然而，對(duì)于（b）中的大量測(cè)試樣本，簡單的直線模型卻取得了更好的識(shí)別結(jié)果。應(yīng)該選擇什么樣的分類模型呢？第三頁，共36頁。圖13.1中復(fù)雜的曲線模型過渡擬合了訓(xùn)練樣本，因而在分類測(cè)試樣本時(shí)效果并不理想。我們了解到通過控制分類模型的復(fù)雜性可以防止過渡擬合，因此SVM更偏愛解釋數(shù)據(jù)的簡單模型——二維空間中的直線，三維空間中的平面和更高維空間中的超平面。第四頁，共36頁。13.1.2模型參數(shù)的選擇如圖13.2所示為2維空間中的兩類樣本，可以采用（a）圖中的任意直線將它們分開。但哪條直線才是最優(yōu)的選擇呢？第五頁，共36頁。第六頁，共36頁。直觀上，距離訓(xùn)練樣本太近的分類線對(duì)噪聲比較敏感，且對(duì)訓(xùn)練樣本之外的數(shù)據(jù)不太可能歸納得很好；而遠(yuǎn)離所有訓(xùn)練樣本的分類線將可能具有較好的歸納能力。所謂最優(yōu)分類線就是要求分類線不但能將兩類正確分開（訓(xùn)練錯(cuò)誤率為0），而且分類間隔最大，實(shí)際上，SVM正是從線性可分情況下的最優(yōu)分類面發(fā)展而來的，其主要的思想是尋找能夠成功分開兩類樣本并具有最大分類間隔的最優(yōu)分類超平面。

尋找最優(yōu)分類面的算法最終將轉(zhuǎn)化為一個(gè)二次型尋優(yōu)問題，從理論上說，得到的將是全局最優(yōu)點(diǎn)，解決了再神經(jīng)網(wǎng)絡(luò)方法中無法避免的局部極值問題。第七頁，共36頁。13.2支持向量機(jī)的理論基礎(chǔ)本節(jié)主要介紹SVM的理論基礎(chǔ)和實(shí)現(xiàn)原理，將分別闡述線性可分，非線性可分以及需要核函數(shù)映射這3種情況下的SVM。第八頁，共36頁。13.2.1線性可分情況下的SVM如果用一個(gè)線性函數(shù)（如二維空間中的直線，三維空間中的平面以及更高維數(shù)空間中的超平面）可以將分類樣本完全分開，就稱這些樣本是線性可分的。反之，如果找不到一個(gè)線性函數(shù)將兩類樣本分開，則稱這些樣本是非線性可分的。第九頁，共36頁。第十頁，共36頁。第十一頁，共36頁。13.2.2非線性可分情況下的C-SVM1.約束條件為處理樣本非線性可分的情況，我們放寬約束，引入松弛變量，此時(shí)約束條件變?yōu)椋旱谑?，?6頁。

值得注意的是對(duì)于不同的松弛變量可以分為3中情況考慮。

1.約束條件退化為線性可分時(shí)的情況即圖中所有“?！焙汀皒”的樣本點(diǎn)。

2.小于1約束條件放寬到允許樣本落在分類間隔內(nèi)，大于0指約束樣本仍可被分割超平面正確分類，對(duì)應(yīng)于圖中標(biāo)號(hào)為2的樣本。

3.大于1此時(shí)約束條件已放寬到允許有分類錯(cuò)誤的樣本

圖中第3類樣本，具體為圖中標(biāo)號(hào)為“。”和“x”。第十三頁，共36頁。第十四頁，共36頁。圖中標(biāo)號(hào)為“1”“2”“3”的均為在線性不可分情況下的支持向量。由于在這種情況下允許樣本落入分類間隔內(nèi)，我們常把這個(gè)分類間隔叫做軟間隔。第十五頁，共36頁。2.目標(biāo)函數(shù)利用一個(gè)附加錯(cuò)誤代價(jià)系數(shù)C后，目標(biāo)函數(shù)變?yōu)椋何覀兊哪繕?biāo)是最小化目標(biāo)函數(shù)。第十六頁，共36頁。通過調(diào)整C值可以實(shí)現(xiàn)分類超平面同時(shí)兼顧訓(xùn)練錯(cuò)誤和推廣能力。

不同的C值對(duì)于分類有不同的影響。（a）對(duì)應(yīng)一個(gè)相對(duì)較大的C值，導(dǎo)致了一個(gè)較小間隔但沒有錯(cuò)分訓(xùn)練樣本的分類超平面；（b）圖是將a中得到的分類超平面應(yīng)用于測(cè)試樣本中的效果，間隔較小，分類器的推廣能力不強(qiáng)，不夠理想；（c）中雖然有一個(gè)訓(xùn)練樣本被分錯(cuò)了，但得到了一個(gè)較大分類間隔的超平面；（d）中展示的是將c中得到的分類超平面應(yīng)用于測(cè)試樣本中的效果，間隔較大，分類器的推廣能力強(qiáng)。第十七頁，共36頁。第十八頁，共36頁。3優(yōu)化求解類似于線性可分情況下的推導(dǎo)，得到下面的對(duì)偶問題。在如下約束條件下：最大化后同樣在利用二次規(guī)劃技術(shù)解得最優(yōu)a值后，可以計(jì)算出w*和b*的值，最終的決策函數(shù)與（13-17）相同。第十九頁，共36頁。13.2.3需要核函數(shù)映射情況下的SVM核函數(shù)

第二十頁，共36頁。第二十一頁，共36頁。13.2.4推廣到多類問題一對(duì)多的最大響應(yīng)策略一對(duì)一的投票策略一對(duì)一的淘汰策略以上3種多類問題的推廣策略在實(shí)際應(yīng)用中一般都能取得滿意的結(jié)果，相比之下第2種和第3種在很多情況下能取得更好的效果。第二十二頁，共36頁。13.3SVM的matlab實(shí)現(xiàn)13.3.1訓(xùn)練——svmtrainSVMStruct=svmtrain(Training,group)參數(shù)說明：training是一個(gè)包含訓(xùn)練數(shù)據(jù)的m行n列的二維矩陣。每行表示1個(gè)訓(xùn)練樣本（特征向量），m表示訓(xùn)練樣本數(shù)目，n表示樣本的維數(shù)。group是一個(gè)訓(xùn)練樣本類標(biāo)簽的一維向量。其元素值只能為0或1，通常1表示正例，0表示反例。Group的維數(shù)必須和training的行數(shù)相等，以保證訓(xùn)練樣本同其他類別標(biāo)號(hào)一一對(duì)應(yīng)。返回值SVMStruct是訓(xùn)練所得的代表SVM分類器的結(jié)構(gòu)體，包含有關(guān)最佳分割超平面的種種信息。

第二十三頁，共36頁。1.設(shè)定核函數(shù)Svmtrain函數(shù)允許選擇非線性映射時(shí)核函數(shù)的種類或是指定自己編寫的核函數(shù)，方式如下：SVMStruct=svmtrain(…,’KernelFunction’,’KernelFunctionVaule);第二十四頁，共36頁。2.訓(xùn)練結(jié)果的可視化

當(dāng)訓(xùn)練數(shù)據(jù)是二維時(shí)可利用‘ShowPlot’選項(xiàng)來獲得訓(xùn)練結(jié)果的可視化解釋，調(diào)用形式如下：

svmtrain(…,’ShowPlot’,ShowPlotVaule);

此時(shí)只需設(shè)置ShowPlotVaule的值為1即可。

3.設(shè)定錯(cuò)誤代價(jià)C

前面對(duì)錯(cuò)誤代價(jià)系數(shù)C做了介紹，了解它對(duì)訓(xùn)練和分類結(jié)果的影響，下面給出設(shè)定C值得方法。因此，在調(diào)用svmtrain時(shí)設(shè)置一個(gè)優(yōu)化選項(xiàng)‘boxconstrain’即可。

SVMStruct=svmtrain(…,’boxconstrain’,C);

其中，C為錯(cuò)誤代價(jià)系數(shù)，默認(rèn)取值為Inf。第二十五頁，共36頁。13.3.2分類——svmclassify函數(shù)svmclassify的作用是利用訓(xùn)練得到的SVMStruct結(jié)構(gòu)對(duì)一組樣本進(jìn)行分類，常用調(diào)用形式為：Group=svmclassify（SVMStruct，Sample）；參數(shù)說明SVMStruct是訓(xùn)練得到的代表SVM分類器的結(jié)構(gòu)體，由函數(shù)svmstrain返回。Sample是要進(jìn)行分類的樣本矩陣，每行為1個(gè)樣本特征向量，總行數(shù)等于樣本數(shù)目，總列數(shù)是樣本特征的維數(shù)，它必須和訓(xùn)練該SVM時(shí)使用的樣本特征維數(shù)相同。返回值group是一個(gè)包含sample中所有樣本分類結(jié)果的列向量，其維數(shù)與sample矩陣的行數(shù)相同。第二十六頁，共36頁。13.4綜合案例——基于PCA和SVM的人臉識(shí)別系統(tǒng)13.4.1人臉識(shí)別的簡介

人臉識(shí)別技術(shù)就是以計(jì)算機(jī)為輔助手段，從靜態(tài)圖像或動(dòng)態(tài)圖像中識(shí)別人臉。一般來說，人臉識(shí)別分為3個(gè)部分：從具有復(fù)雜背景的場(chǎng)景中檢測(cè)并分離出人臉?biāo)诘膮^(qū)域；抽取人臉識(shí)別特征；然后進(jìn)行匹配和識(shí)別。第二十七頁，共36頁。13.4.2前期處理前期預(yù)處理的步驟如下：1.數(shù)據(jù)集的分割將整個(gè)數(shù)據(jù)集分為兩個(gè)部分——一個(gè)訓(xùn)練集和一個(gè)測(cè)試集。2.讀入數(shù)據(jù)集3.利用PCA降維去除像素之間的相關(guān)性。第二十八頁，共36頁。13.4.3數(shù)據(jù)規(guī)劃化數(shù)據(jù)規(guī)劃化又稱為數(shù)據(jù)尺度歸一化，是指將特征的某個(gè)屬性的取值范圍投射到一個(gè)特定的范圍之內(nèi)，以消除數(shù)值型屬性因大小范圍不一而影響基于距離的分類方法結(jié)果的公正性。1.數(shù)據(jù)規(guī)劃化的必要性（1）防止那些處在相對(duì)較大的數(shù)字范圍的特征壓倒那些處在相對(duì)較小的數(shù)字范圍的特征。（2）避免計(jì)算過程中可能出現(xiàn)的數(shù)字問題。第二十九頁，共36頁。2.數(shù)據(jù)規(guī)劃化方法在訓(xùn)練之前，需要對(duì)訓(xùn)練集合中的全體樣本進(jìn)行規(guī)格化。一般來說，有以下兩種常見的數(shù)據(jù)規(guī)劃化策略。（1）最大最小規(guī)格化方法該方法對(duì)被初試數(shù)據(jù)進(jìn)行一種線性轉(zhuǎn)換。（2）零均值規(guī)格化方法該方法是根據(jù)屬性A的均值和偏差來進(jìn)行規(guī)格化，可將訓(xùn)練集中的每個(gè)樣本特征的均值統(tǒng)一變換為0，并都具有統(tǒng)一的方差。3.實(shí)現(xiàn)人臉特征數(shù)據(jù)的規(guī)格化第三十頁，共36頁。13.4.4核函數(shù)的選擇到目前為止，要送入SVM的數(shù)據(jù)已經(jīng)準(zhǔn)備就緒，但在啟動(dòng)之前仍存在兩個(gè)問題：（1）選擇哪一種核函數(shù)；（2）確定核函數(shù)的參數(shù)以及錯(cuò)誤代價(jià)系數(shù)C的最佳取值。盡管最佳核函數(shù)的選擇一般與問題自身有關(guān)，但仍有規(guī)律可循。通常情況下優(yōu)先考慮徑向基核函數(shù)（RBF）：第三十一頁，共36頁。13.4.5參數(shù)選擇在選擇了RBF核函數(shù)的情況下總共有兩個(gè)參數(shù)需要確定，即RBF核自身的參數(shù)以及錯(cuò)誤代價(jià)系數(shù)。1.數(shù)據(jù)集格式化利用LibSVM的參數(shù)選擇工具grid.py，首先需要把數(shù)據(jù)集格式化為grid.py所要求的形式。2.搜索參數(shù)參數(shù)搜索工具grid.py是python的腳本文件，所以首先系統(tǒng)必須安裝python。此外搜索過程中還要用到工具gnuplot.exe以便將搜索過程可視化。第三十二頁，共36頁。13.4.6構(gòu)建多類SVM分類器我們編寫了函數(shù)multiSVMTrain()和multiSVMClassify()作為標(biāo)準(zhǔn)SVM工具箱的擴(kuò)展，從而得到可以解決多類問題的SVM。1.多類問題的訓(xùn)練在多類SV