《數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)》第7章支持向量機(jī)

第7章支持向量機(jī)

《數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)》(第2版)數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-2)緒論

本章討論支持向量機(jī)的一般原理，簡要介紹如下幾個(gè)方面的內(nèi)容：學(xué)習(xí)機(jī)器泛化性能的界線性支持向量機(jī)非線性支持向量機(jī)支持向量機(jī)的VC維支持向量機(jī)應(yīng)用數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-3)引言V.Vapnik等人從20世紀(jì)60年代開始研究統(tǒng)計(jì)學(xué)習(xí)理論（StatisticalLearningTheory，SLT）。與傳統(tǒng)統(tǒng)計(jì)學(xué)相比，SLT是專門研究小樣本情況下機(jī)器學(xué)習(xí)規(guī)律的理論。統(tǒng)計(jì)學(xué)習(xí)理論的一個(gè)核心概念就是VC維(VCDimension)概念，它是描述函數(shù)集或?qū)W習(xí)機(jī)器的復(fù)雜性或者機(jī)器容量(Capacityofthemachine)的一個(gè)重要指標(biāo)，在此概念基礎(chǔ)上發(fā)展出了一系列關(guān)于統(tǒng)計(jì)學(xué)習(xí)的一致性、收斂速度、推廣性能(GeneralizationPerformance)等重要結(jié)論。90年代中期提出支持向量機(jī)(SupportVectorMachine,SVM)，使用SVM可以在高維空間構(gòu)造好的預(yù)測規(guī)則。SVM建立在VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理基礎(chǔ)之上，根據(jù)有限的樣本信息在模型的復(fù)雜性和學(xué)習(xí)能力之間尋求最佳折衷。促使SVM最初發(fā)展的問題包括偏倚方差均衡、容量控制、避免過擬合。對(duì)于訓(xùn)練數(shù)據(jù)數(shù)目有限的學(xué)習(xí)任務(wù)，如果訓(xùn)練集上的精度和機(jī)器的容量間得到恰當(dāng)?shù)钠胶?，則可以達(dá)到最佳泛化性能。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-4)學(xué)習(xí)機(jī)器泛化性能的界假定給定m個(gè)觀察值，每個(gè)觀察值包括：向量xiRn，i=1,…,m，以及相應(yīng)真實(shí)值yi。假定給定數(shù)據(jù)符合未知概率分布P(x,y)，即數(shù)據(jù)獨(dú)立同分布。假定機(jī)器任務(wù)是學(xué)習(xí)映射。通常將機(jī)器定義為可能映射集合，其中函數(shù)f(x,α)具有可調(diào)參數(shù)α。假定機(jī)器是確定性的。對(duì)給定的x及α，總是具有相同輸出f(x,α)。選擇特殊的參數(shù)α可得到訓(xùn)練后的機(jī)器。訓(xùn)練過的機(jī)器測試誤差的期望為：當(dāng)密度p(x,y)存在時(shí)，dP(x,y)可寫成p(x,y)dxdy。稱R(α)為期望風(fēng)險(xiǎn)。經(jīng)驗(yàn)風(fēng)險(xiǎn)定義為訓(xùn)練集上的平均誤差率：

(7.2)

對(duì)于特定的α和特定的訓(xùn)練集{xi,yi}，Remp(α)是固定的值。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-5)學(xué)習(xí)機(jī)器泛化性能的界稱為損失，取值為0或1。任取η，0η1，則下面的界以1-η的概率成立：其中h為非負(fù)整數(shù)，稱為VC維，用以度量容量。公式右邊為風(fēng)險(xiǎn)的界，右邊第二項(xiàng)也稱為VC置信度項(xiàng)。關(guān)于這個(gè)界有三個(gè)要點(diǎn)：第一，獨(dú)立于P(x,y)。第二，不能計(jì)算公式的左邊。第三，如果已知h，易得右邊。界對(duì)于所有備選學(xué)習(xí)機(jī)器族不是緊的，提供了放寬約束的可調(diào)整目標(biāo)。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-6)VC維VC維是函數(shù)族{f(α)}的性質(zhì)，可以對(duì)不同類的函數(shù)f定義VC維。考慮兩類別模式識(shí)別的函數(shù)：對(duì)任意x,α有f(x,α){-1,1}。若給定集合含有m個(gè)點(diǎn)，可以用2l種方式標(biāo)記，對(duì)每一種標(biāo)記，都可以找到{f(α)}中的函數(shù)正確地分開所有不同標(biāo)記的點(diǎn)，則稱點(diǎn)集被函數(shù)族打散。函數(shù)族{f(α)}的VC維定義為能夠被{f(α)}打散的訓(xùn)練點(diǎn)數(shù)目的最大值。如果VC維為h，則至少存在一個(gè)含有h個(gè)點(diǎn)的點(diǎn)集可以被打散，但是并不是所有的h個(gè)點(diǎn)的點(diǎn)集都被打散。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-7)Rn中有向超平面對(duì)點(diǎn)的打散以二維情形為例，{f(α)}由有向直線組成，給定直線后，直線的方向由圖7.1中的箭頭表示，在直線箭頭指向一側(cè)的點(diǎn)分配到+1類，另一側(cè)的點(diǎn)分配到-1類。可以找到3個(gè)點(diǎn)被直線族打散4個(gè)點(diǎn)則不可能被直線族打散，故R2中的有向直線族的VC維是3。

圖7.1R2中的三個(gè)點(diǎn)，被有向直線族打散定理7.1：考慮Rn中的m個(gè)點(diǎn)構(gòu)成的點(diǎn)集，選擇其中一個(gè)點(diǎn)作為原點(diǎn)，則有向超平面族打散m個(gè)點(diǎn)，當(dāng)且僅當(dāng)其余點(diǎn)的位置向量線性無關(guān)。推論：Rn中有向超平面族的VC維是n+1。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-8)VC維和參數(shù)個(gè)數(shù)直觀上，具有更多參數(shù)的學(xué)習(xí)機(jī)器具有更高VC維，而更少參數(shù)的學(xué)習(xí)機(jī)器具有更低VC維。反例：一個(gè)僅具有一個(gè)參數(shù)的學(xué)習(xí)機(jī)器，其VC維卻為無窮。定義階躍函數(shù)

(x)，xR:{(x)=1,x0;

(x)=-1,x0}?？紤]如下定義的僅含一個(gè)參數(shù)的函數(shù)組：

f(x,α)≡θ(sin(αx))},x,αR

(7.4)

給定m，可以按照下式選取能夠被上述函數(shù)族打散的l個(gè)點(diǎn)：

xi=10-i，i=1,…,m(7.5)任意指定點(diǎn)的標(biāo)簽

y1,y2,…,ym，yi{-1,1}(7.6)則只要選取α為

(7.7)就可以使得f(α)正確標(biāo)記l個(gè)點(diǎn)，也就是說{f(α)}打散這l個(gè)點(diǎn)。{f(α)}的VC維為無窮大。

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-9)通過最小化h最小化界對(duì)任意m值，都有VC維是關(guān)于h的單調(diào)遞增函數(shù)。給定若干經(jīng)驗(yàn)風(fēng)險(xiǎn)為零的學(xué)習(xí)機(jī)器，可以選擇其關(guān)聯(lián)函數(shù)集具有最小VC維的學(xué)習(xí)機(jī)器，從而獲得實(shí)際風(fēng)險(xiǎn)的較好上界。給出一個(gè)具有無窮VC維，但性能良好的機(jī)器實(shí)例。圖7.2表明當(dāng)h/l>0.37(η=0.05且l=10000)時(shí)，VC置信度超過1，當(dāng)取更大值時(shí)，界不再是緊的。圖7.2VC維是關(guān)于h的單調(diào)遞增函數(shù)數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-10)結(jié)構(gòu)風(fēng)險(xiǎn)最小化VC置信度項(xiàng)依賴于函數(shù)類的選擇，但是經(jīng)驗(yàn)風(fēng)險(xiǎn)和實(shí)際風(fēng)險(xiǎn)依賴于通過訓(xùn)練過程選擇的一個(gè)特定函數(shù)。由于VC維是整數(shù)，所以不可能令VC維h平滑變化。為選擇的函數(shù)子集具有最小化的風(fēng)險(xiǎn)界。如圖7.3將全部函數(shù)類劃分為嵌套子集，任意子集都可以計(jì)算其h值或其界。利用結(jié)構(gòu)風(fēng)險(xiǎn)最小化，能夠最小化實(shí)際風(fēng)險(xiǎn)界的函數(shù)子集?？梢酝ㄟ^訓(xùn)練一系列學(xué)習(xí)機(jī)器，每一個(gè)子集訓(xùn)練一個(gè)機(jī)器，對(duì)每一個(gè)給定子集，訓(xùn)練的目標(biāo)是最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)。然后可以獲得經(jīng)驗(yàn)風(fēng)險(xiǎn)與VC置信項(xiàng)之和最小的訓(xùn)練過的機(jī)器。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-11)線性支持向量機(jī)(一)可分情形設(shè)訓(xùn)練數(shù)據(jù)為{xi,yi}，i=1,…,l，yi{-1,1}，xiRd。假定有若干劃分正類和負(fù)類的分離超平面。超平面上的點(diǎn)x滿足w?x+b=0，其中w是超平面的法線向量，/為原點(diǎn)到超平面的垂直距離，其中是w的歐幾里得范數(shù)。令d+(d-)表示超平面到最近正例(反例)的距離。定義分離超平面的“間隔”為d++d-。對(duì)于線性可分情形，支持向量算法尋找具有最大間隔的分離超平面。假設(shè)所有訓(xùn)練數(shù)據(jù)滿足下列約束：超平面上的點(diǎn)到原點(diǎn)的距離分別為和因此，可以通過最小化獲得具有最大間隔的超平面對(duì)。

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-12)線性支持向量機(jī)對(duì)每個(gè)不等式約束，引入正的拉格朗日乘子αi，i=1,…,m，構(gòu)造拉格朗日算子如下：

(7.11)關(guān)于w，b最小化LP，令LP關(guān)于w，b的梯度為零，則得：

由于在對(duì)偶形式中是等式約束，代入(7.11)得拉格朗日算子有不同的下標(biāo)，P對(duì)應(yīng)原始問題，D對(duì)應(yīng)對(duì)偶問題，LP和LD由同一目標(biāo)函數(shù)導(dǎo)出，但是具有不同約束。解通過最小化LP或最大化LD獲得。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-13)線性支持向量機(jī)(二)Karush—Kuhn—Tucker條件

Karush—Kuth—Tucker(KKT)條件在約束優(yōu)化理論中具有重要作用。對(duì)于上述原始問題，KKT條件如下：

(7.19)支持向量機(jī)的約束總是線性，滿足正則假定。KKT條件是w，b，α為解的充分必要條件。因此，求解SVM問題相當(dāng)于求解KKT條件的解。作為直接應(yīng)用，w由訓(xùn)練過程完全確定，但閾值b不是，盡管其被隱含確定。但是可以通過KKT補(bǔ)充條件(7.19)很容易求得b(選擇αi0的i)。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-14)線性支持向量機(jī)(三)測試當(dāng)?shù)玫接?xùn)練好的支持向量機(jī)后，判別超平面介于超平面H1與H2中間并平行于兩者，判定測試模式x位于判別超平面的哪一側(cè)，并據(jù)此分配相應(yīng)的類別標(biāo)簽，也即用給x標(biāo)定。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-15)線性支持向量機(jī)(四)非可分情形可分?jǐn)?shù)據(jù)的算法應(yīng)用到不可分?jǐn)?shù)據(jù)時(shí)，不能找到可行解。可以引入正松弛變量ξi，i=,…,m，約束變?yōu)椋耗繕?biāo)函數(shù)為，可以針對(duì)錯(cuò)誤賦一個(gè)額外代價(jià)，其中C表示對(duì)錯(cuò)誤懲罰的程度。當(dāng)取k=1時(shí)，其解為：數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-16)線性支持向量機(jī)原始拉格朗日算子：

(7.28)其中μi是使得ξi為正的拉格朗日乘子。原始問題的KKT條件如下：(i取值從1到訓(xùn)練點(diǎn)數(shù)目m，ν取值從1到數(shù)據(jù)維數(shù))數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-17)非線性支持向量機(jī)

數(shù)據(jù)僅僅以點(diǎn)積的形式xi·xj出現(xiàn)。假設(shè)利用映射將數(shù)據(jù)映射到另外的一個(gè)歐氏空間H：

(7.38)那么，訓(xùn)練算法僅僅通過H中的點(diǎn)積運(yùn)算φ(xi)·φ(xj)依賴于數(shù)據(jù)。如果存在核函數(shù)K使得K(xi,xj)=φ(xi)·φ(xj)，則在訓(xùn)練算法中僅使用K即可，而不需要明確地給出φ。例如：

(7.39)H是無窮維的，使用明確的φ并不方便。如果在算法中用K(xi,xj)代替所有的xi·xj，算法將很容易地生成無窮維空間的支持向量機(jī)。(一)硬間隔非線性支持向量機(jī)硬間隔非線性支持向量機(jī)的數(shù)學(xué)形式與線性可分情形的支持向量機(jī)相似，只是輸入模式x被特征函數(shù)φ(x)代替，而特征函數(shù)的點(diǎn)積φ(xi)·φ(xj)被核函數(shù)K(xi,xj)代替。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-18)非線性支持向量機(jī)得到的支持向量機(jī)的w位于歐氏空間H中，在測試階段，支持向量機(jī)分類器通過計(jì)算給定點(diǎn)x與w的點(diǎn)積，或明確地說通過計(jì)算下式的符號(hào)，給出模式x的標(biāo)簽：其中si是支持向量，Ns為支持向量個(gè)數(shù)。因此，可以避免明確地計(jì)算φ(x)，而是用K(si,x)=φ(si)·φ(x)代替。令L表示數(shù)據(jù)所在空間(L表示低維，H表示高維：通常情況下，φ是從低維空間到高維空間的映射)。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-19)非線性支持向量機(jī)(二)軟間隔非線性支持向量機(jī)通過引入松弛變量ξ和容量C，可以得到軟間隔非線性SVM分類器。容量參數(shù)C用于平衡分類錯(cuò)誤懲罰，由用戶調(diào)整，或者由SVM軟件包自動(dòng)優(yōu)化。當(dāng)取較大C值時(shí)，對(duì)分類錯(cuò)誤的懲罰增大，從而使得分類錯(cuò)誤的模式數(shù)目減少。另一方面，當(dāng)C增大時(shí)，間隔變小，造成分類器對(duì)訓(xùn)練集中的噪音數(shù)據(jù)和錯(cuò)誤敏感。在這對(duì)矛盾之間(小的C值對(duì)應(yīng)大間隔分類器，大的C值對(duì)應(yīng)較小分類錯(cuò)誤)，需要求出C的最優(yōu)值，通常通過最大化交叉驗(yàn)證預(yù)測精度來實(shí)現(xiàn)。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-20)非線性支持向量機(jī)(三)ν-SVM分類器ν-SVM分類的優(yōu)化問題是：該問題的原始拉格朗日函數(shù)是：

其中αi，βi，δ0為拉格朗日乘子。其對(duì)偶問題為：

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-21)非線性支持向量機(jī)對(duì)上述問題，求解后得到的ν-SVM分類器為：(四)處理不平衡數(shù)據(jù)的加權(quán)SVM不平衡數(shù)據(jù)：兩類數(shù)據(jù)比例不平衡，某類的數(shù)目很多在訓(xùn)練后的SVM起支配作用。兩類模式的分類錯(cuò)誤代價(jià)不同對(duì)兩類模式使用不同的懲罰C+和C-。不利的錯(cuò)誤類型具有高懲罰，體現(xiàn)在SVM分類器就是最小化該類錯(cuò)誤。原始問題的為：數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-22)非線性支持向量機(jī)等價(jià)的對(duì)偶問題為：引入特征函數(shù)x→φ(x)，并以核函數(shù)K(xi,xj)代替φ(xi)·φ(xj)后，可以給出非線性情形的數(shù)學(xué)形式。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-23)非線性支持向量機(jī)(五)多類別SVM分類一些多類別SVM分類方法將訓(xùn)練集分解成若干兩類問題。一對(duì)一方法對(duì)訓(xùn)練集中的任意兩類，采用一對(duì)一方法訓(xùn)練兩類SVM，k類問題將得出k(k-1)/2個(gè)SVM模型。在測試階段，采用委員會(huì)投票的方式記錄這些SVM模型的判別，得票最多的類別就是該模式所屬的類別。當(dāng)k較大時(shí)，采用一對(duì)一方式將會(huì)導(dǎo)致所需訓(xùn)練的SVM數(shù)目過大。一對(duì)多方法一對(duì)多過程需要的模型數(shù)目較少，對(duì)于k類問題，僅需要k個(gè)SVM分類器。第i個(gè)SVM分類器在將第i類模式標(biāo)記為+1，其他類模式標(biāo)記為-1的數(shù)據(jù)上訓(xùn)練。一對(duì)多方式訓(xùn)練數(shù)據(jù)時(shí)可能由于-1類模式過多導(dǎo)致過于不平衡。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(28-24)Mercer條件及Mercer定理定理7.2(Mercer定理)核函數(shù)可以表示為K(x,y)=φ(x)·φ(y)當(dāng)且僅當(dāng)對(duì)于任意函數(shù)，如果有限，則滿足Mercer定理的核函數(shù)稱為正定核函數(shù)。以下函數(shù)都滿足Mercer定理：多項(xiàng)式核函數(shù)：

p次多項(xiàng)式分類器

高斯核函數(shù)：高斯徑向基函數(shù)分類器

雙曲正切核函數(shù)：特殊的雙層神經(jīng)網(wǎng)絡(luò)數(shù)據(jù)挖掘與知識(shí)發(fā)