本文實例講述了決策樹剪枝算法的python實現(xiàn)方法。分享給大家供大家參考，具體如下：

決策樹是一種依托決策而建立起來的一種樹。在機器學(xué)習(xí)中，決策樹是一種預(yù)測模型，代表的是一種對象屬性與對象值之間的一種映射關(guān)系，每一個節(jié)點代表某個對象，樹中的每一個分叉路徑代表某個可能的屬性值，而每一個葉子節(jié)點則對應(yīng)從根節(jié)點到該葉子節(jié)點所經(jīng)歷的路徑所表示的對象的值。決策樹僅有單一輸出，如果有多個輸出，可以分別建立獨立的決策樹以處理不同的輸出。

ID3算法:ID3算法是決策樹的一種，是基于奧卡姆剃刀原理的，即用盡量用較少的東西做更多的事。ID3算法，即Iterative Dichotomiser 3，迭代二叉樹3代，是Ross Quinlan發(fā)明的一種決策樹算法，這個算法的基礎(chǔ)就是上面提到的奧卡姆剃刀原理，越是小型的決策樹越優(yōu)于大的決策樹，盡管如此，也不總是生成最小的樹型結(jié)構(gòu)，而是一個啟發(fā)式算法。在信息論中，期望信息越小，那么信息增益就越大，從而純度就越高。ID3算法的核心思想就是以信息增益來度量屬性的選擇，選擇分裂后信息增益大的屬性進行分裂。該算法采用自頂向下的貪婪搜索遍歷可能的決策空間。
信息熵，將其定義為離散隨機事件出現(xiàn)的概率，一個系統(tǒng)越是有序，信息熵就越低，反之一個系統(tǒng)越是混亂，它的信息熵就越高。所以信息熵可以被認為是系統(tǒng)有序化程度的一個度量。

基尼指數(shù)：在CART里面劃分決策樹的條件是采用Gini Index，定義如下：gini(T)=1−sumnj=1p2j。其中，( p_j )是類j在T中的相對頻率，當(dāng)類在T中是傾斜的時，gini(T)會最小。將T劃分為T1（實例數(shù)為N1）和T2（實例數(shù)為N2）兩個子集后，劃分數(shù)據(jù)的Gini定義如下：ginisplit(T)=fracN1Ngini(T1)+fracN2Ngini(T2)，然后選擇其中最小的(gini_{split}(T) )作為結(jié)點劃分決策樹
具體實現(xiàn)
首先用函數(shù)calcShanno計算數(shù)據(jù)集的香農(nóng)熵，給所有可能的分類創(chuàng)建字典

def calcShannonEnt(dataSet): 
  numEntries = len(dataSet) 
  labelCounts = {} 
  # 給所有可能分類創(chuàng)建字典 
  for featVec in dataSet: 
    currentLabel = featVec[-1] 
    if currentLabel not in labelCounts.keys(): 
      labelCounts[currentLabel] = 0
    labelCounts[currentLabel] += 1
  shannonEnt = 0.0
  # 以2為底數(shù)計算香農(nóng)熵
  for key in labelCounts:
    prob = float(labelCounts[key]) / numEntries
    shannonEnt -= prob * log(prob, 2)
  return shannonEnt