整理自《極客時間——數(shù)據(jù)分析》課程
一.決策樹的工作原理
在做決策樹時榴捡，需要經(jīng)歷兩個階段：構(gòu)造和剪枝。
構(gòu)造
構(gòu)造的過程就是選擇什么屬性作為節(jié)點的過程。注意烈菌，葉節(jié)點是決策結(jié)果爱榕。
剪枝
剪枝就是給決策樹瘦身瓣喊，這一步想實現(xiàn)的目標(biāo)就是，不需要太多的判斷黔酥，同樣可以得到不錯的結(jié)果藻三。之所以這么做八匠，是為了防止“過擬合”（Overfitting）現(xiàn)象的發(fā)生。
造成過擬合的原因之一就是因為訓(xùn)練集中樣本量較小趴酣。若選擇的屬性太多梨树，會完美的把訓(xùn)練集中的樣本分類，但是其在真實場景中不一定能夠正常工作岖寞，泛化能力較差抡四。
剪枝分為預(yù)剪枝和后剪枝。
預(yù)剪枝是在決策樹構(gòu)造時就進(jìn)行剪枝仗谆。方法是在構(gòu)造的過程中對節(jié)點進(jìn)行評估指巡，如果對某個節(jié)點進(jìn)行劃分，在驗證集中不能帶來準(zhǔn)確性的提升隶垮，那么對這個節(jié)點進(jìn)行劃分就沒有意義藻雪，這時就會把當(dāng)前節(jié)點作為葉節(jié)點，不對其進(jìn)行劃分狸吞。
后剪枝就是在生成決策樹之后再進(jìn)行剪枝勉耀，通常會從決策樹的葉節(jié)點開始，逐層向上對每個節(jié)點進(jìn)行評估蹋偏。如果剪掉這個節(jié)點子樹便斥，與保留該節(jié)點子樹在分類準(zhǔn)確性上差別不大，或者剪掉該節(jié)點子樹威始，能在驗證集中帶來準(zhǔn)確性的提升枢纠，那么就可以把該節(jié)點子樹進(jìn)行剪枝。
純度與信息熵
純度
可以把決策樹的構(gòu)造過程理解成為尋找純凈劃分的過程黎棠。數(shù)學(xué)上晋渺，我們可以用純度來表示，純度換一種方式來解釋就是讓目標(biāo)變量的分歧最小脓斩。
比如有3個集合：
集合一：6天都去玩
集合二：4天去玩木西，2天不玩
集合三：3天玩，3天不玩
則純度排序：集合一 > 集合二 > 集合三
信息熵
信息熵表示信息的不確定度俭厚。
信息熵的公式如下：
信息熵越大户魏，純度越低。
決策樹的構(gòu)造
在構(gòu)造決策樹的時候挪挤，會基于純度來構(gòu)建叼丑。而經(jīng)典的 “不純度”的指標(biāo)有三種，分別是信息增益（ID3 算法）扛门、信息增益率（C4.5 算法）以及基尼指數(shù)（Cart 算法）鸠信。
ID3算法
ID3 算法計算的是信息增益，信息增益指的就是劃分可以帶來純度
的提高论寨，信息熵的下降星立。它的計算公式爽茴，是父親節(jié)點的信息熵減去所有子節(jié)點的信息熵。在計算的過程中绰垂，我們會計算每個子節(jié)點的歸一化信息熵室奏，即按照每個子節(jié)點在父節(jié)點中出現(xiàn)的概率，來計算這些子節(jié)點的信息熵劲装。
以下為信息增益的計算公式：
我們需要計算不同屬性的信息增益胧沫，并選擇其中最大的作為父節(jié)點，這樣可以得到純度高的決策樹占业。
一層一層的往下進(jìn)行計算和分裂绒怨。
ID3 有一個缺陷就是，有些屬性可能對分類任務(wù)沒有太大作用谦疾，但是他們?nèi)匀豢赡軙贿x為最優(yōu)屬性南蹂。這種缺陷不是每次都會發(fā)生，只是存在一定的概率念恍。在大部分情況下六剥，ID3 都能生成不錯的決策樹分類。針對可能發(fā)生的缺陷樊诺，后人提出了新的算法進(jìn)行改進(jìn)仗考。
C4.5算法（ID3改進(jìn)）
采用信息增益率
因為 ID3 在計算的時候，傾向于選擇取值多的屬性词爬。為了避免這個問題，C4.5 采用信息增益率的方式來選擇屬性权均。信息增益率 = 信息增益 / 屬性熵顿膨。
當(dāng)屬性有很多值的時候，相當(dāng)于被劃分成了許多份叽赊，雖然信息增益變大了恋沃，但是對于 C4.5來說，屬性熵也會變大必指，所以整體的信息增益率并不大囊咏。
采用悲觀剪枝
ID3 構(gòu)造決策樹的時候，容易產(chǎn)生過擬合的情況塔橡。在 C4.5 中梅割，會在決策樹構(gòu)造之后采用悲觀剪枝（PEP），這樣可以提升決策樹的泛化能力葛家。
離散化處理連續(xù)屬性
C4.5 可以處理連續(xù)屬性的情況户辞，對連續(xù)的屬性進(jìn)行離散化的處理。
C4.5 選擇具有最高信息增益的劃分所對應(yīng)的閾值癞谒。
處理缺失值
總結(jié)
ID3 算法的優(yōu)點是方法簡單底燎，缺點是對噪聲敏感刃榨。訓(xùn)練數(shù)據(jù)如果有少量錯
誤，可能會產(chǎn)生決策樹分類錯誤双仍。C4.5 在 ID3 的基礎(chǔ)上枢希，用信息增益率代替了信息增益，解決了噪聲敏感的問題朱沃，并且可以對構(gòu)造樹進(jìn)行剪枝苞轿、處理連續(xù)數(shù)值以及數(shù)值缺失等情況，但是由于 C4.5 需要對數(shù)據(jù)集進(jìn)行多次掃描为流，算法效率相對較低呕屎。
二.CART算法
Classification And Regression Tree，中文叫做分類回歸樹敬察。
CART 只支持二叉樹秀睛。同時 CART 決策樹比較特殊，既可以作分類
樹莲祸，又可以作回歸樹蹂安。
什么是分類樹？什么是回歸樹呢锐帜？
一棵決策樹田盈，想要基于數(shù)據(jù)判斷這個人的職業(yè)身份，這個就屬于分類
樹缴阎，因為是從幾個分類中來做選擇允瞧。如果是給定了數(shù)據(jù)，想要預(yù)測這個人的年齡蛮拔，那就屬于回歸樹述暂。
CART分類樹工作流程
決策樹的核心是尋找純凈的劃分，因此引入了純度的概念建炫。實際上 CART 分類樹與 C4.5 算法類似畦韭，只是屬性選擇的指標(biāo)采用的是基尼系數(shù)。
基尼系數(shù)本身反應(yīng)了樣本的不確定度肛跌。當(dāng)基尼系數(shù)越小的時候艺配，說明樣本之間的差異性小，不確定程度低衍慎。分類的過程本身是一個不確定度降低的過程转唉，即純度的提升過程。所以 CART 算法在構(gòu)造分類樹的時候西饵，會選擇基尼系數(shù)最小的屬性作為屬性的劃分酝掩。
如何使用CART算法創(chuàng)建分類樹
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
#準(zhǔn)備數(shù)據(jù)
iris = load_iris()
#獲取特征集和分類標(biāo)識
features = iris.data
labels = iris.target
#隨機抽取33%的數(shù)據(jù)作為測試集，其余為訓(xùn)練集
train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33, random_state=0)
#創(chuàng)建CART分類樹
clf = DecisionTreeClassifier(criterion='gini')
#擬合構(gòu)造CART分類樹
clf.fit(train_features, train_labels)
#用CART分類樹做預(yù)測
test_predict = clf.predict(test_features)
#預(yù)測結(jié)果與測試集結(jié)果做比對
score = accuracy_score(test_labels, test_predict)
print("cart分類樹準(zhǔn)確率 %.4lf" % score)
CART回歸樹的構(gòu)造流程
CART回歸樹劃分?jǐn)?shù)據(jù)集的過程和分類樹的過程是一樣的眷柔，只是回歸樹得到的預(yù)測結(jié)果是連續(xù)值期虾，而且評判“不純度”的指標(biāo)不同原朝。在CART分類樹中采用的是基尼系數(shù)作為標(biāo)準(zhǔn)，那么在CART回歸樹中镶苞，根據(jù)樣本的混亂程度喳坠，也就是樣本的離散程度來評價“不純度”。
樣本的離散程度具體的計算方式是茂蚓，先計算所有樣本的均值壕鹉，然后計算每個樣本值到均值的差值。我們假設(shè)x為樣本的個體聋涨，均值為u晾浴。為了統(tǒng)計樣本的離散程度，我們可以取差值的絕對值牍白，或者方差脊凰。
所以這兩種節(jié)點劃分的標(biāo)準(zhǔn)，分別對應(yīng)著兩種目標(biāo)函數(shù)最優(yōu)化的標(biāo)準(zhǔn)茂腥，即用最小絕對偏差（LAD）狸涌，或者使用最小二乘偏差（LSD）。
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error
from sklearn.metrics import r2_score, mean_absolute_error, mean_squared_error
from sklearn.tree import DecisionTreeRegressor
from sklearn.datasets import load_boston
#準(zhǔn)備數(shù)據(jù)
boston = load_boston()
#獲取特征集和分類標(biāo)識
features = boston.data
prices = boston.target
#隨機抽取33%的數(shù)據(jù)作為測試集最岗，其余為訓(xùn)練集
train_features, test_features, train_price, test_price = train_test_split(features, prices, test_size=0.33)
#創(chuàng)建CART回歸樹
clf = DecisionTreeRegressor()
#擬合構(gòu)造CART回歸樹
clf.fit(train_features, train_price)
#用CART分類樹做預(yù)測房價
predict_price = clf.predict(test_features)
#預(yù)測結(jié)果與測試集結(jié)果做比對
print('回歸樹二乘偏差均值:', mean_squared_error(test_price, predict_price))
print('回歸樹絕對值偏差均值:', mean_absolute_error(test_price, predict_price))
三.決策樹的應(yīng)用
在金融行業(yè)可以用決策樹做貸款風(fēng)險評估帕胆，醫(yī)療行業(yè)可以用決策樹生成輔助診斷，電商行業(yè)可以用決策樹對銷售額進(jìn)行預(yù)測等般渡。
四.K折交叉驗證
這里可以使用 K 折交叉驗證的方式懒豹，交叉驗證是一種常用的驗證分類準(zhǔn)確率的方法，原理是拿出大部分樣本進(jìn)行訓(xùn)練驯用，少量的用于分類器的驗證歼捐。K 折交叉驗證，就是做 K 次交叉驗證晨汹，每次選取 K 分之一的數(shù)據(jù)作為驗證，其余作為訓(xùn)練贷盲。輪流 K 次淘这，取平均值。
K 折交叉驗證的原理是這樣的：
- 將數(shù)據(jù)集平均分割成 K 個等份巩剖；
- 使用 1 份數(shù)據(jù)作為測試數(shù)據(jù)铝穷，其余作為訓(xùn)練數(shù)據(jù)；
- 計算測試準(zhǔn)確率佳魔；
- 使用不同的測試集曙聂，重復(fù) 2、3 步驟鞠鲜。
