【正文】 減小訓練實例空間，而增大過學習的可能性，所以這種方法也不可取。如果存在另一個假設 39。去除從樹根到葉節(jié)點路徑上重復的屬性判斷等。一般的算子都是對特征串進行操作的。 第二 ,在 ,而對樹的深度 ,結點的個數等不進行考慮 ,而樹平均深度直接對應著決策樹的預測速度 ,樹的結點個數則代表樹的規(guī)模。但對于增量式學習任務來說 ,由于 ID3不能增量地接受訓練例 ,這就使得每增加一次實例都必須拋 棄原有決策樹 ,重新構造新的決策樹 ,造成了極大的開銷。 父 母 教 育 程 度良差中內 向 ， 良 ， 女 生 ： 好外 向 ， 良 ， 男 生 ： 好內 向 ， 良 ， 男 生 ： 好外 向 ， 良 ， 女 生 ： 好內 向 ， 中 ， 女 生 ： 差外 向 ， 中 ， 男 生 ： 好內 向 ， 中 ， 男 生 ： 差外 向 ， 中 ， 女 生 ： 差內 向 ， 差 ， 女 生 ： 差外 向 ， 差 ， 女 生 ： 好內 向 ， 差 ， 男 生 ： 差外 向 ， 差 ， 男 生 ： 差 按“ 父母教育程度 ”劃分后的決策樹 現(xiàn)在必須根據所提供的信息進一步分析“ 父母教育程度 ”為“中”或“差”的小學生的“學習成績好壞” ,因此必須對“中”和“差”兩個分支的實例組成的例子集 (共 8個例子 ) 重復上述計算過程。依次類推可得出決策樹如下圖： 這些例子 一開始全部包含在根結點中 ,為了找出當前的最佳劃分屬性 ,先須根據前述公式計算訓練例集 Es的熵值。 如今普遍 采用的 是 優(yōu)化算法 ,基本思想 :首先用 ID3選擇屬性 F1,建立樹 T1,左、 右子樹的屬性分別為 F2,F3,再以 F2,F3為根 ,重建樹 T2， T3。 假設向量空間 E中的正例集 PE和反例集 NE 的大小分別為 p和 n ,ID3基于下列兩個假設 : (1)在向量空間 E 上的一棵正確決策樹 ,對任意例子的分類概率同 E 中的正、反例的概率一致 。如果每個海南師范大學本科畢業(yè)論文 4 內結點只有兩個分支則稱之為二叉決策樹。 （ 3）條件熵。 本論文主要對決策樹的常見算法（ ID3算法、 ）做初步的研究與探討，（由于遺傳算法與決策樹的構造類型相 似，這里也有涉及。面對大量 多的數據， 人們 往往無法找到自己所需要的知識 或信息 ，這就是 所謂 “信息爆炸 [3]”（ Information detonation）以及它給人們 帶來的困惑。 海 南 師 范 大 學 本科生畢業(yè)論文（設計） 題目 ： 決策樹算法的研究與改進 姓 名： 學 號： 專 業(yè)： 計算機科學與技術 年 級： 05專升本 系 別： 計算機科學與教育技術 完成日期： 2021年 5月 20日 指導教師： 海南師范大學本科畢業(yè)論文 I 本科生畢業(yè)論文（設計）獨創(chuàng)性聲明 本人聲明所呈交的 畢業(yè)論文（設計）是本人在導師指導下進行的研究工作及取得的研究成果，除了 文中特別加以標注和致謝的地方外，本論文中沒有抄襲他人研究成果和偽造數據等行為 。如何有效地利用和處理大量的 信息 成為當今世界共同關心的問題。）并給出決策樹的評價標準以及決策樹的發(fā)展現(xiàn)狀和以后的發(fā)展方向。如果信源 X與隨機變量 Y不是相互獨立的，收信者收到信息 Y。 （ 3）每個屬性可能是值類型，也可能是枚舉類型。(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) 。較 T1,T2,T3的結點個數 ,選擇結點最少的樹。則根節(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 算法的實際流程。這里簡化計算過程 ,算出 :Gain(Es,性格 )= 和 Gain(Es,性別 ) =。于是 ID3 算法被 Quinlan[1]自己擴充為 ,。 第三 ,一邊構造決策樹 ,一邊進行評 價 ,決策樹構造出來之后 ,很難再調整樹的結構和內容 ,決策樹性能的改善十分困難。針對決策樹的結構和特性 ,我們定義遺傳算子 :首先定義適應函數 (fitness function) 。決策樹的構造分為以下幾步 : (1) 第一代群體的產生； (2) 產生下一代； (3) 產生最優(yōu)決策樹。h 使得： ()trainerror h 39。 3．交叉有效性 在此方法中，我們將訓練實例集 T分為互不相交且大小相等的 k個子集 1T ， 2T ...kT 。 下面針對 ID3 算法的第二個不足之處 ,提出一些決策樹改進意見 。 5．距離函數 定義一個距離函數 ,希望投影后 ,各類樣本盡可能分得開些 ,即希望 ujd 越小越好 ； 同時希望各類樣本內部盡量密集 ,即希望類內離散度 wjs 越小越好 . 由式（ 5）和（ 8）定義距離函數。 （ 3）建樹步驟 2中： 對訓練集 D ,要利用式 (5)、 (8)、 (9)等三個公式來 求出 每一個訓練實例的距離函數。 在表 1的數據集中 ,實例集大小為 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( 好內 向|性格 )為性格 屬于 內向 人員所屬類別 (學習成績 )為 好 的條件概率 ,其余類推 ,由條件概率的概念可知 : P(內 向 |性格 ) = 612 ； P(外向 |性格 ) = 612 P(良 |父母教育程度 ) = 412 ； 海南師范大學本科畢業(yè)論文 25 P(中 |父母教育程度 ) = 412； P(差 |父母教育程度 ) = 412； P(男生 |性別 ) = 612； P(女生 |性別 ) = 612； P(好 ,內向 |性格 ) = 212 ； P(好 ,外向 |性格 ) = 412 ； P(好 , 良 |家庭背景 ) = 412 ； P(好 , 中家庭背景 ) = 112 ； P(好 , 差 |家庭背景 ) = 112 ； P(好 ， 男生 |性別 )= 312 P(好 ,女生 |性別 ) = 312 ； 根據公式： P(B|A) = ()()PABPA有 : P(+|正 ) = ( , )()PP?正正, 可以知道每個屬性對分類為 +影響度 : P( 好內 向|性格 ) = P( , | )P( | )好 內 向 性 格內 向 性 格 = 13 ； 同理 : P( 好外 向|性格 ) = P( , | )P( | )好 外 向 性 格外 向 性 格 = 23 ； 海南師范大學本科畢業(yè)論文 26 P(好良|父母教育程度 ) = P( , | )P( | )好 良 父 母 教 育 程 度良 父 母 教 育 程 度 = 1； P(好中|父母教育。 設 P (youth|old)表示年齡屬于 youth的事件發(fā)生的概率 。 （ 4）建樹步驟 3中：若要選擇距離函數最小的訓練實例就要進行排序。 海南師范大學本科畢業(yè)論文 18 根據上述特征選擇方法 ,在 ID3算法的基礎上 ,提出一種改進的決策樹建樹算法 ,算法步驟如下 : 1)將訓練集窗口中的全部數據 ,選擇一種歸一化方法 ,歸一化到 [0 ,1 ]區(qū)間 ,形成訓練集 D。 其中 ,Si表示第 i類總的樣本數 , kijX 表示第 i類第 k個樣本在第 j維特征處的取值 。 4．余一有效性（ leaveoneout validation） 這種有效性的度量與交叉有效性類似，不同之處在于將每個 iT 的大小定為 1。()Derror h 一般將 ()trainerror h 成為重替換（ resubstitution）錯 誤率，在本書中將其簡記為 r錯誤率。下面，給出評價決策樹的一些標準。 復制算子的定義與常用的復制算子的定義一致。 GA(Geic Algorithm) 遺傳算法是一種通用搜索算法。根據放在結點的信息 ,就可以判斷出哪個屬性的訓練例集 Es值最小 ,從而確定當前用哪一個屬性來進行劃分。 父 母 教 育 程 度良差中內 向 ， 良 ， 女 生 ： 好外 向 ， 良 ， 男 生 ： 好內 向 ， 良 ， 男 生 ： 好外 向 ， 良 ， 女 生 ： 好內 向 ， 中 ， 女 生 ： 差內 向 ， 中 ， 男 生 ： 差內 向 ， 差 ， 女 生 ： 差內 向 ， 差 ， 男 生 ： 差性 格內 向外 向外 向 ， 中 ， 男 生 ： 好外 向 ， 中 ， 女 生 ： 差性 格內 向外 向外 向 ， 差 ， 女 生 ： 好外 向 ， 差 ， 男 生 ： 差 海南師范大學本科畢業(yè)論文 10 按“性格”作第二次劃分后的決策樹 現(xiàn)在只有“ 父母教育程度 ”為“中”和“差”的“外向”小學生還沒有明確類別 ,它們要用屬性“性別”來進一步劃分。性格的取 值為外向、內向。盡管作者用一個實驗證明能建立理想的決策樹 ,但算法有較大的弱點 :時間開銷太大 ,因為每選擇一個新的屬性 ,算法都需要建立 3 棵決策樹 ,從中選優(yōu)。對 的不同的取值對應的 E 的 v個子集 iE 遞歸調用上述過程 ,生成的子結點 , 12,BB ? ， VB 。 因為決策樹有不同的等價表示形式，所以會有不同的算法來實現(xiàn)與決策樹學習相同的功能。設 X對應信源符號，Y對應信源符號，為當 Y為時 X為的概率，則有： H（ X/Y） = 11 ( ) lo g ( / )rsi j i jij p a b a b???? （ 4）平均互信息量。 歸納學習 (induction Learning) 是符號學習中研究最為廣泛的一種方法。 自 數據挖掘技術誕生以來，關于數據挖掘技術的研究也就開始了。 論文（設計）作者簽名： 日期： 2021年 5 月 21日 本科生畢業(yè)論文（設計）使用授權聲明 海南師范大學有權保留并向國家有關部門或機構送交畢業(yè)論文（設計）的復印件和磁盤，允許畢業(yè)論文（設計）被查閱和借閱。 Improvement 隨著現(xiàn)代信息技術的 飛速 發(fā)展，在全球 范圍 內掀起了信息化 （ Information） 浪潮。同時，還存在數據的 “ 缺值 ” 處理問題。 （ 2）信息熵。也可能是多變量的。 ID3 的基本原理如下 :設 E = F1 F2 ? Fn 是 n 維有窮向量空間 ,其中 jF 是有窮離散符號集 , E中的元素 e = 1V , 2V ,? ,nV 叫做例子 ,其中 jV ∈ jF , j = 1 ,2 , ? , n。有的對生成的決策樹進行