【正文】 ??? = 1 下面分別計(jì)算例子集中各個(gè)屬性的信息贏取值。因此 , 4 4 2 2( ) l o g 2 l o g 2 0 . 9 1 8 36 2 4 6 2 4sE n tr o p y E ? ? ? ???性 格 , 內(nèi) 向 所以根據(jù)“性格”屬性來(lái)進(jìn)行例子集分類(lèi)的信息贏取值為 : Gain(Es,性格 )=Entropy(Es)Entropy(Esv,格 )= 111 ( * 0 .9 1 8 3 + * 0 .9 1 8 3 ) = 0 .0 8 1 722 同理 ,對(duì)“ 父母教育程度 ”來(lái)說(shuō) :Gain(Es, 父母教育程度 )= 。這里簡(jiǎn)化計(jì)算過(guò)程 ,算出 :Gain(Es,性格 )= 和 Gain(Es,性別 ) =。 父 母 教 育 程 度良差中內(nèi) 向 ， 良 ， 女 生 ： 好外 向 ， 良 ， 男 生 ： 好內(nèi) 向 ， 良 ， 男 生 ： 好外 向 ， 良 ， 女 生 ： 好內(nèi) 向 ， 中 ， 女 生 ： 差內(nèi) 向 ， 中 ， 男 生 ： 差內(nèi) 向 ， 差 ， 女 生 ： 差內(nèi) 向 ， 差 ， 男 生 ： 差性 格內(nèi) 向外 向{ 外 向 ， 中 ， 女 生 ： 差 }性 格內(nèi) 向外 向{ 外 向 ， 差 ， 男 生 ： 差 }性 別女 生男 生{ 外 向 ， 中 ， 男 生 ： 好 }{ 外 向 ， 差 ， 女 生 ： 好 }性 別男 生女 生 最終得到的決策樹(shù) IF 父母教 育程度 =“良” THEN 學(xué)習(xí)成績(jī) =“好” IF 父母教育程度 =“中” AND 性格 =“內(nèi)向” THEN學(xué)習(xí)成績(jī) =“差” IF 父母教育程度 =“差” AND 性格 =“內(nèi)向” THEN學(xué)習(xí)成績(jī) =“差” IF 父母教育程度 =“中” AND 性格 =“外向” AND 性別 =“女生” THEN學(xué)習(xí)成績(jī) =“差” IF 父母教育程度 =“中” AND 性格 =“外向” AND 性別 =“男生” THEN學(xué)習(xí)成績(jī) =“好” IF 父母教育程度 =“差” AND 性格 =“外向” AND 性別 =“女生” THEN學(xué)習(xí)成績(jī) =“好” IF 父母教育程度 =“差” AND 性格 =“外向” AND 性別 =“男生” THEN學(xué)習(xí)成績(jī) =“差” 但是 不能保證 ID3算法對(duì)任何問(wèn)題總能做出最佳選擇 ,只能說(shuō)它在一般情況下能夠找出最優(yōu)決策樹(shù)。其最原始的程序只是用來(lái)區(qū)分象棋中的走步 ,所以區(qū)分的類(lèi)別只有兩種 T或 F ,其屬性值也是一些離散有限的值 ,而今 ID3算法已發(fā)展到允許多于兩個(gè)類(lèi)別 ,而其屬性值可以是整數(shù)或?qū)崝?shù)。 缺點(diǎn) :搜索中只維持一個(gè)解 ,不能像候選剪除算法那樣返回所有可能的與練例集一致的假設(shè) ,并優(yōu)化地查詢(xún)新例以獲得收斂于目標(biāo)函數(shù)的解 。于是 ID3 算法被 Quinlan[1]自己擴(kuò)充為 ,。當(dāng)然訓(xùn)練例進(jìn)行估計(jì)很可能產(chǎn)生偏向于規(guī)則的結(jié)果 ,為了克服這一點(diǎn) ,。 下面就 。再加上 ,實(shí)現(xiàn)高效 ,結(jié)果可靠 ,使 。 第三 ,一邊構(gòu)造決策樹(shù) ,一邊進(jìn)行評(píng) 價(jià) ,決策樹(shù)構(gòu)造出來(lái)之后 ,很難再調(diào)整樹(shù)的結(jié)構(gòu)和內(nèi)容 ,決策樹(shù)性能的改善十分困難。它把一些解決方案用一定的方式來(lái)表示 ,放在一起稱(chēng)為群體 (population) 。在工農(nóng)業(yè)、經(jīng)濟(jì)政治、科研方面應(yīng)用極為廣泛。雖然遺傳算法的進(jìn)發(fā)結(jié)果并不能保證得到理論意義上的最佳的決策樹(shù) ,但是它提供了一種試探的過(guò)程。針對(duì)決策樹(shù)的結(jié)構(gòu)和特性 ,我們定義遺傳算子 :首先定義適應(yīng)函數(shù) (fitness function) 。我們有以下幾種重組方式 : (1) 用后代結(jié)點(diǎn)代替祖先結(jié)點(diǎn) ,類(lèi)似于書(shū)的剪枝操作。針對(duì)內(nèi)部結(jié)點(diǎn)和葉節(jié)點(diǎn) ,屬性值的分組與否這些不同情況 ,變異的處理是不一樣的。 (4) 改變?cè)摻Y(jié)點(diǎn)的分支數(shù)。決策樹(shù)的構(gòu)造分為以下幾步 : (1) 第一代群體的產(chǎn)生； (2) 產(chǎn)生下一代； (3) 產(chǎn)生最優(yōu)決策樹(shù)。我們已經(jīng)看到不可能在沒(méi)有任何偏置（ bias）的情況下學(xué)習(xí)。在 這種情況下，即使我們隨機(jī)地從與訓(xùn)練實(shí)例集相一致的假設(shè)集中選擇一個(gè)，它也能對(duì)未知實(shí)例的分類(lèi)進(jìn)行預(yù)測(cè)。 過(guò)學(xué)習(xí)將導(dǎo)致我們所做出的假設(shè)泛化能力過(guò)差。h 使得： ()trainerror h 39。 海南師范大學(xué)本科畢業(yè)論文 14 Cohen和 Jensen提出了一個(gè)有用的理論來(lái)解釋為何會(huì)出現(xiàn)過(guò)學(xué)習(xí)的情況。而大一些的訓(xùn) 練實(shí)例集產(chǎn)生過(guò)學(xué)習(xí)問(wèn)題的可能性更小。但是這種方法等價(jià)于在測(cè)試實(shí)例集中訓(xùn)練決策樹(shù)，這在大多數(shù)情況下是不現(xiàn)實(shí)的。 3．交叉有效性 在此方法中，我們將訓(xùn)練實(shí)例集 T分為互不相交且大小相等的 k個(gè)子集 1T ， 2T ...kT 。 5．決策樹(shù)的復(fù)雜程度 決策樹(shù)的復(fù)雜程度也是度量決策樹(shù)學(xué)習(xí)效果的一個(gè)重要標(biāo)準(zhǔn)。針對(duì)以上問(wèn)題 ,許多學(xué)者提出了處理大型數(shù)據(jù)集的決策樹(shù)算法。 用互信息作為特征選擇量 ,海南師范大學(xué)本科畢業(yè)論文 16 要求訓(xùn)練例子集中的正、反例比例應(yīng)與實(shí)際領(lǐng)域里正、反例比例相同 。 下面針對(duì) ID3 算法的第二個(gè)不足之處 ,提出一些決策樹(shù)改進(jìn)意見(jiàn) 。 對(duì)于基于距離計(jì)算的挖掘 ,數(shù)值歸一化可以幫助消除因?qū)傩匀≈捣秶煌绊懲诰蚪Y(jié)果的公正性 。 3．樣本總類(lèi)內(nèi)離散度 離散度的定義 :一個(gè)在 d維空間由 N個(gè)點(diǎn)組成的聚類(lèi) ,其散布的程度可以用離散度來(lái)衡量 。 假使取聚類(lèi)的均值點(diǎn)作為引點(diǎn) ,則離散度為： 海南師范大學(xué)本科畢業(yè)論文 17 S = |C| （ 3） 式中 C 是聚類(lèi)的協(xié)方差矩陣 ,即離散度矩陣 S。 5．距離函數(shù) 定義一個(gè)距離函數(shù) ,希望投影后 ,各類(lèi)樣本盡可能分得開(kāi)些 ,即希望 ujd 越小越好 ； 同時(shí)希望各類(lèi)樣本內(nèi)部盡量密集 ,即希望類(lèi)內(nèi)離散度 wjs 越小越好 . 由式（ 5）和（ 8）定義距離函數(shù)。 3)選擇較小的值所對(duì)應(yīng)的那一個(gè)特征 kA 作為分類(lèi)特征 ,對(duì)數(shù)據(jù)集 D 進(jìn)行分割 , kA 取幾個(gè)值就得幾個(gè)子集 。利用數(shù)學(xué)公式計(jì)算并構(gòu)建決策樹(shù)是眾多決策樹(shù)算法中的優(yōu)先選擇。在眾多的歸一化方法中找到一種合適的方式是很耗費(fèi)的事，如果事先為計(jì)算機(jī)選擇好歸一化方法可以減輕計(jì)算機(jī)的負(fù)擔(dān)，但這卻給設(shè)計(jì)者帶來(lái)了負(fù)擔(dān)。 （ 3）建樹(shù)步驟 2中： 對(duì)訓(xùn)練集 D ,要利用式 (5)、 (8)、 (9)等三個(gè)公式來(lái) 求出 每一個(gè)訓(xùn)練實(shí)例的距離函數(shù)。但也需要花費(fèi)計(jì)算機(jī)的時(shí)間來(lái)做。 借用概率統(tǒng)計(jì)知識(shí)并 由此延伸出以下定義 : 定義 :設(shè) A、 B是事件 ,稱(chēng) P(B|A)為事件 A 發(fā)生時(shí)事件 B會(huì)發(fā)生的條件概率 ,并稱(chēng)這個(gè)條件概率P(B|A)為訓(xùn)練實(shí)例集 A發(fā)生后 ,事件 B對(duì)訓(xùn)練集中某例別的影響度 。 例子一： 表 1 ID age ine student credit_rating Class 1 youth high no fair N 2 youth high no excellent N 3 Middleaged high no fair Y 4 old medium no fair Y 5 old low yes fair Y 海南師范大學(xué)本科畢業(yè)論文 20 6 old low yes excellent N 7 Middleaged low yes excellent Y 8 youth medium no fair N 9 youth low yes fair Y 10 old medium yes fair Y 11 youth medium yes excellent Y 12 Middleaged medium no excellent Y 13 Middleaged high yes fair Y 14 old medium no excellent N 表 1的樣本數(shù)據(jù)集實(shí)例按人員所屬類(lèi)別分為 N、 Y兩個(gè)類(lèi)別 ,并利用基于條件概率的決策樹(shù)算法建立決策樹(shù) ,對(duì)表 1的實(shí)例集進(jìn)行分類(lèi) 。 在表 1的數(shù)據(jù)集中 ,實(shí)例集大小為 14,age取值為 youth的記錄有 5條 ,取值為 Middleaged的記錄有 4條，取值為 old的有 5條 ； ine取值為 high的記錄有 4條 ,取值為 medium的記錄有 6條， 取值為 low的記錄有 4條 ； student取值為 no的記錄有 7條，取 值為 yes的記錄有 7條； creditrating取值為 fair的記錄有 8條，取值為 excellent的記錄有 6條。 P( Nyouth|年齡 )為年齡屬于 youth 人員所屬類(lèi)別 (Class)為 N的條件概率 ,其余類(lèi)推 ,由條件概率的概念可知 : 海南師范大學(xué)本科畢業(yè)論文 21 P(youth|age) = 514； P(Middleaged|age) = 414 P(old|age) = 514； P(high|ine) = 414； P(medium|ine) = 614 P(low|ine) = 414 ； P(no|student) = 714 ； P(yes|student) = 714 ； P(fair|creditrating) = 814 ； P(excellent|creditrating) = 614 ； P(N ,youth|age) = 314 ； P(N , Middleaged|age) = 0； P(N ,old|age) = 214 ； P(N,high|ine) = 214 ； P(N , medium | ine) = 214 P(N,low|ine)= 114 海南師范大學(xué)本科畢業(yè)論文 22 P(N ,no|student) = 414； P(N ,yes|student) = 114； P(N,fair|creditrating) = 214； P(N,excellcent|creditrating)= 314 根據(jù)公式： P(B|A) = ()()PABPA有 : P(+|正 ) = ( , )()PP?正正, 可以知道每個(gè)屬性對(duì)分類(lèi)為 N的影響度 : P( Nhigh|ine) = P( N ,hig h| in e)P( hig h| in e) = 12 ； 同理 : P( diNme um |ine) = 12 ； P( Nlow |ine) = 14 ； P( Nyouth|age) = 35 ； P(MiddleagedN|age) = 0； P( Nold |age) = 25 ； P(Nno |student) = 47 ； P( Nyes|student) = 17 ； 海南師范大學(xué)本科畢業(yè)論文 23 P( Nfair|creditrating) = 14； P( Nexcellent|creditrating) = 12。 根 結(jié) 點(diǎn) （ 1 ，2 ， . . . ， 1 4 ） a g e結(jié) 點(diǎn) 3（ 4 , 5 , 6 , 1 0 , 1 4 ）c r e d i t r a t i n g結(jié) 點(diǎn) 1（ 1 , 2 , 8 , 9 , 1 1 , ）s t u d e n tyoutholdMiddleaged結(jié) 點(diǎn) 2（ 3 , 7 , 1 2 , 1 3 ）s t u d e n tnoyes結(jié) 點(diǎn) 4（ 1 , 2 , 8 ）結(jié) 點(diǎn) 5（ 9 , 1 1 , ）noyes結(jié) 點(diǎn) 6（ 4 , 5 , 1 0 ）結(jié) 點(diǎn) 7（ 6 , 1 4 ）NYYNY 生成如下決策樹(shù)分類(lèi)規(guī)則： IF age=“ youth” AND student = “ no” THEN Class=“ N” IF age=“ Middleaged” THEN Class=“ Y” IF age=“ youth” AND student = “ yes” THEN Class=“ Y” IF age=“ old” AND creditrating=“ fair” THEN Class=“ Y” IF age=“ old” AND creditrating=“ excellent” THEN Class=“ N” 例子二： 表 2 性格 父母教育程度 性別 類(lèi)別 內(nèi)向 良 女生 好 海南師范大學(xué)本科畢業(yè)論文 24 外向 外向 內(nèi)向 外向 內(nèi)向 外向 外向 外向 內(nèi)向 內(nèi)