數(shù)據(jù)挖掘與處理論-文庫吧資料
2025-01-12 06:19本頁面
【正文】 ??），我們必須先問自己：這個(gè)問題是不是有解？如果有解，是否能找到？ 對于一般意義上的規(guī)劃問題，兩個(gè)問題的答案都是不一定，但凸二次規(guī)劃讓人喜歡的地方就在于，它有解（教科書里面為了嚴(yán)謹(jǐn)，常常加限定成分，說它有全局最優(yōu)解，由于我們想找的本來就是全局最優(yōu)的解，所以不加也罷），而且可以找到！（當(dāng)然，依據(jù)你使用的算法不同，找到這個(gè)解的速度，行話叫 收斂速度，會有所不同） 還可以發(fā)現(xiàn)，我們的線性分類器問題只有不等式約束，因此形式上看似乎比一般意義上的規(guī)劃問題要簡單，但解起來卻并非如此。 回頭再來看我們線性分類器問題的描述，可以看出更多的東西。注意可行域中的每一個(gè)點(diǎn)都要求滿足所有 p+q 個(gè)條件，而不是滿足其中一條或幾條就可以（切記，要滿足每個(gè)約束），同時(shí)可行域邊界上的點(diǎn)有一個(gè)額外好的特性，它們可以使不等式約束取得等號！而邊界內(nèi)的點(diǎn)不行。 關(guān)于這個(gè)式子可以這樣來理解：式中的 x是自變量，但不限定它的維數(shù)必須為 1（視乎你解決的問題空間維數(shù)，對我 們的文本分類來說，那可是成千上萬?。?。 xi)+b]1≥ 0 (i=1,2,? ,l) （ l是總的樣本數(shù)） 因此我們的兩類分類問題也被我們轉(zhuǎn)化成了它的數(shù)學(xué)形式，一個(gè)帶約束的最小值的問題 ， 從最一般的定義上說，一個(gè)求最小值的問題就是一個(gè)優(yōu)化問題（也叫尋優(yōu)問題），它同樣由兩部分組成，目標(biāo)函數(shù)和約束條件 。我們前文提到過把間隔固定為 1，這是指把所有樣本點(diǎn)中間隔最小的那一點(diǎn)的間隔定為 1（這也是集合的間隔的定義，有點(diǎn)繞嘴），也就意味著集合中的其他點(diǎn)間隔都不會小于 1，按照間隔的定義，滿足這些條件就相當(dāng)于讓下面的式子總是成立： yi[(w這下可好，所有樣本點(diǎn)都進(jìn)入了無法分類的灰色地帶。 接下來我們自然會問的就是，這個(gè)式子是否就描述了我們的問題呢？（回想一下，我們的問題是有一堆點(diǎn)，可以被分成兩類，我們要找出最好的分類面） 如果直接來解這個(gè)求最小值問題，很容易看出當(dāng) ||w||=0的時(shí)候就得到了目標(biāo)函數(shù)的最小值。不難看出當(dāng) ||w||2達(dá)到最小時(shí)， ||w||也達(dá)到最 小，反之亦然（前提當(dāng)然是 ||w||描述的是向量的長度，因而是非負(fù)的）。 而凡是求一個(gè)函數(shù)的最小值（或最大值）的問題都可以稱為尋優(yōu)問題（也叫作一個(gè)規(guī)劃問題），又由于找最大值的問題總可以通過加一個(gè)負(fù)號變?yōu)檎易钚≈档膯栴}，因此我們下面討論的時(shí)候都針對找最小值的過程來進(jìn)行。 尋優(yōu)問題 上節(jié)說到我們有了一個(gè)線性分類函數(shù)，也有了判斷解優(yōu)劣的標(biāo)準(zhǔn) —— 即有了優(yōu)化的目標(biāo)，這個(gè)目標(biāo)就是最大化幾何間隔，但是看過一些關(guān)于 SVM 的論文的人一定記得什么優(yōu)化的目標(biāo)是要最小化 ||w||這樣的說法，這是怎么回事呢？回頭再看看我們對間隔和幾何間隔的定義： 間隔：δ =y(wx+b)=|g(x)| 注 意到幾何間隔與 ||w||是成反比的，因此最大化幾何間隔與最小化 ||w||完全是一回事。 至此我們就明 白為何要選擇幾何間隔來作為評價(jià)一個(gè)解優(yōu)劣的指標(biāo)了，原來幾何間隔越大的解，它的誤差上界越小。下面這張圖更加直觀的展示出了幾何間隔的現(xiàn)實(shí)含義： H 是分類面，而 H1和 H2是平行于 H，且過離 H 最近的兩類樣本的直線，H1與 H， H2與 H 之間的距離就是幾何間隔。 當(dāng)用歸一化的 w 和 b 代替原值之后的間隔有一個(gè)專門的名稱，叫做幾何間隔，幾何間隔所表示的正是點(diǎn)到超平面的 歐氏距離，我們下面就簡稱幾何間隔為“距離 ”。有了這種表示法，我們就可以定義一個(gè)樣本點(diǎn)到某個(gè)超平面的間隔： δi=yi(wxi+b) 這個(gè)公式乍一看沒什么神秘的，也說不出什么道理，只是個(gè)定義而已，但我們做做變換，就能看出一些有意思的東西。如下： Di=(xi,yi) xi就是文本向量（維數(shù)很高）， yi就是分類標(biāo)記。 線性分類器 —— 分類間隔 上回說到對于文本分類這樣的不適定問題（有一個(gè)以上解的問題稱為不適定問題），需要有一個(gè)指標(biāo)來衡量解決方案（即我們通過訓(xùn)練建立的分類模型）的好壞，而分類間隔是一個(gè)比較好的指標(biāo)。此時(shí)就牽涉到一個(gè)問題，對同一個(gè)問題存在多個(gè)分類函數(shù)的時(shí)候，哪一個(gè)函數(shù)更好呢？顯然必須要先找一個(gè)指標(biāo)來量化 “好 ”的程度，通常使用的都是叫做 “分類間隔 ”的指標(biāo)。二，這個(gè)形式并不局限于二維的情況，在 n 維空間中仍然可以使用這個(gè)表達(dá)式，只是式中的 w 成為了 n 維向量（在二維的這個(gè)例子中， w 是二維向量，為了表示起來方便簡潔，以下均不區(qū)別列向量和它的轉(zhuǎn)置，聰明的讀者一看便知）；三， g(x)不是中間那條直線的表達(dá)式，中間那條直線的表達(dá)式是 g(x)=0，即 wx+b=0，我們也把這個(gè)函數(shù)叫做分類面。此時(shí)也等價(jià)于給函數(shù) g(x)附加一個(gè)符號函數(shù) sgn()，即 f(x)=sgn [g(x)]是我們真正的判別函數(shù)。 例如我們有一個(gè)線性函數(shù) g(x)=wx+b 我們可以取閾值為 0，這樣當(dāng)有一個(gè)樣本 xi需要判別的時(shí)候，我們就看 g(xi)的值。一般的，如果一個(gè)線性函數(shù)能夠?qū)颖就耆_的分開，就稱這些數(shù)據(jù)是線性可分的，否則稱為非線性可分的。如圖所示 C1和 C2是要區(qū)分的兩個(gè)類別，在二維平面中它們的樣本如上圖所示。 三、支持向量機(jī) ： 支持向量機(jī)定義： SVM是一種準(zhǔn)確度高的分類器，具有良好的容錯(cuò)和歸納能力，是一種建立在統(tǒng)計(jì)學(xué)理論的 VC理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理基礎(chǔ)上的 ， 支持向量機(jī)技術(shù)是從線性可分情況下的最優(yōu)分類面發(fā)展而來的 。多說一句，關(guān) 于文本分類這個(gè)問題究竟是不是線性可分的，尚沒有定論，因此不能簡單的認(rèn)為它是線性可分的而作簡化處理，在水落石出之前，只好先當(dāng)它是線性不可分的（反正線性可分也不過是線性不可分的一種特例而已，我們向來不怕方法過于通用）。 小樣本，并不是說樣
公司管理相關(guān)推薦
鄂ICP備17016276號-1