智能決策理論與方法

智能決策理論與方法演示文稿本文檔共51頁(yè)；當(dāng)前第1頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分優(yōu)選智能決策理論與方法本文檔共51頁(yè)；當(dāng)前第2頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)是從模擬人類的學(xué)習(xí)行為出發(fā)，研究客觀世界和獲取各種知識(shí)與技能的一些基本方法（如歸納、泛化、特化、類比等），并借助于計(jì)算機(jī)科學(xué)與技術(shù)原理建立各種學(xué)習(xí)模型，從根本上提高計(jì)算機(jī)智能和學(xué)習(xí)能力。研究?jī)?nèi)容是根據(jù)生理學(xué)、認(rèn)知科學(xué)對(duì)人類學(xué)習(xí)機(jī)理的了解，建立人類學(xué)習(xí)的計(jì)算模型或認(rèn)知模型；發(fā)展各種學(xué)習(xí)理論和學(xué)習(xí)方法，研究通用的學(xué)習(xí)算法并進(jìn)行理論上的分析；建立面向任務(wù)且具有特定應(yīng)用的學(xué)習(xí)系統(tǒng)。本文檔共51頁(yè)；當(dāng)前第3頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：泛化歸納學(xué)習(xí)是指從給定的關(guān)于某個(gè)概念的一系列已知的正例和反例中歸納出一個(gè)通用的概念描述。泛化(Generalization)是用來(lái)擴(kuò)展一假設(shè)的語(yǔ)義信息，使其能夠包含更多的正例。泛化所得到的結(jié)論并不總是正確的。常用泛化方法：將常量轉(zhuǎn)為變量規(guī)則：對(duì)于概念F(v)，如果v的某些取值a,b,…使F(v)成立，則這些概念可被泛化為：對(duì)于v的所有值，F(xiàn)(v)均成立：本文檔共51頁(yè)；當(dāng)前第4頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：泛化消除條件規(guī)則：一個(gè)合取條件可看作是對(duì)滿足此概念的可能實(shí)例集的一個(gè)約束。消除一個(gè)條件，則該概念被泛化。添加選項(xiàng)：通過(guò)添加更多條件，使得有更多的實(shí)例滿足概念而使該概念泛化。該規(guī)則特別有用的方式是通過(guò)擴(kuò)展某個(gè)特定概念的取值范圍而增加選項(xiàng)。將合取轉(zhuǎn)為析取規(guī)則本文檔共51頁(yè)；當(dāng)前第5頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：泛化爬升概念樹規(guī)則：通過(guò)爬升概念樹，低層概念被較高層概念替代。設(shè)A表示信息系統(tǒng)中的某個(gè)屬性如Animal，a,b,…分別為對(duì)象u,v,…在屬性A上的取值，若s是概念樹上a,b,…的父結(jié)點(diǎn)，則基于概念樹爬升的泛化規(guī)則表示為：

Nick等人給出了一種面向?qū)傩缘臍w納算法。過(guò)度泛化問(wèn)題當(dāng)某個(gè)屬性被爬升至過(guò)高的概念層會(huì)導(dǎo)致沖突的產(chǎn)生，這種現(xiàn)象稱為過(guò)度泛化。克服過(guò)度泛化必須有相應(yīng)的終止泛化算法的策略。本文檔共51頁(yè)；當(dāng)前第6頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：泛化動(dòng)物哺乳類鳥類企鵝食肉類蹄類飛禽類走禽類虎印度豹長(zhǎng)頸鹿斑馬信天翁鷹駝鳥第1層第2層第3層第4層本文檔共51頁(yè)；當(dāng)前第7頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：決策樹決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。所謂決策樹是一個(gè)類似流程圖的樹結(jié)構(gòu)，其中樹的內(nèi)結(jié)點(diǎn)對(duì)應(yīng)屬性或?qū)傩约總€(gè)分枝表示檢驗(yàn)結(jié)果(屬性值)，樹枝上的葉結(jié)點(diǎn)代表所關(guān)心的因變量的取值(類標(biāo)簽)，最頂端的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。決策樹學(xué)習(xí)采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值比較并根據(jù)不同的屬性值判斷從該結(jié)點(diǎn)向下的分支，在葉結(jié)點(diǎn)得到結(jié)論。從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)都有唯一的一條路徑，這條路徑就是一條決策“規(guī)則”。當(dāng)經(jīng)過(guò)一批訓(xùn)練實(shí)例集的訓(xùn)練產(chǎn)生一顆決策樹，那么該決策樹就可以根據(jù)屬性的取值對(duì)一個(gè)未知實(shí)例集進(jìn)行分類。所有的決策樹都有一等價(jià)的ANN表示；也可用SVM實(shí)現(xiàn)相同的功能。本文檔共51頁(yè)；當(dāng)前第8頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：決策樹A0A1A2A3類0000-10001-10010-10011-101001010110110101111A0A1A2A3類1000-11001-11010-11011-111001110111110-11111-1A0A1A1A2-11-11-110010110本文檔共51頁(yè)；當(dāng)前第9頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：決策樹概念學(xué)習(xí)系統(tǒng)CLS(Hunt)：從一顆空的決策樹出發(fā)，添加新的判定結(jié)點(diǎn)來(lái)改善原來(lái)的決策樹，直到該決策樹能夠正確地將訓(xùn)練實(shí)例分類為止。產(chǎn)生根節(jié)點(diǎn)T，T包含所有的訓(xùn)練樣本；如果T中的所有樣本都是正例，則產(chǎn)生一個(gè)標(biāo)有“1”的節(jié)點(diǎn)作為T的子節(jié)點(diǎn)，并結(jié)束；如果T中的所有樣本都是反例，則產(chǎn)生一個(gè)標(biāo)有“-1”的節(jié)點(diǎn)作為T的子節(jié)點(diǎn)，并結(jié)束；選擇一個(gè)屬性A(如何選?)，根據(jù)該屬性的不同取值v1,v2,…,vn將T中的訓(xùn)練集劃分為n個(gè)子集，并根據(jù)這n個(gè)子集建立T的n個(gè)子節(jié)點(diǎn)T1,T2,…,Tn，并分別以A=vi作為從T到Ti的分支符號(hào)；以每個(gè)子節(jié)點(diǎn)Ti為根建立新的子樹。本文檔共51頁(yè)；當(dāng)前第10頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：決策樹A0A1A1A2-11-11-110010110T2T1T11T12T111T112T21T22T本文檔共51頁(yè)；當(dāng)前第11頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：決策樹ID3算法(Quinlan)：ID3算法對(duì)CLS做了兩方面的改進(jìn)：(1)增加窗口技術(shù)；(2)以信息熵的下降速度(信息增益)作為測(cè)試屬性選擇標(biāo)準(zhǔn)。窗口技術(shù)：對(duì)于訓(xùn)練集很大的情形可選擇其某個(gè)子集(稱為窗口)構(gòu)造一棵決策樹，如果該決策樹對(duì)訓(xùn)練集中的其它樣本的判決效果很差，則擴(kuò)大窗口，選擇不能被正確判別的樣本加入到窗口中，再建立一個(gè)新的決策樹，重復(fù)這個(gè)過(guò)程得到最終的決策樹，顯然不同的初始窗口會(huì)產(chǎn)生不同的決策樹。本文檔共51頁(yè)；當(dāng)前第12頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：決策樹信息增益

：設(shè)決策樹根結(jié)點(diǎn)的樣本數(shù)據(jù)為X={x1,x2,…,xn}，稱X的兩個(gè)訓(xùn)練子集PX(對(duì)應(yīng)類標(biāo)簽為1)和NX(對(duì)應(yīng)類標(biāo)簽為-1)為正例集和反例集，并記正例集和反例集的樣本數(shù)分別為P和N，則樣本空間的信息熵為假設(shè)以隨機(jī)變量A作為決策樹根的測(cè)試屬性，A具有k個(gè)不同的離散值v1,v2,…,vk，它將X劃分為k個(gè)子集，且假設(shè)第j個(gè)子集中包含Pj個(gè)正例，Nj個(gè)反例，則第j個(gè)子集的信息熵為I(Pj,Nj)。本文檔共51頁(yè)；當(dāng)前第13頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：決策樹以A為測(cè)試屬性的期望信息熵為以A為根節(jié)點(diǎn)的信息增益是：Gain(A)=I(P,N)-E(A)ID3的策略就是選擇信息增益最大的屬性作為測(cè)試屬性。ID3的問(wèn)題：測(cè)試屬性的分支越多，信息增益值越大，但輸出分支多并不表示該測(cè)試屬性有更好的預(yù)測(cè)效果。本文檔共51頁(yè)；當(dāng)前第14頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：決策樹A0A1A2A3類0000-10001-10010-10011-101001010110110101111A0A1A2A3類1000-11001-11010-11011-111001110111110-11111-1類似地，求出E(A1)，E(A2)，E(A3)。比較它們的大小，選擇期望信息熵最小的屬性作為根結(jié)點(diǎn)。依次構(gòu)造子決策樹，直至所有的訓(xùn)練樣本均能夠被正確分類。本文檔共51頁(yè)；當(dāng)前第15頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—?dú)w納學(xué)習(xí)：決策樹信息增益率：其中：目前一種比較流行的決策樹算法C4.5算法就是以信息增益率作為測(cè)試屬性的選擇條件。生成的決策樹往往過(guò)大，不利于決策時(shí)的應(yīng)用，需要對(duì)其剪枝(Pruning)，請(qǐng)參閱相關(guān)文獻(xiàn)。本文檔共51頁(yè)；當(dāng)前第16頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)

神經(jīng)網(wǎng)絡(luò)(ArtificialNeuralNetworks)是由具有適應(yīng)性的簡(jiǎn)單單元組成的廣泛并行互連的網(wǎng)絡(luò)，它的組織能夠模擬生物神經(jīng)系統(tǒng)對(duì)真實(shí)世界物體所作出的交互反應(yīng)(T.Koholen)。神經(jīng)網(wǎng)絡(luò)分為前向型、反饋型、隨機(jī)型以及自組織型。我們重點(diǎn)介紹一下前向型網(wǎng)絡(luò)及其學(xué)習(xí)算法。本文檔共51頁(yè)；當(dāng)前第17頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分基本神經(jīng)元及感知機(jī)模型：機(jī)器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)wj1wjiwjnyjf(iwijxi-j)x1xixn本文檔共51頁(yè)；當(dāng)前第18頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)神經(jīng)元函數(shù)f的選擇線性函數(shù)：f(x)=x帶限的線性函數(shù)：為最大輸出。閾值型函數(shù)：sigmoid函數(shù)：本文檔共51頁(yè)；當(dāng)前第19頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)

感知機(jī)學(xué)習(xí)算法：(選取f為閾值函數(shù)，學(xué)習(xí)權(quán)值向量w)(1)初始化：將權(quán)值向量和閾值賦予隨機(jī)量，t=0(2)連接權(quán)的修正：設(shè)訓(xùn)練樣本的輸入為x1,...,xi,...,xn，期望輸出為yj，進(jìn)行如下計(jì)算：計(jì)算網(wǎng)絡(luò)輸出：y(t)=f(iwij(t)xi(t)-j(t))計(jì)算期望輸出與實(shí)際輸出的誤差：e(t)=yj-y(t)若e=0，則說(shuō)明當(dāng)前樣本輸出正確，不必更新權(quán)值，否則更新權(quán)值和閾值

wij(t+1)=wij(t)+yjxi(t)；j(t+1)=j(t)+yjt=t+1(為學(xué)習(xí)率)(3)返回(2)，重復(fù)所有的訓(xùn)練樣本直到所有的樣本輸出正確。本文檔共51頁(yè)；當(dāng)前第20頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)多層前向神經(jīng)網(wǎng)絡(luò)：包括一個(gè)輸入層、一個(gè)輸出層以及多層隱單元。x1xixIy1ykyK輸入層隱含層輸出層u1uiuIv1vjvJwjiwkj本文檔共51頁(yè)；當(dāng)前第21頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)隱含層的接受與投射(以隱含層第j個(gè)神經(jīng)元為例)：接受：第j個(gè)神經(jīng)元的值來(lái)自于前一層網(wǎng)絡(luò)(本例是輸入層)輸出值的加權(quán)和，即netj=iwjiui。投射：將第j個(gè)神經(jīng)元的值經(jīng)過(guò)變換f(netj)，作為下一層網(wǎng)絡(luò)(本例是輸出層)的輸入，一般f(x)=1/(1+e-x)。因此可得到y(tǒng)k=jwkjf(netj)。上述過(guò)程一直持續(xù)到所有的輸出單元得到輸出為止，最后一層的輸出就是網(wǎng)絡(luò)的輸出。因此，神經(jīng)網(wǎng)絡(luò)是一個(gè)黑匣子。本文檔共51頁(yè)；當(dāng)前第22頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)BP算法：BP算法的核心是確定W的調(diào)節(jié)規(guī)則(學(xué)習(xí)規(guī)則)，使實(shí)際的輸出Y1(t)盡可能接近期望的輸出Y(t)。誤差函數(shù)：對(duì)于每種輸入模式特征矢量(x1,x2,…,xI),都有對(duì)應(yīng)的輸出矢量(y1,y2,…,yK)作為訓(xùn)練網(wǎng)絡(luò)的輸出參考基準(zhǔn)。如果用符號(hào)Xp表示第p個(gè)輸入模式特征矢量，用符號(hào)Yp表示對(duì)應(yīng)的第p個(gè)輸出基準(zhǔn)矢量。在訓(xùn)練時(shí)，同時(shí)按輸入輸出矢量對(duì)(Xp,Yp)給出訓(xùn)練集(p=1,…,P)。對(duì)于每個(gè)Xp，按照神經(jīng)元的輸入輸出公式，一個(gè)個(gè)一層層地求出網(wǎng)絡(luò)的實(shí)際輸出Y1p，則誤差函數(shù)定義為：本文檔共51頁(yè)；當(dāng)前第23頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)權(quán)重調(diào)節(jié)策略：學(xué)習(xí)的目標(biāo)是使E最小或不大于規(guī)定的誤差。從理論上可用求極值的方法獲得權(quán)值調(diào)整的一種典型規(guī)則：其他最流行的網(wǎng)絡(luò)結(jié)構(gòu)：徑向基函數(shù)(RBF)神經(jīng)網(wǎng)絡(luò)、自組織映射(SOM)、Hopfield網(wǎng)絡(luò)等。Matlab提供了一套神經(jīng)網(wǎng)絡(luò)工具箱(NeuralNetworksToolbox)，其中包含了一組new函數(shù)，用以創(chuàng)建各種類型的神經(jīng)網(wǎng)絡(luò)。本文檔共51頁(yè)；當(dāng)前第24頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)newcf——cascade-forwardbackpropagationnetwork.newelm——Elmanbackpropagationnetwork.newff——feed-forwardbackpropagationnetwork.newfftd——feed-forwardinput-delaybackpropnetwork.newgrnn——generalizedregressionneuralnetwork.newhop——Hopfieldrecurrentnetwork.newlvq——learningvectorquantizationnetworknewpnn——probabilisticneuralnetwork.newrb——radialbasisnetwork.newrbe——exactradialbasisnetwork.newsom——self-organizingmap本文檔共51頁(yè)；當(dāng)前第25頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)MatLab工具箱之多層前向BP網(wǎng)絡(luò)示例P=[012345678910];&&輸入T=[01234321234];&&期望輸出net=newcf([010],[51],{‘tansig’‘purelin’});創(chuàng)建一個(gè)BP網(wǎng)絡(luò)，最小輸入為0，最大輸入為10，兩隱含層，第一層神經(jīng)元（5個(gè)神經(jīng)元）函數(shù)為tansig函數(shù)，第二層神經(jīng)元（1個(gè)神經(jīng)元）函數(shù)為purelin函數(shù)。Y=sim(net,P);&&實(shí)際輸出(未學(xué)習(xí))plot(P,T,P,Y,'o')net.trainParam.epochs=50;&&迭代次數(shù)net=train(net,P,T);&&網(wǎng)絡(luò)訓(xùn)練Y=sim(net,P);&&實(shí)際輸出(已學(xué)習(xí))plot(P,T,P,Y,'o')本文檔共51頁(yè)；當(dāng)前第26頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)本文檔共51頁(yè)；當(dāng)前第27頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—支持向量機(jī)提出的背景(針對(duì)神經(jīng)網(wǎng)絡(luò)的不足)1.大量的控制參數(shù)。神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)、傳輸函數(shù)、損失函數(shù)、學(xué)習(xí)參數(shù)、訓(xùn)練算法以及訓(xùn)練代數(shù)都需要基于反復(fù)試驗(yàn)的方法獲得。

2.存在過(guò)度擬合問(wèn)題。許多現(xiàn)實(shí)的數(shù)據(jù)包含大量的噪聲，如果神經(jīng)網(wǎng)絡(luò)規(guī)模太大，并且網(wǎng)絡(luò)訓(xùn)練時(shí)間控制不適當(dāng)，那么神經(jīng)網(wǎng)絡(luò)將不但獲得數(shù)據(jù)中的有用信息而且會(huì)得到不希望的噪聲。其結(jié)果它們只能記憶到訓(xùn)練數(shù)據(jù)點(diǎn)，而對(duì)訓(xùn)練數(shù)據(jù)以外的樣本點(diǎn)泛化能力很差。本文檔共51頁(yè)；當(dāng)前第28頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—支持向量機(jī)3.局部極小值問(wèn)題。神經(jīng)網(wǎng)絡(luò)訓(xùn)練過(guò)程中主要使用梯度下降的算法，容易陷入局部極小值。4.收斂速度慢。神經(jīng)網(wǎng)絡(luò)主要采用基于梯度的BP學(xué)習(xí)算法，當(dāng)用于大規(guī)模問(wèn)題時(shí)收斂慢。5.黑箱問(wèn)題。神經(jīng)網(wǎng)絡(luò)沒(méi)有明確的函數(shù)形式解釋輸入和輸出變量之間的相互關(guān)系，很難解釋從神經(jīng)網(wǎng)絡(luò)獲得的結(jié)論。20世紀(jì)90年代Vapnik提出了支持向量機(jī)(SupportVectorMachines,SVM)，它被看作是高維空間函數(shù)表達(dá)的一般方法。使用SVM方法，人們可以在很高維的空間里構(gòu)造好的分類規(guī)則。本文檔共51頁(yè)；當(dāng)前第29頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—支持向量機(jī)SVM提供了一種分類算法統(tǒng)一的理論框架，這是理論上的一個(gè)重要貢獻(xiàn)。感知器只能解決線性分類問(wèn)題；通過(guò)添加隱含層神經(jīng)網(wǎng)絡(luò)可以處理線性不可分問(wèn)題，因而產(chǎn)生了BP網(wǎng)絡(luò)。現(xiàn)已證明，當(dāng)隱含層可以任意設(shè)置時(shí)，三層BP網(wǎng)絡(luò)可以以任意精度逼近任一連續(xù)函數(shù)，但隱含層神經(jīng)元的理論意義不清楚。SVM方法的出現(xiàn)，從理論上解釋了隱含層的作用，即它是將輸入樣本集變換到高維空間，從而使樣本可分性得到改善，即神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法實(shí)際上是一種特殊的核技巧。另外，因?yàn)橹С窒蛄客ǔH為訓(xùn)練數(shù)據(jù)集的一小部分(解的稀疏性)，因而加快了訓(xùn)練過(guò)程的收斂速度。本文檔共51頁(yè)；當(dāng)前第30頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—支持向量機(jī)結(jié)構(gòu)化風(fēng)險(xiǎn)最小化與經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則考慮分類問(wèn)題。樣本集為U={x1,x2,...,xl}(m維空間中的l個(gè)向量)，每個(gè)向量對(duì)應(yīng)一個(gè)類別，類別空間Y={+1,-1}。記p(x,y)表示對(duì)象x為y類的概率分布。分類的任務(wù)就是尋找分類器f：U→Y且使期望風(fēng)險(xiǎn)最小。f的期望風(fēng)險(xiǎn)為：在有限樣本的情況下，p(x,y)是未知的，因此期望風(fēng)險(xiǎn)無(wú)法計(jì)算。常使用經(jīng)驗(yàn)風(fēng)險(xiǎn)代替，且當(dāng)l→∞時(shí)兩者相等。本文檔共51頁(yè)；當(dāng)前第31頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—支持向量機(jī)如果

成立，則稱經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則（EmpiricalRiskMinimization,ERM）具有一致性。結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則

Vapnik在1971年證明經(jīng)驗(yàn)風(fēng)險(xiǎn)最小值未必收斂于期望風(fēng)險(xiǎn)最小值，即ERM不成立。因此提出了結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則(StructuralRiskMinimization,SRM)，為小樣本統(tǒng)計(jì)理論奠定了基礎(chǔ)。本文檔共51頁(yè)；當(dāng)前第32頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—支持向量機(jī)Vapnik和Chervonenkis通過(guò)研究，得出了期望風(fēng)險(xiǎn)和經(jīng)驗(yàn)風(fēng)險(xiǎn)的如下關(guān)系以概率1-成立，即

l為樣本點(diǎn)數(shù)目；參數(shù)01；h為函數(shù)f的維數(shù)，簡(jiǎn)稱VC維。(在無(wú)法求得期望風(fēng)險(xiǎn)的情形下找到了它的一個(gè)上界)不等式右邊與樣本的具體分布無(wú)關(guān)，即Vapnik的統(tǒng)計(jì)學(xué)習(xí)理論無(wú)需假設(shè)樣本分布，克服了高維分布對(duì)樣本點(diǎn)需求隨維數(shù)而指數(shù)增長(zhǎng)的問(wèn)題。這是小樣本統(tǒng)計(jì)理論與經(jīng)典統(tǒng)計(jì)理論的本質(zhì)區(qū)別，也是將Vapnik統(tǒng)計(jì)方法稱之為小樣本統(tǒng)計(jì)理論的原因。VC維置信度本文檔共51頁(yè)；當(dāng)前第33頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—支持向量機(jī)討論：(1)如果l/h較大，則期望風(fēng)險(xiǎn)(實(shí)際風(fēng)險(xiǎn))主要由經(jīng)驗(yàn)風(fēng)險(xiǎn)來(lái)決定，因此對(duì)于大樣本集經(jīng)驗(yàn)風(fēng)險(xiǎn)經(jīng)常能給出較好結(jié)果。(2)如果比值l/h較小(小樣本集)，則小的經(jīng)驗(yàn)風(fēng)險(xiǎn)并不能保證有小的期望風(fēng)險(xiǎn)值，必須同時(shí)考慮經(jīng)驗(yàn)風(fēng)險(xiǎn)和置信范圍(稱之為VC維置信度)。VC維在其中起重要作用，實(shí)際上置信范圍是h的增函數(shù)。在樣本點(diǎn)數(shù)目l一定時(shí)，分類器越復(fù)雜，即VC維越大，則置信范圍越大，導(dǎo)致實(shí)際風(fēng)險(xiǎn)與經(jīng)驗(yàn)風(fēng)險(xiǎn)的差別越大。結(jié)論：要想使實(shí)際風(fēng)險(xiǎn)最小不僅要使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，還同時(shí)需要使分類器函數(shù)f的VC維h盡可能最小，這就是結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則。因此尋找最小屬性集變得非常有意義。本文檔共51頁(yè)；當(dāng)前第34頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—支持向量機(jī)支持向量分類模型基本分類思想：支持向量機(jī)的核心思想是將結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則引入到分類問(wèn)題中。從線性可分情況下的最優(yōu)分類超平面發(fā)展而來(lái)的，其本質(zhì)是在訓(xùn)練樣本中找出具有最優(yōu)分類超平面的支持向量。在數(shù)學(xué)上歸結(jié)為一個(gè)求解不等式約束條件的二次規(guī)劃問(wèn)題。本文檔共51頁(yè)；當(dāng)前第35頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—支持向量機(jī)margin與支持向量：設(shè)樣本集為U={x1,x2,...,xl}(m維空間中的l個(gè)向量)，類別空間Y={+1,-1}。xi為輸入向量，對(duì)應(yīng)的類標(biāo)簽為yi(+1或-1)。若樣本集是線性可分的，則存在超平面H：wx+b=0使得

(1)當(dāng)wxi+b1時(shí)，yi=+1(2)當(dāng)wxi+b-1時(shí)，yi=-1

其中，w為權(quán)值向量，b為偏離值。統(tǒng)一(1),(2)得：yi(wxi+b)1

對(duì)于樣本集的任一向量(點(diǎn))xi，其到超平面H的距離為：本文檔共51頁(yè)；當(dāng)前第36頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—支持向量機(jī)那么，margin的大小可按下式計(jì)算：margin=d++d-d+=min{di|i{1,2,...,l},yi=+1};d-=min{di|i{1,2,...,l},yi=-1}若存在樣本點(diǎn)xi使得wxi+b=±1，則稱此向量xi為支持向量，此時(shí)，d+=d-=1/|w|2，margin=2/|w|2。分類模型：尋求最優(yōu)超平面H，使得margin最大。因此分類問(wèn)題轉(zhuǎn)為二次凸規(guī)劃問(wèn)題：本文檔共51頁(yè)；當(dāng)前第37頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—支持向量機(jī)線性不可分：可引入核函數(shù)將線性不可分問(wèn)題轉(zhuǎn)換為高維空間的線性可分問(wèn)題，常見核函數(shù)有：

d次多項(xiàng)式函數(shù)

高斯徑向基函數(shù)

神經(jīng)網(wǎng)絡(luò)核函數(shù)本文檔共51頁(yè)；當(dāng)前第38頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—遺傳算法遺傳算法(GeneticAlgorithm,GA)是一種借鑒生物界自然選擇和自然遺傳機(jī)制的高度并行、隨機(jī)、自適應(yīng)搜索算法，它利用結(jié)構(gòu)化的隨機(jī)交換技術(shù)組合群體中各個(gè)結(jié)構(gòu)中最好的生存因素，形成最佳代碼串并使之一代一代地進(jìn)化，最終獲得滿意的優(yōu)化結(jié)果。其基本構(gòu)成要素有染色體編碼、適應(yīng)度函數(shù)、遺傳算子(遺傳、交叉、變異)以及相關(guān)的運(yùn)行參數(shù)(種群規(guī)模：20-100；進(jìn)化代數(shù)：100-500；交叉概率Pc：；變異概率Pm：0.0001-0.1)本文檔共51頁(yè)；當(dāng)前第39頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(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)。本文檔共51頁(yè)；當(dāng)前第40頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—遺傳算法遺傳算法示例：基于GA的連續(xù)屬性集離散化問(wèn)題求解問(wèn)題描述：基于GA的離散化思想：將連續(xù)屬性離散化的分割點(diǎn)選擇問(wèn)題轉(zhuǎn)化為分割點(diǎn)組合的尋優(yōu)問(wèn)題。首先對(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)。3kiki-121……本文檔共51頁(yè)；當(dāng)前第41頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—遺傳算法遺傳編碼：用編碼形式表示決策變量的初始解。把所有分割點(diǎn)表示成確定長(zhǎng)度的二進(jìn)制串，每個(gè)分割點(diǎn)與串中的一部分相聯(lián)系。具體地，設(shè)連續(xù)屬性集C’={c1,c2,...,cm}，對(duì)于任意ciC’選擇長(zhǎng)度為l(i)的二進(jìn)制編碼表示分割點(diǎn)cij(j=1,2,...,ki-1)，則表示屬性ci的所有分割點(diǎn)的串長(zhǎng)為l(i)(ki-1)，分割點(diǎn)cij與長(zhǎng)度為l(i)的二進(jìn)制編碼之間的值對(duì)應(yīng)關(guān)系可由下式確定：式中m(s)是長(zhǎng)度為l(i)的二進(jìn)制編碼中第s位的編碼值。si為連續(xù)屬性ci的起點(diǎn)值，ei為其終點(diǎn)值本文檔共51頁(yè)；當(dāng)前第42頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—遺傳算法對(duì)C’中的所有屬性進(jìn)行編碼形成的二進(jìn)制串長(zhǎng)度為：因此，連續(xù)屬性集離散化問(wèn)題的搜索空間規(guī)模為2l。l(i)的選擇與樣本的規(guī)模有關(guān)。例如，若樣本規(guī)模為200，連續(xù)屬性集C’={c1,c2,c3}，k1=k2=4，k3=3。選擇l(1)=l(2)=l(3)=5，則l=5×3+5×3+5×2=40，問(wèn)題的搜索空間規(guī)模為240≈1012

001101001011011

011001010111101

0011110011表示了分割點(diǎn)集的一條染色體。本文檔共51頁(yè)；當(dāng)前第43頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—遺傳算法適應(yīng)度函數(shù)：體現(xiàn)決策目標(biāo)的優(yōu)化方向。從粗糙集理論的角度，離散化往往會(huì)破壞信息系統(tǒng)中原來(lái)的不可分辨關(guān)系，即原來(lái)兩個(gè)可分辨的對(duì)象可能變?yōu)椴豢煞直妫@樣等價(jià)類包含的對(duì)象數(shù)量增加，而等價(jià)類數(shù)量減少，分類能力可能減弱。因此使離散化后系統(tǒng)的分類能力最大是我們的優(yōu)化目標(biāo)，因此可用決策屬性d對(duì)C’的依賴度作為適應(yīng)度函數(shù)：本文檔共51頁(yè)；當(dāng)前第44頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—遺傳算法復(fù)制算子。把當(dāng)前群體中的個(gè)體按與適應(yīng)值成比例的概率復(fù)制到新的群體中，復(fù)制過(guò)程應(yīng)用賭盤技術(shù)選擇要被復(fù)制的串。復(fù)制算子的作用效果將提高群體的平均適應(yīng)值。設(shè)種群數(shù)為N，則將賭盤分成N份，第i份的比例按如下值確定：本文檔共51頁(yè)；當(dāng)前第45頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—遺傳算法s40.31s20.49s10.14s30.06本文檔共51頁(yè)；當(dāng)前第46頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—遺傳算法交叉算子：按一定的概率從交配池中任選2條染色體進(jìn)行多點(diǎn)雜交(隨機(jī)互換兩個(gè)染色體某些位上的基因)。方法如下：挑選2個(gè)染色體串，按概率確定它們是否發(fā)生雜交，若未發(fā)生雜交，另取2個(gè)染色體串，否則，先產(chǎn)生m個(gè)隨機(jī)數(shù)r(i)(ciC’)，隨機(jī)數(shù)的范圍為1到l(i)(ki-1)-1，然后配對(duì)的2個(gè)串相互對(duì)應(yīng)地交換從到的位段。本文檔共51頁(yè)；當(dāng)前第47頁(yè)；編輯于星期日\(chéng)16點(diǎn)14分機(jī)器學(xué)習(xí)—遺傳算法例：設(shè)染色體

s1=001101001011011

011001010111101

0011110011

s2=101101010001011

011010010110101

1000