決策樹也是有監(jiān)督機(jī)器學(xué)習(xí)方法。 電影《無恥混蛋》里有一幕游戲，在德軍小酒館里有幾個人在玩20問題游戲，游戲規(guī)則是一個設(shè)迷者在紙牌中抽出一個目標(biāo)（可以是人，也可以是物），而猜謎者可以提問題，設(shè)迷者只能回答是或者不是，在幾個問題（最多二十個問題）之后，猜謎者通過逐步縮小范圍就準(zhǔn)確的找到了答案。這就類似于決策樹的工作原理。（圖一）是一個判斷郵件類別的工作方式，可以看出判別方法很簡單，基本都是閾值判斷，關(guān)鍵是如何構(gòu)建決策樹，也就是如何訓(xùn)練一個決策樹。

（圖一）

構(gòu)建決策樹的偽代碼如下：

Check if every item in the dataset is in the same class:    If so return the class label    Else       find the best feature to split the data       split the dataset        create a branch node       for each split          call create Branch and add the result to the branch node      return branch node

         原則只有一個，盡量使得每個節(jié)點的樣本標(biāo)簽盡可能少，注意上面?zhèn)未a中一句說：find the best feature to split the data，那么如何find thebest feature?一般有個準(zhǔn)則就是盡量使得分支之后節(jié)點的類別純一些，也就是分的準(zhǔn)確一些。如（圖二）中所示，從海洋中撈取的5個動物，我們要判斷他們是否是魚，先用哪個特征？

（圖二）

         為了提高識別精度，我們是先用“離開陸地能否存活”還是“是否有蹼”來判斷？我們必須要有一個衡量準(zhǔn)則，常用的有信息論、基尼純度等，這里使用前者。我們的目標(biāo)就是選擇使得分割后數(shù)據(jù)集的標(biāo)簽信息增益最大的那個特征，信息增益就是原始數(shù)據(jù)集標(biāo)簽基熵減去分割后的數(shù)據(jù)集標(biāo)簽熵，換句話說，信息增益大就是熵變小，使得數(shù)據(jù)集更有序。熵的計算如（公式一）所示：

有了指導(dǎo)原則，那就進(jìn)入代碼實戰(zhàn)階段，先來看看熵的計算代碼：

def calcShannonEnt(dataSet):   numEntries = len(dataSet)   labelCounts = {}   for featVec in dataSet: #the the number of unique elements and their occurance     currentLabel = featVec[-1]     if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0     labelCounts[currentLabel] += 1 #收集所有類別的數(shù)目，創(chuàng)建字典   shannonEnt = 0.0   for key in labelCounts:     prob = float(labelCounts[key])/numEntries     shannonEnt -= prob * log(prob,2) #log base 2 計算熵   return shannonEnt