前言
生活中有很多利用決策樹的例子。西瓜書上給的例子是西瓜問題（講到這突然想到書中不少西瓜的例子，難道這就是它西瓜封面的由來？）\。大緻意思是，已經有一堆已知好瓜壞瓜的西瓜，每次挑取西瓜的一條屬性，将西瓜進行分類。然後在分類的西瓜中，繼續挑取下一條屬性進行更加細緻的劃分，直到所有的屬性被用完。
這個例子有一個隐含的前提，就是給出所有的屬性，它唯一地決定西瓜的好壞。意思是，不存在兩個都是好瓜的瓜，或者都是壞瓜的瓜，它們的所有屬性都相同。這有點類似資料庫中的實體完整性。這樣，你才能通過建構的決策樹，按照它的用來分類的屬性的順序，每次前進一個分支，直到最後一層就能知道待測西瓜是否是好瓜。
但是如果由許多瓜，有好瓜也有壞瓜，他們的屬性都相同的時候，就意味着你沿決策樹到達葉子節點的時候，面臨多種選擇。這時候，可以選擇出現次數最多的瓜種作為結果傳回。
（這是用手機從西瓜書上拍下來的。結果上傳的時候才發現忘記設定照片大小了，2M）
決策樹的最關鍵的問題是，如何選擇劃分屬性的順序才能使得決策樹的平均性能最好（即平均在樹上走最少的路徑就可以知道結果）。比如說，如果觸感就能夠唯一決定一個瓜是否是好壞，但是觸感确實放在最後進行劃分的，那麼前面走的所有步驟都是多餘的。如果一開始就用觸感來進行劃分，那麼隻需要走一步，就能夠知道西瓜是否是好瓜。
下面來解釋一個概念，它能夠決定用何種屬性進行劃分。
熵
劃分資料集最大的原則就是：将無序的資料變得更加有序。我們選取的是，能夠将資料劃分得“最有序”的屬性。換句話說，選取能夠給出最多資訊的屬性進行劃分。打個比方，我要判斷一個蚊子是否是母蚊子，你首先告訴我它有翅膀。可是所有的蚊子都有翅膀，這對我進行分類毫無意義，就稱“有無翅膀”這一屬性完全沒有給出任何資訊。如果你告訴我它經常在你身邊上下騰飛騷擾你，那麼我能夠給出八成的可能說它是母蚊子，就說它給出了部分資訊。你如果告訴我它會吸血，那母蚊子沒跑了。“會不會吸血”這一屬性給出了決定性的資訊。
熵（Entropy）定義為資訊的期望值，它在實體學上表示物質的混亂程度。在資訊學上可以作類比。熵增加，表示資訊更加混亂，熵減，表示資訊更加有序。假設劃分之前，這堆西瓜的熵是$Ent(D)$，按照某種屬性劃分之後這堆西瓜的熵是$Ent(D\')$，注意後者一定小于等于前者。否則劃分就沒有任何意義。這兩者的差，就是這個屬性對于這堆西瓜有序化的貢獻。下面說明熵的計算方法：
假設樣本集$D$中，第$k$類樣本所占的比例為$p_k$,那麼$D$的熵：
$Ent(D) = - \Sigma p_klog_2p_k$
這裡約定$p_k = 0$時，$p_klog_2p_k = 0$。當這樣本集被某個屬性劃分成$v$份之後，熵就是所有子集的熵的和：
$Ent(D\') = -\Sigma Ent(D^i) \ \ ,i = [1,...,v]$
但是，每個樣本子集中劃分到的樣本數量不一樣，需要對每個子集的熵進行權重：
$Ent(D\') = -\Sigma \frac{|D^i|}{|D|}Ent(D^i) \ \ ,i = [1,...,v]$
于是熵增就定義為
$Gain(D,a) = Ent(D) - Ent(D\') = Ent(D) - \Sigma \frac{|D^i|}{|D|}Ent(D^i) \ \ ,i = [1,...,v]$
表示，按照屬性a對D進行劃分熵的增益。顯然，增益越大，表示越應該提前使用該屬性進行劃分。
下面給出計算熵增的python2.x 代碼
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
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)
return shannonEnt 這裡的dataSet，由多個向量組成，每個向量代表一個樣本。這裡的向量的最後一個元素代表該樣本的類别。這不同于之前的KNN算法。KNN的類别和屬性是分開表示的。
第一個for循環計算每個類别的機率。第二個for循環計算熵。
決策樹完整算法
輸入：樣本集D，每個樣本包含他們的屬性（值）和類别。
輸出：決策樹
算法描述：
- 選擇一個最好的劃分屬性
- 用最好的屬性劃分D，并從屬性清單中删除該屬性。
- 對每個子集，如果屬性已經用完，傳回類别标簽。否則對每個子集，重複1步驟。
python2.x 代碼實作
# 使用坐标為axis的屬性劃分dataSet，将該屬性的值等于value的樣本傳回。并且從樣本中删除該屬性
def splitDataSet(dataSet,axis,value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
# 選擇最好的劃分屬性，它傳回的是屬性在屬性向量中的位置（坐标）
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
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
if(infoGain>bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature
# dataSet 中的向量包含了屬性和類别
def createTree(dataSet,labels):
# 取所有的類别
classList = [example[-1] for example in dataSet]
# 如果所有的類别都相同，就傳回
if classList.count(classList[0]) == len(classList):
return classList[0]
# 如果dataSet中已經沒有屬性了，表示所有的屬性已經被周遊完，就傳回出現次數最多的屬性
if len(dataSet[0] == 1):
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[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
return myTree
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] 這裡的決策樹用的是python的字典嵌套來表示。字典每一層的key由屬性名和屬性值交替，如果這一層的key是屬性名，表示由該屬性名進行劃分，下一層的字典就是該屬性的所有可能的取值。然後每一個對于每一個取值，再選一個屬性名。如果沒有屬性名可選，最終的字典就是類别。具體的含義可以參考這篇部落格：python中字典{}的嵌套。他裡面用的例子剛好是這篇機器學習的代碼。
最後一個函數是為了解決葉子節點有多種結果情況。選擇出現次數最多的結果傳回。函數createTree中第二個參數labels是屬性的名稱，一般類型是字元串，比如‘色澤’，‘外觀’，‘觸感’之類的。而第一個參數dataSet中的屬性是屬性的值。
其他
上述代碼中構造的決策樹是一個嵌套字典。具體如何使用，其實就是下标索引，在上面給出的部落格中也有講。
決策樹的建構過程耗時比較長，但是建構好之後測試樣本就很快。他不同于上一篇的KNN，KNN每次需要測試樣本的時候，都需要重新訓練一次，即‘懶惰學習’。決策樹隻有在拿到新的訓練樣本的時候才需要訓練，以後需要測試樣本都可以調用已經建構好的決策樹，即‘急切學習’。關于建構出來的用嵌套字典表示的決策樹如何繪制出來和存儲，在《機器學習實戰》裡面也有詳細提到，分别用matplotlib和pickle庫。因為我這兩個都不會用，python也是先學不到兩周，還需要學習，是以就不搬運了。如果什麼時候覺得這非常需要作篇部落格以表學習，那到時就另起一篇，放在python分類中。
增益率
西瓜書還提到這個概念。
是想，如果把訓練樣本的每一個樣本都作編号，然後把編号也作為屬性參與決策。通過計算，編号産生的資訊熵增益達到0.998，遠高于其他屬性。這很好了解：每一個編号都産生一個分支，每個分支僅僅包含一個樣本，這樣就完全不需要考慮其他屬性了。然而，這樣的決策樹并不具有泛化能力，無法對新樣本做出有效預測。
資訊增益準則對取值數目多的屬性有偏好。意思是，一個屬性的取值越多，越有可能被選為目前最好的劃分屬性。為了解決這種偏好帶來的不利映像，著名的C4.5決策樹算法不直接使用資訊增益，而是使用“增益率”來選擇最優劃分屬性。增益率定義為：
$Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$
其中
$IV(a) = -\Sigma \frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$
$IV(a)$稱為屬性a的“固有值”。屬性a的可能取值越多，固有值越大，增益率越小。可以看到，原本的資訊增益使用屬性的固有值進行了權重，消除了原本算法對取值數目多的屬性的偏好帶來的影響。
西瓜書上還有一段：
需要注意的是，增益率準則對可取值數目較少的屬性有所偏好，是以，C4.5算法并不是直接選擇增益率最大的候選劃分屬性，而是使用了一個啟發式：先從候選劃分屬性中找出資訊增益高于平均水準的屬性，再從中選擇增益率最高的。