智能決策理論與方法

智能決策理論與方法智能決策理論與方法1、智能決策理論的形成背景2、知識發(fā)現(xiàn)3、粗糙集理論4、機器學(xué)習(xí)機器學(xué)習(xí)機器學(xué)習(xí)是從模擬人類的學(xué)習(xí)行為出發(fā)，研究客觀世界和獲取各種知識與技能的一些基本方法（如歸納、泛化、特化、類比等），并借助于計算機科學(xué)與技術(shù)原理建立各種學(xué)習(xí)模型，從根本上提高計算機智能和學(xué)習(xí)能力。研究內(nèi)容是根據(jù)生理學(xué)、認知科學(xué)對人類學(xué)習(xí)機理的了解，建立人類學(xué)習(xí)的計算模型或認知模型；發(fā)展各種學(xué)習(xí)理論和學(xué)習(xí)方法，研究通用的學(xué)習(xí)算法并進行理論上的分析；建立面向任務(wù)且具有特定應(yīng)用的學(xué)習(xí)系統(tǒng)。機器學(xué)習(xí)—歸納學(xué)習(xí)：泛化歸納學(xué)習(xí)是指從給定的關(guān)于某個概念的一系列已知的正例和反例中歸納出一個通用的概念描述。泛化(Generalization)是用來擴展一假設(shè)的語義信息，使其能夠包含更多的正例。泛化所得到的結(jié)論并不總是正確的。常用泛化方法：將常量轉(zhuǎn)為變量規(guī)則：對于概念F(v)，如果v的某些取值a,b,…使F(v)成立，則這些概念可被泛化為：對于v的所有值，F(xiàn)(v)均成立：機器學(xué)習(xí)—歸納學(xué)習(xí)：泛化消除條件規(guī)則：一個合取條件可看作是對滿足此概念的可能實例集的一個約束。消除一個條件，則該概念被泛化。添加選項：通過添加更多條件，使得有更多的實例滿足概念而使該概念泛化。該規(guī)則特別有用的方式是通過擴展某個特定概念的取值范圍而增加選項。將合取轉(zhuǎn)為析取規(guī)則機器學(xué)習(xí)—歸納學(xué)習(xí)：泛化爬升概念樹規(guī)則：通過爬升概念樹，低層概念被較高層概念替代。設(shè)A表示信息系統(tǒng)中的某個屬性如Animal，a,b,…分別為對象u,v,…在屬性A上的取值，若s是概念樹上a,b,…的父結(jié)點，則基于概念樹爬升的泛化規(guī)則表示為：Nick等人給出了一種面向?qū)傩缘臍w納算法。過度泛化問題當某個屬性被爬升至過高的概念層會導(dǎo)致沖突的產(chǎn)生，這種現(xiàn)象稱為過度泛化。克服過度泛化必須有相應(yīng)的終止泛化算法的策略。機器學(xué)習(xí)—歸納學(xué)習(xí)：泛化動物哺乳類鳥類企鵝食肉類蹄類飛禽類走禽類虎印度豹長頸鹿斑馬信天翁鷹駝鳥第1層第2層第3層第4層機器學(xué)習(xí)—歸納學(xué)習(xí)：決策樹決策樹學(xué)習(xí)是以實例為基礎(chǔ)的歸納學(xué)習(xí)算法。所謂決策樹是一個類似流程圖的樹結(jié)構(gòu)，其中樹的內(nèi)結(jié)點對應(yīng)屬性或?qū)傩约總€分枝表示檢驗結(jié)果(屬性值)，樹枝上的葉結(jié)點代表所關(guān)心的因變量的取值(類標簽)，最頂端的結(jié)點稱為根結(jié)點。決策樹學(xué)習(xí)采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點進行屬性值比較并根據(jù)不同的屬性值判斷從該結(jié)點向下的分支，在葉結(jié)點得到結(jié)論。從根結(jié)點到每個葉結(jié)點都有唯一的一條路徑，這條路徑就是一條決策“規(guī)則”。當經(jīng)過一批訓(xùn)練實例集的訓(xùn)練產(chǎn)生一顆決策樹，那么該決策樹就可以根據(jù)屬性的取值對一個未知實例集進行分類。所有的決策樹都有一等價的ANN表示；也可用SVM實現(xiàn)相同的功能。機器學(xué)習(xí)—歸納學(xué)習(xí)：決策樹A0A1A2A3類0000-10001-10010-10011-101001010110110101111A0A1A2A3類1000-11001-11010-11011-111001110111110-11111-1A0A1A1A2-11-11-110010110機器學(xué)習(xí)—歸納學(xué)習(xí)：決策樹概念學(xué)習(xí)系統(tǒng)CLS(Hunt)：從一顆空的決策樹出發(fā)，添加新的判定結(jié)點來改善原來的決策樹，直到該決策樹能夠正確地將訓(xùn)練實例分類為止。產(chǎn)生根節(jié)點T，T包含所有的訓(xùn)練樣本；如果T中的所有樣本都是正例，則產(chǎn)生一個標有“1”的節(jié)點作為T的子節(jié)點，并結(jié)束；如果T中的所有樣本都是反例，則產(chǎn)生一個標有“-1”的節(jié)點作為T的子節(jié)點，并結(jié)束；選擇一個屬性A(如何選?)，根據(jù)該屬性的不同取值v1,v2,…,vn將T中的訓(xùn)練集劃分為n個子集，并根據(jù)這n個子集建立T的n個子節(jié)點T1,T2,…,Tn，并分別以A=vi作為從T到Ti的分支符號；以每個子節(jié)點Ti為根建立新的子樹。機器學(xué)習(xí)—歸納學(xué)習(xí)：決策樹A0A1A1A2-11-11-110010110T2T1T11T12T111T112T21T22T機器學(xué)習(xí)—歸納學(xué)習(xí)：決策樹ID3算法(Quinlan)：ID3算法對CLS做了兩方面的改進：(1)增加窗口技術(shù)；(2)以信息熵的下降速度(信息增益)作為測試屬性選擇標準。窗口技術(shù)：對于訓(xùn)練集很大的情形可選擇其某個子集(稱為窗口)構(gòu)造一棵決策樹，如果該決策樹對訓(xùn)練集中的其它樣本的判決效果很差，則擴大窗口，選擇不能被正確判別的樣本加入到窗口中，再建立一個新的決策樹，重復(fù)這個過程得到最終的決策樹，顯然不同的初始窗口會產(chǎn)生不同的決策樹。機器學(xué)習(xí)—歸納學(xué)習(xí)：決策樹信息增益：設(shè)決策樹根結(jié)點的樣本數(shù)據(jù)為X={x1,x2,…,xn}，稱X的兩個訓(xùn)練子集PX(對應(yīng)類標簽為1)和NX(對應(yīng)類標簽為-1)為正例集和反例集，并記正例集和反例集的樣本數(shù)分別為P和N，則樣本空間的信息熵為假設(shè)以隨機變量A作為決策樹根的測試屬性，A具有k個不同的離散值v1,v2,…,vk，它將X劃分為k個子集，且假設(shè)第j個子集中包含Pj個正例，Nj個反例，則第j個子集的信息熵為I(Pj,Nj)。機器學(xué)習(xí)—歸納學(xué)習(xí)：決策樹以A為測試屬性的期望信息熵為以A為根節(jié)點的信息增益是：Gain(A)=I(P,N)-E(A)ID3的策略就是選擇信息增益最大的屬性作為測試屬性。ID3的問題：測試屬性的分支越多，信息增益值越大，但輸出分支多并不表示該測試屬性有更好的預(yù)測效果。機器學(xué)習(xí)—歸納學(xué)習(xí)：決策樹信息增益率：其中：目前一種比較流行的決策樹算法C4.5算法就是以信息增益率作為測試屬性的選擇條件。生成的決策樹往往過大，不利于決策時的應(yīng)用，需要對其剪枝(Pruning)，請參閱相關(guān)文獻。機器學(xué)習(xí)—歸納學(xué)習(xí)：決策樹示例計算確定根結(jié)點I(P，N)=-10/16log(10/16)-6/16log(6/16)=-5/8log5-3/8log3+3=0.9544E(A0)=1/2(-4/8log(4/8)-4/8log(4/8))+1/2(-6/8log(6/8)-2/8log(2/8))=3/2-3/8log3=0.9056E(A1)=1-3/8log3=0.4084E(A2)=1-3/16log3=0.9056E(A3)=3-5/8log5-3/8log3=0.9544因此選A1作為起始根結(jié)點。A3沒有改變?nèi)魏涡畔⒘?，無分類價值，可以刪除。機器學(xué)習(xí)—歸納學(xué)習(xí)：決策樹確定子樹根結(jié)點當A1=0時，所有對象類標簽均為-1，此分支結(jié)束。當A1=1時，I(P,N)=-6/8log6/8-2/8log2/8=2-3/4log3=0.8112E(A0)=E(A2)=1/2=0.5E(A3)=2-3/4log3=0.8112A0，A2具有相同的分類能力，任取一個均可。若取A0，則當A0=0時，所有對象類標簽均為+1，此分支結(jié)束。當A0=1時，A2=0，類標簽為+1；A2=1，類標簽為-1。機器學(xué)習(xí)—歸納學(xué)習(xí)：決策樹A1A010-1+1A2+101-101機器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)(ArtificialNeuralNetworks)是由具有適應(yīng)性的簡單單元組成的廣泛并行互連的網(wǎng)絡(luò)，它的組織能夠模擬生物神經(jīng)系統(tǒng)對真實世界物體所作出的交互反應(yīng)(T.Koholen)。神經(jīng)網(wǎng)絡(luò)分為前向型、反饋型、隨機型以及自組織型。我們重點介紹一下前向型網(wǎng)絡(luò)及其學(xué)習(xí)算法?；旧窠?jīng)元及感知機模型：機器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)wj1wjiwjnyjf(iwijxi-j)x1xixn機器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)神經(jīng)元函數(shù)f的選擇線性函數(shù)：f(x)=x帶限的線性函數(shù)：為最大輸出。閾值型函數(shù)：sigmoid函數(shù)：機器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)感知機學(xué)習(xí)算法：(選取f為閾值函數(shù)，學(xué)習(xí)權(quán)值向量w)(1)初始化：將權(quán)值向量和閾值賦予隨機量，t=0(2)連接權(quán)的修正：設(shè)訓(xùn)練樣本的輸入為x1,...,xi,...,xn，期望輸出為yj(=±1)，進行如下計算：計算網(wǎng)絡(luò)輸出(=±1)：y(t)=f(iwij(t)xi(t)-j(t))計算期望輸出與實際輸出的誤差：e(t)=yj-y(t)若e=0，則說明當前樣本輸出正確，不必更新權(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)練樣本直到所有的樣本輸出正確。機器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)多層前向神經(jīng)網(wǎng)絡(luò)：包括一個輸入層、一個輸出層以及多層隱單元。x1xixIy1ykyK輸入層隱含層輸出層u1uiuIv1vjvJwjiwkj機器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)隱含層的接受與投射(以隱含層第j個神經(jīng)元為例)：接受：第j個神經(jīng)元的值來自于前一層網(wǎng)絡(luò)(本例是輸入層)輸出值的加權(quán)和，即netj=iwjiui。投射：將第j個神經(jīng)元的值經(jīng)過變換f(netj)，作為下一層網(wǎng)絡(luò)(本例是輸出層)的輸入，一般f(x)=1/(1+e-x)。因此可得到y(tǒng)k=jwkjf(netj)。上述過程一直持續(xù)到所有的輸出單元得到輸出為止，最后一層的輸出就是網(wǎng)絡(luò)的輸出。因此，神經(jīng)網(wǎng)絡(luò)是一個黑匣子。機器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)BP算法：BP算法的核心是確定W的調(diào)節(jié)規(guī)則(學(xué)習(xí)規(guī)則)，使實際的輸出Y1(t)盡可能接近期望的輸出Y(t)。誤差函數(shù)：對于每種輸入模式特征矢量(x1,x2,…,xI),都有對應(yīng)的輸出矢量(y1,y2,…,yK)作為訓(xùn)練網(wǎng)絡(luò)的輸出參考基準。如果用符號Xp表示第p個輸入模式特征矢量，用符號Yp表示對應(yīng)的第p個輸出基準矢量。在訓(xùn)練時，同時按輸入輸出矢量對(Xp,Yp)給出訓(xùn)練集(p=1,…,P)。對于每個Xp，按照神經(jīng)元的輸入輸出公式，一個個一層層地求出網(wǎng)絡(luò)的實際輸出Y1p，則誤差函數(shù)定義為：機器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)權(quán)重調(diào)節(jié)策略：學(xué)習(xí)的目標是使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ò)。機器學(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機器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)MatLab工具箱之多層前向BP網(wǎng)絡(luò)示例P=[012345678910];&&輸入T=[01234321234];&&期望輸出net=newcf([010],[51],{‘tansig’‘purelin’});創(chuàng)建一個BP網(wǎng)絡(luò)，最小輸入為0，最大輸入為10，兩隱含層，第一層神經(jīng)元函數(shù)為tansig函數(shù)，第二層神經(jīng)元函數(shù)為purelin函數(shù)。Y=sim(net,P);&&實際輸出(未學(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);&&實際輸出(已學(xué)習(xí))plot(P,T,P,Y,'o')機器學(xué)習(xí)—神經(jīng)網(wǎng)絡(luò)機器學(xué)習(xí)—支持向量機提出的背景(相對神經(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ù)試驗的方法獲得。2.存在過度擬合問題。許多現(xiàn)實的數(shù)據(jù)包含大量的噪聲，如果神經(jīng)網(wǎng)絡(luò)規(guī)模太大，并且網(wǎng)絡(luò)訓(xùn)練時間控制不適當，那么神經(jīng)網(wǎng)絡(luò)既會獲得數(shù)據(jù)中的有用信息，也會得到不希望的噪聲。其結(jié)果只能用于訓(xùn)練數(shù)據(jù)點，而對訓(xùn)練數(shù)據(jù)以外的樣本點缺乏泛化能力。機器學(xué)習(xí)—支持向量機3.局部極小值問題。神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程中主要使用梯度下降的算法，容易陷入局部極小值。4.收斂速度慢。神經(jīng)網(wǎng)絡(luò)主要采用基于梯度的BP學(xué)習(xí)算法，當用于大規(guī)模問題時收斂慢。5.黑箱問題。神經(jīng)網(wǎng)絡(luò)沒有明確的函數(shù)形式解釋輸入和輸出變量之間的相互關(guān)系，很難解釋神經(jīng)網(wǎng)絡(luò)獲得的結(jié)論。20世紀90年代Vapnik提出了支持向量機(SupportVectorMachines,SVM)，它被看作是高維空間函數(shù)表達的一般方法。使用SVM方法，人們可以在很高維的空間里構(gòu)造好的分類規(guī)則。機器學(xué)習(xí)—支持向量機結(jié)構(gòu)化風(fēng)險最小化與經(jīng)驗風(fēng)險最小化原則經(jīng)驗風(fēng)險最小化原則考慮分類問題。樣本集為U={x1,x2,...,xl}(m維空間中的l個向量)，每個向量對應(yīng)一個類別，類別空間Y={+1,-1}。記p(x,y)表示對象x為y類的概率分布。分類的任務(wù)就是尋找分類器f：U→Y且使期望風(fēng)險最小。f的期望風(fēng)險為：在有限樣本的情況下，p(x,y)是未知的，因此期望風(fēng)險無法計算。常使用經(jīng)驗風(fēng)險代替，且當l→∞時兩者相等。機器學(xué)習(xí)—支持向量機如果

成立，則稱經(jīng)驗風(fēng)險最小化原則（EmpiricalRiskMinimization,ERM）具有一致性。結(jié)構(gòu)風(fēng)險最小化原則Vapnik在1971年證明經(jīng)驗風(fēng)險最小值未必收斂于期望風(fēng)險最小值，即ERM不成立。因此提出了結(jié)構(gòu)風(fēng)險最小化原則(StructuralRiskMinimization,SRM)，為小樣本統(tǒng)計理論奠定了基礎(chǔ)。機器學(xué)習(xí)—支持向量機Vapnik和Chervonenkis通過研究，得出了期望風(fēng)險和經(jīng)驗風(fēng)險的如下關(guān)系以概率1-成立，即

l為樣本點數(shù)目；參數(shù)01；h為函數(shù)f的維數(shù)，簡稱VC維。(在無法求得期望風(fēng)險的情形下找到了它的一個上界)不等式右邊與樣本的具體分布無關(guān)，即Vapnik的統(tǒng)計學(xué)習(xí)理論無需假設(shè)樣本分布，克服了高維分布對樣本點需求隨維數(shù)而指數(shù)增長的問題。這是小樣本統(tǒng)計理論與經(jīng)典統(tǒng)計理論的本質(zhì)區(qū)別，也是將Vapnik統(tǒng)計方法稱之為小樣本統(tǒng)計理論的原因。VC維置信度機器學(xué)習(xí)—支持向量機討論：(1)如果l/h較大，則期望風(fēng)險(實際風(fēng)險)主要由經(jīng)驗風(fēng)險來決定，因此對于大樣本集經(jīng)驗風(fēng)險經(jīng)常能給出較好結(jié)果。(2)如果比值l/h較小(小樣本集)，則小的經(jīng)驗風(fēng)險并不能保證有小的期望風(fēng)險值，必須同時考慮經(jīng)驗風(fēng)險和置信范圍(稱之為VC維置信度)。VC維在其中起重要作用，實際上置信范圍是h的增函數(shù)。在樣本點數(shù)目l一定時，分類器越復(fù)雜，即VC維越大，則置信范圍越大，導(dǎo)致實際風(fēng)險與經(jīng)驗風(fēng)險的差別越大。結(jié)論：要想使實際風(fēng)險最小不僅要使經(jīng)驗風(fēng)險最小，還同時需要使分類器函數(shù)f的VC維h盡可能最小，這就是結(jié)構(gòu)風(fēng)險最小化原則。因此尋找最小屬性集變得非常有意義。機器學(xué)習(xí)—支持向量機支持向量分類模型基本分類思想：支持向量機的核心思想是將結(jié)構(gòu)風(fēng)險最小化原則引入到分類問題中。從線性可分情況下的最優(yōu)分類超平面發(fā)展而來的，其本質(zhì)是在訓(xùn)練樣本中找出具有最優(yōu)分類超平面的支持向量。在數(shù)學(xué)上歸結(jié)為一個求解不等式約束條件的二次規(guī)劃問題。機器學(xué)習(xí)—支持向量機margin與支持向量：設(shè)樣本集為U={x1,x2,...,xl}(m維空間中的l個向量)，類別空間Y={+1,-1}。xi為輸入向量，對應(yīng)的類標簽為yi(+1或-1)。若樣本集是線性可分的，則存在超平面H：wx+b=0使得(1)當wxi+b1時，yi=+1(2)當wxi+b-1時，yi=-1其中，w為權(quán)值向量，b為偏離值。統(tǒng)一(1),(2)得：yi(wxi+b)1對于樣本集的任一向量(點)xi，其到超平面H的距離為：機器學(xué)習(xí)—支持向量機那么，margin的大小可按下式計算：margin=d++d-d+=min{di|i{1,2,...,l},yi=+1};d-=min{di|i{1,2,...,l},yi=-1}若存在樣本點xi使得wxi+b=±1，則稱此向量xi為支持向量，此時，d+=d-=1/|w|，margin=2/|w|。分類模型：尋求最優(yōu)超平面H，使得margin最大。因此分類問題轉(zhuǎn)為二次凸規(guī)劃問題：機器學(xué)習(xí)—支持向量機線性不可分：可引入核函數(shù)將線性不可分問題轉(zhuǎn)換為高維空間的線性可分問題，常見核函數(shù)有：d次多項式函數(shù)高斯徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)核函數(shù)機器學(xué)習(xí)—遺傳算法遺傳算法(GeneticAlgorithm,GA)是一種借鑒生物界自然選擇和自然遺傳機制的高度并行、隨機、自適應(yīng)搜索算法，它利用結(jié)構(gòu)化的隨機交換技術(shù)組合群體中各個結(jié)構(gòu)中最好的生存因素，形成最佳代碼串并使之一代一代地進化，最終獲得滿意的優(yōu)化結(jié)果。其基本構(gòu)成要素有染色體編碼、適應(yīng)度函數(shù)、遺傳算子(遺傳、交叉、變異)以及相關(guān)的運行參數(shù)(種群規(guī)模：20-100；進化代數(shù)：100-500；交叉概率Pc：0.4-0.99；變異概率Pm：0.0001-0.1)機器學(xué)習(xí)—遺傳算法遺傳算法基本步驟(1)確定遺傳算法的有關(guān)參數(shù)：群體規(guī)模N，最大代數(shù)M，交叉概率Pc，變異概率Pm，停機準則；初始化種群：隨機產(chǎn)生N條表示可能方案集的染色體；(2)是否滿足停機準則，若是，終止；(3)計算群體中每個個體的適應(yīng)值；(4)復(fù)制：根據(jù)適應(yīng)度函數(shù)進行選擇生成中間群體；(5)交叉：以概率Pc選擇兩個個體進行染色體交換形成新的個體，替代老個體插入群體中(6)變異：按概率Pm選擇某條染色體的某一位進行改變形成新的個體，替代老個體插入群體中；(7)轉(zhuǎn)到(2)。機器學(xué)習(xí)—遺傳算法遺傳算法示例：基于GA的連續(xù)屬性集離散化問題求解問題描述：基于GA的離散化思想：將連續(xù)屬性離散化的分割點選擇問題轉(zhuǎn)化為分割點組合的尋優(yōu)問題。首先對分割點空間進行遺傳編碼，以分割點編碼構(gòu)成染色體，用基于粗糙集理論的適應(yīng)度函數(shù)來啟發(fā)并指導(dǎo)進化，最終得到較優(yōu)的能充分體現(xiàn)離散化效果的分割點組合代碼串，從而找到離散化連續(xù)屬性集的全部分割點。3kiki-121……機器學(xué)習(xí)—遺傳算法遺傳編碼：用編碼形式表示決策變量的初始解。把所有分割點表示成確定長度的二進制串，每個分割點與串中的一部分相聯(lián)系。具體地，設(shè)連續(xù)屬性集C’={c1,c2,...,cm}，對于任意ciC’選擇長度為l(i)的二進制編碼表示分割點cij(j=1,2,...,ki-1)，則表示屬性ci的所有分割點的串長為l(i)(ki-1)，分割點cij與長度為l(i)的二進制編碼之間的值對應(yīng)關(guān)系可由下式確定：式中m(s)是長度為l(i)的二進制編碼中第s位的編碼值。si為連續(xù)屬性ci的起點值，ei為其終點值機器學(xué)習(xí)—遺傳算法對C’中的所有屬性進行編碼形成的二進制串長度為：因此，連續(xù)屬性集離散化問題的搜索空間規(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，問題的搜索空間規(guī)模為240≈10120011010010110110110010101111010011110011表示了分割點集的一條染色體。機器學(xué)習(xí)—遺傳算法適應(yīng)度函數(shù)：體現(xiàn)決策目標的優(yōu)化方向。從粗糙集理論的角度，離散化往往會破壞信息系統(tǒng)中原來的不可分辨關(guān)系，即原來兩個可分辨的對象可能變?yōu)椴豢煞直?，這樣等價類包含的對象數(shù)量增加，而等價類數(shù)量減少，分類能力可能減弱。因此使離散化后系統(tǒng)的分類能力最大是我們的優(yōu)化目標，因此可用決策屬性d對C’的依賴度作為適應(yīng)度函數(shù)：機器學(xué)習(xí)—遺傳算法復(fù)制算子。把當前群體中的個體按與適應(yīng)值成比例的概率復(fù)制到新的群體中，復(fù)制過程應(yīng)用賭盤技術(shù)選擇要被復(fù)制的串。復(fù)制算子的作用效果將提高群體的平均適應(yīng)值。設(shè)種群數(shù)為N，則將賭盤分成N份，第i份的比例按如下值確定：機器學(xué)習(xí)—遺傳算法s40.31s20.49s10.14s30.06機器學(xué)習(xí)—遺傳算法交叉算子：按一定的概率從交配池中任選2條染色體進行多點雜交(隨機互換兩個染色體某些位上的基因)。方法如下：挑選2個染色體串，按概率確定它們是否發(fā)生雜交，若未發(fā)生雜交，另取2個染色體串，否則，先產(chǎn)生m個隨機數(shù)r(i)(ciC’)，隨機數(shù)的范圍為1到l(i)(ki-1)-1，然后配對的2個串相互對應(yīng)地交換從到的位段。機器學(xué)習(xí)—遺傳算法例：設(shè)染色體s1=0011010010110110110010101111010011110011

s2=1011010100010110110100101101011000110101按箭頭所指進行交叉，得到兩條新的染色體。s1’=0011001011110110110001101111011010110011

s2’=101101010010010

1010100101101011000100111機器學(xué)習(xí)—遺傳算法變異算子：以一個很小的概率隨機改變某條染色體中的某些基因位