【正文】 年 月 日 南京理工大學(xué) 課程考核課題 課程名稱： 數(shù)據(jù)挖掘與處理 課題題目： 支持向量機(jī) 組 長： 組 員： 陳志巖（ 912113850117） 成 績： 支持向量機(jī) 一、概述： 支持向量機(jī)是數(shù)據(jù)挖掘中的一項(xiàng)新技術(shù)，是在統(tǒng)計學(xué)習(xí)理論基礎(chǔ)上發(fā)展起來的一種新的數(shù)據(jù)挖掘方法，借助于最優(yōu)化方法解決機(jī)器學(xué)習(xí)問題的新工具。 統(tǒng)計學(xué)習(xí)因此而引入了泛化誤差界的概念，就是指真實(shí)風(fēng)險應(yīng)該由兩部分內(nèi)容刻畫，一是經(jīng)驗(yàn)風(fēng)險，代表了分類器在給定樣本上的誤差；二是置信風(fēng)險，代表了我們在多大程度上可以信任分類器在未知文本上分類的結(jié)果。 什么叫線性函數(shù)呢？在一維空間里就是一 個點(diǎn)，在二維空間里就是一條直線，三維空間里就是一個平面，可以如此想象下去，如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個統(tǒng)一的名稱 ——超平面（ Hyper Plane）！ 實(shí)際上，一個線性函數(shù)是一個實(shí)值函數(shù)（即函數(shù)的值是連續(xù)的實(shí)數(shù)），而我們的分類問題（例如這里的二元分類問題 ——回答一個樣本屬于還是不屬于一個類別的問題）需要離散的輸出值，例如用 1 表示某個樣本屬于類別 C1，而用 0表示不屬于（不屬于 C1也就意味著屬于 C2），這時候只需要簡單的在實(shí)值函數(shù)的基礎(chǔ)上附加一個閾值即可，通過分類函數(shù)執(zhí)行時得到的值大于還是小于這個 閾值來確定類別歸屬。以上是單個點(diǎn)到某個超平面的距離（就是間隔，后面不再區(qū)別這兩個詞）定義，同樣可以定義一個點(diǎn)的集合（就是一組樣本）到某個超平面的距離為此集合中離超平面最近的點(diǎn)的距離。 xi)+b]≥ 1 (i=1,2,? ,l) （ l是總的樣本數(shù)） 但我們常常習(xí)慣讓 式子的值和 0比較，因而經(jīng)常用變換過的形式： yi[(w因此在求 g(x)的時候， w才是變 量。核函數(shù)為支持向量機(jī)提供了一個重要 的構(gòu)成模塊，常用的核函數(shù)有多項(xiàng)式函數(shù)、徑向基函數(shù)和 Sigmoid函數(shù)等，在選用不同的核函數(shù)時可以構(gòu)造出不同的支持向量機(jī)。優(yōu)化問題也變?yōu)椋? * * * * *, 1 1 11( , ) ( ) ( ) ( , ) ( ) ( )2 l l li i j j i j i i i i ii j i iW k x x y? ? ? ? ? ? ? ? ? ? ?? ? ?? ? ? ? ? ? ? ?? ? ? 其中 *1 ( ) ( )li i iiwx? ? ????? ()fx可表示為 *1*1( ) ( ) ( ( ) ( ) )( ) ( )li i iili i iif x x x bk x x b? ? ? ?????? ? ? ?? ? ? ??? 1m in 2 TTHc? ? ?? 其中 ( ( , ))i j i j l lH y y k x x ?? ， 1[ 1, 1, , 1]T lc ?? ? ? ?， 12( , , , ) , , 1 , 2 , ,TNY y y y i j l?? 約束條件變?yōu)? 0 , 0 , 1, ,T iY i l??? ? ? 再采用二次規(guī)劃優(yōu)化的算法，即可實(shí)現(xiàn)學(xué)習(xí)算法 。如果提供的樣本線性不可分，結(jié)果很簡單，線性分類器的求解程序會無限循環(huán)，永遠(yuǎn)也解不出來。 再一次比較完整的重復(fù)一下我們要解決的問題：我們有屬于兩個類別的樣本點(diǎn)（并不限定這些點(diǎn)在二維空間中）若干，如圖， 圓形的樣本點(diǎn)定為正樣本（連帶著，我們可以把正樣本所屬的類叫做正類） ，方形的點(diǎn)定為負(fù)例。但是你也會發(fā)現(xiàn)，無論你給什么樣的數(shù)據(jù)，都是這個解！反映在圖中，就是 H1與 H2兩條直線間的距離無限大，這個時候，所有的樣本點(diǎn)（無論正樣本還是負(fù)樣本）都跑 到了 H1和 H2中間，而我們原本的意圖是， H1右側(cè)的被分為正類， H2 左側(cè)的被分為負(fù)類，位于兩類中間的樣本則拒絕分類（拒絕分類的另一種理解是分給哪一類都有道理，因而分給哪一類也都沒有道理）。 在二元的線性分類中，這個表示分類的標(biāo)記只有兩個值， 1 和 1（用來表示屬于還是不屬于這個類）。 線性分類器 線性分類器 (一定意義上 ,也可以叫做感知機(jī) ) 是最簡單也很有效的分類器形式 .在一個線性分類器中 ,可以看到 SVM 形成的思路 ,并接觸很多 SVM 的核心概念 . 用一個二維空間里僅有兩類樣本的分類問題來舉個小例子。這個差值叫做經(jīng)驗(yàn)風(fēng)險 Remp(w)。正是因?yàn)?SVM 關(guān)注的是 VC維，我們可以 了解 到，SVM解決問題的時候，和樣本的維數(shù)是無關(guān)的（甚至樣本是上萬維的都可以，這使得 SVM很適合用來解決文本分類的問題，當(dāng)然， 有這樣的能力也因?yàn)橐肓撕撕瘮?shù)）。 SVM正是這樣一種努力最小化結(jié)構(gòu)風(fēng)險的算法。二，這個形式并不局限于二維的情況，在 n 維空間中仍然可以使用這個表達(dá)式，只是式中的 w 成為了 n 維向量（在二維的這個例子中， w 是二維向量，為了表示起來方便簡潔，以下均不區(qū)別列向量和它的轉(zhuǎn)置，聰明的讀者一看便知）；三， g(x)不是中間那條直線的表達(dá)式，中間那條直線的表達(dá)式是 g(x)=0，即 wx+b=0，我們也把這個函數(shù)叫做分類面。 尋優(yōu)問題 上節(jié)說到我們有了一個線性分類函數(shù)，也有了判斷解優(yōu)劣的標(biāo)準(zhǔn) —— 即有了優(yōu)化