一. 決策樹（decision tree）：是一種基本的分類與回歸方法，此處主要討論分類的決策樹。
在分類問題中，表示基于特征對實例進(jìn)行分類的過程，可以認(rèn)為是if-then的集合，也可以認(rèn)為是定義在特征空間與類空間上的條件概率分布。
二. 決策樹通常有三個步驟：特征選擇、決策樹的生成、決策樹的修剪。
用決策樹分類：從根節(jié)點開始，對實例的某一特征進(jìn)行測試，根據(jù)測試結(jié)果將實例分配到其子節(jié)點，此時每個子節(jié)點對應(yīng)著該特征的一個取值，如此遞歸的對實例進(jìn)行測試并分配，直到到達(dá)葉節(jié)點，最后將實例分到葉節(jié)點的類中。
下圖為決策樹示意圖，圓點——內(nèi)部節(jié)點，方框——葉節(jié)點
- 決策樹學(xué)習(xí)的目標(biāo)：根據(jù)給定的訓(xùn)練數(shù)據(jù)集構(gòu)建一個決策樹模型，使它能夠?qū)嵗M(jìn)行正確的分類。
- 決策樹學(xué)習(xí)的本質(zhì)：從訓(xùn)練集中歸納出一組分類規(guī)則，或者說是由訓(xùn)練數(shù)據(jù)集估計條件概率模型。
- 決策樹學(xué)習(xí)的損失函數(shù)：正則化的極大似然函數(shù)
- 決策樹學(xué)習(xí)的測試：最小化損失函數(shù)
- 決策樹學(xué)習(xí)的目標(biāo)：在損失函數(shù)的意義下，選擇最優(yōu)決策樹的問題。
- 決策樹原理和問答猜測結(jié)果游戲相似，根據(jù)一系列數(shù)據(jù)，然后給出游戲的答案
三. 決策樹的構(gòu)造
決策樹學(xué)習(xí)的算法通常是一個遞歸地選擇最優(yōu)特征，并根據(jù)該特征對訓(xùn)練數(shù)據(jù)進(jìn)行分割，使得各個子數(shù)據(jù)集有一個最好的分類的過程。這一過程對應(yīng)著對特征空間的劃分，也對應(yīng)著決策樹的構(gòu)建。
1） 開始：構(gòu)建根節(jié)點，將所有訓(xùn)練數(shù)據(jù)都放在根節(jié)點，選擇一個最優(yōu)特征，按著這一特征將訓(xùn)練數(shù)據(jù)集分割成子集，使得各個子集有一個在當(dāng)前條件下最好的分類。
2） 如果這些子集已經(jīng)能夠被基本正確分類，那么構(gòu)建葉節(jié)點，并將這些子集分到所對應(yīng)的葉節(jié)點去。
3）如果還有子集不能夠被正確的分類，那么就對這些子集選擇新的最優(yōu)特征，繼續(xù)對其進(jìn)行分割，構(gòu)建相應(yīng)的節(jié)點，如果遞歸進(jìn)行，直至所有訓(xùn)練數(shù)據(jù)子集被基本正確的分類，或者沒有合適的特征為止。
4）每個子集都被分到葉節(jié)點上，即都有了明確的類，這樣就生成了一顆決策樹。
四. 決策樹的特點：
優(yōu)點：計算復(fù)雜度不高，輸出結(jié)果易于理解，對中間值的缺失不敏感，可以處理不相關(guān)特征數(shù)據(jù)。
缺點：可能會產(chǎn)生過度匹配的問題
適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型
首先：確定當(dāng)前數(shù)據(jù)集上的決定性特征，為了得到該決定性特征，必須評估每個特征，完成測試之后，原始數(shù)據(jù)集就被劃分為幾個數(shù)據(jù)子集，這些數(shù)據(jù)子集會分布在第一個決策點的所有分支上，如果某個分支下的數(shù)據(jù)屬于同一類型，則當(dāng)前無序閱讀的垃圾郵件已經(jīng)正確的劃分?jǐn)?shù)據(jù)分類，無需進(jìn)一步對數(shù)據(jù)集進(jìn)行分割，如果不屬于同一類，則要重復(fù)劃分?jǐn)?shù)據(jù)子集，直到所有相同類型的數(shù)據(jù)均在一個數(shù)據(jù)子集內(nèi)。
五. 信息增益
在劃分?jǐn)?shù)據(jù)集之前之后信息發(fā)生的變化成為信息增益，知道如何計算信息增益，我們就可以計算每個特征值劃分?jǐn)?shù)據(jù)集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇。
-
熵
-
信息增益
表示得知特征X的信息而使得類Y的信息不確定性減少的程度。
六. 決策樹的剪枝策略
決策樹生成算法遞歸的產(chǎn)生決策樹，直到不能繼續(xù)下去為止，這樣產(chǎn)生的樹往往對訓(xùn)練數(shù)據(jù)的分類很準(zhǔn)確，但對未知測試數(shù)據(jù)的分類缺沒有那么精確，即會出現(xiàn)過擬合現(xiàn)象。過擬合產(chǎn)生的原因在于在學(xué)習(xí)時過多的考慮如何提高對訓(xùn)練數(shù)據(jù)的正確分類，從而構(gòu)建出過于復(fù)雜的決策樹，解決方法是考慮決策樹的復(fù)雜度，對已經(jīng)生成的樹進(jìn)行簡化。
剪枝（pruning）：從已經(jīng)生成的樹上裁掉一些子樹或葉節(jié)點，并將其根節(jié)點或父節(jié)點作為新的葉子節(jié)點，從而簡化分類樹模型。
決策樹算法很容易過擬合（overfitting），剪枝算法就是用來防止決策樹過擬合，提高泛華性能的方法。
剪枝分為預(yù)剪枝與后剪枝。
預(yù)剪枝是指在決策樹的生成過程中，對每個節(jié)點在劃分前先進(jìn)行評估，若當(dāng)前的劃分不能帶來泛化性能的提升，則停止劃分，并將當(dāng)前節(jié)點標(biāo)記為葉節(jié)點。
后剪枝是指先從訓(xùn)練集生成一顆完整的決策樹，然后自底向上對非葉節(jié)點進(jìn)行考察，若將該節(jié)點對應(yīng)的子樹替換為葉節(jié)點，能帶來泛化性能的提升，則將該子樹替換為葉節(jié)點。
那么怎么來判斷是否帶來泛化性能的提升那？最簡單的就是留出法，即預(yù)留一部分?jǐn)?shù)據(jù)作為驗證集來進(jìn)行性能評估。
剪枝就是當(dāng)α 確定時，選擇損失函數(shù)最小的模型，即損失函數(shù)最小的子樹。
當(dāng)α 值確定時，子樹越大，往往與訓(xùn)練數(shù)據(jù)的擬合越好，但是模型的復(fù)雜度越高；子樹越小，模型的復(fù)雜度就越低，但是往往與訓(xùn)練數(shù)據(jù)的擬合不好損失函數(shù)正好表示了對兩者的平衡。
七. ID3、C4.5、CART的區(qū)別
ID3 使用信息增益作為選擇特征的準(zhǔn)則；C4.5 使用信息增益比作為選擇特征的準(zhǔn)則；CART 使用 Gini 指數(shù)作為選擇特征的準(zhǔn)則。
- ID3
熵表示的是數(shù)據(jù)中包含的信息量大小。熵越小，數(shù)據(jù)的純度越高，也就是說數(shù)據(jù)越趨于一致，這是我們希望的劃分之后每個子節(jié)點的樣子。
信息增益 = 劃分前熵 - 劃分后熵。信息增益越大，則意味著使用屬性 a 來進(jìn)行劃分所獲得的 “純度提升” 越大 **。也就是說，用屬性 a 來劃分訓(xùn)練集，得到的結(jié)果中純度比較高。
ID3 僅僅適用于二分類問題。ID3 僅僅能夠處理離散屬性。
- C4.5
C4.5 克服了 ID3 僅僅能夠處理離散屬性的問題，以及信息增益偏向選擇取值較多特征的問題，使用信息增益比來選擇特征。信息增益比 = 信息增益 / 劃分前熵 選擇信息增益比最大的作為最優(yōu)特征。
C4.5 處理連續(xù)特征是先將特征取值排序，以連續(xù)兩個值中間值作為劃分標(biāo)準(zhǔn)。嘗試每一種劃分，并計算修正后的信息增益，選擇信息增益最大的分裂點作為該屬性的分裂點。
- CART
CART 與 ID3，C4.5 不同之處在于 CART 生成的樹必須是二叉樹。也就是說，無論是回歸還是分類問題，無論特征是離散的還是連續(xù)的，無論屬性取值有多個還是兩個，內(nèi)部節(jié)點只能根據(jù)屬性值進(jìn)行二分。
CART 的全稱是分類與回歸樹。從這個名字中就應(yīng)該知道，CART 既可以用于分類問題，也可以用于回歸問題。
回歸樹中，使用平方誤差最小化準(zhǔn)則來選擇特征并進(jìn)行劃分。每一個葉子節(jié)點給出的預(yù)測值，是劃分到該葉子節(jié)點的所有樣本目標(biāo)值的均值，這樣只是在給定劃分的情況下最小化了平方誤差。
要確定最優(yōu)化分，還需要遍歷所有屬性，以及其所有的取值來分別嘗試劃分并計算在此種劃分情況下的最小平方誤差，選取最小的作為此次劃分的依據(jù)。由于回歸樹生成使用平方誤差最小化準(zhǔn)則，所以又叫做最小二乘回歸樹。
分類樹種，使用 Gini 指數(shù)最小化準(zhǔn)則來選擇特征并進(jìn)行劃分；
Gini 指數(shù)表示集合的不確定性，或者是不純度?；嶂笖?shù)越大，集合不確定性越高，不純度也越大。這一點和熵類似。另一種理解基尼指數(shù)的思路是，基尼指數(shù)是為了最小化誤分類的概率。
信息增益 vs 信息增益比
之所以引入了信息增益比，是由于信息增益的一個缺點。那就是：信息增益總是偏向于選擇取值較多的屬性。信息增益比在此基礎(chǔ)上增加了一個罰項，解決了這個問題。
Gini 指數(shù) vs 熵
既然這兩個都可以表示數(shù)據(jù)的不確定性，不純度。那么這兩個有什么區(qū)別那？
Gini 指數(shù)的計算不需要對數(shù)運算，更加高效；
Gini 指數(shù)更偏向于連續(xù)屬性，熵更偏向于離散屬性。
八. 可視化
%matplotlib inline
import matplotlib.pyplot as plt
import pandas as pd
from sklearn.datasets.california_housing import fetch_california_housing
housing = fetch_california_housing()
print(housing.DESCR)
housing.data.shape
housing.data[0]
from sklearn import tree
dtr = tree.DecisionTreeRegressor(max_depth = 2)
dtr.fit(housing.data[:, [6, 7]], housing.target)
#要可視化顯示 首先需要安裝 graphviz http://www.graphviz.org/Download..php
dot_data = \
tree.export_graphviz(
dtr,
out_file = None,
feature_names = housing.feature_names[6:8],
filled = True,
impurity = False,
rounded = True
)
#pip install pydotplus
import pydotplus
graph = pydotplus.graph_from_dot_data(dot_data)
graph.get_nodes()[7].set_fillcolor("#FFF2DD")
from IPython.display import Image
Image(graph.create_png())
graph.write_png("dtr_white_background.png")
from sklearn.model_selection import train_test_split
data_train, data_test, target_train, target_test = \
train_test_split(housing.data, housing.target, test_size = 0.1, random_state = 42)
dtr = tree.DecisionTreeRegressor(random_state = 42)
dtr.fit(data_train, target_train)
dtr.score(data_test, target_test)
from sklearn.ensemble import RandomForestRegressor
rfr = RandomForestRegressor( random_state = 42)
rfr.fit(data_train, target_train)
rfr.score(data_test, target_test)
參數(shù)說明如下：
criterion：特征選擇標(biāo)準(zhǔn)，可選參數(shù)，默認(rèn)是gini，可以設(shè)置為entropy。gini是基尼不純度，是將來自集合的某種結(jié)果隨機應(yīng)用于某一數(shù)據(jù)項的預(yù)期誤差率，是一種基于統(tǒng)計的思想。entropy是香農(nóng)熵，也就是上篇文章講過的內(nèi)容，是一種基于信息論的思想。Sklearn把gini設(shè)為默認(rèn)參數(shù)，應(yīng)該也是做了相應(yīng)的斟酌的，精度也許更高些？ID3算法使用的是entropy，CART算法使用的則是gini。
splitter：特征劃分點選擇標(biāo)準(zhǔn)，可選參數(shù)，默認(rèn)是best，可以設(shè)置為random。每個結(jié)點的選擇策略。best參數(shù)是根據(jù)算法選擇最佳的切分特征，例如gini、entropy。random隨機的在部分劃分點中找局部最優(yōu)的劃分點。默認(rèn)的”best”適合樣本量不大的時候，而如果樣本數(shù)據(jù)量非常大，此時決策樹構(gòu)建推薦”random”。
max_features：劃分時考慮的最大特征數(shù)，可選參數(shù)，默認(rèn)是None。尋找最佳切分時考慮的最大特征數(shù)(n_features為總共的特征數(shù))，有如下6種情況：
如果max_features是整型的數(shù)，則考慮max_features個特征；
如果max_features是浮點型的數(shù)，則考慮int(max_features * n_features)個特征；
如果max_features設(shè)為auto，那么max_features = sqrt(n_features)；
如果max_features設(shè)為sqrt，那么max_featrues = sqrt(n_features)，跟auto一樣；
如果max_features設(shè)為log2，那么max_features = log2(n_features)；
如果max_features設(shè)為None，那么max_features = n_features，也就是所有特征都用。
一般來說，如果樣本特征數(shù)不多，比如小于50，我們用默認(rèn)的”None”就可以了，如果特征數(shù)非常多，我們可以靈活使用剛才描述的其他取值來控制劃分時考慮的最大特征數(shù)，以控制決策樹的生成時間。
max_depth：決策樹最大深，可選參數(shù)，默認(rèn)是None。這個參數(shù)是這是樹的層數(shù)的。層數(shù)的概念就是，比如在貸款的例子中，決策樹的層數(shù)是2層。如果這個參數(shù)設(shè)置為None，那么決策樹在建立子樹的時候不會限制子樹的深度。一般來說，數(shù)據(jù)少或者特征少的時候可以不管這個值?；蛘呷绻O(shè)置了min_samples_slipt參數(shù)，那么直到少于min_smaples_split個樣本為止。如果模型樣本量多，特征也多的情況下，推薦限制這個最大深度，具體的取值取決于數(shù)據(jù)的分布。常用的可以取值10-100之間。
min_samples_split：內(nèi)部節(jié)點再劃分所需最小樣本數(shù)，可選參數(shù)，默認(rèn)是2。這個值限制了子樹繼續(xù)劃分的條件。如果min_samples_split為整數(shù)，那么在切分內(nèi)部結(jié)點的時候，min_samples_split作為最小的樣本數(shù)，也就是說，如果樣本已經(jīng)少于min_samples_split個樣本，則停止繼續(xù)切分。如果min_samples_split為浮點數(shù)，那么min_samples_split就是一個百分比，ceil(min_samples_split * n_samples)，數(shù)是向上取整的。如果樣本量不大，不需要管這個值。如果樣本量數(shù)量級非常大，則推薦增大這個值。
min_weight_fraction_leaf：葉子節(jié)點最小的樣本權(quán)重和，可選參數(shù)，默認(rèn)是0。這個值限制了葉子節(jié)點所有樣本權(quán)重和的最小值，如果小于這個值，則會和兄弟節(jié)點一起被剪枝。一般來說，如果我們有較多樣本有缺失值，或者分類樹樣本的分布類別偏差很大，就會引入樣本權(quán)重，這時我們就要注意這個值了。
max_leaf_nodes：最大葉子節(jié)點數(shù)，可選參數(shù)，默認(rèn)是None。通過限制最大葉子節(jié)點數(shù)，可以防止過擬合。如果加了限制，算法會建立在最大葉子節(jié)點數(shù)內(nèi)最優(yōu)的決策樹。如果特征不多，可以不考慮這個值，但是如果特征分成多的話，可以加以限制，具體的值可以通過交叉驗證得到。
class_weight：類別權(quán)重，可選參數(shù)，默認(rèn)是None，也可以字典、字典列表、balanced。指定樣本各類別的的權(quán)重，主要是為了防止訓(xùn)練集某些類別的樣本過多，導(dǎo)致訓(xùn)練的決策樹過于偏向這些類別。類別的權(quán)重可以通過{class_label：weight}這樣的格式給出，這里可以自己指定各個樣本的權(quán)重，或者用balanced，如果使用balanced，則算法會自己計算權(quán)重，樣本量少的類別所對應(yīng)的樣本權(quán)重會高。當(dāng)然，如果你的樣本類別分布沒有明顯的偏倚，則可以不管這個參數(shù)，選擇默認(rèn)的None。
random_state：可選參數(shù)，默認(rèn)是None。隨機數(shù)種子。如果是證書，那么random_state會作為隨機數(shù)生成器的隨機數(shù)種子。隨機數(shù)種子，如果沒有設(shè)置隨機數(shù)，隨機出來的數(shù)與當(dāng)前系統(tǒng)時間有關(guān)，每個時刻都是不同的。如果設(shè)置了隨機數(shù)種子，那么相同隨機數(shù)種子，不同時刻產(chǎn)生的隨機數(shù)也是相同的。如果是RandomState instance，那么random_state是隨機數(shù)生成器。如果為None，則隨機數(shù)生成器使用np.random。
min_impurity_split：節(jié)點劃分最小不純度,可選參數(shù)，默認(rèn)是1e-7。這是個閾值，這個值限制了決策樹的增長，如果某節(jié)點的不純度(基尼系數(shù)，信息增益，均方差，絕對差)小于這個閾值，則該節(jié)點不再生成子節(jié)點。即為葉子節(jié)點 。
presort：數(shù)據(jù)是否預(yù)排序，可選參數(shù)，默認(rèn)為False，這個值是布爾值，默認(rèn)是False不排序。一般來說，如果樣本量少或者限制了一個深度很小的決策樹，設(shè)置為true可以讓劃分點選擇更加快，決策樹建立的更加快。如果樣本量太大的話，反而沒有什么好處。問題是樣本量少的時候，我速度本來就不慢。所以這個值一般懶得理它就可以了。
除了這些參數(shù)要注意以外，其他在調(diào)參時的注意點有：
當(dāng)樣本數(shù)量少但是樣本特征非常多的時候，決策樹很容易過擬合，一般來說，樣本數(shù)比特征數(shù)多一些會比較容易建立健壯的模型
如果樣本數(shù)量少但是樣本特征非常多，在擬合決策樹模型前，推薦先做維度規(guī)約，比如主成分分析（PCA），特征選擇（Losso）或者獨立成分分析（ICA）。這樣特征的維度會大大減小。再來擬合決策樹模型效果會好。
推薦多用決策樹的可視化，同時先限制決策樹的深度，這樣可以先觀察下生成的決策樹里數(shù)據(jù)的初步擬合情況，然后再決定是否要增加深度。
from sklearn.grid_search import GridSearchCV
tree_param_grid = { 'min_samples_split': list((3,6,9)),'n_estimators':list((10,50,100))}
grid = GridSearchCV(RandomForestRegressor(),param_grid=tree_param_grid, cv=5)
grid.fit(data_train, target_train)
grid.grid_scores_, grid.best_params_, grid.best_score_
rfr = RandomForestRegressor( min_samples_split=3,n_estimators = 100,random_state = 42)
rfr.fit(data_train, target_train)
rfr.score(data_test, target_test)
pd.Series(rfr.feature_importances_, index = housing.feature_names).sort_values(ascending = False)
九. 總結(jié)
優(yōu)點：
- 易于理解和解釋，決策樹可以可視化。
- 幾乎不需要數(shù)據(jù)預(yù)處理。其他方法經(jīng)常需要數(shù)據(jù)標(biāo)準(zhǔn)化，創(chuàng)建虛擬變量和刪除缺失值。決策樹還不支持缺失值。
- 使用樹的花費（例如預(yù)測數(shù)據(jù)）是訓(xùn)練數(shù)據(jù)點(data points)數(shù)量的對數(shù)。
- 可以同時處理數(shù)值變量和分類變量。其他方法大都適用于分析一種變量的集合。
- 可以處理多值輸出變量問題。
- 使用白盒模型。如果一個情況被觀察到，使用邏輯判斷容易表示這種規(guī)則。相反，如果是黑盒模型（例如人工神經(jīng)網(wǎng)絡(luò)），結(jié)果會非常難解釋。
- 即使對真實模型來說，假設(shè)無效的情況下，也可以較好的適用。
缺點： - 決策樹學(xué)習(xí)可能創(chuàng)建一個過于復(fù)雜的樹，并不能很好的預(yù)測數(shù)據(jù)。也就是過擬合。修剪機制（現(xiàn)在不支持），設(shè)置一個葉子節(jié)點需要的最小樣本數(shù)量，或者數(shù)的最大深度，可以避免過擬合。
- 決策樹可能是不穩(wěn)定的，因為即使非常小的變異，可能會產(chǎn)生一顆完全不同的樹。這個問題通過decision trees with an ensemble來緩解。
- 學(xué)習(xí)一顆最優(yōu)的決策樹是一個NP-完全問題under several aspects of optimality and even for simple concepts。因此，傳統(tǒng)決策樹算法基于啟發(fā)式算法，例如貪婪算法，即每個節(jié)點創(chuàng)建最優(yōu)決策。這些算法不能產(chǎn)生一個全家最優(yōu)的決策樹。對樣本和特征隨機抽樣可以降低整體效果偏差。
- 概念難以學(xué)習(xí)，因為決策樹沒有很好的解釋他們，例如，XOR, parity or multiplexer problems.
- 如果某些分類占優(yōu)勢，決策樹將會創(chuàng)建一棵有偏差的樹。因此，建議在訓(xùn)練之前，先抽樣使樣本均衡。
決策樹算法主要包括三個部分：特征選擇、樹的生成、樹的剪枝。常用算法有 ID3、C4.5、CART。
- 特征選擇。特征選擇的目的是選取能夠?qū)τ?xùn)練集分類的特征。特征選擇的關(guān)鍵是準(zhǔn)則：信息增益、信息增益比、Gini 指數(shù)；
- 決策樹的生成。通常是利用信息增益最大、信息增益比最大、Gini 指數(shù)最小作為特征選擇的準(zhǔn)則。從根節(jié)點開始，遞歸的生成決策樹。相當(dāng)于是不斷選取局部最優(yōu)特征，或?qū)⒂?xùn)練集分割為基本能夠正確分類的子集；
- 決策樹的剪枝。決策樹的剪枝是為了防止樹的過擬合，增強其泛化能力。包括預(yù)剪枝和后剪枝。
