最近微信朋友圈很多人在轉發的一個游戲叫做“微軟小冰讀心術”，游戲的規則很簡單：參與游戲的一方在腦海里想好一個人的名字，然后微軟小冰會問你15個問題，問題的答案只能用“是”、“不是”或者“不知道”回答。
微軟小冰通過你的回答進行推斷分解，逐步縮小待猜測人名的范圍，決策樹的工作原理與這些問題類似，用戶輸入一系列數據，然后會給出游戲的答案。
###一、決策樹簡介
決策樹（decision tree）是機器學習與數據挖掘中一種十分常用的分類和回歸方法，屬于有監督學習（supervised learning）算法。通俗來說，決策樹分類的思想類似于找對象。現在想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：
女兒：多大年紀了？
母親：26。
女兒：長的帥不帥？
母親：挺帥的。
女兒：收入高不？
母親：不算很高，中等情況。
女兒：是公務員不？
母親：是，在稅務局上班呢。
女兒：那好，我去見見。
這個女孩的決策過程就是典型的決策樹方法。相當于通過年齡、長相、收入和是否公務員對將男人分為兩個類別：見和不見。假設這個女孩對男人的要求是：30歲以下、長相中等以上并且是高收入者或中等以上收入的公務員，那么這個可以用下圖表示女孩的決策邏輯：
決策樹是一種樹型結構，其中每個內部結點表示在一個屬性上的測試，每個分支代表一個測試輸出，每個葉結點代表一個類別。
決策樹學習是以實例為基礎的歸納學習，決策樹學習采用的是自頂向下的遞歸方法，其基本思想是以信息熵為度量構造一棵熵值（熵的概念請參考信息論的書籍）下降最快的樹，到葉子結點處的熵值為零，此時，每個葉結點中的實例都屬于同一類。
###二、決策樹的構造
1.創建分支
創建分支的偽代碼函數createBranch()如下所示：
檢測數據集中的每一個子項是否屬于同一類；
If so return 類標簽；
Else
? ? 尋找劃分數據集的最好特征；
? ? 劃分數據集；
? ? 創建分支結點；
? ? ? ? for 每個劃分的子集
? ? ? ? ? ? 調用函數createBranch()并增加返回結果到分支結點中
? ? ?return 分支結點；
上面的偽代碼createBranch()是一個遞歸函數，在倒數第二行直接調用了它本身。
上表的數據包含5個海洋生物，特征包括：不浮出水面是否可以生存，以及是否有腳蹼。
我們可以將這些生物分成兩類：魚類和非魚類，現在我們想要決定依據第一個特征還是第二個特征來劃分數據。
在討論這個問題前，我們先了解決策樹算法中的一些信息論概念：
1.信息量
定義事件X發生的信息量為：
某事件發生的概率越小，則該事件的信息量越大，一定發生和一定不會發生的必然事件的信息量為0。
例如，今天是22號，別人說明天是23號，這就沒有一點信息量。
2.信息熵
信息熵是信息量的期望，定義為：
其中p(x)是，事件x發生的概率。信息熵一般用來表征事件或變量的不確定性，變量的不確定性越大，信息熵就越大。一個系統越有序，它的信息熵就越小，反之，一個混亂的系統信息熵越大，所以信息熵是系統有序化程度的一個度量。
3.聯合熵和條件熵
兩個隨機變量X、Y的聯合分布形成聯合熵H(X,Y)，已知Y發生的前提下，X的熵叫做條件熵H(X|Y)。
4.互信息兩個隨機變量X、Y的互信息定義為X、Y的信息熵減去X、Y的聯合熵。
5.信息增益
信息熵又稱為先驗熵，是在信息發送前信息量的數學期望，后驗熵是指信息發送后，從信宿（即信息的接收者）角度對信息量的數學期望。一般先驗熵大于后驗熵，先驗熵與后驗熵的差就是信息增益，反映的是信息消除隨機不確定性的程度。
決策樹學習中的信息增益等價于訓練集中類別與特征的互信息。
信息增益表示得知特征A的信息而使得類X的信息的不確定性減少的程度。
劃分數據集的最大原則是：將無序的數據變得更加有序。劃分數據集前后信息發送的變化就行信息增益，通過計算每個特征值劃分數據集獲得的信息增益，我們就可以根據獲得信息增益最高的特征來選擇其作為劃分數據的特征。
信息增益的計算方法：
（1）計算給定數據集的信息熵
~~~
from math import log
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
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob * log(prob,2) #log base 2
return shannonEnt
~~~
代碼解析：首先，計算數據集中實例的總數numEntries，然后創建一個字典，它的鍵值是最后一列的數值，如果當前鍵值不存在，則擴展字典并將當前鍵值加入字典，每個鍵值都記錄了當前類別出現的次數labelCounts，最后，使用所有類別標簽的發生頻率計算類別出現的概率。
（2）創建數據集
利用createDataSet（）函數得到表3-1所示的簡單魚鑒定數據集：
~~~
def createDataSet():
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
labels = ['no surfacing','flippers']
#change to discrete values
return dataSet, labels
~~~
（3）劃分數據集
對每個特征劃分數據集的結果計算一次信息熵，然后判斷按照哪個特征劃分數據集是最后的劃分方式。
~~~
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis] #chop out axis used for splitting
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
~~~
代碼解析：spiltDataSet()的三個輸入參數分別是待劃分數據集dataSet、劃分數據集的特征axis、需要返回的特征的值。遍歷數據集中的每個元素，一旦發現符合要求的值，則將其添加到新創建的列表中。
選擇最好的數據集劃分方式：
~~~
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 #the last column is used for the labels
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0; bestFeature = -1
for i in range(numFeatures): #iterate over all the features
featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
uniqueVals = set(featList) #get a set of unique values
newEntropy = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy #calculate the info gain; ie reduction in entropy
if (infoGain > bestInfoGain): #compare this to the best gain so far
bestInfoGain = infoGain #if better than current best, set to best
bestFeature = i
return bestFeature #returns an integer
~~~
代碼運行結果告訴我們，第0個特征是最好的用于劃分數據集的特征。數據集的數據來源于表3-1，
如果我們按照第一個特征屬性劃分數據，也就是說第一個特征為1的放在一組，第一個特征是0的放在另一個組，按照這種方式劃分的話，第一個特征為1的海洋生物分組將有兩個屬于魚類，一個屬于非魚類；另一個分組則全部屬于非魚類。
如果我們按照第二個特征分組，第一個海洋生物分組將有兩個屬于魚類，兩個屬于非魚類；另一個分組則只有一個非魚類。
可以看出，第一種劃分很好地處理了相關數據。
（4）遞歸構建決策樹
~~~
def majorityCnt(classList):
classCount={}
for vote in classList:
if vote not in classCount.keys(): classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
~~~
創建決策樹的函數代碼：
~~~
def createTree(dataSet,labels):
classList = [example[-1] for example in dataSet]
if classList.count(classList[0]) == len(classList):
return classList[0]#stop splitting when all of the classes are equal
if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:] #copy all of labels, so trees don't mess up existing labels
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
return myTree
~~~
###三、決策樹的過擬合
決策樹對訓練屬于有很好的分類能力，但對未知的預測數據未必有好的分類能力，泛化能力較弱，即可能發生過擬合現象。
解決過擬合的方法：
1.剪枝
2.隨機森林
