【正文】 過程是搜索特征子集的過程，負(fù)責(zé)為評價(jià)函數(shù)提供特征子集。 (2) 評價(jià)函數(shù)( Evaluation Function )評價(jià)函數(shù)是評價(jià)一個(gè)特征子集好壞程度的一個(gè)準(zhǔn)則。(4) 驗(yàn)證過程( Validation Procedure )在驗(yàn)證數(shù)據(jù)集上驗(yàn)證選出來的特征子集的有效性。在概率論和信息論中，信息增益是非對稱的，用以度量兩種概率分布P和Q的差異。通常P代表樣本或觀察值的分布，也有可能是精確計(jì)算的理論分布。盡管信息增益通常被直觀地作為是一種度量或距離，但事實(shí)上信息增益并不是。信息增益是f增益（fdivergences）的一種特殊情況。它與微積分中的增益不同，但可以從Bregman增益（Bregman divergence）推導(dǎo)得到。因此先回憶一下信息論中有關(guān)信息量（就是“熵”）的定義。對分類系統(tǒng)來說，類別C是變量，它可能的取值是，而每一個(gè)類別出現(xiàn)的概率是，因此n就是類別的總數(shù)。系統(tǒng)含有特征t的時(shí)候信息量很好計(jì)算，就是剛才的式子，它表示的是包含所有特征時(shí)系統(tǒng)的信息量。對應(yīng)到我們的系統(tǒng)中，就是下面的等價(jià)：（1）系統(tǒng)不包含特征t；（2）系統(tǒng)雖然包含特征t，但是t已經(jīng)固定了，不能變化。這個(gè)信息量其實(shí)也有專門的名稱，就叫做“條件熵”，條件嘛，自然就是指“t已經(jīng)固定“這個(gè)條件。而取均值也不是簡單的加一加然后除以n，而是要用每個(gè)值出現(xiàn)的概率來算平均（簡單理解，就是一個(gè)值出現(xiàn)的可能性比較大，固定在它上面時(shí)算出來的信息量占的比重就要多一些）。從剛才計(jì)算均值的討論可以看出來，第二個(gè)式子與第一個(gè)式子的關(guān)系就是： 熵在信息論中，要對符號進(jìn)行編碼，一個(gè)符號的熵就是要表示這個(gè)符號所需要的最少二進(jìn)制數(shù)位數(shù)；這是一個(gè)極限；這也是信息壓縮的基礎(chǔ)；條件熵，當(dāng)兩個(gè)符號之間存在某種關(guān)系，或者兩個(gè)隨機(jī)變量不互相獨(dú)立的時(shí)候，對于A，B兩個(gè)隨機(jī)事件，非獨(dú)立，知道A的情況，B的不確定性減少。 unsigned int i,j。//哨兵值 for(j = 1。 j++){ if(done_flag) break。i()。amp。 } else count[1]++。 } } if(count[0] == 0 || count[1] == 0 ) return 0。 doubleentropy=count[0]/sum*log(count[0]/sum)/log() count[1]/sum*log(count[1]/sum)/log()。 }舉個(gè)例子：A事件是：季節(jié){春，夏，秋，冬}，B事件是：天氣{下雨，下雪，晴天，多云}；那就可以畫出一個(gè)二維表格，最直觀的是 夏天amp。下雪的概率；當(dāng)我知道天氣是下雪的時(shí)候，我就有很大的概率認(rèn)為季節(jié)是冬天；這說明：我知道了B事件的情況，對A的不確定性減少了；如果A，B是獨(dú)立的，比如，A事件是季節(jié){春，夏，秋，冬}，B事件是交通的情況{堵，不堵}，我知道B的情況，對A的不確定性并沒影響。信息論中有熵，用來表示時(shí)間的不確定性，這個(gè)跟這個(gè)事件的可能值數(shù)目，還有取每個(gè)值的概率，比如有A事件{1,2,3,4}每個(gè)取值等概，那么熵為2；如果A{1,2}每個(gè)取值等概率，熵為1；當(dāng)取值數(shù)目一樣的時(shí)候A{1,2,3,4}，那么這個(gè)熵小于2；這是為什么？因?yàn)樵跀?shù)據(jù)壓縮方面，對于小概率事件就要用長的編碼，大概率事件用短編碼，這樣最后平均每個(gè)事件的編碼就比較??！而對于等概率事件，這種策略就沒法使用，就沒法實(shí)現(xiàn)數(shù)據(jù)的壓縮；熵說的就是這種下界。 決策樹的生成 ID3算法如果學(xué)習(xí)的任務(wù)是對一個(gè)大的例子集作分類概念的歸納定義，而這些例子又都是用一些無結(jié)構(gòu)的屬性值對來表示，則可以采用示例學(xué)習(xí)方法的一個(gè)變種──決策樹學(xué)習(xí)，其代表性的算法是昆蘭（，1986）提出的ID3。該算法是以信息論為基礎(chǔ)，以信息熵和信息增益度為衡量標(biāo)準(zhǔn)，從而實(shí)現(xiàn)對數(shù)據(jù)的歸納分類。：若一個(gè)記錄集合T根據(jù)類別屬性的值被分成互相獨(dú)立的類C1C2..Ck，則識別T的一個(gè)元素所屬哪個(gè)類所需要的信息量為Info(T)=I(p)，其中P為C1C2…Ck的概率分布，即。對被選取的測試屬性創(chuàng)建一個(gè)節(jié)點(diǎn)，并以該節(jié)點(diǎn)的屬性標(biāo)記，對該屬性的每個(gè)值創(chuàng)建一個(gè)分支據(jù)此劃分樣本。例子由預(yù)先定義的屬性值對來表示?！　渲械拿恳环侨~節(jié)點(diǎn)對應(yīng)一個(gè)需測試的屬性，每個(gè)分叉就是該屬性可能的取值；樹的葉節(jié)點(diǎn)則指示一個(gè)例子事物的類別。當(dāng)然，ID3只能處理用屬性值對表示的例子。構(gòu)造決策樹的目的是為了對事物作出正確的分類。如Ｃ是空的，那么它無需分類，對應(yīng)的決策樹也為空；如Ｃ中的對象是同一類的，那么決策樹就一個(gè)葉節(jié)點(diǎn)，即該類名；如果Ｃ集中的對象屬于二個(gè)不同的類別，那未我們可以選取一個(gè)對象的屬性，隨后按其可能值把Ｃ劃分成一些不相交的子集C1，C2，…，Cn，其中Ci是含有所選屬性的第ｉ個(gè)值的那些對象集。ID3（Examples,Targetattrlbute,Attrlbutes）創(chuàng)建樹的root節(jié)點(diǎn)如果Examples都為正，返回label=+的單節(jié)點(diǎn)輸root如果Examples都為反，返回label=的單節(jié)點(diǎn)輸root如果Attrlbutes為空，那么返回單節(jié)點(diǎn)輸root，label=Examples中最普遍的Targetattributes值否則開始A Attributes中分類examples能力最好的屬性Root的決策屬性A對于A的每個(gè)可能值vi 在root下加一個(gè)新的分支對應(yīng)測試A=vi 令Examples為Examples中滿足A屬性值為vi的子集 如果Examples為空 在這個(gè)新分支下加一個(gè)葉子結(jié)點(diǎn)，節(jié)點(diǎn)的label=Examples中最普遍的Targetattributes值 否則在新分支下加一個(gè)子樹ID3 （Examples Targetattribute，Attributes{A}）結(jié)束返回root　　下面給出一個(gè)關(guān)于人分類的例子（對象）集，并預(yù)先定義了指定的一組屬性及其可取值：高度{高，矮}，發(fā)色{黑色, 紅色，金色}和眼睛{蘭色，棕色}?！? 高度　　 發(fā)色　 眼睛　 　　　　類別　　　　　　　矮　　　　　黑色　　　蘭色　　　　　?。　　　　　　「摺　　　　『谏　　√m色　　　　　　－　　　　　　　矮　　　　　金色　　　蘭色　　　　　?。　　　　　　「摺　　　　〗鹕　　∽厣　　　　　。　　　　　　「摺　　　　『谏　　∽厣　　　　　。　　　　　　“　　?