支持向量機分析課件

第五章支持向量機第五章支持向量機1內(nèi)容提要§1引言§2統(tǒng)計學(xué)習(xí)理論§3線性支持向量機§4非線性支持向量機§5支持向量回歸§6支持向量聚類內(nèi)容提要§1引言2§1引言一.SVM(SupportVectorMachine)的歷史神經(jīng)網(wǎng)絡(luò)分類器，Bayes分類器等是基于大樣本學(xué)習(xí)的分類器。Vapnik等從1960年開始關(guān)于統(tǒng)計學(xué)習(xí)理論的研究。統(tǒng)計學(xué)習(xí)理論是關(guān)于小樣本的機器學(xué)習(xí)理論。1992年支持向量機首次被引入。1995年Vapnik發(fā)展了支持向量機理論。支持向量機是基于統(tǒng)計學(xué)習(xí)理論的一種實用的機器學(xué)習(xí)方法?！?引言一.SVM(SupportVector3二.SVM的發(fā)展

⒈SVM理論的發(fā)展:最小二乘支持向量機(LS–SVM)多分類支持向量機(M-SVM)支持向量回歸(SVR)支持向量聚類(SVC)

⒉SVM與計算智能的融合:神經(jīng)網(wǎng)絡(luò)+支持向量機模糊邏輯+支持向量機遺傳算法+支持向量機小波分析+支持向量機主分量分析+支持向量機粗糙集理論+支持向量機二.SVM的發(fā)展

⒈SVM理論的發(fā)展:4三.SVM的應(yīng)用數(shù)據(jù)與文本分類系統(tǒng)建模及預(yù)測模式識別(圖像及語音識別，生物特征識別)異常檢測(入侵檢測，故障診斷)

時間序列預(yù)測三.SVM的應(yīng)用5§2統(tǒng)計學(xué)習(xí)理論

一.兩分類問題給定

l個觀測值:,i=1,2,...,l

?Rn

每個觀測值與一個標記相連:

,

i=1,2,...,l

?

{土1}

對于(2-類)分類,建立一個函數(shù):

:表示函數(shù)的參數(shù)

使得f能正確地分類未學(xué)習(xí)過的樣本第2類第1類§2統(tǒng)計學(xué)習(xí)理論一.兩分類問題第2類第1類6二.期望風(fēng)險與實驗風(fēng)險期望風(fēng)險最小化

其中x,y的聯(lián)合概率P(x,y)是未知的實驗風(fēng)險最小化

實驗風(fēng)險是由在訓(xùn)練集上測得的平均誤差所確定的如果訓(xùn)練樣本的個數(shù)是有限的,則實驗風(fēng)險最小化的方法不保證有高推廣能力二.期望風(fēng)險與實驗風(fēng)險7三.VC理論VC(Vapnik-Chervonenkis)維數(shù)分類函數(shù)的集合F的VC維數(shù)p=VCdim(F)定義(Vapnik–Chervonenkis).函數(shù)的集合F的VC維數(shù)是p,當且僅當存在點集

{xi}pi=1

使得這些點能夠被所有2p種可能的分類方式分開,且不存在集合

{xi}qi=1

(q>p)滿足這一性質(zhì)。在n維空間中,超平面集合的VC維數(shù)等于n+1。VC維數(shù)刻畫了“可能近似正確”意義上的學(xué)習(xí)能力。三.VC理論8例:VC維數(shù)例:VC維數(shù)9支持向量機分析課件10四.結(jié)構(gòu)風(fēng)險最小化

VC理論引入期望風(fēng)險的邊界,它依賴于實驗風(fēng)險與F的能力。這些邊界的最小化導(dǎo)出結(jié)構(gòu)風(fēng)險最小化原理:實驗風(fēng)險與VC可信度之和為最小其中

h與VC維數(shù)有關(guān),是能力概念的一種測度支持向量機是基于結(jié)構(gòu)風(fēng)險最小化原理構(gòu)造的一種學(xué)習(xí)機四.結(jié)構(gòu)風(fēng)險最小化11§3線性支持向量機

一.兩分類問題:線性分割情形第1類第2類許多決策邊界可以分割這些數(shù)據(jù)點出為兩類我們選取哪一個?§3線性支持向量機

一.兩分類問題:線性分割情形第12壞的決策邊界的例子第1類第2類第1類第2類壞的決策邊界的例子第1類第2類第1類第2類13好的決策邊界:間隔大決策邊界離兩類數(shù)據(jù)應(yīng)盡可能遠最大化間隔m第1類第2類m好的決策邊界:間隔大決策邊界離兩類數(shù)據(jù)應(yīng)盡可能遠第114二.最優(yōu)化問題設(shè){x1,...,xn}為數(shù)據(jù)集,yi

?{1,-1}為xi的類標記要求決策邊界正確地分類所有的點

T于是得到一個帶有約束的優(yōu)化問題二.最優(yōu)化問題設(shè){x1,...,xn}為數(shù)據(jù)集,15將上述最優(yōu)化問題轉(zhuǎn)換成其對偶問題:取Lagrange函數(shù)Φ(w,b;α)=1/2‖w‖2–∑ni=1

αi(yi[(w,xi)+b]

–1)則對偶問題由maxαW(α)=maxα(minw,bΦ(w,b;α))給出。由minw,bΦ(w,b;α)得

?Φ/?b=0?∑ni=1

αiyi=0?Φ/?w=0?w=∑ni=1

αiyixi將上述最優(yōu)化問題轉(zhuǎn)換成其對偶問題:16于是得到對偶問題這是一個二次規(guī)劃(QP)問題ai的全局最大值總可以求得W的計算于是得到對偶問題17解得α*=argminα1/2∑ni=1∑ni=1

αiαjyiyj<xi,xj>–∑n

k

=1

αkw*=∑ni=1

αiyixi,b*=–1/2<w*,xr+xs>其中Xr

與xs滿足

xr,xs>0,yr=–1,ys=1則

f(x)=sgn(<w*,x>+b)解得α*=argminα1/2∑ni=1∑ni=1α18三.解的性質(zhì)許多的ai為零w只是少數(shù)數(shù)據(jù)的線性組合具有非零ai的xi稱為支持向量(SV)決策邊界僅由SV確定

設(shè)tj(j=1,...,s)為支持向量的指標,于是

為了檢測一個新數(shù)據(jù)z計算如果WTZ+b30,則z屬于第一類;否則,屬于第二類。三.解的性質(zhì)許多的ai為零19a6=1.4四.幾何解釋第1類第2類a1=0.8a2=0a3=0a4=0a5=0a7=0a8=0.6a9=0a10=0a6=1.4四.幾何解釋第1類第2類a1=0.8a2=0a20§4非線性支持向量機

一.非線性分割問題§4非線性支持向量機

一.非線性分割問題21關(guān)鍵思想:

為了解決非線性分割問題,將xi變換到一個高維空間。

輸入空間:xi所在的空間特征空間:變換后f(xi)的空間如何變換?利用一個適當?shù)淖儞Qf,使分類變得容易些。

特征空間中的線性算子等價于輸入空間中的非線性算子。

關(guān)鍵思想:22變換可能出現(xiàn)的問題難以得到一個好的分類且計算開銷大SVM同時解決這兩個問題

最小化||w||2能得到好的分類利用核函數(shù)技巧可以進行有效的計算f()f()f()f()f()f()f()f()f(·)f()f()f()f()f()f()f()f()f()f()特征空間輸入空間變換可能出現(xiàn)的問題f()f()f()f()f23變換舉例定義核函數(shù)K(x,y)如下考慮下列變換內(nèi)積可由K計算,不必通過映射f(?)計算變換舉例24二.核函數(shù)技巧核函數(shù)K與映射f(.)之間的關(guān)系是作為核函數(shù)技巧這是已知的在應(yīng)用中,我們指定K,從而間接地確定f(?)，以代替選取f(?)。直觀地,K(x,y)表示我們對數(shù)據(jù)x和y之間相似性的一種描述，且來自我們的先驗知識。為了f(?)存在，K(x,y)需要滿足Mercer條件。二.核函數(shù)技巧25核函數(shù)舉例d階多項式核具有寬度s的徑向基函數(shù)核相當接近于徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)具有參數(shù)kand

q的Sigmoid核對所有的k和q，它不滿足Mercer條件

核函數(shù)舉例26三.非線性SVM算法將所有的內(nèi)積改為核函數(shù)

訓(xùn)練算法:線性的非線性的三.非線性SVM算法線性的非線性的27檢測算法:線性的非線性的對于一個新數(shù)據(jù)z，如果f30，則分到第1類；如果f<0，則分到第2類。檢測算法:線性的非線性的對于一個新數(shù)據(jù)z，如果f30，28例題設(shè)有5個1維數(shù)據(jù)點:x1=1,x2=2,x3=4,x4=5,x5=6,其中1,2,6為第1類,而4,5為第2類y1=1,y2=1,y3=-1,y4=-1,y5=1。利用2階多項式核K(x,y)=(xy+1)2C取為100先求ai

(i=1,…,5):例題設(shè)有5個1維數(shù)據(jù)點:29利用QP求解,得到a1=0,a2=2.5,a3=0,a4=7.333,a5=4.833注意到確實滿足約束條件支持向量為{x2=2,x4=5,x5=6}描述函數(shù)為確定b當x2,x4,x5位于上時,f(2)=1,f(5)=-1,f(6)=1,由此解得b=9利用QP求解,得到30描述函數(shù)的值12456第2類第1類第1類描述函數(shù)的值12456第2類第1類第1類31§5支持向量回歸

一.最小二乘法xf(x)i求解:§5支持向量回歸

一.最小二乘法xf(x)i求解:32二.線性支持向量回歸(SVR)

約束:+-0

求解:xf(x)二.線性支持向量回歸(SVR)約束:+-0求解:33線性支持向量回歸(SVR)

最小化:xf(x)+-0*

約束:線性支持向量回歸(SVR)最小化:xf(x)+-034Lagrange最優(yōu)化目標函數(shù)約束條件Lagrange最優(yōu)化目標函數(shù)約束條件35回歸公式回歸公式:性質(zhì):冗余性全局的且唯一的非線性推廣回歸公式回歸公式:性質(zhì):36三.非線性支持向量回歸f(x)x+-0f(x)(x)+-0輸入空間特征空間三.非線性支持向量回歸f(x)x+-0f(x)(37回歸公式線性的:非線性的:一般的:回歸公式線性的:非線性的:一般的:38多項式型:核函數(shù)的類型線性型:徑向基函數(shù)型:指數(shù)徑向基函數(shù)型:多項式型:核函數(shù)的類型線性型:徑向基函數(shù)型:指數(shù)徑向基函數(shù)型39幾點說明SVM基本上是一個兩分類器,修改QP公式,以允許多類別分類。常用的方法:以不同的方式智能地將數(shù)據(jù)集分為兩部分,對每一種分割方式用SVM訓(xùn)練,多類別分類的結(jié)果,由所有的SVM分類器的輸出經(jīng)組合后得到(多數(shù)規(guī)則)?！耙粚σ弧辈呗赃@種方法對N類訓(xùn)練數(shù)據(jù)兩兩組合,構(gòu)建C2N=N(N-1)/2個支持向量機。最后分類的時候采取“投票”的方式?jīng)Q定分類結(jié)果?！耙粚ζ溆唷辈呗赃@種方法對N分類問題構(gòu)建N個支持向量機,每個支持向量機負責(zé)區(qū)分本類數(shù)據(jù)和非本類數(shù)據(jù)。最后結(jié)果由輸出離分界面距離w·x+b最大的那個支持向量機決定。幾點說明40

軟件關(guān)于SVM的實現(xiàn)可以在下列網(wǎng)址找到/software.htmlSVMLight是最早的SVM軟件之一SVM的各種Matlabtoolbox也是可利用的LIBSVM可以進行多類別分類CSVM用于SVM分類rSVM用于SVM回歸mySVM用于SVM分類與回歸M-SVM用于SVM多類別分類

軟件41§6支持向量聚類

一.發(fā)展簡介Vapnik(1995):支持向量機Tax&Duin(1999):利用SV表示高維分布的特征Scholkopfetal.(2001):利用SV計算封閉數(shù)據(jù)點的輪廓線的集合Ben-Huretal.(2001):利用SV系統(tǒng)地搜索聚類解§6支持向量聚類一.發(fā)展簡介42二.方法的基本思想利用高斯核函數(shù)將數(shù)據(jù)點映射到高維特征空間在特征空間內(nèi)尋找封閉數(shù)據(jù)點的像點的最小球面將球面映射回數(shù)據(jù)空間，構(gòu)成封閉數(shù)據(jù)點的輪廓線的集合被每條輪廓線所封閉的點即屬于與同一個聚類減小高斯核函數(shù)的寬度，增加輪廓線的數(shù)目用一個大的軟間隙值處理重迭的聚類二.方法的基本思想43映射到高維特征空間映射到高維特征空間44三.主要步驟

⒈球分析⒉聚類分析三.主要步驟45設(shè)為一具有N個點的數(shù)據(jù)集用一個非線性變換Φ映射到高維特征空間尋求由限制的中心為a且半徑為R的最小閉球

⒈球分析設(shè)為46引入

Lagrangian函數(shù):引入松弛變量ξj＞0給出:

βj

＞0與μj＞0為Lagrange乘子,C為常數(shù)，C∑ξj為懲罰項引入Lagrangian函數(shù):引入松弛變量ξj＞0給出:47支持向量機分析課件48利用KKT(Karush-Kuhn-Tucker)完備性條件給出:

支持向量機分析課件49球球50由球心到像點的距離:當R=D(xj)時，則xj為支持向量在數(shù)據(jù)空間中封閉點的輪廓線為集合

{x|D(x)=R}由球心到像點的距離:51支持向量滿足ξi=0的點xi的像點位于特征空間之外或在邊界上如果0<βi<C,它的像點位于特征空間球的曲面上這些都是支持向量支持向量滿足ξi=0的點xi的像點位于特征空間之外或在邊52有界支持向量滿足ξi＞0及βi

＞0的點xi的像點位于特征空間之外，這樣的點有μi=0，因此βi=C這些是有界支持向量(BSVs)當C＞1時，不存在有界支持向量有界支持向量滿足ξi＞0及βi＞0的點xi的像點位于特53支持向量小結(jié)SVs位于聚類邊界上BSVs位于聚類邊界之外所有其它的點位于聚類邊界之內(nèi)支持向量小結(jié)SVs位于聚類邊界上54數(shù)據(jù)空間數(shù)據(jù)空間55⒉聚類分析聚類分配觀察:給定不同聚類中的一對數(shù)據(jù)點，任一連接它們的軌線必定走出特征空間中的球，即這條軌線包含使得D(y)>R的點y的弧段。所有點的鄰接矩陣﹛Aij﹜Aij=1，如果對于弧段上所有的y，D(y)≤

RAij=0，如果對于弧段上至少1個y，D(y)>R⒉聚類分析聚類分配56聚類分析:鄰接矩陣聚類分析:鄰接矩陣57計算主要部分的偽代碼GetAdjacentMatrix(A)初始化矩陣A,各元素清零fori←2tonforj←1toi-1ifj<ithenifa(i,j)=1theni、j兩行合并為第i行elseifa(i,j)=0then計算xi和xj之間各樣點x與球心距離d,一旦有樣點滿足d>R,則跳出循環(huán)ifd≤Rthena(i,j)=a(j,i)←1endendendend計算主要部分的偽代碼GetAdjacentMatrix58參數(shù)聚類水平由兩個參數(shù)控制:

1)q—Gaussian核的寬度參數(shù)。q增加，不相連的輪廓線增加，聚類的個數(shù)增加。

2)C—軟間隙常數(shù)。它允許特征空間中的球不封閉所有的點。參數(shù)聚類水平由兩個參數(shù)控制:59沒有BSV的例沒有BSV的例60有BSV的例.外點的個數(shù)由參數(shù)C控制nbs