第6章分類預(yù)測支持向量機支持向量機支持向量機是在統(tǒng)計學(xué)理論的基礎(chǔ)上最新發(fā)展起來的新一代學(xué)習(xí)算法，是一種借助最優(yōu)化方法解決機器學(xué)習(xí)問題的新工具，也是數(shù)據(jù)挖掘中的一項新技術(shù)。支持向量機(SVM，SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機器學(xué)習(xí)問題中。原理【例】建立分類模型xyc

xyc5.211.2+1

18.08.0-14.014.1+1

19.55.5-19.011.0+1

20.07.0-14.95.5+1

17.06.4-13.28.0+1

16.05.1-17.213.9+1

12.56.0-18.07.0+1

17.72.0-13.010.5+1

16.83.7-16.27.9+1

14.57.5-1？分割線在分割線右側(cè)

C2在分割線左側(cè)

C1訓(xùn)練數(shù)據(jù)原理【例】建立分類模型分割線可以有無窮多個，分割線的位置不同，則對未分類點的分類結(jié)果也會不同：未分類點被分割線l1分類為C2而對于分割l2，則會被分類為C1怎樣分割合適？靠“中間”！l1l2原理設(shè)分割線：方法1兩個類中相距最近的點的連線的垂直平分線作為分割線。這種方法不能保證分割線能夠在中間位置，有時用這種方法甚至無法找出正確的分割線原理設(shè)分割線：方法2找出C1中臨近C2的兩個點并連線，平行推移到最臨近的C2中的點，取中間位置做分割線；或者反過來，找出C2中臨近C1的兩個點并連線，平行推移到最臨近的C1中的點，取中間位置做分割線。能使分類間隔較寬的分割線即為最優(yōu)分割線。支持向量確定分割線時，圖中提供垂直平分線的兩個點構(gòu)成的向量，支持了分割線的確定。這些點被稱為支持向量(SupprotVectors)邊界線分割線到間隔線（圖中虛線）的距離被稱為分類間隔，虛線稱為邊界線分割線方程二維平面

分割線方程二維平面

分類模型

分類模型

【例】建立分類模型

xyc

xyc5.211.2+1

18.08.0-14.014.1+1

19.55.5-19.011.0+1

20.07.0-14.95.5+1

17.06.4-13.28.0+1

16.05.1-17.213.9+1

12.56.0-18.07.0+1

17.72.0-13.010.5+1

16.83.7-16.27.9+1

14.57.5-1訓(xùn)練數(shù)據(jù)

【例】建立分類模型

分類間隔約為3.5【例】建立分類模型

分類間隔約為4.6

分類間隔最大化的過程?！纠拷⒎诸惸Ｐ?/p>

(9,11)(8,7)(12.5,6)得平行于得到分類模型

【例】建立分類模型(12.5,9)對未知數(shù)據(jù)點進(jìn)行分類有應(yīng)分類為C2。支持向量機分類模型：

支持向量機分類總結(jié)來說，支持向量機的原理就是根據(jù)給定的訓(xùn)練數(shù)據(jù)，找到一個最優(yōu)分割線或超平面，能夠正確地對訓(xùn)練數(shù)據(jù)進(jìn)行分類，建立起有效的分類模型，并可對新數(shù)據(jù)進(jìn)行正確分類。這里所說的最優(yōu)，就是使分割線或超平面距兩個類別的數(shù)據(jù)點具有最大的最小距離。支持向量機分類直觀上，在兩個類之間能夠找到一條分割線，使得C1類中的數(shù)據(jù)點距該分割線的距離的最小值，與C2類中的數(shù)據(jù)點距該分割線的距離的最小值相等，即分割線能夠在“中間”分割兩個類別的數(shù)據(jù)，則認(rèn)為這條分割線能夠較好地代表了對C1和C2類的分類。進(jìn)一步，如果能夠找到使這個距離的最小值最大的分割線，則找到了對數(shù)據(jù)進(jìn)行劃分的模型。PartI多維數(shù)據(jù)，分割超平面對于訓(xùn)練數(shù)據(jù)為多維數(shù)據(jù)的情況，則數(shù)據(jù)被映射到一個高維度的空間，同樣可以在這個多維空間中，找出一個超平面，將兩個不同類的數(shù)據(jù)集合區(qū)分開來。多維數(shù)據(jù)，分割超平面

多維數(shù)據(jù)，分割超平面

多維數(shù)據(jù)，分割超平面

定義分割超平面

定義分割超平面距超平面最近的點，到超平面的距離，可以表示為：

定義分割超平面

則

定義分割超平面

或等效地：

求解分割超平面拉格朗日函數(shù)

求解分割超平面拉格朗日函數(shù)對偶性SMOKaruch-Kuhn-Tucher（KKT）條件二次規(guī)劃方法

幾點擴展對于互相滲透的情況引入松弛變量

幾點擴展對于互相滲透的情況為“+”為“-”找不到符合條件的線性函數(shù)y≥0，x<0;否則x>0多類問題SVM是對二類問題設(shè)計的，其對應(yīng)方法也是針對二類問題的，如何處理多類問題?訓(xùn)練令C={c1,c2,...,ck}是類標(biāo)號的集合1-r方法：分解成k個二類問題每一個類ci

C創(chuàng)建一個二類問題，其中所有屬于ci的樣本都被看作正類，而其他樣本作為負(fù)類1-1方法：構(gòu)建k(k

1)/2個二類分類器每一個分類器用來區(qū)分一對類(ci,cj)為類(ci,cj)構(gòu)建二類分類器時，不屬于ci或cj的樣本被忽略掉32多類問題(續(xù))分類投票表決票的計算1-r方法如果一個樣本被分為正類，則正類得一票如果一個樣本被分為負(fù)類，則除正類之外的所有類都得到一票1-1方法

如果Cj把樣本分到y(tǒng)i類，則yi類得一票沖突處理分到多數(shù)類/少數(shù)類33多類問題:例例：C={c1,c2,c3,c4}1-r方法建立4個分類器(1/234,2/134,3/124,4/123)設(shè)這4個分類器分別把檢驗實例x

分類為+，

，

，

使用簡單的多數(shù)表決，c1得到最高的票4，而其他類僅僅得到3票，因此檢驗實例被分類為c11-1方法建立6個分類器(1/2,1/3,1/4,2/3,2/4,3/4)假設(shè)它們對

x投票結(jié)果如下表c1和c4都得到2票，而c2和c3僅僅得到1票34二類分類器類對+：c1

：c2

+：c1

：c3

+：c1

：c4

+：c2

：c3

+：c2

：c4

+：c3