數(shù)據(jù)挖掘與處理論(文件)
【正文】 足所有 p+q 個(gè)條件，而不是滿足其中一條或幾條就可以（切記，要滿足每個(gè)約束），同時(shí)可行域邊界上的點(diǎn)有一個(gè)額外好的特性，它們可以使不等式約束取得等號(hào)！而邊界內(nèi)的點(diǎn)不行。 一下子提了這么多術(shù)語(yǔ)，實(shí)在不是為了讓大家以后能向別人炫耀學(xué)識(shí)的淵博，這其實(shí)是我們繼續(xù)下去的一個(gè)重要前提，因?yàn)樵趧?dòng)手求一個(gè)問(wèn)題的解之前（好吧，我承認(rèn)，是動(dòng)計(jì)算機(jī)求??），我們必須先問(wèn)自己：這個(gè)問(wèn)題是不是有解？如果有解，是否能找到？ 對(duì)于一般意義上的規(guī)劃問(wèn)題，兩個(gè)問(wèn)題的答案都是不一定，但凸二次規(guī)劃讓人喜歡的地方就在于，它有解（教科書里面為了嚴(yán)謹(jǐn)，常常加限定成分，說(shuō)它有全局最優(yōu)解，由于我們想找的本來(lái)就是全局最優(yōu)的解，所以不加也罷），而且可以找到！（當(dāng)然，依據(jù)你使用的算法不同，找到這個(gè)解的速度，行話叫 收斂速度，會(huì)有所不同） 還可以發(fā)現(xiàn)，我們的線性分類器問(wèn)題只有不等式約束，因此形式上看似乎比一般意義上的規(guī)劃問(wèn)題要簡(jiǎn)單，但解起來(lái)卻并非如此。我們想求得這樣一個(gè)線性函數(shù)（在 n維空間中的線性函數(shù)）： g(x)=wx+b 使得所有屬于正類的點(diǎn) x+代入以后有 g(x+)≥ 1，而所有屬于負(fù)類的點(diǎn) x代入后有 g(x)≤ 1（之所以總跟 1比較，無(wú)論正一還是負(fù)一，都是因?yàn)槲覀児潭碎g隔為 1，注意間隔和幾何間隔的區(qū)別）。 你肯定能看出來(lái)，一旦求出了 w（也就求出了 b），那么中間的直線 H就知道了（因?yàn)樗褪?wx+b=0嘛，哈哈），那么 H1和 H2也就知道了（因?yàn)槿呤瞧叫械?，而且相隔的距離還是 ||w||決定的）。因此 g(x)的表達(dá)式嚴(yán)格的形式應(yīng)該是： g(x)=w,x+b 但是上面的式子還不夠好，你回頭看看圖中正樣本和負(fù)樣本的位置，想像一下，我不動(dòng)所有點(diǎn)的位置，而只是把其中一個(gè)正樣本點(diǎn)定為負(fù)樣本點(diǎn)（也就是把一個(gè)點(diǎn) 的形狀從圓形變?yōu)榉叫危?，結(jié)果怎么樣？三條直線都必須移動(dòng)（因?yàn)閷?duì)這三條直線的要求是必須把方形和圓形的點(diǎn)正確分開）！這說(shuō)明 w不僅跟樣本點(diǎn)的位置有關(guān)，還跟樣本的類別有關(guān)（也就是和樣本的“標(biāo)簽”有關(guān)）。其實(shí)簡(jiǎn)化了，只不過(guò)在你看不見的地方，以這樣的形式描述問(wèn)題以后，我們的優(yōu)化問(wèn)題少了很大一部分不等式約束（記得這是我們解不了極值問(wèn)題的萬(wàn)惡之源）。這必然使得它的適用范圍大大縮小，而它的很多優(yōu)點(diǎn)我們實(shí)在不原意放棄，怎么辦呢？是否有某種方法，讓線性不可分的數(shù)據(jù)變得線性可分呢？ 這時(shí)候，我們便需要核函數(shù)方法來(lái)解決問(wèn)題。 多項(xiàng)式核函數(shù)： 選用下列核函數(shù) 2( , ) [( , ) 1]iiK x x x x??，構(gòu)造的支持向量機(jī)的判別函數(shù)為： 2*1( ) s g n { [ ( , ) 1 ] }ni i iif x a y x x b?? ? ?? 其中， s 為支持矢量的個(gè)數(shù)。 支持向量機(jī)回歸的實(shí)現(xiàn) 如果將估計(jì)指示函數(shù)中得到的結(jié)論推廣到實(shí)函數(shù)（回歸）中，就變成了支持向量機(jī)回歸。這樣，在高維特征空間的線性回歸就對(duì)應(yīng)于低維輸入空間的非線性回歸。 目標(biāo)形式為 1m in 2 TTx H x c x? 其中 KKHKK???? ?????， YcY???????????，*x????????? 12( , , , ) , ( , ) , , 1 , 2 , ,TN ij i jY y y y K k x x i j l? ? ? 約束條件變?yōu)?*( 1 , 1 , , 1 , 1 ) 0 , , 0 , 1 , ,iix i l??? ? ? ? ? ? 再采用二次規(guī)劃優(yōu)化的算法，即可實(shí)現(xiàn)學(xué)習(xí)算法 。這樣就避免了在高維空間計(jì)算復(fù)雜的點(diǎn)積運(yùn)算。再根據(jù) KKT 條件，得到 **1**11* * * **( ) 0 0 1 , ,( ) 0 ( )li i i iilli i i i i iiii i i iiLC i lbLw x w xwLCC? ? ? ?? ? ? ?? ? ? ??????? ? ? ? ? ???? ? ? ? ? ? ???? ? ? ? ? ????? * * * * *, 1 1 11( , ) ( ) ( ) ( ) ( ) ( )2 l l li i j j i j i i i i ii j i iW x x y? ? ? ? ? ? ? ? ? ? ?? ? ?? ? ? ? ? ? ? ? ?? ? ? 在第一式約束條件下，最大化 *( , )W?? 求得參數(shù) *,ii??，代入代入第二式，得到回歸函數(shù) *1( ) ( ) ( )li i iif x x x b???? ? ? ??，其中 *ii??? 不等于零對(duì)應(yīng)的樣本數(shù)據(jù)就是支持向量。徑向基函數(shù)所對(duì)應(yīng)的特征空間可以是無(wú)窮維數(shù)，因此理論上講，一切有限的數(shù)據(jù)樣本在該特征空間中肯定是線性可分的。這個(gè)矩陣也稱為核矩陣，用 K表示。 核函數(shù)： 之前一直在討論的線性分 類器 ,器如其名，只能對(duì)線性可分的樣本做處理。其實(shí)以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于 0（不等于 0才對(duì) w起決定作用），這部分不等于 0的拉格朗日乘子后面所乘的樣本點(diǎn)，其實(shí)都落在 H1 和 H2上，也正是這部分樣本 （而不需要全部樣本）唯一的確定了分類函數(shù)，當(dāng)然，更嚴(yán)格的說(shuō)，這些樣本的一部分就可以確定，因?yàn)槔绱_定一條直線，只需要兩個(gè)點(diǎn)就可以，即便有三五個(gè)都落在上面，我們也不是全都需要。 樣本確定了 w，用數(shù)學(xué)的語(yǔ)言描述，就是 w可以表示為樣本的某種組合： w=α 1x1+α 2x2+? +α nxn 式子中的α i是一個(gè)一個(gè)的數(shù)（在
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1