【正文】 ......... 2 ............................................................................................................. 2 ................................................................................. 2 .................................................................................... 2 .................................................................................... 3 ...................................................................... 4 算法 .................................................................................................. 4 ........................................................................................ 11 GA(Geic Algorithm) .......................................................... 12 [1] ....................................................................................... 13 .................................................................................. 15 .......................................................... 15 ................................................... 15 ................................................................................................ 15 [6]的特征選擇方法 .................................................................. 16 ................................................................................................ 16 ........................................................................... 17 ............................................................................................. 18 ....................................................................................................... 18 ............................................................. 18 .................................................................... 19 ................................................................................................ 19 ............................................................................................. 27 ....................................................................................................... 27 ............................................................................................................................ 28 ......................................................................................................................... 28 ............................................................................................................................ 28 參考文獻 ......................................................................................................................... 29 海南師范大學本科畢業(yè)論文 1 挖掘決策樹算法的研究與改進 作者： 指導老師： （海南師范大學，?？?， 571158） 摘 要： 在大量信息展現(xiàn)給人們的時候，“知識爆炸”給人們帶來了極大的困擾，如何有效的利用數(shù)據(jù)成為人們事業(yè)成敗的關鍵。s mon algorithm, and produces the policymaking tree39。 Research。如何有效地利用和處理大量的 信息 成為當今世界共同關心的問題。目前， 普遍采用的主要有數(shù)據(jù)挖掘（ DM）和數(shù)據(jù)庫中的知識發(fā)現(xiàn)（ Knowledge Discovery 海南師范大學本科畢業(yè)論文 2 in Database，簡稱 KDD）。 如今有多種數(shù)據(jù)挖掘技術方法，可以分為兩大類。其缺點是處理復雜性的數(shù)據(jù)時，分支數(shù) 目 非常多，管理難度大。）并給出決策樹的評價標準以及決策樹的發(fā)展現(xiàn)狀和以后的發(fā)展方向。歸納學習能夠獲得新的概念，創(chuàng)立新的規(guī)則，發(fā)現(xiàn)新的理論。 信息論在決策樹學習中有著重要的意義， 1948年 Shannon[1]提出并發(fā)展了信息論，研究以數(shù)學的方法度量并研究信息。即，其中為信源發(fā)出 的概率。如果信源 X與隨機變量 Y不是相互獨立的，收信者收到信息 Y。 決策樹是定義布爾函數(shù)的一種方法 ,其輸入是一組屬性描述的對象 ,輸出為 yes/ no 決策。一棵決策樹可以代表一個決定訓練實例集分類的決策過程 ,樹的每個結(jié)點對應于一個屬性名或一個特定的測試 ,該測試在此結(jié)點根據(jù)測試的可能結(jié)果對訓練實例集進行劃分。根據(jù)決策樹各種不同的屬性，可分為以下幾種： （ 1）決策樹的內(nèi)結(jié)點的測試屬性 可能是單變量的，即每個內(nèi)結(jié)點只包含一個屬性。 （ 3）每個屬性可能是值類型，也可能是枚舉類型。 算法 算法簡介 上面講到?jīng)Q策樹學習是一種歸納學習方法 ,這里介紹 決策樹學習的核心算法 — ID3 算法， ID3 算法是在所有可能的決策樹空間中一種自頂向下、貪婪的搜索方法。 ID3是基于信息熵的決策樹分類算法。使用該屬性將例子集分成子集后 ,系統(tǒng)的熵值最小 ,期望該非葉結(jié)點到達各后代葉節(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) 。設樣本集 S 共有 C類樣本 ,每類樣本數(shù)為 pi ,( i = 1 ,2 ,3 , ? c) 。 (3)葉節(jié)點數(shù)量最少且葉子結(jié)點深度最小。有的采用基于屬性相關性的啟發(fā)式函數(shù) 。較 T1,T2,T3的結(jié)點個數(shù) ,選擇結(jié)點最少的樹。此例假定要按是否買 手機 對一個集合進行分類 ,該集合中用來描述人群的屬性有 age、 ine、 student 和creditrating。 表 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?=，然后計算每個屬性的熵。 海南師范大學本科畢業(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） =。則根節(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 算法的實際流程。性別的取值為男 生 、 女生 。則根節(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 ? ?