劃分數據集的最大原則是：使無序的數據變的有序。如果一個訓練數據中有20個特征，那么選取哪個做劃分依據?這就必須采用量化的方法來判斷，量化劃分方法有多重，其中一項就是“信息論度量信息分類”。基于信息論的決策樹算法有ID3、CART和C4.5等算法，其中C4.5和CART兩種算法從ID3算法中衍生而來。

決策樹的生成算法由很多變形，這里簡單說一下幾種經典的實現算法：ID3算法，C4.5算法和CART算法。這些算法的主要區別在于分類結點熵特征選擇的選取標準不同，下面了解一下算法的具體實現過程。

一：ID3算法

ID3算法所采用的度量標準就是我們前面提到的“信息增益”。當屬性a的信息增益最大時，則意味著用a屬性劃分，其所獲得的“純度”提升最大，我們所要做的，就是找到信息增益最大的屬性。

ID3算法的核心是在決策樹的各個節點上應用信息增益準則進行特征選擇，具體的做法是：

從根節點上開始，對結點計算所有可能特征的信息增益，選擇信息增益最大的特征作為結點的特征，并由該特征的不同取值構建子節點;

對于子節點遞歸的調用以上方法，構建決策樹;

直到所有特征的信息增益均很小或者沒有特征可選擇的時候為止。

ID3算法具體的算法過程如下：

輸入的是m個樣本，樣本輸出集合為D，每個樣本有n個離散特征，特征集合為A，輸出為決策樹T。

1，初始化信息增益的閾值€

2，判斷樣本是否為同一類輸出Di，如果是則返回單節點樹T，標記類別為Di

3，判斷特征是否為空，如果是則返回單節點樹T，標記類別為樣本值紅輸出類別D實例數最多的類別

4，計算A中的各個特征(一共n個)對輸出D的信息增益，選擇信息增益最大的特征Ag

5，如果Ag的信息增益小于閾值€，則返回單節點樹T，標記類別為樣本中輸出類別D實例樹最多的類別

6，否則，按特征Ag的不同取值Agi將對應的樣本輸出D分成不同的類別Di，每個類別產生一個子節點。對應特征為Agi，返回增加了節點的數T

7，對于所有的子節點，令D=Di，A=A-{Ag}遞歸調用2~6步，得到子樹Ti并返回

ID3算法存在的缺點：

1.ID3算法在選擇根節點和內部節點中的分支屬性時，采用信息增益作為評價標準。信息增益的缺點是傾向于選擇取值較多是屬性，在有些情況下這類屬性可能不會提供太多有價值的信息。

2.ID3算法只能對描述屬性為離散型屬性的數據集構造決策樹。

3.ID3算法對于缺失值的情況沒做考慮。

4.沒有考慮過擬合的問題。

以上內容為大家介紹了Python決策樹的生成算法介紹，希望對大家有所幫助，如果想要了解更多Python相關知識，請關注IT培訓機構:千鋒教育。