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

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

一：ID3算法

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

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

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

對于子節(jié)點遞歸的調(diào)用以上方法，構建決策樹;

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

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

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

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

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

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

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

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

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

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

ID3算法存在的缺點：

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

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

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

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

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