決策樹
決策樹是什么？決策樹(decision tree)是一種基本的分類與回歸方法顿肺。舉個通俗易懂的例子钟鸵，如下圖所示的流程圖就是一個決策樹，長方形代表判斷模塊(decision block)撇眯，橢圓形成代表終止模塊(terminating block)报嵌，表示已經(jīng)得出結(jié)論，可以終止運行熊榛。從判斷模塊引出的左右箭頭稱作為分支(branch)锚国，它可以達到另一個判斷模塊或者終止模塊。我們還可以這樣理解玄坦，分類決策樹模型是一種描述對實例進行分類的樹形結(jié)構(gòu)血筑。決策樹由結(jié)點(node)和有向邊(directed edge)組成。結(jié)點有兩種類型：內(nèi)部結(jié)點(internal node)和葉結(jié)點(leaf node)。內(nèi)部結(jié)點表示一個特征或?qū)傩圆蜃埽~結(jié)點表示一個類梆砸。蒙圈沒？园欣？如下圖所示的決策樹帖世，長方形和橢圓形都是結(jié)點。長方形的結(jié)點屬于內(nèi)部結(jié)點沸枯，橢圓形的結(jié)點屬于葉結(jié)點日矫，從結(jié)點引出的左右箭頭就是有向邊。而最上面的結(jié)點就是決策樹的根結(jié)點(root node)绑榴。這樣哪轿，結(jié)點說法就與模塊說法對應(yīng)上了，理解就好翔怎。
我們回到這個流程圖窃诉，對，你沒看錯赤套，這就是一個假想的相親對象分類系統(tǒng)飘痛。它首先檢測相親對方是否有房。如果有房容握，則對于這個相親對象可以考慮進一步接觸宣脉。如果沒有房，則觀察相親對象是否有上進心剔氏，如果沒有塑猖，直接Say Goodbye，此時可以說："你人很好谈跛，但是我們不合適羊苟。"如果有，則可以把這個相親對象列入候選名單感憾，好聽點叫候選名單蜡励，有點瑕疵地講，那就是備胎吹菱。
不過這只是個簡單的相親對象分類系統(tǒng)巍虫，只是做了簡單的分類彭则。真實情況可能要復(fù)雜得多鳍刷，考慮因素也可以是五花八門。脾氣好嗎俯抖？會做飯嗎输瓜？愿意做家務(wù)嗎？家里幾個孩子？父母是干什么的尤揣？天啊搔啊，我不想再說下去了，想想都可怕北戏。
我們可以把決策樹看成一個if-then規(guī)則的集合负芋，將決策樹轉(zhuǎn)換成if-then規(guī)則的過程是這樣的：由決策樹的根結(jié)點(root node)到葉結(jié)點(leaf node)的每一條路徑構(gòu)建一條規(guī)則；路徑上內(nèi)部結(jié)點的特征對應(yīng)著規(guī)則的條件嗜愈，而葉結(jié)點的類對應(yīng)著規(guī)則的結(jié)論旧蛾。決策樹的路徑或其對應(yīng)的if-then規(guī)則集合具有一個重要的性質(zhì)：互斥并且完備。這就是說蠕嫁，每一個實例都被一條路徑或一條規(guī)則所覆蓋锨天，而且只被一條路徑或一條規(guī)則所覆蓋。這里所覆蓋是指實例的特征與路徑上的特征一致或?qū)嵗凉M足規(guī)則的條件剃毒。
使用決策樹做預(yù)測需要以下過程：
- 收集數(shù)據(jù)：可以使用任何方法病袄。比如想構(gòu)建一個相親系統(tǒng)，我們可以從媒婆那里赘阀，或者通過采訪相親對象獲取數(shù)據(jù)益缠。根據(jù)他們考慮的因素和最終的選擇結(jié)果，就可以得到一些供我們利用的數(shù)據(jù)了基公。
- 準備數(shù)據(jù)：收集完的數(shù)據(jù)左刽，我們要進行整理，將這些所有收集的信息按照一定規(guī)則整理出來酌媒，并排版欠痴，方便我們進行后續(xù)處理。
- 分析數(shù)據(jù)：可以使用任何方法秒咨，決策樹構(gòu)造完成之后喇辽，我們可以檢查決策樹圖形是否符合預(yù)期。
- 訓(xùn)練算法：這個過程也就是構(gòu)造決策樹雨席，同樣也可以說是決策樹學(xué)習(xí)菩咨，就是構(gòu)造一個決策樹的數(shù)據(jù)結(jié)構(gòu)。
- 測試算法：使用經(jīng)驗樹計算錯誤率陡厘。當錯誤率達到了可接收范圍抽米，這個決策樹就可以投放使用了。
- 使用算法：此步驟可以使用適用于任何監(jiān)督學(xué)習(xí)算法糙置，而使用決策樹可以更好地理解數(shù)據(jù)的內(nèi)在含義云茸。
決策樹構(gòu)建的準備工作
使用決策樹做預(yù)測的每一步驟都很重要，數(shù)據(jù)收集不到位谤饭，將會導(dǎo)致沒有足夠的特征讓我們構(gòu)建錯誤率低的決策樹标捺。數(shù)據(jù)特征充足懊纳，但是不知道用哪些特征好，將會導(dǎo)致無法構(gòu)建出分類效果好的決策樹模型亡容。從算法方面看嗤疯，決策樹的構(gòu)建是我們的核心內(nèi)容。
決策樹要如何構(gòu)建呢闺兢？通常茂缚，這一過程可以概括為3個步驟：特征選擇、決策樹的生成和決策樹的修剪屋谭。
1阱佛、特征選擇
特征選擇在于選取對訓(xùn)練數(shù)據(jù)具有分類能力的特征。這樣可以提高決策樹學(xué)習(xí)的效率戴而，如果利用一個特征進行分類的結(jié)果與隨機分類的結(jié)果沒有很大差別凑术，則稱這個特征是沒有分類能力的。經(jīng)驗上扔掉這樣的特征對決策樹學(xué)習(xí)的精度影響不大所意。通常特征選擇的標準是信息增益(information gain)或信息增益比淮逊，為了簡單，本文使用信息增益作為選擇特征的標準扶踊。那么泄鹏，什么是信息增益？在講解信息增益之前秧耗，讓我們看一組實例备籽，貸款申請樣本數(shù)據(jù)表。
希望通過所給的訓(xùn)練數(shù)據(jù)學(xué)習(xí)一個貸款申請的決策樹分井，用于對未來的貸款申請進行分類车猬，即當新的客戶提出貸款申請時，根據(jù)申請人的特征利用決策樹決定是否批準貸款申請尺锚。
特征選擇就是決定用哪個特征來劃分特征空間珠闰。比如，我們通過上述數(shù)據(jù)表得到兩個可能的決策樹瘫辩，分別由兩個不同特征的根結(jié)點構(gòu)成伏嗜。
圖(a)所示的根結(jié)點的特征是年齡，有3個取值伐厌，對應(yīng)于不同的取值有不同的子結(jié)點承绸。圖(b)所示的根節(jié)點的特征是工作，有2個取值挣轨，對應(yīng)于不同的取值有不同的子結(jié)點军熏。兩個決策樹都可以從此延續(xù)下去。問題是：究竟選擇哪個特征更好些刃唐？這就要求確定選擇特征的準則羞迷。直觀上界轩，如果一個特征具有更好的分類能力画饥，或者說衔瓮，按照這一特征將訓(xùn)練數(shù)據(jù)集分割成子集，使得各個子集在當前條件下有最好的分類抖甘，那么就更應(yīng)該選擇這個特征热鞍。信息增益就能夠很好地表示這一直觀的準則。
什么是信息增益呢衔彻？在劃分數(shù)據(jù)集之后信息發(fā)生的變化稱為信息增益薇宠，知道如何計算信息增益，我們就可以計算每個特征值劃分數(shù)據(jù)集獲得的信息增益艰额，獲得信息增益最高的特征就是最好的選擇澄港。
（1）香農(nóng)熵
在可以評測哪個數(shù)據(jù)劃分方式是最好的數(shù)據(jù)劃分之前，我們必須學(xué)習(xí)如何計算信息增益柄沮。集合信息的度量方式稱為香農(nóng)熵或者簡稱為熵(entropy)回梧，這個名字來源于信息論之父克勞德·香農(nóng)。
如果看不明白什么是信息增益和熵祖搓，請不要著急狱意，因為他們自誕生的那一天起，就注定會令世人十分費解拯欧∠甓冢克勞德·香農(nóng)寫完信息論之后，約翰·馮·諾依曼建議使用"熵"這個術(shù)語镐作，因為大家都不知道它是什么意思藏姐。
熵定義為信息的期望值。在信息論與概率統(tǒng)計中该贾，熵是表示隨機變量不確定性的度量包各。如果待分類的事物可能劃分在多個分類之中，則符號xi的信息定義為 ：
其中p(xi)是選擇該分類的概率靶庙。有人可能會問问畅，信息為啥這樣定義啊六荒？答曰：前輩得出的結(jié)論护姆。這就跟1+1等于2一樣，記住并且會用即可掏击。上述式中的對數(shù)以2為底卵皂，也可以e為底(自然對數(shù))。
通過上式砚亭，我們可以得到所有類別的信息灯变。為了計算熵殴玛，我們需要計算所有類別所有可能值包含的信息期望值(數(shù)學(xué)期望)，通過下面的公式得到：
期中n是分類的數(shù)目添祸。熵越大滚粟，隨機變量的不確定性就越大。
當熵中的概率由數(shù)據(jù)估計(特別是最大似然估計)得到時刃泌，所對應(yīng)的熵稱為經(jīng)驗熵(empirical entropy)凡壤。什么叫由數(shù)據(jù)估計？比如有10個數(shù)據(jù)耙替，一共有兩個類別亚侠，A類和B類。其中有7個數(shù)據(jù)屬于A類俗扇，則該A類的概率即為十分之七硝烂。其中有3個數(shù)據(jù)屬于B類，則該B類的概率即為十分之三铜幽。淺顯的解釋就是滞谢，這概率是我們根據(jù)數(shù)據(jù)數(shù)出來的。我們定義貸款申請樣本數(shù)據(jù)表中的數(shù)據(jù)為訓(xùn)練數(shù)據(jù)集D啥酱，則訓(xùn)練數(shù)據(jù)集D的經(jīng)驗熵為H(D)爹凹，|D|表示其樣本容量，及樣本個數(shù)镶殷。設(shè)有K個類Ck, = 1,2,3,...,K,|Ck|為屬于類Ck的樣本個數(shù)禾酱，因此經(jīng)驗熵公式就可以寫為 ：
根據(jù)此公式計算經(jīng)驗熵H(D)，分析貸款申請樣本數(shù)據(jù)表中的數(shù)據(jù)绘趋。最終分類結(jié)果只有兩類颤陶，即放貸和不放貸。根據(jù)表中的數(shù)據(jù)統(tǒng)計可知陷遮，在15個數(shù)據(jù)中滓走，9個數(shù)據(jù)的結(jié)果為放貸，6個數(shù)據(jù)的結(jié)果為不放貸帽馋。所以數(shù)據(jù)集D的經(jīng)驗熵H(D)為：
經(jīng)過計算可知搅方，數(shù)據(jù)集D的經(jīng)驗熵H(D)的值為0.971。
（3） 信息增益
在上面绽族，我們已經(jīng)說過姨涡，如何選擇特征，需要看信息增益。也就是說，信息增益是相對于特征而言的逾冬，信息增益越大缝龄，特征對最終的分類結(jié)果影響也就越大，我們就應(yīng)該選擇對最終分類結(jié)果影響最大的那個特征作為我們的分類特征算利。
在講解信息增益定義之前额划，我們還需要明確一個概念帘睦，條件熵悠轩。
熵我們知道是什么间狂，條件熵又是個什么鬼？條件熵H(Y|X)表示在已知隨機變量X的條件下隨機變量Y的不確定性哗蜈，隨機變量X給定的條件下隨機變量Y的條件熵(conditional entropy)H(Y|X)前标，定義為X給定條件下Y的條件概率分布的熵對X的數(shù)學(xué)期望：
這里坠韩，
同理距潘，當條件熵中的概率由數(shù)據(jù)估計(特別是極大似然估計)得到時，所對應(yīng)的條件熵稱為條件經(jīng)驗熵(empirical conditional entropy)只搁。
明確了條件熵和經(jīng)驗條件熵的概念音比。接下來，讓我們說說信息增益氢惋。前面也提到了洞翩，信息增益是相對于特征而言的。所以焰望，特征A對訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A)骚亿，定義為集合D的經(jīng)驗熵H(D)與特征A給定條件下D的經(jīng)驗條件熵H(D|A)之差，即：
一般地熊赖，熵H(D)與條件熵H(D|A)之差稱為互信息(mutual information)来屠。決策樹學(xué)習(xí)中的信息增益等價于訓(xùn)練數(shù)據(jù)集中類與特征的互信息。
設(shè)特征A有n個不同的取值{a1,a2,···,an}震鹉，根據(jù)特征A的取值將D劃分為n個子集{D1,D2俱笛，···,Dn}，|Di|為Di的樣本個數(shù)传趾。記子集Di中屬于Ck的樣本的集合為Dik迎膜，即Dik = Di ∩ Ck，|Dik|為Dik的樣本個數(shù)浆兰。于是經(jīng)驗條件熵的公式可以些為：
說了這么多概念性的東西磕仅，沒有聽懂也沒有關(guān)系，舉幾個例子簸呈，再回來看一下概念榕订，就懂了。
以貸款申請樣本數(shù)據(jù)表為例進行說明蝶棋⌒读粒看下年齡這一列的數(shù)據(jù)，也就是特征A1玩裙，一共有三個類別兼贸，分別是：青年段直、中年和老年。我們只看年齡是青年的數(shù)據(jù)溶诞，年齡是青年的數(shù)據(jù)一共有5個鸯檬，所以年齡是青年的數(shù)據(jù)在訓(xùn)練數(shù)據(jù)集出現(xiàn)的概率是十五分之五，也就是三分之一螺垢。同理喧务，年齡是中年和老年的數(shù)據(jù)在訓(xùn)練數(shù)據(jù)集出現(xiàn)的概率也都是三分之一。現(xiàn)在我們只看年齡是青年的數(shù)據(jù)的最終得到貸款的概率為五分之二枉圃，因為在五個數(shù)據(jù)中功茴，只有兩個數(shù)據(jù)顯示拿到了最終的貸款，同理孽亲，年齡是中年和老年的數(shù)據(jù)最終得到貸款的概率分別為五分之三坎穿、五分之四。所以計算年齡的信息增益返劲，過程如下：
同理玲昧，計算其余特征的信息增益g(D,A2)、g(D,A3)和g(D,A4)篮绿。分別為：
最后孵延，比較特征的信息增益，由于特征A3(有自己的房子)的信息增益值最大亲配，所以選擇A3作為最優(yōu)特征尘应。
代碼如下
from math import log
'''
函數(shù)說明：dataSet是數(shù)據(jù)集，該函數(shù)為計算數(shù)據(jù)集的初始熵
'''
def calcShannonEnt(dataSet):
numEntries = len(dataSet) #數(shù)據(jù)集元素的個數(shù)
labelCounts = {} #保存每個標簽（label出現(xiàn)的次數(shù)）
for featVec in dataSet:
currentLabel = featVec[-1] #數(shù)據(jù)集的最后一列為標簽
if currentLabel not in labelCounts.keys(): #將標簽放進labelCounts中并計算每個標簽的個數(shù)
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
'''
函數(shù)說明：dateaSet數(shù)據(jù)集
axis劃分的特征
value需要返回的特征的值
'''
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
#將符合條件的哪一行數(shù)據(jù)的axis屬性前面的數(shù)據(jù)添加到redecedFeatVec [:axis]是左閉右開
reducedFeatVec = featVec[:axis]
#extend() 函數(shù)用于在列表末尾一次性追加另一個序列中的多個值（用新列表擴展原來的列表）
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
def createDataSet():
dataSet = [[0, 0, 0, 0, 'no'], # 數(shù)據(jù)集
[0, 0, 0, 1, 'no'],
[0, 1, 0, 1, 'yes'],
[0, 1, 1, 0, 'yes'],
[0, 0, 0, 0, 'no'],
[1, 0, 0, 0, 'no'],
[1, 0, 0, 1, 'no'],
[1, 1, 1, 1, 'yes'],
[1, 0, 1, 2, 'yes'],
[1, 0, 1, 2, 'yes'],
[2, 0, 1, 2, 'yes'],
[2, 0, 1, 1, 'yes'],
[2, 1, 0, 1, 'yes'],
[2, 1, 0, 2, 'yes'],
[2, 0, 0, 0, 'no']]
labels = ['不放貸', '放貸'] # 分類屬性
return dataSet, labels
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1
baseEntropty = calcShannonEnt(dataSet) #初始熵
bestInfoGain = 0.0 #信息增益
bestFeature = -1 #最優(yōu)特征的索引值
for i in range(numFeatures):
featList = [example[i] for example in dataSet] #獲取一個特征的所有值
uniqueVals = set(featList) #創(chuàng)建唯一的分類標簽列表,就是把一個特征的所有屬性不重復(fù)的一個集合
newEntropy = 0.0 #經(jīng)驗條件熵
for value in uniqueVals:
subDataSet =splitDataSet(dataSet,i, value) #得到一個劃分子集
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob *calcShannonEnt(dataSet) #計算子集的熵
infoGain = baseEntropty - newEntropy #信息增益
if(infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestInfoGain, bestFeature
