數(shù)據(jù)挖掘與處理論-在線瀏覽
2025-02-23 06:19本頁(yè)面
【正文】 后話），使得即 使樣本維數(shù)很高，也不會(huì)給存儲(chǔ)和計(jì)算帶來(lái)大麻煩。 線性分類(lèi)器 線性分類(lèi)器 (一定意義上 ,也可以叫做感知機(jī) ) 是最簡(jiǎn)單也很有效的分類(lèi)器形式 .在一個(gè)線性分類(lèi)器中 ,可以看到 SVM 形成的思路 ,并接觸很多 SVM 的核心概念 . 用一個(gè)二維空間里僅有兩類(lèi)樣本的分類(lèi)問(wèn)題來(lái)舉個(gè)小例子。中間的直線就是一個(gè)分類(lèi)函數(shù)，它可以將兩類(lèi)樣本完全分開(kāi)。 什么叫線性函數(shù)呢？在一維空間里就是一 個(gè)點(diǎn)，在二維空間里就是一條直線，三維空間里就是一個(gè)平面，可以如此想象下去，如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個(gè)統(tǒng)一的名稱(chēng) ——超平面（ Hyper Plane）！ 實(shí)際上，一個(gè)線性函數(shù)是一個(gè)實(shí)值函數(shù)（即函數(shù)的值是連續(xù)的實(shí)數(shù)），而我們的分類(lèi)問(wèn)題（例如這里的二元分類(lèi)問(wèn)題 ——回答一個(gè)樣本屬于還是不屬于一個(gè)類(lèi)別的問(wèn)題）需要離散的輸出值，例如用 1 表示某個(gè)樣本屬于類(lèi)別 C1，而用 0表示不屬于（不屬于 C1也就意味著屬于 C2），這時(shí)候只需要簡(jiǎn)單的在實(shí)值函數(shù)的基礎(chǔ)上附加一個(gè)閾值即可，通過(guò)分類(lèi)函數(shù)執(zhí)行時(shí)得到的值大于還是小于這個(gè) 閾值來(lái)確定類(lèi)別歸屬。若 g(xi)0，就判別為類(lèi)別 C1，若 g(xi)0，則判別為類(lèi)別 C2（等于的時(shí)候我們就拒絕判斷，呵呵）。 關(guān)于 g(x)=wx+b 這個(gè)表達(dá)式要注意三點(diǎn)：一，式中的 x 不是二維坐標(biāo)系中的橫軸，而是樣本的向量表示，例如一個(gè)樣本點(diǎn)的坐標(biāo)是 (3,8)，則 xT=(3,8) ，而不是 x=3（一般說(shuō)向量都是說(shuō)列向量，因此以行向量形式來(lái)表示時(shí)，就加上轉(zhuǎn)置）。 實(shí)際上很容易看出來(lái)，中間那條分界線并不是唯一的，我們把它稍微旋轉(zhuǎn)一下，只要不把兩類(lèi)數(shù)據(jù)分錯(cuò)，仍然可以達(dá) 到上面說(shuō)的效果，稍微平移一下，也可以。下一節(jié)我們就仔細(xì)說(shuō)說(shuō)分類(lèi)間隔，也補(bǔ)一補(bǔ)相關(guān)的數(shù)學(xué)知識(shí)。 在進(jìn)行文本分類(lèi)的時(shí)候，我們可以讓計(jì)算機(jī)這樣來(lái)看待我們提供 給它的訓(xùn)練樣本，每一個(gè)樣本由一個(gè)向量（就是那些文本特征所組成的向量）和一個(gè)標(biāo)記（標(biāo)示出這個(gè)樣本屬于哪個(gè)類(lèi)別）組成。 在二元的線性分類(lèi)中，這個(gè)表示分類(lèi)的標(biāo)記只有兩個(gè)值， 1 和 1（用來(lái)表示屬于還是不屬于這個(gè)類(lèi)）。 首先注意到如果某個(gè)樣本屬于該類(lèi)別 的話，那么 wxi+b0（記得么？這是因?yàn)槲覀兯x的 g(x)=wx+b 就通過(guò)大于 0 還是小于 0 來(lái)判斷分類(lèi)），而 yi也大于 0；若不屬于該類(lèi)別的話，那么 wxi+b0，而 yi 也小于 0，這意味著 yi(wxi+b)總是大于 0 的，而且它的值就等于 |wxi+b|?。ㄒ簿褪?|g(xi)|） 現(xiàn)在把 w和 b進(jìn)行一下歸一化，即用 w/||w||和 b/||w||分別代替原來(lái)的 w和 b，就是解析幾何中點(diǎn) xi到直線 g(x)=0 的距離公式 。以上是單個(gè)點(diǎn)到某個(gè)超平面的距離（就是間隔，后面不再區(qū)別這兩個(gè)詞）定義，同樣可以定義一個(gè)點(diǎn)的集合（就是一組樣本）到某個(gè)超平面的距離為此集合中離超平面最近的點(diǎn)的距離。 之所以如此關(guān)心幾何間隔這個(gè)東西，是因?yàn)閹缀伍g隔與樣本的誤分次數(shù)間存在關(guān)系：誤分次數(shù)的上界由幾何間隔決定！（當(dāng)然，是樣本已知的時(shí)候） 。因此 最大化幾何間隔 成了我們訓(xùn)練階段的目標(biāo)，而且，最大化分類(lèi)間隔并不是 SVM 的專(zhuān)利，而是早在線性分類(lèi)時(shí)期就已有的思想。而我們常用的方法并不是固定 ||w||的大小而尋求最大幾何間隔，而是固定間隔（例如固定為 1），尋找最小的 ||w||。一個(gè)尋優(yōu)問(wèn)題最重要的部分是目標(biāo)函數(shù)，顧名思義，就是指尋優(yōu)的目標(biāo)。之所以采用這種形式，是因?yàn)楹竺娴那蠼膺^(guò)程會(huì)對(duì)目標(biāo)函數(shù)作一系列變換。但是你也會(huì)發(fā)現(xiàn)，無(wú)論你給什么樣的數(shù)據(jù)，都是這個(gè)解！反映在圖中，就是 H1與 H2兩條直線間的距離無(wú)限大，這個(gè)時(shí)候，所有的樣本點(diǎn)（無(wú)論正樣本還是負(fù)樣本）都跑 到了 H1和 H2中間，而我們?cè)镜囊鈭D是， H1右側(cè)的被分為正類(lèi)， H2 左側(cè)的被分為負(fù)類(lèi)，位于兩類(lèi)中間的樣本則拒絕分類(lèi)（拒絕分類(lèi)的另一種理解是分給哪一類(lèi)都有道理，因而分給哪一類(lèi)也都沒(méi)有道理）。 造成這 種結(jié)果的原因是在描述問(wèn)題的時(shí)候只考慮了目標(biāo)，而沒(méi)有加入約束條件，約束條件就是在求解過(guò)程中必須滿足的條件，體現(xiàn)在我們的問(wèn)題中就是樣本點(diǎn)必須在 H1或 H2的某一側(cè)（或者至少在 H1 和 H2上），而不能跑到兩者中間。 xi)+b]≥ 1 (i=1,2,? ,l) （ l是總的樣本數(shù)） 但我們常常習(xí)慣讓 式子的值和 0比較，因而經(jīng)常用變換過(guò)的形式： yi[(w 約束條件用函數(shù) c來(lái)表示，你可以看出一共有 p+q個(gè)約束條件，其中 p 個(gè)是不等式約束， q個(gè)等式約束。要求 f(x)在哪一點(diǎn)上取得最小值（反倒不太關(guān)心這個(gè)最小值到底是多少，關(guān)鍵是哪一點(diǎn)），但不是在整個(gè)空間里找，而是在約束條件所劃定的一個(gè)有限的空間里找，這個(gè)有限的空間就是優(yōu)化理論里所說(shuō)的可行域。 關(guān)于可行域還有個(gè)概念不得不提，那就是凸集，凸集是指有這么一個(gè)點(diǎn)的集合，其中任取兩個(gè)點(diǎn)連一 條直線，這條線上的點(diǎn)仍然在這個(gè)集合內(nèi)部，因此說(shuō)“凸”是很形象的（一個(gè)反例是，二維平面上，一個(gè)月牙形的區(qū)域就不是凸集，你隨便就可以找到兩個(gè)點(diǎn)違反了剛才的規(guī)定）。 在這個(gè)問(wèn)題中，自變量就是 w，而目標(biāo)函數(shù)是 w的二次函數(shù)，所有的約束條件都是 w的線性函數(shù)（哎，千萬(wàn)不要把 xi當(dāng)成變量，它代表樣本，是已知的），這種規(guī)劃問(wèn)題有個(gè)很有名氣的稱(chēng)呼 —— 二次規(guī)劃（ Quadratic Programming， QP），而且可以更進(jìn)一步的說(shuō)，由于它的可行域是一個(gè)凸集，因此它是一個(gè) 凸二次規(guī)劃。 因?yàn)槲覀儗?shí)際上并不知道該怎么解一個(gè)帶約束的優(yōu)化問(wèn)題。 再一次比較完整的重復(fù)一下我們要解決的問(wèn)題：我們有屬于兩個(gè)類(lèi)別的樣本點(diǎn)（并不限定這些點(diǎn)在二維空間中）若干，如圖， 圓形的樣本點(diǎn)定為正樣本（連帶著，我們可以把正樣本所屬的類(lèi)叫做正類(lèi)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1