【正文】 .. 16 ................................................................................................ 16 ........................................................................... 17 ............................................................................................. 18 ....................................................................................................... 18 ............................................................. 18 .................................................................... 19 ................................................................................................ 19 ............................................................................................. 27 ....................................................................................................... 27 ............................................................................................................................ 28 ......................................................................................................................... 28 ............................................................................................................................ 28 參考文獻(xiàn) ......................................................................................................................... 29 海南師范大學(xué)本科畢業(yè)論文 1 挖掘決策樹算法的研究與改進(jìn) 作者： 指導(dǎo)老師： （海南師范大學(xué)，?？?， 571158） 摘 要： 在大量信息展現(xiàn)給人們的時候，“知識爆炸”給人們帶來了極大的困擾，如何有效的利用數(shù)據(jù)成為人們事業(yè)成敗的關(guān)鍵。 Research。目前， 普遍采用的主要有數(shù)據(jù)挖掘（ DM）和數(shù)據(jù)庫中的知識發(fā)現(xiàn)（ Knowledge Discovery 海南師范大學(xué)本科畢業(yè)論文 2 in Database，簡稱 KDD）。其缺點是處理復(fù)雜性的數(shù)據(jù)時，分支數(shù) 目 非常多，管理難度大。歸納學(xué)習(xí)能夠獲得新的概念，創(chuàng)立新的規(guī)則，發(fā)現(xiàn)新的理論。即，其中為信源發(fā)出 的概率。 決策樹是定義布爾函數(shù)的一種方法 ,其輸入是一組屬性描述的對象 ,輸出為 yes/ no 決策。根據(jù)決策樹各種不同的屬性，可分為以下幾種： （ 1）決策樹的內(nèi)結(jié)點的測試屬性 可能是單變量的，即每個內(nèi)結(jié)點只包含一個屬性。 算法 算法簡介 上面講到?jīng)Q策樹學(xué)習(xí)是一種歸納學(xué)習(xí)方法 ,這里介紹 決策樹學(xué)習(xí)的核心算法 — ID3 算法， ID3 算法是在所有可能的決策樹空間中一種自頂向下、貪婪的搜索方法。使用該屬性將例子集分成子集后 ,系統(tǒng)的熵值最小 ,期望該非葉結(jié)點到達(dá)各后代葉節(jié)點的平均路徑最短 ,使生成的決策樹平均深度較小 ,提高分類速度和準(zhǔn)確率。設(shè)樣本集 S 共有 C類樣本 ,每類樣本數(shù)為 pi ,( i = 1 ,2 ,3 , ? c) 。有的采用基于屬性相關(guān)性的啟發(fā)式函數(shù) 。此例假定要按是否買 手機 對一個集合進(jìn)行分類 ,該集合中用來描述人群的屬性有 age、 ine、 student 和creditrating。 海南師范大學(xué)本科畢業(yè)論文 7 對于 age=“ youth”： 11Y =2 21Y =3 I（ 11Y ， 12Y ） = 對于 age=“ middleaged” 12Y =4 22Y =0 I（ 21Y , 22Y ） =0 對于 age=“ old” 13Y =3 23Y =2 I（ 13Y ， 23Y ） = 如果樣本按 age劃分，對一個給定的樣本分類所需的期望信息為： E（ age） =514 I（ 11Y ， 12Y ） +414 I（ 21Y , 22Y ） +514 I（ 13Y ， 23Y ） = 計算其信息增益為： Gain（ 1Y ， 2Y ） = I（ 1Y ， 2Y ） E（ age） = 類似地，計算 Gain（ ine） =， Gain（ student） = Gain（ creditrating） =。性別的取值為男 生 、 女生 。因此 , 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ù)“性格”屬性來進(jìn)行例子集分類的信息贏取值為 : Gain(Es,性格 )=Entropy(Es)Entropy(Esv,格 )= 111 ( * 0 .9 1 8 3 + * 0 .9 1 8 3 ) = 0 .0 8 1 722 同理 ,對“ 父母教育程度 ”來說 :Gain(Es, 父母教育程度 )= 。 父 母 教 育 程 度良差中內(nèi) 向 ， 良 ， 女 生 ： 好外 向 ， 良 ， 男 生 ： 好內(nèi) 向 ， 良 ， 男 生 ： 好外 向 ， 良 ， 女 生 ： 好內(nèi) 向 ， 中 ， 女 生 ： 差內(nèi) 向 ， 中 ， 男 生 ： 差內(nèi) 向 ， 差 ， 女 生 ： 差內(nèi) 向 ， 差 ， 男 生 ： 差性 格內(nèi) 向外 向{ 外 向 ， 中 ， 女 生 ： 差 }性 格內(nèi) 向外 向{ 外 向 ， 差 ， 男 生 ： 差 }性 別女 生男 生{ 外 向 ， 中 ， 男 生 ： 好 }{ 外 向 ， 差 ， 女 生 ： 好 }性 別男 生女 生 最終得到的決策樹 IF 父母教 育程度 =“良” THEN 學(xué)習(xí)成績 =“好” IF 父母教育程度 =“中” AND 性格 =“內(nèi)向” THEN學(xué)習(xí)成績 =“差” IF 父母教育程度 =“差” AND 性格 =“內(nèi)向” THEN學(xué)習(xí)成績 =“差” IF 父母教育程度 =“中” AND 性格 =“外向” AND 性別 =“女生” THEN學(xué)習(xí)成績 =“差” IF 父母教育程度 =“中” AND 性格 =“外向” AND 性別 =“男生” THEN學(xué)習(xí)成績 =“好” IF 父母教育程度 =“差” AND 性格 =“外向” AND 性別 =“女生” THEN學(xué)習(xí)成績 =“好” IF 父母教育程度 =“差” AND 性格 =“外向” AND 性別 =“男生” THEN學(xué)習(xí)成績 =“差” 但是 不能保證 ID3算法對任何問題總能做出最佳選擇 ,只能說它在一般情況下能夠找出最優(yōu)決策樹。 缺點 :搜索中只維持一個解 ,不能像候選剪除算法那樣返回所有可能的與練例集一致的假設(shè) ,并優(yōu)化地查詢新例以獲得收斂于目標(biāo)函數(shù)的解 。當(dāng)然訓(xùn)練例進(jìn)行估計很可能產(chǎn)生偏向于規(guī)則的結(jié)果 ,為了克服這一點 ,。再加上 ,實現(xiàn)高效 ,結(jié)果可靠 ,使 。它把一些解決方案用一定的方式來表示 ,放在一起稱為群體 (population) 。雖然遺傳算法的進(jìn)發(fā)結(jié)果并不能保證得到理論意義上的最佳的決策樹 ,但是它提供了一種試探的過程。我們有以下幾種重組方式 : (1) 用后代結(jié)點代替祖先結(jié)點 ,類似于書的剪枝操作。 (4) 改變該結(jié)點的分支數(shù)。我們已經(jīng)看到不可能在沒有任何偏置（ bias）的情況下學(xué)習(xí)。 過學(xué)習(xí)將導(dǎo)致我們所做出的假設(shè)泛化能力過差。 海南師范大學(xué)本科畢業(yè)論文 14 Cohen和 Jensen提出了一個有用的理論來解釋為何會出現(xiàn)過學(xué)習(xí)的情況。但是這種方法等價于在測試實例集中訓(xùn)練決策樹，這在大多數(shù)情況下是不現(xiàn)實的。 5．決策樹的復(fù)雜程度 決策樹的復(fù)雜程度也是度量決策樹學(xué)習(xí)效果的一個重要標(biāo)準(zhǔn)。 用互信息作為特征選擇量 ,海南師范大學(xué)本科畢業(yè)論文 16 要求訓(xùn)練例子集中的正、反例比例應(yīng)與實際領(lǐng)域里正、反例比例相同 。 對于基于距離計算的挖掘 ,數(shù)值歸一化可以幫助消除因?qū)傩匀≈捣秶煌绊懲诰蚪Y(jié)果的公正性 。 假使取聚類的均值點作為引點 ,則離散度為： 海南師范大學(xué)本科畢業(yè)論文 17 S = |C| （ 3） 式中 C 是聚類的協(xié)方差矩陣 ,即離散度矩陣 S。 3)選擇較小的值所對應(yīng)的那一個特征 kA 作為分類特征 ,對數(shù)據(jù)集 D 進(jìn)行分割 , kA 取幾個值就得幾個子集 。在眾多的歸一化方法中找到一種合適的方式是很耗費的事，如果事先為計算機選擇好歸一化方法可以減輕計算機的負(fù)擔(dān)，但這卻給設(shè)計者帶來了負(fù)擔(dā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ù)集實例按人員所屬類別分為 N、 Y兩個類別 ,并利用基于條件概率的決策樹算法建立決策樹 ,對表 1的實例集進(jìn)行分類 。 P( Nyouth|年齡 )為年齡屬于 youth 人員所屬類別 (Class)為 N的條件概率 ,其余類推 ,由條件概率的概念可知 : 海南師范大學(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?正正,