【正文】 p o c h sTrainingBlueP e r f o r m a n c e i s 0 . 0 0 2 2 5 4 8 8 , G o a l i s 0決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 支持向量機(jī) ?提出的背景 (相對(duì)神經(jīng)網(wǎng)絡(luò)的不足 ) 1. 大量的控制參數(shù)。其結(jié)果只能用于訓(xùn)練數(shù)據(jù)點(diǎn)，而對(duì)訓(xùn)練數(shù)據(jù)以外的樣本點(diǎn)缺乏泛化能力。神經(jīng)網(wǎng)絡(luò)主要采用基于梯度的 BP學(xué)習(xí)算法，當(dāng)用于大規(guī)模問(wèn)題時(shí)收斂慢。使用 SVM方法，人們可以在很高維的空間里構(gòu)造好的分類(lèi)規(guī)則。 分類(lèi)的任務(wù)就是尋找分類(lèi)器 f： U→Y 且使期望風(fēng)險(xiǎn)最小。 ? 結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則 Vapnik在 1971年證明經(jīng)驗(yàn)風(fēng)險(xiǎn)最小值未必收斂于期望風(fēng)險(xiǎn)最小值，即 ERM不成立。這是小樣本統(tǒng)計(jì)理論與經(jīng)典統(tǒng)計(jì)理論的本質(zhì)區(qū)別，也是將 Vapnik統(tǒng)計(jì)方法稱(chēng)之為小樣本統(tǒng)計(jì)理論 的原因。在樣本點(diǎn)數(shù)目 l一定時(shí)，分類(lèi)器越復(fù)雜，即 VC維越大，則置信范圍越大，導(dǎo)致實(shí)際風(fēng)險(xiǎn)與經(jīng)驗(yàn)風(fēng)險(xiǎn)的差別越大。 從線性可分情況下的 最優(yōu)分類(lèi)超平面 發(fā)展而來(lái)的 ， 其本質(zhì)是在訓(xùn)練樣本中找出具有最優(yōu)分類(lèi)超平面的 支持向量 。若樣本集是線性可分的，則存在超平面 H： wx+b=0使得 (1)當(dāng) wxi+b?1時(shí)， yi=+1 (2)當(dāng) wxi+b?1時(shí)， yi=1 其中， w為權(quán)值向量， b為偏離值。 ? 分類(lèi)模型 ：尋求最優(yōu)超平面 H，使得 margin最大。首先對(duì)分割點(diǎn)空間進(jìn)行遺傳編碼，以分割點(diǎn)編碼構(gòu)成染色體，用基于粗糙集理論的適應(yīng)度函數(shù)來(lái)啟發(fā)并指導(dǎo)進(jìn)化，最終得到較優(yōu)的能充分體現(xiàn)離散化效果的分割點(diǎn)組合代碼串，從而找到離散化連續(xù)屬性集的全部分割點(diǎn)。 si為連續(xù)屬性 ci的起點(diǎn)值， ei為其終點(diǎn)值 )(122)()()(11iiililssiji sesmsc ???????決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 遺傳算法 對(duì) C’中的所有屬性進(jìn)行編碼形成的二進(jìn)制串長(zhǎng)度為： 因此，連續(xù)屬性集離散化問(wèn)題的搜索空間規(guī)模為 2l。 ????miikill1)1)((決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 遺傳算法 ? 適應(yīng)度函數(shù) ： 體現(xiàn)決策目標(biāo)的優(yōu)化方向 。 復(fù)制算子的作用效果將提高群體的平均適應(yīng)值。 s1’ = 00110 01011 11011 01100 01101 11101 10101 10011 s2’ = 10110 10100 10010 10101 00101 10101 10001 00111 決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 遺傳算法 ? 變異算子 ：以一個(gè)很小的概率隨機(jī)改變某條染色體中的某些基因位，形成新的種群，改變種群結(jié)構(gòu)。 決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 遺傳算法 ? 原始數(shù)據(jù) ? 分割點(diǎn) c1 c2 c3 d c1 c2 c3 d 19 119 1 270 2 26 120 1 202 1 93 15 1 199 2 186 1 11 120 2 101 2 121 1 150 1 266 1 58 1 141 1 65 1 214 1 172 1 屬性 (區(qū)間 ) c1() c2(58270) c3() 分割點(diǎn) c11 c12 c21 c22 c31 c32 c33 分割點(diǎn)基因 0010 0100 0011 1101 00011 00110 01110 分割點(diǎn)坐標(biāo) 決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 遺傳算法 ? 離散化結(jié)果 c1 c2 c3 d c1 c2 c3 d 2 1 1 1 2 2 3 2 2 1 2 1 2 1 3 1 2 0 0 1 0 1 0 2 2 1 3 1 1 1 0 2 2 1 1 2 2 1 1 1 1 1 1 1 2 2 3 1 1 0 0 1 1 1 1 1 2 0 0 1 2 1 3 1 2 1 3 1 決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 遺傳算法 ? Matlab(Geic Algrithm Direct Search Toolbox)提供了一個(gè)函數(shù) ga()，可直接求解某個(gè)函數(shù)的極小值；另外還提供了一個(gè)遺傳算法工具gatool。 )()1)((11irkjlijj ?????決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 遺傳算法 例： 設(shè)染色體 s1= 00110 10010 11011 01100 10101 11101 00111 10011 按下劃線所指進(jìn)行變異操作，得到一條新的染色體。方法如下：挑選 2個(gè)染色體串，按概率確定它們是否發(fā)生雜交，若未發(fā)生雜交，另取 2個(gè)染色體串，否則，先產(chǎn)生 m個(gè)隨機(jī)數(shù) r(i)(ci?C’ )，隨機(jī)數(shù)的范圍為 1到 l(i)(ki1)1，然后配對(duì)的 2個(gè)串相互對(duì)應(yīng)地交換從 到 的位段。因此使離散化后系統(tǒng)的分類(lèi)能力最大是我們的優(yōu)化目標(biāo)，因此可用決策屬性 d對(duì) C’的依賴(lài)度作為適應(yīng)度函數(shù)： )())((),( / UCardXCCarddCk dUX???? ???決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 遺傳算法 ? 復(fù)制算子 。 例如，若樣本規(guī)模為 200，連續(xù)屬性集 C’ ={c1,c2,c3}，k1=k2=4， k3=3。 把所有分割點(diǎn)表示成確定長(zhǎng)度的二進(jìn)制串，每個(gè)分割點(diǎn)與串中的一部分相聯(lián)系。其基本構(gòu)成要素有 染色體編碼、適應(yīng)度函數(shù)、遺傳算子 (遺傳、交叉、變異 )以及相關(guān)的運(yùn)行參數(shù)(種群規(guī)模： 20100；進(jìn)化代數(shù)： 100500；交叉概率 Pc： ；變異概率 Pm： ) 決策理論與方法 智能決策理論與方法 機(jī)器學(xué)習(xí) — 遺傳算法 ? 遺傳算法基本步驟 (1)確定遺傳算法的有關(guān)參數(shù)：群體規(guī)模 N，最大代數(shù) M，交叉概率 Pc，變異概率 Pm，停機(jī)準(zhǔn)則；初始化種群：隨機(jī)產(chǎn)生 N條表示 可能方案集 的染色體； (2)是否滿足停機(jī)準(zhǔn)則，若是，終止； (3)計(jì)算群體中每個(gè)個(gè)體的適應(yīng)值； (4)復(fù)制：根據(jù)適應(yīng)度函數(shù)進(jìn)行選擇生成中間群體； (5)交叉：以概率 Pc選擇兩個(gè)個(gè)體進(jìn)行染色體交換形成新的個(gè)體，替代老個(gè)體插入群體中 (6)變異：按概率 Pm選擇某條染色體的某一位進(jìn)行改變形成新的個(gè)體，替代老個(gè)體插入群體中； (7)轉(zhuǎn)到 (2)。