寫在之前
想看程序參數(shù)說明的請到：
- http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html
- http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html#sklearn.tree.DecisionTreeRegressor
-
http://www.th7.cn/Program/Python/201604/830424.shtml
本文是Scikit-learn中的決策樹算法的原理、應(yīng)用的介紹。歡迎轉(zhuǎn)載歼捏，轉(zhuǎn)載注明出處即可。如有錯誤境钟，請指正。
正文部分
決策樹是一個非參數(shù)的監(jiān)督式學(xué)習(xí)方法，主要用于分類和回歸饲齐。算法的目標(biāo)是通過推斷數(shù)據(jù)特征诫隅，學(xué)習(xí)決策規(guī)則從而創(chuàng)建一個預(yù)測目標(biāo)變量的模型腐魂。如下如所示，決策樹通過一系列if-then-else 決策規(guī)則 近似估計一個正弦曲線逐纬。
決策樹優(yōu)勢：
- 簡單易懂蛔屹，原理清晰，決策樹可以實現(xiàn)可視化
- 數(shù)據(jù)準(zhǔn)備簡單豁生。其他的方法需要實現(xiàn)數(shù)據(jù)歸一化兔毒，創(chuàng)建虛擬變量，刪除空白變量甸箱。(注意：這個模塊不支持缺失值)
- 使用決策樹的代價是數(shù)據(jù)點的對數(shù)級別育叁。
- 能夠處理數(shù)值和分類數(shù)據(jù)
- 能夠處理多路輸出問題
- 使用白盒子模型(內(nèi)部結(jié)構(gòu)可以直接觀測的模型)。一個給定的情況是可以觀測的摇肌，那么就可以用布爾邏輯解釋這個結(jié)果擂红。相反，如果在一個黑盒模型(ANN)围小，結(jié)果可能很難解釋
- 可以通過統(tǒng)計學(xué)檢驗驗證模型昵骤。這也使得模型的可靠性計算變得可能
- 即使模型假設(shè)違反產(chǎn)生數(shù)據(jù)的真實模型，表現(xiàn)性能依舊很好肯适。
決策樹劣勢：
- 可能會建立過于復(fù)雜的規(guī)則变秦，即過擬合。為避免這個問題框舔，剪枝蹦玫、設(shè)置葉節(jié)點的最小樣本數(shù)量、設(shè)置決策樹的最大深度有時候是必要的刘绣。
- 決策樹有時候是不穩(wěn)定的樱溉，因為數(shù)據(jù)微小的變動，可能生成完全不同的決策樹纬凤。 可以通過總體平均(ensemble)減緩這個問題福贞。應(yīng)該指的是多次實驗。
- 學(xué)習(xí)最優(yōu)決策樹是一個NP完全問題停士。所以挖帘，實際決策樹學(xué)習(xí)算法是基于試探性算法完丽，例如在每個節(jié)點實現(xiàn)局部最優(yōu)值的貪心算法。這樣的算法是無法保證返回一個全局最優(yōu)的決策樹拇舀÷咦澹可以通過隨機(jī)選擇特征和樣本訓(xùn)練多個決策樹來緩解這個問題。
- 有些問題學(xué)習(xí)起來非常難骄崩，因為決策樹很難表達(dá)聘鳞。如：異或問題、奇偶校驗或多路復(fù)用器問題
- 如果有些因素占據(jù)支配地位要拂，決策樹是有偏的搁痛。因此建議在擬合決策樹之前先平衡數(shù)據(jù)的影響因子。
分類
DecisionTreeClassifier 能夠?qū)崿F(xiàn)多類別的分類宇弛。輸入兩個向量：向量X，大小為[n_samples,n_features]源请，用于記錄訓(xùn)練樣本枪芒；向量Y，大小為[n_samples]谁尸，用于存儲訓(xùn)練樣本的類標(biāo)簽舅踪。
from sklearn import tree
X = [[0, 0], [1, 1]]
Y = [0, 1]
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X, Y)
clf.predict([[2., 2.]])
clf.predict_proba([[2., 2.]]) #計算屬于每個類的概率
能夠?qū)崿F(xiàn)二進(jìn)制分類和多分類。使用Isis數(shù)據(jù)集良蛮，有：
from sklearn.datasets import load_iris
from sklearn import tree
iris = load_iris()
clf = tree.DecisionTreeClassifier()
clf = clf.fit(iris.data, iris.target)
# export the tree in Graphviz format using the export_graphviz exporter
with open("iris.dot", 'w') as f:
f = tree.export_graphviz(clf, out_file=f)
# predict the class of samples
clf.predict(iris.data[:1, :])
# the probability of each class
clf.predict_proba(iris.data[:1, :])
安裝Graphviz將其添加到環(huán)境變量抽碌，使用dot創(chuàng)建一個PDF文件。dot -Tpdf iris.dot -o iris.pdf
# 刪除dot文件
import os
os.unlink('iris.dot')
如果安裝了pydotplus决瞳，也可以在Python中直接生成：
import pydotplus
dot_data = tree.export_graphviz(clf, out_file=None)
graph = pydotplus.graph_from_dot_data(dot_data)
graph.write_pdf("iris.pdf")
可以根據(jù)不同的類別輸出不同的顏色货徙，也可以指定類別名字。
from IPython.display import Image
dot_data = tree.export_graphviz(clf, out_file=None,
feature_names=iris.feature_names,
class_names=iris.target_names,
filled=True, rounded=True,
special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data)
Image(graph.create_png())
更多地可以看到分類的效果：
回歸
和分類不同的是向量y可以是浮點數(shù)皮胡。
from sklearn import tree
X = [[0, 0], [2, 2]]
y = [0.5, 2.5]
clf = tree.DecisionTreeRegressor()
clf = clf.fit(X, y)
clf.predict([[1, 1]])
# Import the necessary modules and libraries
import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt
# Create a random dataset
rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80, 1), axis=0)
y = np.sin(X).ravel()
y[::5] += 3 * (0.5 - rng.rand(16))
# Fit regression model
regr_1 = DecisionTreeRegressor(max_depth=2)
regr_2 = DecisionTreeRegressor(max_depth=5)
regr_1.fit(X, y)
regr_2.fit(X, y)
# Predict
X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
y_1 = regr_1.predict(X_test)
y_2 = regr_2.predict(X_test)
# Plot the results
plt.figure()
plt.scatter(X, y, c="darkorange", label="data")
plt.plot(X_test, y_1, color="cornflowerblue", label="max_depth=2", linewidth=2)
plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=5", linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()
多輸出問題
多輸出問題時需要預(yù)測多個輸出的監(jiān)督式學(xué)習(xí)問題痴颊。即Y是一個2d的向量，大小為[n_samples, n_outputs]屡贺。
當(dāng)輸出之間不相關(guān)時蠢棱，一個簡單的解決辦法是建立n個獨立模型。對于每一個輸出甩栈，使用這些模型獨立預(yù)測這每個輸出泻仙。由于輸出是和相同的輸入相關(guān)的，所以一個更好的辦法是建立一個能夠持續(xù)預(yù)測所有輸出的單一模型量没。首先玉转，系統(tǒng)需要的訓(xùn)練時間更少了，因為只建立了一個模型允蜈。其次準(zhǔn)確性也會得到提高冤吨。
決策樹的策略需要修改以支持多分類問題蒿柳。
- 葉子上存儲n個輸出變量
- 使用不同的標(biāo)準(zhǔn)計算所有n輸出的平均減少
這一節(jié)是關(guān)于 DecisionTreeClassifier 和DecisionTreeRegressor的一些知識點。如果一個決策樹的輸出向量Y大小為[n_samples, n_outputs]漩蟆，預(yù)測量有：
- predict：輸出n個預(yù)測值
- predict_proba：輸出有n個輸出的向量組成的列表垒探。
多輸出的回歸的例子：輸入X是一個單一的值，輸出Y是輸入X的Sine和Cosine怠李。
Multi-output Decision Tree Regression
多輸出的分類的例子：Face completion with a multi-output estimators
輸入X是上半臉的像素圾叼，輸出Y是下半臉的像素。
參考文獻(xiàn)：
- M. Dumont et al, Fast multi-class image annotation with random subwindows and multiple output randomized trees, International Conference on Computer Vision Theory and Applications 2009
復(fù)雜度
通常生成一個二進(jìn)制樹運(yùn)行時間為
惕鼓，使得整個樹的消耗為
使用小貼士
- 如果數(shù)據(jù)量大蝉衣，決策樹容易過擬合。樣本和特征的比例非常重要仲智。如果決策樹樣本少买乃，特征多，非车隽荆可能過擬合剪验。
- 可以考慮事先做維度約減(PCA，ICA)前联，以產(chǎn)生一個特征之間區(qū)別性大的決策樹
- 通過
export將你的訓(xùn)練的決策樹可視化功戚，使用max_depth =3作為一個初始的樹的深度，有一個數(shù)據(jù)擬合決策樹模型的大概感覺似嗤，然后逐漸增加深度 - 數(shù)據(jù)的樣本量的增加將加深決策樹的深度啸臀，使用
max_depth控制決策樹的尺寸以防止過擬合 - 使用
min_samples_split或者min_samples_leaf來控制葉節(jié)點的樣本數(shù)量。一個非常小的數(shù)量往往意味著過擬合，而一個較大的數(shù)可以防止過擬合乘粒⊥阕ⅲ可以將min_samples_leaf=5作為一個初始值。如果樣本數(shù)據(jù)變化巨大灯萍，可以采用一個浮點數(shù)轧铁。兩者的區(qū)別在于min_samples_leaf保證了葉節(jié)點最小的數(shù)量，min_samples_split能夠建立任意數(shù)量的葉子節(jié)點旦棉，在文學(xué)上用到也更多 - 如果樣本是有權(quán)重的齿风，可以使用
min_weight_fraction_leaf來實現(xiàn)基于權(quán)重的預(yù)修剪規(guī)則來優(yōu)化決策樹結(jié)構(gòu) - 決策樹內(nèi)部使用
np.float32向量，如果樣本不是這個形式的绑洛，將產(chǎn)生一個數(shù)據(jù)集的樣本 - 如果數(shù)據(jù)矩陣X是非常稀疏的剂娄，建議在擬合和預(yù)測之前轉(zhuǎn)換為稀疏矩陣
csc_matrix甸鸟。稀疏矩陣將比稠密矩陣快數(shù)量級的速度
決策樹算法：ID3,C4.5,C5.0,CART
ID3是由Ross Quinlan在1985年建立的。這個方法建立多路決策樹幼苛，并找到最大的信息增益废登。當(dāng)樹長到最大的尺寸咽弦，經(jīng)常應(yīng)用剪枝來提高決策樹對未知數(shù)據(jù)的一般化势木。
C4.5是ID3的進(jìn)一步延伸易猫，通過將連續(xù)屬性離散化，去除了特征的限制晾匠。C4.5將訓(xùn)練樹轉(zhuǎn)換為一系列if-then的語法規(guī)則√莞眨可確定這些規(guī)則的準(zhǔn)確性凉馆，從而決定哪些應(yīng)該被采用。如果去掉某項規(guī)則亡资，準(zhǔn)確性能提高澜共，則應(yīng)該實行修剪。
C5.0較C4.5使用更小的內(nèi)存锥腻，建立更小的決策規(guī)則嗦董，更加準(zhǔn)確。
CART和C4.5很相似瘦黑，但是它支持?jǐn)?shù)值的目標(biāo)變量（回歸）且不產(chǎn)生決策規(guī)則京革。CART使用特征和閾值在每個節(jié)點獲得最大的信息增益來構(gòu)建決策樹。
scikit-learn使用一個最佳的CART算法
數(shù)學(xué)公式
訓(xùn)練向量
分類標(biāo)準(zhǔn)
類k在節(jié)點m的比例：
回歸標(biāo)準(zhǔn)
| 函數(shù) | 函數(shù)功能 |
|---|---|
apply(X[, check_input]) |
返回每個樣本的葉節(jié)點的預(yù)測序號 |
decision_path(X[, check_input]) |
返回決策樹的決策路徑 [n_samples, n_nodes] |
fit(X, y[, sample_weight, check_input, ...]) |
從訓(xùn)練數(shù)據(jù)建立決策樹，返回一個對象 |
| fit_transform(X[, y]) | 將數(shù)據(jù)X轉(zhuǎn)換[n_samples, n_features_new] |
| get_params([deep]) | 得到估計量的參數(shù)冰悠，返回一個映射 |
| predict(X[, check_input]) | 預(yù)測X的分類或者回歸堡妒，返回[n_samples] |
| predict_log_proba(X) | 預(yù)測輸入樣本的對數(shù)概率，返回[n_samples, n_classes] |
| predict_proba(X[, check_input]) | 預(yù)測輸入樣本的屬于各個類的概率[n_samples, n_classes] |
| score(X, y[, sample_weight]) | 返回對于測試數(shù)據(jù)的平均準(zhǔn)確率 |
| set_params(**params) | 設(shè)置估計量的參數(shù) |
| transform(*args, **kwargs) | 將輸入?yún)?shù)X減少的最重要的特征屿脐，返回[n_samples, n_selected_features] |
- https://en.wikipedia.org/wiki/Decision_tree_learning
- https://en.wikipedia.org/wiki/Predictive_analytics
- L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984.
- J.R. Quinlan. C4. 5: programs for machine learning. Morgan Kaufmann, 1993.
- T. Hastie, R. Tibshirani and J. Friedman. Elements of Statistical Learning, Springer, 2009.
