天天看點
傳回

《統計學習方法》系列（5）1、理論講解2、代碼實作

  本篇對應全書第五章，講的是決策樹。決策樹（decision tree）是一種基本的分類與回歸方法。決策樹模型呈樹形結構，在分類問題中，表示基于特征對執行個體進行分類的過程。決策樹學習通常包括3個步驟：特征選擇、決策樹的生成和決策樹的修剪。決策樹學習常用的算法有ID3、C4.5和CART。

1、理論講解

  ID3和C4.5生成的決策樹隻能用于分類問題，而CART生成的決策樹既可用于分類問題也可用于回歸問題，是以本文主要讨論用于分類的決策樹，隻在CART部分講述用于回歸的決策樹。

1.1、基礎知識

  決策樹由結點（node）和有向邊（directed edge）組成。結點有兩種類型：内部結點（internal node）和葉結點（leaf node）。内部結點表示一個特征或屬性，葉結點表示一個類。

  用決策樹分類，從根結點開始，對執行個體的某一特征進行測試，根據測試結果，将執行個體配置設定到其子結點：這時，每一個子結點對應着該特征的一個取值。如此遞歸地對執行個體進行測試并配置設定，直至達到葉結點。最後将執行個體分到葉結點的類中。下面是一個決策樹的示意圖，矩形框和橢圓框分别表示内部結點和葉結點。

![在這裡插入圖檔描述](https://img-blog.csdn.net/20180922211138224)   決策樹的學習過程就是決策樹的生成過程，決策樹的生成基本遵循以下流程：

輸入：訓練集D，特征集A；

輸出：決策樹T。

（1）若D中所有執行個體屬于同一類 C k C_k Ck​，則T為單結點樹，并将類 C k C_k Ck​作為該結點的類标記，傳回T；

（2）若 A = ∅ A=\varnothing A=∅，或D中樣本在A上取值相同，則T為單結點樹，并将D中執行個體數最大的類 C k C_k Ck​作為該結點的類标記，傳回T；

（3）從A中選取最優劃分特征 A ∗ A^* A∗，對 A ∗ A^* A∗的每一可能值 a i a_i ai​，依 A ∗ = a i A^*=a_i A∗=ai​将D分割為若幹非空子集 D i D_i Di​，将 D i D_i Di​中執行個體數最大的類作為标記，建構子結點，由結點及其子結點構成樹T，傳回T；

（4）對第i個子結點，以 D i D_i Di​為訓練集，以 A − { A ∗ } A-\{A^*\} A−{A∗}為特征集，遞歸地調用步（1）～步（3），得到子樹 T i T_i Ti​，傳回 T i T_i Ti​。

  上述流程中，有幾個關鍵問題：1).如何選取最優劃分特征；2).資料怎麼分割；3).決策樹停止分裂的條件。

  第一個問題，實際上就是“特征選擇”，“特征選擇”的目的在于選取對訓練資料具有分類能力的特征，這樣可以提高決策樹學習的效率；如果利用一個特征進行分類的結果與随機分類的結果沒有很大差别，則稱這個特征是沒有分類能力的，經驗上扔掉這樣的特征對決策樹學習的精度影響不大；“特征選擇”的關鍵是其準則，不同的算法會有所不同，這一點後面我們還會詳細解釋，不過它們的本質都在于“選擇使得所有子結點資料最純的特征”。

  第二個問題，最優劃分特征 A ∗ A^* A∗，其資料屬性分離散和連續兩種，對于離散型資料，可以按照特征取值進行資料分割，每一個取值對應一個分裂點；對于連續型資料，不同的算法有不同的處理方式，後面我們再解釋。

  第三個問題，決策樹不能無限制分裂。一方面複雜度太高，易過拟合，泛化能力差；另一方面，分裂到後期容易受噪聲資料影響。停止分裂的條件一般有這麼幾個：a).最小結點數：當結點資料量小于門檻值時，停止分裂；b).熵或者基尼值小于門檻值：熵和基尼值的大小表示資料的複雜程度，當熵或者基尼值過小時，表示資料的純度比較大；c).決策樹的深度達到指定條件；d).特征集為空。

  決策樹生成的過程中，為了盡可能正确分類訓練集，結點進行了多次分裂，有時會造成決策樹分支過多而過拟合的情況。我們需要對已生成的樹進行剪枝，将樹變得更簡單，進而使它具有更好的泛化能力。

  常見的剪枝政策有預剪枝（pre-pruning）和後剪枝（post-pruning）。

  預剪枝，即在完全正确分類訓練集之前，較早地停止樹的生長，前面所講的決策樹停止分裂的條件即可看作是預剪枝。一種更普遍的做法是，根據驗證集，計算每次分裂對決策樹性能的增益，如果這個增益值小于某個門檻值則不進行分裂。預剪枝的優點在于算法簡單，效率高；缺點在于其基于“貪心”的本質，過早地停止決策樹的生長，可能帶來欠拟合的風險。

  後剪枝，即在已生成的過拟合決策樹上進行剪枝。主要的後剪枝政策有：REP（Reduced-Error Pruning，錯誤率降低剪枝）、PEP（Pessimistic Error Pruning，悲觀剪枝）、MEP（Minimum Error Pruning，最小錯誤率剪枝）、CCP（Cost-Complexity Pruning，代價複雜度剪枝）。這裡我們不贅述每種剪枝政策的細節，感興趣的讀者可閱讀[11]和[12]。

1.2、ID3、C4.5和CART

  1984年，Breiman等人提出CART；1986年，Quinlan提出ID3；1993年，Quinlan提出C4.5。ID3和C4.5是分類樹，C4.5是對ID3的優化，CART是分類和回歸樹。

  由于關于此三種算法的介紹很多，是以本節會省略不必要的細節，隻保留重要的結論性的内容講述。

1.2.1、ID3

特性：

  最優特征選取準則：資訊增益（information gain）；

  資料分割：離散型資料，按取值進行分割；連續型資料，無法處理，隻能将連續型資料離散化（如等距離資料劃分）後再做處理；

  資料預設值處理：無；

  剪枝：無。

缺點：

  1. 以資訊增益作為特征選取準則，存在偏向于選取取值較多的特征的問題；
  2. 無法處理連續資料和資料預設值；
  3. 未剪枝，可能過拟合。

1.2.2、C4.5

特性：

  最優特征選取準則：資訊增益比（information gain ratio），這裡需要注意的是，資訊增益比準則對可取值數目較少的特征有所偏好，是以C4.5采用的是一個啟發式的方法：先從候選特征中找出資訊增益高于平均水準的特征，再從中選擇資訊增益比最高的；

  資料分割：離散型資料，同ID3；連續型資料，對于特征a的n個取值，将它們從小到大排序，求得n個取值的n-1個資料中點，對每一個資料中點 t i t_i ti​，根據特征取值大于或小于 t i t_i ti​對資料進行二分，計算特征a在每個資料中點 t i t_i ti​的資訊增益，選取資訊增益最大的 t i t_i ti​作為特征a的分裂點，再在不同特征之間根據資訊增益比選擇最優劃分特征（與離散特征不同的是，如果目前結點為連續特征，則該特征後面還可參與子結點的産生選擇過程）；

  資料預設值處理：有，具體請參考《機器學習》（周志華 著）；

  剪枝：PEP。

缺點：

  1. C4.5生成的是多叉樹，很多時候，在計算機中二叉樹模型會比多叉樹計算效率高；
  2. C4.5隻能用于分類；
  3. C4.5使用了熵模型，其中有大量耗時的對數運算，如果是連續值還有大量的排序運算。

1.2.3、CART

  CART（Classification And Regression Tree，分類和回歸樹）既可用于分類也可用于回歸。CART假設決策樹是二叉樹，遞歸地二分每個特征。

特性：

  最優特征選取準則：最小方差（回歸樹），基尼指數（分類樹）；

  資料分割：離散型資料，将其中一個離散值獨立作為一個節點，其他的離散值生成另外一個節點，有多少個離散值就有多少種可供選擇的劃分方式（分裂後，若某一分支上的被選取特征取值多于1個，被選取特征依然可參與到後續結點的産生選擇過程）；連續型資料，同C4.5；

  資料預設值處理：同C4.5；

  剪枝：CCP。

1.3、其它

  1. 從所有可能的決策樹中選取最優決策樹是NP完全問題，是以現實中決策樹學習算法通常采用啟發式方法，近似求解這一最優化問題，這樣得到的決策樹是次最優（sub-optimal）的；
  2. 決策樹的生成對應于模型的局部選擇，決策樹的剪枝對應于模型的全局選擇；
  3. 如果特征數量很多，也可以在決策樹學習開始的時候，對特征進行選擇，隻留下對訓練資料有足夠分類能力的特征；
  4. 決策樹的剪枝往往通過極小化決策樹整體的損失函數來實作；

2、代碼實作

2.1、sklearn實作 

from __future__ import division
import numpy as np
import graphviz
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn import tree
from sklearn.model_selection import train_test_split


if __name__ == "__main__":
        iris = load_iris()
        X = iris.data
        y = iris.target

        X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.2, random_state = 0)

        clf = DecisionTreeClassifier()
        clf.fit(X_train, y_train)
        score = clf.score(X_test, y_test)
        print "score : %s" % score

        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 = graphviz.Source(dot_data)
        graph.render("iris")

代碼已上傳至github：https://github.com/xiongzwfire/statistical-learning-method

#參考文獻

[1] 《機器學習》（周志華 著）

[2] http://www.cnblogs.com/yonghao/p/5061873.html

[3] http://www.cnblogs.com/yonghao/p/5064996.html

[4] http://www.cnblogs.com/yonghao/p/5096358.html

[5] http://www.cnblogs.com/yonghao/p/5122703.html

[6] https://www.cnblogs.com/yonghao/p/5135386.html

[7] http://www.cnblogs.com/pinard/p/6050306.html

[8] http://www.cnblogs.com/pinard/p/6053344.html

[9] http://www.cnblogs.com/pinard/p/6056319.html

[10] https://www.zhihu.com/question/22697086

[11] https://zhuanlan.zhihu.com/p/30296061

[12] http://blog.sina.com.cn/s/blog_4e4dec6c0101fdz6.html

[13] https://blog.csdn.net/jiede1/article/details/76034328

[14] https://blog.csdn.net/baimafujinji/article/details/53269040

[15] https://www.zhihu.com/question/27205203?sort=created

[16] https://blog.csdn.net/mao_xiao_feng/article/details/52728164

[17] https://www.cnblogs.com/pinard/p/6140514.html

[18] https://zhuanlan.zhihu.com/p/30296061

[19] http://blog.sina.com.cn/s/blog_4e4dec6c0101fdz6.html

以上為本文的全部參考文獻，對原作者表示感謝。

機器學習 決策樹 ID3 C4.5 CART
上一篇: 常見決策樹算法（ID3、C4.5、CART）
下一篇: Vuex是否可以了解成為元件間的通信機制

繼續閱讀