【正文】 )好 外 向 性 格外 向 性 格 = 23 ； 海南師范大學本科畢業(yè)論文 26 P(好良|父母教育程度 ) = P( , | )P( | )好 良 父 母 教 育 程 度良 父 母 教 育 程 度 = 1； P(好中|父母教育。 根 結(jié) 點 （ 1 ，2 ， . . . ， 1 4 ） a g e結(jié) 點 3（ 4 , 5 , 6 , 1 0 , 1 4 ）c r e d i t r a t i n g結(jié) 點 1（ 1 , 2 , 8 , 9 , 1 1 , ）s t u d e n tyoutholdMiddleaged結(jié) 點 2（ 3 , 7 , 1 2 , 1 3 ）s t u d e n tnoyes結(jié) 點 4（ 1 , 2 , 8 ）結(jié) 點 5（ 9 , 1 1 , ）noyes結(jié) 點 6（ 4 , 5 , 1 0 ）結(jié) 點 7（ 6 , 1 4 ）NYYNY 生成如下決策樹分類規(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 性格 父母教育程度 性別 類別 內(nèi)向 良 女生 好 海南師范大學本科畢業(yè)論文 24 外向 外向 內(nèi)向 外向 內(nèi)向 外向 外向 外向 內(nèi)向 內(nèi)向 內(nèi)向 良 中 差 中 良 差 差 良 中 中 差 男生 女生 女生 男生 男生 女生 男生 女生 女生 男生 男生 好 差 差 好 好 好 差 好 差 差 差 表 2的樣本數(shù)據(jù)集實例按人員所屬類別分為 好 、 差 兩個類別 ,并利用基于條件概率的 決策樹算法建立決策樹 ,對表 2的實例集進行分類 。 在表 1的數(shù)據(jù)集中 ,實例集大小為 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條。 借用概率統(tǒng)計知識并 由此延伸出以下定義 : 定義 :設 A、 B是事件 ,稱 P(B|A)為事件 A 發(fā)生時事件 B會發(fā)生的條件概率 ,并稱這個條件概率P(B|A)為訓練實例集 A發(fā)生后 ,事件 B對訓練集中某例別的影響度 。 （ 3）建樹步驟 2中： 對訓練集 D ,要利用式 (5)、 (8)、 (9)等三個公式來 求出 每一個訓練實例的距離函數(shù)。利用數(shù)學公式計算并構建決策樹是眾多決策樹算法中的優(yōu)先選擇。 5．距離函數(shù) 定義一個距離函數(shù) ,希望投影后 ,各類樣本盡可能分得開些 ,即希望 ujd 越小越好 ； 同時希望各類樣本內(nèi)部盡量密集 ,即希望類內(nèi)離散度 wjs 越小越好 . 由式（ 5）和（ 8）定義距離函數(shù)。 3．樣本總類內(nèi)離散度 離散度的定義 :一個在 d維空間由 N個點組成的聚類 ,其散布的程度可以用離散度來衡量 。 下面針對 ID3 算法的第二個不足之處 ,提出一些決策樹改進意見 。針對以上問題 ,許多學者提出了處理大型數(shù)據(jù)集的決策樹算法。 3．交叉有效性 在此方法中，我們將訓練實例集 T分為互不相交且大小相等的 k個子集 1T ， 2T ...kT 。而大一些的訓 練實例集產(chǎn)生過學習問題的可能性更小。h 使得： ()trainerror h 39。在 這種情況下，即使我們隨機地從與訓練實例集相一致的假設集中選擇一個，它也能對未知實例的分類進行預測。決策樹的構造分為以下幾步 : (1) 第一代群體的產(chǎn)生； (2) 產(chǎn)生下一代； (3) 產(chǎn)生最優(yōu)決策樹。針對內(nèi)部結(jié)點和葉節(jié)點 ,屬性值的分組與否這些不同情況 ,變異的處理是不一樣的。針對決策樹的結(jié)構和特性 ,我們定義遺傳算子 :首先定義適應函數(shù) (fitness function) 。在工農(nóng)業(yè)、經(jīng)濟政治、科研方面應用極為廣泛。 第三 ,一邊構造決策樹 ,一邊進行評 價 ,決策樹構造出來之后 ,很難再調(diào)整樹的結(jié)構和內(nèi)容 ,決策樹性能的改善十分困難。 下面就 。于是 ID3 算法被 Quinlan[1]自己擴充為 ,。其最原始的程序只是用來區(qū)分象棋中的走步 ,所以區(qū)分的類別只有兩種 T或 F ,其屬性值也是一些離散有限的值 ,而今 ID3算法已發(fā)展到允許多于兩個類別 ,而其屬性值可以是整數(shù)或?qū)崝?shù)。這里簡化計算過程 ,算出 :Gain(Es,性格 )= 和 Gain(Es,性別 ) =。則根節(jié)點的熵值為 : 6 6 6 6( ) l o g 2 l o g 21 2 6 6 1 2 6 6E n tr o p y E s ? ? ??? = 1 下面分別計算例子集中各個屬性的信息贏取值。則根節(jié)點的熵值為 : a g eC r e d i t r a t i n gs t u d e n tyoutholdMiddleageds t u d e n tnoyesfairexcellentN Y YNY 生成 如下決策樹分類規(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” 海南師范大學本科畢業(yè)論文 8 IF age=“ old” AND creditrating=“ fair” THEN Class=“ Y” IF age=“ old” AND creditrating=“ excellent” THEN Class=“ N” 例子二： 這里我們通過考察?？谀承?學生的學習狀況為例 ,來展示 ID3 算法的實際流程。 表 1 ID age ine student Creditrating 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 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 首先利用公式 I（ p,n） = l o g 2 l o g 2p p np n p n p n? ? ????計算樣本分類所需要的期望信息： I（ 1Y ， 2Y ） = I（ 9， 5） =229 9 5 5lo g lo g1 4 1 4 1 4 1 4?=，然后計算每個屬性的熵。較 T1,T2,T3的結(jié)點個數(shù) ,選擇結(jié)點最少的樹。 (3)葉節(jié)點數(shù)量最少且葉子結(jié)點深度最小。(2)一棵決策樹能對一例子 做 出正確類別判斷所需的信息量為 : I（ p,n） = l o g 2 l o g 2p p np n p n p n? ? ???? 如果以屬性 A作為決策樹的根 , A具有 v個值 (1V , 2V ,? ,nV ) ,它將 E分為 v個子集 ( 1E , 2E ,? , 海南師范大學本科畢業(yè)論文 5 vE ) ,假設 iE 中含有 Pi個正例和 in 個反例 ,子集 iE 的信息熵為 I(Pi,in ) ,以屬性 A為根分類后的信息熵為： 1( ) ( )v iiiii pnE A I p npn? ????? 因此 ,以 A 為根的信息增益是 Gain (A) = I (p,n) E(A) 。 ID3是基于信息熵的決策樹分類算法。 （ 3）每個屬性可能是值類型，也可能是枚舉類型。一棵決策樹可以代表一個決定訓練實例集分類的決策過程 ,樹的每個結(jié)點對應于一個屬性名或一個特定的測試 ,該測試在此結(jié)點根據(jù)測試的可能結(jié)果對訓練實例集進行劃分。如果信源 X與隨機變量 Y不是相互獨立的，收信者收到信息 Y。 信息論在決策樹學習中有著重要的意義， 1948年 Shannon[1]提出并發(fā)展了信息論，研究以數(shù)學的方法度量并研究信息。）并給出決策樹的評價標準以及決策樹的發(fā)展現(xiàn)狀和以后的發(fā)展方向。 如今有多種數(shù)據(jù)挖掘技術方法，可以分為兩大類。如何有效地利用和處理大量的 信息 成為當今世界共同關心的問題。s mon algorithm, and produces the policymaking tree39。 海 南 師 范 大 學 本科生畢業(yè)論文（設計） 題目 ： 決策樹算法的研究與改進 姓 名： 學 號： 專 業(yè)： 計算機科學與技術 年 級： 05專升本 系 別： 計算機科學與教育技術 完成日期： 2021年 5月 20日 指導教師： 海南師范大學本科畢業(yè)論文 I 本科生畢業(yè)論文（設計）獨創(chuàng)性聲明 本人聲明所呈交的 畢業(yè)論文（設計）是本人在導師指導下進行的研究工作及取得的研究成果，除了 文中特別加以標注和致謝的地方外，本論文中沒有抄襲他人研究成果和偽造數(shù)據(jù)等行為 。 關鍵詞： 數(shù)據(jù)挖掘；決策樹；研究；改進 The Research and Improvement Of Data Mining decisionmaking tree algorithm Author: Tutor: (Hainan Normal University,HaiKou,571158) Abstract: Nowadays there are so much information tounfold in the people at present, which causes our eyes taking out all in, the knowledge explosion has brought the enormous puzzle to the people, how does the effective use data bee the people enterprise success or failure the key. This paper mainly discussed the preliminary research and the discussion to the policymaking tree39。面對大量 多的數(shù)據(jù)， 人們 往往無法找到自己所需要的知識 或信息 ，這就是 所謂 “信息爆炸 [3]”（ Information detonation）以及它給人們 帶來的困惑。數(shù)據(jù)挖掘是在對數(shù)據(jù)實例集 全面而深刻認識的基礎上，對數(shù)據(jù)內(nèi)在和本質(zhì)的高度抽象與概括，也是對數(shù)據(jù)從 感性 認識到 理性 認識的升華 [2]。 本論文主要對決策樹的常見算法（ ID3算法、 ）做初步的研究與探討，（由于遺傳算法與決策樹的構造類型相 似，這里也有涉及。特化是泛化的相反操作，用于限制概念描述的應用范圍。 （ 3）條件熵。在命題邏輯范圍內(nèi) ,