本文主要介紹了決策樹(shù)的原理及算法

決策樹(shù)的工作原理

image.png

決策樹(shù)基本上就是把我們以前的經(jīng)驗(yàn)總結(jié)出來(lái)审编。我給你準(zhǔn)備了一個(gè)打籃球的訓(xùn)練集。如果我們要出門打籃球辛润，一般會(huì)根據(jù)“天氣”濒生、“溫度”、“濕度”控乾、“刮風(fēng)”這幾個(gè)條件來(lái)判斷么介，最后得到結(jié)果：去打籃球？還是不去阱持？

上面這個(gè)圖就是一棵典型的決策樹(shù)夭拌。我們?cè)谧鰶Q策樹(shù)的時(shí)候，會(huì)經(jīng)歷兩個(gè)階段：構(gòu)造和剪枝衷咽。

構(gòu)造

構(gòu)造就是生成一棵完整的決策樹(shù)鸽扁。簡(jiǎn)單來(lái)說(shuō)，構(gòu)造的過(guò)程就是選擇什么屬性作為節(jié)點(diǎn)的過(guò)程镶骗，那么在構(gòu)造過(guò)程中桶现，會(huì)存在三種節(jié)點(diǎn)：
根節(jié)點(diǎn)：就是樹(shù)的最頂端，最開(kāi)始的那個(gè)節(jié)點(diǎn)鼎姊。在上圖中骡和，“天氣”就是一個(gè)根節(jié)點(diǎn)；
內(nèi)部節(jié)點(diǎn)：就是樹(shù)中間的那些節(jié)點(diǎn)相寇，比如說(shuō)“溫度”慰于、“濕度”、“刮風(fēng)”唤衫；
葉節(jié)點(diǎn)：就是樹(shù)最底部的節(jié)點(diǎn)婆赠，也就是決策結(jié)果。

剪枝

剪枝就是給決策樹(shù)瘦身佳励，防止過(guò)擬合休里。分為“預(yù)剪枝”（Pre-Pruning）和“后剪枝”（Post-Pruning）。

預(yù)剪枝是在決策樹(shù)構(gòu)造時(shí)就進(jìn)行剪枝赃承。方法是在構(gòu)造的過(guò)程中對(duì)節(jié)點(diǎn)進(jìn)行評(píng)估妙黍，如果對(duì)某個(gè)節(jié)點(diǎn)進(jìn)行劃分，在驗(yàn)證集中不能帶來(lái)準(zhǔn)確性的提升瞧剖，那么對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行劃分就沒(méi)有意義拭嫁，這時(shí)就會(huì)把當(dāng)前節(jié)點(diǎn)作為葉節(jié)點(diǎn)，不對(duì)其進(jìn)行劃分抓于。

后剪枝就是在生成決策樹(shù)之后再進(jìn)行剪枝噩凹，通常會(huì)從決策樹(shù)的葉節(jié)點(diǎn)開(kāi)始，逐層向上對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行評(píng)估毡咏。如果剪掉這個(gè)節(jié)點(diǎn)子樹(shù)驮宴，與保留該節(jié)點(diǎn)子樹(shù)在分類準(zhǔn)確性上差別不大，或者剪掉該節(jié)點(diǎn)子樹(shù)呕缭，能在驗(yàn)證集中帶來(lái)準(zhǔn)確性的提升堵泽，那么就可以把該節(jié)點(diǎn)子樹(shù)進(jìn)行剪枝。

擬合

1是欠擬合恢总，3是過(guò)擬合迎罗，都會(huì)導(dǎo)致分類錯(cuò)誤。

image.png

造成過(guò)擬合的原因之一就是因?yàn)橛?xùn)練集中樣本量較小片仿。如果決策樹(shù)選擇的屬性過(guò)多纹安，構(gòu)造出來(lái)的決策樹(shù)一定能夠“完美”地把訓(xùn)練集中的樣本分類，但是這樣就會(huì)把訓(xùn)練集中一些數(shù)據(jù)的特點(diǎn)當(dāng)成所有數(shù)據(jù)的特點(diǎn)，但這個(gè)特點(diǎn)不一定是全部數(shù)據(jù)的特點(diǎn)厢岂，這就使得這個(gè)決策樹(shù)在真實(shí)的數(shù)據(jù)分類中出現(xiàn)錯(cuò)誤光督，也就是模型的“泛化能力”差。

信息熵（entropy）

image.png

p(i|t) 代表了節(jié)點(diǎn) t 為分類 i 的概率塔粒，其中 log2 為取以 2 為底的對(duì)數(shù)结借。這里我們不是來(lái)介紹公式的，而是說(shuō)存在一種度量卒茬，它能幫我們反映出來(lái)這個(gè)信息的不確定度船老。當(dāng)不確定性越大時(shí)，它所包含的信息量也就越大圃酵，信息熵也就越高柳畔。

ID3 算法

ID3 算法計(jì)算的是信息增益，信息增益指的就是劃分可以帶來(lái)純度的提高郭赐，信息熵的下降薪韩。它的計(jì)算公式，是父親節(jié)點(diǎn)的信息熵減去所有子節(jié)點(diǎn)的信息熵堪置。

image.png

公式中 D 是父親節(jié)點(diǎn)躬存，Di 是子節(jié)點(diǎn)，Gain(D,a) 中的 a 作為 D 節(jié)點(diǎn)的屬性選擇舀锨。

C4.5 算法

1. 采用信息增益率

因?yàn)?ID3 在計(jì)算的時(shí)候岭洲，傾向于選擇取值多的屬性。為了避免這個(gè)問(wèn)題坎匿，C4.5 采用信息增益率的方式來(lái)選擇屬性盾剩。信息增益率 = 信息增益 / 屬性熵，具體的計(jì)算公式這里省略替蔬。

當(dāng)屬性有很多值的時(shí)候告私，相當(dāng)于被劃分成了許多份，雖然信息增益變大了承桥，但是對(duì)于 C4.5 來(lái)說(shuō)驻粟，屬性熵也會(huì)變大，所以整體的信息增益率并不大凶异。

2. 采用悲觀剪枝

ID3 構(gòu)造決策樹(shù)的時(shí)候蜀撑，容易產(chǎn)生過(guò)擬合的情況。在 C4.5 中剩彬，會(huì)在決策樹(shù)構(gòu)造之后采用悲觀剪枝（PEP）酷麦，這樣可以提升決策樹(shù)的泛化能力。

悲觀剪枝是后剪枝技術(shù)中的一種喉恋，通過(guò)遞歸估算每個(gè)內(nèi)部節(jié)點(diǎn)的分類錯(cuò)誤率沃饶，比較剪枝前后這個(gè)節(jié)點(diǎn)的分類錯(cuò)誤率來(lái)決定是否對(duì)其進(jìn)行剪枝母廷。這種剪枝方法不再需要一個(gè)單獨(dú)的測(cè)試數(shù)據(jù)集屹徘。

3. 離散化處理連續(xù)屬性

C4.5 可以處理連續(xù)屬性的情況筏勒，對(duì)連續(xù)的屬性進(jìn)行離散化的處理。比如打籃球存在的“濕度”屬性净嘀，不按照“高轩褐、中”劃分椎咧，而是按照濕度值進(jìn)行計(jì)算玖详，那么濕度取什么值都有可能把介。該怎么選擇這個(gè)閾值呢，C4.5 選擇具有最高信息增益的劃分所對(duì)應(yīng)的閾值蟋座。

4. 處理缺失值

針對(duì)數(shù)據(jù)集不完整的情況拗踢，C4.5 也可以進(jìn)行處理。

示例

image.png

我們不考慮缺失的數(shù)值向臀，可以得到溫度 D={2-,3+,4+,5-,6+,7-}巢墅。溫度 = 高：D1={2-,3+,4+} ；溫度 = 中：D2={6+,7-}券膀；溫度 = 低：D3={5-} 君纫。這里 + 號(hào)代表打籃球，- 號(hào)代表不打籃球芹彬。比如 ID=2 時(shí)蓄髓，決策是不打籃球，我們可以記錄為 2-舒帮。
所以三個(gè)葉節(jié)點(diǎn)的信息熵可以結(jié)算為：

image.png

這三個(gè)節(jié)點(diǎn)的歸一化信息熵為 3/60.918+2/61.0+1/60=0.792会喝。
針對(duì)將屬性選擇為溫度的信息增益率為：
Gain(D′, 溫度)=Ent(D′)-0.792=1.0-0.792=0.208
D′的樣本個(gè)數(shù)為 6，而 D 的樣本個(gè)數(shù)為 7玩郊，所以所占權(quán)重比例為 6/7肢执，所以 Gain(D′，溫度) 所占權(quán)重比例為 6/7译红，所以：
Gain(D, 溫度)=6/70.208=0.178
這樣即使在溫度屬性的數(shù)值有缺失的情況下预茄，我們依然可以計(jì)算信息增益，并對(duì)屬性進(jìn)行選擇侦厚。

Cart 算法

暫無(wú)

例題

請(qǐng)你用下面的例子來(lái)模擬下決策樹(shù)的流程耻陕，假設(shè)好蘋果的數(shù)據(jù)如下，請(qǐng)用 ID3 算法來(lái)給出好蘋果的決策樹(shù)假夺。

image.png

「紅」的信息增益為：1「大」的信息增益為：0
因此選擇「紅」的作為根節(jié)點(diǎn)淮蜈，「大」沒(méi)有用，剪枝已卷。

代碼實(shí)現(xiàn)如下

from sklearn import tree
import graphviz
import numpy as np

#創(chuàng)建數(shù)據(jù)[紅梧田，大]，1==是，0==否
data = np.array([[1,1],[1,0],[0,1],[0,0]])
#數(shù)據(jù)標(biāo)注為裁眯，1==好蘋果鹉梨，0==壞蘋果
target = np.array([1,1,0,0])

clf = tree.DecisionTreeClassifier() #創(chuàng)建決策樹(shù)分類器模型
clf = clf.fit(data, target) #擬合數(shù)據(jù)

#最后利用graphviz庫(kù)打印出決策樹(shù)圖
dot_data = tree.export_graphviz(clf,out_file=None)
graph = graphviz.Source(dot_data)# doctest: +SKIP
#在同級(jí)目錄下生成tree.pdf文件
graph.render("tree") 

image.png

參考來(lái)源

數(shù)據(jù)分析實(shí)戰(zhàn)45講.17 丨決策樹(shù)（上）：要不要去打籃球？決策樹(shù)來(lái)告訴你