1、第四章 分類和預(yù)測(cè),主講教師：魏宏喜 (博士，副教授) E-mail: ,2,第四章 分類和預(yù)測(cè),4.1 分類和預(yù)測(cè)的定義 4.2 數(shù)據(jù)分類方法 決策樹 神經(jīng)網(wǎng)絡(luò) SVM 貝葉斯網(wǎng)絡(luò) 4.3 數(shù)據(jù)預(yù)測(cè)方法 線性回歸 非線性回歸,3,Support Vector Machine,SVM概述 SVM的基本原理 線性可分硬間隔SVM 線性不可分軟間隔SVM 非線性核函數(shù) SVM多分類問題 SVM工具,4,Support Vector Machine,SVM概述 SVM的基本原理 線性可分硬間隔SVM 線性不可分軟間隔SVM 非線性核函數(shù) SVM多分類問題 SVM工具,5,SVM概述,支持向量機(jī)(Su

2、pport Vector Machine, SVM)是由Cortes(科爾特斯)和Vapnik(瓦普尼克)于1995年首先提出。,V. Vapnik,6,SVM概述,支持向量機(jī)(Support Vector Machine, SVM)是由Cortes(科爾特斯)和Vapnik(瓦普尼克)于1995年首先提出。 SVM在解決小樣本、非線性等分類問題中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣到函數(shù)擬合等有關(guān)數(shù)據(jù)預(yù)測(cè)的應(yīng)用中。 手寫數(shù)字識(shí)別 人臉識(shí)別 文本分類 ,7,Support Vector Machine,SVM概述 SVM的基本原理 線性可分硬間隔SVM 線性不可分軟間隔SVM 非線性核函數(shù) SVM

3、多分類問題 SVM工具,8,SVM的基本原理,SVM是在兩類線性可分情況下，從獲得最優(yōu)分類面問題中提出的。 例如：有如下圖所示一個(gè)兩類分類問題，其中“紅色空心圓圈”表示一類，“綠色實(shí)心正方形”表示另一類。 問題：如何在二維平面上尋找一條直線，將這兩類分開。,9,SVM的基本原理,Find a linear hyperplane (decision boundary) that will separate the data,10,SVM的基本原理,One Possible Solution,11,SVM的基本原理,Another possible solution,12,SVM的基本原理,Oth

4、er possible solutions,13,SVM的基本原理,Which one is better? B1 or B2? How do you define better?,14,SVM的基本原理,SVM是在兩類線性可分情況下，從獲得最優(yōu)分類面問題中提出的。 最優(yōu)分類面就是要求分類面(二維情況下是分類線、高維情況下是超平面)不但能將兩類正確分開，而且應(yīng)使分類間隔最大。,15,SVM的基本原理,SVM是在兩類線性可分情況下，從獲得最優(yōu)分類面問題中提出的。 分類間隔：假設(shè)H代表分類線，H1和H2是兩條平行于分類線H的直線，并且它們分別過每類中離分類線H最近的樣本， H1和H2之間的距離叫做

5、分類間隔(margin)。,16,SVM的基本原理,SVM是在兩類線性可分情況下，從獲得最優(yōu)分類面問題中提出的。 SVM就是要在滿足條件的眾多分類面中，尋找一個(gè)能使分類間隔達(dá)到最大的那個(gè)分類面(二維情況下是分類線、高維情況下是超平面)。,17,SVM的基本原理,Find hyperplane maximizes the margin = B1 is better than B2,Margin越大，對(duì)新樣本 的分類(抗干擾)能力越強(qiáng)。,18,SVM的基本原理,Find hyperplane maximizes the margin = B1 is better than B2,Margin越大，

6、分類面可 移動(dòng)的范圍更大。,19,SVM的基本原理,問題：在給定的訓(xùn)練數(shù)據(jù)集上，如何求得具有最大分類間隔的分類面？ 設(shè)：兩類線性可分樣本集(x1, y1), (x2, y2), , (xn, yn)，其中：xiRd，yi+1, -1是類別標(biāo)號(hào)，i=1, 2, , n。 對(duì)于線性可分問題，分類超平面的定義如下： 其中，w和b是分類超平面的參數(shù)，且w=w1, w2, , wd是分類超平面的法向量，b是偏差。,20,SVM的基本原理,問題：在給定的訓(xùn)練數(shù)據(jù)集上，如何求得具有最大分類間隔的分類面？ 設(shè)：兩類線性可分樣本集(x1, y1), (x2, y2), , (xn, yn)，其中：xiRd，yi

7、+1, -1是類別標(biāo)號(hào)，i=1, 2, , n。 在分類超平面上方的樣本，滿足如下條件： 在分類超平面下方的樣本，滿足如下條件：,21,SVM的基本原理,問題：在給定的訓(xùn)練數(shù)據(jù)集上，如何求得具有最大分類間隔的分類面？ 設(shè)：兩類線性可分樣本集(x1, y1), (x2, y2), , (xn, yn)，其中：xiRd，yi+1, -1是類別標(biāo)號(hào)，i=1, 2, , n。 將上面兩個(gè)公式合并，對(duì)所有樣本的分類應(yīng)滿足如下公式：,22,SVM的基本原理,問題：在給定的訓(xùn)練數(shù)據(jù)集上，如何求得具有最大分類間隔的分類面？ 設(shè)：兩類線性可分樣本集(x1, y1), (x2, y2), , (xn, yn)，其

8、中：xiRd，yi+1, -1是類別標(biāo)號(hào)，i=1, 2, , n。 為了處理方便，假設(shè)所有樣本數(shù)據(jù)(xi, yi)，i=1, 2, , n，到分類超平面的距離至少為1，則對(duì)所有樣本數(shù)據(jù)都滿足：,滿足不等式等號(hào)條件的樣 本數(shù)據(jù)被稱為“支持向量”,23,SVM的基本原理,Margin是多少？,24,SVM的基本原理, 每個(gè)樣本到分類超平面的距離為yi*(w*xi+b)/|w| Margin = 2*支持向量到超平面的距離 = 2/|w|,Margin是多少？,SVM找出使得Margin達(dá)到最大的參數(shù)對(duì)(w, b)。,25,SVM的基本原理,在線性可分情況下，SVM通常被描述成一個(gè)帶有約束條件的優(yōu)化

9、問題：,26,SVM的基本原理,樣本數(shù)據(jù)是線性不可分時(shí)，該怎么辦？,27,SVM的基本原理,樣本數(shù)據(jù)是線性不可分時(shí)，該怎么辦？ 解決方法1：通過引入松弛變量(slack variables)，來構(gòu)建軟間隔SVM，帶約束條件的最優(yōu)化問題形式如下：,28,SVM的基本原理,樣本數(shù)據(jù)是線性不可分時(shí)，該怎么辦？ 解決方法1：通過引入松弛變量(slack variables)，來構(gòu)建軟間隔SVM，帶約束條件的最優(yōu)化問題形式如下：,29,SVM的基本原理,觀察懲罰因子C的不同取值對(duì)分類的影響,原始數(shù)據(jù),30,SVM的基本原理,觀察懲罰因子C的不同取值對(duì)分類的影響,C=100,31,SVM的基本原理,觀察懲

10、罰因子C的不同取值對(duì)分類的影響,C=1,000,32,SVM的基本原理,觀察懲罰因子C的不同取值對(duì)分類的影響,C=100,000,C越大分類超平面 越向離群點(diǎn)移動(dòng)， 最終的分類超平面 由離群點(diǎn)決定。,33,SVM的基本原理,樣本數(shù)據(jù)是線性不可分時(shí)，該怎么辦？ 解決方法2：將樣本數(shù)據(jù)轉(zhuǎn)換到高維空間中，在高維空間中尋找分類超平面。,34,SVM的基本原理,樣本數(shù)據(jù)是線性不可分時(shí)，該怎么辦？ 解決方法2：將樣本數(shù)據(jù)轉(zhuǎn)換到高維空間中，在高維空間中尋找分類超平面。,35,SVM的基本原理,樣本數(shù)據(jù)是線性不可分時(shí)，該怎么辦？ 解決方法2：將樣本數(shù)據(jù)轉(zhuǎn)換到高維空間中，在高維空間中尋找分類超平面。 數(shù)據(jù)變換到

11、高維空間可分的理由：當(dāng)維度增加到無限維的時(shí)候，一定可以讓任意兩個(gè)物體可分。 舉一個(gè)哲學(xué)的例子：世界上本來沒有兩個(gè)完全一樣的物體，對(duì)于所有的兩個(gè)物體，可通過增加維度來讓他們最終有所區(qū)別。 比如：兩本書，從(顏色，內(nèi)容)兩個(gè)維度來說，可能是一樣的，可以加上作者這個(gè)維度，實(shí)在不行還可以加入頁碼，擁有者，購買地點(diǎn) ,36,SVM的基本原理,樣本數(shù)據(jù)是線性不可分時(shí)，該怎么辦？ 解決方法2：將樣本數(shù)據(jù)轉(zhuǎn)換到高維空間中，在高維空間中尋找分類超平面。 使用一種非線性變換，可將原數(shù)據(jù)映射到高維空間中。,左圖中的點(diǎn)可被映射 成三維空間中的某個(gè)點(diǎn),37,SVM的基本原理,樣本數(shù)據(jù)是線性不可分時(shí)，該怎么辦？ 解決方法

12、2：將樣本數(shù)據(jù)轉(zhuǎn)換到高維空間中，在高維空間中尋找分類超平面。 使用一種非線性變換，可將原數(shù)據(jù)映射到高維空間中。 非線性變換的形式是什么樣的？,38,SVM的基本原理,樣本數(shù)據(jù)是線性不可分時(shí)，該怎么辦？ 解決方法2：將樣本數(shù)據(jù)轉(zhuǎn)換到高維空間中，在高維空間中尋找分類超平面。,通過拉格朗日乘子， 可得到其對(duì)偶問題。,39,SVM的基本原理,樣本數(shù)據(jù)是線性不可分時(shí)，該怎么辦？ 解決方法2：將樣本數(shù)據(jù)轉(zhuǎn)換到高維空間中，在高維空間中尋找分類超平面。 使用一種非線性變換，可將原數(shù)據(jù)映射到高維空間中。 非線性變換的形式是什么樣的？ 在數(shù)學(xué)上，數(shù)據(jù)的點(diǎn)積等價(jià)于使用一個(gè)核函數(shù)K(Xi, Xj)，即：K(Xi, X

13、j) = (Xi)(Xj)。,40,SVM的基本原理,樣本數(shù)據(jù)是線性不可分時(shí)，該怎么辦？ 解決方法2：將樣本數(shù)據(jù)轉(zhuǎn)換到高維空間中，在高維空間中尋找分類超平面。 常用的核函數(shù)形式如下：,多項(xiàng)式核,高斯核,S型核,41,SVM的基本原理,在核函數(shù)的作用下，SVM相當(dāng)于如下形式的網(wǎng)絡(luò)結(jié)構(gòu)：,S個(gè)支持向量 參與核變換。,42,SVM的基本原理,優(yōu)點(diǎn)： 有嚴(yán)格的數(shù)學(xué)推理； 小樣本分類器； 特別適合處理復(fù)雜的非線性分類問題。 缺點(diǎn)： 訓(xùn)練時(shí)間非常長； 無法直接處理多分類問題。,43,Support Vector Machine,SVM概述 SVM的基本原理 線性可分硬間隔SVM 線性不可分軟間隔SVM 非

14、線性核函數(shù) SVM多分類問題 SVM工具,44,SVM多分類問題,對(duì)于N(N2) 類分類問題，有兩種解決辦法： 1 vs (N1)：需要訓(xùn)練N個(gè)分類器，第i個(gè)分類器用于判斷樣本數(shù)據(jù)是否屬于第i類； 1 vs 1：需要訓(xùn)練N*(N 1)/2個(gè)分類器，分類器(i,j)能夠判斷樣本數(shù)據(jù)是屬于第i類，還是第j類。 在實(shí)際中，通常采用1 vs (N-1)方式解決多分類問題。,45,美國貝爾實(shí)驗(yàn)室對(duì)郵政手寫數(shù)字庫進(jìn)行如下實(shí)驗(yàn)（多分類問題）：,SVM多分類問題應(yīng)用實(shí)例,46,Support Vector Machine,SVM概述 SVM的基本原理 線性可分硬間隔SVM 線性不可分軟間隔SVM 非線性核函數(shù)

15、 SVM多分類問題 SVM工具,47,SVM工具,libsvm 由國立臺(tái)灣大學(xué)林智仁教授帶領(lǐng)的團(tuán)隊(duì)開發(fā)，版本眾多，包括：Matlab版，Java版，C+版等等。 .tw/cjlin/libsvm/index.html 函數(shù)：svm-train, svm-predict, svm-scale SVMlight 函數(shù)：svm_learn, svm_classify,48,SVM工具libsvm,Matlab環(huán)境下，配置libsvm。 第一步，下載最新的libsvm版本； 第二步，將下載下來的.zip文件解壓縮

16、，并將整個(gè)文件夾放到Matlab的toolbox文件夾內(nèi)； 第三步，在Matlab命令窗口中，鍵入如下命令： mex setup Would you like mex to locate installed compliers y/n? y 根據(jù)系統(tǒng)提示，選擇所需要的編譯器，并對(duì)編譯器的路徑進(jìn)行設(shè)置。,49,SVM工具libsvm,Matlab環(huán)境下，配置libsvm。 第四步，將這個(gè)路徑添加到Matlab的工作空間中：“File”“Set Path”“Add Folder”“選擇上述libsvm文件夾所在路徑”“Add with Subfolders”“再次選擇libsvm文件夾所在路徑”“

17、Save”“Close”； 第五步：將Matlab工作空間路徑改為libsvm所在路徑下面的matlab目錄，并在命令窗口中鍵入如下命令： make (如果執(zhí)行成功，則沒有任何提示),50,Support Vector Machine,SVM概述 SVM的基本原理 線性可分硬間隔SVM 線性不可分軟間隔SVM 非線性核函數(shù) SVM多分類問題 SVM工具,51,Support Vector Machine,課外閱讀資料： 1 Christopher J. C. Burges, “A tutorial on support vector machines for pattern recognition”J, Data Mining and Knowledge Discovery, 1998, Vol.2, pp. 121-167. 2 陶卿，姚穗，范勁松等，“一種新的機(jī)器學(xué)習(xí)算法：Supp