《數據挖掘與知識發(fā)現(第2版)》第7章支持向量機

第7章支持向量機

《數據挖掘與知識發(fā)現》(第2版)數據挖掘與知識發(fā)現(第2版)(28-2)緒論

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

(7.2)

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

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

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

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

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

(7.4)

給定m，可以按照下式選取能夠被上述函數族打散的l個點：

xi=10-i，i=1,…,m(7.5)任意指定點的標簽

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

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

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

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

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

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

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

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

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

數據僅僅以點積的形式xi·xj出現。假設利用映射將數據映射到另外的一個歐氏空間H：

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

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

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

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

p次多項式分類器

高斯核函數：高斯徑向基函數分類器

雙曲正切核函數：特殊的雙層神經網絡數據挖掘與知識發(fā)