# 1.10. 決策樹 校驗者: [@文誼](https://github.com/apachecn/scikit-learn-doc-zh) [@皮卡乒的皮卡乓](https://github.com/apachecn/scikit-learn-doc-zh) 翻譯者: [@I Remember](https://github.com/apachecn/scikit-learn-doc-zh) **Decision Trees (DTs)** 是一種用來 [classification](#tree-classification) 和 [regression](#tree-regression) 的無參監督學習方法。其目的是創建一種模型從數據特征中學習簡單的決策規則來預測一個目標變量的值。 例如，在下面的圖片中，決策樹通過if-then-else的決策規則來學習數據從而估測數一個正弦圖像。決策樹越深入，決策規則就越復雜并且對數據的擬合越好。 [](../auto_examples/tree/plot_tree_regression.html) 決策樹的優勢: > - 便于理解和解釋。樹的結構可以可視化出來。 > > > - 訓練需要的數據少。其他機器學習模型通常需要數據規范化，比如構建虛擬變量和移除缺失值,不過請注意，這種模型不支持缺失值。 > > - 由于訓練決策樹的數據點的數量導致了決策樹的使用開銷呈指數分布(訓練樹模型的時間復雜度是參與訓練數據點的對數值)。 > - 能夠處理數值型數據和分類數據。其他的技術通常只能用來專門分析某一種變量類型的數據集。詳情請參閱算法。 > - 能夠處理多路輸出的問題。 > - 使用白盒模型。如果某種給定的情況在該模型中是可以觀察的，那么就可以輕易的通過布爾邏輯來解釋這種情況。相比之下，在黑盒模型中的結果就是很難說明清 楚地。 > - 可以通過數值統計測試來驗證該模型。這對事解釋驗證該模型的可靠性成為可能。 > - 即使該模型假設的結果與真實模型所提供的數據有些違反，其表現依舊良好。 決策樹的缺點包括: > - 決策樹模型容易產生一個過于復雜的模型,這樣的模型對數據的泛化性能會很差。這就是所謂的過擬合.一些策略像剪枝、設置葉節點所需的最小樣本數或設置數的最大深度是避免出現 該問題最為有效地方法。 > - 決策樹可能是不穩定的，因為數據中的微小變化可能會導致完全不同的樹生成。這個問題可以通過決策樹的集成來得到緩解 > - 在多方面性能最優和簡單化概念的要求下，學習一棵最優決策樹通常是一個NP難問題。因此，實際的決策樹學習算法是基于啟發式算法，例如在每個節點進 行局部最優決策的貪心算法。這樣的算法不能保證返回全局最優決策樹。這個問題可以通過集成學習來訓練多棵決策樹來緩解,這多棵決策樹一般通過對特征和樣本有放回的隨機采樣來生成。 > - 有些概念很難被決策樹學習到,因為決策樹很難清楚的表述這些概念。例如XOR，奇偶或者復用器的問題。 > - 如果某些類在問題中占主導地位會使得創建的決策樹有偏差。因此，我們建議在擬合前先對數據集進行平衡。 ## 1.10.1. 分類 [`DecisionTreeClassifier`](generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier "sklearn.tree.DecisionTreeClassifier") 是能夠在數據集上執行多分類的類,與其他分類器一樣，[`DecisionTreeClassifier`](generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier "sklearn.tree.DecisionTreeClassifier") 采用輸入兩個數組：數組X，用 `[n_samples, n_features]` 的方式來存放訓練樣本。整數值數組Y，用 `[n_samples]` 來保存訓練樣本的類標簽: ``` >>> from sklearn import tree >>> X = [[0, 0], [1, 1]] >>> Y = [0, 1] >>> clf = tree.DecisionTreeClassifier() >>> clf = clf.fit(X, Y) ``` 執行通過之后，可以使用該模型來預測樣本類別: ``` >>> clf.predict([[2., 2.]]) array([1]) ``` 另外，也可以預測每個類的概率，這個概率是葉中相同類的訓練樣本的分數: ``` >>> clf.predict_proba([[2., 2.]]) array([[ 0., 1.]]) ``` [`DecisionTreeClassifier`](generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier "sklearn.tree.DecisionTreeClassifier") 既能用于二分類（其中標簽為\[-1,1\]）也能用于多分類（其中標簽為\[0,…,k-1\]）。使用Lris數據集，我們可以構造一個決策樹，如下所示: ``` >>> from sklearn.datasets import load_iris >>> from sklearn import tree >>> iris = load_iris() >>> clf = tree.DecisionTreeClassifier() >>> clf = clf.fit(iris.data, iris.target) ``` 經過訓練，我們可以使用 [`export_graphviz`](generated/sklearn.tree.export_graphviz.html#sklearn.tree.export_graphviz "sklearn.tree.export_graphviz") 導出器以 [Graphviz](http://www.graphviz.org/) 格式導出決策樹. 如果你是用 [conda](http://conda.io) 來管理包，那么安裝 graphviz 二進制文件和 python 包可以用以下指令安裝 > conda install python-graphviz 或者，可以從 graphviz 項目主頁下載 graphviz 的二進制文件，并從 pypi 安裝 Python 包裝器，并安裝 pip install graphviz .以下是在整個 iris 數據集上訓練的上述樹的 graphviz 導出示例; 其結果被保存在 iris.pdf 中: ``` >>> import graphviz # doctest: +SKIP >>> dot_data = tree.export_graphviz(clf, out_file=None) # doctest: +SKIP >>> graph = graphviz.Source(dot_data) # doctest: +SKIP >>> graph.render("iris") # doctest: +SKIP :func:`export_graphviz` 出導出還支持各種美化，包括通過他們的類著色節點（或回歸值），如果需要，使用顯式變量和類名。Jupyter notebook也可以自動找出相同的模塊:: >>> dot_data = tree.export_graphviz(clf, out_file=None, # doctest: +SKIP feature_names=iris.feature_names, # doctest: +SKIP class_names=iris.target_names, # doctest: +SKIP filled=True, rounded=True, # doctest: +SKIP special_characters=True) # doctest: +SKIP >>> graph = graphviz.Source(dot_data) # doctest: +SKIP >>> graph # doctest: +SKIP ```  執行通過之后，可以使用該模型預測樣品類別: ``` >>> clf.predict(iris.data[:1, :]) array([0]) ``` 或者，可以根據決策樹葉子樹里訓練樣本中的相同類的分數，使得類預測成為可能: ``` >>> clf.predict_proba(iris.data[:1, :]) array([[ 1., 0., 0.]]) ``` [](../auto_examples/tree/plot_iris.html) 示例: - [Plot the decision surface of a decision tree on the iris dataset](../auto_examples/tree/plot_iris.html#sphx-glr-auto-examples-tree-plot-iris-py) ## 1.10.2. 回歸 [](../auto_examples/tree/plot_tree_regression.html) 決策樹通過使用 [`DecisionTreeRegressor`](generated/sklearn.tree.DecisionTreeRegressor.html#sklearn.tree.DecisionTreeRegressor "sklearn.tree.DecisionTreeRegressor") 類也可以用來解決回歸問題。如在分類設置中，擬合方法將數組X和數組y作為參數，只有在這種情況下，y數組預期才是浮點值: ``` >>> 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]]) array([ 0.5]) ``` 示例: - [Decision Tree Regression](../auto_examples/tree/plot_tree_regression.html#sphx-glr-auto-examples-tree-plot-tree-regression-py) ## 1.10.3. 多值輸出問題 一個多值輸出問題是一個類似當 Y 是大小為當 Y 是大小為 `[n_samples, n_outputs]` 的2d數組時，有多個輸出值需要預測的監督學習問題。 當輸出值之間沒有關聯時，一個很簡單的處理該類型的方法是建立一個n獨立模型，即每個模型對應一個輸出，然后使用這些模型來獨立地預測n個輸出中的每一個。然而，由于可能與相同輸入相關的輸出值本身是相關的，所以通常更好的方法是構建能夠同時預測所有n個輸出的單個模型。首先，因為僅僅是建立了一個模型所以訓練時間會更短。第二，最終模型的泛化性能也會有所提升。對于決策樹，這一策略可以很容易地用于多輸出問題。 這需要以下更改： > - 在葉中存儲n個輸出值，而不是一個; > - 通過計算所有n個輸出的平均減少量來作為分裂標準. 該模塊通過在 `DecisionTreeClassifier `和 :class:`DecisionTreeRegressor` 中實現該策略來支持多輸出問題。如果決策樹與大小為 `[n_samples, n_outputs]` 的輸出數組Y向匹配，則得到的估計器將: ``` * ``predict`` 是輸出n_output的值 * 在 ``predict_proba`` 上輸出 n_output 數組列表 ``` 用多輸出決策樹進行回歸分析 [Multi-output Decision Tree Regression](../auto_examples/tree/plot_tree_regression_multioutput.html#sphx-glr-auto-examples-tree-plot-tree-regression-multioutput-py) 。 在該示例中，輸入X是單個實數值，并且輸出Y是X的正弦和余弦。 [](../auto_examples/tree/plot_tree_regression_multioutput.html) 使用多輸出樹進行分類，在 [Face completion with a multi-output estimators](../auto_examples/plot_multioutput_face_completion.html#sphx-glr-auto-examples-plot-multioutput-face-completion-py) 中進行了演示。 在該示例中，輸入X是面的上半部分的像素，并且輸出Y是這些面的下半部分的像素。 [](../auto_examples/plot_multioutput_face_completion.html) 示例: - [Multi-output Decision Tree Regression](../auto_examples/tree/plot_tree_regression_multioutput.html#sphx-glr-auto-examples-tree-plot-tree-regression-multioutput-py) - [Face completion with a multi-output estimators](../auto_examples/plot_multioutput_face_completion.html#sphx-glr-auto-examples-plot-multioutput-face-completion-py) 參考: - M. Dumont et al, [Fast multi-class image annotation with random subwindows and multiple output randomized trees](http://www.montefiore.ulg.ac.be/services/stochastic/pubs/2009/DMWG09/dumont-visapp09-shortpaper.pdf), International Conference on Computer Vision Theory and Applications 2009 ## 1.10.4. 復雜度分析 總體來說，用來構建平衡二叉樹的運行時間為  查詢時間為  。盡管樹的構造算法嘗試生成平衡樹，但它們并不總能保持平衡。假設子樹能大概保持平衡，每個節點的成本包括通過  時間復雜度來搜索找到提供熵減小最大的特征。每個節點的花費為  ，從而使得整個決策樹的構造成本為  。 Scikit-learn提供了更多有效的方法來創建決策樹。初始實現（如上所述）將重新計算沿著給定特征的每個新分割點的類標簽直方圖（用于分類）或平均值（用于回歸）。與分類所有的樣本特征，然后再次訓練時運行標簽計數，可將每個節點的復雜度降低為  ，則總的成本花費為  。這是一種對所有基于樹的算法的改進選項。默認情況下，對于梯度提升模型該算法是打開的，一般來說它會讓訓練速度更快。但對于所有其他算法默認是關閉的，當訓練深度很深的樹時往往會減慢訓練速度。 ## 1.10.5. 實際使用技巧 > > - 對于擁有大量特征的數據決策樹會出現過擬合的現象。獲得一個合適的樣本比例和特征數量十分重要，因為在高維空間中只有少量的樣本的樹是十分容易過擬合的。 > > - 考慮事先進行降維( [PCA](decomposition.html#pca) , [ICA](decomposition.html#ica) ，使您的樹更好地找到具有分辨性的特征。 > > - 通過 `export` 功能可以可視化您的決策樹。使用 `max_depth=3` 作為初始樹深度，讓決策樹知道如何適應您的數據，然后再增加樹的深度。 > > - 請記住，填充樹的樣本數量會增加樹的每個附加級別。使用 `max_depth` 來控制輸的大小防止過擬合。 > > - 通過使用 `min_samples_split` 和 `min_samples_leaf` 來控制葉節點上的樣本數量。當這個值很小時意味著生成的決策樹將會過擬合，然而當這個值很大時將會不利于決策樹的對樣本的學習。所以嘗試 `min_samples_leaf=5` 作為初始值。如果樣本的變化量很大，可以使用浮點數作為這兩個參數中的百分比。兩者之間的主要區別在于 `min_samples_leaf` 保證葉結點中最少的采樣數，而 `min_samples_split` 可以創建任意小的葉子，盡管在文獻中 `min_samples_split` 更常見。 > > - 在訓練之前平衡您的數據集，以防止決策樹偏向于主導類.可以通過從每個類中抽取相等數量的樣本來進行類平衡，或者優選地通過將每個類的樣本權重 (`sample_weight`) 的和歸一化為相同的值。還要注意的是，基于權重的預修剪標準 (`min_weight_fraction_leaf`) 對于顯性類別的偏倚偏小，而不是不了解樣本權重的標準，如 `min_samples_leaf` 。 > > - 如果樣本被加權，則使用基于權重的預修剪標準 `min_weight_fraction_leaf` 來優化樹結構將更容易，這確保葉節點包含樣本權重的總和的至少一部分。 > - 所有的決策樹內部使用 `np.float32` 數組 ，如果訓練數據不是這種格式，將會復制數據集。 > - 如果輸入的矩陣X為稀疏矩陣，建議您在調用fit之前將矩陣X轉換為稀疏的``csc\_matrix`` ,在調用predict之前將 `csr_matrix` 稀疏。當特征在大多數樣本中具有零值時，與密集矩陣相比，稀疏矩陣輸入的訓練時間可以快幾個數量級。 ## 1.10.6. 決策樹算法: ID3, C4.5, C5.0 和 CART 所有種類的決策樹算法有哪些以及它們之間的區別？scikit-learn 中實現何種算法呢？ ID3（Iterative Dichotomiser 3）由 Ross Quinlan 在1986年提出。該算法創建一個多路樹，找到每個節點（即以貪心的方式）分類特征，這將產生分類目標的最大信息增益。決策樹發展到其最大尺寸，然后通常利用剪枝來提高樹對未知數據的泛華能力。 C4.5 是 ID3 的后繼者，并且通過動態定義將連續屬性值分割成一組離散間隔的離散屬性（基于數字變量），消除了特征必須被明確分類的限制。C4.5 將訓練的樹（即，ID3算法的輸出）轉換成 if-then 規則的集合。然后評估每個規則的這些準確性，以確定應用它們的順序。如果規則的準確性沒有改變，則需要決策樹的樹枝來解決。 C5.0 是 Quinlan 根據專有許可證發布的最新版本。它使用更少的內存，并建立比 C4.5 更小的規則集，同時更準確。 CART（Classification and Regression Trees （分類和回歸樹））與 C4.5 非常相似，但它不同之處在于它支持數值目標變量（回歸），并且不計算規則集。CART 使用在每個節點產生最大信息增益的特征和閾值來構造二叉樹。 scikit-learn 使用 CART 算法的優化版本。 ## 1.10.7. 數學表達 給定訓練向量 , i=1,…, l 和標簽向量 。決策樹遞歸地分割空間，例如將有相同標簽的樣本歸為一組。 將  節點上的數據用  來表示。每一個候選組  包含一個特征  和閾值  將,數據分成  和  子集。  使用不純度函數  計算  處的不純度,其選擇取決于正在解決的任務（分類或回歸）  選擇使不純度最小化的參數  重新計算子集  和  ，直到達到最大允許深度， 或 。 ### 1.10.7.1. 分類標準 對于節點  ，表示具有  個觀測值的區域  ，如果分類結果采用值是 0,1,…,K-1 的值，讓  是節點  中k類觀測的比例通常用來處理雜質的方法是Gini  Cross-Entropy （交叉熵）  和 Misclassification （錯誤分類）  在  訓練  節點上的數據時。 ### 1.10.7.2. 回歸標準 如果目標是連續性的值，那么對于節點  ,表示具有  個觀測值的區域  ，對于以后的分裂節點的位置的決定常用的最小化標準是均方差和平均絕對誤差，前者使用終端節點處的平均值來最小化L2誤差，后者使用終端節點處的中值來最小化 L1 誤差。 Mean Squared Error （均方誤差）:  Mean Absolute Error（平均絕對誤差）:  在  訓練  節點上的數據時。 示例: - [https://en.wikipedia.org/wiki/Decision\_tree\_learning](https://en.wikipedia.org/wiki/Decision_tree_learning) - [https://en.wikipedia.org/wiki/Predictive\_analytics](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.