決策樹模型與學習
決策樹模型
分類決策樹模型是一種描述對實例進行分類的樹形結構。決策樹由結點和有向邊組成。結點有兩種類型：內部節(jié)點和葉節(jié)點，內部節(jié)點表示一個特征或屬性，葉節(jié)點表示一個類。
分類的時候，從根節(jié)點開始，當前節(jié)點設為根節(jié)點，當前節(jié)點必定是一種特征，根據(jù)實例的該特征的取值，向下移動，直到到達葉節(jié)點，將實例分到葉節(jié)點對應的類中。
決策樹與if-then規(guī)則
決策樹的屬性結構其實對應著一個規(guī)則集合：由決策樹的根節(jié)點到葉節(jié)點的每條路徑構成的規(guī)則組成；路徑上的內部特征對應著if條件，葉節(jié)點對應著then結論。決策樹和規(guī)則集合是等效的，都具有一個重要的性質：互斥且完備。也就是說任何實例都被且僅被一條路徑或規(guī)則覆蓋。
決策樹與條件概率分布
決策樹還是給定特征條件下類的條件概率分布的一種退化表示（非等效，個人理解）。該條件分布定義在特征空間的劃分上，特征空間被花費為互不相交的單元，每個單元定義一個類的概率分布就構成了一個條件概率分布。決策樹的每條路徑對應于劃分中的一個單元。給定實例的特征X，一定落入某個劃分，決策樹選取該劃分里最大概率的類作為結果輸出。如圖：
關于b圖，我是這么理解的，將a圖的基礎上增加一個條件概率的維度P，代表在當前特征X的情況下，分類為+的后驗概率。圖中的方塊有些地方完全沒有，比如x2軸上[a2,1]這個區(qū)間，說明只要X落在這里，Y就一定是-的，同理對于[0,a1]和[0,a2]圍起來的一定是+的。有些地方只有一半，比如x1軸上[a1,1]這個區(qū)間，說明決策樹認為X落在這里，Y只有一半概率是+的，根據(jù)選擇條件概率大的類別的原則，就認為Y是-的（因為不滿足P(+)>0.5)。
決策樹學習
決策樹學習算法包含特征選擇、決策樹的生成與剪枝過程。決策樹的學習算法一般是遞歸地選擇最優(yōu)特征，并用最優(yōu)特征對數(shù)據(jù)集進行分割。開始時，構建根節(jié)點，選擇最優(yōu)特征，該特征有幾種值就分割為幾個子集，每個子集分別遞歸調用此方法，返回節(jié)點，返回的節(jié)點就是上一層的子節(jié)點。直到數(shù)據(jù)集為空，或者數(shù)據(jù)集只有一維特征為止。
基本骨架的Python實現(xiàn)：
def majorityCnt(classList):
"""
返回出現(xiàn)次數(shù)最多的分類名稱
:param classList: 類列表
:return: 出現(xiàn)次數(shù)最多的類名稱
"""
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, chooseBestFeatureToSplitFunc=chooseBestFeatureToSplitByID3):
"""
創(chuàng)建決策樹
:param dataSet:數(shù)據(jù)集
:param labels:數(shù)據(jù)集每一維的名稱
:return:決策樹
"""
classList = [example[-1] for example in dataSet] # 類別列表
if classList.count(classList[0]) == len(classList):
return classList[0] # 當類別完全相同則停止繼續(xù)劃分
if len(dataSet[0]) == 1: # 當只有一個特征的時候，遍歷完所有實例返回出現(xiàn)次數(shù)最多的類別
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplitFunc(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
由于決策樹表示條件概率分布，所以高度不同的決策樹對應不同復雜度的概率模型。最優(yōu)決策樹的生成是個NP問題，能實現(xiàn)的生成算法都是局部最優(yōu)的，剪枝則是既定決策樹下的全局最優(yōu)。
特征選擇
特征選擇
樣本通常有很多維特征，希望選擇具有分類能力的特征。比如下表：
可以用Python建立數(shù)據(jù)集：
def createDataSet():
"""
創(chuàng)建數(shù)據(jù)集
:return:
"""
dataSet = [[u'青年', u'否', u'否', u'一般', u'拒絕'],
[u'青年', u'否', u'否', u'好', u'拒絕'],
[u'青年', u'是', u'否', u'好', u'同意'],
[u'青年', u'是', u'是', u'一般', u'同意'],
[u'青年', u'否', u'否', u'一般', u'拒絕'],
[u'中年', u'否', u'否', u'一般', u'拒絕'],
[u'中年', u'否', u'否', u'好', u'拒絕'],
[u'中年', u'是', u'是', u'好', u'同意'],
[u'中年', u'否', u'是', u'非常好', u'同意'],
[u'中年', u'否', u'是', u'非常好', u'同意'],
[u'老年', u'否', u'是', u'非常好', u'同意'],
[u'老年', u'否', u'是', u'好', u'同意'],
[u'老年', u'是', u'否', u'好', u'同意'],
[u'老年', u'是', u'否', u'非常好', u'同意'],
[u'老年', u'否', u'否', u'一般', u'拒絕'],
]
labels = [u'年齡', u'有工作', u'有房子', u'信貸情況']
# 返回數(shù)據(jù)集和每個維度的名稱
return dataSet, labels
也可以根據(jù)特征分割數(shù)據(jù)集：
def splitDataSet(dataSet, axis, value):
"""
按照給定特征劃分數(shù)據(jù)集
:param dataSet: 待劃分的數(shù)據(jù)集
:param axis: 劃分數(shù)據(jù)集的特征的維度
:param value: 特征的值
:return: 符合該特征的所有實例（并且自動移除掉這維特征）
"""
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis] # 刪掉這一維特征
reducedFeatVec.extend(featVec[axis + 1:])
retDataSet.append(reducedFeatVec)
return retDataSet
如何判斷一個特征的分類能力呢？
信息增益
先得介紹熵，應該算是NLP和ML的老相好了：
對于一個可能有n種取值的隨機變量：
其熵為：
另外，0log0=0。當對數(shù)的底為2時，熵的單位為bit，為e時，單位為nat。
用Python實現(xiàn)信息熵（香農熵）：
def calcShannonEnt(dataSet):
"""
計算訓練數(shù)據(jù)集中的Y隨機變量的香農熵
:param dataSet:
:return:
"""
numEntries = len(dataSet) # 實例的個數(shù)
labelCounts = {}
for featVec in dataSet: # 遍歷每個實例，統(tǒng)計標簽的頻次
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
由定義值，X的熵與X的值無關，只與分布有關，所以也可以將X的熵記作H(p)，即:
熵其實就是X的不確定性，從定義可驗證：
設有隨機變量(X,Y)，其聯(lián)合分布為：
條件熵H(Y|X)表示在已知隨機變量X的條件下隨機變量Y的不確定性，定義為在X給定的條件下，Y的條件概率分布對X的數(shù)學期望：
這里，
當上述定義式中的概率由數(shù)據(jù)估計（比如上一章提到的極大似然估計）得到時，所對應的熵和條件熵分別稱為經驗熵和經驗條件熵。
Python實現(xiàn)條件熵的計算
def calcConditionalEntropy(dataSet, i, featList, uniqueVals):
'''
計算X_i給定的條件下，Y的條件熵
:param dataSet:數(shù)據(jù)集
:param i:維度i
:param featList: 數(shù)據(jù)集特征列表
:param uniqueVals: 數(shù)據(jù)集特征集合
:return:條件熵
'''
ce = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet) / float(len(dataSet)) # 極大似然估計概率
ce += prob * calcShannonEnt(subDataSet) # ∑pH(Y|X=xi) 條件熵的計算
return ce
有了上述知識，就可以一句話說明什么叫信息增益了：信息增益表示得知特征X的信息而使類Y的信息的熵減少的程度。形式化的定義如下：
這個差又稱為互信息（關于互信息的一個應用：《基于互信息和左右信息熵的短語提取識別》），決策樹學習中的信息增益等價于訓練數(shù)據(jù)集中類與特征的互信息。
用Python計算信息增益：
def calcInformationGain(dataSet, baseEntropy, i):
"""
計算信息增益
:param dataSet:數(shù)據(jù)集
:param baseEntropy:數(shù)據(jù)集中Y的信息熵
:param i: 特征維度i
:return: 特征i對數(shù)據(jù)集的信息增益g(dataSet|X_i)
"""
featList = [example[i] for example in dataSet] # 第i維特征列表
uniqueVals = set(featList) # 轉換成集合
newEntropy = calcConditionalEntropy(dataSet, i, featList, uniqueVals)
infoGain = baseEntropy - newEntropy # 信息增益，就是熵的減少，也就是不確定性的減少
return infoGain
回到最初的問題，如何判斷一個特征的分類能力呢？信息增益大的特征具有更強的分類能力。只要計算出各個特征的信息增益，找出最大的那一個就行。形式化的描述如下：
信息增益比
這種算法有個缺點，信息增益的值是相對于訓練數(shù)據(jù)集而言的，當H(D)大的時候，信息增益值往往會偏大，這樣對H(D)小的特征不公平。改進的方法是信息增益比：
注：上述公式分母應該是特征A的 split information value ：
參考http://www.inf.unibz.it/dis/teaching/DWDM/slides2011/lesson5-Classification-2.pdf
由于《統(tǒng)計學習方法》是我看的第一本機器學習書籍，所以無法對其中錯誤做出全面的勘誤，請帶著質疑的精神閱讀，謝謝。
Python代碼：
def calcInformationGainRate(dataSet, baseEntropy, i):
"""
計算信息增益比
:param dataSet:數(shù)據(jù)集
:param baseEntropy:數(shù)據(jù)集中Y的信息熵
:param i: 特征維度i
:return: 特征i對數(shù)據(jù)集的信息增益g(dataSet|X_i)
"""
return calcInformationGain(dataSet, baseEntropy, i) / baseEntropy
決策樹的生成
ID3算法
從根節(jié)點開始，計算所有可能的特征的信息增益，選擇信息增益最大的特征作為當前節(jié)點的特征，由特征的不同取值建立空白子節(jié)點，對空白子節(jié)點遞歸調用此方法，直到所有特征的信息增益小于閥值或者沒有特征可選為止。
形式化的描述參考P63，我上面的描述應該很好懂了，老是截圖沒意思。
Python實現(xiàn)
還是直接上代碼比較痛快。
ID3特征選擇算法的Python實現(xiàn)：
def chooseBestFeatureToSplitByID3(dataSet):
"""
選擇最好的數(shù)據(jù)集劃分方式
:param dataSet:
:return:
"""
numFeatures = len(dataSet[0]) - 1 # 最后一列是分類
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeature = -1
for i in range(numFeatures): # 遍歷所有維度特征
infoGain = calcInformationGain(dataSet, baseEntropy, i)
if (infoGain > bestInfoGain): # 選擇最大的信息增益
bestInfoGain = infoGain
bestFeature = i
return bestFeature # 返回最佳特征對應的維度
完整調用
# -*- coding:utf-8 -*-
# Filename: testTree.py
# Author：hankcs
# Date: 2014-04-19 下午9:19
###########中文支持################
import sys
from tree import *
reload(sys)
sys.setdefaultencoding('utf-8')
from pylab import *
mpl.rcParams['font.sans-serif'] = ['SimHei'] # 指定默認字體
mpl.rcParams['axes.unicode_minus'] = False # 解決保存圖像時負號'-'顯示為方塊的問題
##################################
# 測試決策樹的構建
myDat, labels = createDataSet()
myTree = createTree(myDat, labels)
# 繪制決策樹
import treePlotter
treePlotter.createPlot(myTree)
此處的可視化使用了《Machine Learning in Action》中的代碼：
# -*- coding:utf-8 -*-
# Filename: treePlotter.py
# Author：hankcs
# Date: 2015/2/9 21:24
import matplotlib.pyplot as plt
# 定義文本框和箭頭格式
decisionNode = dict(boxstyle="round4", color='#3366FF') #定義判斷結點形態(tài)
leafNode = dict(boxstyle="circle", color='#FF6633') #定義葉結點形態(tài)
arrow_args = dict(arrowstyle="<-", color='g') #定義箭頭
#繪制帶箭頭的注釋
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
xytext=centerPt, textcoords='axes fraction',
va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)
#計算葉結點數(shù)
def getNumLeafs(myTree):
numLeafs = 0
firstStr = myTree.keys()[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
numLeafs += getNumLeafs(secondDict[key])
else:
numLeafs += 1
return numLeafs
#計算樹的層數(shù)
def getTreeDepth(myTree):
maxDepth = 0
firstStr = myTree.keys()[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
thisDepth = 1 + getTreeDepth(secondDict[key])
else:
thisDepth = 1
if thisDepth > maxDepth:
maxDepth = thisDepth
return maxDepth
#在父子結點間填充文本信息
def plotMidText(cntrPt, parentPt, txtString):
xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0]
yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]
createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)
def plotTree(myTree, parentPt, nodeTxt):
numLeafs = getNumLeafs(myTree)
depth = getTreeDepth(myTree)
firstStr = myTree.keys()[0]
cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)
plotMidText(cntrPt, parentPt, nodeTxt) #在父子結點間填充文本信息
plotNode(firstStr, cntrPt, parentPt, decisionNode) #繪制帶箭頭的注釋
secondDict = myTree[firstStr]
plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict':
plotTree(secondDict[key], cntrPt, str(key))
else:
plotTree.xOff = plotTree.xOff + 1.0 / plotTree.totalW
plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD
def createPlot(inTree):
fig = plt.figure(1, facecolor='white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
plotTree.totalW = float(getNumLeafs(inTree))
plotTree.totalD = float(getTreeDepth(inTree))
plotTree.xOff = -0.5 / plotTree.totalW;
plotTree.yOff = 1.0;
plotTree(inTree, (0.5, 1.0), '')
plt.show()
python實現(xiàn)
def chooseBestFeatureToSplitByC45(dataSet):
"""
選擇最好的數(shù)據(jù)集劃分方式
:param dataSet:
:return:
"""
numFeatures = len(dataSet[0]) - 1 # 最后一列是分類
baseEntropy = calcShannonEnt(dataSet)
bestInfoGainRate = 0.0
bestFeature = -1
for i in range(numFeatures): # 遍歷所有維度特征
infoGainRate = calcInformationGainRate(dataSet, baseEntropy, i)
if (infoGainRate > bestInfoGainRate): # 選擇最大的信息增益
bestInfoGainRate = infoGainRate
bestFeature = i
return bestFeature # 返回最佳特征對應的維度
調用方法只需加個參數(shù)：
myTree = createTree(myDat, labels, chooseBestFeatureToSplitByC45)
可視化
并沒有變化。
決策樹的剪枝
決策樹很容易發(fā)生過擬合，過擬合的原因在于學習的時候過多地考慮如何提高對訓練數(shù)據(jù)的正確分類，從而構建出過于復雜的決策樹。解決這個問題的辦法就是簡化已生成的決策樹，也就是剪枝。
決策樹的剪枝往往通過極小化決策樹整體的損失函數(shù)或代價函數(shù)來實現(xiàn)。
設決策樹T的葉節(jié)點有|T|個，t是某個葉節(jié)點，t有Nt個樣本點，其中歸入k類的樣本點有Ntk個，Ht(T)為葉節(jié)點t上的經驗熵，α≥0為參數(shù)，則損失函數(shù)可以定義為：
其中經驗熵Ht(T)為：
表示葉節(jié)點t所代表的類別的不確定性。損失函數(shù)對它求和表示所有被導向該葉節(jié)點的樣本點所帶來的不確定的和的和。我沒有多打一個“的和”，第二個是針對葉節(jié)點t說的。
在損失函數(shù)中，將右邊第一項記作：
則損失函數(shù)可以簡單記作：
C(T)表示模型對訓練數(shù)據(jù)的預測誤差，即模型與訓練數(shù)據(jù)的擬合程度，|T|表示模型復雜度，參數(shù)α≥0控制兩者之間的影響，α越大，模型越簡單，α=0表示不考慮復雜度。
剪枝，就是當α確定時，選擇損失函數(shù)最小的模型。子樹越大C(T)越小，但是α|T|越大，損失函數(shù)反映的是兩者的平衡。
決策樹的生成過程只考慮了信息增益或信息增益比，只考慮更好地擬合訓練數(shù)據(jù)，而剪枝過程則考慮了減小復雜度。前者是局部學習，后者是整體學習。
樹的剪枝算法
從每個葉節(jié)點往上走，走了后如果損失函數(shù)減小了，則減掉葉節(jié)點，將父節(jié)點作為葉節(jié)點。如圖：
說是這么說，實際上如果葉節(jié)點有多個，那么父節(jié)點變成葉節(jié)點后，新葉節(jié)點到底應該選擇原來的葉節(jié)點中的哪一種類別呢？大概又是多數(shù)表決吧，原著并沒有深入展開。
CART算法
分類與回歸樹（CART）模型同樣由特征選取、樹的生成和剪枝組成，既可以用于分類也可以用于回歸。CART假設決策樹是二叉樹，內部節(jié)點特征的取值為是和否，對應一個實例的特征是否是這樣的。決策樹遞歸地二分每個特征，將輸入空間劃分為有限個單元。
CART生成
就是遞歸地構建二叉決策樹的過程。對回歸樹用平方誤差最小化準則，對分類樹用基尼指數(shù)最小化準則，進行特征選取，生成二叉樹。
1、回歸樹
回歸樹與分類樹在數(shù)據(jù)集上的不同就是數(shù)據(jù)集的輸出部分不是類別，而是連續(xù)變量。
假設輸入空間已經被分為M個單元
，分別對應輸出值cm，于是回歸樹模型可以表示為：
回歸樹的預測誤差：
那么輸出值就是使上面誤差最小的值，也就是均值：
難點在于怎么劃分，一種啟發(fā)式的方法（其實就是暴力搜索吧）：
遍歷所有輸入變量，選擇第j個變量和它的值s作為切分變量和切分點，將空間分為兩個區(qū)域：
然后計算兩個區(qū)域的平方誤差，求和，極小化這個和，具體的，就是：
當j最優(yōu)化的時候，就可以將切分點最優(yōu)化：
遞歸調用此過程，這種回歸樹通常稱為最小二乘回歸樹。
2、分類樹
與回歸樹算法流程類似，只不過選擇的是最優(yōu)切分特征和最優(yōu)切分點，并采用基尼指數(shù)衡量?；嶂笖?shù)定義：
對于給定數(shù)據(jù)集D，其基尼指數(shù)是：
Ck是屬于第k類的樣本子集，K是類的個數(shù)。Gini(D)反應的是D的不確定性（與熵類似），分區(qū)的目標就是降低不確定性。
D根據(jù)特征A是否取某一個可能值a而分為D1和D2兩部分：
則在特征A的條件下，D的基尼指數(shù)是：
有了上述知識儲備，可以給出CART生成算法的偽碼：
設節(jié)點的當前數(shù)據(jù)集為D，對D中每一個特征A，對齊每個值a根據(jù)D中樣本點是否滿足A==a分為兩部分，計算基尼指數(shù)。對所有基尼指數(shù)選擇最小的，對應的特征和切分點作為最優(yōu)特征和最優(yōu)切分點，生成兩個子節(jié)點，將對應的兩個分區(qū)分配過去，然后對兩個子節(jié)點遞歸。
CART剪枝
在上面介紹的損失函數(shù)中，當α固定時，一定存在使得損失函數(shù)最小的子樹，記為復雜度=Tα，α偏大Tα就偏小。設對α遞增的序列，對應的最優(yōu)子樹序列為Tn，子樹序列第一棵包含第二棵，依次類推。
從T0開始剪枝，對它內部的任意節(jié)點t，只有t這一個節(jié)點的子樹的損失函數(shù)是：
以t為根節(jié)點的子樹的損失函數(shù)是：
當α充分小，肯定有
這個不等式的意思是復雜模型在復雜度影響力小的情況下?lián)p失函數(shù)更小。
當α增大到某一點，這個不等式的符號會反過來。
只要
，損失函數(shù)值就相同，但是t更小啊，所以t更可取，于是把Tt剪枝掉。
為此，對每一個t，計算
表示損失函數(shù)的減少程度，從T中剪枝掉g(t)最小的Tt，取新的α=g(t)，直到根節(jié)點。這樣就得到了一個子樹序列，對此序列，應用獨立的驗證數(shù)據(jù)集交叉驗證，選取最優(yōu)子樹，剪枝完畢。
