決策樹(shù)
決策樹(shù)是什么？決策樹(shù)(decision tree)是一種基本的分類與回歸方法。舉個(gè)通俗易懂的例子，如下圖所示的流程圖就是一個(gè)決策樹(shù)，長(zhǎng)方形代表判斷模塊(decision block)，橢圓形成代表終止模塊(terminating block)，表示已經(jīng)得出結(jié)論，可以終止運(yùn)行。從判斷模塊引出的左右箭頭稱作為分支(branch)，它可以達(dá)到另一個(gè)判斷模塊或者終止模塊。我們還可以這樣理解，分類決策樹(shù)模型是一種描述對(duì)實(shí)例進(jìn)行分類的樹(shù)形結(jié)構(gòu)。決策樹(shù)由結(jié)點(diǎn)(node)和有向邊(directed edge)組成。結(jié)點(diǎn)有兩種類型：內(nèi)部結(jié)點(diǎn)(internal node)和葉結(jié)點(diǎn)(leaf node)。內(nèi)部結(jié)點(diǎn)表示一個(gè)特征或?qū)傩?，葉結(jié)點(diǎn)表示一個(gè)類。蒙圈沒(méi)？？如下圖所示的決策樹(shù)，長(zhǎng)方形和橢圓形都是結(jié)點(diǎn)。長(zhǎng)方形的結(jié)點(diǎn)屬于內(nèi)部結(jié)點(diǎn)，橢圓形的結(jié)點(diǎn)屬于葉結(jié)點(diǎn)，從結(jié)點(diǎn)引出的左右箭頭就是有向邊。而最上面的結(jié)點(diǎn)就是決策樹(shù)的根結(jié)點(diǎn)(root node)。這樣，結(jié)點(diǎn)說(shuō)法就與模塊說(shuō)法對(duì)應(yīng)上了，理解就好。
我們回到這個(gè)流程圖，對(duì)，你沒(méi)看錯(cuò)，這就是一個(gè)假想的相親對(duì)象分類系統(tǒng)。它首先檢測(cè)相親對(duì)方是否有房。如果有房，則對(duì)于這個(gè)相親對(duì)象可以考慮進(jìn)一步接觸。如果沒(méi)有房，則觀察相親對(duì)象是否有上進(jìn)心，如果沒(méi)有，直接Say Goodbye，此時(shí)可以說(shuō)："你人很好，但是我們不合適。"如果有，則可以把這個(gè)相親對(duì)象列入候選名單，好聽(tīng)點(diǎn)叫候選名單，有點(diǎn)瑕疵地講，那就是備胎。
不過(guò)這只是個(gè)簡(jiǎn)單的相親對(duì)象分類系統(tǒng)，只是做了簡(jiǎn)單的分類。真實(shí)情況可能要復(fù)雜得多，考慮因素也可以是五花八門。脾氣好嗎？會(huì)做飯嗎？愿意做家務(wù)嗎？家里幾個(gè)孩子？父母是干什么的？天啊，我不想再說(shuō)下去了，想想都可怕。
我們可以把決策樹(shù)看成一個(gè)if-then規(guī)則的集合，將決策樹(shù)轉(zhuǎn)換成if-then規(guī)則的過(guò)程是這樣的：由決策樹(shù)的根結(jié)點(diǎn)(root node)到葉結(jié)點(diǎn)(leaf node)的每一條路徑構(gòu)建一條規(guī)則；路徑上內(nèi)部結(jié)點(diǎn)的特征對(duì)應(yīng)著規(guī)則的條件，而葉結(jié)點(diǎn)的類對(duì)應(yīng)著規(guī)則的結(jié)論。決策樹(shù)的路徑或其對(duì)應(yīng)的if-then規(guī)則集合具有一個(gè)重要的性質(zhì)：互斥并且完備。這就是說(shuō)，每一個(gè)實(shí)例都被一條路徑或一條規(guī)則所覆蓋，而且只被一條路徑或一條規(guī)則所覆蓋。這里所覆蓋是指實(shí)例的特征與路徑上的特征一致或?qū)嵗凉M足規(guī)則的條件。
使用決策樹(shù)做預(yù)測(cè)需要以下過(guò)程：
- 收集數(shù)據(jù)：可以使用任何方法。比如想構(gòu)建一個(gè)相親系統(tǒng)，我們可以從媒婆那里，或者通過(guò)采訪相親對(duì)象獲取數(shù)據(jù)。根據(jù)他們考慮的因素和最終的選擇結(jié)果，就可以得到一些供我們利用的數(shù)據(jù)了。
- 準(zhǔn)備數(shù)據(jù)：收集完的數(shù)據(jù)，我們要進(jìn)行整理，將這些所有收集的信息按照一定規(guī)則整理出來(lái)，并排版，方便我們進(jìn)行后續(xù)處理。
- 分析數(shù)據(jù)：可以使用任何方法，決策樹(shù)構(gòu)造完成之后，我們可以檢查決策樹(shù)圖形是否符合預(yù)期。
- 訓(xùn)練算法：這個(gè)過(guò)程也就是構(gòu)造決策樹(shù)，同樣也可以說(shuō)是決策樹(shù)學(xué)習(xí)，就是構(gòu)造一個(gè)決策樹(shù)的數(shù)據(jù)結(jié)構(gòu)。
- 測(cè)試算法：使用經(jīng)驗(yàn)樹(shù)計(jì)算錯(cuò)誤率。當(dāng)錯(cuò)誤率達(dá)到了可接收范圍，這個(gè)決策樹(shù)就可以投放使用了。
- 使用算法：此步驟可以使用適用于任何監(jiān)督學(xué)習(xí)算法，而使用決策樹(shù)可以更好地理解數(shù)據(jù)的內(nèi)在含義。
決策樹(shù)構(gòu)建的準(zhǔn)備工作
使用決策樹(shù)做預(yù)測(cè)的每一步驟都很重要，數(shù)據(jù)收集不到位，將會(huì)導(dǎo)致沒(méi)有足夠的特征讓我們構(gòu)建錯(cuò)誤率低的決策樹(shù)。數(shù)據(jù)特征充足，但是不知道用哪些特征好，將會(huì)導(dǎo)致無(wú)法構(gòu)建出分類效果好的決策樹(shù)模型。從算法方面看，決策樹(shù)的構(gòu)建是我們的核心內(nèi)容。
決策樹(shù)要如何構(gòu)建呢？通常，這一過(guò)程可以概括為3個(gè)步驟：特征選擇、決策樹(shù)的生成和決策樹(shù)的修剪。
1、特征選擇
特征選擇在于選取對(duì)訓(xùn)練數(shù)據(jù)具有分類能力的特征。這樣可以提高決策樹(shù)學(xué)習(xí)的效率，如果利用一個(gè)特征進(jìn)行分類的結(jié)果與隨機(jī)分類的結(jié)果沒(méi)有很大差別，則稱這個(gè)特征是沒(méi)有分類能力的。經(jīng)驗(yàn)上扔掉這樣的特征對(duì)決策樹(shù)學(xué)習(xí)的精度影響不大。通常特征選擇的標(biāo)準(zhǔn)是信息增益(information gain)或信息增益比，為了簡(jiǎn)單，本文使用信息增益作為選擇特征的標(biāo)準(zhǔn)。那么，什么是信息增益？在講解信息增益之前，讓我們看一組實(shí)例，貸款申請(qǐng)樣本數(shù)據(jù)表。
希望通過(guò)所給的訓(xùn)練數(shù)據(jù)學(xué)習(xí)一個(gè)貸款申請(qǐng)的決策樹(shù)，用于對(duì)未來(lái)的貸款申請(qǐng)進(jìn)行分類，即當(dāng)新的客戶提出貸款申請(qǐng)時(shí)，根據(jù)申請(qǐng)人的特征利用決策樹(shù)決定是否批準(zhǔn)貸款申請(qǐng)。
特征選擇就是決定用哪個(gè)特征來(lái)劃分特征空間。比如，我們通過(guò)上述數(shù)據(jù)表得到兩個(gè)可能的決策樹(shù)，分別由兩個(gè)不同特征的根結(jié)點(diǎn)構(gòu)成。
圖(a)所示的根結(jié)點(diǎn)的特征是年齡，有3個(gè)取值，對(duì)應(yīng)于不同的取值有不同的子結(jié)點(diǎn)。圖(b)所示的根節(jié)點(diǎn)的特征是工作，有2個(gè)取值，對(duì)應(yīng)于不同的取值有不同的子結(jié)點(diǎn)。兩個(gè)決策樹(shù)都可以從此延續(xù)下去。問(wèn)題是：究竟選擇哪個(gè)特征更好些？這就要求確定選擇特征的準(zhǔn)則。直觀上，如果一個(gè)特征具有更好的分類能力，或者說(shuō)，按照這一特征將訓(xùn)練數(shù)據(jù)集分割成子集，使得各個(gè)子集在當(dāng)前條件下有最好的分類，那么就更應(yīng)該選擇這個(gè)特征。信息增益就能夠很好地表示這一直觀的準(zhǔn)則。
什么是信息增益呢？在劃分?jǐn)?shù)據(jù)集之后信息發(fā)生的變化稱為信息增益，知道如何計(jì)算信息增益，我們就可以計(jì)算每個(gè)特征值劃分?jǐn)?shù)據(jù)集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇。
（1）香農(nóng)熵
在可以評(píng)測(cè)哪個(gè)數(shù)據(jù)劃分方式是最好的數(shù)據(jù)劃分之前，我們必須學(xué)習(xí)如何計(jì)算信息增益。集合信息的度量方式稱為香農(nóng)熵或者簡(jiǎn)稱為熵(entropy)，這個(gè)名字來(lái)源于信息論之父克勞德·香農(nóng)。
如果看不明白什么是信息增益和熵，請(qǐng)不要著急，因?yàn)樗麄冏哉Q生的那一天起，就注定會(huì)令世人十分費(fèi)解?？藙诘隆は戕r(nóng)寫完信息論之后，約翰·馮·諾依曼建議使用"熵"這個(gè)術(shù)語(yǔ)，因?yàn)榇蠹叶疾恢浪鞘裁匆馑肌?/p>
熵定義為信息的期望值。在信息論與概率統(tǒng)計(jì)中，熵是表示隨機(jī)變量不確定性的度量。如果待分類的事物可能劃分在多個(gè)分類之中，則符號(hào)xi的信息定義為 ：
其中p(xi)是選擇該分類的概率。有人可能會(huì)問(wèn)，信息為啥這樣定義??？答曰：前輩得出的結(jié)論。這就跟1+1等于2一樣，記住并且會(huì)用即可。上述式中的對(duì)數(shù)以2為底，也可以e為底(自然對(duì)數(shù))。
通過(guò)上式，我們可以得到所有類別的信息。為了計(jì)算熵，我們需要計(jì)算所有類別所有可能值包含的信息期望值(數(shù)學(xué)期望)，通過(guò)下面的公式得到：
期中n是分類的數(shù)目。熵越大，隨機(jī)變量的不確定性就越大。
當(dāng)熵中的概率由數(shù)據(jù)估計(jì)(特別是最大似然估計(jì))得到時(shí)，所對(duì)應(yīng)的熵稱為經(jīng)驗(yàn)熵(empirical entropy)。什么叫由數(shù)據(jù)估計(jì)？比如有10個(gè)數(shù)據(jù)，一共有兩個(gè)類別，A類和B類。其中有7個(gè)數(shù)據(jù)屬于A類，則該A類的概率即為十分之七。其中有3個(gè)數(shù)據(jù)屬于B類，則該B類的概率即為十分之三。淺顯的解釋就是，這概率是我們根據(jù)數(shù)據(jù)數(shù)出來(lái)的。我們定義貸款申請(qǐng)樣本數(shù)據(jù)表中的數(shù)據(jù)為訓(xùn)練數(shù)據(jù)集D，則訓(xùn)練數(shù)據(jù)集D的經(jīng)驗(yàn)熵為H(D)，|D|表示其樣本容量，及樣本個(gè)數(shù)。設(shè)有K個(gè)類Ck, = 1,2,3,...,K,|Ck|為屬于類Ck的樣本個(gè)數(shù)，因此經(jīng)驗(yàn)熵公式就可以寫為 ：
根據(jù)此公式計(jì)算經(jīng)驗(yàn)熵H(D)，分析貸款申請(qǐng)樣本數(shù)據(jù)表中的數(shù)據(jù)。最終分類結(jié)果只有兩類，即放貸和不放貸。根據(jù)表中的數(shù)據(jù)統(tǒng)計(jì)可知，在15個(gè)數(shù)據(jù)中，9個(gè)數(shù)據(jù)的結(jié)果為放貸，6個(gè)數(shù)據(jù)的結(jié)果為不放貸。所以數(shù)據(jù)集D的經(jīng)驗(yàn)熵H(D)為：
經(jīng)過(guò)計(jì)算可知，數(shù)據(jù)集D的經(jīng)驗(yàn)熵H(D)的值為0.971。
（3） 信息增益
在上面，我們已經(jīng)說(shuō)過(guò)，如何選擇特征，需要看信息增益。也就是說(shuō)，信息增益是相對(duì)于特征而言的，信息增益越大，特征對(duì)最終的分類結(jié)果影響也就越大，我們就應(yīng)該選擇對(duì)最終分類結(jié)果影響最大的那個(gè)特征作為我們的分類特征。
在講解信息增益定義之前，我們還需要明確一個(gè)概念，條件熵。
熵我們知道是什么，條件熵又是個(gè)什么鬼？條件熵H(Y|X)表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性，隨機(jī)變量X給定的條件下隨機(jī)變量Y的條件熵(conditional entropy)H(Y|X)，定義為X給定條件下Y的條件概率分布的熵對(duì)X的數(shù)學(xué)期望：
這里，
同理，當(dāng)條件熵中的概率由數(shù)據(jù)估計(jì)(特別是極大似然估計(jì))得到時(shí)，所對(duì)應(yīng)的條件熵稱為條件經(jīng)驗(yàn)熵(empirical conditional entropy)。
明確了條件熵和經(jīng)驗(yàn)條件熵的概念。接下來(lái)，讓我們說(shuō)說(shuō)信息增益。前面也提到了，信息增益是相對(duì)于特征而言的。所以，特征A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A)，定義為集合D的經(jīng)驗(yàn)熵H(D)與特征A給定條件下D的經(jīng)驗(yàn)條件熵H(D|A)之差，即：
一般地，熵H(D)與條件熵H(D|A)之差稱為互信息(mutual information)。決策樹(shù)學(xué)習(xí)中的信息增益等價(jià)于訓(xùn)練數(shù)據(jù)集中類與特征的互信息。
設(shè)特征A有n個(gè)不同的取值{a1,a2,···,an}，根據(jù)特征A的取值將D劃分為n個(gè)子集{D1,D2，···,Dn}，|Di|為Di的樣本個(gè)數(shù)。記子集Di中屬于Ck的樣本的集合為Dik，即Dik = Di ∩ Ck，|Dik|為Dik的樣本個(gè)數(shù)。于是經(jīng)驗(yàn)條件熵的公式可以些為：
說(shuō)了這么多概念性的東西，沒(méi)有聽(tīng)懂也沒(méi)有關(guān)系，舉幾個(gè)例子，再回來(lái)看一下概念，就懂了。
以貸款申請(qǐng)樣本數(shù)據(jù)表為例進(jìn)行說(shuō)明。看下年齡這一列的數(shù)據(jù)，也就是特征A1，一共有三個(gè)類別，分別是：青年、中年和老年。我們只看年齡是青年的數(shù)據(jù)，年齡是青年的數(shù)據(jù)一共有5個(gè)，所以年齡是青年的數(shù)據(jù)在訓(xùn)練數(shù)據(jù)集出現(xiàn)的概率是十五分之五，也就是三分之一。同理，年齡是中年和老年的數(shù)據(jù)在訓(xùn)練數(shù)據(jù)集出現(xiàn)的概率也都是三分之一?，F(xiàn)在我們只看年齡是青年的數(shù)據(jù)的最終得到貸款的概率為五分之二，因?yàn)樵谖鍌€(gè)數(shù)據(jù)中，只有兩個(gè)數(shù)據(jù)顯示拿到了最終的貸款，同理，年齡是中年和老年的數(shù)據(jù)最終得到貸款的概率分別為五分之三、五分之四。所以計(jì)算年齡的信息增益，過(guò)程如下：
同理，計(jì)算其余特征的信息增益g(D,A2)、g(D,A3)和g(D,A4)。分別為：
最后，比較特征的信息增益，由于特征A3(有自己的房子)的信息增益值最大，所以選擇A3作為最優(yōu)特征。
代碼如下
from math import log
'''
函數(shù)說(shuō)明：dataSet是數(shù)據(jù)集，該函數(shù)為計(jì)算數(shù)據(jù)集的初始熵
'''
def calcShannonEnt(dataSet):
numEntries = len(dataSet) #數(shù)據(jù)集元素的個(gè)數(shù)
labelCounts = {} #保存每個(gè)標(biāo)簽（label出現(xiàn)的次數(shù)）
for featVec in dataSet:
currentLabel = featVec[-1] #數(shù)據(jù)集的最后一列為標(biāo)簽
if currentLabel not in labelCounts.keys(): #將標(biāo)簽放進(jìn)labelCounts中并計(jì)算每個(gè)標(biāo)簽的個(gè)數(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ù)說(shuō)明：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]是左閉右開(kāi)
reducedFeatVec = featVec[:axis]
#extend() 函數(shù)用于在列表末尾一次性追加另一個(gè)序列中的多個(gè)值（用新列表擴(kuò)展原來(lái)的列表）
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] #獲取一個(gè)特征的所有值
uniqueVals = set(featList) #創(chuàng)建唯一的分類標(biāo)簽列表,就是把一個(gè)特征的所有屬性不重復(fù)的一個(gè)集合
newEntropy = 0.0 #經(jīng)驗(yàn)條件熵
for value in uniqueVals:
subDataSet =splitDataSet(dataSet,i, value) #得到一個(gè)劃分子集
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob *calcShannonEnt(dataSet) #計(jì)算子集的熵
infoGain = baseEntropty - newEntropy #信息增益
if(infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestInfoGain, bestFeature
