【正文】 算法有 ID 、 CART、 CHAID、 SLIQ和 SPRINT等。 本論文主要對決策樹的常見算法（ ID3算法、 ）做初步的研究與探討，（由于遺傳算法與決策樹的構造類型相 似，這里也有涉及。）并給出決策樹的評價標準以及決策樹的發(fā)展現狀和以后的發(fā)展方向。并在此基礎上利用最新的決策樹算法思想由本人設計實例集驗證相關文獻中筆者的思想，最后提出自己一點意見和看法。 歸納學習 (induction Learning) 是符號學習中研究最為廣泛的一種方法。給定關于某個概念的一系列已知的正例和反例，從中歸納出一個通用的概念描述。歸納學習能夠獲得新的概念，創(chuàng)立新的規(guī)則，發(fā)現新的理論。它的一般操作是泛化（ generalization）和特化（ specialization）。泛化用來擴展一假設的語義信息，以使其能夠包含更多的正例，應用于更多的情況。特化是泛化的相反操作，用于限制概念描述的應用范圍。 信息論在決策樹學習中有著重要的意義， 1948年 Shannon[1]提出并發(fā)展了信息論，研究以數學的方法度量并研究信息。通過通信后對信源中各種符號出現的不確定程度的消除來度量信息量的大小。他提出了一系列概念： 海南師范大學本科畢業(yè)論文 3 （ 1）自信息量。在收到之前，收信者對信源發(fā)出的不確定性定義為信息符號的自信息量。即，其中為信源發(fā)出 的概率。 （ 2）信息熵。自信息量只能反映符號的不確定性，而信息熵可以用來度量信源 X整體的不確定性，定義如下： H（ X） =p(ia )I（ ia ） +P（ 2a ） I（ 2a ） +? +P（ ra ） I（ ra ） = 1 ( ) log ( )riii p a p a?? 其中 r為信源 X所有可能的符號數，即用信源每發(fā)一個符號所提供的平均自信息量來定義信息熵。 （ 3）條件熵。如果信源 X與隨機變量 Y不是相互獨立的，收信者收到信息 Y。那么，用條件熵 H（ X/Y）來度量收信者在收到隨機變量 Y之后，對隨機變量 X仍然存在的不確定性。設 X對應信源符號，Y對應信源符號，為當 Y為時 X為的概率，則有： H（ X/Y） = 11 ( ) lo g ( / )rsi j i jij p a b a b???? （ 4）平均互信息量。用它來表示信號 Y所能提供的關于 X的信息良的大小，用 I（ X， Y） 表示： H（ X， Y） = H（ X） H（ X/Y） 信息論的這些基本概念，對決策樹來說是非常重要的，是決策樹算法的設計與實現基礎。 決策樹是定義布爾函數的一種方法 ,其輸入是一組屬性描述的對象 ,輸出為 yes/ no 決策。它代表一個假設 ,可以寫成邏輯公式。其表達能力限于命題邏輯 ,該對象的任一個屬性的任一次測試均是一個命題 。在命題邏輯范圍內 ,決策樹的表達能力是完全的。一棵決策樹可以代表一個決定訓練實例集分類的決策過程 ,樹的每個結點對應于一個屬性名或一個特定的測試 ,該測試在此結點根據測試的可能結果對訓練實例集進行劃分。劃分出的每個部分都對應于相應訓練實例集子空間的一個分類子問題 ,該分類子問題可以由一棵決策樹來解決。因此 ,一棵決策樹可以看作是 — 個對目標分類的劃分和獲取策略。 一棵決策樹的內部結點是屬性或屬性的集合（又稱測試屬性），葉結點是所要學習劃分的類。根據決策樹各種不同的屬性，可分為以下幾種： （ 1）決策樹的內結點的測試屬性 可能是單變量的，即每個內結點只包含一個屬性。也可能是多變量的。 （ 2）根據測試屬性的不同屬性值的個數，可能使得每個內結點有兩個或多個分支。如果每個海南師范大學本科畢業(yè)論文 4 內結點只有兩個分支則稱之為二叉決策樹。 （ 3）每個屬性可能是值類型，也可能是枚舉類型。 （ 4）分類結果既可能是兩類有可能是多類，如果只有兩類則稱為布爾決策樹。 因為決策樹有不同的等價表示形式，所以會有不同的算法來實現與決策樹學習相同的功能。例如： ID 、 CART、 CHAID、 SLIQ和 SPRINT等等。 算法 算法簡介 上面講到決策樹學習是一種歸納學習方法 ,這里介紹 決策樹學習的核心算法 — ID3 算法， ID3 算法是在所有可能的決策樹空間中一種自頂向下、貪婪的搜索方法。 ID3 算法的關鍵是確定屬性表As中可對訓練實例集 Es進行的最佳分類的屬性 A ,即在樹的每一個節(jié)點上確定一個候選屬性 ,它的測試對訓練例的分類最有利。 ID3搜索的假設空間是可能的決策樹的集合 ,而 ID3搜索目的是構造與訓練數據一致的一棵決策樹。 ID3的搜索策略是爬山法 ,在構造決策樹時從簡單到復雜 ,用信息贏取作為指導 爬山法的評價函數。 ID3是基于信息熵的決策樹分類算法。自從 Quinlan描述和分析了 ID3算法以來 , 有大量的學者圍繞該算法作了十分廣泛的研究。該算法是根據屬性集的取值選擇實例的類別。它的核心是在決策樹中各級結點上選擇屬性 ,用信息增益率作為屬性選擇標準 ,使得在每一非葉結點進行測試時 ,能獲得關于被測試例子最大的類別信息。使用該屬性將例子集分成子集后 ,系統(tǒng)的熵值最小 ,期望該非葉結點到達各后代葉節(jié)點的平均路徑最短 ,使生成的決策樹平均深度較小 ,提高分類速度和準確率。 ID3 的基本原理如下 :設 E = F1 F2 ? Fn 是 n 維有窮向量空間 ,其中 jF 是有窮離散符號集 , E中的元素 e = 1V , 2V ,? ,nV 叫做例子 ,其中 jV ∈ jF , j = 1 ,2 , ? , n。設 PE 和 NE 是 E 的F 兩個例子集 ,分別叫 正例集和反例集。 假設向量空間 E中的正例集 PE和反例集 NE 的大小分別為 p和 n ,ID3基于下列兩個假設 : (1)在向量空間 E 上的一棵正確決策樹 ,對任意例子的分類概率同 E 中的正、反例的概率一致 。(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 選擇使 Gain (A) 最大 (即 E(A) 最小 )的屬性 作為根結點。對 的不同的取值對應的 E 的 v個子集 iE 遞歸調用上述過程 ,生成的子結點 , 12,BB ? ， VB 。 ID3 的基本原理是基于兩類分類問題 ,但很容易擴展到多類。設樣本集 S 共有 C類樣本 ,每類樣本數為 pi ,( i = 1 ,2 ,3 , ? c) 。若以屬性 A 作為決策樹的根 , A 具有 V 個值 1V ,2V ,? ,nV ,它將 E 分成 V 個子集 [ 1E , 2E ,? , vE ] ,假設 iE 中含有 j類樣本的個數為 ijp ,j = 1,2,? ,c那么 ,子集 jE 的信息量是 I( iE )。 1( ) * lo g| | | |c ijvi j iiPPIE EE?? ? 以 A 為根分類的信息熵為 : 1||( ) * ( )||v i iiEE A I EE?? ? 選擇屬性 使 E( A) 最小 ,信息增益也將增大。 理想的決策樹分成 3種 : (1)葉節(jié)點數最小 , (2)葉節(jié)點深度最小 。 (3)葉節(jié)點數量最少且葉子結點深度最小。決策樹的好壞 ,不僅影響分類的效率 ,而且還影響分類的準確率。因而許多學者致力于尋找更優(yōu)的啟發(fā)式函數和評價函數 ,洪家榮、 Pei Lei Tu等人分別證明了要找到這種最優(yōu)的決策樹是 NP難題。因此人們?yōu)榱藢で筝^優(yōu)的解 ,不得不尋求各種啟發(fā)式的方法。有的采用基于屬性相關性的啟發(fā)式函數 。有的對生成的決策樹進行剪枝處 理 。有的則擴充決策樹 ,形成決策圖。 如今普遍 采用的 是 優(yōu)化算法 ,基本思想 :首先用 ID3選擇屬性 F1,建立樹 T1,左、 右子樹的屬性分別為 F2,F3,再以 F2,F3為根 ,重建樹 T2， T3。較 T1,T2,T3的結點個數 ,選擇結點最少的樹。對于選擇定樹的兒子結點采用同樣的方法遞歸建樹。盡管作者用一個實驗證明能建立理想的決策樹 ,但算法有較大的弱點 :時間開銷太大 ,因為每選擇一個新的屬性 ,算法都需要建立 3 棵決策樹 ,從中選優(yōu)。 算法實例 例子 一 ： 這里我們通過考察不同的人群購買 手機 的狀況為例 ,來展示 ID3 算法的實際流程。此例假定要按是否買 手機 對一個集合進行分類 ,該集合中用來描述人群的屬性有 age、 ine、 student 和creditrating。 age的取值為 youth、 Middleaged、 old； Ine的取值為 high、 medium和 low；海南師范大學本科畢業(yè)論文 6 student的取值為 no和 yes； creditrating的取值為 fair和 excellent。例子集中共有 14個人 ,如表 1 所示。在類別一欄 ,將正例即“買 手機 ”的人用“ Y” 標出 ,反例即“不買 手機 ”的人用“ N”標出。 表 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?=，然后計算每個屬性的熵。從 age屬性開始。需要觀察 age的每個樣本值的 Y和 N的分布。 對每個分布計算期望信息。 海南師范大學本科畢業(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） =。由此可知 age在屬性中的信息增益最高，故選它做為測試屬性。創(chuàng)建根結點，用 age標記，并對每個屬值得引出一個分支。依次類推可得出決策樹如下圖： 這些例子 一開始全部包含在根結點中 ,為了找出當前的最佳劃分屬性 ,先須根據前述公式計算訓練例集 Es的熵值。則根節(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=“ you